Comme tous les modèles de machine learning supervisé, les arbres de décision un ensemble d'exemples d'entraînement. L'entraînement optimal d'un arbre de décision un problème NP-difficile. Par conséquent, l'entraînement est généralement effectué à l'aide d'une méthode heuristique, un algorithme d'apprentissage facile à créer qui donne une réponse non optimale, mais proche de optimal, l'arbre de décision.
La plupart des algorithmes utilisés pour entraîner les arbres de décision fonctionnent avec une division gloutonne et stratégie de vaincre. L'algorithme commence par créer un nœud unique (la racine) et et pousse l'arbre de décision de manière récursive.
Au niveau de chaque nœud, toutes les conditions possibles sont évaluées et notées. La l'algorithme sélectionne le "meilleur" la condition, c'est-à-dire celle dont le score. Pour l'instant, sachez simplement que le score est une métrique en corrélation avec le une tâche et des conditions sont sélectionnées pour maximiser cette métrique.
Par exemple, dans le Palmer Manchots (utilisé pour les exemples de code plus loin dans ce cours), la plupart des modèles Adelie et Chinstrap les manchots ont un bec supérieur à 16 mm, alors que la plupart des Gentoo les manchots ont un bec plus petit. Par conséquent, la condition bill_length_mm ≥ 16 permet d'obtenir des prédictions presque parfaites pour le Les manchots papou, mais qui ne peuvent pas différencier entre Adelies et Chinstraps. L'algorithme choisira probablement cette condition.
<ph type="x-smartling-placeholder"></ph> Figure 7. La 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 feuille la prédiction est déterminée comme étant 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)
Passons en revue les étapes d'entraînement d'un arbre de décision particulier dans plus en détail.
Étape 1:Créez une racine:
Étape 2:Développer le nœud 1. Condition "x1 ≥ 1" a été trouvé. Deux nœuds enfants sont créés:
Étape 3:Développer le nœud 2. Aucune condition satisfaisante n'a été trouvée. Ainsi, le nœud dans une feuille:
Étape 4:Développer le nœud 3. Condition "x2 ≥ 0,5" a été trouvé. Deux enfants les nœuds sont créés.
Il existe d'autres méthodes pour faire pousser des arbres de décision. Une alternative populaire consiste à optimiser les nœuds de manière globale au lieu d'utiliser une stratégie de division et de conquête.
growing_strategy="BEST_FIRST_GLOBAL".
Voir <ph type="x-smartling-placeholder"></ph>
consultez la documentation.
Selon le nombre et le type de caractéristiques d'entrée, le nombre de les conditions possibles pour un nœud donné peuvent être énormes, généralement infinies. Par exemple, pour une condition de seuil $\mathrm{feature}_i \geq t$, la combinaison de tous les possible valeurs de seuil pour $t \in \mathbb{R}$ est infini.
La routine responsable de la recherche du meilleur état s'appelle la splitter. Comme il doit tester un grand nombre de conditions possibles, les diviseurs sont les goulots d'étranglement lors de l'entraînement d'un arbre de décision.
Le score maximisé par le séparateur dépend de la tâche. Exemple :
- Gain d'informations et Gini (tous deux abordés plus tard) sont couramment utilisées pour la classification.
- L'erreur quadratique moyenne est couramment utilisée pour la régression.
Il existe de nombreux algorithmes de fractionnement, chacun prenant en charge différemment les éléments suivants:
- le type de caractéristiques ; par exemple, numérique, catégorielle, textuelle
- La tâche ; (classification binaire, classification à plusieurs classes, etc.) classification, régression
- Le type de condition par exemple, une condition de seuil, une condition in-set, condition oblique
- 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 fractionnement équivalentes avec différents compromis concernant l'utilisation de la mémoire, l'utilisation du processeur, la distribution des calculs, etc.