Algoritmo C4.5

Algoritmo para la elaboración de árboles de decisión

C4.5 es un algoritmo utilizado para generar un árbol de decisión desarrollado por Ross Quinlan . ^[1] C4.5 es una extensión del algoritmo ID3 anterior de Quinlan . Los árboles de decisión generados por C4.5 se pueden utilizar para la clasificación y, por este motivo, a C4.5 se le suele denominar clasificador estadístico . En 2011, los autores del software de aprendizaje automático Weka describieron el algoritmo C4.5 como "un programa de árbol de decisión emblemático que probablemente sea el caballo de batalla del aprendizaje automático más utilizado en la práctica hasta la fecha". ^[2]

Se hizo bastante popular después de ocupar el puesto número 1 en el artículo preeminente Top 10 Algorithms in Data Mining publicado por Springer LNCS en 2008. ^[3]

Algoritmo

C4.5 construye árboles de decisión a partir de un conjunto de datos de entrenamiento de la misma manera que ID3 , utilizando el concepto de entropía de la información . Los datos de entrenamiento son un conjunto de muestras ya clasificadas. Cada muestra consta de un vector p-dimensional , donde los representan los valores de los atributos o características de la muestra, así como la clase en la que se encuentra. ${\displaystyle S={s_{1},s_{2},...}}$ ${\displaystyle s_{i}}$ ${\displaystyle (x_{1,i},x_{2,i},...,x_{p,i})}$ ${\displaystyle x_{j}}$ ${\displaystyle s_{i}}$

En cada nodo del árbol, C4.5 elige el atributo de los datos que divide de forma más eficaz su conjunto de muestras en subconjuntos enriquecidos en una u otra clase. El criterio de división es la ganancia de información normalizada (diferencia de entropía). Se elige el atributo con la mayor ganancia de información normalizada para tomar la decisión. A continuación, el algoritmo C4.5 recurre sobre las sublistas particionadas .

Este algoritmo tiene algunos casos base .

• Todas las muestras de la lista pertenecen a la misma clase. Cuando esto sucede, simplemente se crea un nodo de hoja para el árbol de decisión que indica que se debe elegir esa clase.
• Ninguna de las características aporta información. En este caso, C4.5 crea un nodo de decisión más arriba en el árbol utilizando el valor esperado de la clase.
• Se encontró una instancia de una clase no vista anteriormente. Nuevamente, C4.5 crea un nodo de decisión más arriba en el árbol utilizando el valor esperado.

Pseudocódigo

En pseudocódigo , el algoritmo general para construir árboles de decisión es: ^[4]

1. Verifique los casos base anteriores.
2. Para cada atributo a , encuentre la relación de ganancia de información normalizada a partir de la división en a .
3. Sea a_best el atributo con la mayor ganancia de información normalizada.
4. Crea un nodo de decisión que se divida en a_best .
5. Recurra a las sublistas obtenidas al dividir en a_best y agregue esos nodos como hijos del nodo .

Implementaciones

J48 es una implementación Java de código abierto del algoritmo C4.5 en la herramienta de minería de datos Weka .

Mejoras del algoritmo ID3

La versión 4.5 introdujo una serie de mejoras en ID3. Algunas de ellas son:

• Manejo de atributos continuos y discretos: para manejar atributos continuos, C4.5 crea un umbral y luego divide la lista en aquellos cuyo valor de atributo está por encima del umbral y aquellos que son menores o iguales a él. ^[5]
• Manejo de datos de entrenamiento con valores de atributos faltantes: C4.5 permite marcar los valores de atributos como ? por faltantes. Los valores de atributos faltantes simplemente no se utilizan en los cálculos de ganancia y entropía.
• Manejo de atributos con diferentes costos.
• Poda de árboles después de su creación: C4.5 recorre el árbol una vez creado e intenta eliminar las ramas que no ayudan reemplazándolas con nodos de hojas.

Mejoras en el algoritmo C5.0/See5

Quinlan creó posteriormente C5.0 y See5 (C5.0 para Unix/Linux, See5 para Windows), que comercializa. C5.0 ofrece una serie de mejoras con respecto a C4.5. Algunas de ellas son: ^{[6] [7]}

• Velocidad: C5.0 es significativamente más rápido que C4.5 (varios órdenes de magnitud)
• Uso de memoria: C5.0 es más eficiente en el uso de memoria que C4.5
• Árboles de decisión más pequeños: C5.0 obtiene resultados similares a C4.5 con árboles de decisión considerablemente más pequeños.
• Soporte para potenciar : potenciar mejora los árboles y les otorga más precisión.
• Ponderación: C5.0 le permite ponderar diferentes casos y tipos de clasificación errónea.
• Selección: una opción de C5.0 selecciona automáticamente los atributos para eliminar aquellos que pueden no ser útiles.

El código fuente de una versión Linux de un solo subproceso de C5.0 está disponible bajo la Licencia Pública General de GNU (GPL).

Véase también

• Algoritmo ID3
• Modificación de C4.5 para generar reglas temporales y causales

Referencias

1. Quinlan, JR C4.5: Programas para el aprendizaje automático . Morgan Kaufmann Publishers, 1993.
2. Ian H. Witten; Eibe Frank; Mark A. Hall (2011). "Minería de datos: herramientas y técnicas prácticas de aprendizaje automático, 3.ª edición". Morgan Kaufmann, San Francisco. pág. 191.
3. Umd.edu - Los 10 mejores algoritmos en minería de datos
4. SB Kotsiantis, "Aprendizaje automático supervisado: una revisión de las técnicas de clasificación", Informatica 31(2007) 249-268, 2007
5. JR Quinlan. Uso mejorado de atributos continuos en c4.5. Journal of Artificial Intelligence Research, 4:77-90, 1996.
6. Es See5/C5.0 mejor que C4.5?
7. M. Kuhn y K. Johnson, Modelado predictivo aplicado, Springer 2013

Enlaces externos

• Implementación original en la página de inicio de Ross Quinlan: http://www.rulequest.com/Personal/
• See5 y C5.0