Site mis à jour le : 21 avril 2026

Les Arbres de Décision

Introduction

Quand on regarde un arbre dans la nature, nous avons les racines, le tronc, les branches et les feuilles. Pour nos arbres de décisions, c'est la même chose :

• La racine : le problème auquel nous devons faire face,
• Les branches porteuses représentent nos principaux choix,
• Les sous-branches sont des extensions de branches.

Comment penser l'arbre de décision ?

Pour créer la racine, il faut se demander quelle décision nous devons prendre. Une fois que nous avons formulé notre décision, nous devons la transformer en question.

Par exemple, si ma décision se porte autour de ce que je dois manger ce soir pour être en forme pour ma course de demain, je peux tout simplement la transformer en "Que dois-je manger ce soir pour être en forme pour ma course de demain ?" Cet exemple est simple et limpide. Nous n'avons pas de problèmes à traduire en question notre problématique, mais pour des problèmes plus techniques, la reformulation est parfois difficile.

Suite à la transformation de notre problème en problématique, nous devons définir les branches et sous-branches. On peut le savoir plus au moins en fonction des paramètres que nous avons. Si nous reprenons le cas de notre course de demain, nous pouvons avoir la masse de protéine que nous souhaitons ingérer, et si nous voulons des légumes ou non.

Toujours dans le même objectif, nous devons choisir des critères discriminants. Dans le cadre hypothétique du choix de ce que nous devons manger, des critères discriminants pourraient être :

• + ou - de 2500 KCAL
• Riche ou faible en lipides
• Jour de la semaine ou week-end
• Etc.

En clair, ce sont des choix binaires qui doivent séparer l'ensemble de nos choix. L'efficacité et le choix des discriminants les plus pertinents sera géré par l'algorithme.

Petit tour d'histoire & Algorithmes

Un peu d'histoire s'impose... La base des arbres de décision se résument dans l'algorithme ID3. C'est lui l'ancien.

Une chose importante à avoir en tête : L'algorithme est là pour construire l'arbre. Il sert uniquement à ça.

C4.5 est le successeur de l'algorithme ID3. Des améliorations majeures ont été apporté et une fois qu'on connait celui-là, on peut dire que nous avons terminé les arbres de décision (ou presque).

Dans les sections suivantes, j'ai détaillé le code afin de mieux voir les différences entre les 2 algorithmes.

L'Algorithme ID3

L'algorithme ID3 se base sur le concept du gain d'information (Entropie) pour segmenter les données.

Concrètement, l'entropie mesure le degré d'incertitude d'un ensemble. C'est Claude Shannon, mathématicien américain, qui a inventé ce concept.

Plus l'entropie est élevée, plus l'ensemble est désordonné. L'algorithme cherche à minimiser l'entropie en choisissant les attributs qui séparent le mieux les données.

Voici la formule mathématique de l'entropie :

H(S) = - Σ (p_i * log2(p_i))

Où :

Prenons un exemple concret : Si nous reprenons la question "Que dois-je manger ce soir pour être en forme pour ma course de demain ?", nous devons prendre le critère le plus discriminant.

import pandas as pd
import math
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier, plot_tree
from sklearn.preprocessing import LabelEncoder

# Entropie (Mesure le degré de mixité d'une colonne)
def entropie(column):
    h = 0
    val = column.value_counts(normalize=True)
    for p in val:
        if p > 0:
            h -= p * math.log2(p)
    return h

# Gain d'information
def gain_information(df, attribut, cible):
    entropieInitiale = entropie(df[cible])
    val = df[attribut].unique()
    entropie_apres = 0

    for v in val:
        sous_df = df[df[attribut] == v]
        poids = len(sous_df) / len(df)
        entropie_apres += poids * entropie(sous_df[cible])

    return entropieInitiale - entropie_apres

# Algorithme ID3
def ID3(df, attributs, cible):
    # Si tous les exemples ont la même classe, retourne cette classe
    if len(df[cible].unique()) == 1:
        return df[cible].iloc[0]
    
    # Si plus d'attributs, retourne la classe majoritaire
    if len(attributs) == 0:
        return df[cible].mode()[0]
    
    # Cherche l'attribut qui maximise le gain d'information
    gains = {a: gain_information(df, a, cible) for a in attributs}
    meilleur = max(gains, key=gains.get)
    arbre = {meilleur: {}}

    for v in df[meilleur].unique():
        sous_df = df[df[meilleur] == v]
        if sous_df.empty:
            arbre[meilleur][v] = df[cible].mode()[0]
        else:
            reste_attributs = [a for a in attributs if a != meilleur]
            arbre[meilleur][v] = ID3(sous_df, reste_attributs, cible)
    return arbre

data = [
    {"plat": "Saumon et pâtes", "lourd_leger": "Oui", "week_end": "Non", "sportDemain": "Oui"},
    {"plat": "Salade",          "lourd_leger": "Non", "week_end": "Non", "sportDemain": "Oui"},
    {"plat": "Soupe",           "lourd_leger": "Non", "week_end": "Non", "sportDemain": "Non"},
    {"plat": "Pizza",           "lourd_leger": "Oui", "week_end": "Oui", "sportDemain": "Non"},
    {"plat": "Paella",          "lourd_leger": "Oui", "week_end": "Non", "sportDemain": "Non"},
]

df = pd.DataFrame(data)
attributs = ["lourd_leger", "week_end", "sportDemain"]

label_encoders = {}
for column in df.columns:
    le = LabelEncoder()
    df[column] = le.fit_transform(df[column])
    label_encoders[column] = le

X = df[attributs]
y = df["plat"]

clf = DecisionTreeClassifier(criterion='entropy')
clf.fit(X, y)

plt.figure(figsize=(15, 10))
plot_tree(clf, feature_names=attributs, class_names=label_encoders["plat"].classes_, filled=True)
plt.show()

L'Algorithme C4.5

Cet algorithme est la version améliorée d'ID3. Il gère la discrétisation et l'élagage (pruning) de l'arbre pour minimiser le sur-apprentissage.

import pandas as pd
import math
from sklearn.tree import DecisionTreeClassifier

# Algorithme C4.5
def C45(df, attributs, cible):
    if len(df[cible].unique()) == 1:
        return df[cible].iloc[0]
    
    if len(attributs) == 0:
        return df[cible].mode()[0]
    
    gains = {a: gain_information(df, a, cible) for a in attributs}
    meilleur = max(gains, key=gains.get)
    arbre = {meilleur: {}}

    for v in df[meilleur].unique():
        sous_df = df[df[meilleur] == v]
        if sous_df.empty:
            arbre[meilleur][v] = df[cible].mode()[0]
        else:
            reste_attributs = [a for a in attributs if a != meilleur]
            arbre[meilleur][v] = C45(sous_df, reste_attributs, cible)
    return arbre

# Discrétisation
def discretisation(df, attribut, cible):
    seuils = sorted(df[attribut].unique())
    meilleur_seuil = None
    meilleur_gain = -1
    for s in seuils:
        df['temp'] = (df[attribut] <= s).astype(str)
        gain = gain_information(df, 'temp', cible)
        if gain > meilleur_gain:
            meilleur_gain = gain
            meilleur_seuil = s
    df.drop('temp', axis=1, inplace=True)
    df[f'{attribut}_discretise'] = (df[attribut] <= meilleur_seuil).astype(int)
    return df

# Erreur pessimiste et Élagage
def erreur_pessimiste(E, N, z=0.61):
    numerateur = E + 0.5 * z**2 + z * math.sqrt(E*(N-E)/N + z**2/4)
    denominateur = N + z**2
    return numerateur / denominateur

def elaguer(arbre, df, cible):
    if isinstance(arbre, dict):
        attribut = next(iter(arbre))
        sous_arbres = arbre[attribut]
        for valeur, sous_arbre in sous_arbres.items():
            sous_df = df[df[attribut] == valeur]
            sous_arbres[valeur] = elaguer(sous_arbre, sous_df, cible)

        E = len(df) - len(df[df[cible] == df[cible].mode()[0]])
        N = len(df)
        erreur_arbre = erreur_pessimiste(E, N)

        classe_majoritaire = df[cible].mode()[0]
        E_feuille = len(df[df[cible] != classe_majoritaire])
        erreur_feuille = erreur_pessimiste(E_feuille, N)

        if erreur_feuille <= erreur_arbre:
            return classe_majoritaire
        return arbre
    else:
        return arbre

clf = DecisionTreeClassifier(ccp_alpha=0.01) # Contrôle de l'élagage via CCP
# ... fit(X,y) et plot_tree(...)