L'apprentissage par l'information : arbres de décision

La première grande famille d'algorithmes de cette tranche du livre repose sur une idée que tout le monde a déjà pratiquée sans le savoir : pour deviner quelque chose le plus vite possible, il faut poser la question la plus informative. C'est l'intuition du jeu de devinettes, du « Qui est-ce ? » et des vingt questions, et c'est aussi le principe qui anime l'apprentissage par l'information (information-based learning). Ce chapitre formalise cette intuition à l'aide de la théorie de l'information de Claude Shannon — l'entropie (entropy) et le gain d'information (information gain) — puis montre comment l'algorithme ID3 s'en sert pour construire automatiquement des arbres de décision (decision trees), avant d'aborder les extensions qui rendent ces modèles utilisables sur des données réelles.

La grande idée : poser la question la plus informative

Imaginez une partie de « Qui est-ce ? » où l'on doit identifier un personnage parmi quatre — Brian, John, Aphra et Aoife — en posant des questions à réponse oui/non. Deux premières questions s'offrent à vous : « Est-ce un homme ? » ou « Porte-t-il des lunettes ? ». La plupart des gens choisissent la première, et leur intuition est correcte, même si elle peut sembler paradoxale.

Personnage	Homme	Cheveux longs	Lunettes
Brian	oui	non	oui
John	oui	non	non
Aphra	non	oui	non
Aoife	non	non	non

La question des lunettes est tentante : si la réponse est « oui », on a immédiatement gagné, car seul Brian en porte. Mais ce raisonnement oublie la vraisemblance des réponses : trois fois sur quatre en moyenne, la réponse sera « non », et il faudra encore distinguer trois personnages. La question « Est-ce un homme ? », en revanche, partage toujours le domaine en deux ensembles de taille égale — Brian/John d'un côté, Aphra/Aoife de l'autre — et il ne reste alors qu'une seule question à poser. En tenant compte à la fois de la probabilité de chaque réponse et de la manière dont elle partitionne l'espace des solutions, la première question demande en moyenne moins de questions par partie.

Les fondamentaux : arbres, entropie et gain d'information

Pour ancrer les définitions, le livre utilise un petit jeu de prédiction de courriels indésirables (spam) contre courriels légitimes (ham). Chaque courriel est décrit par trois descripteurs binaires : MOTS SUSPECTS (le message contient des mots typiques du spam comme casino ou viagra), EXPÉDITEUR INCONNU (l'adresse ne figure pas dans les contacts) et CONTIENT IMAGES.

ID	Mots suspects	Expéd. inconnu	Contient images	Classe
376	oui	non	oui	spam
489	oui	oui	non	spam
541	oui	oui	non	spam
693	non	oui	oui	ham
782	non	non	non	ham
976	non	non	non	ham

L'arbre de décision

Un arbre de décision prédit en enchaînant des tests sur les descripteurs d'une instance de requête. Comme tout arbre, il comporte un nœud racine (root node), des nœuds internes (interior nodes) et des nœuds feuilles (leaf nodes) reliés par des branches. Chaque nœud non-feuille spécifie un test sur un descripteur ; le nombre de niveaux que peut prendre ce descripteur détermine le nombre de branches descendantes. Chaque feuille indique le niveau prédit du descripteur cible.

                    [ Mots suspects ? ]
                     /              
                  oui                non
                   |                  |
                (spam)              (ham)

Pour classer une requête, on teste le descripteur de la racine, on descend la branche correspondante, et on répète jusqu'à atteindre une feuille. Le point essentiel est que plusieurs arbres différents peuvent être cohérents avec le même jeu de données. Sur les données de spam, on peut construire un arbre qui teste d'abord CONTIENT IMAGES puis MOTS SUSPECTS (deux tests), ou un arbre qui teste seulement MOTS SUSPECTS (un seul test). Comment choisir ? On préfère les arbres peu profonds : MOTS SUSPECTS sépare parfaitement le jeu en un groupe pur de spams et un groupe pur de hams, alors qu'il faut un test de plus avec CONTIENT IMAGES. Cette préférence pour les arbres courts est le biais inductif (inductive bias) fondamental de cette famille d'algorithmes — une forme de rasoir d'Occam appliquée aux modèles. Pour la mettre en œuvre, il faut une mesure formelle du pouvoir discriminant d'un descripteur ; c'est le rôle de l'entropie.

Le modèle d'entropie de Shannon

L'entropie mesure l'impureté, l'hétérogénéité d'un ensemble. Intuitivement, c'est l'incertitude associée au tirage aléatoire d'un élément. Un paquet où toutes les cartes sont identiques a une entropie nulle : aucune incertitude. Un ensemble de douze cartes toutes distinctes et équiprobables a une entropie très élevée. Shannon transforme les probabilités des issues en valeurs d'entropie via le logarithme : une grande probabilité doit donner une petite entropie, et inversement. Le logarithme en base 2 d'une probabilité (comprise entre 0 et 1) renvoie de grands nombres négatifs pour les faibles probabilités et de petits nombres négatifs pour les fortes ; en multipliant par −1, on obtient une grandeur positive idéale. La formule de l'entropie est une somme pondérée de ces logarithmes :

H(t) = -Σ ( P(t = i) × log2 P(t = i) )      pour i de 1 à l

où P(t = i) est la probabilité de tirer un élément de type i et l le nombre de types. On utilise toujours la base 2, ce qui exprime l'entropie en bits.

Composition de l'ensemble	Entropie (bits)
1 seul type (tout identique)	0,00
2 types, 25 % / 75 %	0,81
2 types à parts égales (maximum à 2 types)	1,00
3 types déséquilibrés	1,50
3 types équiprobables (maximum à 3 types)	1,58
12 types équiprobables	3,58

Le gain d'information

Quel rapport avec la prédiction ? Si l'on construit une séquence de tests qui découpe les données d'entraînement en ensembles purs vis-à-vis de la cible, alors on étiquette une requête en lui appliquant la même séquence. Le gain d'information mesure la réduction d'entropie obtenue en testant un descripteur. Son calcul se fait en trois temps : (1) calculer l'entropie du jeu complet par rapport à la cible ; (2) pour chaque descripteur, partitionner le jeu selon ses valeurs et faire la somme pondérée des entropies des partitions — c'est l'entropie restante, notée rem ; (3) soustraire l'entropie restante de l'entropie initiale.

H(t, D)     = -Σ ( P(t = l) × log2 P(t = l) )           sur les niveaux l de t

rem(d, D)   =  Σ ( |Dd=l| ÷ |D| ) × H(t, Dd=l)          sur les niveaux l de d

IG(d, D)    =  H(t, D) - rem(d, D)

La pondération par la taille de chaque partition garantit qu'une grande partition pèse davantage qu'une petite. Sur le jeu de spam, l'entropie initiale vaut 1 bit (trois spams, trois hams, parfaitement équilibrés). On calcule alors le gain de chaque descripteur :

Descripteur	Entropie restante (rem)	Gain d'information
Mots suspects	0,0	1,0
Expéditeur inconnu	0,9183	0,0817
Contient images	1,0	0,0

Le verdict colle parfaitement à l'intuition. MOTS SUSPECTS a un gain de 1 bit, égal à l'entropie totale : c'est un descripteur parfaitement discriminant (un cas rare en pratique). EXPÉDITEUR INCONNU n'apporte qu'un peu d'information, et CONTIENT IMAGES n'en apporte aucune. Le gain d'information nous donne donc le moyen de choisir, à chaque étape, le meilleur test à ajouter à la séquence.

L'approche standard : l'algorithme ID3

L'Iterative Dichotomizer 3 (ID3) construit l'arbre le plus court possible cohérent avec les données, de manière récursive, descendante et en profondeur d'abord (depth-first), de la racine vers les feuilles. À chaque nœud, il choisit le descripteur de plus haut gain d'information, partitionne le jeu, retire ce descripteur des tests disponibles sur ce chemin, et se rappelle lui-même sur chaque partition.

Entrée : descripteurs d, instances D
1: si toutes les instances de D ont le même niveau cible C alors
2:    retourner une feuille étiquetée C
3: sinon si d est vide alors
4:    retourner une feuille = niveau cible majoritaire de D
5: sinon si D est vide alors
6:    retourner une feuille = niveau cible majoritaire du nœud parent
7: sinon
8:    d_best  <- argmax IG(d, D)   sur d
9:    créer un nœud étiqueté d_best
10:   partitionner D selon d_best
11:   retirer d_best de d
12:   pour chaque partition Di faire
13:      faire croître une branche vers ID3(d sans d_best, Di)

L'algorithme fait l'une de deux choses à chaque appel : soit il arrête le chemin courant en créant une feuille (lignes 1 à 6), soit il l'étend par un nœud interne (lignes 7 à 13). Les cas de base méritent attention. Premièrement, le jeu considéré à un nœud interne n'est pas le jeu complet, mais le sous-ensemble hérité du parent pour la branche empruntée. Deuxièmement, un descripteur testé une fois sur un chemin ne peut plus l'être sur ce même chemin (mais il peut réapparaître sur une autre branche). De ces contraintes découlent trois conditions d'arrêt : toutes les instances ont le même niveau cible (feuille pure) ; il n'y a plus de descripteur à tester (feuille = niveau majoritaire) ; la partition est vide (feuille = niveau majoritaire du parent).

Exemple chiffré : prédire la végétation

Le livre déroule ID3 sur un problème de modélisation écologique : prédire le type de végétation d'une parcelle (chapparal, riparian ou conifer) à partir de descripteurs extraits de cartes. STREAM indique la présence d'un cours d'eau (binaire), SLOPE la pente (flat, moderate, steep) et ELEVATION l'altitude (low, medium, high, highest).

ID	Stream	Slope	Elevation	Végétation
1	non	steep	high	chapparal
2	oui	moderate	low	riparian
3	oui	steep	medium	riparian
4	non	steep	medium	chapparal
5	non	flat	high	conifer
6	oui	steep	highest	conifer
7	oui	steep	high	chapparal

L'entropie du jeu complet vaut 1,5567 bits (trois chapparal, deux riparian, deux conifer). On calcule ensuite le gain pour chaque descripteur à la racine :

Descripteur	Entropie restante (rem)	Gain d'information
Stream	1,2507	0,3060
Slope	0,9793	0,5774
Elevation	0,6793	0,8774

ELEVATION a le plus haut gain et devient la racine. Le partage en quatre branches crée deux partitions pures (les niveaux low et highest, une instance chacune, converties en feuilles) et deux partitions mixtes — celles des niveaux medium et high — qu'il faut continuer à découper. Sur la partition medium (instances 3, 4), STREAM l'emporte sur SLOPE et produit deux feuilles pures (oui → riparian, non → chapparal). Sur la partition high (instances 1, 5, 7), c'est SLOPE qui est retenu ; l'un des sous-ensembles générés est vide (aucune instance moderate), ce qui produit une feuille étiquetée du niveau majoritaire du parent — chapparal. L'arbre final classe correctement les sept instances : il est cohérent avec les données.

                       [ Elevation ]
        low /     medium |        high       highest
       (riparian)        |        |          (conifer)
                    [ Stream ] [ Slope ]
                    /         /   |    
                  oui     non steep flat moderate
              (riparian)(chapp.)(chapp.)(conifer)(chapp.)

Ce qui est instructif, c'est la feuille issue de la partition vide : l'arbre prédira chapparal pour une parcelle STREAM = oui, SLOPE = moderate, ELEVATION = high, alors qu'aucune instance d'entraînement ne combine moderate et chapparal. Le modèle généralise au-delà des données — et la justesse de cette généralisation dépend entièrement de la pertinence du biais inductif.

Extensions et variations

ID3 tel quel suppose des descripteurs catégoriels et des données propres. Plusieurs raffinements le rendent utilisable en conditions réelles.

Autres mesures de sélection et d'impureté

Le gain d'information souffre d'un biais : il favorise les descripteurs à nombreux niveaux, qui découpent le jeu en de nombreux petits sous-ensembles tendant naturellement à être purs, indépendamment de toute corrélation avec la cible. Le ratio de gain d'information (information gain ratio) corrige ce biais en divisant le gain par l'entropie du descripteur lui-même :

GR(d, D) = IG(d, D) ÷ H(d, D)

où le dénominateur est l'entropie du jeu vis-à-vis des niveaux de d. Sur le jeu de végétation, ce diviseur change le classement : SLOPE obtient le meilleur ratio (IG = 0,5774 ÷ H = 1,1488 = 0,5026) alors qu'ELEVATION avait le meilleur gain brut. Construire l'arbre avec le ratio donnerait donc une structure différente et, sur certaines requêtes hors jeu, des prédictions différentes — illustration nette du fait que deux modèles cohérents avec les mêmes données peuvent généraliser autrement.

Une autre mesure d'impureté est l'indice de Gini (Gini index) :

Gini(t, D) = 1 - Σ ( P(t = l)² )      sur les niveaux l de t

Il s'interprète comme la fréquence à laquelle on classerait mal une instance en pariant au hasard selon la distribution des cibles. Il vaut 0 pour un ensemble pur et tend vers 1 - 1/k pour k niveaux équiprobables ; ses scores restent toujours entre 0 et 1, ce qui facilite parfois les comparaisons. Le gain d'information se calcule à l'identique avec Gini (impureté du jeu moins somme pondérée des impuretés des partitions). Sur le jeu de végétation, Gini donne des nombres différents mais le même classement qu'avec l'entropie, et donc le même arbre.

Descripteurs continus et cibles continues

Pour un descripteur continu, on définit un seuil (threshold) et l'on partitionne selon que les valeurs lui sont supérieures ou inférieures. Le seuil optimal ne se cherche pas parmi une infinité de valeurs : on trie les instances selon le descripteur, on repère les frontières entre instances adjacentes de niveaux cibles différents, et l'on évalue le gain pour chaque frontière candidate (la valeur médiane entre deux instances). Sur le jeu de végétation où ELEVATION est exprimée en pieds, quatre frontières émergent ; le seuil ≥ 4 175 offre le meilleur gain (0,8631 bits), supérieur à celui des autres descripteurs, et devient la racine. Contrairement aux descripteurs catégoriels, un descripteur continu peut être réutilisé plusieurs fois sur un même chemin avec des seuils différents.

Quand la cible est continue, on parle d'arbre de régression (regression tree) : la feuille renvoie la moyenne des valeurs cibles des instances qui l'atteignent. On remplace alors l'entropie par la variance : à chaque nœud, on choisit le descripteur qui minimise la variance pondérée des partitions, ce qui regroupe les instances de cibles proches.

var(t, D) = ( 1 ÷ (n - 1) ) × Σ ( ti - moyenne(t) )²      pour i de 1 à n

d_best = argmin  Σ ( |Dd=l| ÷ |D| ) × var(t, Dd=l)        sur d

Comme il n'existe pas de partition « pure » pour une cible continue, le cas de base d'arrêt change : on introduit un critère d'arrêt anticipé (par exemple, ne plus partitionner si la partition contient moins de 5 % des instances), faute de quoi l'arbre isole chaque instance dans sa propre feuille — du sur-apprentissage caractérisé.

Le sur-apprentissage et l'élagage

Un modèle sur-apprend (overfits) lorsque certaines de ses prédictions reposent sur des motifs fortuits — bruit, variance d'échantillonnage — présents dans les données d'entraînement. Les arbres y sont particulièrement enclins : en partitionnant récursivement, ils tendent à isoler les instances bruitées dans des feuilles dédiées, et le risque croît avec la profondeur, car les prédictions s'appuient sur des sous-ensembles de plus en plus petits. L'élagage (pruning) identifie et supprime les sous-arbres probablement dus au bruit, en les remplaçant par une feuille qui prédit le niveau majoritaire (ou la moyenne) des instances fusionnées. On sacrifie ainsi la cohérence stricte avec l'entraînement au profit de la capacité de généralisation.

Deux familles s'opposent. Le pré-élagage (pre-pruning) introduit des critères d'arrêt anticipé pendant la construction : nombre minimal d'instances dans une partition, gain insuffisant, profondeur maximale, ou tests statistiques comme le χ². Il est efficace mais peut manquer des interactions entre descripteurs qui n'apparaissent qu'au sein de sous-arbres profonds. Le post-élagage (post-pruning) laisse l'arbre croître complètement, puis examine chaque branche et coupe celles qui semblent dues au sur-apprentissage. La méthode la plus recommandée compare le taux d'erreur de l'arbre avec et sans un sous-arbre, mesuré sur un jeu de validation (validation set) tenu à l'écart de l'entraînement.

L'élagage par réduction d'erreur (reduced error pruning) en est la version classique : on parcourt l'arbre de bas en haut, de gauche à droite ; un sous-arbre est élagué si le taux d'erreur sur la validation à sa racine est inférieur ou égal au taux d'erreur combiné de ses feuilles. Sur l'exemple d'orientation post-opératoire de patients (vers les soins intensifs icu ou un service général gen), considérez un sous-arbre dont la racine prédit correctement icu pour trois instances de validation (erreur 0), tandis que ses feuilles se trompent sur deux d'entre elles (erreur 2). Comme l'erreur des feuilles dépasse celle de la racine, le sous-arbre est élagué et remplacé par une feuille.

Les ensembles : bagging, boosting et forêts aléatoires

Plutôt que de viser le meilleur modèle unique, un ensemble de modèles (model ensemble) combine les prédictions de plusieurs modèles, à la manière d'un comité d'experts plus fiable qu'un expert isolé. Deux conditions le définissent : chaque modèle est induit sur une version modifiée du jeu de données, et les prédictions sont agrégées (vote majoritaire pour une cible catégorielle, moyenne ou médiane pour une cible continue). À condition que les modèles soient indépendants, un ensemble peut être très précis même si chaque membre n'est que légèrement meilleur que le hasard — il faut éviter la « pensée de groupe ».

Le boosting ajoute les modèles séquentiellement, chacun étant biaisé pour prêter plus d'attention aux instances que les précédents ont mal classées. On utilise un jeu pondéré : à chaque itération, on induit un modèle, on calcule l'erreur totale ∈ (somme des poids des instances mal classées), on augmente les poids des instances mal classées et diminue ceux des bien classées, puis on calcule un facteur de confiance α qui croît quand ∈ décroît. L'ensemble vote ensuite de façon pondérée par les α.

Le bagging (bootstrap aggregating) entraîne chaque modèle sur un échantillon bootstrap : un tirage aléatoire avec remise, de la même taille que le jeu original. Le tirage avec remise crée des doublons, si bien que chaque échantillon est différent et manque certaines instances. Les arbres de décision s'y prêtent admirablement : très sensibles aux variations du jeu, un petit changement peut modifier le descripteur choisi à la racine et se propager dans tout l'arbre, ce qui garantit la diversité. On étend souvent le bagging par un échantillonnage de sous-espace (subspace sampling), où chaque arbre n'utilise qu'un sous-ensemble aléatoire des descripteurs. La combinaison bagging + échantillonnage de sous-espace + arbres de décision porte un nom célèbre : la forêt aléatoire (random forest).

	Bagging (forêt aléatoire)	Boosting
Construction	Modèles indépendants, en parallèle	Modèles séquentiels, chacun corrige le précédent
Échantillonnage	Bootstrap (avec remise) + sous-espace	Rééchantillonnage pondéré par les erreurs
Agrégation	Vote majoritaire / médiane	Vote / moyenne pondérés par la confiance α
Facilité	Simple à paralléliser	Plus délicat, risque de sur-apprentissage
Quand il brille	Jeux à plus de 4 000 descripteurs	Jeux à moins de 4 000 descripteurs

Forces, limites et variantes

ID3 a engendré des variantes répandues : C4.5 (implémentée en logiciel libre sous le nom J48) gère descripteurs continus, valeurs manquantes et post-élagage ; CART utilise l'indice de Gini et sait traiter les cibles continues. Le principal atout des arbres reste leur interprétabilité : on suit aisément la séquence de tests qui mène à une prédiction, ce qui est décisif en médecine, où l'on attend une explication et pas seulement un verdict. Les arbres gèrent descripteurs catégoriels et continus, et modélisent les interactions entre descripteurs.

Ils ont aussi des faiblesses. Ils deviennent volumineux et difficiles à lire face à des données purement continues — les modèles par l'erreur du chapitre 7 conviennent alors mieux. Ils peinent en grande dimension avec peu d'instances (sur-apprentissage probable), là où les modèles probabilistes du chapitre 6 sont plus robustes. Enfin, ce sont des apprenants gloutons (eager learners) : ils doivent être réentraînés pour suivre un concept qui évolue, contrairement aux modèles par la similarité du chapitre suivant, réentraînables de façon incrémentale.

À retenir

• La grande idée de l'apprentissage par l'information est de poser à chaque étape la question la plus informative, en tenant compte de la probabilité des réponses et de la manière dont elles partitionnent l'espace des solutions.
• L'entropie de Shannon H(t) = -Σ (P(t=i) × log2 P(t=i)) mesure l'impureté d'un ensemble en bits ; elle est nulle pour un ensemble pur et maximale (log2 k) pour k types équiprobables.
• Le gain d'information IG = H(t,D) - rem(d,D) quantifie la réduction d'entropie obtenue en testant un descripteur ; l'algorithme ID3 construit l'arbre récursivement en choisissant à chaque nœud le descripteur de plus haut gain — ce qui produit des arbres peu profonds (biais inductif, rasoir d'Occam).
• Le gain d'information favorise les descripteurs à nombreux niveaux ; le ratio de gain (division par l'entropie du descripteur) et l'indice de Gini 1 - Σ P(t=l)² offrent des alternatives — à comparer empiriquement par jeu de données.
• Les descripteurs continus se gèrent par un seuil optimal trouvé aux frontières de transition de la cible ; les cibles continues mènent aux arbres de régression, qui minimisent la variance pondérée et prédisent la moyenne en feuille.
• Les arbres sur-apprennent en isolant le bruit ; l'élagage (pré-élagage par arrêt anticipé, ou post-élagage par réduction d'erreur sur un jeu de validation) sacrifie la cohérence au profit de la généralisation.
• Les ensembles combinent des modèles indépendants : le bagging (échantillons bootstrap + sous-espace + arbres = forêt aléatoire) et le boosting (modèles séquentiels pondérés par l'erreur) figurent parmi les modèles les plus précis, au prix de l'interprétabilité.