Notes de Cours : Data Mining

Ce document présente les notions fondamentales de la classification supervisée en data mining, ainsi que des méthodes simples pour construire des modèles prédictifs. Il s'adresse aux étudiants et débutants en apprentissage automatique souhaitant comprendre les bases de la classification et des approches bayésiennes.

Introduction à la Classification Supervisée

Définition du problème de classification supervisée (PCS)

La classification supervisée consiste à prédire la classe d'une nouvelle donnée à partir d'un ensemble d'exemplaires déjà étiquetés. On dispose d'un ensemble d'exemples noté X = {(x1,y1), (x2,y2), ..., (xn,yn)}, où chaque exemplaire est un couple :

• x : un vecteur de p attributs (x1, ..., xp) appartenant à un domaine D bien défini ;
• y : une classe (ou étiquette) nominale appartenant à un ensemble fini Y.

Si |Y| = 2, on parle de classification binaire, sinon de classification multi-classes. Chaque exemplaire appartient à une seule classe vraie, inconnue.

L'objectif est de construire un classeur (algorithme) qui, en entrée, reçoit un vecteur x et en sortie prédit la classe y correspondante.

On distingue deux ensembles :

• Échantillon d’apprentissage (training set) : utilisé pour induire le classeur ;
• Échantillon de test (testing set) : utilisé pour évaluer la performance du classeur.

Il est crucial que l’échantillon de test soit indépendant de l’échantillon d’apprentissage pour éviter une surestimation de la performance.

Deux processus sont à distinguer dans le cycle de vie d’un classeur :

1. Induction (training) du classeur ;
2. Utilisation du classeur comme une « boîte noire » pour prédire de nouvelles données.

Approche très naïve : la méthode ZeroR

ZeroR est une méthode simple qui ignore totalement les attributs :

• Version 1 : prédit une classe au hasard parmi Y ;
• Version 2 : prédit la classe la plus fréquente dans l’échantillon d’apprentissage.

La méthode ZeroR sert de référence minimale (baseline) car son taux de classification est généralement très faible. Toute méthode fiable doit surpasser ZeroR.

Approche Bayésienne et Méthodes Simples

Introduction à l’approche Bayésienne

Cette approche considère les données x et y comme des variables aléatoires X et Y. Le problème de classification revient à estimer la probabilité conditionnelle :

Pr[y | x, X], pour tout y ∈ Y

La prédiction consiste à choisir la classe la plus probable :

y = argmaxy ∈ Y Pr[y | x, X]

L’induction du classeur correspond à l’estimation de ces probabilités conditionnelles à partir des données d’apprentissage. Cependant, estimer Pr[y | x, X] directement est souvent impraticable à cause du grand nombre de combinaisons possibles de valeurs d’attributs.

Des simplifications permettent d’obtenir des méthodes efficaces, notamment OneR et Naïve Bayes.

Méthode OneR

OneR simplifie l’approche bayésienne en utilisant un seul attribut à la fois. Le principe est :

1. Pour chaque attribut i, construire un classeur basé uniquement sur cet attribut.
2. Estimer la probabilité conditionnelle Pr[y | xi, X] pour chaque valeur xi de l’attribut i :

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

où :

• n(xi, y) est le nombre d’exemplaires ayant la valeur xi pour l’attribut i et appartenant à la classe y ;
• n(xi) est le nombre d’exemplaires ayant la valeur xi pour l’attribut i.

3. Évaluer le taux de classification correcte de chaque classeur.
4. Choisir le classeur basé sur l’attribut qui donne la meilleure performance.

Exemple : Considérons un jeu de données « jouer tennis » avec un attribut « météo » ayant les valeurs {ensoleillé, pluvieux, nuageux} et une classe {oui, non} indiquant si l’on joue au tennis. Pour chaque valeur de « météo », on calcule la classe la plus fréquente et on construit un classeur qui prédit cette classe en fonction de la météo uniquement.

Méthode de Naïve Bayes

La méthode de Naïve Bayes étend l’approche bayésienne en supposant que les attributs sont conditionnellement indépendants, ce qui simplifie grandement le calcul des probabilités conditionnelles. Cette méthode sera détaillée dans la suite du cours.

Glossaire des termes clés

• Classification supervisée : Tâche consistant à prédire une classe à partir d’exemples étiquetés.
• Exemplaire : Un couple (x, y) où x est un vecteur d’attributs et y la classe associée.
• Attribut : Caractéristique ou variable décrivant un exemplaire.
• Classe (étiquette) : Valeur nominale représentant la catégorie d’un exemplaire.
• Échantillon d’apprentissage (training set) : Ensemble d’exemples utilisés pour construire un modèle.
• Échantillon de test (testing set) : Ensemble d’exemples utilisés pour évaluer un modèle.
• Classeur : Algorithme ou modèle qui prédit la classe d’un exemplaire.
• ZeroR : Méthode naïve qui prédit la classe la plus fréquente sans utiliser les attributs.
• Approche bayésienne : Méthode probabiliste qui prédit la classe la plus probable selon Pr[y | x].
• OneR : Méthode bayésienne simplifiée utilisant un seul attribut pour la classification.

Points clés à retenir

• La classification supervisée vise à prédire une classe à partir d’exemples étiquetés.
• Il est essentiel de séparer les données d’apprentissage et de test pour évaluer correctement un modèle.
• ZeroR est une méthode de référence très simple, souvent utilisée comme baseline.
• L’approche bayésienne repose sur le calcul des probabilités conditionnelles Pr[y | x].
• OneR simplifie l’approche bayésienne en utilisant un seul attribut, facilitant l’estimation des probabilités.
• La méthode de Naïve Bayes repose sur l’hypothèse d’indépendance conditionnelle des attributs.