Data Mining

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.

Classification Supervisée à Base d’Exemplaires Représentatifs

Introduction

En classification supervisée, on distingue deux grandes catégories de classeurs :

• Ceux qui utilisent un modèle ou une formule construite durant la phase d’induction. Les exemplaires d’apprentissage sont utilisés uniquement pour construire ce modèle, mais pas lors de la prédiction sur de nouvelles données. Exemples : ZeroR, OneR, Naïve Bayes.
• Ceux qui utilisent directement les exemplaires d’apprentissage pour prédire la classe d’une nouvelle donnée. Ces méthodes sont appelées classeurs à base d’exemplaires représentatifs.

L’algorithme des k plus proches voisins (kPPV) appartient à cette deuxième catégorie.

Approche Générale des Classeurs à Base d’Exemplaires Représentatifs

É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 :

1. Quelle notion de dissimilarité ou de proximité utiliser ?
2. Combien d’exemplaires proches considérer ?
3. Comment combiner les classes des voisins pour prédire la classe finale de x ?

Mesure de Dissimilarité

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 :

• Non-dégénérescence : d(x,z) = 0 si et seulement si x = z, pour tout x, z ∈ D.
• Symétrie : d(x,z) = d(z,x) pour tout x, z ∈ D.
• Inégalité triangulaire : d(x,z) ≤ d(x,w) + d(w,z) pour tout x, w, z ∈ D.

Mesure de Dissimilarité pour Attributs Numériques

Plusieurs distances sont utilisées, basées sur une interprétation géométrique :

• Distance Euclidienne
• Cosine similarity
• Distance de Manhattan

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].

Mesure de Dissimilarité pour Attributs Nominaux

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.

Algorithme des Plus Proches Voisins (kPPV)

Le kPPV est une méthode simple basée sur l’approche à base d’exemplaires représentatifs :

1. Étant donné un ensemble d’exemplaires X et une nouvelle donnée x, on détermine les k plus proches voisins de x dans X, en utilisant la fonction de dissimilarité d.
2. On prédit la classe de x comme étant la classe majoritaire parmi ces k voisins (k est généralement choisi impair pour éviter les égalités).

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.

Exemple d’Application de kPPV

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 :

• d(x,x1) ≈ 0.56
• d(x,x2) ≈ 0.65
• d(x,x3) ≈ 0.07
• d(x,x4) ≈ 0.07
• d(x,x5) ≈ 0.11

Les 3 plus proches voisins sont x3, x4 et x5, tous de classe B. La prédiction pour x est donc la classe B.

Application : Classification de Textes

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 :

• Détection de spam : classes {spam, non-spam}
• Classification de pages Web selon un sujet X : classes {traite_sujet_X, ne_traite_pas_sujet_X}
• Classification de pages Web en catégories générales : {actualités, sport, arts, technologie, ...}

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.

Glossaire des Termes Clés

• Classification supervisée : Méthode d’apprentissage où les données d’entraînement sont étiquetées avec leur classe.
• Classeur : Modèle ou méthode utilisée pour prédire la classe d’une nouvelle donnée.
• Exemplaire : Instance ou donnée individuelle utilisée dans l’apprentissage ou la classification.
• Classeur à base d’exemplaires représentatifs : Méthode qui utilise directement les exemplaires d’apprentissage pour prédire la classe d’une nouvelle donnée.
• k plus proches voisins (kPPV) : Algorithme qui classe une donnée selon la majorité des classes de ses k voisins les plus proches.
• Dissimilarité : Mesure du degré de différence entre deux exemplaires.
• Distance Euclidienne : Mesure géométrique de la distance entre deux points dans un espace à n dimensions.
• Distance de Manhattan : Somme des distances absolues entre les coordonnées des points.
• Cosine similarity : Mesure de similarité basée sur l’angle entre deux vecteurs.
• Normalisation : Transformation des données pour les ramener dans un même intervalle, souvent [0,1].
• Sac de mots : Représentation d’un texte sous forme d’un vecteur de fréquences ou de présences de mots, sans tenir compte de l’ordre.

Points Clés à Retenir

• La classification supervisée à base d’exemplaires utilise directement les données d’apprentissage pour la prédiction, sans construire de modèle explicite.
• L’algorithme kPPV est simple et efficace : il prédit la classe d’une donnée en regardant la classe majoritaire de ses k voisins les plus proches.
• La mesure de dissimilarité est cruciale et doit respecter certaines propriétés (non-dégénérescence, symétrie, inégalité triangulaire).
• Les distances les plus courantes pour les attributs numériques sont la distance euclidienne, la distance de Manhattan et la similarité cosinus.
• Pour les attributs nominaux, la dissimilarité peut être simplement le nombre d’attributs différents.
• La normalisation des attributs numériques est indispensable pour éviter que des attributs à grande échelle dominent la distance.
• La classification de textes peut être abordée avec ces méthodes en représentant les documents sous forme de sacs de mots.