¿Por qué no son computacionalmente costosos árboles de decisión?

Question

En Una Introducción a la Estadística de Aprendizaje con Aplicaciones en R, los autores escriben que la colocación de un árbol de decisión es muy rápido, pero esto no tiene sentido para mí. El algoritmo tiene que ir a través de cada función y la partición en cada manera posible con el fin de encontrar el óptimo de split. Para numérica características con $n$ observaciones, esto podría resultar en $n$ particiones para cada característica.

Soy un malentendido de cómo el binario de la división de obras? O es que hay una razón por la que este algoritmo no llevaría mucho tiempo?

Answer 1

Algoritmos de árboles de decisión no calcular todos los posibles árboles cuando se ajustan a un árbol. Si lo hiciera sería la solución de una NP-duro problema. Árbol de decisión de ajuste de los algoritmos suelen hacer codiciosos decisiones en el proceso de montaje—en cada etapa de optimizar el sub-problema para encontrar un óptimo split con los datos en el nodo dado y seguir avanzando en el proceso de montaje. También, como usted se mueve más en el árbol de decisión tiene un conjunto de datos más pequeño que la haya hecho el nodo dado, de modo que usted será la optimización de la división de la regla sobre un subconjunto más pequeño de datos. Todas estas opciones son lineales exploraciones de los datos en el nodo dado. Esto no es complicado de hacer, pero puede ser un poco costoso computacionalmente si usted tiene un gran número de observaciones o de un gran número de covariables dividir. Sin embargo, una gran parte del trabajo puede ser dividido y enviados a diferentes máquinas para trabajar por lo que hay maneras de construir su arquitectura computacional a escala. En general, el método funciona con bastante rapidez en muchos de los conjuntos de datos que vemos en los cursos y en muchos escenarios del mundo real así.

Answer 2

Hay algunas diferencias entre el CARRO y el C4.5 algoritmos de construcción de árboles de decisión. Por ejemplo, el CARRITO de los usos de Gini Impureza a de selección de características, mientras que C. 4.5 usos de la Entropía de Shannon. Yo creo que las diferencias no son relevantes para la respuesta, así que no voy a diferenciar entre aquellos.

Lo que hace que los árboles de decisión más rápido de lo que se podría pensar es:

1. Como otros han dicho, estos algoritmos son: 1-algoritmos de búsqueda hacia delante. Realizar optimizaciones locales. En cada rama, seleccione la regla que maximiza/minimiza cualquier métrica que utiliza (Gini o Entropía). Esto significa que podría perder reglas donde el uso de un operador lógico como and resultaría en un mejor árbol. Esto significa que usted debe ser muy cuidadoso/inteligente cuando haciendo característica de la ingeniería. Por ejemplo, digamos que usted está tratando de predecir lo que la gente bebe, usted podría querer función de ingeniero de cosas como new_feature = hour > 22 & hour < 4 & (friday_night | saturday_night). Los árboles de decisión se pueden perder estas reglas, o darle menos importancia de lo que deberían.
2. Lo que es más importante, las métricas utilizadas por los árboles de decisión pueden ser calculadas de forma incremental. Digamos que usted tiene una característica $X_1 = \{3,1.5,2.5,2,1\}$. El árbol de decisión no necesita para calcular la métrica de X <= 1, a continuación, calcular la métrica de nuevo por X <= 1.5, luego de nuevo para X <= 2, etc. De Gini y la Entropía fueron escogidos debido a que puede ser calculada de forma incremental. Primero de todo, cada función se clasifican, por lo que ha $X_1 = \{1,1.5,2,2.5,3\}$. En segundo lugar, cuando se compute X <= 1, puede utilizar el resultado para fácilmente calcular X <= 1.5. Es como hacer un promedio. Si usted tiene una media de una muestra, $\bar x$, y os dará otro valor $v$, se puede barato actualización de su promedio haciendo, $\bar x \leftarrow \frac{n\bar x+v}{n+1}$. Coeficiente de Gini se calcula como una fracción de la suma, que puede ser fácilmente calculada de forma incremental para la muestra.
3. Los árboles de decisión pueden ser paralelizado. Cada nodo se compone de dos ramas, que son independientes. Por lo tanto, en cada sucursal, usted tiene la oportunidad de poner en paralelo la creación de árboles. Además, la selección de la función en sí misma también puede ser paralelizado. Esto es lo que hace que los paquetes como xgboost tan rápido. Gradiente de impulsar es secuencial y no puede ser paralelizado, pero los árboles mismos.

Answer 3

Sólo para enriquecer las respuestas,

Jerárquica de los ejes paralelos los árboles de decisiones son rápidas (CARRO, C4.5), pero existen otras alternativas, tales como la no-jerárquica de árboles de decisión o aquellos que realizan oblicuo particiones que no son, a pesar de que puede ser más preciso. Compruebe las siguientes referencias si usted está interesado (Que no son un exahustive de selección).

No-jerárquica:

Grubinger, T., Zeileis, A. y Pfeiffer, K.-., 2014. Evtree: aprendizaje Evolutivo de globalmente óptima árboles de clasificación y regresión en R. J. Stat.Software 61 (1), 1-29.

Oblicuo divisiones:

Murthy, S. K., Kasif, S. y Salzberg, S., 1994. Un sistema para la inducción de la oblicua de árboles de decisión. J. Artif. Intell. Res. 2 (1), 1-32. http://dx.doi.org/doi:10.1613/jair.63. Cantú-Paz, E. y Kamath, C., 2003. La inducción de la oblicua de árboles de decisión con algoritmos evolutivos. IEEE Trans. Evol. Comput. 7 (1), 54-68. http://dx.doi.org/10.1109/TEVC.2002.806857. De salud, D., Kasif, S. y Salzberg, S., 1993. La inducción de la oblicua de árboles de decisión. J. Artif. Intell. Res. 2 (2), 1002-1007.

Buena suerte!