Si cultivas el árbol completo, el mejor primero (en forma de hoja) y el primero en profundidad (en términos de nivel) darán como resultado el mismo árbol. La diferencia está en el orden en que se expande el árbol. Dado que normalmente no cultivamos árboles en toda su profundidad, el orden es importante: la aplicación de criterios de detención temprana y métodos de poda puede dar lugar a árboles muy diferentes. Debido a que las hojas sabias eligen divisiones en función de su contribución a la pérdida global y no solo a la pérdida a lo largo de una rama en particular, a menudo (no siempre) aprenderán árboles de error más bajos "más rápido" que a nivel. Es decir, para un pequeño número de nodos, las hojas probablemente superen el nivel. A medida que agrega más nodos, sin detenerse ni podarse, convergerán con el mismo rendimiento porque literalmente construirán el mismo árbol eventualmente.
Referencia:
Shi, H. (2007). Mejor primer árbol de decisión de aprendizaje (Tesis, Master of Science (MSc)). La Universidad de Waikato, Hamilton, Nueva Zelanda. Recuperado de https://hdl.handle.net/10289/2317
EDITAR: Con respecto a su primera pregunta, tanto C4.5 como CART son ejemplos profundos, no los mejores primero. Aquí hay contenido relevante de la referencia anterior:
1.2.1 Árboles de decisión estándar
Algoritmos estándar como C4.5 (Quinlan, 1993) y CART (Breiman et al., 1984) para la inducción de arriba hacia abajo de los árboles de decisión expanden los nodos en primer orden en profundidad en cada paso utilizando la estrategia de dividir y conquistar. Normalmente, en cada nodo de un árbol de decisión, la prueba solo implica un atributo único y el valor del atributo se compara con una constante. La idea básica de los árboles de decisión estándar es que, primero, seleccione un atributo para colocar en el nodo raíz y cree algunas ramas para este atributo en función de algunos criterios (por ejemplo, información o índice de Gini). Luego, divida las instancias de entrenamiento en subconjuntos, uno para cada rama que se extiende desde el nodo raíz. El número de subconjuntos es el mismo que el número de ramas. Luego, este paso se repite para una rama elegida, utilizando solo aquellas instancias que realmente la alcanzan. Se usa un orden fijo para expandir los nodos (normalmente, de izquierda a derecha). Si en algún momento todas las instancias en un nodo tienen la misma etiqueta de clase, que se conoce como un nodo puro, la división se detiene y el nodo se convierte en un nodo terminal. Este proceso de construcción continúa hasta que todos los nodos sean puros. Luego es seguido por un proceso de poda para reducir el sobreajuste (ver Sección 1.3).
1.2.2 Mejores árboles de decisión primero
Otra posibilidad, que hasta ahora parece haber sido evaluada solo en el contexto de algoritmos de refuerzo (Friedman et al., 2000), es expandir los nodos en el mejor primer orden en lugar de un orden fijo. Este método agrega el "mejor" nodo dividido al árbol en cada paso. El "mejor" nodo es el nodo que reduce al máximo la impureza entre todos los nodos disponibles para la división (es decir, no etiquetados como nodos terminales). Aunque esto da como resultado el mismo árbol completamente desarrollado que la expansión estándar de profundidad primero, nos permite investigar nuevos métodos de poda de árboles que usan validación cruzada para seleccionar el número de expansiones. Tanto la poda previa como la poda posterior se pueden realizar de esta manera, lo que permite una comparación equitativa entre ellas (consulte la Sección 1.3).
Los mejores árboles de decisión primero se construyen de una manera de dividir y conquistar similar a los árboles de decisión estándar de profundidad primero. La idea básica de cómo se construye el mejor árbol primero es la siguiente. Primero, seleccione un atributo para colocar en el nodo raíz y cree algunas ramas para este atributo según algunos criterios. Luego, divida las instancias de entrenamiento en subconjuntos, uno para cada rama que se extiende desde el nodo raíz. En esta tesis solo se consideran los árboles de decisión binarios y, por lo tanto, el número de ramas es exactamente dos. Luego, este paso se repite para una rama elegida, utilizando solo aquellas instancias que realmente la alcanzan. En cada paso elegimos el "mejor" subconjunto entre todos los subconjuntos que están disponibles para expansiones. Este proceso de construcción continúa hasta que todos los nodos son puros o se alcanza un número específico de expansiones. Figura 1. 1 muestra la diferencia en orden dividido entre un árbol hipotético binario best-first y un árbol hipotético binary first-first. Tenga en cuenta que se pueden elegir otros ordenamientos para el mejor primer árbol, mientras que el orden es siempre el mismo en el caso de profundidad primero.
