De Wikipedia, la enciclopedia libre
Ir a navegaciónSaltar a buscar

C4.5 es un algoritmo que se utiliza para generar un árbol de decisiones 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 esta razón, a menudo se hace referencia a C4.5 como 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 decisiones histórico 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 de los 10 mejores algoritmos en minería de datos 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 información . Los datos de entrenamiento son un conjuntode muestras ya clasificadas. Cada muestra consta de un vector p-dimensional , donde el representar valores de atributo o características de la muestra, así como la clase en la que caídas.

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

Este algoritmo tiene algunos casos base .

  • Todas las muestras de la lista pertenecen a la misma clase. Cuando esto sucede, simplemente crea un nodo hoja para el árbol de decisión que dice que elija esa clase.
  • Ninguna de las funciones proporciona ganancia de información. En este caso, C4.5 crea un nodo de decisión más arriba en el árbol usando el valor esperado de la clase.
  • Se ha encontrado una instancia de una clase nunca antes vista. Nuevamente, C4.5 crea un nodo de decisión más arriba en el árbol usando el valor esperado.

Pseudocódigo

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

  1. Compruebe los casos base anteriores.
  2. Para cada atributo a , encuentre la relación de ganancia de información normalizada al dividir en a .
  3. Sea a_best el atributo con la mayor ganancia de información normalizada.
  4. Cree 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 de node .

Implementaciones

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

Mejoras del algoritmo ID.3

C4.5 realizó una serie de mejoras en ID3. Algunos de estos son:

  • Manejo de atributos tanto continuos como 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 atributo faltantes: C4.5 permite marcar los valores de atributo como? por faltar. Los valores de atributo que faltan 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 la creación: C4.5 retrocede por el árbol una vez que se ha creado e intenta eliminar las ramas que no ayudan reemplazándolas con nodos de hojas.

Mejoras en el algoritmo C5.0 / See5

Quinlan pasó a crear C5.0 y See5 (C5.0 para Unix / Linux, See5 para Windows) que comercializa. C5.0 ofrece una serie de mejoras en C4.5. Algunos de estos 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 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 el impulso : el impulso mejora los árboles y les da más precisión.
  • Ponderación: C5.0 le permite ponderar diferentes casos y tipos de clasificación errónea.
  • Aventar: una opción de C5.0 aventa automáticamente los atributos para eliminar aquellos que pueden no ser útiles.

La fuente para una versión de Linux de un solo subproceso de C5.0 está disponible bajo la GPL.

Ver también

Referencias

  1. ^ Quinlan, JR C4.5: Programas de aprendizaje automático . Editorial Morgan Kaufmann, 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. pag. 191.
  3. ^ Umd.edu - Top 10 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. Se mejoró el uso de atributos continuos en c4.5. Revista de Investigación en Inteligencia Artificial, 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