Comme tous les modèles de machine learning supervisé, les arbres de décision sont entraînés pour expliquer au mieux un ensemble d'exemples d'entraînement. L'entraînement optimal d'un arbre de décision est un problème NP-difficile. Par conséquent, l'entraînement est généralement effectué à l'aide d'heuristiques, un algorithme d'apprentissage facile à créer qui fournit un arbre de décision non optimal, mais proche de l'optimal.
La plupart des algorithmes utilisés pour entraîner les arbres de décision fonctionnent avec une stratégie gourmande en division et conquête. L'algorithme commence par créer un seul nœud (la racine), puis développe l'arbre de décision de manière récursive et aiguë.
À chaque nœud, toutes les conditions possibles sont évaluées et notées. L'algorithme sélectionne la "meilleure" condition, c'est-à-dire celle qui a obtenu le score le plus élevé. Pour l'instant, sachez simplement que le score est une métrique en corrélation avec la tâche et que des conditions sont sélectionnées pour maximiser cette métrique.
Par exemple, dans l'ensemble de données Palmer Penguins (utilisé pour les exemples de code plus loin dans ce cours), la plupart des manchots Adélie et Chinstrap ont une longueur supérieure à 16 mm, tandis que la plupart des manchots Gentoo ont un bec plus petit. Par conséquent, la condition bill_length_mm ≥ 16 donne des prédictions presque parfaites pour les manchots génératifs, mais ne peut pas faire la différence entre les manchots à jugulaire et les manchots à jugulaire. L'algorithme choisira probablement cette condition.
Figure 7. Première étape pour faire pousser un arbre.
L'algorithme se répète ensuite de manière récursive et indépendante sur les deux nœuds enfants. Lorsqu'aucune condition satisfaisante n'est trouvée, le nœud devient une feuille. La prédiction feuille est déterminée comme la valeur d'étiquette la plus représentative dans les exemples.
L'algorithme est le suivant:
def train_decision_tree(training_examples):
root = create_root() # Create a decision tree with a single empty root.
grow_tree(root, training_examples) # Grow the root node.
return root
def grow_tree(node, examples):
condition = find_best_condition(examples) # Find the best condition.
if condition is None:
# No satisfying conditions were found, therefore the grow of the branch stops.
set_leaf_prediction(node, examples)
return
# Create two childrens for the node.
positive_child, negative_child = split_node(node, condition)
# List the training examples used by each children.
negative_examples = [example for example in examples if not condition(example)]
positive_examples = [example for example in examples if condition(example)]
# Continue the growth of the children.
grow_tree(negative_child, negative_examples)
grow_tree(positive_child, positive_examples)
Examinons plus en détail les étapes de l'entraînement d'un arbre de décision particulier.
Étape 1:Créez une racine:
Étape 2:Développez le nœud 1. La condition "x1 ≥ 1" a été trouvée. Deux nœuds enfants sont créés:
Étape 3:Développez le nœud 2. Aucune condition satisfaisante n'a été trouvée. Donc, faites du nœud une feuille:
Étape 4:Développez le nœud 3. La condition "x2 ≥ 0,5" a été trouvée. Deux nœuds enfants sont créés.
D'autres méthodes existent pour faire pousser des arbres de décision. Une alternative populaire consiste à optimiser les nœuds à l'échelle mondiale au lieu d'utiliser une stratégie "diviser pour mieux régner".
growing_strategy="BEST_FIRST_GLOBAL".
Pour en savoir plus, consultez la
documentation.
Selon le nombre et le type de caractéristiques d'entrée, le nombre de conditions possibles pour un nœud donné peut être énorme, voire infini. Par exemple, avec une condition de seuil $\mathrm{feature}_i \geq t$, la combinaison de toutes les valeurs de seuil possibles pour $t \in \mathbb{R}$ est infinie.
La routine chargée de trouver la meilleure condition s'appelle le séparateur. Étant donné qu'il doit tester un grand nombre de conditions possibles, les séparateurs constituent le goulot d'étranglement lors de l'entraînement d'un arbre de décision.
Le score maximal par le séparateur dépend de la tâche. Exemple :
- Les acquisitions d'informations et Gini (tous deux décrits plus loin) sont couramment utilisés pour la classification.
- L'erreur quadratique moyenne est couramment utilisée pour la régression.
Il existe de nombreux algorithmes de division, chacun offrant une compatibilité variable pour les éléments suivants:
- Type de caractéristiques (numérique, catégorielle ou textuelle, par exemple)
- La tâche (par exemple, classification binaire, classification à classes multiples, régression)
- Type de condition (par exemple, condition de seuil, condition d'encart, condition obligatoire)
- Les critères de régularisation (par exemple, des séparateurs exacts ou approximatifs pour les conditions de seuil)
En outre, il existe des variantes de séparateurs équivalentes avec différents compromis en termes d'utilisation de la mémoire, du processeur, de la distribution des calculs, etc.