Árbol de decisión

Tradicionalmente, se han creado árboles de decisión manualmente.

Un árbol de decisiones es un modelo jerárquico de soporte de decisiones que utiliza un modelo de árbol de decisiones y sus posibles consecuencias, incluidos los resultados de eventos fortuitos, los costos de los recursos y la utilidad. Es una forma de mostrar un algoritmo que solo contiene declaraciones de control condicionales.

Los árboles de decisión se usan comúnmente en la investigación de operaciones, específicamente en el análisis de decisiones, para ayudar a identificar una estrategia con más probabilidades de alcanzar un objetivo, pero también son una herramienta popular en el aprendizaje automático.

Resumen

Un árbol de decisiones es una estructura similar a un diagrama de flujo en el que cada nodo interno representa una "prueba" en un atributo (por ejemplo, si al lanzar una moneda sale cara o cruz), cada rama representa el resultado de la prueba y cada nodo hoja representa una etiqueta de clase (decisión tomada después de calcular todos los atributos). Los caminos desde la raíz hasta la hoja representan reglas de clasificación.

En el análisis de decisiones, se utiliza un árbol de decisiones y el diagrama de influencia estrechamente relacionado como una herramienta visual y analítica de apoyo a las decisiones, donde se calculan los valores esperados (o la utilidad esperada) de las alternativas en competencia.

Un árbol de decisión consta de tres tipos de nodos:

1. Nodos de decisión – típicamente representados por cuadrados
2. Nodos de oportunidad – típicamente representados por círculos
3. Nodos finales – típicamente representados por triángulos

Los árboles de decisión se utilizan comúnmente en la investigación y gestión de operaciones. Si, en la práctica, las decisiones tienen que tomarse en línea sin recuerdo bajo conocimiento incompleto, un árbol de decisión debe ir acompañado de un modelo de probabilidad como modelo de mejor elección o algoritmo de modelo de selección en línea. Otro uso de los árboles de decisión es como medio descriptivo para calcular probabilidades condicionales.

Los árboles de decisión, los diagramas de influencia, las funciones de utilidad y otras herramientas y métodos de análisis de decisiones se enseñan a estudiantes universitarios en escuelas de negocios, economía de la salud y salud pública, y son ejemplos de métodos de investigación de operaciones o ciencia administrativa.

Bloques de construcción del árbol de decisiones

Elementos del árbol de decisiones

Dibujado de izquierda a derecha, un árbol de decisión solo tiene nodos de ráfaga (trayectos de división) pero no nodos de sumidero (trayectos de convergencia). Por lo tanto, si se usan manualmente, pueden crecer mucho y, a menudo, son difíciles de dibujar completamente a mano. Tradicionalmente, los árboles de decisión se han creado manualmente, como muestra el ejemplo aparte, aunque cada vez se emplea más software especializado.

Reglas de decisión

El árbol de decisión se puede linealizar en reglas de decisión, donde el resultado es el contenido del nodo hoja y las condiciones a lo largo de la ruta forman una conjunción en la cláusula if. En general, las reglas tienen la forma:

si condición1 y condición 2 y condición3 entonces Resultado.

Las reglas de decisión se pueden generar mediante la construcción de reglas de asociación con la variable de destino a la derecha. También pueden denotar relaciones temporales o causales.

Árbol de decisión usando símbolos de diagrama de flujo

Por lo general, un árbol de decisión se dibuja utilizando símbolos de diagrama de flujo, ya que es más fácil de leer y comprender para muchos. Tenga en cuenta que hay un error conceptual en el mensaje "Continuar" cálculo del árbol que se muestra a continuación; el error se relaciona con el cálculo de "costes" otorgado en una acción legal.

Ejemplo de análisis

El análisis puede tener en cuenta la preferencia o la función de utilidad del tomador de decisiones (por ejemplo, la empresa), por ejemplo:

La interpretación básica en esta situación es que la empresa prefiere el riesgo de B y los pagos con coeficientes de preferencia de riesgo realistas (superiores a 400.000 dólares; en ese rango de aversión al riesgo, la empresa necesitaría modelar una tercera estrategia, "Ni A ni B").

Otro ejemplo, comúnmente utilizado en los cursos de investigación operativa, es la distribución de salvavidas en las playas (también conocido como el ejemplo 'La vida es una playa'). El ejemplo describe dos playas con socorristas a distribuir en cada playa. Existe un presupuesto máximo B que se puede distribuir entre las dos playas (en total), y utilizando una tabla de rendimientos marginales, los analistas pueden decidir cuántos socorristas asignar a cada playa.

En este ejemplo, se puede dibujar un árbol de decisión para ilustrar los principios de los rendimientos decrecientes en la playa #1.

Árbol de decisión de playa

El árbol de decisiones ilustra que cuando se distribuyen secuencialmente los salvavidas, sería óptimo colocar un primer salvavidas en la playa n.º 1 si solo hay presupuesto para 1 salvavidas. Pero si hay un presupuesto para dos guardias, colocar ambos en la playa #2 evitaría más ahogamientos en general.

Salvavidas

Diagrama de influencia

Gran parte de la información de un árbol de decisiones se puede representar de forma más compacta como un diagrama de influencia, centrando la atención en los problemas y las relaciones entre los eventos.

El rectángulo de la izquierda representa una decisión, los ovalados representan acciones, y el diamante representa resultados.

Inducción de reglas de asociación

Los árboles de decisión también pueden verse como modelos generativos de reglas de inducción a partir de datos empíricos. Un árbol de decisión óptimo se define entonces como un árbol que da cuenta de la mayoría de los datos, al tiempo que minimiza el número de niveles (o "preguntas"). Se han ideado varios algoritmos para generar dichos árboles óptimos, como ID3/4/5, CLS, ASSISTANT y CART.

Ventajas y desventajas

Entre las herramientas de apoyo a la toma de decisiones, los árboles de decisión (y los diagramas de influencia) tienen varias ventajas. Árboles de decisión:

• Son simples de entender e interpretar. La gente puede entender los modelos de árboles de decisión después de una breve explicación.
• Tener valor incluso con poco datos duros. Se pueden generar ideas importantes basadas en expertos que describen una situación (sus alternativas, probabilidades y costos) y sus preferencias por los resultados.
• Ayuda a determinar valores peores, mejores y esperados para diferentes escenarios.
• Usa un modelo de caja blanca. Si un resultado dado es proporcionado por un modelo.
• Puede combinarse con otras técnicas de decisión.
• Se puede considerar la adopción de medidas por más de una decisión.

Desventajas de los árboles de decisión:

• Son inestables, lo que significa que un pequeño cambio en los datos puede llevar a un gran cambio en la estructura del árbol de decisión óptimo.
• A menudo son relativamente inexactos. Muchos otros predictores cumplen mejor con datos similares. Esto se puede remediar reemplazando un único árbol de decisión por un bosque aleatorio de árboles de decisión, pero un bosque aleatorio no es tan fácil de interpretar como un único árbol de decisiones.
• Para los datos que incluyen variables categóricas con diferentes números de niveles, la ganancia de información en los árboles de decisión sesgada a favor de esos atributos con más niveles.
• Las cálculos pueden llegar a ser muy complejas, especialmente si muchos valores son inciertos y/o si muchos resultados están vinculados.

Optimización de un árbol de decisión

Deben tenerse en cuenta algunas cosas al mejorar la precisión del clasificador del árbol de decisión. Las siguientes son algunas posibles optimizaciones que se deben considerar al buscar asegurarse de que el modelo de árbol de decisión producido tome la decisión o clasificación correcta. Tenga en cuenta que estas cosas no son las únicas cosas a considerar, sino solo algunas.

Aumentando el número de niveles del árbol

La precisión del árbol de decisión puede cambiar según la profundidad del árbol de decisión. En muchos casos, las hojas del árbol son nudos puros. Cuando un nodo es puro, significa que todos los datos de ese nodo pertenecen a una sola clase. Por ejemplo, si las clases en el conjunto de datos son Cancer y Non-Cancer, un nodo de hoja se consideraría puro cuando todos los datos de muestra en un nodo de hoja forman parte de una sola clase, ya sea cancerosa o no cancerosa. Es importante tener en cuenta que un árbol más profundo no siempre es mejor cuando se optimiza el árbol de decisión. Un árbol más profundo puede influir negativamente en el tiempo de ejecución. Si se utiliza un cierto algoritmo de clasificación, un árbol más profundo podría significar que el tiempo de ejecución de este algoritmo de clasificación es significativamente más lento. También existe la posibilidad de que el algoritmo real que construye el árbol de decisiones se vuelva significativamente más lento a medida que el árbol se vuelve más profundo. Si el algoritmo de creación de árboles que se utiliza divide los nodos puros, se podría experimentar una disminución en la precisión general del clasificador de árboles. Ocasionalmente, profundizar en el árbol puede provocar una disminución de la precisión en general, por lo que es muy importante probar modificando la profundidad del árbol de decisión y seleccionando la profundidad que produce los mejores resultados. Para resumir, observe los puntos a continuación, definiremos el número D como la profundidad del árbol.

Posibles ventajas de aumentar el número D:

• Aumenta la exactitud del modelo de clasificación de los árboles de decisión.

Posibles desventajas de aumentar D

• Cuestiones de horario de ejecución
• Disminución de la precisión en general
• Las divisiones puras del nodo mientras se profundizan pueden causar problemas.

La capacidad de probar las diferencias en los resultados de clasificación al cambiar D es imprescindible. Debemos ser capaces de cambiar y probar fácilmente las variables que podrían afectar la precisión y confiabilidad del modelo de árbol de decisión.

La elección de las funciones de división de nodos

La función de división de nodos utilizada puede tener un impacto en la mejora de la precisión del árbol de decisión. Por ejemplo, el uso de la función de obtención de información puede generar mejores resultados que el uso de la función phi. La función phi se conoce como una medida de la "bondad" de un candidato dividido en un nodo del árbol de decisión. La función de ganancia de información se conoce como una medida de la "reducción de la entropía". A continuación, construiremos dos árboles de decisión. Se construirá un árbol de decisión usando la función phi para dividir los nodos y se construirá un árbol de decisión usando la función de ganancia de información para dividir los nodos.

Las principales ventajas y desventajas de la ganancia de información y la función phi

• Un importante inconveniente de la ganancia de información es que la característica que se elige como el próximo nodo en el árbol tiende a tener valores más únicos.
• Una ventaja de la ganancia de información es que tiende a elegir las características más impactantes que están cerca de la raíz del árbol. Es una medida muy buena para decidir la relevancia de algunas características.
• La función phi es también una buena medida para decidir la relevancia de algunas características basadas en "la bondad".

Esta es la fórmula de la función de ganancia de información. La fórmula establece que la ganancia de información es una función de la entropía de un nodo del árbol de decisión menos la entropía de una división candidata en el nodo t de un árbol de decisión.

Igains()s)=H()t)− − H()s,t){displaystyle Igains(s)=H(t)-H(s,t)}

Esta es la fórmula de la función phi. La función phi se maximiza cuando la característica elegida divide las muestras de una manera que produce divisiones homogéneas y tiene aproximadamente el mismo número de muestras en cada división.

CCPR CCPR ()s,t)=()2Alternativa Alternativa PLAlternativa Alternativa PR)Alternativa Alternativa Q()sSilenciot){displaystyle Phi (s,t)=(2*P_{L}*P_{R})*Q(s sometidat)}

Estableceremos D, que es la profundidad del árbol de decisiones que estamos construyendo, en tres (D = 3). También tenemos el siguiente conjunto de datos de muestras cancerosas y no cancerosas y las características de mutación que las muestras tienen o no. Si una muestra tiene una mutación característica, entonces la muestra es positiva para esa mutación y estará representada por uno. Si una muestra no tiene una mutación característica, entonces la muestra es negativa para esa mutación y estará representada por cero.

Para resumir, C significa cáncer y NC significa no cáncer. La letra M significa mutación, y si una muestra tiene una mutación particular, aparecerá en la tabla como uno y, de lo contrario, como cero.

Ahora, podemos usar las fórmulas para calcular los valores de la función phi y los valores de ganancia de información para cada M en el conjunto de datos. Una vez que se calculan todos los valores, se puede producir el árbol. Lo primero que hay que hacer es seleccionar el nodo raíz. En la ganancia de información y la función phi, consideramos que la división óptima es la mutación que produce el valor más alto para la ganancia de información o la función phi. Ahora suponga que M1 tiene el valor de función phi más alto y M4 tiene el valor de ganancia de información más alto. La mutación M1 será la raíz de nuestro árbol de función phi y M4 será la raíz de nuestro árbol de ganancia de información. Puede observar los nodos raíz a continuación.

Ahora, una vez que hayamos elegido el nodo raíz, podemos dividir las muestras en dos grupos según si una muestra es positiva o negativa para la mutación del nodo raíz. Los grupos se llamarán grupo A y grupo B. Por ejemplo, si usamos M1 para dividir las muestras en el nodo raíz, obtenemos las muestras NC2 y C2 en el grupo A y el resto de las muestras NC4, NC3, NC1, C1 en el grupo. B.

Sin tener en cuenta la mutación elegida para el nodo raíz, proceda a colocar las siguientes mejores características que tengan los valores más altos para la ganancia de información o la función phi en los nodos secundarios izquierdo o derecho del árbol de decisión. Una vez que elegimos el nodo raíz y los dos nodos secundarios para el árbol de profundidad = 3, solo podemos agregar las hojas. Las hojas representarán la decisión de clasificación final que ha producido el modelo en función de las mutaciones que tiene o no tiene una muestra. El árbol de la izquierda es el árbol de decisión que obtenemos al usar la ganancia de información para dividir los nodos y el árbol de la derecha es lo que obtenemos al usar la función phi para dividir los nodos.

Ahora suponga que los resultados de la clasificación de ambos árboles se dan usando una matriz de confusión.

Matriz de confusión de ganancia de información:

Matriz de confusión de la función Phi:

El árbol que usa la ganancia de información tiene los mismos resultados cuando se usa la función phi al calcular la precisión. Cuando clasificamos las muestras según el modelo utilizando la ganancia de información, obtenemos un verdadero positivo, un falso positivo, cero falsos negativos y cuatro verdaderos negativos. Para el modelo que utiliza la función phi, obtenemos dos verdaderos positivos, cero falsos positivos, un falso negativo y tres verdaderos negativos. El siguiente paso es evaluar la efectividad del árbol de decisión utilizando algunas métricas clave que se discutirán en la sección de evaluación de un árbol de decisión a continuación. Las métricas que se discutirán a continuación pueden ayudar a determinar los próximos pasos a seguir al optimizar el árbol de decisión.

Otras técnicas

La información anterior no es donde termina para construir y optimizar un árbol de decisión. Hay muchas técnicas para mejorar los modelos de clasificación de árboles de decisión que construimos. Una de las técnicas es hacer nuestro modelo de árbol de decisiones a partir de un conjunto de datos de arranque. El conjunto de datos de arranque ayuda a eliminar el sesgo que se produce al crear un modelo de árbol de decisiones con los mismos datos con los que se prueba el modelo. La capacidad de aprovechar el poder de los bosques aleatorios también puede ayudar a mejorar significativamente la precisión general del modelo que se está construyendo. Este método genera muchas decisiones de muchos árboles de decisión y suma los votos de cada árbol de decisión para hacer la clasificación final. Hay muchas técnicas, pero el objetivo principal es probar la construcción de su modelo de árbol de decisiones de diferentes maneras para asegurarse de que alcanza el nivel de rendimiento más alto posible.

Evaluación de un árbol de decisiones

Es importante conocer las medidas que se utilizan para evaluar los árboles de decisión. Las principales métricas utilizadas son la precisión, la sensibilidad, la especificidad, la precisión, la tasa de errores, la tasa de descubrimientos falsos y la tasa de omisiones falsas. Todas estas medidas se derivan del número de verdaderos positivos, falsos positivos, verdaderos negativos y falsos negativos obtenidos al analizar un conjunto de muestras a través del modelo de clasificación del árbol de decisión. Además, se puede hacer una matriz de confusión para mostrar estos resultados. Todas estas métricas principales dicen algo diferente sobre las fortalezas y debilidades del modelo de clasificación construido en base a su árbol de decisiones. Por ejemplo, una sensibilidad baja con una especificidad alta podría indicar que el modelo de clasificación creado a partir del árbol de decisiones no identifica bien las muestras cancerosas sobre las muestras no cancerosas.

Tomemos la siguiente matriz de confusión. La matriz de confusión nos muestra que el clasificador del modelo de árbol de decisión construido dio 11 verdaderos positivos, 1 falso positivo, 45 falsos negativos y 105 verdaderos negativos.

Ahora calcularemos los valores de precisión, sensibilidad, especificidad, precisión, tasa de errores, tasa de descubrimientos falsos y tasa de omisiones falsas.

Precisión:

AccuracSí.=()TP+TN)/()TP+TN+FP+FN){displaystyle Accuracy=(TP+TN)/(TP+TN+FP+FN)}

()11+104).. 162=71.60% % {displaystyle (11+104)div 162=71,60%}

Sensibilidad (TPR – verdadero estado positivo):

TPR=TP/()TP+FN){displaystyle TPR=TP/(TP+FN)}

()11).. ()11+45)=19.64% % {displaystyle (11)div (11+45)=19.64%}

Especificidad (TNR – tasa de verdaderos negativos):

TNR=TN/()TN+FP){displaystyle TNR=TN/(TN+FP)}

105.. ()105+1)=99.06% % {displaystyle 105div (105+1)=99.06%}

Precisión (PPV – valor predictivo positivo):

PPV=TP/()TP+FP){displaystyle PPV=TP/(TP+FP)}

11/()11+1)=91.66% % {displaystyle 11/(11+1)=91.66%}

Tasa de fallas (FNR – tasa de falsos negativos):

FNR=FN/()FN+TP){displaystyle FNR=FN/(FN+TP)}

45.. ()45+11)=80.35% % {displaystyle 45div (45+11)=80.35%}

Tasa de descubrimiento falso (FDR):

FDR=FP/()FP+TP){displaystyle FDR=FP/(FP+TP)}

1.. ()1+11)=8.30% % {displaystyle 1div (1+11)=8.30%}

Tasa de omisiones falsas (FOR):

FOR=FN/()FN+TN){displaystyle FOR=FN/(FN+TN)}

45.. ()45+105)=30.00% % {displaystyle 45div (45+105)=30.00%}

Una vez que hayamos calculado las métricas clave, podemos sacar algunas conclusiones iniciales sobre el rendimiento del modelo de árbol de decisión construido. La precisión que calculamos fue del 71,60%. El valor de precisión es bueno para empezar, pero nos gustaría que nuestros modelos fueran lo más precisos posible manteniendo el rendimiento general. El valor de sensibilidad del 19,64 % significa que de todos los que dieron positivo para el cáncer dieron positivo. Si observamos el valor de especificidad del 99,06%, sabemos que de todas las muestras que dieron negativo para el cáncer, en realidad dieron negativo. Cuando se trata de sensibilidad y especificidad, es importante tener un equilibrio entre los dos valores, por lo que si podemos disminuir nuestra especificidad para aumentar la sensibilidad, resultaría beneficioso. Estos son solo algunos ejemplos de cómo usar estos valores y los significados detrás de ellos para evaluar el modelo de árbol de decisiones y mejorar la próxima iteración.