Download C4.5\C4.5(2005-II

Equipo # 6
José Antonio Espino López
Javier Eduardo Tijerina Flores
Manuel Cedano Mendoza
Eleazar de la Fuente Amaya
Juan José Pérez González
Aníbal Chiñas Carballo
Algoritmo C4.5
INTELIGENCIA ARTIFICIAL
Algoritmo C4.5
Historia
Fue desarrollado en 1993 por JR Quinlan, como una extensión al
algoritmo ID3. Para dar solución a ciertas situaciones que el
algoritmo ID3 no consideraba.
Los tres tipos de pruebas posibles
propuestas por el C4.5 son:
 La prueba "estándar" para las variables
discretas.
 Una prueba más compleja.
 Si una variable A tiene valores numéricos
continuos.
A <= Z y A > Z.
CARACTERÍSTICAS
• Permite trabajar con valores continuos para los atributos,
separando los posibles resultados en 2 ramas Ai<=N y Ai>N.
• 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.
• Es Recursivo.
Heurística
• Gain Ratio (proporción de ganancia)
Atributos
• Atributos de Valores Continuos
• Atributos con Valores Perdidos
• Atributos con Aspectos Diferentes
Ventajas respecto al Algoritmo ID3
•
•
•
•
•
•
•
•
•
Evitar Sobreajuste de los datos.
Determinar que tan profundo debe crecer el árbol de decisión.
Reducir errores en la poda.
Condicionar la Post-Poda.
Manejar atributos continuos.
Escoger un rango de medida apropiado.
Manejo de datos de entrenamiento con valores faltantes.
Manejar atributos con diferentes valores.
Mejorar la eficiencia computacional.
Estructura de Algoritmo C4.5
El C4.5 se basa en el ID3, por lo tanto, la estructura principal de ambos
métodos es la misma.
C4.5 forma parte de la familia de los TDIDT (Top Down Induction Trees), junto
con antecesor el ID3.
C4.5 construye un árbol de decisión mediante el algoritmo "divide y vencerás"
C4.5 evalúa la Información en cada caso utilizando los criterios de entropía y
ganancia
Estructura General Arbol
de Decisión
+ Nodos: Id de Atributos
+ Ramas: Posibles valores del
atributo asociado al nodo
+ Hojas: Conjuntos ya clasificados
de ejemplos y etiquetados con el
nombre de una clase
Raíz
ramas
NodoA
Set de
posibles
respuestas
NodoB
Set de
posibles
respuestas
Árboles de decisión
Outlo Temperat
ok
ure
Humid
ity
Win
Play (positive) / Don't Play
d
(negative)
y
sunny
85
85
false
Don't Play
sunny
80
90
true
Don't Play
overc
ast
83
78
false
Play
rain
70
96
false
Play
rain
68
80
false
Play
rain
65
70
true
Don't Play
overc
ast
64
65
true
Play
sunny
72
95
false
Don't Play
sunny
69
70
false
Play
rain
75
80
false
Play
sunny
75
70
true
Play
overc
ast
72
90
true
Play
Atributos: conjunto de atributos no
clasificadores,
C: atributo clasificador,
Ejemplos: conjunto de ejemplos, devuelve
un árbol de decisión
AtributoM atributo con mayor Proporción de Ganancia(AtributoM,Ejemplos) entre los atributos de R;
Devolver un árbol con la raíz nombrada como AtributoM y con los arcos nombrados
C4.5(R-{D}, C, Sl), C4.5(R-{D}, C, S2), C4.5(R-{D}, C, Sm);
Pseudocódigo de C4.5
Función C4.5
R: conjunto de atributos no clasificadores,
C: atributo clasificador,
S: conjunto de ejemplos, devuelve un árbol de decisión
Comienzo
Si S está vacío,
Devolver un único nodo con Valor Falla;
‘ para formar el nodo raiz
Si todos los registros de S tienen el mismo valor para el atributo clasificador,
Devolver un único nodo con dicho valor; ‘un unico nodo para todos
Si R está vacío,
Devolver un único nodo con el valor más frecuente del atributo
clasificador en los registros de S [Nota: habrá errores, es decir,
registros que no estarán bien clasificados en este caso];
Si R no está vacío,
D atributo con mayor Proporción de Ganancia(D,S) entre los atributos de R;
Sean {dj | j=1,2,...., m} los valores del atributo D;
Sean {dj | j=1,2,...., m} los subconjuntos de S correspondientes a los valores de dj
respectivamente;
Devolver un árbol con la raíz nombrada como D y con los arcos nombrados d1,
d2,....,dm, que van respectivamente a los árboles
C4.5(R-{D}, C, Sl), C4.5(R-{D}, C, S2), C4.5(R-{D}, C, Sm);
Fin
Conclusión
Se genera un árbol de decisión a partir de los datos mediante particiones
realizadas recursivamente, aplicando la estrategia de profundidadprimero (depth-first).
El algoritmo considera todas las pruebas posibles que pueden dividir el
conjunto de datos y selecciona la prueba que resulta en 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 sobre cada
uno de los valores que toma el atributo en los datos.
Muchas Gracias por Su
Atención
Algoritmo C4.5
Continuara…
Equipo # 6
José Antonio Espino López
Javier Eduardo Tijerina Flores
Manuel Cedano Mendoza
Eleazar de la Fuente Amaya
Juan José Pérez González
Aníbal Chiñas Carballo
Algoritmo C4.5
Aplicaciones
Algoritmo C4.5
Simulador Para Volar un Avión
Cessna
Los datos se obtuvieron de 3 pilotos experimentados.
Haciendo un plan de vuelo asignado 30 veces.
Cada acción del piloto creaba un ejemplo.
Se usaron 90,000 ejemplos descritos por 20 atributos.
Se uso C4.5 que genero un árbol y se convirtió a C.
Se insertó en el simulador y logro volar.
Los resultados fueron sorprendentes en el sentido de que aparte
de aprender a volar a veces tomaba decisiones mejores que las
de sus ``maestros''
Aprendizaje en la WWW
 WebWatcher es un sistema de ayuda de localización de
información.
 Aprender las preferencias de un usuario.
 Se registra, cada vez que el usuario selecciona información de la
página, o enlaces.
 Esta información está descrita por 530 atributos boléanos
indicando si una palabra en particular aparece o no en el texto.
Grúa de embarcación
 Manejar una grúa (6 variables, 450,000 ejemplos)
 Imágenes de alta calidad generadas en tiempo real.
 Gráficos 3D.
 Texturas fotográficas obtenidas en el escenario real de
trabajo.
 Información para el usuario y el instructor en pantalla.
 Secuencia de arranque y parada de la grúa real.
 Estiba y desestiba en bodega con grapín.
 Trabajo con varios tipos de materiales, con diferentes
densidades y comportamientos.
Sistemas expertos
 Cine.
 Mecánica.
 Autos.
 Diagnostico medico.
DEMO
Muchas Gracias por Su
Atención
Algoritmo C4.5