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.