Data Mining
2013/2014
Prof. Chiraz Ben Abdelkader
TD no. 2 : Classification de Textes avec Naïve Bayes
21 Octobre, 2013
Plan:
Introduction
1)
2) Le problème et les données
3) La représentation des textes
4) Classification de textes avec méthode de Naïve Bayes
1. Introduction
Le but de ce TD est de démontrer l’utilisation de la méthode de Naïve Bayes pour
la classification de textes.
Reference : notes de cours du 30 Septembre et du 07 Octobre.
2. Le problème et les données
On a un ensemble de 1000 emails, chacun marqué comme étant spam ou non-
spam. Source : SpamAssassin Public Corpus
http://spamassassin.apache.org/publiccorpus/
On vise à construire un classeur Naïve Bayes qui nous aide à détecter si un nouvel
email est du spam ou pas.
Quelques exemplaires, juste pour vous donner une idée :
o Exemplaire email no. 1: (classe = 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..
o Exemplaire email no. 2: (classe = 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
Publicité
3. Représentation des textes
Le but est de transformer tous les textes à des vecteurs de P attributs, x.
Pour cela on va effectuer les étapes suivantes :
1) Normaliser les textes :
Extraction des racines de mots
Supprimer les mots non importants : prépositions, articles, pronoms
2) Construction du vocabulaire V à partir de notre ensemble d’exemplaires.
3) Appliquer le modèle sac de mots-- version binaire sur chaque texte normalisé,
en se basant sur l’ensemble V construit.
On imagine que le vocabulaire V (2eme étape) a été déjà construit pour nous, et
qu’il s’agit des 16 mots (en fait racines de mots) suivants :
best, big, buck, buy, cost, expect, host, http,
month, pay, portal, run, satisf, sell, web, www
(En réalité, le vocabulaire peut contenir des milliers de mots !)
Appliquer 1ere puis 3eme étapes sur les deux exemplaires en haut :
Représentation du 1er exemplaire : x1 =
Représentation du 2eme exemplaire : x2 =
4. Classification de textes avec méthode de Naïve Bayes
a. Construction du classeur Naïve Bayes
On suppose que les exemplaires textes sont tous déjà transformes en des vecteurs
x de 16 attributs.
On doit maintenant estimer toutes les probabilités conditionnelles Pr[xi| y,X] ,
pour toutes les valeurs de l’attribut xi et de la classe y
On dénote :
n(m,y) : nombre de textes exemplaires de la classe y contenant le mot m
n(y) : nombre de textes exemplaires de la classe y
On se rappelle que :
Pr[xi = 1 | y,X] = n(mi,y) / n(y) ou mi est l’ieme mot dans V
Publicité
Pr[xi = 0 | y,X] = 1 - Pr[xi = 1 | y,X]
On suppose que le travail demande a été partiellement effectué dans le tableau ci-
dessus. Compléter-le pour déduire toutes les probabilités du classeur Naïve Bayes.
Table 1 Calcul des probabilités conditionnelles du classeur Naïve Bayes.
y=non-spam
n(y)
n(mi,y)
Pr[xi=0|y,X]
Pr[xi=1|y,X]
y=spam
n(mi,y)
n(y)
Pr[xi=0|y,X]
Pr[xi=1|y,X]
i
1
2
3
4
5
6
7
8
9
mi
best
Publicité
big
buck
buy
cost
expect
host
http
month
10 pay
11 portal
12 run
13 satisf
14 sell
15 web
16 www
b. Classification d’un nouvel email
On considère 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!
Normaliser ce texte puis transformer-le a un vecteur x, comme on fait en haut.
o Remplir les valeurs de x dans le tableau ci-dessus.
Appliquer la formule Naïve Bayes ci-dessus, tout en utilisant les probabilités dans
le tableau en haut :
y = argmaxy Y (
i=1..p Pr[xi | y,X] ) . Pr[y | X]
o Remplir les probabilités dans Table 2 ci-dessus en les copiant les valeurs
convenables du Table 1.
o Appliquer maintenant la formule en haut.
Table 2 Classification d'un nouvel email avec Naive Bayes
Pr[xi | y=non-spam,X] Pr[xi | y=non-spam,X]
xi
Publicité
i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
mi
best
big
buck
buy
cost
expect
host
http
month
pay
portal
run
satisf
sell
web
www