Árbol de decisión

Los árboles de decisión (en inglés : árbol de decisión ) son árboles ordenados, dirigidos , se utilizan la descripción de las reglas de decisión . La representación gráfica como un diagrama de árbol ilustra decisiones jerárquicamente sucesivas . Son importantes en numerosas áreas en las que tiene lugar la clasificación automática o las reglas formales se derivan o se presentan a partir del conocimiento empírico .

Propiedades y uso

Los árboles de decisión son un método para la clasificación automática de objetos de datos y, por lo tanto, para resolver problemas de decisión. También se utilizan para la presentación clara de reglas formales. Un árbol de decisión siempre consta de un nodo raíz y cualquier número de nodos internos, así como al menos dos hojas. Cada nodo representa una regla lógica y cada hoja una respuesta al problema de decisión.

La complejidad y la semántica de las reglas no están limitadas desde el principio. Con árboles de decisión binarios , cada expresión de regla solo puede tomar uno de dos valores. Todos los árboles de decisión se pueden convertir en árboles de decisión binarios.

Los árboles de decisión se utilizan en numerosas áreas, e. B.

funcionalidad

Clasificar con árboles de decisión

Para leer una clasificación de un objeto de datos individual, desciende desde el nodo raíz a lo largo del árbol. Se consulta un atributo para cada nodo y se toma una decisión sobre la selección del siguiente nodo. Este procedimiento continúa hasta llegar a una hoja. La hoja corresponde a la clasificación. Básicamente, un árbol contiene reglas para responder exactamente una pregunta.

Ejemplo: un árbol de decisiones con baja complejidad

Árbol de decisión binaria para predecir si un manzano dará fruto

El árbol de decisión binario de enfrente proporciona una respuesta a la pregunta de si un manzano dará fruto. Como entrada, el árbol necesita un vector con información sobre los atributos de un manzano. Por ejemplo, un manzano puede tener los atributos viejo , variedad natural y suelo rico . Comenzando con el nodo raíz, las reglas de decisión del árbol ahora se aplican al vector de entrada. En el árbol de ejemplo, se consulta un atributo del vector de entrada en cada nodo, por ejemplo, la edad del manzano en el nodo raíz. La respuesta decide sobre el siguiente nodo y, por lo tanto, sobre la siguiente regla de decisión a aplicar, en este caso la pregunta sobre la variedad, y luego la pregunta sobre la naturaleza del suelo. Si llega a una hoja de papel después de una serie de reglas evaluadas, obtiene la respuesta a la pregunta original. No siempre es necesario pasar por todos los niveles del árbol de decisiones. Para el manzano descrito anteriormente, la respuesta es sí , lo que significa que el árbol dará fruto. Este proceso de toma de decisiones se llama clasificación formal .

Inducción de árboles de decisión

Los expertos pueden escribir manualmente los árboles de decisión o inducirlos automáticamente a partir de valores empíricos recopilados mediante técnicas de aprendizaje automático . Hay varios algoritmos que compiten para esto.

La inducción de los árboles de decisión suele tener lugar de forma recursiva utilizando el principio de arriba hacia abajo . Para ello, es de crucial importancia que se disponga de un conjunto de datos adecuado con valores empíricos fiables para el problema de decisión (el denominado conjunto de datos de entrenamiento ). Esto significa que se debe conocer la clasificación del atributo de destino para cada objeto en el conjunto de datos de entrenamiento. Para cada paso de inducción, se busca el atributo con el que los datos de entrenamiento se pueden clasificar mejor en este paso con respecto al atributo objetivo . Las medidas de entropía , el índice de Gini u otras se utilizan como medida para determinar la mejor clasificación . El atributo identificado ahora se usa para dividir los datos. El procedimiento se aplica de forma recursiva a los subconjuntos creados de esta manera hasta que cada subconjunto solo contenga objetos con una clasificación. Al final, se creó un árbol de decisiones que describe el conocimiento empírico del conjunto de datos de entrenamiento en reglas formales.

Los árboles ahora se pueden usar para clasificar automáticamente otros conjuntos de datos o para interpretar y evaluar el conjunto de reglas resultante.

Comparación de algoritmos

Todos los algoritmos para la inducción automática de árboles de decisión se basan en el mismo principio recursivo de arriba hacia abajo. Solo difieren en sus criterios para seleccionar los atributos y valores de las reglas en los nodos del árbol, en sus criterios para cancelar el proceso de inducción y en los posibles pasos de posprocesamiento que posteriormente optimizan una rama ya calculada de un árbol ( o árboles enteros) según varios criterios.

En la práctica, existen diferentes familias de algoritmos:

  • La familia más antigua son los CHAID ( Detectores automáticos de interacción de chi-cuadrado ) de 1964. Pueden crear árboles sobre la base de atributos discretos .
  • La familia de CART's ( Classification And Regression Trees ) extiende el CHAIDS sobre todo la capacidad de poder procesar atributos de valor real mediante un criterio de división ( criterio dividido en inglés ) para dividir los atributos de valor real en categorías discretas. Además, algunas estrategias de optimización como B. introdujo la poda .
  • Los algoritmos más recientes son el algoritmo ID3 y sus sucesores C4.5 y C5.0 . Formalmente, pertenecen a la familia CART , pero a menudo se los considera un grupo independiente, ya que introducen numerosas estrategias de optimización nuevas en comparación con CART .

Tasa de error y efectividad

La tasa de error de un árbol de decisión es el número de objetos de datos clasificados incorrectamente en relación con todos los objetos de datos en un conjunto de datos. Este número se determina regularmente en los datos de entrenamiento utilizados o, mejor, en un conjunto de objetos de datos que se clasifican de la manera más correcta posible en relación con los datos de entrenamiento.

Dependiendo del área de aplicación, puede ser particularmente importante mantener bajo el número de objetos clasificados como falso positivo o falso negativo . En medicina de emergencia, por ejemplo, es mucho menos dañino tratar a un paciente sano que no tratar a un paciente enfermo. Por tanto, la eficacia de los árboles de decisión es siempre una variable dependiente del contexto.

Representación en forma normal disyuntiva

Cada clasificación posible de un árbol de decisión se puede dar en forma normal disyuntiva . Para hacer esto, considere todas las hojas de esta clasificación y sus rutas al nodo raíz. Para cada uno de estos caminos, todas las condiciones de los nodos de decisión a lo largo del camino se establecen en conjunto entre sí y los términos resultantes se establecen en disyunción . Para el ejemplo que se muestra arriba, la siguiente declaración resulta para la clasificación "manzano da fruto" (sí):

ventajas

Interpretabilidad y comprensibilidad

Una gran ventaja de los árboles de decisión es que son fáciles de explicar y comprender. Esto permite al usuario evaluar el resultado y reconocer atributos clave. Esto es particularmente útil cuando las propiedades básicas de los datos no se conocen de antemano. Por lo tanto, la inducción de árboles de decisión también es una técnica importante en la minería de datos .

Los árboles de decisión pueden generar reglas comprensibles. Hacen una clasificación sin mucho cálculo. Puede manejar variables continuas y categóricas. Dan una indicación clara de qué campos son más importantes para la predicción o clasificación.

Sin embargo, si aumentar o está embolsado utilizado, la decisión de árboles modelos también son difíciles de entender.

desventaja

Calidad de clasificación en espacios de datos de valor real

Una desventaja que se menciona a menudo de los árboles de decisión es la calidad de clasificación relativamente baja en los espacios de datos de valor real cuando los árboles se utilizan para la clasificación automática. Debido a su conjunto discreto de reglas , a los árboles les va un poco peor para la mayoría de los problemas de clasificación del mundo real en comparación con otras técnicas de clasificación, como las redes neuronales artificiales o las máquinas de vectores de soporte . Esto significa que aunque los árboles pueden generar reglas fácilmente comprensibles para las personas, estas reglas comprensibles a menudo no tienen la mejor calidad posible para problemas de clasificación en el mundo real, desde un punto de vista estadístico.

Tamaño de los árboles de decisión y sobreajuste

Otra desventaja es el posible tamaño de los árboles de decisión si no se pueden inducir reglas simples a partir de los datos de entrenamiento. Esto puede tener múltiples efectos negativos: por un lado, un espectador humano pierde rápidamente la descripción general del contexto de las muchas reglas, por otro lado, árboles tan grandes generalmente conducen a una sobreadaptación al conjunto de datos de entrenamiento, de modo que los nuevos conjuntos de datos solo se clasifican automáticamente de forma incorrecta. Por esta razón, se desarrollaron los llamados métodos de poda , que acortan los árboles de decisión a un tamaño razonable. Por ejemplo, puede limitar la profundidad máxima de los árboles o especificar un número mínimo de objetos por nodo.

Procesamiento adicional de los resultados

Los árboles de decisión a menudo solo se utilizan como un paso intermedio hacia una representación más eficiente del conjunto de reglas. Para llegar a las reglas, se generan diferentes árboles de decisión utilizando diferentes métodos. Se extraen las reglas que ocurren con frecuencia. Las optimizaciones se superponen para obtener un conjunto de reglas sólido, general y correcto. El hecho de que las reglas no estén relacionadas entre sí y de que puedan generarse reglas contradictorias tiene un efecto desfavorable en este método.

Tareas de estimación y problemas de clasificación

Los árboles de decisión son menos adecuados para tareas de estimación donde el objetivo es predecir el valor de un atributo continuo. Con muchas clases y un número relativamente pequeño de ejemplos de entrenamiento, los árboles de decisión son propensos a errores en el caso de problemas de clasificación.

Alto esfuerzo computacional

El entrenamiento de un árbol de decisiones puede ser computacionalmente intensivo. El crecimiento de un árbol de decisiones es computacionalmente intensivo. En cada nodo, cada campo de división candidato debe ordenarse antes de poder encontrar la mejor división. En algunos algoritmos se utilizan combinaciones de campos y se deben buscar pesos de combinación óptimos. Los algoritmos de limpieza también pueden ser costosos, ya que muchos subárboles candidatos deben construirse y compararse.

Más desarrollos y ampliaciones

Bosques de decisión

Un método para aumentar la calidad de la clasificación cuando se utilizan árboles de decisión es utilizar conjuntos de árboles de decisión en lugar de árboles individuales. Estas cantidades de árboles de decisión se utilizan como bosques de decisión (en inglés: bosques de decisión ), respectivamente.

El uso de bosques de decisión es una de las llamadas técnicas de conjunto en el aprendizaje automático . La idea de los bosques de decisión es que un solo árbol de decisión no tiene que proporcionar una clasificación óptima, pero la decisión mayoritaria de un conjunto de árboles adecuados puede hacerlo. Los métodos comunes para crear bosques adecuados son el refuerzo , el ensacado y el arco .

La desventaja de los bosques de decisión es que ya no es tan fácil para los humanos interpretar las reglas contenidas en todos los árboles en su totalidad de una manera simple, como sería posible con árboles individuales.

Combinación con redes neuronales

Los árboles de decisión se pueden combinar con redes neuronales . De esta manera, es posible reemplazar las ramas ineficientes del árbol con redes neuronales para lograr una mayor calidad de clasificación que no se puede lograr con los árboles solos. Las ventajas de ambos métodos de clasificación también se pueden utilizar mapeando estructuras parciales en la otra metodología: los árboles no necesitan tantos datos de entrenamiento para la inducción como las redes neuronales. Por otro lado, pueden ser bastante inexactos, especialmente cuando son pequeños. Las redes neuronales, por otro lado, clasifican con mayor precisión, pero requieren más datos de entrenamiento. Por lo tanto, se está intentando utilizar las propiedades de los árboles de decisión para generar partes de redes neuronales mediante el llamado TBNN (Tree-Based Neural Network) traduciendo las reglas de los árboles de decisión en las redes neuronales.

Aplicaciones prácticas

Ejemplo: árbol de decisiones para subir imágenes a Wikipedia

Programas de aplicación

Hay una serie de programas de aplicación que han implementado árboles de decisión, por ejemplo, se ofrecen en los paquetes de software de estadísticas GNU R , Scikit-learn ( XGBoost ), SPSS y SAS . Los dos últimos paquetes, como la mayoría de los otros paquetes de software de minería de datos, utilizan el algoritmo CHAID .

Ejemplo: clasificación de clientes

Un banco quiere vender un nuevo servicio con una campaña de correo directo . Para aumentar las posibilidades de éxito, la campaña solo debe dirigirse a los hogares que corresponden a una combinación de variables demográficas que un árbol de decisiones correspondiente ha declarado que es óptima. Este proceso se denomina segmentación de datos o modelado de segmentación .

Ver también

literatura

  • Leo Breiman, Jerome H. Friedman, Richard A. Olshen, Charles J. Stone: árboles de clasificación y regresión , Wadsworth International Group, Belmont CA, 1984, ISBN 0-412-04841-8
  • Tom M. Mitchell: Aprendizaje automático , McGraw-Hill, Boston, EE. UU., 1997, ISBN 0-07-115467-1
  • Jiawei Han, Micheline Kamber: Minería de datos , editores de Morgan Kaufmann, San Francisco CA, 2006 (segunda edición), ISBN 978-1558609013
  • Peter Dörsam: teoría de la decisión claramente presentada , Pd-Verlag, Heidenau, 2007 (5.a edición), ISBN 978-3867073059
  • Günter Bamberg, Adolf G. Coenenberg , Michael Krapp: Toma de decisiones comerciales , Verlag Franz Vahlen, Munich, 2008 (14a edición), ISBN 978-3-8006-3506-1

enlaces web

Commons : Diagramas de decisión  : colección de imágenes, videos y archivos de audio

Evidencia individual

  1. ^ SÍ Sonquist, JN Morgan: La detección de efectos de interacción , Centro de investigación de encuestas, Instituto de investigación social, Universidad de Michigan, Ann Arbor.
  2. ↑ JR Quinlan: Inducción de árboles de decisión , aprendizaje automático, 1 (1): 81-106, 1986
  3. ↑ Xindong Wu, Vipin Kumar, J. Ross Quinlan, Joydeep Ghosh, Qiang Yang, Hiroshi Motoda, Geoffrey J. McLachlan, Angus Ng, Bing Liu y Philip S. Yu, et al.: Top 10 algoritmos en minería de datos , conocimiento y Information Systems Volumen 14, Número 1 (2008), 1-37
  4. ↑ a b GeeksforGeeks: Árbol de decisiones
  5. ↑ R. King, C.Feng, A.Sutherland: Comparación de algoritmos de clasificación en grandes problemas del mundo real , Inteligencia artificial aplicada, 9 (3): 259-287, mayo / junio de 1995
  6. ↑ O.Gascuel, B. Bouchon-Meunier, G. Caraux, P.Gallinari, A. Guénoche, Y.Guermeur: Doce métodos de clasificación supervisados ​​numéricos, simbólicos e híbridos , International Journal of Pattern Recognition and Artificial Intelligence, 12 (5) : 517-571, 1998
  7. ↑ A. Flöter: Análisis de datos de expresión biológica basados ​​en la inducción del árbol de decisión , disertación, Universidad de Potsdam, 2006
  8. ↑ M. Murata, Q. Ma, H. Isahara: Comparación de tres métodos de aprendizaje automático para el etiquetado de parte del discurso tailandés , Transacción ACM sobre procesamiento de información en idiomas asiáticos, 1 (2): 145-158, junio de 2002
  9. ↑ Y.Freund: Impulsar un algoritmo de aprendizaje débil por mayoría , Información y Computación, 121 (2): 256-285, 1995
  10. ↑ W.Tong, Q.Xie, H.Hong, H.Fang, L.Shi, R.Perkins, EFPetricoin: Uso de bosques de decisión para clasificar muestras de cáncer de próstata sobre la base de datos raros de ms: Evaluación de correlación y predicción de probabilidades confianza , Environmental Health Perspectives , 112 (16): 1622-1627, 2004
  11. ↑ E.Bauer, R.Kohavi: Una comparación empírica de algoritmos de clasificación de votación: Bagging, Boosting y variantes , Machine Learning, 36 (1-2): 105-139, 1998
  12. ↑ RESchapire: Una breve introducción al impulso , Sociedad Japonesa de Inteligencia Artificial, 14 (5): 771-780, 1999
  13. ↑ L.Breiman: Predictores de embolsado , Aprendizaje automático, 24 (2): 123-140, 1996
  14. ↑ R. Nock: Inducción de clasificadores de votación interpretables sin precisión comercial por simplicidad: resultados teóricos, algoritmos de aproximación y experimentos , Journal of Artificial Intelligence Research, 17: 137-170, agosto de 2002
  15. ^ AK Seewald, J. Petrak, G. Widmer: aprendices de árboles de decisión híbridos con clasificadores de hojas alternativos , Actas de la 14a conferencia internacional FLAIRS, AAAI Press, Menlo Park CA, 2000
  16. ↑ Árboles de decisión: documentación de scikit-learn. Consultado el 24 de agosto de 2018 .