TD no. 2 : Classification de Textes avec Naïve Bayes

Ce travaux dirigé (TD) présente une méthode de classification de textes basée sur l'algorithme de Naïve Bayes. L'objectif est d'apprendre à détecter automatiquement si un email est un spam ou non, en utilisant un ensemble d'emails annotés. Pour réaliser ce TD, il est nécessaire de disposer d'un corpus d'emails (ici le SpamAssassin Public Corpus) et de connaissances de base en traitement automatique du langage et en probabilités.

Objectifs

• Comprendre le problème de classification de textes, notamment la détection de spam.
• Apprendre à représenter des textes sous forme de vecteurs d'attributs.
• Mettre en œuvre la méthode de Naïve Bayes pour la classification binaire (spam / non-spam).
• Calculer et interpréter les probabilités conditionnelles nécessaires au classifieur.
• Classer un nouvel email à partir des probabilités estimées.

Prérequis et préparation

• Corpus d'emails annotés en spam et non-spam (SpamAssassin Public Corpus).
• Connaissances en traitement de texte : normalisation, extraction de racines, suppression des mots non significatifs.
• Notions de probabilités conditionnelles et de modèle Naïve Bayes.
• Outils pour manipuler les textes et calculer les probabilités (logiciel ou script).

Le problème et les données

Le corpus contient 1000 emails, chacun étiqueté comme spam ou non-spam. L'objectif est de construire un classifieur Naïve Bayes capable de prédire la classe d'un nouvel email.

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, chaque texte doit être transformé en un vecteur d'attributs x de dimension P. Le processus comprend :

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

Le vocabulaire V utilisé ici est composé des 16 mots suivants :

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

Par exemple, pour l'email no. 1, on extrait les racines et on construit le vecteur x1 correspondant à la présence ou non de chacun de ces mots. De même pour l'email no. 2, on obtient le vecteur x2.

Construction du classifieur Naïve Bayes

On suppose que tous les emails sont déjà transformés en vecteurs x de 16 attributs binaires. Le but est d'estimer les probabilités conditionnelles Pr[xi | y, X] pour chaque mot i et chaque classe y (spam ou non-spam).

On note :

• n(m, y) : nombre d'emails de la classe y contenant le mot m
• n(y) : nombre total d'emails 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]

Le tableau suivant (Table 1) doit être complété pour toutes les valeurs de i (de 1 à 16) et pour chaque classe y (non-spam et spam) :

i	mi	y=non-spam n(mi,y)	y=non-spam n(y)	Pr[xi=0|y=non-spam,X]	Pr[xi=1|y=non-spam,X]	y=spam n(mi,y)	y=spam n(y)	Pr[xi=0|y=spam,X]	Pr[xi=1|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

Compléter ce tableau permet d'obtenir toutes les probabilités nécessaires pour le classifieur.

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 normalisé en un vecteur x selon le vocabulaire V.
3. Remplir les valeurs de x dans le tableau des mots (Table 2 ci-dessous).
4. Pour chaque mot i, récupérer Pr[xi | y=non-spam, X] et Pr[xi | y=spam, X] depuis le tableau des probabilités conditionnelles (Table 1).
5. Appliquer la formule Naïve Bayes :

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

où Pr[y | X] est la probabilité a priori de la classe y.

i	mi	Pr[xi | y=non-spam, X]	Pr[xi | y=spam, X]	xi (valeur dans le vecteur)
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 résultat de cette formule donne la classe la plus probable pour cet email.

Résultats attendus

Après avoir complété les tableaux et appliqué la formule Naïve Bayes, l'étudiant doit obtenir :

• Les probabilités conditionnelles Pr[xi | y, X] pour chaque mot et chaque classe.
• Le vecteur binaire x du nouvel email.
• La probabilité de chaque classe (spam et non-spam) pour ce nouvel email.
• La classe finale choisie par le classifieur (celle qui maximise la probabilité).

Pièges courants

• Mauvaise normalisation : ne pas extraire correctement les racines ou oublier de supprimer les mots non importants fausse la représentation vectorielle.
• Erreur dans le calcul des probabilités : oublier de diviser par le nombre total d'emails de la classe ou confondre Pr[xi=1|y,X] et Pr[xi=0|y,X].
• Vocabulaire incomplet : ne pas utiliser le vocabulaire fourni ou en ajouter d'autres mots non prévus perturbe la classification.
• Confusion dans l'application de la formule : ne pas appliquer la multiplication des probabilités conditionnelles ou oublier la probabilité a priori Pr[y|X].
• Valeurs manquantes dans les tableaux : ne pas remplir toutes les cases du tableau des probabilités empêche la classification correcte.