Notes de Cours : Data Mining
S ance 5, 07 Octobre 2013
Prof. Chiraz Ben Abdelkader, ENSI
Plan: Classification Supervis e Base dExemples Repr sentatifs
Introduction
1)
2) Description g n rale de lapproche
3) Mesure de dissimilarit entre deux donn es
4) Lalgorithme des plus proches voisins (kPPV)
5) Application : classification de textes avec m thodes de Na ve Bayes et kPPV
Voir TD#2 et TD#3
6) TD/TP : classification de textes sur Weka
R f rences :
(Disponibles sur mon Google Drive, sous le dossier R f rences & Ressources )
1) Notes de cours (Fran ais) : Prof. Philippe Preux, Chapitre 5
Comme il y en a quelques graves fautes de frappes, ne lutiliser pas comme r f rence primaire.
2) Livre (Anglais): Data Mining, Practical ML tools and techniques, Chapitre 4 p. 131-134
1) Introduction
On distingue deux grandes cat gories de classeurs supervis s :
i.
ii.
Ceux qui utilisent un mod le ou une formule qui est d j construite
durant la phase dinduction du classeur. Les exemplaires X sont
seulement utilis es pour linduction du classeur (donc du mod le), mais
pas durant lapplication du classeur sur des donn es nouvelles. Les
m thodes quon a discut jusqu ce point (ZeroR, OneR et NaiveBayes)
tombent tous dans cette cat gorie.
Ceux qui utilisent directement les exemplaires pour pr dire la classe dune
donn e nouvelle, x.
On appelle les m thodes de cette deuxi me cat gorie les classeurs base
dexemplaires repr sentatifs.
Lalgorithme des k plus proches voisins (kPPV) est lun de ces m thodes les plus
connus.
2) Approche G n rale
Les techniques de classification supervis e base dexemplaires repr sentatifs se
basent sur lapproche g n rale suivante : tant donn lensemble X, on stocke
ces exemplaires tel quils sont ; puis, tant donne une nouvelle donn e x, on
pr dit sa classe en fonction des classes des exemplaires dans X qui sont les plus
similaires (ou bien les moins dissimilaires ) de x.
Quelques d tails doivent tre pr cis s afin dobtenir une m thode de
classification concr te :
i) quelle notion de dissimilarit ou de proximit va-t-on utiliser ?
ii) combien dexemplaires proches va-t-on consid rer/utiliser?
iii) quel fonction va-t-on utiliser pour finalement pr dire la classe de x?
On discutera la notion de dissimilarit en g n ral, puis on discutera les deux
autres taches dans le contexte de la technique des plus proches voisins.
3) Mesures de Dissimilarit
Dans les techniques base dexemplaires repr sentatifs, il faut tout dabord
d finir une mesure, ou fonction de proximit ou de dissimilarit entre deux
donn es quelconques x et z : d(x,z)
La fonction d doit ob ir aux 3 propri t s suivantes :
o d est non-d g n r e : d(x,z)=0 SSi x=z " x,z D2
o d est sym trique : d(x,z) = d(z,x) " x,z D2
o lin galit triangulaire : d(x,z) d(x,w)+d(w,z) " x,w,z D3
a. Attributs num riques
Lorsque les donn es x sont tous num riques, linterpr tation g om trique
du probl me de classification supervis e est utile : x repr sente un point
dans un espace Euclidien de p dimensions, ou chaque dimension
correspond la valeur dun attribut.
Distance Euclidienne : la plus simple mesure de dissimilarit
p
2
d
Publicité
),(
zx
(
x
i
2
z
i
)
i
1
o On peut facilement v rifier que cette fonction ob it aux 3
propri t s discut es au-dessus.
Distance de Manhattan : la somme des valeurs absolues |xi-zi|
Cosine similarity : cosinus de langle entre les vecteurs x et z
),(
zxs
P
1
i
P
i
1
zx
i
i
2
zx
i
2
i
s(x,z) est toujours dans lintervalle [0,1]
s(x,z) est en fait une mesure de similarit , donc on la
convertit a une dissimilarit avec : d(x,z) = 1- s(x,z)
Quand on utilise la distance Euclidienne ou bien la distance de Manhattan,
les attributs doivent tre tous du m me ordre de grandeur, pour que nul
=
-
=
=
=
=
attribut ne domine la valeur de la distance (imaginez par exemple si
quelques attributs sont mesur s en m tres et dautres sont mesur s en
mm). Pour assurer cette condition, on peut transformer les attributs de la
fa on suivante :
x
i
x
i
max(
x
Publicité
i
min(
)
x
)
i
min(
x
i
)
o Ainsi les nouvelles valeurs de tous attributs
[0,1]
b. Attributs nominaux
On utilise typiquement une fonction d de la forme suivante :
),(
zxd
p
i
1
(
xf
i
z
i
)
o Ou xi zi est la valeur enti re : 0 si xi=zi , 1 sinon.
o Dans le cas le plus simple, f est lidentit . Cest- -dire, d(x,z) = le
nombre des attributs ayant des valeurs diff rentes.
4) Lalgorithme des plus proches voisins
Cet algorithme est lun des techniques les plus simples bas es sur lapproche
g n rale base dexemplaires repr sentatifs, discut e au-dessus.
Etant donn un ensemble dexemplaires X et une nouvelle donn e x, cet
algorithme d termine la classe y avec les deux tapes suivantes :
Etape 1 : d terminer les k plus proches voisins dans X a la donn e x, avec k
tant une valeur fixe, et la fonction d de dissimilarit tant bien d finie ;
Etape 2 : calculer la classe majoritaire des k voisins.
Evidemment k est un param tre de la m thode, dont la valeur est choisi selon
la performance du classeur sur un ensemble dexemplaires de test (Xtest).
Il existe dautres versions de cette m thode ; celle-ci est la plus simple.
Exemple : Voir TD#3
5) Application : Classification de Textes
a. Pr sentation du probl me
Il sagit dun probl me de classification supervis e ou chaque exemplaire
de lensemble X sagit dun document texte.
Exemples :
o D tection de spam : Les textes sont des emails et les classes sont {
spam, non-spam}
o Classification de pages Web par apport a un sujet X: les textes sont des
pages Web, et les classes sont { traite_sujet_X, ne_traite_pas_sujet_X }
o Classification de page Web: les textes sont des pages Web et les
classes sont { actualit s, sport, les arts, technologie, & }
b. Repr sentation de textes en sacs de mots
-
-
=
=
=
Publicité
Evidemment, les textes doivent tre mis sous une forme convenable tre
trait s par les m thodes de classification supervis e, donc on doit extraire
partir dun texte un ensemble dattributs, x.
Une repr sentation tr s fr quemment utilis e est celle de sacs de
mots , ou un texte est caract ris par un ensemble de p attributs, chaque
attribut tant associ un mot dun ensemble fixe bien d fini de mots
(quon appelle un vocabulaire)V = { m1, m2, & , mp }, et ayant pour valeur
une fonction du nombre doccurrences de ce mot dans le texte.
Sacs de mots--version binaire : Les attributs dun texte t sont d finis par:
m
si
i
sinon
0
1
x
i
t
Sacs de mots--version TF.IDF : Les attributs dun texte t sont d finis par :
x
i
0
(1
log(n(m
,
t)))
i
log(w
)
i
t
si
m
i
sinon
ou :
n(mi,t) : nombre doccurrences du mot mi dans un texte t
wi : facteur dimportance du mot mi
o Le facteur dimportance dun mot mi est calcul partir de
lensemble X dexemplaires (textes), comme tant linverse de la
proportion de ces textes qui contiennent mi , donc: wi = |X|/n(mi)
ou n(mi) est le nombre de textes dans X qui contiennent le mot mi.
c. Construction du Vocabulaire V
Le mod le sacs de mots demande un ensemble V de P mots (le
vocabulaire), pour que lon puisse transformer les textes des vecteurs de
P attributs. Cet ensemble est typiquement construit partir des
exemplaires de lensemble X comme tant lunion des P/|Y| mots les plus
fr quents dans les textes de chaque classe y.
d. Pr traitement (normalisation) des textes
Intuitivement, on veut que les mots dans le vocabulaire V refl tent le
contenu (sens) des textes et quils soient non redondants.
Cest pour cela que les textes sont habituellement pr trait s
( normalis s ) de la mani re suivante :
(i) transformer chaque mot a sa racine (Stemming). Par exemple,
afficher et affichage seront transform s a affich
(ii) supprimer les mots non-importants tel que les pr positions,
pronoms, articles, etc. (Stop words)
e. Classification avec Na ve Bayes
=
Publicité
+
=
Etant donn un ensemble X de textes et leurs classes, et un autre texte t
qui nappartient pas X, on souhaite pr dire la classe y de t, en utilisant la
m thode Na ve Bayes. Pour cela, on a trois t ches principales faire :
1) Repr senter tous les textes comme des vecteurs dattributs, x.
2) Construire un classeur na ve Bayes, donc estimer toutes les
probabilit s conditionnelles Pr , pour toutes les valeurs de xi et
de y. Voir les notes de cours du 30 Septembre, 2013.
3) Utiliser ce classeur na ve Bayes pour pr dire la classe du texte t.
Pour la 1ere tache, on va utiliser le mod le sacs de mots-version binaire,
discut en haut. Rappelons que dans ce cas, chaque attribut xi prend deux
valeurs possibles, 0 et 1, associ es respectivement labsence et pr sence
dun mot dans le vocabulaire V . Le vocabulaire V doit tre construit
partir des exemplaires dans X comme on a d j discut en haut
Pour la 2eme tache, on calcule les probabilit s Pr comme suit :
Pr = n(mi,y) / n(y)
Pr = 1 - Pr
(probabilit dobserver mi dans un texte du classe y)
ou n(y) : nombre de textes exemplaires de la classe y
n(mi,y) : nombre de textes de la classe y contenant let mot de mi
Pour la 3eme tache, on suppose que le texte t est d j transform en un
vecteur dattributs x. On applique la formule Na ve Bayes (avec les valeurs
de probabilit s d j calcul es dans l tape pr c dente) :
y = argmaxy Y ( P
i=1..p Pr ) . Pr
Exemple : Voir TD#2
f. Classification avec m thode kPPV
Etant donn un ensemble X de textes et leurs classes, et un autre texte t
qui nappartient pas X, on souhaite pr dire la classe y de t, en utilisant la
m thode kPPV. Pour cela, on a deux t ches principales faire :
1) Repr senter tous les textes comme des vecteurs dattributs, x.
2) Choisir une mesure de dissimilarit entre deux textes.
3) Appliquer la m thode kPPV pour pr dire la classe du texte t.
Pour la 1ere tache, on va utiliser le mod le sacs de mots-version TF.IDF
introduite en haut. Le vocabulaire V doit tre construit pour ce mod le
partir des exemplaires dans X comme on a d j discut en haut.
Pour la 2eme tache, on va utiliser la cosine similarity, d j d finie en haut.
Pour la 3eme tache, on suppose que le texte t est d j transform en un
vecteur dattributs x. On applique maintenant la methode kPPV :
o On calcule les dissimilarit s : d(x,xi) " xi X
o On trouve les k plus proches voisins de x : les k exemplaires qui
correspondent au k plus petites valeurs de dissimilarit s.
o On pr dit y = classe majoritaire entre ces k exemplaires.
Exemple : Voir TD#5