Classification Supervisée (par Apprentissage)

Cet article traite de la classification supervisée par apprentissage automatique, une méthode essentielle en intelligence artificielle pour attribuer automatiquement une classe à un individu ou un objet à partir d'exemples préalablement classifiés. Il s'adresse aux étudiants et chercheurs débutants en apprentissage automatique, en particulier ceux qui souhaitent comprendre comment fonctionnent les arbres de décision, une technique largement utilisée pour créer des modèles de classification interprétables.

La question

Le travail s'intéresse au problème de la classification automatique d'individus ou d'objets à partir d'exemples étiquetés. Plutôt que de s'appuyer sur un système expert construit manuellement à partir de règles définies par des spécialistes, il s'agit ici d'extraire automatiquement une procédure de classification à partir d'un ensemble d'exemples. Cette approche inductive vise à construire une règle générale capable de prédire correctement la classe d'exemples nouveaux, non vus lors de l'apprentissage. Le défi est de concevoir une méthode qui, à partir d'un échantillon d'apprentissage, génère un modèle avec un bon pouvoir prédictif, tout en étant compréhensible et utilisable dans des contextes réels comme le diagnostic médical.

Concepts de base

Avant d'aborder les algorithmes, il est important de comprendre quelques notions fondamentales :

• Classification supervisée : méthode d'apprentissage où chaque exemple est décrit par des attributs et une classe connue. L'objectif est d'apprendre une fonction qui associe une classe à toute nouvelle description.
• Arbres de décision : structure arborescente où chaque nœud interne correspond à un test sur un attribut, et chaque feuille à une classe. Ils permettent de représenter graphiquement une procédure de classification sous forme de règles facilement interprétables.
• Attributs : caractéristiques descriptives des exemples, pouvant être numériques (ex : température) ou catégoriques (ex : présence d'une gorge irritée).
• Tests dans les nœuds : chaque nœud interne applique un test sur un attribut, dirigeant l'exemple vers une branche selon la valeur de cet attribut.
• Pureté d'un nœud : mesure du degré de mélange des classes dans un sous-ensemble d'exemples. Un nœud est pur si tous les exemples appartiennent à la même classe.
• Fonctions de pureté : utilisées pour évaluer la qualité d'un test. Deux fonctions classiques sont :
• Entropie : Entropie(p) = - Σ P(k/p) × log(P(k/p)) où P(k/p) est la proportion d'exemples de classe k au nœud p. Elle est minimale (0) si le nœud est pur et maximale quand les classes sont également réparties.
• Indice de Gini : Gini(p) = 1 - Σ P(k/p)^2, qui mesure aussi l'impureté, avec des propriétés similaires à l'entropie.

Gain d'information : mesure l'amélioration apportée par un test, calculée comme la différence entre l'impureté du nœud avant le test et la moyenne pondérée des impuretés des sous-nœuds après le test. Le test avec le gain maximal est choisi.

Approche

La méthode étudiée consiste à construire un arbre de décision de manière récursive :

• On commence avec l'ensemble complet d'exemples à la racine.
• On décide si le nœud courant est terminal (par exemple, s'il est pur ou si la classification est suffisamment précise).
• Si ce nœud n'est pas terminal, on sélectionne le test (sur un attribut) qui maximise le gain d'information.
• On divise l'ensemble d'exemples selon les résultats du test, créant des sous-nœuds.
• On répète ce processus récursivement pour chaque sous-nœud.
• Enfin, on attribue à chaque feuille la classe majoritaire des exemples qui y sont associés.

Ce processus descend dans l'arbre sans revenir en arrière, ce qui signifie que les choix faits à chaque étape sont définitifs. Pour améliorer la qualité du modèle, une phase d'élagage peut être appliquée après la construction initiale afin de supprimer certains sous-arbres et réduire ainsi le risque de surapprentissage.

Résultats

Les algorithmes d'apprentissage par arbres de décision permettent de construire des modèles avec une erreur apparente faible sur l'échantillon d'apprentissage. Par exemple, dans un cas simple de classification de patients en malades ou bien portants selon la température et la présence d'une gorge irritée, l'arbre produit des règles claires et interprétables. De même, dans un exemple bancaire, un arbre construit à partir d'attributs comme le montant moyen, l'âge, la résidence et le niveau d'études peut prédire si un client utilise Internet pour consulter ses comptes.

Le choix des tests est guidé par des critères quantitatifs comme le gain d'information basé sur l'entropie ou l'indice de Gini. Ces critères permettent de sélectionner les attributs qui discriminent le mieux les classes, améliorant ainsi la pureté des nœuds et la qualité globale de la classification.

Les méthodes étudiées, telles que CART et ID3, diffèrent principalement par leurs critères de sélection des tests, leurs critères d'arrêt et leurs méthodes d'élagage, mais reposent toutes sur ce schéma général.

Limitations et questions ouvertes

Plusieurs limites subsistent :

• La construction d'un arbre parfait, qui classifie sans erreur tous les exemples, n'est pas toujours possible, notamment si des exemples identiques appartiennent à des classes différentes.
• Le problème de trouver l'arbre d'erreur apparente minimale est NP-complet, ce qui rend impossible une recherche exhaustive dans un temps raisonnable.
• Le processus de construction est glouton et ne revient jamais sur les choix faits, ce qui peut conduire à un arbre sous-optimal.
• L'erreur apparente sur l'échantillon d'apprentissage est souvent une estimation trop optimiste de l'erreur réelle sur de nouvelles données. L'arbre peut donc être surajusté (overfitting) et avoir un faible pouvoir prédictif.
• Il n'existe pas encore de critère fiable pour arrêter la croissance de l'arbre au moment optimal. Le risque d'arrêter trop tôt est généralement plus grave que celui d'arrêter trop tard.
• La phase d'élagage, bien qu'essentielle pour améliorer la généralisation, repose sur des heuristiques et peut ne pas toujours garantir une meilleure performance.

Glossaire

• Apprentissage supervisé : méthode d'apprentissage où les exemples d'entrée sont associés à des classes connues.
• Attribut : caractéristique descriptive d'un exemple, pouvant être numérique ou catégorique.
• Arbre de décision : structure arborescente utilisée pour représenter une procédure de classification sous forme de tests et de règles.
• Entropie : mesure de l'impureté d'un ensemble d'exemples, utilisée pour guider la construction des arbres.
• Indice de Gini : autre mesure d'impureté, alternative à l'entropie.
• Gain d'information : différence entre l'impureté avant et après un test, utilisée pour sélectionner le test optimal.
• Élagage : processus de suppression de sous-arbres pour réduire le surapprentissage et améliorer la généralisation.
• Erreur apparente : taux d'erreur mesuré sur l'échantillon d'apprentissage.
• Surapprentissage (overfitting) : phénomène où un modèle est trop adapté aux données d'apprentissage et performe mal sur de nouvelles données.