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

Ce TD vise à démontrer l’utilisation de la méthode de classification Naïve Bayes appliquée aux textes, en particulier pour détecter si un email est un spam ou non. Il nécessite un ensemble de données d’emails étiquetés, des connaissances de base en traitement de texte et en probabilités, ainsi qu’un environnement permettant de manipuler des vecteurs et calculer des 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 numériques.
• Mettre en œuvre la méthode Naïve Bayes pour classer des emails.
• Calculer et interpréter les probabilités conditionnelles utilisées dans Naïve Bayes.
• Classer un nouvel email à partir des probabilités estimées.

Prérequis et installation

• Connaissances de base en traitement automatique du langage naturel (normalisation, racinisation).
• Notions élémentaires de probabilités conditionnelles et de classification.
• Accès à un corpus d’emails étiquetés spam/non-spam, ici le SpamAssassin Public Corpus.
• Outils pour manipuler des textes et calculer des probabilités (langage de programmation ou tableur).

Le problème et les données

Nous disposons d’un ensemble de 1000 emails, chacun classé comme spam ou non-spam. L’objectif est de construire un classificateur 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, il faut transformer chaque texte en un vecteur d’attributs numériques.

Étapes :

1. Normalisation des textes : extraction des racines des mots, suppression des mots non importants (prépositions, articles, pronoms).
2. Construction du vocabulaire V : ensemble des mots racines retenus, ici fixé à 16 mots :

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

3. Application du modèle sac de mots binaire : chaque texte est représenté par un vecteur x de 16 attributs, où chaque xi vaut 1 si le mot i est présent, 0 sinon.

Par exemple :

• Représentation du 1er email : x1 = (valeurs à compléter selon présence des mots dans le texte)
• Représentation du 2ème email : x2 = (idem)

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

Construction du classificateur Naïve Bayes

On part des vecteurs x de 16 attributs pour chaque email. Il faut estimer les probabilités conditionnelles Pr[xi | y, X], où y est la classe (spam ou non-spam) et xi la présence ou absence du mot i.

Définitions :

• n(m, y) : nombre d’emails de la classe y contenant le mot m.
• n(y) : nombre total d’emails de la classe y.

On calcule :

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

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

Le tableau suivant (à compléter) donne ces probabilités pour chaque mot et chaque classe :

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

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

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

où Pr[y | X] est la probabilité a priori de la classe y (estimée par la fréquence des classes dans l’ensemble d’apprentissage).

Le tableau 2 doit être complété en copiant les probabilités conditionnelles adéquates du tableau 1 selon la présence ou l’absence des mots dans le nouvel email.

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

Résultats attendus

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

• Les probabilités conditionnelles Pr[xi | y, X] pour chaque mot et chaque classe.
• La représentation binaire correcte du nouvel email.
• Le calcul des probabilités totales pour chaque classe.
• La classe prédite y correspondant à la probabilité la plus élevée.

Ces résultats permettent de valider la capacité du classificateur Naïve Bayes à distinguer un spam d’un non-spam.

Erreurs courantes

• 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 n(y) ou confondre Pr[xi=1|y,X] et Pr[xi=0|y,X].
• Oublier d’appliquer la formule Naïve Bayes correctement : ne pas multiplier toutes les probabilités conditionnelles ou ne pas prendre en compte la probabilité a priori Pr[y|X].
• Confusion dans la présence/absence des mots : mal remplir les valeurs xi dans le vecteur.
• Ne pas compléter tous les mots du vocabulaire : ce qui fausse le calcul des probabilités totales.