Data Mining

Ce document présente une introduction à la classification de textes à l'aide de la méthode de Naïve Bayes. Destiné aux étudiants en informatique ou en sciences des données, il explique comment transformer des emails en vecteurs de caractéristiques, estimer les probabilités nécessaires, puis classifier un nouvel email comme spam ou non-spam.

Le problème et les données

Nous disposons d'un ensemble de 1000 emails, chacun étiqueté comme spam ou non-spam. La source de ces données est le SpamAssassin Public Corpus (http://spamassassin.apache.org/publiccorpus/). L'objectif est de construire un classificateur Naïve Bayes capable de détecter si un nouvel email est un spam ou non.

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 la méthode de classification, il faut transformer chaque texte en un vecteur de P attributs x. La procédure est la suivante :

1. Normalisation des textes :
   • Extraction des racines des mots (lemmatisation)
   • Suppression des mots non importants : prépositions, articles, pronoms
2. Construction du vocabulaire V : à partir de l'ensemble des exemplaires.
3. Application du modèle sac de mots (version binaire) : chaque texte est représenté par un vecteur indiquant la présence (1) ou l'absence (0) de chaque mot du vocabulaire V.

Dans cet exemple, le vocabulaire V contient 16 mots (racines) :

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

Exemple de représentation binaire :

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

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

Construction du classificateur Naïve Bayes

On suppose que tous les textes sont déjà transformés en vecteurs x de 16 attributs (correspondant aux mots du vocabulaire V). Le but est d'estimer les probabilités conditionnelles Pr[xi | y, X] pour chaque attribut xi et chaque classe y (spam ou non-spam).

Définitions :

• 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)   où mi est le ième mot du vocabulaire V
Pr[xi = 0 | y, X] = 1 - Pr[xi = 1 | y, X]

Ces probabilités sont utilisées pour construire le classificateur Naïve Bayes.

i	mi	y = non-spam : n(mi,y)	y = non-spam : Pr[xi=1|y,X]	y = non-spam : Pr[xi=0|y,X]	y = spam : n(mi,y)	y = spam : Pr[xi=1|y,X]	y = spam : Pr[xi=0|y,X]
1	best
2	big
3	buck
4	buy
5	cost
6	expect
7	host
8	http
9	month
10	pay
11	portal
12	run
13	satisf
14	sell
15	web
16	www

Classification d’un nouvel email

Considérons le nouvel email :

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 le texte normalisé en vecteur x selon le vocabulaire V.
3. Remplir les valeurs de x dans le tableau des probabilités conditionnelles.
4. Appliquer la formule Naïve Bayes :

y = argmax_{y ∈ Y} ( ∏_{i=1}^p Pr[xi | y, X] ) · Pr[y | X]

où :

• Pr[xi | y, X] sont les probabilités conditionnelles calculées précédemment
• Pr[y | X] est la probabilité a priori de la classe y (par exemple proportion des emails spam et non-spam dans l'ensemble d'apprentissage)

i	mi	xi	Pr[xi | y=non-spam, X]	Pr[xi | y=spam, X]
1	best
2	big
3	buck
4	buy
5	cost
6	expect
7	host
8	http
9	month
10	pay
11	portal
12	run
13	satisf
14	sell
15	web
16	www

Le classificateur choisira la classe y qui maximise la probabilité calculée.

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.
• Non-spam : Email légitime, ne faisant pas partie des spams.
• Vocabulaire (V) : Ensemble des mots retenus pour représenter les textes.
• Modèle sac de mots : Représentation d'un texte par la présence ou l'absence de mots du vocabulaire, sans tenir compte de l'ordre.
• Probabilité conditionnelle Pr[xi | y, X] : Probabilité que l'attribut xi prenne une certaine valeur sachant la classe y et l'ensemble d'apprentissage X.
• Normalisation : Processus de préparation des textes (extraction des racines, suppression des mots non importants).
• Vecteur d'attributs (x) : Représentation numérique d'un texte selon la présence ou l'absence des mots du vocabulaire.

Points clés à retenir

• La classification de textes par Naïve Bayes repose sur la transformation des textes en vecteurs binaires selon un vocabulaire défini.
• La méthode estime les probabilités conditionnelles de présence des mots dans chaque classe à partir des données d'apprentissage.
• La classification d'un nouvel email consiste à calculer la probabilité de chaque classe et choisir celle qui est la plus probable.
• La normalisation des textes est essentielle pour réduire le bruit et améliorer la qualité des représentations.
• Le modèle sac de mots simplifie la représentation en ignorant l'ordre des mots, ce qui est souvent suffisant pour la classification.