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.
