Notes de Cours : Data Mining

)

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 l’angle 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 l’intervalle [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 d’autres 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

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 l’identité. C’est-à-dire, d(x,z) = le

nombre des attributs ayant des valeurs différentes.

4) L’algorithme des plus proches voisins

Cet algorithme est l’un des techniques les plus simples basées sur l’approche générale à base d’exemplaires représentatifs, discutée au-dessus. Etant donné un ensemble d’exemplaires 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 d’exemplaires de test (Xtest). Il existe d’autres 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 s’agit d’un problème de classification supervisée ou chaque exemplaire de l’ensemble X s’agit d’un 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 »

               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 d’un texte un ensemble d’attributs, 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 d’un ensemble fixe bien défini de mots (qu’on appelle un vocabulaire)V = { m1, m2, … , mp }, et ayant pour valeur une fonction du nombre d’occurrences de ce mot dans le texte.

Sacs de mots--version binaire : Les attributs d’un texte t sont définis par: m si i sinon

0 1

x i

t

Sacs de mots--version TF.IDF : Les attributs d’un 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 d’occurrences du mot mi dans un texte t

wi : facteur d’importance du mot mi

o Le facteur d’importance d’un mot mi est calculé à partir de

l’ensemble X d’exemplaires (textes), comme étant l’inverse 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 l’on puisse transformer les textes à des vecteurs de P attributs. Cet ensemble est typiquement construit à partir des exemplaires de l’ensemble X comme étant l’union 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 qu’ils soient non redondants. C’est 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

                   Etant donné un ensemble X de textes et leurs classes, et un autre texte t qui n’appartient 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 d’attributs, x. 2) Construire un classeur naïve Bayes, donc estimer toutes les probabilités conditionnelles Pr[xi| y,X], 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 à l’absence et présence d’un 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[xi| y,X] comme suit :

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

(probabilité d’observer 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 d’attributs 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 ( 

i=1..p Pr[xi | y,X] ) . Pr[y | X]

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 n’appartient 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 d’attributs, 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 d’attributs 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

