Decision Stump : Guide complet — Principes, Exemples et Implémentation Python

Résumé — Le Decision Stump (ou « arbre de décision à une seule branche ») est le classifieur le plus simple possible : il pose UNE seule question sur UNE seule feature et prend sa décision en conséquence. Considéré individuellement, c’est un « weak learner » (apprenant faible) avec une précision à peine supérieure au hasard. Mais assemblé en milliers dans des algorithmes de boosting comme AdaBoost ou Gradient Boosting, il devient une brique fondamentale du machine learning moderne.

Principe mathématique

Le Decision Stump est un arbre de décision de profondeur 1 : exactement un nœud de décision (split) et deux feuilles.

1. Structure du modèle

Pour chaque feature j du dataset, et pour chaque seuil possible t parmi les valeurs prises par cette feature :

• Si x[j] ≤ t alors prédire la classe majoritaire à gauche
• Sinon prédire la classe majoritaire à droite

Le couple (feature, seuil) optimal est celui qui minimise l’impureté totale des deux nœuds enfants.

2. Mesures d’impureté

Deux critères sont principalement utilisés pour évaluer la qualité d’un split :

Indice de Gini :
$$G = 1 – \sum_{k=1}^{K} p_k^2$$

où p_k est la proportion d’exemples de la classe k dans le nœud. Pour un problème binaire (classes +1 et -1) :
$$G = 1 – p_+^2 – p_-^2 = 2 \cdot p_+ \cdot (1 – p_+)$$

Un nœud pur (une seule classe) a un Gini de 0. Un nœud parfaitement mélangé (50/50) a un Gini de 0.5.

Entropie (Information Gain) :
$$H = -\sum_{k=1}^{K} p_k \cdot \log_2(p_k)$$

Pour un nœud binaire : H = -p₊·log₂(p₊) – p₋·log₂(p₋). L’entropie est maximale (1.0) quand les classes sont parfaitement mélangées et nulle quand le nœud est pur.

3. Critère de split optimal

Pour chaque feature j et chaque seuil candidat t, on calcule l’impureté pondérée des deux nœuds enfants :

$$I(j, t) = \frac{N_G}{N} \cdot \text{Impureté}(G) + \frac{N_D}{N} \cdot \text{Impureté}(D)$$

où N_G et N_D sont le nombre d’exemples à gauche et à droite du seuil, et N = N_G + N_D est le nombre total d’exemples.

Le meilleur split est celui qui minimise cette impureté pondérée :

$$(j^, t^) = \arg\min_{j, t} I(j, t)$$

C’est équivalent à maximiser le gain d’information (réduction d’impureté) :

$$\Delta I = \text{Impureté}_{parent} – I(j^, t^)$$

4. Prédiction après split

Après le split optimal trouvé, chaque feuille prédit la classe majoritaire des exemples qui y tombent :

• Feuille gauche (x[j] ≤ t) : classe y_G = mode({y_i | x_i[j] ≤ t})
• Feuille droite (x[j] > t) : classe y_D = mode({y_i | x_i[j] > t})

Intuition

Le Decision Stump pose UNE seule question et prend sa décision en conséquence.

Imaginez que vous devez deviner si une personne va acheter un produit sur un site web. Vous avez des milliers de features à disposition : âge, localisation, historique d’achat, temps passé sur le site, etc.

Le Decision Stump ne va poser qu’une seule question :

« Est-ce que le temps passé sur le site est supérieur à 30 secondes ? »

• Oui → Prédire : achat probable
• Non → Prédire : pas d’achat

C’est tout. Un seul test, deux branches, deux prédictions.

Cela semble trop simple pour être utile, et c’est vrai : un Decision Stump seul est un classifieur très médiocre, à peine meilleur que le hasard. Sa précision est rarement au-delà de 60-70%, même sur des problèmes simples.

Mais — et c’est là toute la magie du boosting — si vous assemblez des centaines ou milliers de Decision Stumps, chacun posant sa propre question sur sa propre feature, et que vous combinez leurs votes par pondération, vous obtenez un classifieur extrêmement puissant. C’est exactement le principe d’AdaBoost : chaque stump est un expert imparfait, et l’ensemble est un conseil d’experts dont la sagesse collective dépasse largement celle de chacun.

Implémentation Python

Exemple 1 : Decision Stump from scratch

import numpy as np
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

class DecisionStump:
    """Decision Stump - un arbre de décision de profondeur 1."""

    def __init__(self, criterion='gini'):
        self.criterion = criterion
        self.best_feature = None
        self.best_threshold = None
        self.left_class = None
        self.right_class = None

    def _gini(self, y):
        if len(y) == 0:
            return 0.0
        p = np.mean(y == 1)
        return 2 * p * (1 - p)

    def _entropy(self, y):
        if len(y) == 0:
            return 0.0
        p = np.mean(y == 1)
        if p == 0 or p == 1:
            return 0.0
        return -(p * np.log2(p) + (1 - p) * np.log2(1 - p))

    def _impurity(self, y):
        if self.criterion == 'gini':
            return self._gini(y)
        else:
            return self._entropy(y)

    def fit(self, X, y):
        n_samples, n_features = X.shape
        best_impurity = float('inf')

        for feature_idx in range(n_features):
            # Seuil candidats : médianes entre valeurs triées uniques
            thresholds = np.unique(X[:, feature_idx])
            if len(thresholds) > 50:
                thresholds = np.percentile(X[:, feature_idx],
                    np.linspace(0, 100, 50))

            for threshold in thresholds:
                left_mask = X[:, feature_idx] <= threshold
                right_mask = ~left_mask

                if np.sum(left_mask) == 0 or np.sum(right_mask) == 0:
                    continue

                left_impurity = self._impurity(y[left_mask])
                right_impurity = self._impurity(y[right_mask])

                n_left = np.sum(left_mask)
                n_right = np.sum(right_mask)
                weighted_impurity = (n_left * left_impurity +
                                    n_right * right_impurity) / n_samples

                if weighted_impurity < best_impurity:
                    best_impurity = weighted_impurity
                    self.best_feature = feature_idx
                    self.best_threshold = threshold
                    self.left_class = 1 if np.mean(y[left_mask]) > 0.5 else 0
                    self.right_class = 1 if np.mean(y[right_mask]) > 0.5 else 0

        return self

    def predict(self, X):
        predictions = np.where(
            X[:, self.best_feature] <= self.best_threshold,
            self.left_class, self.right_class
        )
        return predictions

# Données
X, y = make_classification(n_samples=500, n_features=10, n_informative=3,
    n_redundant=2, random_state=42)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3,
    random_state=42)

# Entraînement
stump_gini = DecisionStump(criterion='gini')
stump_gini.fit(X_train, y_train)
pred_gini = stump_gini.predict(X_test)

stump_ent = DecisionStump(criterion='entropy')
stump_ent.fit(X_train, y_train)
pred_ent = stump_ent.predict(X_test)

print(f"Stump (Gini)    : {accuracy_score(y_test, pred_gini):.3f}")
print(f"Stump (Entropy) : {accuracy_score(y_test, pred_ent):.3f}")
print(f"Feature utilisée : {stump_gini.best_feature}")
print(f"Seuil optimal    : {stump_gini.best_threshold:.4f}")

Exemple 2 : Comparaison avec DecisionTreeClassifier(max_depth=1)

from sklearn.tree import DecisionTreeClassifier

# sklearn Decision Stump (arbre de profondeur 1)
sklearn_stump = DecisionTreeClassifier(max_depth=1, random_state=42)
sklearn_stump.fit(X_train, y_train)
sklearn_pred = sklearn_stump.predict(X_test)

print(f"\nComparaison :")
print(f"Stump from scratch (Gini)  : {accuracy_score(y_test, pred_gini):.3f}")
print(f"sklearn DecisionTree(d=1)  : {accuracy_score(y_test, sklearn_pred):.3f}")

# Visualisation de la frontière
import matplotlib.pyplot as plt

# Utiliser 2 features pour la visualisation
X2 = X[:, :2]
X2_train, X2_test, y2_train, y2_test = train_test_split(X2, y, test_size=0.3,
    random_state=42)

stump2 = DecisionStump()
stump2.fit(X2_train, y2_train)

fig, ax = plt.subplots(figsize=(8, 6))
xx, yy = np.meshgrid(np.linspace(X2[:, 0].min()-1, X2[:, 0].max()+1, 200),
                     np.linspace(X2[:, 1].min()-1, X2[:, 1].max()+1, 200))
Z = stump2.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
ax.contourf(xx, yy, Z, alpha=0.3, cmap='RdBu')
ax.scatter(X2_train[:, 0], X2_train[:, 1], c=y2_train, cmap='RdBu',
    edgecolors='black', s=30)

# Tracer la frontière
f = stump2.best_feature
t = stump2.best_threshold
if f == 0:
    ax.axvline(x=t, color='black', linestyle='--', linewidth=2)
else:
    ax.axhline(y=t, color='black', linestyle='--', linewidth=2)

ax.set_title(f'Decision Stump — Feature {f}, Seuil = {t:.3f}')
plt.tight_layout()
plt.savefig('decision_stump_boundary.png', dpi=150)

Exemple 3 : Decision Stump comme base d’AdaBoost

from sklearn.ensemble import AdaBoostClassifier

# AdaBoost avec Decision Stumps (max_depth=1 par défaut)
ada = AdaBoostClassifier(
    estimator=DecisionTreeClassifier(max_depth=1),
    n_estimators=200,
    learning_rate=1.0,
    random_state=42
)
ada.fit(X_train, y_train)
ada_pred = ada.predict(X_test)

print(f"\nAdaBoost (200 stumps) : {accuracy_score(y_test, ada_pred):.3f}")
print(f"Un seul stump seul      : {accuracy_score(y_test, pred_gini):.3f}")
print(f"Gain de performance     : {accuracy_score(y_test, ada_pred) - accuracy_score(y_test, pred_gini):.3f}")

# Visualisation de la courbe de score cumulé
scores = []
for n in range(1, 201, 10):
    ada_n = AdaBoostClassifier(
        estimator=DecisionTreeClassifier(max_depth=1),
        n_estimators=n, learning_rate=1.0, random_state=42
    )
    ada_n.fit(X_train, y_train)
    scores.append(accuracy_score(y_test, ada_n.predict(X_test)))

plt.figure(figsize=(8, 5))
plt.plot(range(1, 201, 10), scores, 'b-o', linewidth=2, markersize=4)
plt.axhline(y=accuracy_score(y_test, pred_gini), color='red', linestyle='--',
    label='Single stump')
plt.title('AdaBoost — Accumulation de Decision Stumps')
plt.xlabel('Nombre de stumps')
plt.ylabel('Accuracy')
plt.legend()
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('adaboost_stumps.png', dpi=150)

Exemple 4 : Analyse des poids AdaBoost

# Quels stumps sont les plus importants dans AdaBoost ?
ada_full = AdaBoostClassifier(
    estimator=DecisionTreeClassifier(max_depth=1),
    n_estimators=50, learning_rate=1.0, random_state=42
)
ada_full.fit(X_train, y_train)

print("\nPoids des premiers stumps dans AdaBoost :")
for i, (tree, w) in enumerate(zip(ada_full.estimators_, ada_full.estimator_weights_)):
    feat = tree.tree_.feature[0]
    thresh = tree.tree_.threshold[0]
    print(f"  Stump {i+1} : feature {feat}, seuil {thresh:.3f}, poids {w:.4f}")

Hyperparamètres

Avantages du Decision Stump

1. Extrême simplicité : Un seul test, deux branches. C’est le modèle le plus simple possible en classification supervisée, ce qui le rend parfaitement interprétable.
2. Rapidité d’entraînement : Trouver le meilleur split est O(n_features × n_unique_values × n_samples), très rapide comparé à un arbre complet.
3. Brique fondamentale du boosting : AdaBoost, Gradient Boosting et XGBoost utilisent tous des Decision Stumps comme weak learners de base. Comprendre le stump, c’est comprendre la brique élémentaire de ces algorithmes puissants.
4. Interprétabilité totale : La règle de décision est une seule condition lisible par un humain. C’est un atout majeur dans les domaines réglementés (finance, santé) où chaque décision doit être explicable.
5. Peu sensible au surapprentissage individuel : Un Decision Stump seul a un biais élevé mais une variance très faible — il ne surajuste jamais. C’est cette propriété qui le rend si utile en ensemble.

Limites du Decision Stump

1. Performance individuelle très limitée : Un Decision Stump seul atteint rarement plus de 60-70% de précision. C’est insuffisant pour la plupart des applications réelles sans boosting.
2. Frontière de décision très simple : La frontière est toujours une ligne droite parallèle à un axe. Impossible de capturer des relations non linéaires ou des interactions entre features.
3. Instabilité du split optimal : Un léger changement dans les données d’entraînement peut sélectionner une feature ou un seuil complètement différent. Le stump individuel est instable.
4. Incapacité à modéliser les interactions : Comme il ne teste qu’une seule feature, un Decision Stump est aveugle aux combinaisons de features (ex: « âge < 30 ET revenu > 50 000 »).
5. Dépendance au critère d’impureté : Le choix entre Gini et Entropie peut produire des splits différents, bien que les résultats finaux soient généralement similaires en pratique.

4 cas d’usage concrets

1. Détection de spam (faible coût de fausse alarme)

Un Decision Stump peut détecter du spam avec une seule règle très simple : « Est-ce que le mot ‘gratuit’ apparaît plus de 3 fois dans l’email ? ». Bien qu’imparfait, ce filtrage rapide élimine une fraction significative du spam évident avant de passer à un classifieur plus sophistiqué pour le reste.

2. Prédiction du risque médical (modèle interprétable)

Dans un contexte clinique où l’interprétabilité est cruciale, un Decision Stump peut offrir une règle de triage simple : « Est-ce que la glycémie à jeun est supérieure à 126 mg/dL ? ». Cette règle unique, bien que non exhaustive, peut servir de premier filtre d’alerte avant des analyses complémentaires.

3. Brique de base d’AdaBoost en production

C’est l’usage principal du Decision Stump en pratique. Les systèmes de scoring de crédit, de prédiction de churn, ou de recommandation utilisent souvent des ensembles de stumps via Gradient Boosting (XGBoost, LightGBM). Chaque stump est simple, mais leurs milliers combinés produisent des modèles compétitifs avec les réseaux de neurones sur des données tabulaires.

4. Feature selection rapide

En entraînant un Decision Stump sur chaque feature individuellement et en comparant leurs performances, on obtient un classement rapide des features par pouvoir discriminant individuel. C’est une méthode de sélection de features très simple mais efficace pour identifier les variables les plus informatives avant d’entraîner des modèles plus complexes.

Conclusion

Le Decision Stump est le classifieur le plus humble du machine learning : une seule question, deux branches, deux réponses. Individuellement, il est si faible qu’on l’appelle « weak learner ». C’est précisément cette faiblesse qui fait sa force en boosting, où des milliers de stumps assemblés donnent naissance à des modèles parmi les plus performants pour les données tabulaires.

Comprendre le Decision Stump, c’est comprendre la brique élémentaire d’AdaBoost, de Gradient Boosting, de XGBoost et de LightGBM — des algorithmes qui dominent les compétitions Kaggle et les déploiements industriels sur des données structurées.

Voir aussi

• Maîtriser les Produits Concatenés Pandigitaux avec Python : Guide Complet pour Développeurs en 2024
• Créer des Sous-ensembles à Somme Unique en Python : Guide Complet et Astuces Avancées