Notes de Cours : Data Mining

Ce document présente les concepts fondamentaux de la classification supervisée à base d’exemplaires représentatifs, notamment l’algorithme des k plus proches voisins (kPPV), ainsi que son application à la classification de textes. Il s’adresse principalement aux étudiants en data mining ou apprentissage automatique souhaitant comprendre et appliquer ces méthodes.

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

On distingue deux grandes catégories de classifieurs supervisés :

• Ceux qui utilisent un modèle construit durant la phase d’induction, sans recours direct aux exemplaires lors de la classification (exemples : ZeroR, OneR, Naïve Bayes).
• Ceux qui utilisent directement les exemplaires pour prédire la classe d’une nouvelle donnée. Ces méthodes sont appelées classifieurs à base d’exemplaires représentatifs.

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

Approche Générale

La classification supervisée à base d’exemplaires représentatifs repose sur le principe suivant :

• On conserve l’ensemble des exemplaires X tels quels.
• Pour une nouvelle donnée x, on prédit sa classe en fonction des classes des exemplaires les plus « similaires » à x dans X.

Pour concrétiser cette méthode, il faut préciser :

1. La notion de dissimilarité ou de proximité entre données.
2. Le nombre d’exemplaires proches à considérer (paramètre k).
3. La fonction utilisée pour prédire la classe finale à partir des voisins.

Mesures de Dissimilarité

Une fonction de dissimilarité d(x,z) entre deux données x et z doit vérifier :

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

Attributs numériques

Les données sont vues comme des points dans un espace euclidien de dimension p, chaque dimension correspondant à un attribut.

Distance Euclidienne :

d(x,z) = √(∑(xi - zi)^2) pour i = 1 à p

Cette distance respecte les propriétés de la fonction d.

Distance de Manhattan :

d(x,z) = ∑ |xi - zi| pour i = 1 à p

Cosine similarity : mesure la similarité entre deux vecteurs :

s(x,z) = (∑ xi * zi) / (√(∑ xi^2) * √(∑ zi^2))

où s(x,z) ∈ [0,1]. Pour obtenir une dissimilarité :

d(x,z) = 1 - s(x,z)

Note : Pour les distances Euclidienne et Manhattan, il est important que les attributs soient sur la même échelle. On normalise souvent les attributs par :

ˆxi = (xi - min(xi)) / (max(xi) - min(xi))

pour que les valeurs soient dans [0,1].

Attributs nominaux

On utilise une fonction simple :

d(x,z) = ∑ fi(xi, zi) pour i = 1 à p

avec fi(xi, zi) = 0 si xi = zi, 1 sinon.

Dans ce cas, la dissimilarité est le nombre d’attributs différents entre x et z.

L’algorithme des plus proches voisins (kPPV)

Algorithme simple basé sur la recherche des k exemplaires les plus proches d’une nouvelle donnée x :

1. Déterminer les k plus proches voisins de x dans X selon une fonction de dissimilarité d.
2. Prédire la classe de x comme la classe majoritaire parmi ces k voisins.

Le paramètre k est choisi en fonction de la performance sur un ensemble de test.

Exemple

Soit un ensemble X de points avec classes associées. Pour une nouvelle donnée x, on calcule d(x, xi) pour chaque xi ∈ X, on sélectionne les k plus petits d(x, xi), puis on attribue à x la classe la plus fréquente parmi ces k voisins.

Application : Classification de Textes

Présentation du problème

Chaque exemplaire est un document texte à classer. Exemples :

• Détection de spam : classes {spam, non-spam}.
• Classification de pages Web selon un sujet : classes {traite_sujet_X, ne_traite_pas_sujet_X}.
• Classification thématique de pages Web : classes {actualités, sport, arts, technologie, …}.

Représentation des textes en sacs de mots

Un texte est représenté par un vecteur d’attributs x = (x1, x2, ..., xp), chaque attribut correspondant à un mot du vocabulaire V = {m1, m2, ..., mp}.

Deux versions courantes :

• Sacs de mots version binaire :

xi(t) = 1 si mi ∈ texte t
       0 sinon
  

• Sacs de mots version TF.IDF :

xi(t) = 0 si n(mi,t) = 0
       = (1 + log(n(mi,t))) * log(wi) sinon
  

avec :

• n(mi,t) : nombre d’occurrences du mot mi dans le texte t
• wi = |X| / n(mi) où n(mi) est le nombre de textes contenant mi dans l’ensemble X

Construction du vocabulaire V

Le vocabulaire est construit à partir des exemplaires X en sélectionnant, pour chaque classe y, les P/|Y| mots les plus fréquents dans les textes de cette classe, puis en prenant l’union de ces ensembles.

Prétraitement (normalisation) des textes

Pour que le vocabulaire reflète mieux le contenu des textes :

1. Stemming : réduire chaque mot à sa racine (ex. : afficher et affichage → affich).
2. Suppression des mots non importants (stop words) : prépositions, pronoms, articles, etc.

Classification avec Naïve Bayes

Pour prédire la classe y d’un texte t :

1. Représenter tous les textes par des vecteurs binaires selon le modèle sacs de mots binaire.
2. Estimer les probabilités conditionnelles Pr[xi | y, X] :

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

avec n(y) le nombre de textes de la classe y et n(mi, y) le nombre de textes de la classe y contenant le mot mi.

3. Prédire la classe de t par :

y = argmax_{y ∈ Y} ( ∏_{i=1}^p Pr[xi | y, X] ) * Pr[y | X]
  

Classification avec la méthode kPPV

Pour prédire la classe d’un texte t :

1. Représenter les textes par des vecteurs selon le modèle sacs de mots version TF.IDF.
2. Choisir la mesure de dissimilarité : cosine similarity transformée en dissimilarité.
3. Appliquer l’algorithme kPPV :
• Calculer d(x, xi) pour tous xi ∈ X.
• Identifier les k plus proches voisins (k plus petites valeurs de d).
• Prédire la classe y comme la classe majoritaire parmi ces k voisins.

Exemple

Voir TD#5 pour un exemple détaillé d’application de kPPV à la classification de textes.

Glossaire des termes clés

• Classifieur supervisé : méthode d’apprentissage utilisant un ensemble d’exemples étiquetés pour prédire la classe de nouvelles données.
• Exemplaire représentatif : donnée d’apprentissage utilisée directement pour la classification dans les méthodes à base d’exemplaires.
• k plus proches voisins (kPPV) : algorithme qui classe une donnée en fonction des classes des k exemplaires les plus proches.
• Dissimilarité : mesure de la différence entre deux données, respectant certaines propriétés mathématiques.
• Distance Euclidienne : racine carrée de la somme des carrés des différences entre attributs.
• Distance de Manhattan : somme des valeurs absolues des différences entre attributs.
• Cosine similarity : mesure de similarité basée sur le cosinus de l’angle entre deux vecteurs.
• Sacs de mots : représentation d’un texte par un vecteur d’attributs correspondant à la présence ou fréquence de mots.
• TF.IDF : pondération des mots dans un texte tenant compte de leur fréquence locale et de leur rareté globale.
• Stemming : réduction des mots à leur racine pour normaliser le vocabulaire.
• Stop words : mots courants et peu informatifs supprimés du texte avant analyse.
• Naïve Bayes : classifieur probabiliste basé sur l’hypothèse d’indépendance conditionnelle des attributs.

Points clés à retenir

• La classification supervisée à base d’exemplaires utilise directement les données d’apprentissage pour la prédiction.
• La mesure de dissimilarité est essentielle pour comparer les données, avec des choix adaptés selon le type d’attributs.
• L’algorithme kPPV est simple et efficace, basé sur la majorité des classes des voisins proches.
• La représentation des textes par sacs de mots permet d’appliquer ces méthodes à la classification de documents.
• Le prétraitement des textes (stemming, suppression des stop words) améliore la qualité du vocabulaire.
• Naïve Bayes et kPPV sont deux approches différentes mais complémentaires pour la classification de textes.