Árboles de decisión: ¿Cómo optimizar mi proceso de toma de decisiones?

Imaginemos que estás jugando un juego de Veinte Preguntas. Tu oponente ha elegido secretamente un tema, y ​​debes descubrir qué eligió. En cada turno, puedes hacer una pregunta de sí o no, y tu oponente debe responder con sinceridad. ¿Cómo descubrir el secreto en la menor cantidad de preguntas?

Debería ser obvio que algunas preguntas son mejores que otras. Por ejemplo, preguntar "¿Puede volar?", Ya que es probable que su primera pregunta no sea fructífera, mientras que preguntar "¿Está vivo?" Es un poco más útil. Intuitivamente, desea que cada pregunta reduzca significativamente el espacio de posibles secretos, lo que finalmente conduce a su respuesta.

Esa es la idea básica detrás de los árboles de decisión. En cada punto, considera un conjunto de preguntas que pueden dividir su conjunto de datos. Usted elige la pregunta que proporciona la mejor división y nuevamente encuentra las mejores preguntas para las particiones. Te detienes una vez que todos los puntos que estás considerando son de la misma clase. Entonces la tarea de clasificación es fácil. Simplemente puedes agarrar un punto y tirarlo por el árbol. Las preguntas lo guiarán a su clase apropiada.

Términos importantes

El árbol de decisión es un tipo de algoritmo de aprendizaje supervisado que se puede usar tanto en problemas de regresión como de clasificación. Funciona para variables de entrada y salida categóricas y continuas.

Identifiquemos terminologías importantes en el Árbol de decisión, mirando la imagen de arriba:

  • El nodo raíz representa a toda la población o muestra. Además se divide en 2 o más conjuntos homogéneos.
  • La división es un proceso de dividir un nodo en 2 o más subnodos.
  • Cuando un subnodo se divide en subnodos adicionales, se llama un nodo de decisión.
  • Los nodos que no se dividen se llaman un nodo terminal o una hoja.
  • Cuando elimina subnodos de un nodo de decisión, este proceso se denomina poda. Lo contrario de la poda es la división.
  • Una subsección de un árbol completo se llama rama.
  • Un nodo, que se divide en subnodos se llama un nodo principal de los subnodos; mientras que los subnodos se denominan secundarios del nodo primario.

Cómo funciona

Aquí solo hablo del árbol de clasificación, que se usa para predecir una respuesta cualitativa. El árbol de regresión es el que se usa para predecir valores cuantitativos.

En un árbol de clasificación, predecimos que cada observación pertenece a la clase más común de observaciones de entrenamiento en la región a la que pertenece. Al interpretar los resultados de un árbol de clasificación, a menudo estamos interesados ​​no solo en la predicción de clase correspondiente a una región de nodo terminal particular, sino también en las proporciones de clase entre las observaciones de entrenamiento que caen en esa región. La tarea de hacer crecer un árbol de clasificación depende del uso de uno de estos 3 métodos como criterio para hacer las divisiones binarias:

1 - Tasa de error de clasificación: podemos definir la "tasa de aciertos" como la fracción de las observaciones de entrenamiento en una región en particular que no pertenece a la clase más extendida. El error viene dado por esta ecuación:

E = 1 - argmax_ {c} (π̂ mc)

en el que π̂ mc representa la fracción de datos de entrenamiento en la región R_m que pertenecen a la clase c.

2 - Índice de Gini: El Índice de Gini es una métrica de error alternativa que está diseñada para mostrar cuán "pura" es una región. "Pureza" en este caso significa la cantidad de datos de entrenamiento en una región particular que pertenece a una sola clase. Si una región R_m contiene datos que provienen principalmente de una sola clase c, entonces el valor del índice de Gini será pequeño:

3 - Entropía cruzada: una tercera alternativa, que es similar al índice de Gini, se conoce como entropía cruzada o desviación:

La entropía cruzada tomará un valor cercano a cero si los π̂ mc están todos cerca de 0 o cerca de 1. Por lo tanto, al igual que el índice de Gini, la entropía cruzada tomará un valor pequeño si el m-ésimo nodo es puro. De hecho, resulta que el índice de Gini y la entropía cruzada son numéricamente bastante similares.

Cuando se construye un árbol de clasificación, el índice de Gini o la entropía cruzada generalmente se usan para evaluar la calidad de una división en particular, ya que son más sensibles a la pureza del nodo que la tasa de error de clasificación. Cualquiera de estos 3 enfoques podría usarse al podar el árbol, pero la tasa de error de clasificación es preferible si el objetivo es la precisión de la predicción del árbol podado final.

Implementación desde cero

Veamos el algoritmo de creación de árboles de decisión, con todos sus detalles. Para construir un árbol de decisión, necesitamos tomar una decisión inicial sobre el conjunto de datos para dictar qué función se usa para dividir los datos. Para determinar esto, debemos probar cada función y medir qué división nos dará los mejores resultados. Después de eso, dividiremos el conjunto de datos en subconjuntos. Los subconjuntos atravesarán las ramas del primer nodo de decisión. Si los datos en las ramas son de la misma clase, los hemos clasificado correctamente y no necesitamos continuar dividiéndolos. Si los datos no son los mismos, entonces debemos repetir el proceso de división en este subconjunto. La decisión sobre cómo dividir este subconjunto se realiza de la misma manera que el conjunto de datos original, y repetimos este proceso hasta que hayamos clasificado todos los datos.

¿Cómo dividimos nuestro conjunto de datos? Una forma de organizar este desorden es medir la información. Usando la teoría de la información, podemos medir la información antes y después de la división. El cambio en la información antes y después de la división se conoce como ganancia de información. Cuando sabemos cómo calcular la ganancia de información, podemos dividir nuestros datos en cada función para ver qué división nos da la mayor ganancia de información. La división con la mayor ganancia de información es nuestra mejor opción.

Para calcular la ganancia de información, podemos usar la Entropía de Shannon, que es el valor esperado de toda la información de todos los valores posibles de nuestra clase. Veamos el código de Python para ello:

Como puede ver, primero calculamos un recuento del número de instancias en el conjunto de datos. Luego creamos un diccionario cuyas claves son los valores en la columna final. Si no se encontró una clave anteriormente, se crea una. Para cada tecla, hacemos un seguimiento de cuántas veces se produce esta etiqueta. Finalmente, usamos la frecuencia de todas las diferentes etiquetas para calcular la probabilidad de esa etiqueta. Esta probabilidad se usa para calcular la entropía de Shannon, y sumamos esto para todas las etiquetas.

Después de encontrar una manera de medir la entropía del conjunto de datos, necesitamos dividir el conjunto de datos, medir la entropía en los conjuntos divididos y ver si dividirlo fue lo correcto. Aquí está el código para hacerlo:

Este código requiere 3 entradas: los datos a dividir, la función a dividir y el valor de la función a devolver. Creamos una nueva lista al principio cada vez porque llamaremos a esta función varias veces en el mismo conjunto de datos y no queremos que se modifique el conjunto de datos original. Nuestro conjunto de datos es una lista de listas; a medida que iteramos sobre cada elemento de la lista y si contiene el valor que estamos buscando, lo agregaremos a nuestra lista recién creada. Dentro de la declaración if, eliminamos la función en la que nos dividimos.

Ahora, combinaremos 2 funciones: ShannonEntropy y splitDataset para recorrer el conjunto de datos y decidimos qué función es la mejor para dividir.

Examinemos rápidamente el código:

  • Calculamos la entropía de Shannon de todo el conjunto de datos antes de que se produzca cualquier división y asignamos el valor a la variable baseEntropía.
  • El primero de los bucles de bucle sobre todas las características de nuestros datos. Utilizamos las comprensiones de listas para crear una lista (featList) de todas las entradas i-ésima de los datos o todos los valores posibles presentes en los datos.
  • A continuación, creamos un nuevo conjunto de una lista para obtener los valores únicos (uniqueVals).
  • Luego, revisamos todos los valores únicos de esta característica y dividimos los datos para cada característica (subData). La nueva entropía se calcula (newEntropy) y se resume para todos los valores únicos de esa característica. La ganancia de información (infoGain) es la reducción de la entropía (baseEntropy - newEntropy).
  • Finalmente, comparamos la ganancia de información entre todas las características y devolvemos el índice de la mejor característica para dividir (bestFeature).

Ahora que podemos medir qué tan organizado está un conjunto de datos y podemos dividir los datos, es hora de poner todo esto junto y construir el árbol de decisión. Desde un conjunto de datos, lo dividimos en función del mejor atributo para dividir. Una vez divididos, los datos atravesarán las ramas del árbol a otro nodo. Este nodo dividirá los datos nuevamente. Vamos a usar la recursividad para manejar esto.

Solo nos detendremos en las siguientes condiciones: (1) Quedarse sin atributos en los que dividir o (2) todas las instancias en una rama son de la misma clase. Si todas las instancias tienen la misma clase, crearemos un nodo hoja. Cualquier dato que llegue a este nodo hoja se considera que pertenece a la clase de ese nodo hoja.

Aquí está el código para construir nuestros árboles de decisión:

Nuestro código toma 2 entradas: los datos y una lista de etiquetas:

  • Primero creamos una lista de todas las etiquetas de clase en el conjunto de datos y llamamos a esta classList. La primera condición de detención es que si todas las etiquetas de clase son iguales, entonces devolvemos esta etiqueta. La segunda condición de detención es el caso cuando no hay más funciones para dividir. Si no cumplimos con las condiciones de detención, entonces usamos la función chooseBestFeatureToSplit para elegir la mejor función.
  • Para crear el árbol, lo almacenaremos en un diccionario (myTree). Luego obtenemos todos los valores únicos del conjunto de datos para nuestra función elegida (bestFeat). El código de valor único usa conjuntos (uniqueVals).
  • Finalmente, iteramos sobre todos los valores únicos de nuestra característica elegida y llamamos recursivamente createTree () para cada división del conjunto de datos. Este valor se inserta en el diccionario myTree, por lo que terminamos con muchos diccionarios anidados que representan nuestro árbol.

Implementación a través de Scikit-Learn

Ahora que sabemos cómo implementar el algoritmo desde cero, usemos scikit-learn. En particular, usaremos la clase DecisionTreeClassifier. Trabajando con el conjunto de datos de iris, primero importamos los datos y los dividimos en una parte de entrenamiento y prueba. Luego construimos un modelo usando la configuración predeterminada de desarrollar completamente el árbol (cultivar el árbol hasta que todas las hojas sean puras). Arreglamos random_state en el árbol, que se usa para romper el lazo internamente:

La ejecución del modelo debería darnos una precisión del conjunto de prueba del 95%, lo que significa que el modelo predijo la clase correctamente para el 95% de las muestras en el conjunto de datos de prueba.

Fortalezas y debilidades

La principal ventaja de usar árboles de decisión es que son intuitivamente muy fáciles de explicar. Reflejan de cerca la toma de decisiones humanas en comparación con otros enfoques de regresión y clasificación. Se pueden mostrar gráficamente y pueden manejar fácilmente predictores cualitativos sin la necesidad de crear variables ficticias.

Otra gran ventaja es que los algoritmos son completamente invariables para el escalado de los datos. Como cada función se procesa por separado y las posibles divisiones de los datos no dependen del escalado, no se necesita un procesamiento previo como la normalización o la estandarización de las funciones para los algoritmos del árbol de decisiones. En particular, los árboles de decisión funcionan bien cuando tenemos características que están en escalas completamente diferentes, o una combinación de características binarias y continuas.

Sin embargo, los árboles de decisión generalmente no tienen el mismo nivel de precisión predictiva que otros enfoques, ya que no son bastante robustos. Un pequeño cambio en los datos puede causar un gran cambio en el árbol estimado final. Incluso con el uso de la poda previa, tienden a sobreajustar y proporcionan un bajo rendimiento de generalización. Por lo tanto, en la mayoría de las aplicaciones, al agregar muchos árboles de decisión, utilizando métodos como embolsado, bosques aleatorios e impulso, el rendimiento predictivo de los árboles de decisión se puede mejorar sustancialmente.

Fuentes de referencia:

  • Introducción al aprendizaje estadístico por Gareth James, Daniela Witten, Trevor Hastie y Robert Tibshirani (2014)
  • Aprendizaje automático en acción por Peter Harrington (2012)
  • Introducción al aprendizaje automático con Python por Sarah Guido y Andreas Muller (2016)

- -

Si disfrutaste esta pieza, me encantaría si presionas el botón de aplaudir para que otros puedan tropezar con ella. Puede encontrar mi propio código en GitHub y más de mis escritos y proyectos en https://jameskle.com/. También puedes seguirme en Twitter, enviarme un correo electrónico directamente o encontrarme en LinkedIn.