Arbre de décision : Splits Gini

Un arbre de décision partitionne l'espace des caractéristiques par une suite de coupures binaires alignées sur les axes, chacune choisie pour réduire au maximum une mesure d'impureté nodale. L'impureté de Gini en un nœud vaut 1 moins la somme des carrés des probabilités de classe : elle est nulle pour un nœud pur et atteint 0,5 pour un nœud à deux classes parfaitement mélangées. L'algorithme CART évalue chaque seuil possible sur chaque caractéristique et retient celui qui minimise la moyenne pondérée de l'indice de Gini des deux nœuds enfants, les poids étant la fraction des exemples d'entraînement dans chaque enfant. Un arbre de profondeur 1 (une souche de décision) effectue une seule coupure binaire ; les arbres plus profonds subdivisent l'espace en régions rectangulaires de plus en plus fines. À chaque division, le gain d'information est égal à l'impureté du nœud parent moins la moyenne pondérée des impuretés des enfants, mesurant ainsi la réduction d'incertitude obtenue.

Sans contraintes, un arbre croît jusqu'à ce que chaque feuille soit pure, mémorisant parfaitement le jeu d'entraînement mais généralisant très mal : c'est le surapprentissage propre aux arbres de décision. Les remèdes principaux sont l'élagage préventif (limiter la profondeur maximale, exiger un nombre minimum d'exemples pour qu'un nœud soit divisé ou qu'une feuille existe) et l'élagage a posteriori (laisser l'arbre pousser complètement, puis supprimer les feuilles qui n'améliorent pas la perte sur un ensemble de validation, pondérée par un paramètre de complexité alpha, comme dans l'élagage par coût-complexité). Un arbre peu profond, de profondeur 3 à 5, est interprétable et peut être représenté sous forme d'organigramme ; ses décisions sont auditables par un humain, ce qui en fait l'un des rares classifieurs véritablement en boîte blanche. Les arbres de décision servent également d'apprenants de base pour les forêts aléatoires (arbres entièrement développés et agrégés par bagging) et le gradient boosting (arbres peu profonds ajustés séquentiellement sur les résidus), où l'assemblage restaure la propriété de faible biais tout en contrôlant la variance.