Arbre de Décision (Classification) : Guide complet — Principes, Exemples et Implémentation Python

Résumé

L’arbre de décision est l’un des algorithmes de classification les plus populaires et les plus intuitifs du machine learning supervisé. Contrairement à des modèles tels que les réseaux de neurones ou les machines à vecteurs de support, l’arbre de décision offre une transparence totale : chaque prédiction peut être tracée et expliquée le long d’un chemin de règles « si-alors ». Cet article explore en profondeur les principes mathématiques, le fonctionnement de l’algorithme CART, les critères de division (Gini et entropie de Shannon), la gestion du surapprentissage par élagage, et propose une implémentation Python complète avec scikit-learn, y compris la visualisation de l’arbre et la comparaison des critères de split.

Principe mathématique de l’arbre de décision classification

L’algorithme CART (Classification And Regression Trees)

L’algorithme CART, introduit par Breiman, Friedman, Olshen et Stone en 1984, construit l’arbre de manière récursive et gloutonne. À chaque étape, il examine toutes les caractéristiques et tous les seuils possibles, puis sélectionne le couple (feature, seuil) qui maximise la pureté des sous-ensembles résultants.

Le processus se déroule ainsi :

1. Partir de la racine contenant l’ensemble des données d’entraînement.
2. Pour chaque caractéristique j et chaque seuil t possible :
   – Diviser les données en deux sous-ensembles : gauche (Xⱼ ≤ t) et droit (Xⱼ > t).
   – Calculer l’impureté pondérée des deux sous-ensembles.
3. Choisir la division qui minimise l’impureté pondérée.
4. Répéter récursivement sur chaque sous-ensemble jusqu’à ce qu’un critère d’arrêt soit atteint.

Critère de Gini

L’indice de Gini mesure l’impureté d’un nœud m. Pour un nœud contenant des échantillons de K classes :

Gini(m) = 1 – Σᵢ₌₁ᴷ pᵢ²

où pᵢ représente la proportion d’échantillons de la classe i dans le nœud.

Exemple concret : un nœud contient 80 échantillons de classe A et 20 de classe B. Alors p_A = 0,8 et p_B = 0,2, et :

Gini = 1 – (0,8² + 0,2²) = 1 – (0,64 + 0,04) = 1 – 0,68 = 0,32

Un nœud parfaitement pur (tous les échantillons appartiennent à la même classe) a un indice de Gini de 0. Un nœud maximalement impur (répartition uniforme entre deux classes) a un indice de Gini de 0,5 (cas binaire). Pour K classes, le maximum est 1 – 1/K.

Entropie de Shannon

L’entropie, inspirée de la théorie de l’information de Claude Shannon (1948), est une autre mesure d’impureté :

H(m) = -Σᵢ₌₁ᴷ pᵢ · log₂(pᵢ)

Par convention, on pose 0 · log₂(0) = 0.

Reprenons l’exemple précédent (80 % A, 20 % B) :

H = -(0,8 · log₂(0,8) + 0,2 · log₂(0,2)) ≈ -(0,8 · (-0,322) + 0,2 · (-2,322)) ≈ 0,258 + 0,464 = 0,722

Un nœud pur a une entropie de 0. Un nœud équilibré à deux classes a une entropie maximale de 1,0 (log₂(2) = 1).

Gain d’information (Information Gain)

Le gain d’information quantifie la réduction d’impureté apportée par une division :

IG(parent, enfants) = Impureté(parent) – Σᵢ (nᵢ / n_parent) · Impureté(enfantᵢ)

où nᵢ est le nombre d’échantillons dans le sous-ensemble enfant i.

L’algorithme CART cherche systématiquement la division qui maximise ce gain d’information (ou, de manière équivalente, qui minimise l’impureté pondérée des enfants).

Pourquoi ces deux critères donnent des résultats similaires

En pratique, Gini et entropie conduisent très souvent à des arbres quasi identiques. Le critère de Gini est légèrement plus rapide à calculer (pas de logarithme), tandis que l’entropie tend à produire des arbres un peu plus équilibrés. La différence est généralement marginale sur des jeux de données réels.

Intuition : l’arbre de décision comme un jeu de vingt questions

Imaginez que vous jouez au jeu des vingt questions. Votre interlocuteur pense à un animal, et vous devez le deviner en posant des questions fermées (réponse oui/non). Votre stratégie naturelle sera de poser des questions qui réduisent le plus possible l’incertitude à chaque étape.

« Est-ce un mammifère ? » est une excellente première question : elle élimine d’un coup oiseaux, reptiles, poissons et insectes. « Est-ce un animal dont le nom commence par la lettre Z ? » est une bien moins bonne question : dans le pire des cas, elle n’élimine presque rien.

L’arbre de décision classification fonctionne exactement de cette manière. Chaque nœud interne pose une question du type « la caractéristique Xⱼ est-elle inférieure ou égale au seuil t ? ». La question choisie est celle qui sépare les données en deux groupes les plus purs possibles. On répète le processus jusqu’à ce que chaque feuille contienne des échantillons quasi homogènes.

Cette analogie explique pourquoi les arbres de décision sont si populaires : ce sont littéralement des organigrammes de décision que n’importe quel être humain peut lire et comprendre, sans formation en mathématiques avancées.

Implémentation Python complète avec scikit-learn

Exemple de base avec le dataset Wine

from sklearn.datasets import load_wine
from sklearn.tree import DecisionTreeClassifier, plot_tree
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score, classification_report
import matplotlib.pyplot as plt

# Chargement du dataset Wine
wine = load_wine()
X, y = wine.data, wine.target

# Séparation entraînement / test
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.25, random_state=42, stratify=y
)

# Création et entraînement du classifieur
clf = DecisionTreeClassifier(
    criterion='gini',
    max_depth=4,
    random_state=42
)
clf.fit(X_train, y_train)

# Prédictions et évaluation
y_pred = clf.predict(X_test)
print(f"Précision : {accuracy_score(y_test, y_pred):.4f}")
print(f"\nRapport de classification :\n{classification_report(y_test, y_pred, target_names=wine.target_names)}")

# Visualisation de l'arbre
plt.figure(figsize=(20, 10))
plot_tree(
    clf,
    feature_names=wine.feature_names,
    class_names=wine.target_names,
    filled=True,
    rounded=True,
    fontsize=10
)
plt.title("Arbre de décision — Dataset Wine (max_depth=4, Gini)")
plt.tight_layout()
plt.show()

Visualisation de la frontière de décision

import numpy as np
from sklearn.datasets import make_classification

# Génération de données synthétiques en 2D pour visualisation
X_2d, y_2d = make_classification(
    n_samples=500,
    n_features=2,
    n_informative=2,
    n_redundant=0,
    n_clusters_per_class=1,
    random_state=42
)

# Entraînement
clf_2d = DecisionTreeClassifier(max_depth=5, random_state=42)
clf_2d.fit(X_2d, y_2d)

# Grille pour visualiser la frontière
xx, yy = np.meshgrid(
    np.linspace(X_2d[:, 0].min() - 0.5, X_2d[:, 0].max() + 0.5, 500),
    np.linspace(X_2d[:, 1].min() - 0.5, X_2d[:, 1].max() + 0.5, 500)
)
Z = clf_2d.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)

plt.figure(figsize=(10, 7))
plt.contourf(xx, yy, Z, alpha=0.3, cmap='RdYlBu')
plt.scatter(X_2d[:, 0], X_2d[:, 1], c=y_2d, edgecolors='black', cmap='RdYlBu', s=50)
plt.xlabel("Caractéristique 1")
plt.ylabel("Caractéristique 2")
plt.title("Frontière de décision — Arbre de classification (max_depth=5)")
plt.colorbar(label="Classe prédite")
plt.show()

Comparaison Gini vs Entropie

from sklearn.model_selection import cross_val_score

# Comparaison systématique sur le dataset Wine
resultats = {}
for crit in ['gini', 'entropy']:
    modele = DecisionTreeClassifier(criterion=crit, random_state=42)
    scores = cross_val_score(modele, X, y, cv=5, scoring='accuracy')
    resultats[crit] = scores
    print(f"{crit.capitalize()} : moy={scores.mean():.4f} (±{scores.std():.4f})")

# Comparaison des profondeurs d'arbres
for crit in ['gini', 'entropy']:
    modele = DecisionTreeClassifier(criterion=crit, random_state=42)
    modele.fit(X_train, y_train)
    print(f"{crit.capitalize()} : profondeur de l'arbre = {modele.get_depth()}, "
          f"nombre de feuilles = {modele.get_n_leaves()}")

Ce code révèle un fait intéressant : sur le dataset Wine, les deux critères produisent des performances quasi identiques. Le critère de Gini est marginalement plus rapide en temps d’entraînement, mais la différence est imperceptible sur des jeux de données de taille modeste.

Guide des hyperparamètres

La puissance de l’arbre de décision dépend largement du bon réglage de ses hyperparamètres. Voici les plus importants :

criterion

• Valeurs : 'gini' (par défaut) ou 'entropy'
• Rôle : Détermine la fonction d’impureté utilisée pour évaluer la qualité d’une division.
• Conseil : Commencez par 'gini'. Si les résultats sont insatisfaisants, testez 'entropy'. La différence est généralement minime.

max_depth

• Valeurs : entier (par défaut : None, aucune limite)
• Rôle : Limite la profondeur maximale de l’arbre.
• Conseil : C’est l’hyperparamètre le plus important pour contrôler le surapprentissage. Commencez avec des valeurs entre 3 et 7, puis ajustez par validation croisée. Un arbre sans limite de profondeur apprend souvent par cœur l’entraînement.

min_samples_split

• Valeurs : entier ≥ 2 (par défaut : 2) ou flottant entre 0 et 1
• Rôle : Nombre minimum d’échantillons requis pour diviser un nœud interne.
• Conseil : Augmenter cette valeur (par exemple à 10 ou 20) force l’arbre à être moins profond et à se généraliser davantage.

min_samples_leaf

• Valeurs : entier ≥ 1 (par défaut : 1) ou flottant entre 0 et 1
• Rôle : Nombre minimum d’échantillons requis dans une feuille.
• Conseil : Très utile pour lisser les prédictions dans les régions à faible densité. Des valeurs de 5 à 10 fonctionnent bien en pratique.

max_features

• Valeurs : entier, flottant, 'sqrt', 'log2', ou None (par défaut : None)
• Rôle : Nombre maximum de caractéristiques examinées pour chaque split.
• Conseil : None examine toutes les caractéristiques (comportement par défaut). 'sqrt' ou 'log2' sont pertinents lorsque le nombre de caractéristiques est élevé — c’est d’ailleurs la stratégie utilisée par les forêts aléatoires.

ccp_alpha (élagage par coût-complexité)

• Valeurs : flottant ≥ 0 (par défaut : 0.0)
• Rôle : Paramètre d’élagage minimal (Minimal Cost-Complexity Pruning). Plus la valeur est grande, plus l’arbre est élagué.
• Conseil : C’est la méthode d’élagage la plus rigoureuse. On peut utiliser clf.cost_complexity_pruning_path(X_train, y_train) pour obtenir la série des alpha candidats, puis sélectionner le meilleur par validation croisée.

# Exemple d'élagage par coût-complexité
path = clf.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas = path.ccp_alphas[:-1]  # On exclut la dernière valeur

modeles = []
for alpha in ccp_alphas[:20]:  # On teste les 20 premières valeurs
    arbre = DecisionTreeClassifier(ccp_alpha=alpha, random_state=42)
    arbre.fit(X_train, y_train)
    modeles.append((alpha, arbre))

# Visualisation du compromis précision / complexité
train_scores = [m.score(X_train, y_train) for _, m in modeles]
test_scores = [m.score(X_test, y_test) for _, m in modeles]

plt.figure(figsize=(10, 5))
plt.plot(ccp_alphas[:20], train_scores[:20], label='Entraînement', marker='o')
plt.plot(ccp_alphas[:20], test_scores[:20], label='Test', marker='s')
plt.xlabel('ccp_alpha')
plt.ylabel('Précision')
plt.title('Élagage par coût-complexité : compromis biais-variance')
plt.legend()
plt.xscale('log')
plt.grid(True, alpha=0.3)
plt.show()

Avantages et limites de l’arbre de décision classification

Avantages

• Interprétabilité totale : L’arbre peut être visualisé et compris par des non-experts. Chaque prédiction est justifiable par un chemin de règles.
• Pas de normalisation nécessaire : Contrairement aux SVM ou aux k-plus proches voisins, les arbres de décision sont invariants aux transformations monotones des caractéristiques.
• Gestion naturelle des variables catégorielles et numériques.
• Sélection implicite de caractéristiques : L’arbre n’utilise que les caractéristiques pertinentes, ignorant automatiquement le bruit.
• Robustesse aux valeurs aberrantes : Les valeurs extrêmes n’affectent pas significativement la structure de l’arbre.
• Non-paramétrique : Aucune hypothèse sur la distribution sous-jacente des données.

Limites

• Surapprentissage (overfitting) : C’est le principal défaut. Un arbre profond sans régularisation mémorise l’entraînement et généralise mal. L’élagage est indispensable.
• Instabilité : Une légère variation dans les données d’entraînement peut produire un arbre radicalement différent. C’est précisément cette instabilité que les forêts aléatoires exploitent.
• Frontières orthogonales : L’arbre partitionne l’espace selon des hyperplans perpendiculaires aux axes. Pour capturer des relations diagonales, il a besoin d’une profondeur importante.
• Biais pour les caractéristiques à nombreuses modalités : Le critère d’information (entropie) favorise les caractéristiques avec un grand nombre de valeurs uniques.
• Difficulté avec l’extrapolation : Les feuilles prédisent toujours la moyenne des classes observées à l’entraînement ; l’arbre ne peut ni extrapoler ni interpoler au-delà de ces valeurs.

4 cas d’usage concrets

1. Diagnostic médical

L’arbre de décision est utilisé pour construire des arbres diagnostiques en médecine. Par exemple, classifier une tumeur comme bénigne ou maligne à partir de caractéristiques cytologiques (rayon moyen, texture, périmètre, surface, lissage, etc.). L’avantage majeur est la transparence : un médecin peut suivre le chemin de décision et comprendre exactement pourquoi le modèle a formulé tel diagnostic. C’est crucial dans un domaine où l’interprétabilité est aussi importante que la précision.

2. Détection de fraude bancaire

Dans le secteur financier, les arbres de décision servent à classer les transactions comme légitimes ou frauduleuses. Les caractéristiques incluent le montant, l’heure, le lieu géographique, le type de commerçant, et l’historique du compte. Bien que les forêts aléatoires et le gradient boosting surpassent généralement un arbre unique en précision, un arbre élagué reste extrêmement utile pour établir des règles de détection explicites et auditées par les régulateurs.

3. Segmentation client en marketing

Un arbre de décision peut identifier les profils de clients les plus susceptibles de répondre positivement à une campagne marketing. En segmentant la clientèle selon des critères démographiques (âge, revenu, localisation) et comportementaux (fréquence d’achat, panier moyen), l’arbre produit des segments clairement définis et exploitables par les équipes commerciales. Cette approche est particulièrement appréciée pour sa capacité à communiquer des insights actionnables.

4. Prédiction d’attrition (churn)

Dans les industries de services (télécommunications, SaaS, streaming), prédire quels clients risquent de se désabonner est un enjeu stratégique. L’arbre de décision classification identifie les facteurs les plus discriminants : durée de contrat, nombre d’appels au service client, utilisation récente du service, etc. La sortie est directement exploitable : « Les clients avec un contrat de moins de 6 mois ET plus de 3 appels au SAV présentent un risque d’attrition de 78 %. »

Conclusion

L’arbre de décision classification reste un outil fondamental du machine learning supervisé. Sa force réside dans son équilibre unique entre simplicité conceptuelle et puissance prédictive. Bien qu’un arbre unique soit rarement le modèle le plus performant sur des tâches complexes, il constitue la brique fondamentale des ensembles d’arbres (forêts aléatoires, gradient boosting) qui dominent les compétitions de data science.

Maîtriser l’arbre de décision — ses critères de division, ses hyperparamètres, ses mécanismes d’élagage — est une condition préalable indispensable pour comprendre et utiliser efficacement ces méthodes ensemblistes plus avancées.

Voir aussi

• Deux modules pour bien sécuriser votre navigateur web
• Tester la Primalité de $2n^2 – 1$ en Python : Guide Complet et Optimisé