PDF de programación - Algoritmo C4.5 - Inteligencia Artificial - Ingeniería en sistemas computacionales

Inteligencia Artificial

Algoritmo c4.5



INGENIERÍA EN SISTEMAS COMPUTACIONALES



INTELIGENCIA ARTIFICIAL

~ ALGORITMO C4.5 ~

ING. BRUNO LÓPEZ TAKEYAS


ALUMNOS:

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



Nuevo Laredo, Tamaulipas, Noviembre del 2005

Instituto Tecnológico de Nuevo Laredo Pág. 1

Inteligencia Artificial

Algoritmo c4.5

ÍNDICE



INTRODUCCIÓN
LA FAMILIA TDIDT

CONSTRUCCIÓN DE LOS ÁRBOLES DE DECISIÓN
ALGORITMO C4.5 ORIGEN

CARACTERÍSTICAS DEL ALGORITMO C4.5

HEURÍSTICA
ATRIBUTOS

MEJORAS DEL ALGORITMO C4.5
SOBREAJUSTE (OVERFITTING)
POST PRUNNING (POST PODA)

ESTRUCTURAS UTILIZADAS EN EL ALGORITMO C4.5
EJEMPLO APLICADO DE ÁRBOL DE DECISIÓN ADAPTADO PARA C4.5
PSEUDOCODIGO DE C4.5
DIAGRAMA GENÉRICO DE ALGORITMO C4.5
ESTIMACIÓN DE LA PROPORCIÓN DE ERRORES PARA LOS ÁRBOLES DE DECISIÓN
CONSTRUCCIÓN DE UN ÁRBOL DE DECISIÓN UTILIZANDO EL C4.5
APLICACIONES ALGORITMO C4.5

SIMULADOR PARA VOLAR UN AVIÓN CESSNA
APRENDIZAJE EN LA WWW
GRÚA DE EMBARCACIÓN
SISTEMAS EXPERTOS


BIBLIOGRAFÍA

3
3
3
3
4
4
5
5
5
6
6
7
8
9
9
10
13
13
13
13
14

15

Instituto Tecnológico de Nuevo Laredo Pág. 2

Inteligencia Artificial

Algoritmo c4.5

INTRODUCCIÓN


LA FAMILIA TDIDT

La familia de los Top Down Induction Trees (TDIDT) pertenece a los métodos inductivos del
Aprendizaje Automático que aprenden a partir de ejemplos preclasificados. En Minería de Datos, se
utiliza para modelar las clasificaciones en los datos mediante árboles de decisión.

CONSTRUCCIÓN DE LOS ÁRBOLES DE DECISIÓN

Los árboles TDIDT, a los cuales pertenecen los generados por el ID3 y pos el C4.5, se construyen a
partir del método de Hunt. El esqueleto de este método para construir un árbol de decisión a partir
de un conjunto T de datos de entrenamiento es muy simple. Sean las clases {C1, C2,. . ., Ck}.
Existen tres posibilidades:

1. T contiene uno o más casos, todos pertenecientes a una única clase Cj:

El árbol de decisión para T es una hoja identificando la clase Cj.

2. T no contiene ningún caso:

El árbol de decisión es una hoja, pero la clase asociada debe ser determinada por
información que no pertenece a T. Por ejemplo, una hoja puede escogerse de acuerdo a
conocimientos de base del dominio, como ser la clase mayoritaria.

3. T contiene casos pertenecientes a varias clases:

En este caso, la idea es refinar T en subconjuntos de casos que tiendan, o parezcan tender
hacia una colección de casos pertenecientes a una única clase. Se elige una prueba basada
en un único


ALGORITMO C4.5 ORIGEN

El algoritmo c4.5 fue desarrollado por JR Quinlan en 1993, como una extensión (mejora) del
algoritmo ID3 que desarrollo en 1986.


Instituto Tecnológico de Nuevo Laredo Pág. 3



Inteligencia Artificial

Algoritmo c4.5

El algoritmo C4.5 genera un árbol de decisión a partir de los datos mediante particiones realizadas
recursivamente. El árbol se construye mediante la estrategia de profundidad-primero (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. En cada nodo, el sistema debe decidir cuál prueba escoge para
dividir los datos.

Los tres tipos de pruebas posibles propuestas por el C4.5 son:

La prueba "estándar" para las variables discretas, con un resultado y una rama para cada valor
posible de la variable.
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.
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 determinarse el valor límite Z.

Todas estas pruebas se evalúan de la misma manera, mirando el resultado de la proporción de
ganancia, o alternativamente, el de la ganancia resultante de la división que producen. Ha sido útil
agregar una restricción adicional: 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.


CARACTERÍSTICAS DEL ALGORITMO C4.5



• Permite trabajar con valores continuos para los atributos, separando los posibles resultados

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

en 2 ramas Ai<=N y Ai>N.

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 basa en la utilización del criterio de proporción de ganancia (gain ratio), definido como
I(Xi,C)/H(Xi). De esta manera se consigue evitar que las variables con mayor número de
posibles valores salgan beneficiadas en la selección.

• Es Recursivo.


HEURÍSTICA

Utiliza una técnica conocida como Gain Ratio (proporción de ganancia). Es una medida basada en
información que considera diferentes números (y diferentes probabilidades) de los resultados de las
pruebas.



Instituto Tecnológico de Nuevo Laredo Pág. 4

Inteligencia Artificial

Algoritmo c4.5

ATRIBUTOS

Atributos de valores continuos: Inicialmente el algoritmo ID3 se planteó para atributos que
presentaban un número discreto de valores. Podemos fácilmente incorporar atributos con valores
continuos, simplemente dividiendo estos valores en intervalos discretos, de forma que el atributo
tendrá siempre valores comprendidos en uno de estos intervalos.

Medidas alternativas en la selección de atributos: Al utilizar la ganancia de información estamos
introduciendo involuntariamente un sesgo que favorece a los atributos con muchos valores distintos.
Debido a que dividen el conjunto de ejemplos en muchos subconjuntos, la ganancia de información
es forzosamente alta. Sin embargo, estos atributos no son buenos predictores de la función objetivo
para nuevos ejemplos. Una medida alternativa que se ha usado con éxito es la "gain ratio".

Atributos con valores perdidos: En ciertos casos existen atributos de los cuales conocemos su
valor para algunos ejemplos, y para otros no. Por ejemplo una base de datos médica en la que no a
todos los pacientes se les ha practicado un análisis de sangre. En estos casos lo más común es
estimar el valor basándose en otros ejemplos de los que sí conocemos el valor. Normalmente se fija
la atención en los demás ejemplos de ese mismo nodo. Así, al ejemplo de valor desconocido se le
da el valor que más aparezca en los demás ejemplos.

Atributos con pesos diferentes: En algunas tareas de aprendizaje los atributos pueden tener
costes asociados. Por ejemplo, en una aplicación médica para diagnosticar enfermedades podemos
tener atributos como temperatura, resultado de la biopsia, pulso, análisis de sangre, etc., que varían
significativamente en su coste, monetario y relativo a molestias para el paciente.
Ventajas respecto al algoritmo ID3



MEJORAS DEL ALGORITMO C4.5



• 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.


SOBREAJUSTE (OVERFITTING)

A medida que se añaden niveles AD, las hipótesis se refinan tanto que describen muy bien los
ejemplos utilizados en el aprendizaje, pero el error de clasificación puede aumentar al evaluar los
ejemplos. Es decir, clasifica muy bien los datos de entrenamiento pero luego no sabe generalizar al
conjunto de prueba. Es debido a que aprende hasta el ruido del conjunto de entrenamiento,
adaptándose a las regularidades del conjunto de entrenamiento.

Instituto Tecnológico de Nuevo Laredo Pág. 5

Inteligencia Artificial

Algoritmo c4.5



Este efecto es, por supuesto, indeseado. Hay varias causas posibles para que esto ocurra. Las
principales son:


• Exceso de ruido (lo que se traduce en nodos adicionales)
• Un conjunto de entrenamiento demasiado pequeño como para ser una muestra

representativa de la verdadera función objetivo.

Hay varias estrategias para evitar el sobreajuste en los datos. Pueden ser agrupadas en dos clases:


• Estrategias que frenan el crecimiento del árbol antes de que llegue a clasificar

perfecta