Cours decision trees classification et regression data mining

Ce document académique propose une introduction aux arbres de décision, une méthode essentielle de classification et de régression en apprentissage automatique. Destiné aux étudiants universitaires, il aborde les points clés suivants :

Principes de construction et types d'arbres de décision.
Évaluation des performances et algorithmes d'induction (Hunt's, CART, C4.5).
Critères de division (entropie, Gini) et gestion du surapprentissage (élagage).

L'objectif est de doter les étudiants des outils pour comprendre et appliquer cette technique fondamentale.

Cours Decision Trees Classification et Regression Data mining

Télécharger PDF

Arbres de Décision : Concepts Clés

Les arbres de décision sont une méthode populaire et intuitive en apprentissage automatique, utilisée pour les tâches de classification et de régression. Ils permettent de construire un modèle prédictif à partir d'un ensemble de données, sous la forme d'une structure arborescente ou d'un ensemble de règles de décision.

Structure d'un Arbre de Décision

Une structure arborescente similaire à un organigramme.
Un nœud interne représente un test sur un attribut spécifique.
Une branche représente un résultat possible de ce test.
Les nœuds feuilles représentent les étiquettes de classe (pour la classification) ou la distribution des classes/valeurs (pour la régression).

Types d'Arbres de Décision

Arbres de Classification : La variable cible prend un ensemble discret de valeurs (par exemple, oui/non, chat/chien).
Arbres de Régression : La variable cible peut prendre des valeurs continues (par exemple, le prix d'une maison, la température).

Exemple d'Application : Le Score de Crédit

Considérons un exemple de score de crédit où l'objectif est de prédire si un emprunteur sera en défaut de paiement.

Un ensemble de données d'entraînement contient des informations sur des emprunteurs passés (par exemple, propriétaire, statut matrimonial, revenu annuel) et leur statut de défaut de paiement (oui/non).

Pour un nouvel emprunteur, l'arbre de décision utilise ces attributs pour le guider à travers des tests (nœuds internes) jusqu'à un nœud feuille qui lui attribue une classe de défaut ou non.

Il est important de noter qu'il peut exister plusieurs arbres de décision différents qui s'adaptent aux mêmes données d'entraînement.

Évaluation de la Performance d'un Modèle

La performance d'un modèle (classifieur) est cruciale. Une méthode courante d'évaluation est la matrice de confusion.

Bien que la matrice de confusion offre une vue détaillée, une métrique unique est souvent préférée pour comparer différents modèles, comme l'exactitude (accuracy). L'objectif est d'atteindre la plus haute exactitude ou le plus faible taux d'erreur sur les données de test.

Algorithmes d'Induction d'Arbres de Décision

Trouver l'arbre de décision optimal est un problème NP-difficile. En pratique, des algorithmes efficaces sont utilisés pour construire des arbres raisonnablement précis en un temps raisonnable.

Parmi les algorithmes d'induction populaires, on trouve :

L'Algorithme de Hunt (l'un des plus anciens)
CART
ID3
C4.5
SLIQ
SPRINT

Une caractéristique commune à ces algorithmes est qu'ils emploient tous une stratégie gloutonne. Cette stratégie consiste à diviser les enregistrements en fonction d'un test d'attribut qui optimise un certain critère à chaque étape.

L'Algorithme de Hunt

Soit Dt l'ensemble des enregistrements d'entraînement qui atteignent un nœud t. L'algorithme de Hunt procède comme suit :

Si Dt contient des enregistrements appartenant à la même classe yt, alors t est un nœud feuille étiqueté yt.
Si Dt contient des enregistrements avec les mêmes valeurs d'attributs, alors t est un nœud feuille étiqueté avec la classe majoritaire yt.
Si Dt est un ensemble vide, alors t est un nœud feuille étiqueté par la classe par défaut, yd.
Si Dt contient des enregistrements appartenant à plus d'une classe, un test d'attribut est utilisé pour diviser les données en sous-ensembles plus petits. La procédure est appliquée récursivement à chaque sous-ensemble.

Construction d'un Arbre avec l'Algorithme de Hunt : Exemple du Score de Crédit

Considérons à nouveau l'exemple du score de crédit avec des données d'emprunteurs comprenant les attributs "Propriétaire", "Statut Matrimonial", "Revenu Annuel", et la variable cible "Emprunteur en Défaut".

Étape 1 : Division des exemples selon l'attribut "Propriétaire". Les emprunteurs "Propriétaire : Oui" sont tous "Non en défaut". Ce sous-ensemble devient un nœud feuille "Défaut = Non". Les emprunteurs "Propriétaire : Non" présentent plusieurs classes et nécessitent une division ultérieure.
Étape 2 : Pour le sous-ensemble "Propriétaire : Non", une division est effectuée selon l'attribut "Statut Matrimonial". Les emprunteurs "Marié(e)" sont tous "Non en défaut". Ce sous-ensemble devient un nœud feuille "Défaut = Non". Les emprunteurs "Célibataire ou Divorcé(e)" nécessitent une division supplémentaire.
Étape 3 : Pour le sous-ensemble "Propriétaire : Non" et "Statut Matrimonial : Célibataire/Divorcé(e)", une division est effectuée selon l'attribut "Revenu Annuel". Par exemple, si le revenu est inférieur à 80 000, ils ne sont pas en défaut, et s'il est supérieur à 80 000, ils sont en défaut.

Ce processus récursif continue jusqu'à ce que tous les nœuds soient des feuilles, ou qu'une condition d'arrêt soit remplie.

Spécification des Conditions de Test

La manière de spécifier une condition de test dépend de plusieurs facteurs :

Type d'attribut : Nominal, Ordinal, Continu.
Nombre de divisions : Division binaire ou multi-voies.

Division Basée sur les Attributs Nominaux

Division multi-voies : Utilise autant de partitions que de valeurs distinctes de l'attribut (ex: Type de Voiture : Famille, Sport, Luxe).
Division binaire : Divise les valeurs en deux sous-ensembles. Nécessite de trouver le partitionnement optimal (ex: {Sport} ou {Famille, Luxe}).

Division Basée sur les Attributs Ordinaux

Division multi-voies : Utilise autant de partitions que de valeurs distinctes (ex: Taille : Petite, Moyenne, Grande).
Division binaire : Divise les valeurs en deux sous-ensembles en respectant l'ordre (ex: {Petite, Moyenne} ou {Grande}). Une division {Petite, Grande} vs {Moyenne} ne respecterait pas l'ordre et serait généralement sous-optimale.

Division Basée sur les Attributs Continus

Plusieurs approches sont possibles :

Décision binaire : (A < v) ou (A ≥ v), où 'v' est un seuil. Cela implique de considérer tous les seuils possibles pour trouver la meilleure coupure, ce qui peut être gourmand en calcul.
Discrétisation : Convertir l'attribut continu en un attribut catégoriel ordinal en définissant des plages (ex: Revenu Imposable : <10 000, [10 000,25 000), etc.). L'algorithme doit alors considérer toutes les plages possibles.

Détermination de la Meilleure Division

Une approche gloutonne est utilisée pour déterminer la meilleure division, en privilégiant les nœuds avec une distribution de classe homogène.

Mesure de l'Impureté des Nœuds

Il est nécessaire de mesurer l'impureté d'un nœud. Les mesures courantes incluent :

L'Entropie : Une mesure de l'incertitude dans un ensemble d'entraînement due à la présence de plusieurs classifications possibles (utilisée dans ID3 et C4.5).
L'Impureté de Gini : Utilisée dans CART, SLIQ, SPRINT.

Ces mesures d'impureté prennent une valeur minimale (zéro) pour un nœud "pur" (où une seule classe a une probabilité de 1) et une valeur maximale lorsque la distribution des classes est uniforme.

Le Gain

Le gain d'une division d'attribut compare l'impureté du nœud parent avec l'impureté moyenne pondérée des nœuds enfants. Maximiser le gain revient à minimiser l'impureté moyenne pondérée des nœuds enfants. Si l'entropie est utilisée, le gain est appelé "gain d'information".

Pour un problème à deux classes, les différentes mesures d'impureté sont généralement cohérentes.

Problème et Solution pour la Mesure d'Impureté

Les mesures d'impureté peuvent favoriser les attributs qualitatifs ayant un grand nombre de valeurs distinctes. Une condition de test avec un grand nombre de résultats n'est pas toujours souhaitable, car le nombre d'enregistrements dans chaque partition peut devenir trop faible pour faire des prédictions fiables.

Deux façons de surmonter ce problème :

Générer uniquement des arbres de décision binaires (comme dans CART).
Utiliser le Gain Ratio, qui prend en compte le nombre de partitions produites par l'attribut (utilisé dans C4.5).

Le Gain Ratio

Le Gain Ratio, utilisé dans l'algorithme C4.5, est conçu pour pallier l'inconvénient des mesures d'impureté qui favorisent les attributs à nombreuses valeurs distinctes en pondérant le gain par une mesure de la "taille" de la division.

Avantages des Arbres de Décision

Les arbres de décision basés sur la classification offrent plusieurs avantages :

Coût de construction faible : Relativement peu coûteux à construire.
Classification rapide : Extrêmement rapides pour classifier de nouveaux enregistrements.
Facilité d'interprétation : Faciles à interpréter, surtout pour les arbres de petite taille.
Précision comparable : Leur précision est comparable à d'autres techniques de classification pour de nombreux jeux de données simples.

Problèmes Pratiques : Le Surapprentissage et le Sous-apprentissage

Un problème courant est le surapprentissage (overfitting) des données. Cela peut survenir à cause du bruit dans les données, d'un nombre trop faible d'exemples d'entraînement pour représenter la vraie fonction cible, ou lorsque l'arbre de décision dépend trop de caractéristiques non pertinentes des instances d'entraînement. En conséquence, le modèle fonctionne bien sur les données d'entraînement, mais ses performances sont relativement médiocres sur des instances non vues.

Sous-apprentissage et Surapprentissage

Sous-apprentissage (Underfitting) : Se produit lorsque le modèle est trop simple pour capturer la structure sous-jacente des données. Les erreurs d'entraînement et de test sont toutes deux élevées.
Surapprentissage (Overfitting) : Se produit lorsque le modèle est trop complexe et modélise les détails et le bruit du jeu d'entraînement, échouant ainsi sur le jeu de test.

Le Rasoir d'Occam et la Complexité du Modèle

Le Rasoir d'Occam suggère que, étant donné deux modèles avec des erreurs de généralisation similaires, il faut préférer le modèle le plus simple au modèle le plus complexe. Pour les modèles complexes, il y a une plus grande probabilité qu'ils aient été ajustés accidentellement à des erreurs dans les données. Par conséquent, la complexité du modèle doit être prise en compte lors de son évaluation.

Comment Gérer le Surapprentissage ?

Il existe deux approches principales pour lutter contre le surapprentissage :

L'Élagage Préalable (Pre-Pruning ou Règle d'Arrêt Précoce)

Consiste à arrêter l'algorithme avant que l'arbre ne soit entièrement développé. Les conditions d'arrêt typiques pour un nœud incluent :

Arrêter si toutes les instances appartiennent à la même classe.
Arrêter si toutes les valeurs d'attribut sont identiques.

Des conditions plus restrictives peuvent être utilisées :

Seuil de taille : Élaguer si le sous-ensemble contient moins d'un certain seuil d'instances spécifié par l'utilisateur (par exemple, 5 ou 10 instances).
Seuil de profondeur maximale : Élaguer si la longueur de la branche est égale à un nombre spécifié par l'utilisateur (par exemple, 3 ou 4).
Arrêter si l'expansion du nœud actuel n'améliore pas les mesures d'impureté (par exemple, Gini ou le gain d'information).

L'Élagage Post-Pruning (Élagage Après Construction)

Cette approche implique de construire un arbre complet, puis de l'élaguer.

1. Élagage par Réduction d'Erreur (Reduced-Error Pruning)

Cette méthode procède comme suit :

Construire l'arbre de décision dans son intégralité.
Élaguer les nœuds de l'arbre de décision de manière ascendante (bottom-up).
Utiliser un ensemble d'exemples séparé (ensemble d'élagage ou de validation), distinct des exemples d'entraînement, pour évaluer l'utilité de l'élagage des nœuds.
Si l'erreur de généralisation (ou l'exactitude) s'améliore après l'élagage, remplacer le sous-arbre par un nœud feuille.
L'étiquette de classe du nœud feuille est déterminée par la classe majoritaire des instances du sous-arbre.
L'élagage des nœuds est poursuivi tant qu'un élagage supplémentaire diminue l'exactitude sur l'ensemble de validation.

2. Élagage Post-Règles (Rule-Post Pruning, utilisé par C4.5)

Cette méthode est utile lorsque les données sont limitées :

Construire l'arbre de décision dans son intégralité.
Convertir l'arbre appris en un ensemble équivalent de règles, en créant une règle pour chaque chemin allant du nœud racine à un nœud feuille.
Élaguer (généraliser) chaque règle en supprimant les préconditions qui améliorent son exactitude estimée. Un ensemble d'exemples séparé (ensemble de validation) est utilisé pour estimer l'exactitude des règles.
Trier les règles élaguées par leur exactitude estimée, et les considérer dans cet ordre lors de la classification des instances ultérieures.

Foire Aux Questions (FAQ)

Qu'est-ce qu'un arbre de décision et à quoi sert-il ?

Un arbre de décision est un modèle d'apprentissage automatique représenté par une structure arborescente. Il est utilisé pour prendre des décisions en divisant un ensemble de données en sous-ensembles de plus en plus petits en fonction de tests sur des attributs. Il est applicable aux tâches de classification (prédire une catégorie) et de régression (prédire une valeur continue).

Quelles sont les principales mesures d'impureté utilisées pour construire un arbre de décision ?

Les deux principales mesures d'impureté sont l'Entropie et l'Impureté de Gini. L'Entropie mesure l'incertitude dans un ensemble de données, tandis que l'Impureté de Gini mesure la probabilité d'une classification incorrecte si un élément est choisi au hasard dans l'ensemble. L'objectif est de minimiser cette impureté lors de chaque division du nœud.

Comment les arbres de décision gèrent-ils le problème du surapprentissage ?

Le surapprentissage peut être géré de deux manières principales : l'élagage préalable (pre-pruning) et l'élagage postérieur (post-pruning). L'élagage préalable arrête la croissance de l'arbre avant qu'il ne devienne trop complexe, tandis que l'élagage postérieur construit un arbre complet puis supprime les branches inutiles ou les transforme en règles pour améliorer la généralisation sur de nouvelles données.