Diferentes algoritmos de árbol de decisión con comparación de complejidad o rendimiento

Question

Estoy investigando la minería de datos y, más precisamente, los árboles de decisión.

Me gustaría saber si hay varios algoritmos para construir un árbol de decisión (o sólo uno?), Y que es mejor, en función de criterios tales como

• Rendimiento
• Complejidad
• Errores en la toma de decisiones
• y más.

Answer 1

implementaciones de árboles de decisión se diferencian principalmente a lo largo de estos ejes:

• el criterio división (es decir, cómo se calcula la "variación")

• si se construye modelos para regresión (variables continuas, p. Ej., Una puntuación ), Así como clasificación (variables discretas, por ejemplo, una clase etiqueta)

• técnica para eliminar/reducir exceso de ajuste

• si puede manejar datos incompletos

Los principales implementaciones de árboles de decisión son:

• ID3, o iterativo Dichotomizer, fue el primero de tres Árbol de decisión implementaciones desarrolladas por Ross Quinlan (Quinlan, J. R. 1986. La inducción de árboles de decisión. Mach Aprender. 1, 1 (Mar. 1986), 81-106.)

• Carro o clasificación y regresión árboles se utiliza a menudo como un sigla genérica para el Árbol de Decisión término, a pesar de que aparentemente tiene una mayor significado específico. En resumen, la implementación de CART es muy similar a C4.5; la única diferencia notable es que CART construye el árbol en base a un criterio de división numérica aplicado de forma recursiva a los datos, mientras que C4.5 incluye el paso intermedio de construir conjunto de reglas s.

• C4.5, la siguiente iteración de Quinlan.Las nuevas características (frente ID3) son: (i) acepta ambas características continuas y discretas; (ii) maneja puntos de datos incompletos; (Iii) resuelve exceso de ajuste problema mediante la técnica de abajo a arriba (muy inteligente) generalmente conocido como "poda"; y (iv) pesos diferentes se pueden aplicar las características que comprenden los datos de entrenamiento . De estos, los primeros tres son muy importantes, y sugeriría que cualquier implementación DT que elija tenga los tres. El cuarto (ponderación diferencial) es mucho menos importante

• C5.0, la iteración de Quinlan más reciente. Esta implementación es cubierta por una patente y, probablemente, como resultado, rara vez se implementa (fuera de los paquetes de software comercial). Nunca he codificado una implementación C5.0 a mí mismo (yo ni siquiera he visto el código fuente) así que no puedo ofrecer una comparación informada de C5.0 C4.5 frente. Siempre he sido escéptico acerca de las mejoras reclamadas por su inventor (Ross Quinlan) - por ejemplo, afirma que es "varios órdenes de magnitud" más rápido que C4.5. Otros reclamos son similarmente amplios ("significativamente más eficiente en memoria") y así sucesivamente. Sólo te señalo studies que informan el resultado de la comparación de las dos técnicas y se puede decidir por sí mismo.

• CHAID (detector automático de interacciones de chi-cuadrado) en realidad es anterior la aplicación ID3 original de aproximadamente seis años (publicado en una tesis Ph.D. por Gordon Kass en 1980). Sé que cada poco de este technique.The R plataforma tiene un paquete llamado CHAID cuales incluye una excelente documentación

• MARS (splines de regresión múltiple adaptativo) es en realidad un término registrado por el inventor original de Marte, Sistemas de Salford . Como resultado de , los clones de MARS en bibliotecas no vendidas por Salford se denominan de manera diferente a MARS, por ejemplo, en R, la función relevante son los polímeros en la biblioteca de poli-splines. Matlab y Statistica también tienen implementaciones con MARS-funcionalidad

que recomendaría cesta o C4.5 (aunque, de nuevo, no tengo experiencia directa con C5.0 o con CHAID, aunque estoy familiarizado con su función conjuntos).

C4.5 es el sabor del Árbol de decisiones implementado en Orange; CART es el sabor en sklearn, ambas excelentes implementaciones en excelentes bibliotecas de ML.

C4.5 es un paso importante más allá de ID3 - en términos de rango (C4.5 tiene un espectro mucho más amplio de casos de uso, ya que puede manejar las variables continuas en los datos de entrenamiento) y en términos de modelo de calidad.

Tal vez la mejora reclamado más significativo de C5.0 C4.5 frente es el soporte para árboles potenciado. El soporte conjunto para DTs - árboles potenciados y Random Forests - se ha incluido en la implementación de DT en Orange; aquí, se agregó el soporte de conjunto a un algoritmo C4.5. sklearn también cuenta con una variedad de métodos aleatorios de bosque y refuerzo.