Data Mining
Data Mining
Programming, Math, etc. · course
Fiche de révisionFiche de cours
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce matériel couvre les principes fondamentaux de la classification supervisée à base d’exemplaires représentatifs, notamment l’algorithme des k plus proches voisins (kPPV). Il s’adresse aux étudiants en data mining ou apprentissage automatique souhaitant comprendre cette approche et son application à la classification de textes.
En classification supervisée, on distingue deux grandes catégories de classeurs :
L’algorithme des k plus proches voisins (kPPV) appartient à cette deuxième catégorie.
Étant donné un ensemble d’exemplaires d’apprentissage X, on les stocke tels quels. Pour prédire la classe d’une nouvelle donnée x, on se base sur les classes des exemplaires dans X qui sont les plus similaires (ou les moins dissimilaires) à x.
Trois questions fondamentales restent à préciser :
Soient deux exemplaires quelconques x et z appartenant à l’ensemble D. On définit une fonction d : D × D → ℝ telle que d(x,z) mesure le degré de dissimilarité entre x et z.
Cette fonction d doit satisfaire trois propriétés :
Plusieurs distances sont utilisées, basées sur une interprétation géométrique :
Pour la distance euclidienne, il est important de normaliser les attributs afin qu’ils contribuent de manière équitable, notamment lorsque les unités de mesure diffèrent (ex. mètres vs millimètres).
La normalisation d’un attribut x_i se fait par :
ˆx_i = (x_i - min(x_i)) / (max(x_i) - min(x_i))
Les attributs normalisés sont ainsi compris dans l’intervalle [0,1].
Pour des attributs catégoriels, on peut utiliser une fonction simple :
d(x,z) = Σ_i f(x_i ≠ z_i)
où f vaut 1 si x_i ≠ z_i, et 0 sinon. Autrement dit, la dissimilarité est le nombre d’attributs dont les valeurs diffèrent entre x et z.
Le kPPV est une méthode simple basée sur l’approche à base d’exemplaires représentatifs :
Le paramètre k est choisi en fonction de la performance de la méthode sur un ensemble de test X_test. Il existe d’autres variantes de kPPV, mais celle-ci est la plus simple et la plus utilisée.
Supposons que l’on ait un ensemble X de 5 exemplaires avec leurs classes :
| Exemplaire | Attribut 1 | Attribut 2 | Classe |
|---|---|---|---|
| x1 | 0.2 | 0.4 | A |
| x2 | 0.1 | 0.5 | A |
| x3 | 0.8 | 0.7 | B |
| x4 | 0.9 | 0.6 | B |
| x5 | 0.85 | 0.75 | B |
Pour une nouvelle donnée x = (0.82, 0.65), avec k=3, on calcule la distance euclidienne normalisée entre x et chaque exemplaire :
Les 3 plus proches voisins sont x3, x4 et x5, tous de classe B. La prédiction pour x est donc la classe B.
La classification de textes est un problème de classification supervisée où les exemplaires sont des documents textuels à classer dans deux ou plusieurs catégories.
Exemples d’applications :
Les textes sont souvent représentés sous forme de « sacs de mots », c’est-à-dire comme des vecteurs où chaque dimension correspond à la fréquence ou la présence d’un mot dans le document.