Los árboles de decisiones construyen modelos de clasificación o de regresión con una estructura en forma de árbol. Descompone un dataset en conjuntos cada vez más pequeños, al tiempo que construye un árbol de decisiones cada vez más desarrollado. El resultado final es un árbol con nodos de decisión y nodos hoja. Un nodo de decisión (ej. pronóstico/outlook) tiene dos o más hojas (ej. Soleado, Nublado, Lluvioso). Un nodo hoja (ej. Jugar) representa la clasificación de una decisión. El primer nodo superior de un árbol corresponde la mejor predicción llamada nodo raiz. Los árboles de decisiones soportan tanto datos numéricos como categóricos.
Algoritmo
El algoritmo base para construir arboles de decisión se llama ID3 creado por J.R.Quinlan, y emplea una busqueda ambiciosa descendente por todas las ramas posibles del árbol sin retroceder. El algoritmo ID3 utiliza la Ganancia de Entropía e Información para construr el árbol de decisiones.
En el modelo ZeroR no hay predictores, en el modelo UnR intentamos encontrar el mejor predictor de todos, con Bayes Básico incluimos todos los predictores utilizando la regla de Bayes y las suposiciones independientes entre los predictores, pero con el árbol de decisiones incluimos a todos los predictores con la suposicion de dependencia entre ellos.
Entropia
Un arbol de decision se construye desde arriba con un nodo raíz, y requiere particionar los datos en subconjuntos que contienen instancias de valores similares (homogeneos). El algoritmo ID3 utiliza la entropía para calcularla homogeneidad de un sampleo. Si el conjunto sampleado es completamente homogeneo la entrooía es cero (0) y si el conjunto esta dividido por partes iguales la entropía es de uno (1).
Para construir un árbol de decisiones necesitamos calcular dos tipos de entropias utilizando tablas de frecuencia de la siguiente manera:
a) Entropia utilizando la tabla de frecuencias de un atributo:
b) Entropia utilizando la tabla de frecuencias de dos atributos.
Ganancia de Información
La ganancia de información se basa en el grado de entropía despues de que se separa un dataset a partir de un atributo. Construir un árbol de decisiones se trata de encontrar el atributo que devuelve la mayor ganancia de información (ej. el que tiene más ramas homogeneas)
Paso 1: Calcular la entropía del target.
Paso 2: Se divide el dataset en los diferentes atributos. Se calcula la entropía para cada rama, luego se sumariza proporcionalmente, para conseguir la entropía total de la división. La entropía resultante se resta de la entropía previa a la división. El resultado es la Ganancia de Información, o la disminución de la entropía.
Paso 3: Seleccionar el atributo que posee la mayor Ganancia de Información como el nodo de decisiones, dividimos el dataset según sus ramas y repetimos el mismo proceso para cada rama.
Paso 4a: Una rama con una entropía de 0 es un nodo hoja.
Paso 4b: Una rama con una entropía mayor a 1 necesita seguir dividiéndose, asi que es una rama.
Paso 5: El algoritmo ID3 corre recursivamente en todas las ramas que no son hojas todavía, hasta conseguir clasificar todos los datos.
De Árbol de decisiones a Reglas de decisión
Un arbol de decisiones se puede transformar facilmente en un conjunto de reglas. Solo es necesario mapear el nodo raiz hasta cada uno de los nodos hojas.
Árboles de decisiones – Problemas
- Trabajar con atributos continuos (Discretizar)
- Evitar el Overfitting
- Super Atributos (Atributos con muchos valores únicos)
- Trabajar con Valores faltantes