Arbres de décision: traversée des feuilles (meilleur en premier) et des arbres au niveau

14

Problème 1:

Je suis confus par la description de LightGBM concernant la façon dont l'arbre est développé.

Ils déclarent:

La plupart des algorithmes d'apprentissage de l'arbre de décision développent l'arbre par niveau (profondeur), comme dans l'image suivante:

entrez la description de l'image ici

Question 1 : Quels «la plupart» des algorithmes sont implémentés de cette façon? Autant que je sache, C4.5 et CART utilisent DFS. XGBoost utilise BFS. Quels autres algorithmes ou packages utilisent BFS pour les arbres de décision?

Problème 2:

LightGBM déclare:

LightGBM pousse l'arbre par feuille (meilleur en premier) .Il choisira la feuille avec la perte de delta maximale pour croître. Lors de la croissance d'une même feuille, l'algorithme au niveau des feuilles peut réduire plus de pertes que l'algorithme au niveau du niveau.

entrez la description de l'image ici

Question 2 : Est-il exact de dire que les arbres à croissance nivelée auront une profondeur égale pour toutes les feuilles?

Questions 3: Si la question 2 n'est pas correcte, les arbres de croissance au niveau et au niveau des feuilles auront la même apparence à la fin du parcours (sans élagage, etc.). Est-ce une affirmation correcte?

Questions 4: Si la question 3 est correcte, comment "l'algorithme au niveau des feuilles peut réduire plus de pertes que l'algorithme au niveau des niveaux"? Cela a-t-il à voir avec l'algorithme de post-élagage?

Jekaterina Kokatjuhha
la source

Réponses:

11

Si vous cultivez l'arbre complet, le meilleur en premier (feuille) et la profondeur en premier (niveau) donneront le même arbre. La différence réside dans l' ordre dans lequel l'arborescence est développée. Comme nous ne cultivons pas normalement les arbres à leur pleine profondeur, l'ordre est important: l'application de critères d'arrêt précoce et de méthodes d'élagage peut entraîner des arbres très différents. Parce que les feuilles choisissent les divisions en fonction de leur contribution à la perte globale et pas seulement à la perte le long d'une branche particulière, elles apprennent souvent (pas toujours) les arbres à erreurs plus faibles "plus rapidement" que les niveaux. C'est-à-dire pour un petit nombre de nœuds, les feuilles seront probablement plus performantes au niveau des feuilles. Au fur et à mesure que vous ajoutez des nœuds, sans arrêt ni élagage, ils convergeront vers les mêmes performances, car ils construiront littéralement le même arbre à terme.

Référence:

Shi, H. (2007). Apprendre le meilleur premier arbre de décision (Thèse, Master of Science (MSc)). Université de Waikato, Hamilton, Nouvelle-Zélande. Récupéré de https://hdl.handle.net/10289/2317


EDIT: En ce qui concerne votre première question, C4.5 et CART sont des exemples de profondeur d'abord, pas les meilleurs d'abord. Voici un contenu pertinent de la référence ci-dessus:

1.2.1 Arbres de décision standard

Les algorithmes standard tels que C4.5 (Quinlan, 1993) et CART (Breiman et al., 1984) pour l'induction descendante des arbres de décision développent les nœuds en ordre de profondeur à chaque étape en utilisant la stratégie de division et de conquête. Normalement, à chaque nœud d'un arbre de décision, le test ne fait intervenir qu'un seul attribut et la valeur d'attribut est comparée à une constante. L'idée de base des arbres de décision standard est que, d'abord, sélectionnez un attribut à placer au nœud racine et créez des branches pour cet attribut en fonction de certains critères (par exemple, des informations ou un index Gini). Ensuite, divisez les instances de formation en sous-ensembles, un pour chaque branche s'étendant à partir du nœud racine. Le nombre de sous-ensembles est le même que le nombre de branches. Ensuite, cette étape est répétée pour une branche choisie, en utilisant uniquement les instances qui y parviennent réellement. Un ordre fixe est utilisé pour développer les nœuds (normalement, de gauche à droite). Si à tout moment toutes les instances d'un nœud ont la même étiquette de classe, connue sous le nom de nœud pur, le fractionnement s'arrête et le nœud est transformé en nœud terminal. Ce processus de construction se poursuit jusqu'à ce que tous les nœuds soient purs. Il est ensuite suivi d'un processus d'élagage pour réduire les sur-raccords (voir section 1.3).

1.2.2 Arbres de décision du meilleur avant tout

Une autre possibilité, qui jusqu'à présent ne semble avoir été évaluée que dans le contexte des algorithmes de renforcement (Friedman et al., 2000), consiste à étendre les nœuds dans le meilleur ordre au lieu d'un ordre fixe. Cette méthode ajoute le «meilleur» nœud partagé à l'arborescence à chaque étape. Le «meilleur» nœud est le nœud qui réduit au maximum l'impureté parmi tous les nœuds disponibles pour le fractionnement (c'est-à-dire non étiquetés comme nœuds terminaux). Bien que cela se traduise par le même arbre adulte que l'expansion standard en profondeur d'abord, il nous permet d'étudier de nouvelles méthodes d'élagage d'arbres qui utilisent la validation croisée pour sélectionner le nombre d'extensions. Le pré-élagage et le post-élagage peuvent être effectués de cette manière, ce qui permet une comparaison équitable entre eux (voir section 1.3).

Les meilleurs arbres de décision sont construits de façon divisée et conquérante semblable aux arbres de décision standard en profondeur d'abord. L'idée de base de la construction d'un arbre best-first est la suivante. Tout d'abord, sélectionnez un attribut à placer au nœud racine et créez des branches pour cet attribut en fonction de certains critères. Ensuite, divisez les instances de formation en sous-ensembles, un pour chaque branche s'étendant à partir du nœud racine. Dans cette thèse, seuls les arbres de décision binaires sont considérés et donc le nombre de branches est exactement deux. Ensuite, cette étape est répétée pour une branche choisie, en utilisant uniquement les instances qui y parviennent réellement. À chaque étape, nous choisissons le «meilleur» sous-ensemble parmi tous les sous-ensembles disponibles pour les extensions. Ce processus de construction se poursuit jusqu'à ce que tous les nœuds soient purs ou qu'un nombre spécifique d'extensions soit atteint. Figure 1. 1 montre la différence dans l'ordre de division entre un arbre binaire hypothétique best-first et un arbre hypothétique binaire profondeur-first. Notez que d'autres ordonnances peuvent être choisies pour l'arbre le meilleur en premier alors que l'ordre est toujours le même dans le cas de la profondeur en premier.

David Marx
la source
Pouvez-vous également répondre à la première question?
Jekaterina Kokatjuhha
Mis à jour ma réponse. La version courte est que C4.5 et CART sont des exemples de profondeur d'abord, pas de meilleur premier.
David Marx
Ma première question ne portait pas sur la définition ou l'explication de best-first ou DFS. Et je me suis dit que C4.5 et CART sont DFS. La première question concernait "Quels" la plupart "des algorithmes sont implémentés par niveau? [...] Quels autres algorithmes ou packages utilisent BFS pour les arbres de décision?"
Jekaterina Kokatjuhha
1
La croissance des arbres «en profondeur d'abord» est au niveau. Voilà ce que j'essayais de vous dire. Lisez l'extrait que j'ai mis en évidence pour vous. Ne confondez pas ici la traversée de graphe DFS et BFS avec la croissance d'arbre "Profondeur d'abord" et "Meilleure première". Ce ne sont pas les mêmes, et la première croissance en profondeur fait référence à ce que vous appelez "BFS", pas "DFS".
David Marx
C'était le point critique qui me manquait tout le temps. Je vous remercie.
Jekaterina Kokatjuhha