Data Mining Course Notes

Ce document présente les notions fondamentales de la classification supervisée en data mining, avec un focus sur deux méthodes simples : la méthode OneR adaptée aux attributs numériques et la méthode Naïve Bayes. Il s’adresse aux étudiants en informatique ou en sciences des données souhaitant comprendre et appliquer ces techniques de classification, notamment dans le cadre de la classification de textes.

Méthode OneR avec attributs numériques

La méthode OneR est une technique simple de classification supervisée initialement conçue pour des attributs de type nominal. Lorsque les attributs sont numériques, il est nécessaire de les convertir en attributs nominaux en définissant des intervalles disjoints. Par exemple, dans la base de données « Jouer Tennis », l’attribut Température (T) peut être transformé selon les intervalles suivants :

Valeur numérique (°C)	Valeur nominale
T > 32	Chaude
10 ≤ T ≤ 32	Tiède
T < 10	Fraîche

Cette conversion permet ensuite d’appliquer la méthode OneR comme pour des attributs nominaux.

Méthode de Naïve Bayes

Introduction

La méthode Naïve Bayes est une approche probabiliste de classification supervisée basée sur le théorème de Bayes. Elle suppose que les attributs sont statistiquement indépendants, ce qui simplifie grandement le calcul des probabilités conditionnelles.

Règle de Bayes

Le théorème de Bayes s’applique à trois événements aléatoires A, B et C :

Pr[A | B, C] = (Pr[B | A, C] × Pr[A | C]) / Pr[B | C]

Dans le contexte de la classification supervisée :

• A : la classe de l’exemplaire est y
• B : les valeurs des attributs de l’exemplaire sont x
• C : l’échantillon d’apprentissage est X

On peut écrire :

Pr[y | x, X] = (Pr[x | y, X] × Pr[y | X]) / Pr[x | X]

En appliquant l’hypothèse d’indépendance des attributs, on obtient :

Pr[y | x, X] ∝ Pr[x | y, X] × Pr[y | X]
          ∝ (∏(i=1 à p) Pr[xi | y, X]) × Pr[y | X]

La prédiction de la classe y pour un nouvel exemplaire x se fait par :

y = argmaxy ∈ Y (∏(i=1 à p) Pr[xi | y, X]) × Pr[y | X]

Cette méthode est appelée classifieur Naïve Bayes.

Estimation des probabilités

Estimation de Pr[y | X]

Cette probabilité correspond à la proportion d’exemplaires de la classe y dans l’échantillon d’apprentissage X :

Pr[y | X] ≈ n(y) / n

où :

• n(y) = nombre d’exemplaires de la classe y dans X
• n = nombre total d’exemplaires dans X

Estimation de Pr[xi | y, X]

• Attributs nominaux :

On estime :

Pr[xi | y, X] ≈ n(xi, y) / n(y)

avec :

• n(xi, y) = nombre d’exemplaires de la classe y dont l’attribut i vaut xi
• n(y) = nombre d’exemplaires de la classe y

• Attributs numériques :

On suppose que la distribution de xi conditionnellement à y est normale :

xi ~ N(μi, σi^2)

avec μi et σi estimés à partir des données de la classe y. La probabilité s’évalue alors par :

Pr[xi | y, X] ≈ (1 / (√(2π) σi)) × exp(- (xi - μi)^2 / (2 σi^2))

Gestion des probabilités nulles

Si pour un attribut xi et une classe y, on obtient n(xi, y) = 0, alors Pr[xi | y, X] = 0, ce qui annule la probabilité globale Pr[y | x, X]. Pour éviter ce problème, on applique un lissage en ajoutant 1 à tous les comptes n(xi, y) avant de recalculer les probabilités. Cette technique est appelée « lissage de Laplace ».

Application : classification de textes

Présentation du problème

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étection de spam : classes {spam, non-spam}
• Classification de pages Web par sujet : classes {traite_sujet_X, ne_traite_pas_sujet_X}
• Classification multi-classes : classes {actualités, sport, arts, technologie, …}

Représentation d’un texte en « sac de mots »

Pour appliquer les méthodes de classification, les textes doivent être transformés en un ensemble fixe d’attributs. La représentation la plus courante est celle du sac de mots :

• On définit un vocabulaire V = {m1, m2, …, mp} constitué d’un ensemble fini de mots.
• Pour un texte t, on définit l’attribut xi par :

xi = {
  1 si le mot mi est présent dans t
  0 sinon
}

Classifieur Naïve Bayes pour la classification de textes

Une fois la représentation en sac de mots définie, on applique la méthode Naïve Bayes :

y = argmaxy ∈ Y (∏(i=1 à p) Pr[xi | y, X]) × Pr[y | X]

Dans ce contexte, xi ne prend que deux valeurs possibles : 1 (présence du mot) ou 0 (absence).

Les probabilités conditionnelles s’estiment ainsi :

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

où :

• n(mi, y) = nombre d’occurrences du mot mi dans les textes de la classe y
• n(y) = nombre de textes de la classe y

et :

Pr[xi = 0 | y, X] = 1 - Pr[xi = 1 | y, X]

La prédiction de la classe d’un nouveau texte se fait en appliquant la formule du classifieur Naïve Bayes présentée ci-dessus.

Glossaire des termes clés

• Classification supervisée : Technique d’apprentissage automatique où un modèle est entraîné à partir d’exemples étiquetés pour prédire la classe de nouveaux exemplaires.
• Attribut nominal : Variable catégorielle prenant un nombre fini de valeurs discrètes non ordonnées.
• Attribut numérique : Variable quantitative prenant des valeurs réelles ou entières.
• Méthode OneR : Méthode simple de classification qui construit une règle basée sur un seul attribut.
• Naïve Bayes : Classifieur probabiliste basé sur le théorème de Bayes avec l’hypothèse d’indépendance des attributs.
• Théorème de Bayes : Relation fondamentale en probabilité reliant les probabilités conditionnelles inverses.
• Lissage de Laplace : Technique consistant à ajouter 1 aux comptes pour éviter des probabilités nulles.
• Sac de mots : Représentation d’un texte par la présence ou l’absence d’un ensemble fixe de mots.
• Vocabulaire : Ensemble fini de mots utilisés pour représenter les textes dans la classification.

Points clés à retenir

• La méthode OneR nécessite la conversion des attributs numériques en intervalles nominaux pour être applicable.
• Le classifieur Naïve Bayes repose sur l’hypothèse d’indépendance des attributs, ce qui simplifie le calcul des probabilités conditionnelles.
• Les probabilités Pr[y | X] et Pr[xi | y, X] s’estiment respectivement par la fréquence relative des classes et des attributs dans l’échantillon d’apprentissage.
• Pour les attributs numériques, la distribution conditionnelle est supposée normale et les paramètres sont estimés sur les données.
• Le lissage de Laplace est indispensable pour éviter que des probabilités nulles n’annulent la prédiction.
• La classification de textes utilise la représentation en sac de mots, où chaque mot du vocabulaire est un attribut binaire indiquant sa présence ou son absence.
• Le classifieur Naïve Bayes est efficace pour la classification de textes grâce à sa simplicité et à sa capacité à gérer un grand nombre d’attributs.