Data Mining

Ce document présente une introduction à la classification de textes par la méthode de Naïve Bayes, destinée aux étudiants en data mining ou apprentissage automatique. Il illustre la démarche à partir d'un corpus d'emails étiquetés spam ou non-spam, en détaillant la préparation des données, la représentation des textes, la construction du modèle et la classification d’un nouvel email.

Le problème et les données

Le but est de construire un classifieur Naïve Bayes capable de détecter si un email est un spam ou non. Le corpus utilisé contient 1000 emails, chacun marqué comme spam ou non-spam, provenant du SpamAssassin Public Corpus (http://spamassassin.apache.org/publiccorpus/).

Exemples d'emails :

• Email no. 1 (non-spam) :

  Anyone knows how much it costs to host a web portal ?
  Well, it depends on how many visitors you're expecting.
  This can be anywhere from less than 10 bucks a month to a couple of $100.
  You should checkout http://www.rackspace.com/ or perhaps Amazon EC2 if youre running something big..

• Email no. 2 (spam) :

  Best Buy Viagra Generic Online
  Viagra 100mg x 60 Pills $125, Free Pills & Reorder Discount, Top Selling
  100% Quality & Satisfaction guaranteed!
  We accept VISA, Master & E-Check Payments, 90000+ Satisfied Customers!
  http://medphysitcstech.ru

Représentation des textes

Pour appliquer Naïve Bayes, les textes doivent être transformés en vecteurs d'attributs. La démarche est la suivante :

1. Normalisation des textes :
   • Extraction des racines des mots (lemmatisation)
   • Suppression des mots non importants (prépositions, articles, pronoms)

Construction du vocabulaire V à partir de l'ensemble des textes.

Application du modèle sac de mots (bag of words) en version binaire : chaque texte est représenté par un vecteur x de dimension P (taille du vocabulaire), où chaque composante xi vaut 1 si le mot i est présent dans le texte, 0 sinon.

Le vocabulaire V, supposé déjà construit, contient 16 racines de mots :

best, big, buck, buy, cost, expect, host, http, month, pay, portal, run, satisf, sell, web, www

Exemple de représentation (non explicitée dans le document) :

• 1er email (non-spam) : x1 = vecteur binaire indiquant la présence ou l'absence des mots de V.
• 2e email (spam) : x2 = vecteur binaire similaire.

Classification de textes avec la méthode de Naïve Bayes

Construction du classifieur Naïve Bayes

Chaque texte est représenté par un vecteur x de 16 attributs (mots). Le classifieur estime les probabilités conditionnelles Pr[xi | y, X] pour chaque mot i et chaque classe y (spam ou non-spam).

On définit :

• n(m, y) : nombre de textes de la classe y contenant le mot m
• n(y) : nombre total de textes de la classe y

Les probabilités conditionnelles sont calculées par :

Pr[xi = 1 | y, X] = n(mi, y) / n(y)

Pr[xi = 0 | y, X] = 1 - Pr[xi = 1 | y, X]

où mi est le ième mot dans le vocabulaire V.

Un tableau (non reproduit intégralement ici) permet de compléter ces probabilités pour chaque mot et chaque classe.

Classification d’un nouvel email

Considérons l'email suivant :

Looking forward to your call and I will introduce you to people like yourself who are currently making $10,000 plus per week!

Étapes :

1. Normaliser ce texte (extraction des racines, suppression des mots non importants).
2. Transformer ce texte en vecteur binaire x selon le vocabulaire V.
3. Remplir les probabilités Pr[xi | y=non-spam, X] et Pr[xi | y=spam, X] à partir du tableau des probabilités conditionnelles.
4. Appliquer la formule Naïve Bayes :

y = argmaxy ∈ Y (∏i=1..p Pr[xi | y, X]) · Pr[y | X]

où Y = {spam, non-spam} et Pr[y | X] est la probabilité a priori de la classe y.

Le calcul consiste à multiplier les probabilités conditionnelles des mots présents ou absents selon la classe, puis à choisir la classe qui maximise ce produit.

Glossaire des termes clés

• Naïve Bayes : Méthode de classification probabiliste basée sur le théorème de Bayes, supposant l'indépendance conditionnelle des attributs.
• Spam : Email non sollicité, souvent publicitaire ou malveillant.
• Corpus : Ensemble de documents ou textes utilisés pour l'apprentissage.
• Vocabulaire (V) : Ensemble des mots (ou racines) retenus pour représenter les textes.
• Sac de mots (bag of words) : Modèle de représentation des textes par la présence ou absence des mots du vocabulaire, sans ordre.
• Probabilité conditionnelle : Probabilité d'un événement sachant qu'un autre événement est réalisé.
• Normalisation : Traitement des textes pour extraire les racines des mots et supprimer les mots non significatifs.
• Vecteur binaire : Représentation d'un texte par une suite de 0 et 1 indiquant l'absence ou la présence des mots du vocabulaire.

Points clés à retenir

• La classification de textes par Naïve Bayes nécessite une étape préalable de transformation des textes en vecteurs d'attributs.
• La normalisation des textes (lemmatisation, suppression des mots vides) est essentielle pour réduire la dimension et améliorer la qualité des données.
• Le modèle sac de mots binaire est simple et efficace pour représenter la présence des mots.
• Les probabilités conditionnelles Pr[xi | y, X] sont calculées à partir des fréquences d'apparition des mots dans chaque classe.
• La classification d'un nouvel email se fait en calculant la probabilité a posteriori de chaque classe et en choisissant la classe la plus probable.