Ejemplo de construcción de un árbol de decisión con C4.5

Los datos con los que contamos vienen en la siguiente tabla:

La distribución de datos para el atributo Estado es:

En primer lugar, hay que calcular la entropía del conjunto. Los atributos desconocidos no se tienen en cuenta. En total hay 13 casos, de los cuales 3 son positivos. Obtenemos por tanto:

Ahora se calcula la entropía que tendrían los conjuntos resultantes de la división de datos según este atributo:

El siguiente paso es calcular la ganancia resultante de dividir al subconjunto según el atributo Estado:

Al calcular la información de la división, hay que tener en cuenta una categoría extra para el valor desconocido para el atributo. Se calcula de la siguiente manera:

Para terminar, se calcula la proporción de ganancia:

Para la Humedad se calculan de la misma manera, obteniéndose un 0.0746702 bits de Ganancia y el mismo valor como Proporción de Ganancia.
Para el atributo Viento, la Ganancia es 0.00597760 bits y 0.0060687 bits la Proporción de Ganancia.

Tanto si nos fijamos en la Ganancia como en la Proporción de Ganancia, nos conviene  dividir el conjunto según el atributo Estado. Los 13 casos de los que se conoce su valor de Estado se reparten sin problema, mientras que para el que no se conoce su valor, se reparte entre los conjuntos que tienen Soleado, Nublado y Lluvia con los pesos 4/13, 4/16 y 5/13 respectivamente.

Si tomamos por ejemplo la división del conjunto de datos para el valor Nublado del atributo Estado, los datos tenidos en cuenta son:

La distribución de datos para el atributo Humedad es:

Con estos datos, obtenemos una Ganancia de 0.068 bits y una Proporción de Ganancia de 0.068 bits también para el atributo Humedad.
Para el caso del atributo Viento, la Ganancia es de 0.068 bits y la Proporción de Ganancia igual.
Con estos datos podemos sabemos que la división del conjunto de datos no ofrece ninguna mejora, por lo tanto, colapsamos el árbol a la hoja Sí, que es la que mayor peso tiene. En la siguiente imagen se pueden apreciar todos los pasos dados para la construcción del árbol.

El C4.5 analiza los errores predichos en cada uno de los subárboles y ramas del árbol generado para simplificarlo en caso de que sea necesario. En este ejemplo, el error total predicho se calcula de la siguiente manera:

Ahora se calcula el error total predicho tras simplificar el árbol por la hoja Sí:

El error predicho para el árbol simplificado es menor que el del árbol generado, por lo que el C4.5 poda el árbol en la hoja del Sí.

Principales características y funcionamiento

C4.5 es un algoritmo usado para generar un árbol de decisión. Fue desarrollado por Ross Quinlan en 1993 y es una extensión del algoritmo ID3 desarrollado también por Quinlan previamente. Los árboles de decisión generados con C4.5 se pueden usar para clasificación, por ello es conocido como un clasificador estadístico. Las mejoras que propone C4.5 frente a ID3 son:

• Manejo de los datos perdidos. A la hora de construir el árbol se ignoran los campos perdidos, de manera que solo se tienen en cuenta los registros que tienen valor para ese atributo.

• Posibilidad de trabajar con datos continuos. Para poder trabajar con datos continuos, C4.5 divide los datos en rangos en base a los valores encontrados en el conjunto de entrenamiento.

• Propone soluciones para el sobreaprendizaje, pudiendo usar pre-poda (se decide cuando dejar de subdividir el árbol) y post-poda (se construye el árbol y después se poda).

Características del algoritmo C4.5

Las principales características del algoritmo son las siguientes:

• Permite trabajar con valores continuos para los atributos, separando los posibles resultados en 2 ramas Ai<=Z y Ai>Z; siendo Z un umbral escogido anteriormente.

• Los árboles son menos frondosos, ya que cada hoja cubre una distribución de clases, no una clase en particular.

• Utiliza el método "divide y vencerás" para generar el árbol de decisión inicial a partir de un conjunto de datos de entrenamiento.

• Se basan en la utilización del criterio de proporción de ganancia. De esta manera se consigue evitar que las variables con mayor número de categorías salgan beneficiadas en la selección.

• Es recursivo.

Funcionamiento

El algoritmo considera todas las pruebas posibles que pueden dividir el conjunto de datos y selecciona la prueba que le haya generado la mayor ganancia de información. Para cada atributo discreto, se considera una prueba con n resultados, siendo n el número de valores posibles que puede tomar el atributo. Para cada atributo continuo, se realiza una prueba binaria (1,0) sobre cada uno de los valores que toma el atributo en los datos. En cada nodo, el sistema debe decidir que prueba escoge para dividir los datos. Según Espino (2005) los tres tipos de pruebas posibles propuestas para el C4.5 son:

1. La prueba estándar para las variables discretas, con un resultado y una rama para cada valor posible de la variable. 
2. Una prueba más compleja, basada en una variable discreta, en donde los valores posibles son asignados a un número variable de grupos con un resultado posible para cada grupo,en lugar de para cada valor. 
3. Si una variable A tiene valores numéricos continuos, se realiza una prueba binaria con resultados A<=Z y A>Z, para lo cual debe determinar el valor limite Z.

Todas estas pruebas se evalúan observando el ratio de ganancia resultante de la división de datos que producen. El ratio de ganancia puede calcularse mediante la siguiente fórmula:

Además, es útil agregar una restricción adicional. Esta restricción consiste en que, para cualquier división, al menos dos de los subconjuntos Ci deben contener un número razonable de casos. Esta restricción, que evita las subdivisiones casi triviales, es tenida en cuenta solamente cuando el conjunto C es pequeño. 

Representación  general del algoritmo en pseudocódigo

1. Comprobar los casos base.
2. Para cada atributo a:
1. Encontrar la ganancia de información normalizada de la división de a.
3. Dejar que a_best sea el atributo con la ganancia de información normalizada más alta
4. Crear un nodo de decisión que divida a_best.
5. Repetir en las sublistas obtenidas por división de a_best, y agregar estos nodos como hijos de nodo.