Les arbres de décision sont l'un des algorithmes d'apprentissage automatique les plus intuitifs et les plus largement utilisés pour la classification et la régression. Ils fonctionnent en divisant les données en branches basées sur les valeurs de caractéristiques, en imitant la façon dont les humains prennent les décisions. Bien que les bibliothèques comme scikit-learn rendent les arbres de décision de construction trivial, la mise en œuvre d'un arbre de décision à partir de zéro est une excellente façon pour les débutants de saisir le fonctionnement intérieur de l'algorithme.

Qu'est-ce qu'un arbre de décision?

Un arbre de décision est une structure semblable à un diagramme de flux où chaque noeud interne représente un test sur une caractéristique (p. ex., -Est âge > 30?-), chaque branche représente le résultat de ce test, et chaque noeud de feuille détient une étiquette de classe ou une valeur continue. L'objectif est de créer un modèle qui prédit une variable cible en apprenant des règles de décision simples déduites des caractéristiques de données.

L'arbre est construit de façon récursive : à partir de la racine, l'algorithme sélectionne la meilleure fonctionnalité et le point de division qui sépare les données de façon la plus nette. Ce processus est répété sur chaque sous-ensemble jusqu'à ce qu'une condition d'arrêt soit remplie.

Concepts fondamentaux que vous devez comprendre

Noeuds, branches et feuilles

Le nœud racine contient l'ensemble des données de formation. Les nœuds internes testent une fonctionnalité et divisent les données en deux ou plusieurs nœuds enfants. Les branches sont les connexions qui représentent le résultat d'un test. Les nœuds leafs (nodes terminaux) produisent la prédiction finale – la classe la plus courante dans la classification ou la valeur moyenne dans la régression.

Critères de partage

Pour construire un arbre, il faut un moyen de mesurer la qualité d'une séparation potentielle. Les critères les plus courants sont les suivants :

  • Impureté gini[ – utilisée dans la classification pour mesurer la fréquence à laquelle un élément choisi au hasard serait mal étiqueté s'il était étiqueté au hasard selon la distribution des classes du sous-ensemble.
  • Entropie – mesure la quantité de désordre ou d'incertitude dans un ensemble. L'objectif est de minimiser l'entropie après la scission (gain d'information).
  • Réduction de la variation[ – utilisée pour les arbres de régression. Il calcule la réduction de la variance (ou erreur carrée moyenne) obtenue par la fraction.

L'algorithme évalue chaque scission possible sur chaque fonction et choisit celle qui produit la plus grande réduction de l'impureté (ou gain d'information).

Ratio des gains et des gains d'information

Le gain d'information est la différence entre l'impureté du nœud parent et la somme pondérée des impuretés enfantines. Bien que simple, il tend à favoriser les fonctionnalités avec de nombreuses valeurs. Le rapport de gain (utilisé dans C4.5) normalise cela. Pour ce tutoriel, nous allons coller avec le gain d'information standard en utilisant l'impureté Gini, qui est la valeur par défaut dans CART (Classification et Arbres de régression).

Construire un arbre de décision étape par étape

1. Préparez vos données

Pour être simple, utilisez un ensemble de données de classification binaire avec des fonctionnalités numériques. Par exemple:

  • Caractéristiques: Âge, revenu
  • Cible : Approuvé (1) ou Non Approuvé (0)

Nettoyer les données : gérer les valeurs manquantes, supprimer les duplicata et assurer les types numériques. Les arbres de décision peuvent gérer les types de données mixtes mais nous nous en tenons à la numérotation pour l'implémentation.

2. Définir une fonction de critère de division

Nous allons mettre en œuvre l'impureté de Gini. L'index de Gini pour un ensemble d'éléments est:

où p i est la proportion d'éléments dans la classe i. Pour une fraction binaire, le Gini global est la moyenne pondérée des nœuds enfants.

3. Mettre en œuvre l'évaluation de fractionnement

Pour chaque fonction, triez les valeurs uniques. Testez chaque seuil possible (point intermédiaire entre les valeurs triées consécutives). Pour chaque seuil candidat, divisez les données en groupes gauche et droit, calculez le Gini et suivez la meilleure division.

4. Construire l'arbre de façon récursive

Créer une fonction qui prend un sous-ensemble de données et une profondeur courante. Elle vérifie les conditions d'arrêt (p. ex., profondeur maximale atteinte, échantillons minimums par noeud, ou aucun gain d'information). Si une condition est remplie, créer un noeud de feuille avec la classe majoritaire. Sinon, trouver le meilleur partage et créer un noeud interne, puis appeler récursivement la fonction sur les fractions gauche et droite.

5. Faire des prédictions

Une fois l'arbre construit, la prédiction est simple : commencez à la racine, suivez les branches en évaluant les tests de fonctionnalité sur le nouvel échantillon, et retournez la valeur de la feuille que vous atterrissez.

Mise en œuvre complète en Python

Ci-dessous est une mise en œuvre minimale et complète d'un arbre de décision pour la classification à l'aide de l'impureté Gini. Ce code est destiné à l'apprentissage – il n'est pas optimisé pour les grands ensembles de données.

import numpy as np
from collections import Counter

class DecisionTree:
 def __init__(self, max_depth=None, min_samples_split=2):
 self.max_depth = max_depth
 self.min_samples_split = min_samples_split
 self.tree = None

 def fit(self, X, y):
 dataset = np.column_stack((X, y))
 self.tree = self._grow_tree(dataset)

 def _grow_tree(self, dataset, depth=0):
 X, y = dataset[:, :-1], dataset[:, -1]
 n_samples, n_features = X.shape
 n_labels = len(np.unique(y))

 # Stopping conditions
 if (n_labels == 1 or depth == self.max_depth or n_samples < self.min_samples_split):
 leaf_value = Counter(y).most_common(1)[0][0]
 return {'leaf': True, 'value': leaf_value}

 best_feature, best_threshold = self._best_split(dataset, n_features)
 if best_feature is None:
 leaf_value = Counter(y).most_common(1)[0][0]
 return {'leaf': True, 'value': leaf_value}

 left_idx, right_idx = self._split(dataset[:, best_feature], best_threshold)
 left_subtree = self._grow_tree(dataset[left_idx], depth+1)
 right_subtree = self._grow_tree(dataset[right_idx], depth+1)
 return {'leaf': False,
 'feature': best_feature,
 'threshold': best_threshold,
 'left': left_subtree,
 'right': right_subtree}

 def _best_split(self, dataset, n_features):
 best_gini = float('inf')
 best_feature, best_threshold = None, None
 for feature in range(n_features):
 thresholds = np.unique(dataset[:, feature])
 for i in range(len(thresholds)-1):
 thresh = (thresholds[i] + thresholds[i+1]) / 2
 left_idx, right_idx = self._split(dataset[:, feature], thresh)
 if len(left_idx) == 0 or len(right_idx) == 0:
 continue
 gini = self._gini_gain(dataset, left_idx, right_idx)
 if gini < best_gini:
 best_gini = gini
 best_feature = feature
 best_threshold = thresh
 return best_feature, best_threshold

 def _split(self, values, threshold):
 left_idx = np.where(values <= threshold)[0]
 right_idx = np.where(values > threshold)[0]
 return left_idx, right_idx

 def _gini_gain(self, dataset, left_idx, right_idx):
 total = len(left_idx) + len(right_idx)
 gini_left = self._gini(dataset[left_idx, -1])
 gini_right = self._gini(dataset[right_idx, -1])
 return (len(left_idx)/total) * gini_left + (len(right_idx)/total) * gini_right

 def _gini(self, labels):
 _, counts = np.unique(labels, return_counts=True)
 p = counts / np.sum(counts)
 return 1 - np.sum(p**2)

 def predict(self, X):
 return np.array([self._predict_row(x, self.tree) for x in X])

 def _predict_row(self, x, node):
 if node['leaf']:
 return node['value']
 if x[node['feature']] <= node['threshold']:
 return self._predict_row(x, node['left'])
 else:
 return self._predict_row(x, node['right'])

Tester l'arbre

Utilisez un jeu de données simple comme le jeu de données iris classique (deux fonctionnalités pour la classification binaire). Le jeu de données scikit‐learn Iris fonctionne bien. Comparez la précision de votre arbre avec les scikit‐learn=s pour vérifier la justesse.

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

data = load_iris()
X = data.data[:100] # take only first two classes (binary)
y = data.target[:100]

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

tree = DecisionTree(max_depth=3)
tree.fit(X_train, y_train)
preds = tree.predict(X_test)
accuracy = np.mean(preds == y_test)
print(f'Accuracy: {accuracy:.2f}')

Techniques avancées pour améliorer votre arbre

Élagage pour éviter les surajustements

Un arbre entièrement cultivé peut mémoriser le bruit dans les données de formation. La taille enlève les branches qui ont peu de puissance prédictive. Les méthodes courantes sont la pré-élagage (arrêt de la croissance tôt par ou ) et la post-élagage (croissance de l'arbre complet puis suppression des branches à l'aide d'un ensemble de validation ou de taille de complexité des coûts).

Manipulation en continu et caractéristiques catégoriques

Pour les caractéristiques continues, nous avons utilisé des points médians entre les valeurs triées comme seuils. Pour les caractéristiques catégoriques (p. ex. -Couleur = rouge/vert/bleu), chaque catégorie peut devenir une branche séparée (découpage multidirectionnel) ou vous pouvez les encoder binairement. La plupart des implémentations modernes (comme scikit-learn) utilisent des fractions binaires même pour les caractéristiques catégoriques en évaluant tous les sous-ensembles.

Faire face aux valeurs manquantes

Les données du monde réel ont souvent des valeurs manquantes. Une approche simple consiste à attribuer les valeurs manquantes à la branche la plus fréquente parmi les échantillons d'entraînement qui ont la fonctionnalité. C4.5 utilise une méthode probabiliste. Comme il s'agit d'un tutoriel débutant, nous supposons que les données sont complètes.

Comparaison avec les bibliothèques et lectures complémentaires

Bien que construire à partir de zéro est éducatif, les systèmes de production utilisent des bibliothèques comme scikit-learn qui fournissent des implémentations optimisées C. Vous pouvez en apprendre plus sur la documentation officielle scikit-learn de décision des arbres. Pour une théorie plus profonde, le livre -Les éléments de l'apprentissage statistique de Hastie, Tibshirani et Friedman est une ressource faisant autorité.

Conclusion

Construire un arbre de décision à partir de zéro démystique l'un des algorithmes les plus fondamentaux de l'apprentissage machine. Vous avez appris comment une simple procédure de fractionnement récursif peut produire un modèle puissant. En écrivant vous-même le code, vous acquiérez une compréhension plus approfondie des mesures d'impureté, de la sélection fractionnée et des compromis entre biais et variance.