Data Mining

Séance 5, 07 Octobre 2013

Prof. Chiraz Ben Abdelkader

ENSI

Plan

• Classification Supervisée à Base d’Exemples Représentatifs :

1) Introduction

2) Description générale de l’approche

3) Mesure de dissimilarité entre deux données

4) L’algorithme des plus proches voisins (kPPV)

5) Application : classification de textes avec Naïve Bayes et kPPV

6) TD/TP : classification de textes sur Weka

10/27/2013

Références

• Notes de cours (Français) : Prof. Philippe Preux, Chapitre 5

• Livre (Anglais): Data Mining, Practical ML tools and techniques,

Chapitre 4 p. 131-134

(Disponibles sur mon Google Drive, sous le dossier « Références &

Ressources »)

Introduction

• On distingue deux grandes catégories de classeurs supervisés :

1) Ceux qui utilisent un modèle ou une formule qui est déjà construite

durant la phase d’induction du classeur. Les exemplaires X sont

seulement utilisées pour l’induction du classeur (donc du modèle),

mais pas durant l’application du classeur sur des données nouvelles.

• Les méthodes qu’on a discuté jusqu’à ce point (ZeroR, OneR et NaiveBayes)

tombent tous dans cette catégorie.

10/27/2013

Introduction

• On distingue deux grandes catégories de classeurs supervisés :

2) Ceux qui utilisent directement les exemplaires pour prédire la classe

d’une donnée nouvelle, x

• On appelle les méthodes de cette deuxième catégorie les classeurs à base

d’exemplaires représentatifs.

• L’algorithme des k plus proches voisins (kPPV) est l’un de ces méthodes les

plus connus.

Classeurs à base d’exemplaires

représentatifs : Approche Générale

• étant donné un ensemble d’exemplaires d’apprentissage, X, on les

stocke tel qu’ils sont

• é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

10/27/2013

Classeurs à base d’exemplaires

représentatifs : Approche Générale

• Quelques taches nous restent a préciser :

1) notion de dissimilarité ou de proximité va-t-on utiliser ?

2) combien d’exemplaires proches va-t-on considérer/utiliser?

3) comment combiner les classes des voisins pour finalement

prédire la classe de x?

Mesure de Dissimilarité

• Etant donné deux exemplaires quelconques x, z  D, on souhaite

définir une fonction d : D  , tel que d(x,z) est proportionnel au

degré de dissimilarité entre le valeurs de x et z

• La fonction d doit obéir aux 3 propriétés suivantes :

• d est non-dégénérée : d(x,z)=0 SSi x=z x,zD2

• d est symétrique : d(x,z) = d(z,x) x,zD2

• l’inégalité triangulaire : d(x,z) d(x,w)+d(w,z) x,w,zD3

10/27/2013

Mesure de Dissimilarité des Attributs

Numériques

• Distance Euclidienne

• Cosine similarity

• Distance de Manhattan

(basé sur l’interprétation géométrique des attributs)

Mesure de Dissimilarité des Attributs

Numériques

• Normalisation des attributs pour distance euclidienne:



max(

)

min(

)





)

• Les attributs normalisées sont dans l’intervalle [0,1]

• Ils contribuent tous de la même façon à la formule de la distance euclidienne

• Exemple: imaginez si quelques attributs sont mesurés en mètres et autres

sont mesurés en mm

10/27/2013

Mesure de Dissimilarité des Attributs

Nominaux

• Une fonction de la forme :

),(

zxd







(



)

• Ou xizi est la valeur entière : 0 si xi=zi , 1 sinon.

• Dans le cas le plus simple, on définit la fonction f comme étant l’identité

• C’est-à-dire, d(x,z) = le nombre des attributs ayant des valeurs différentes

Algorithme des plus proches voisins (kPPV)

• l’un des techniques les plus simples basées sur l’approche générale à

base d’exemplaires représentatifs

• Etant donné un ensemble d’exemplaires X et une nouvelle donnée x,

l’algorithme kPPV détermine la classe y avec les 2 é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 (en supposant k est

impaire)

10/27/2013

Algorithme des plus proches voisins (kPPV)

• 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

Application : Classification de Textes

• Il s’agit d’un problème de classification supervisée ou les exemplaires

consistent en des textes qu’on souhaite classifier à deux ou plusieurs

classes (catégories)

• Exemples :

• Détection de spam : Les textes sont des emails et les classes sont { spam, non-

spam}

• 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 }

• Classification de page Web: les textes sont des pages Web et les classes sont {

actualités, sport, les arts, technologie, … }

10/27/2013

Application : Classification de Textes

• Représentation des textes en « sacs de mots »

10/27/2013