Notes de Cours : Data Mining

Ce matériel couvre la classification supervisée par arbres de décision, une méthode largement utilisée en data mining. Il s’adresse aux étudiants et chercheurs souhaitant comprendre la construction et l’interprétation des arbres de décision, ainsi que l’algorithme ID3 pour leur induction.

Introduction à la classification par arbres de décision

La classification supervisée consiste à attribuer une classe y à une donnée x à partir d’un ensemble d’exemples (xi, yi), où xi est un vecteur d’attributs (quantitatifs ou qualitatifs) et yi une classe qualitative. L’objectif est de construire un algorithme (classeur) capable de prédire la classe d’une nouvelle donnée.

Un arbre de décision est un modèle de classification basé sur une structure arborescente :

• Chaque nœud (y compris la racine) correspond à un test logique sur la valeur d’un attribut.
• Chaque branche partant d’un nœud correspond à une ou plusieurs valeurs possibles de ce test.
• Chaque feuille est associée à une classe y ∈ Y.

Pour classer une nouvelle donnée x, on parcourt l’arbre depuis la racine jusqu’à une feuille en suivant les branches correspondant aux valeurs des attributs de x. La classe prédite est celle associée à la feuille atteinte.

Une donnée x est dite couverte par un nœud si ce nœud fait partie du chemin parcouru pour x. Un arbre est optimal s’il minimise le nombre d’erreurs de classification, c’est-à-dire maximise la précision.

Exemple d’arbre de décision : le cas "Jouer Tennis"

L’arbre comporte trois nœuds :

• Racine : test sur l’attribut « Ciel » avec 3 branches possibles.
• Nœud « Vent » : test avec 2 branches.
• Nœud « Humidité » : test avec 2 branches.

Il y a cinq feuilles, trois associées à la classe « oui » et deux à la classe « non ». Chaque branche est marquée par la valeur de l’attribut correspondant.

Par exemple, pour la donnée (Couvert, Fraîche, Élevée, Fort), on suit le chemin correspondant aux valeurs successives des attributs dans l’arbre pour déterminer la classe prédite.

Les nœuds couvrent différents sous-ensembles des données : la racine couvre tous les exemples, tandis que le nœud « Humidité = Élevée » couvre uniquement les exemples où l’humidité est élevée.

Construction d’un arbre de décision

Approches d’induction

Les algorithmes les plus connus pour construire un arbre de décision sont :

• ID3 : ne considère que des attributs nominaux.
• C4.5 et C5.0 : extensions de ID3 qui gèrent aussi des attributs quantitatifs.

Cette section se concentre sur l’algorithme ID3 (Iterative Dichotomiser 3), développé par Ross Quinlan en 1979.

Caractéristiques de l’algorithme ID3

• Ne prend en compte que des attributs nominaux.
• Chaque nœud teste la valeur d’un seul attribut.
• Chaque feuille correspond à une combinaison unique des valeurs des attributs.

Description récursive de l’algorithme ID3

ID3(X, A)
  Entrées :
    X = ensemble d’exemples
    A = ensemble d’attributs
  Sortie :
    Sous-arbre de décision

  1) Choisir un attribut am ∈ A qui maximise le gain d’information
  2) Construire la racine avec le test sur am
  3) Pour chaque valeur v de am :
       - Construire la branche correspondante
       - Appeler récursivement ID3(Xv, A - {am}), où Xv est le sous-ensemble de X où am = v
  4) Cas d’arrêt (création d’une feuille) :
       - Si tous les exemples de X ont la même classe y, créer une feuille avec y
       - Si X est vide, créer une feuille avec la classe la plus fréquente dans le nœud-père
       - Si A est vide mais X non vide, créer une feuille avec la classe la plus fréquente dans X

À chaque étape, l’ensemble X est partitionné en sous-ensembles disjoints selon les valeurs de l’attribut choisi am. Le nombre de branches est égal au nombre de valeurs de am.

Choix de l’attribut am : le gain d’information

Le choix de l’attribut am est crucial et repose sur la notion d’entropie et de gain d’information.

Entropie d’un ensemble d’exemples X :

H(X) = - ∑_y∈Y p_y log₂(p_y)

où p_y est la proportion d’exemples de X appartenant à la classe y.

• H(X) ∈ [0,1]
• H(X) = 0 si tous les exemples ont la même classe (ensemble homogène)
• H(X) est maximal (1) si les exemples sont uniformément répartis entre toutes les classes (ensemble hétérogène)

Gain d’information pour un attribut aj :

G(X, aj) = H(X) - ∑_{v∈Valeurs(aj)} (|Xv| / |X|) H(Xv)

où Xv est le sous-ensemble de X pour lequel l’attribut aj prend la valeur v.

• Le gain d’information mesure la réduction d’entropie obtenue en partitionnant X selon aj.
• G(X, aj) ∈ [0,1], toujours positif ou nul.
• L’attribut choisi am est celui qui maximise G(X, aj), c’est-à-dire qui produit les sous-ensembles les plus homogènes.

Interprétation

En choisissant l’attribut avec le gain d’information maximal, on cherche à réduire au maximum l’hétérogénéité (entropie) des sous-ensembles à chaque nœud, ce qui améliore la précision de la classification.

Exemple simplifié

Supposons un ensemble X avec 10 exemples répartis en deux classes : 6 de classe A et 4 de classe B.

Calcul de l’entropie initiale :

H(X) = - (6/10) log₂(6/10) - (4/10) log₂(4/10) ≈ -0.6 × (-0.737) - 0.4 × (-1.322) ≈ 0.971

Supposons un attribut aj avec deux valeurs possibles v1 et v2, partitionnant X en :

• Xv1 : 4 exemples (3 de classe A, 1 de classe B)
• Xv2 : 6 exemples (3 de classe A, 3 de classe B)

Calcul des entropies des sous-ensembles :

H(Xv1) = - (3/4) log₂(3/4) - (1/4) log₂(1/4) ≈ 0.811

H(Xv2) = - (3/6) log₂(3/6) - (3/6) log₂(3/6) = 1

Entropie moyenne pondérée :

(4/10) × 0.811 + (6/10) × 1 = 0.324 + 0.6 = 0.924

Gain d’information :

G(X, aj) = 0.971 - 0.924 = 0.047

Si un autre attribut ak donne un gain supérieur, il sera préféré pour le test au nœud.

Glossaire des termes clés

• Arbre de décision : modèle de classification sous forme d’arbre où chaque nœud correspond à un test sur un attribut et chaque feuille à une classe.
• Classification supervisée : apprentissage à partir d’exemples étiquetés pour prédire la classe de nouvelles données.
• Classeur : algorithme ou modèle qui attribue une classe aux données.
• Entropie : mesure de l’hétérogénéité d’un ensemble d’exemples par rapport à leurs classes.
• Gain d’information : réduction d’entropie obtenue en partitionnant un ensemble selon un attribut.
• ID3 : algorithme d’induction d’arbres de décision utilisant le gain d’information, ne traitant que les attributs nominaux.
• Nœud : élément d’un arbre représentant un test ou une décision.
• Feuille : nœud terminal d’un arbre, associé à une classe.
• Attribut nominal : variable catégorielle avec un nombre fini de valeurs distinctes.
• Partition : division d’un ensemble en sous-ensembles disjoints.

Points clés à retenir

• Un arbre de décision est un modèle graphique de classification supervisée basé sur des tests successifs d’attributs.
• L’algorithme ID3 construit l’arbre en choisissant à chaque étape l’attribut maximisant le gain d’information.
• L’entropie mesure l’hétérogénéité d’un ensemble d’exemples ; le gain d’information mesure la réduction d’entropie.
• La construction est récursive et s’arrête lorsque tous les exemples d’un nœud ont la même classe ou que les attributs sont épuisés.
• Les arbres de décision sont faciles à interpréter et permettent de visualiser les règles de classification.