¿Qué es un árbol de decisión?

Como puede ver en el siguiente diagrama, un árbol de decisión comienza con un nodo raíz, que no tiene ninguna rama entrante. Las ramas salientes del nodo raíz luego alimentan los nodos internos, también conocidos como nodos de decisión. En función de las características disponibles, ambos tipos de nodos realizan evaluaciones para formar subconjuntos homogéneos, que se denotan mediante nodos hoja o nodos terminales. Los nodos hoja representan todos los resultados posibles dentro del conjunto de datos.

A modo de ejemplo, imaginemos que estuviera tratando de evaluar si debe o no ir a hacer surf, puede utilizar las siguientes reglas de decisión para hacer una elección:

Este tipo de estructura de diagrama de flujo también crea una representación fácil de digerir de la toma de decisiones, lo que permite a los diferentes grupos de una organización comprender mejor por qué se tomó una decisión.

El aprendizaje de árboles de decisión emplea una estrategia de divide y vencerás realizando una búsqueda codiciosa para identificar los puntos de división óptimos dentro de un árbol. Este proceso de división se repite de forma descendente y recursiva hasta que todos o la mayoría de los registros se hayan clasificado con etiquetas de clase específicas.

El hecho de que todos los puntos de datos se clasifiquen como conjuntos homogéneos depende en gran medida de la complejidad del árbol de decisión. Los árboles más pequeños tienen más facilidad para alcanzar nodos de hojas puras, es decir, puntos de datos en una sola clase. Sin embargo, a medida que un árbol crece en tamaño, se vuelve cada vez más difícil mantener esta pureza y, por lo general, da como resultado que caigan muy pocos datos dentro de un subárbol determinado. Cuando esto ocurre, se conoce como fragmentación de datos y, a menudo, puede conducir a un sobreajuste.

Como resultado, los árboles de decisión tienen preferencia por los árboles pequeños, lo que es coherente con el principio de parsimonia de la Navaja de Occam; es decir, "las entidades no deben multiplicarse más allá de lo necesario". Dicho de otra manera, los árboles de decisión deben agregar complejidad solo si es necesario, ya que la explicación más simple suele ser la mejor. Para reducir la complejidad y evitar el sobreajuste, se suele emplear la poda; se trata de un proceso que elimina las ramas que se dividen en características con poca importancia. A continuación, se puede evaluar el ajuste del modelo mediante el proceso de validación cruzada.

Otra forma en que los árboles de decisión pueden mantener su precisión es formando un conjunto mediante un algoritmo bosque aleatorio; este clasificador predice resultados más precisos, sobre todo cuando los árboles individuales no están correlacionados entre sí.

El algoritmo de Hunt, desarrollado en la década de 1960 para modelar el aprendizaje humano en Psicología, es la base de muchos algoritmos populares de árboles de decisión, como los siguientes:

- ID3: a Ross Quinlan se le atribuye el desarrollo de ID3, que es la abreviatura de "Iterative Dichotomiser 3". Este algoritmo aprovecha la entropía y la ganancia de información como métricas para evaluar las divisiones de los candidatos. Algunas de las investigaciones de Quinlan sobre este algoritmo de 1986 se pueden encontrar aquí.

- C4.5: este algoritmo se considera una iteración posterior de ID3, que también fue desarrollado por Quinlan. Puede utilizar la ganancia de información o los ratios de ganancia para evaluar los puntos de división dentro de los árboles de decisión.

- CART: el término CART es una abreviatura de "árboles de clasificación y regresión" y fue introducido por Leo Breiman. Este algoritmo suele utilizar la impureza de Gini para identificar el atributo ideal para dividir. La impureza de Gini mide la frecuencia con la que se clasifica erróneamente un atributo elegido al azar. Al evaluar utilizando la impureza de Gini, un valor más bajo es más ideal.

Aunque hay múltiples formas de seleccionar el mejor atributo en cada nodo, dos métodos, la ganancia de información y la impureza de Gini, actúan como criterio de división popular para los modelos de árbol de decisión. Ayudan a evaluar la calidad de cada condición de prueba y lo bien que podrá clasificar las muestras en una clase.

Es difícil explicar la ganancia de información sin hablar primero de la entropía. La entropía es un concepto que procede de la teoría de la información y que mide la impureza de los valores de la muestra. Se define con la siguiente fórmula, donde:

• S representa el conjunto de datos en el que se calcula la entropía 
• c representa las clases en conjunto, S
• p(c) representa la proporción de puntos de datos que pertenecen a la clase c respecto del número total de puntos de datos del conjunto, S

Los valores de entropía pueden estar comprendidos entre 0 y 1. Si todas las muestras del conjunto de datos, S, pertenecen a una clase, entonces la entropía será igual a cero. Si la mitad de las muestras se clasifican en una clase y la otra mitad en otra, la entropía alcanzará su máximo en 1. Con el fin de seleccionar la mejor característica para dividir y encontrar el árbol de decisión óptimo, se debe utilizar el atributo con la menor cantidad de entropía.

Ganancia de información representa la diferencia en la entropía antes y después de una división en un atributo dado. El atributo con la mayor ganancia de información producirá la mejor división, ya que está haciendo el mejor trabajo al clasificar los datos de entrenamiento de acuerdo con su clasificación de destino. La ganancia de información generalmente se representa con la siguiente fórmula:

donde

• a representa un atributo específico o una etiqueta de clase
• La entropía (S) es la entropía del conjunto de datos, S
• |Sv|/|S| representa la proporción de los valores en S_v al número de valores en el conjunto de datos, S.

Veamos un ejemplo para consolidar estos conceptos. Imagine que tenemos el siguiente conjunto de datos arbitrario:

Para este conjunto de datos, la entropía es de 0,94. Esto se puede calcular encontrando la proporción de días en los que “Jugar tenis” es “Sí”, que es 9/14, y la proporción de días en los que “Jugar tenis” es “No”, que es 5/14. Entonces, estos valores se pueden conectar a la fórmula de entropía anterior.

Entropía (Tenis) = -(9/14) log2(9/14) – (5/14) log2 (5/14) = 0,94

A continuación, podemos calcular la ganancia de información para cada uno de los atributos individualmente. Por ejemplo, la ganancia de información para el atributo "Humedad" sería la siguiente:

Ganancia (Tenis, Humedad) = (0,94)-(7/14)*(0,985) – (7/14)*(0,592) = 0,151

En resumen,

- 7/14 representa la proporción de valores en los que la humedad es igual a "alta" respecto al número total de valores de humedad. En este caso, el número de valores en los que la humedad es igual a "alta" es el mismo que el número de valores en los que la humedad es igual a "normal".

- 0,985 es la entropía cuando la humedad = “alta”

- 0,59 es la entropía cuando la humedad = “normal”

A continuación, repita el cálculo de la ganancia de información para cada atributo de la tabla anterior y seleccione el atributo con la mayor ganancia de información para que sea el primer punto de división en el árbol de decisión. En este caso, Outlook produce la mayor ganancia de información. Desde ahí, el proceso se repite para cada subárbol.

La impureza de Gini es la probabilidad de clasificar incorrectamente un punto de datos aleatorio del conjunto de datos si se etiquetara en función de la distribución de clases del conjunto de datos. Al igual que la entropía, si se establece, S, es pura (es decir, perteneciente a una clase) entonces, su impureza es cero. Esto se denota mediante la siguiente fórmula:

Aunque los árboles de decisión se pueden utilizar en una variedad de casos de uso, otros algoritmos generalmente superan a los algoritmos de árboles de decisión. Dicho esto, los árboles de decisión son particularmente útiles para las tareas de minería de datos y descubrimiento de conocimiento. A continuación, exploraremos más en profundidad los principales beneficios y desafíos de utilizar árboles de decisión:

• Fácil de interpretar: la lógica booleana y las representaciones visuales de los árboles de decisión facilitan su comprensión y consumo. La naturaleza jerárquica de un árbol de decisión también hace que sea fácil ver qué atributos son los más importantes, lo que no siempre está claro con otros algoritmos, como las redes neuronales.
  
  
• Requiere poca o ninguna preparación de datos: los árboles de decisión tienen una serie de características que los hacen más flexibles que otros clasificadores. Puede manejar varios tipos de datos, es decir, valores discretos o continuos, y los valores continuos se pueden convertir en valores categóricos mediante el uso de umbrales. Además, también puede manejar valores con valores faltantes, lo que puede ser problemático para otros clasificadores, como Naive Bayes.
  
  
• Más flexibles: los árboles de decisión pueden utilizarse tanto para tareas de clasificación como de regresión, lo que los hace más flexibles que otros algoritmos. También es insensible a las relaciones subyacentes entre atributos; esto significa que si dos variables están muy correlacionadas, el algoritmo sólo elegirá una de las características para dividir.

• Propenso al sobreajuste: los árboles de decisión complejos tienden a sobreajustarse y no se generalizan bien a los nuevos datos. Este escenario se puede evitar mediante los procesos de poda previa o posterior a la poda. La poda previa detiene el crecimiento de los árboles cuando no hay datos suficientes, mientras que la poda elimina los subárboles con datos inadecuados tras la construcción del árbol.
  
  
• Estimadores de alta varianza: pequeñas variaciones dentro de los datos pueden producir un árbol de decisión muy diferente. Embolsado, o el promedio de estimaciones, puede ser un método para reducir la varianza de árboles de decisión. Sin embargo, este enfoque es limitado, ya que puede conducir a predictores altamente correlacionados.
  
  
• Más costoso: dado que los árboles de decisión adoptan un enfoque de búsqueda codicioso durante la construcción, su entrenamiento puede resultar más costoso en comparación con otros algoritmos.