Arbres de décision : le jeu des vingt questions

Vous connaissez le jeu des vingt questions ? « Est-ce vivant ? » « Est-ce plus grand qu’un chat ? » Un bon joueur ne pose pas des questions au hasard ; il pose celle qui coupe à peu près en deux les possibilités restantes. Un arbre de décision est un modèle qui joue à ce jeu avec des données – et comme ses questions sont formulées en clair, c’est l’un des rares modèles qu’on peut lire comme un organigramme.

À vous de jouer

• Réglez le curseur de profondeur maximale sur 1. L’arbre n’a droit qu’à une question. Lisez-la dans la liste des divisions : quelle variable l’algorithme a-t-il jugée la plus informative ?
• Montez la profondeur maximale cran par cran. Regardez l’exactitude d’entraînement grimper et comparez-la à l’exactitude de test à chaque profondeur.
• Poussez le curseur de profondeur maximale au maximum. L’exactitude d’entraînement est-elle presque parfaite ? Qu’est devenue l’exactitude de test ?
• Trouvez la profondeur où l’exactitude de test est la meilleure et lisez-y les premières divisions. Pourriez-vous expliquer cet arbre à quelqu’un en deux phrases ?

L’idée en quelques mots

Voyons maintenant ce que vous venez de manipuler, en termes simples.

Un arbre de décision prédit en posant une suite de questions oui/non sur les variables : « Le passager a-t-il moins de tel âge ? », « A-t-il voyagé en première classe ? ». Chaque réponse envoie l’exemple dans une branche, et la question suivante dépend des réponses précédentes. Au bout de chaque chemin se trouve une feuille portant une prédiction – en général l’étiquette la plus fréquente parmi les exemples d’entraînement arrivés là.

Dans cette leçon, nous utilisons des données sur 891 passagers du Titanic, dont 342 ont survécu. Les variables comprennent la classe du billet, le sexe, l’âge, le nombre de proches à bord et le prix payé. L’arbre apprend quelles questions sur ces variables séparent le mieux les survivants des autres.

Pensez à une infirmière d’accueil aux urgences qui fait le tri. Elle ne calcule pas de somme pondérée ; elle suit une courte chaîne de questions – respire-t-il ? saigne-t-il ? est-il conscient ? –, chacune réduisant ce qu’il faut faire. Un arbre, c’est cette chaîne, apprise à partir de données au lieu d’être écrite par des médecins.

Pourquoi ça marche

L’arbre se construit par le haut, une question à la fois. À chaque étape, l’algorithme essaie chaque variable et chaque valeur de coupure possible, et se demande : quelle question sépare ce groupe en deux groupes aussi purs que possible, c’est-à-dire contenant chacun surtout une seule étiquette ? Une mesure d’impureté répandue est l’indice de Gini d’un groupe :

Gini = 1 − Σ pₖ²

où pₖ est la part de l’étiquette k dans le groupe. Un groupe où tout le monde a la même étiquette a un Gini de 0 ; un groupe partagé moitié-moitié entre deux étiquettes a un Gini de 0,5, la pire valeur possible pour deux classes. L’algorithme choisit la question qui fait le plus baisser l’impureté moyenne, puis répète la procédure séparément dans chaque branche. Cette recherche gloutonne, étape par étape, ne garantit pas le meilleur arbre possible, mais elle est rapide et marche bien en pratique.

Livré à lui-même, l’arbre continue de se diviser jusqu’à ce que chaque feuille soit pure – même si une feuille ne contient qu’un seul passager. À ce stade, il a appris par cœur les données d’entraînement, bruit compris : le surapprentissage de la leçon 7 sous un nouveau costume. Le principal réglage est la profondeur maximale, le nombre de questions autorisées le long d’un chemin. Un arbre peu profond est facile à lire mais peut manquer de vraies tendances ; un arbre profond colle presque parfaitement aux données d’entraînement et généralise moins bien. La validation croisée de la leçon 8 est la façon honnête de choisir la profondeur.

Erreur fréquente

Une division n’explique pas une cause. L’arbre interroge la variable qui sépare le mieux les étiquettes dans ces données, et elle peut en représenter une autre : la classe du billet et le prix vont de pair, et tous deux disent quelque chose de l’endroit du navire où dormait un passager. La seconde erreur est de faire confiance à un arbre profond parce que ses règles ont l’air si précises. Une règle comme « âge entre 31,5 et 32,5 et billet au-dessus d’une certaine valeur » décrit généralement un ou deux passagers, pas une tendance. De petits changements dans les données peuvent aussi modifier la première division et donc l’arbre entier, ce qui rend les arbres isolés instables.

Cette instabilité est une faiblesse, mais on peut la transformer en force. Dans la prochaine leçon, nous faisons pousser beaucoup d’arbres différents et nous les laissons voter.

import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier

df = pd.read_csv("data/raw/titanic.csv")
X = pd.DataFrame({"female": (df["sex"] == "female").astype(int)}).join(df[["pclass", "age", "sibsp", "parch", "fare"]])
Xtr, Xte, ytr, yte = train_test_split(X, df["survived"], test_size=0.3, stratify=df["survived"], random_state=1)
Xtr, Xte = Xtr.fillna({"age": Xtr["age"].median()}), Xte.fillna({"age": Xtr["age"].median()})  # médiane d'entraînement pour les deux
print(f"passengers {len(df)}, survived {df['survived'].sum()}")
for d in (1, 3, 20):
    t = DecisionTreeClassifier(max_depth=d, random_state=0).fit(Xtr, ytr)
    print(f"depth {d:2d}: train {t.score(Xtr, ytr):.3f}, test {t.score(Xte, yte):.3f}, leaves {t.get_n_leaves()}")

passengers 891, survived 342
depth  1: train 0.780, test 0.802, leaves 2
depth  3: train 0.833, test 0.802, leaves 8
depth 20: train 0.986, test 0.780, leaves 141