Upload
fabricio-echeverria
View
384
Download
3
Embed Size (px)
Citation preview
UNIVERSIDAD CENTROAMERICANA
“JOSÉ SIMEÓN CAÑAS”
IMPLEMENTACIÓN DEL ALGORITMO C4.5 DE APRENDIZAJE
AUTOMÁTICO PARA LA GENERACIÓN DE ÁRBOLES DE DECISIÓN
EN FORMA INDUCTIVA EN EL PROYECTO AIPI.
TRABAJO DE GRADUACIÓN PREPARADO PARA LA
FACULTAD DE INGENIERÍA Y ARQUITECTURA
PARA OPTAR AL GRADO DE
LICENCIADO(A) EN CIENCIAS DE LA COMPUTACION
POR:
SILVIA ESTELA MARTÍNEZ GALDÁMEZ
CARLOS FABRICIO RAMÍREZ ECHEVERRÍA
GERMAN ERICK ROLANDO RODRÍGUEZ HERNÁNDEZ
WALTER OSWALDO SALAZAR GONZÁLEZ
OCTUBRE 2013
ANTIGUO CUSCATLÁN, EL SALVADOR, C.A.
RECTOR
ANDREU OLIVA DE LA ESPERANZA, S.J.
SECRETARIA GENERAL
SILVIA ELINOR AZUCENA DE FERNÁNDEZ
DECANO DE LA FACULTAD DE INGENIERIA Y ARQUITECTURA
CARLOS GONZALO CAÑAS GUTIERRÉZ
COORDINADOR DE LA CARRERA DE LICENCIATURA EN CIENCIAS
DE LA COMPUTACIÓN
ÁNGEL FERNANDO DUARTE NOVOA
DIRECTOR DEL TRABAJO
MAURICIO ALFARO
LECTOR
EDUARDO RIVERA
AGRADECIMIENTO
Agradecemos primeramente a Dios que nos ha permitido llegar hasta este punto en
nuestra carrera universitaria. También, a nuestros padres, familiares y amigos que nos han
apoyado en diferentes aspectos durante este largo camino para culminar nuestra carrera.
Además, agradecemos también a todos los catedráticos, instructores y a todas las
personas que nos guiaron, enseñaron y compartieron con nosotros todo el conocimiento
que ellos tenían y que nos ayudó a desarrollarnos en las diferentes áreas de esta carrera.
Silvia Martínez
Fabricio Echeverría
Erick Rodríguez
Walter Salazar
i
RESUMEN
La implementación del algoritmo C4.5, para la generación de árboles de decisión en forma
inductiva, como un módulo para el software AIPI incluye su comprensión, codificación e
incorporación en el software AIPI.
Para ello primeramente se tuvo que estudiar el algoritmo ID3, ya que el C4.5 es una
mejora del ID3, esto sirvió para comprender los cálculos básicos que se realizan para la
generación de los árboles de decisión, que se utilizan para predecir comportamientos de
acuerdo a los datos proporcionados a cada uno.
Luego de ello, se investigó sobre las mejoras que contiene el algoritmo C4.5 con respecto
al ID3, para ver las variaciones y así poder desarrollar algunos ejemplos. Entre las mejoras,
más relevantes, se puede mencionar la utilización de atributos continuos y atributos
desconocidos.
Es importante aclarar que la información sobre el tema es poca y no posee mucho detalle,
por ello se tuvo que deducir algunos comportamientos a partir del algoritmo original
desarrollado por Quinlan, para poder construir tanto los ejemplos como el código.
Después de toda la investigación bibliográfica que se pudo recopilar se comenzó con el
estudio del C4.5, obteniendo como resultado la construcción de ejemplos completos en
los cuáles se pueden apreciar el funcionamiento del algoritmo, dichos ejemplos incluyen el
uso de atributos continuos, de atributos desconocidos y de la poda del árbol de decisión
generado.
ii
Posteriormente, para el desarrollo del código se tuvo como base el C4.5 desarrollado por
Quinlan el cuál se encuentra en lenguaje C, este fue totalmente adaptado al lenguaje de
desarrollo utilizado en el software AIPI, el cual es C++ que utiliza la librería MFC (Microsoft
Fundation Classes). La diferencia entre ambos lenguajes es bastante evidenciada, como lo
es en la sintaxis que utilizan ambos leguajes. Se hicieron varias modificaciones y
correcciones para poder incluirlo en AIPI y que funcionara como el módulo que se pidió
implementar. En el desarrollo, también se modificaron algunas interfaces de AIPI para
poder mostrar los resultados obtenidos del algoritmo, como lo es el árbol de decisión
generado.
Al terminar el desarrollo se realizaron todas las pruebas de forma exhaustiva para verificar
que el algoritmo C4.5 implementado estuviera generando el árbol de decisión correcto, de
acuerdo a los datos proporcionados. Para poder hacer dicha verificación se utilizó el
software de minería de datos WEKA, el cual incluye el C4.5 (denominado como J48). Lo
que se hizo fue probar en ambos software el mismo ejemplo para poder comparar los
árboles de decisión generados y el tiempo que se tardaba cada uno en la generación de
dichos árboles.
Luego de todas las pruebas y de realizar las correcciones que surgieron como resultado de
dichas pruebas, se terminó el desarrollo del módulo para el software AIPI. El cuál contiene
el algoritmo C4.5 que genera el árbol de decisión a partir de los datos proporcionados y lo
realiza de manera eficiente y óptima, con respecto al lenguaje en el que se ha
desarrollado. Los resultados son los esperados de acuerdo a lo planteado en los objetivos
y alcances del tema y se lograron realizar algunos agregados en el desarrollo.
ÍNDICE
RESUMEN .................................................................................................................................. i
ÍNDICE DE FIGURAS ................................................................................................................... v
ÍNDICE DE TABLAS ................................................................................................................... vii
CAPÍTULO 1: GENERALIDADES ................................................................................................... 1
1.1 DEFINICIÓN DEL PROBLEMA................................................................................................ 1
1.2 OBJETIVOS ................................................................................................................................. 2
1.2.1 OBJETIVO GENERAL ............................................................................................................ 2
1.2.2 OBJETIVOS ESPECÍFICOS ..................................................................................................... 2
1.3 ALCANCES Y LÍMITES .................................................................................................................. 3
1.3.1 ALCANCES ........................................................................................................................... 3
1.3.2 LÍMITES ............................................................................................................................... 3
1.4 ANTECEDENTES ......................................................................................................................... 4
1.5 ESTRUCTURA PRELIMINAR DEL TRABAJO .................................................................................. 5
1.6 PROGRAMACIÓN Y DIVISIÓN DEL TRABAJO .............................................................................. 6
CAPÍTULO 2: MARCO TEÓRICO .................................................................................................. 7
ALGORITMO ID3 .............................................................................................................................. 7
ALGORITMO C4.5 ............................................................................................................................ 9
CAPÍTULO 3: METODOLOGÍA ................................................................................................... 17
CAPÍTULO 4: PRESENTACIÓN, ANÁLISIS E INTERPRETACIÓN DE LOS RESULTADOS ..................... 19
CAPÍTULO 5: CONCLUSIONES Y RECOMENDACIONES ................................................................ 59
5.1 CONCLUSIONES ....................................................................................................................... 59
5.2 RECOMENDACIONES ............................................................................................................... 60
REFERENCIAS .......................................................................................................................... 61
ANEXOS
ANEXO A: MODIFICACIÓN DE CÓDIGO
ANEXO B: MANUAL DE USUARIO
ANEXO C: DETALLE DE LAS SALIDAS QUE PRODUCE EL ALGORITMO C4.5
v
ÍNDICE DE FIGURAS
Figura 1.1. Línea de tiempo de software de minería de datos ........................................................... 4
Figura 3.1. Metodología SCRUM ....................................................................................................... 17
Figura 4.1. Árbol de decisión generado ............................................................................................ 32
Figura 4.2. Árbol de decisión podado ............................................................................................... 37
Figura 4.3. Primer división para formar el árbol de decisión ............................................................ 43
Figura 4.4. Ramificación por el conjunto X3 ..................................................................................... 44
Figura 4.5. Árbol de decisión resultante ........................................................................................... 45
Figura 4.6. Árbol formado ................................................................................................................. 46
Figura 4.7. Árbol de decisión ............................................................................................................. 47
Figura 4.8. Función que selecciona el menor umbral ....................................................................... 48
Figura 4.9. Función que selecciona el menor umbral modificada .................................................... 49
Figura 4.10. Árbol de decisión generado con la función modificada ................................................ 49
Figura 4.11. Árbol de la solución del proyecto.................................................................................. 50
Figura 4.12. Entorno de trabajo ........................................................................................................ 51
Figura 4.13. Ejecución del algoritmo generando un árbol no podado.............................................. 52
Figura 4.14. Generación de un árbol no podado utilizando el algoritmo C4.5 ................................. 52
Figura 4.15. Ejecución del algoritmo generando un árbol podado ................................................... 53
Figura 4.16. Generación de un árbol podado utilizando el algoritmo C4.5 ...................................... 53
Figura 4.17. Árbol de decisión del ejemplo iris generado en WEKA ................................................. 54
Figura 4.18. Árbol de decisión del ejemplo iris generado por AIPI ................................................... 55
Figura 4.19. Árbol de decisión del ejemplo laborneg generado en WEKA ....................................... 56
Figura 4.20. Árbol de decisión del ejemplo laborneg generado en AIPI ........................................... 56
Figura 4.21. Árbol de decisión del ejemplo vote generado en WEKA .............................................. 57
Figura 4.22. Árbol de decisión del ejemplo vote generado en AIPI .................................................. 57
Figura B.1. Interfaz del software AIPI ............................................................................................... B-1
Figura B.2. Elección de archivo de ejemplo ..................................................................................... B-2
Figura B.3. Carga de datos ............................................................................................................... B-2
Figura B.4. Selección de atributo de salida ...................................................................................... B-2
Figura B.5. Selección de tipo de atributo ......................................................................................... B-2
Figura B.6. Creación de archivo ........................................................................................................ B-2
Figura B.7. Especificación de nombre y ruta del archivo ................................................................. B-2
Figura B.8. Ejecución del algoritmo C4.5.......................................................................................... B-2
Figura B.9. Árbol de decisión generado ........................................................................................... B-2
Figura B.10. Opciones para cambiar presentación del árbol ........................................................... B-2
Figura B.11. Árbol de decisión horizontal ........................................................................................ B-2
Figura B.12. Datos de salida ............................................................................................................. B-2
Figura B.13. Guardar árbol de decisión ............................................................................................ B-2
Figura C.1. Árbol de decisión ............................................................................................................ C-2
Figura C.2. Datos de salida ............................................................................................................... C-2
vii
ÍNDICE DE TABLAS
Tabla 4.1. Casos (ejemplo jugar golf) ................................................................................................ 20
Tabla 4.2. División de los datos por el atributo clima ....................................................................... 20
Tabla 4.3. División de los datos por el atributo temperatura ........................................................... 23
Tabla 4.4. División de los datos por el atributo humedad ................................................................ 24
Tabla 4.5. Datos del atributo temperatura, para el valor soleado.................................................... 25
Tabla 4.6. Valores N y E, para temperatura (valor soleado) ............................................................. 26
Tabla 4.7. Datos del atributo humedad, para el valor soleado ......................................................... 26
Tabla 4.8. Valores N y E, para humedad (valor soleado) .................................................................. 27
Tabla 4.9. Datos para el valor nublado, del atributo clima ............................................................... 27
Tabla 4.10. Datos del atributo temperatura, para el valor nublado ................................................. 27
Tabla 4.11. Valores N y E, para temperatura (valor nublado) .......................................................... 28
Tabla 4.12. Datos del atributo humedad, para el valor nublado ...................................................... 28
Tabla 4.13. Valores N y E, para humedad (valor nublado) ................................................................ 29
Tabla 4.14. Datos para el valor lluvia, del atributo clima .................................................................. 30
Tabla 4.15. Datos del atributo temperatura, para el valor lluvia ...................................................... 30
Tabla 4.16. Valores N y E, para temperatura (valor lluvia) ............................................................... 31
Tabla 4.17. Datos del atributo humedad, para el valor lluvia ........................................................... 31
Tabla 4.18. Valores N y E, para humedad (valor lluvia) .................................................................... 32
Tabla 4.19. Casos (ejemplo de atributos continuos) ......................................................................... 38
Tabla 4.20. Información del atributo ................................................................................................ 39
Tabla 4.21. Información del atributo ................................................................................................ 40
Tabla 4.22. Posibles umbrales ........................................................................................................... 40
Tabla 4.23. Cálculos para el umbral 72.5 .......................................................................................... 41
Tabla 4.24. Cálculos para el umbral 79 ............................................................................................. 42
Tabla 4.25. Cálculos para el umbral 82.5 .......................................................................................... 42
Tabla 4.26. Cálculos para el umbral 92.5 .......................................................................................... 42
Tabla 4.27. Subconjunto de X1 ......................................................................................................... 43
Tabla 4.28. Información del atributo ................................................................................................ 43
Tabla 4.29. Posibles umbrales ........................................................................................................... 44
Tabla 4.30. Información del atributo ................................................................................................ 44
Tabla 4.31. Subconjunto para X1 ...................................................................................................... 45
Tabla 4.32. Información del atributo ................................................................................................ 46
Tabla 4.33. Posibles umbrales ........................................................................................................... 46
Tabla 4.34. Resumen de los tiempos ................................................................................................ 58
1
CAPÍTULO 1: GENERALIDADES
1.1 DEFINICIÓN DEL PROBLEMA
AIPI es un software en desarrollo basado en metodologías de Inteligencia Artificial, el cual
contiene una interfaz gráfica de usuario diseñada con el objeto de ejecutar un lenguaje
propio del sistema, el cual está englobado en reglas y bases de conocimientos que se
apoyan en los conceptos de Sistemas Expertos, todo esto con el fin de dar interpretación a
dicha base de conocimientos para obtener un resultado útil al usuario. Este software
utiliza un conjunto de reglas basadas en la experiencia y el conocimiento de uno o varios
humanos expertos, las cuales se codifican en el lenguaje propio de la herramienta para
luego ser ejecutadas con el fin de llegar a un resultado apegado a la realidad. (AIPI Work)
Uno de los algoritmos que utiliza dicho software es el ID3 que consiste en un conjunto de
instrucciones que generan un árbol de decisión a partir de la entropía de los atributos
utilizados, este algoritmo es utilizado en el ámbito de la Inteligencia Artificial, y su uso se
basa en la búsqueda de hipótesis y reglas, dado un conjunto de ejemplos. (Tutorial -
ML_Ejercicios Algoritmo ID3.pdf)
El algoritmo C4.5 es una mejora del algoritmo ID3. Su utilización es básicamente la misma
que la del algoritmo ID3 con la diferencia que construye árboles más pequeños y más
representativos. (C4.5(2005-II-B).pdf)
El algoritmo ID3 se encuentra implementado en el software denominado AIPI y posee
algunas limitantes con respecto al algoritmo C4.5 como son: manejo únicamente de
valores discretos, en ocasiones genera grandes árboles de decisión que pueden
representar reglas no muy eficientes, no existe discriminación en el árbol de decisión, y
otras que se especificarán con detalle en las limitaciones del proyecto.
Estos algoritmos pueden ser utilizados para la creación de Sistemas Expertos debido a que
su estructura de árbol de decisión se asemeja mucho a una regla de
2
producción, y estas a su vez son usadas como base de conocimiento dentro de un sistema
experto. Esta funcionalidad es la que se pretende ser implementada en el software AIPI,
sin embargo debido a las limitantes del algoritmo ID3 se ha buscado la implementación
del algoritmo C4.5 como una mejora significativa al software AIPI. Este algoritmo (C4.5)
permitirá el uso de variables discretas y continuas, a diferencia del ID3 que solo permite
variables discretas, además de implementar otras extensiones que buscan que las
predicciones (o deducciones) sean más precisas y optimizadas.
1.2 OBJETIVOS
1.2.1 OBJETIVO GENERAL
Implementar el algoritmo C4.5 en el software AIPI, el cual está basado en procesos
automáticos basados en Inteligencia Artificial y busca como resultado la generación de
árboles de decisión en forma inductiva los cuales permiten predecir comportamientos y
crear modelos según los datos proporcionados.
1.2.2 OBJETIVOS ESPECÍFICOS
Analizar y entender el código del algoritmo ID3 implementado en software AIPI
para después incorporar las mejoras respectivas del algoritmo C4.5.
Implementar el algoritmo C4.5 utilizando las interfaces gráficas de usuario del
software AIPI.
Integrar el algoritmo C4.5 al proyecto AIPI como módulo adicional para el
crecimiento y mejora de dicho software, y refinamiento en la predicción de
problemas de forma más eficiente.
Dar a conocer el funcionamiento detallado del algoritmo C4.5 por medio del
desarrollo y explicación de ejemplos, ya que a diferencia de otras metodologías de
inteligencia artificial no existe información detallada sobre dicho algoritmo.
Contribuir a la comunidad de software libre, donando este módulo que será un
aporte al proyecto AIPI.
3
Apoyar la educación e investigación científica dando a conocer metodologías
relativamente desconocidas en El Salvador.
Realizar un manual de usuario del algoritmo C4.5 implementado, para facilitar su
utilización.
1.3 ALCANCES Y LÍMITES
1.3.1 ALCANCES
Estudio del algoritmo ID3 para tener una mayor comprensión del algoritmo C4.5.
Comprensión en detalle del algoritmo C4.5 para poder implementarlo.
Implementación de las mejoras del algoritmo ID3:
Manejo de Atributos continuos.
Manejo de valores desconocidos en los atributos.
Poda de los árboles de decisión.
Incorporación del algoritmo C4.5 para el proyecto AIPI.
1.3.2 LÍMITES
No se incluirá una de las mejoras del algoritmo C4.5 la cual consiste en el
agrupamiento de atributos con características parecidas, esto se debe a que esta
característica no es muy importante y muchos de los software que implementan
este algoritmo no la traen y si la traen lo hacen como una opción en el momento
de generar el árbol de decisión.
No se incluirá ningún método de verificación de errores al construir el modelo.
Técnicas como el de validación cruzada (cross validation) suelen utilizarse después
de construir el árbol de decisión como herramienta para determinar la calidad del
modelo generado. El proyecto no incluirá esta metodología de verificación debido
a que se sale de la teoría básica de lo que es el algoritmo C4.5.
4
1.4 ANTECEDENTES
Para este tema, se buscó información en la Universidad Centroamericana José Simeón
Cañas (UCA) y no se encontró ninguna tesis o trabajo relacionado con la generación de
árboles de decisión, de igual manera se investigó en las demás Universidades de El
Salvador teniendo los mismos resultados, no encontrando ninguna información
relacionada al tema.
En el Salvador algunas empresas, como El Banco Agrícola, trabajan en Desarrollo de
modelos de minería de datos que es utilizado para segmentación de sectores, además de
identificación de tipologías de lavado de dinero, de sectores de alto riesgo, de
transacciones inusuales, etc. Estas empresas también utilizan otras técnicas, como la antes
mencionada, las cuales no generan árboles de toma de decisiones.
En la web
En la figura 1.1, se muestra una línea de tiempo con las diferentes aplicaciones de minería
de datos:
Figura 1.1: Línea de tiempo de software de minería de datos
5
En la web se encontraron programas relacionados a la minería de datos, algunos software
pagados como: SAS Enterprise Miner (SAS decision tree module), Alice d'Isoft (Interactive
decision tree), Salford Systems Data Mining Suite (CART Decision Trees) y xpertrule
(Nesting Decision Trees) que incluyen el uso de árboles de decisión.
Además, existen otros software pagados que utilizan técnicas diferentes de minería de
datos (que no son árboles de decisión) como son: Powerhouse, Quiterian y dVelox
Enterprise.
También, hay software libre de minería de datos con árboles de decisión como Weka, el
cual servirá de apoyo más adelante, Rapid Miner, KNIME (Decision Tree Ensemble), KEEL
(Ocupa el ID3 y C4.5 entre otros), Orange (orngTree: Orange Decision Trees Module).
1.5 ESTRUCTURA PRELIMINAR DEL TRABAJO
El trabajo final de tesis constará de los siguientes capítulos:
Introducción
En este capítulo se presentará la definición del problema, los objetivos generales y
específicos, los alcances y límites, y los antecedentes existentes para este
proyecto.
Marco teórico
En este capítulo se incluirá toda la teoría correspondiente al tema, en este caso
sobre el software AIPI, el algoritmo ID3 y el C4.5.
Metodología
En este capítulo de detallará la metodología de trabajo a utilizar, además de las
herramientas a utilizar, para lograr el desarrollo del proyecto.
6
Presentación, análisis e interpretación de resultados
En este capítulo se presentarán los resultados que se obtengan del proyecto, en
este caso el algoritmo implementado y además una serie de comprobaciones de
árboles previamente construidos con el software WEKA con el fin de comparar la
de los árboles generados.
Además se tomará en cuenta el tiempo que se tardará el software en construir los
árboles de decisión comparados al software WEKA.
Conclusiones y recomendaciones
En este capítulo se abordarán las conclusiones y recomendaciones a las que se
llegaron a partir del desarrollo del proyecto.
Además, al final del documento se colocará una sección con los anexos que se consideren
necesarios e importantes.
1.6 PROGRAMACIÓN Y DIVISIÓN DEL TRABAJO
FECHA ACTIVIDAD RESPONSABLES
06-Marzo/31-Abril Investigación y estudio sobre el tema, incluyendo comprensión de los algoritmos correspondientes.
Todos los integrantes.
13-Marzo/01-Abril Elaboración de documento de anteproyecto.
Todos los integrantes.
20-Marzo/06-Abril Mejora de atributos continuos, en el desarrollo del algoritmo C4.5
Todos los integrantes.
07-Abril/03-Mayo Mejora cuando existen tablas con datos incompletos.
Todos los integrantes.
04-Mayo/01-Junio Mejora de la poda del árbol de decisión generado por el algoritmo.
Todos los integrantes.
02-Junio/01-Julio Mejora de la toma de la muestra de datos cuando existen demasiados.
Todos los integrantes.
02-Julio/28-Julio Realización de pruebas. Todos los integrantes.
15-Abril/29-Julio Elaboración del documento final del proyecto.
Todos los integrantes.
30-Julio Entrega de software y documentación
7
CAPÍTULO 2: MARCO TEÓRICO
AIPI es un software basado en Inteligencia Artificial el cual está siendo implementado para
la creación de Sistemas Expertos. Este software además de contar con una interface para
la creación y ejecución de Sistemas Expertos, está conformado por varios módulos
adicionales que buscan simplificar la generación de conocimiento para los Sistemas
Expertos, entre ellos se encuentran el algoritmo ID3 y el C4.5.
ALGORITMO ID3
El ID3 es un algoritmo de aprendizaje simbólico, el cual sirve para resolver problemas de
clasificación o predicción de comportamientos de datos a través del aprendizaje inductivo.
Este algoritmo tiene como finalidad la creación de un árbol de inducción correspondiente
a los datos que se le han proporcionado (base de datos) para la creación de dicho árbol.
Además, se basa en la entropía para elegir el mejor atributo dentro los datos utilizados
para crear el árbol, y una vez seleccionado este atributo, se realiza una partición de los
datos basándose en dicho atributo que representa el mejor candidato para ramificar el
árbol, para luego comenzar el proceso nuevamente en forma recursiva.
Al igual que todo algoritmo existente, este tiene sus limitantes entre las cuáles se pueden
mencionar: favorece atributos con muchos valores que no necesariamente son los más
útiles para la construcción del árbol de decisión, se pueden dar conflictos en la base de
datos debido a que se puede llegar a diferentes soluciones a partir de los mimos valores,
manejo sólo de valores discretos, se generan grandes árboles de decisión que no
representan garantía de reglas eficientes, su aplicación es sólo a problemas de
clasificación y diagnóstico (Ing. Bruno López Takeyas, algoritmo ID3).
Los árboles de decisión, que se generan con el algoritmo ID3, están formados por:
Nodos: nombres o identificadores de los atributos.
Ramas: posibles valores del atributo asociado al nodo.
8
Hojas: conjuntos ya clasificados de los ejemplos y etiquetados con el nombre de
una clase.
Para conocer un poco más sobre el funcionamiento de algoritmo ID3 se muestra a
continuación el pseudocódigo de dicho algoritmo, el cuál se realiza de forma recursiva:
Aprendizaje-Árbol-Decisión (Ejemplos, Atributos, Default) retorna Árbol de decisión
If no hay ejemplos
Retornar Default
ElseIf si todos los ejemplos tienen la misma clasificación
Retornar la clasificación
ElseIf Atributos = vacío
Retornar Mayoría (Ejemplos)
Else
Mejor-atr elegir-atributo (Atributos,Ejemplo)
Árbol nuevo árbol de decisión con raíz en Mejor-atr
ForEach valor v[i] de Mejor-atr Do
Ejemplos[i] {elementos de Ejemplos con Mejor-atr=v[i]}
Sub-ar Aprendizaje-Árbol-Decisión {Ejemplos[i], Atributos-
Mejor-atr, Mayoría(Ejemplos)}
Agregar rama al árbol con etiqueta v[i] y subárbol Sub-ar
Next
Retornar Árbol
Algunos de los datos importantes, que se pueden apreciar en el pseudocódigo anterior
son los siguientes:
Atributos: Son los factores que influencian la clasificación o decisión.
Ejemplos: Es el conjunto de combinaciones de atributos dados.
Además de los anteriores, es importante tener en cuenta los siguientes datos para poder
desarrollar el algoritmo:
Clase: Posibles valores de solución.
9
Entropía: Es la medida de la incertidumbre que hay en un sistema. Es decir, ante
una determinada situación, la probabilidad de que ocurra cada uno de los posibles
resultados. La fórmula utilizada para su cálculo se presenta en la Ec.2.1:
I(p,n) = -(p/(p + n))*LOG2(p/(p + n))-(n/(p + n))*LOG2(n/(p + n)) (Ec.2.1)
Donde,
I(p,n) es la entropía del conjunto.
P es el número de atributos correspondientes a una clase.
N es el total de atributos.
LOG2 es logaritmo base dos.
Además, la fórmula para calcular la entropía total de los atributos se presenta en la
Ec.2.2:
E(A)=((p1+n1)*I(p1,n1)+(p2+n2)*I(p2,n2)+...+(pv+nv)*I(pv,nv))/(p+n)
(Ec.2.2)
Donde,
E(A) es la entropía total de los atributos.
Ganancia: Es la diferencia entre la entropía de un nodo y la de uno de sus
descendientes. La fórmula para calcular la ganancia se presenta en la Ec. 2.3:
Ganancia(A) = I(p,n) - E(A) (Ec.2.3)
ALGORITMO C4.5
El algoritmo C4.5 fue desarrollado por J.R. Quinlan en 1993, como una mejora o extensión
del algoritmo ID3. Este algoritmo genera un árbol de decisión, a partir de los datos
proporcionados, mediante particiones realizadas recursivamente al igual que el ID3. Dicho
árbol se construye mediante la estrategia de profundidad-primero (Ing. Bruno López
Takeyas, algoritmo C4.5).
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
10
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.
Las mejoras que presenta el algoritmo C4.5 con respecto al ID3 son (C4.5(2005-II-B).pdf):
Evitar Sobreajuste de los datos.
Determinar la profundidad de crecimiento que debe tener 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.
Algunos datos importantes que son necesarios para la comprensión del algoritmo se
detallan a continuación.
El algoritmo C4.5 utiliza las siguientes estructuras para su desarrollo:
El C4.5 forma parte de la familia de los TDIDT (Top Down Induction Trees), junto
con antecesor el ID3.
11
El C4.5 se basa en el ID3, por lo tanto, la estructura principal de ambos métodos es
la misma.
El C4.5 construye un árbol de decisión mediante el algoritmo "divide y vencerás" y
evalúa la información en cada caso utilizando los criterios de Entropía, Ganancia o
proporción de ganancia, según sea el caso.
Por otra parte, los árboles de decisión pueden entenderse como una representación de
los procesos involucrados en las tareas de clasificación.
Están formados por:
Nodos: Nombres o identificadores de los atributos.
Ramas: Posibles valores del atributo asociado al nodo.
Hojas: Conjuntos ya clasificados de ejemplos y etiquetados con el nombre de una
clase.
Además, este algoritmo utiliza los siguientes atributos:
Atributos de valores continuos: Inicialmente el algoritmo ID3 se planteó para atributos
que presentaban un número discreto de valores. Se puede 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 se
está 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".
12
Atributos con valores perdidos: En ciertos casos existen atributos de los cuales se conoce
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í se conoce 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 se pueden 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
Por otra parte, el algoritmo C4.5 ha tenido varias aplicaciones entre las cuáles se
mencionan:
Simulación de equipos.
Diagnósticos médicos
Resolución de problemas de clasificación y predicción
Aprendizaje en la WWW.
Modelado de conocimiento.
Sistemas Expertos.
El pseudocódigo para implementar el algoritmo C4.5, según Espino (2003), es el siguiente:
Función C4.5
R: Conjunto de atributos no clasificados.
C: Atributo clasificador.
S: Conjunto de entrenamiento, devuelve un árbol de decisión.
Comienzo
13
Si S está vacío,
Devolver el único nodo con Valor Falla; para formar el nodo raíz.
Si todos los registros de S tienen el mismo valor del atributo clasificador,
Devolver un único nodo con dicho valor; un único 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, S1),
C4.5(R-{D}, C, S2),
…,
C4.5(R-{D}, C, Sm);
Fin
En el algoritmo C4.5 de Quinlan, se destacan las mejoras del uso de atributos continuos,
atributos desconocidos y poda. Por ello, se mencionarán a continuación y serán mostradas
a detalle en los ejemplos posteriores de este documento.
14
Atributos continuos.
Cuando se trabaja con atributos continuos se ordenan los valores que tiene dicho atributo
ascendentemente, especificando la clase a la que pertenecen. Además, se verifican los
puntos de corte (que son los posibles umbrales que puede tener) que son analizados para
la construcción del árbol de decisión.
Atributos desconocidos.
Cuando se trabaja con atributos desconocidos hay que tomar en cuenta algunas variantes
a la hora de realizar los cálculos, las cuales son:
Cuando se realiza la distribución para la clase que posee el atributo desconocido, el
cálculo de la entropía del conjunto se hace sin tomar en cuenta los valores
asociados al atributo desconocido.
Para el mismo caso anterior, cuando se calcula la información de la división se
debe tomar en cuenta el atributo desconocido, como una categoría extra.
Luego de haber realizados todos los cálculos, en el caso anterior, se verifica por
cuál atributo es conveniente dividir, para continuar con la construcción del árbol, a
cada atributo conocido de la clase se le agrega el atributo desconocido colocándole
un peso que corresponde al resultado de dividir los pesos de los atributos
conocidos entre el número total de atributos conocidos.
Para el resto de clases que no poseen un atributo desconocido no se toman en
cuenta los casos anteriores, sino que se realizan los cálculos normalmente.
Poda.
El algoritmo C4.5 utiliza la post-poda basada en el cálculo del error, esto lo hace para el
árbol completo que se ha obtenido como resultado.
Para ello se hace lo siguiente:
Para cada nodo se hace el cálculo de 2 errores (A y B):
A: Estimación error objetivo si no se poda el nodo.
B: Estimación error objetivo si se poda el nodo.
Se verifica la condición B<A (o A>B), si es verdadera se poda el nodo.
15
Para calcular la estimación del error si no se poda el nodo (A), se hace lo siguiente para
cada nodo hoja:
Se definen los siguientes datos (representados en las ecuaciones: Ec.2.4, Ec.2.5 y Ec.2.6):
(Ec.2.4)
(Ec.2.5)
(Ec.2.6)
Y se aplica la fórmula de la Ec.2.7 para calcular la estimación del error:
√
(Ec.2.7)
Luego de tener todos los datos, se calcula A como la suma de N*q correspondiente a cada
nodo.
Para calcular la estimación del error si se poda el nodo (B) se hacen los mismos cálculos
anteriores, pero aplicado a todo el árbol (una solo hoja).
Reglas.
Las reglas son construidas a partir del árbol de decisión que genera el algoritmo C4.5.
Características:
Su representación tiene básicamente la estructura Si <condición> Entonces
<clase>.
Se crea una regla por cada camino desde la raíz hasta una hoja del árbol.
El algoritmo C4.5, en particular, realiza una poda de las reglas obtenidas.
El pseudocódigo del algoritmo para obtener reglas del C4.5 es el siguiente:
16
ObtenerReglas (árbol) { Convertir el árbol de decisión (árbol) a un conjunto de reglas, R error = error de clasificación con R Para cada regla Ri de R Hacer
Para cada precondición pj de Ri Hacer nuevoError = error al eliminar pj de Ri Si nuevoError <= error Entonces
Eliminar pj de Ri error = nuevoError
Si Ri no tiene precondiciones Entonces Eliminar Ri
}
Cross Validation.
También conocido como validación cruzada. Es un método que se utiliza para prevenir el
sobreajuste en los modelos que se construyen (en este caso, el árbol de decisión que se
genera). Principalmente lo que busca este método es intentar estimar qué tan bien el
modelo predecirá los datos que aún no se han visto. Además, este método se puede
utilizar con cualquier otro método para la construcción de árboles.
Consiste en dividir el conjunto de casos en K subconjuntos del mismo tamaño. Se utilizan
K-1 subconjuntos como datos de entrenamiento y un subconjunto como datos de test. El
procedimiento se repite para los K subconjuntos y se calcula la media de la evaluación.
(Suele utilizarse un K=10).
17
CAPÍTULO 3: METODOLOGÍA
Para el desarrollo de este proyecto se utilizará la metodología de SCRUM
(http://www.proyectosagiles.org/que-es-scrum), la cual consiste en entregas parciales y
regulares del producto final.
En SCRUM un proyecto se ejecuta en bloques temporales cortos y fijos (iteraciones de un
mes natural y hasta de dos semanas, si así se necesita), así como se muestra en la figura
2.1. Cada iteración tiene que proporcionar un resultado completo, un incremento de
producto final que sea susceptible de ser entregado con el mínimo esfuerzo al cliente
cuando lo solicite.
Para ello se utilizarán algunas plantillas para detallar los avances que cada integrante
realice y las actividades del proyecto.
Figura 3.1: Metodología SCRUM
18
Además, para la implementación de este proyecto se utilizará el sistema operativo
Windows XP y como herramienta de programación el Microsoft Visual Studio V.6.0 para
C++, debido a que estos son los requerimientos solicitados para poder desarrollar en el
software de AIPI.
19
CAPÍTULO 4: PRESENTACIÓN, ANÁLISIS E INTERPRETACIÓN DE LOS RESULTADOS
Para comprender de una mejor manera el por qué se incorpora el algoritmo C4.5 al
proyecto AIPI, se ha realizado un cuadro comparativo (Tabla 4.1) entre el algoritmo ID3 y
el algoritmo C4.5 donde se indican las mejoras que incorpora el algoritmo C4.5.
CUADRO COMPARATIVO ENTRE ALGORITMOS
ID3 C4.5
Manejo de atributos discretos Manejo de atributos continuos y discretos
Manejo solo de atributos conocidos Manejo de atributos desconocidos
Los árboles construidos nunca son demasiado grandes
Poda de árboles después de ser construidos, para evitar el sobreajuste de datos
No verifica acerca de los errores producidos en la poda
Reduce los errores en la poda
No escoge rangos de medida de un conjunto de datos
Puede escoger un rango de medida apropiado
Tabla 4.1: Cuadro comparativo entre algoritmo ID3 y C4.5
Como se puede observar, en la Tabla 4.1, el algoritmo C4.5 posee más ventajas que el ID3
en todos los aspectos mencionados (C4.5(2005-II-B).pdf).
Cabe mencionar que, dentro de la investigación bibliográfica realizada, se encontró el
algoritmo C4.5 implementado en lenguaje C, por el autor Quinlan, y se tomó como base
para terminar de comprender el funcionamiento y realizar las posteriores modificaciones
para AIPI.
A continuación, se presentarán algunos ejemplos correspondientes a las mejoras de
atributos continuos, atributos desconocidos y a la poda correspondientes a este
algoritmo.
Dichos ejemplos han sido desarrollados con todos los cálculos y el árbol resultante es igual
al generado por el algoritmo implementado.
El siguiente ejemplo, incluye la utilización de atributos desconocidos y la poda.
20
EJEMPLO 1: JUGAR GOLF
CLIMA TEMPERATURA HUMEDAD CLASE
1 ? Alta Leve No
2 Soleado Alta Fuerte No
3 Nublado Alta Leve Si
4 Lluvia Alta Leve Si
5 Lluvia Normal Leve Si
6 Lluvia Normal Fuerte No
7 Nublado Normal Fuerte Si
8 Soleado Alta Leve No
9 Soleado Normal Leve Si
10 Lluvia Normal Leve Si
11 Soleado Normal Fuerte Si
12 Nublado Alta Fuerte Si
13 Nublado Normal Leve Si
14 Lluvia Alta Fuerte Si Tabla 4.1: Casos (ejemplo jugar golf)
Para este ejemplo, se tiene un total de 14 casos, como se muestra en la Tabla 1.
Para comenzar se toma por el atributo CLIMA, como se muestra en la Tabla 2:
? Soleado Nublado Lluvia Total por clase (sin incluir atributo
desconocido)
Si 0 2 4 4 10
No 1 2 0 1 3
Total de casos 1 4 4 5 13 Tabla 4.2: División de los datos por el atributo clima
Se realizan los cálculos de la siguiente información:
La entropía es la medida de la incertidumbre que hay en un sistema. Es decir, ante una
determinada situación, la probabilidad de que ocurra cada uno de los posibles resultados
(Tutorial - ML_Ejercicios Algoritmo ID3.pdf). Este valor se calcula con la Ec. 4.1 para todo
el conjunto y con la Ec. 4.2 para los atributos.
21
La ganancia es la diferencia entre la entropía del conjunto y la entropía de los atributos y
se calcula utilizando la Ec 4.3 (Tutorial - ML_Ejercicios Algoritmo ID3.pdf).
La información de la división representa la información potencial generada al dividir un
atributo en un número n de subconjuntos. Es calculada utilizando la Ec. 4.4 (C4.5(2005-II-
B).pdf).
La proporción de la ganancia (técnica del Gain Ratio) es una medida basada en
información que considera diferentes números y diferentes probabilidades de los
resultados de las pruebas. Este valor es calculado utilizando la Ec. 4.5 (C4.5(2005-II-B).pdf).
Se calcula la entropía del conjunto, sin tomar en cuenta los atributos desconocidos:
(Ec. 4.1)
Donde,
= 10 (Total para la clase Si, sin incluir el atributo desconocido)
= 3 (Total para la clase No, sin incluir el atributo desconocido)
= 13 (Total de casos conocidos)
Ahora se calcula la entropía (de los atributos) y la ganancia al dividir el conjunto por el
atributo CLIMA:
∑
(Ec. 4.2)
Donde,
22
Cada sumando representa a un atributo conocido.
= El cociente del total de casos correspondiente a un atributo
conocido y el total de casos conocidos.
se obtiene de los valores tomados de la
tabla 4.3, realizando lo mismo que se explicó anteriormente.
(
)
(
)
(
)
(Ec. 4.3)
Luego se calcula la información de la división, para ello hay que tomar en cuenta el
atributo desconocido:
∑
(Ec. 4.4)
Finalmente se calcula la proporción de la ganancia:
23
(Ec. 4.5)
Ahora se realizan los mismos cálculos para el atributo temperatura, como se muestra en la
Tabla 4.4:
Alta Normal Total por clase
Si 4 6 10
No 3 1 4
Total de casos 7 7 14 Tabla 4.3: División de los datos por el atributo temperatura
(
)
(
)
24
Luego, se realizan los mismos cálculos para el atributo humedad, como se muestra en la
Tabla 4.5:
Leve Fuerte Total por clase
Si 6 4 10
No 2 2 4
Total de casos 8 6 14 Tabla 4.4: División de los datos por el atributo humedad
(
)
(
)
Conviene dividir el árbol por el atributo CLIMA (debido a que la ganancia es mayor para este, y la información de la división también)
25
La división de los datos sería la siguiente (a cada valor del atributo se le agrega el atributo desconocido):
Para soleado (Tabla 4.6):
CLIMA TEMPERATURA HUMEDAD CLASE PESO
Soleado Alta Fuerte No 1
Soleado Alta Leve No 1
Soleado Normal Leve Si 1
Soleado Normal Fuerte Si 1
? Alta Leve No 4/13=0.3 Tabla 4.6: Datos para el valor soleado, del atributo clima
El peso que se le coloca al atributo desconocido corresponde al total del peso de los atributos conocidos entre el número de casos conocidos.
Temperatura (Tabla 4.7):
Alta Normal
Si 0 2 2
No 2.3 0 2.3
2.3 2 4.3 Tabla 4.5: Datos del atributo temperatura, para el valor soleado
(
)
(
)
26
Valores N y E (Tabla 4.8):
N 4.3
E 2.3 Tabla 4.6: Valores N y E, para temperatura (valor soleado)
N: Cantidad de casos cubiertos por la hoja.
E: Cantidad de casos cubiertos incorrectamente por la hoja.
Humedad (Tabla 4.9):
Leve Fuerte
Si 1 1 2
No 1.3 1 2.3
2.3 2 4.3 Tabla 4.7: Datos del atributo humedad, para el valor soleado
(
)
(
)
27
Valores N y E (Tabla 4.10):
N 4.3
E 2.3 Tabla 4.8: Valores N y E, para humedad (valor soleado)
Para Nublado (Tabla 4.11):
CLIMA TEMPERATURA HUMEDAD CLASE PESO
Nublado Alta Leve Si 1
Nublado Normal Fuerte Si 1
Nublado Alta Fuerte Si 1
Nublado Normal Leve Si 1
? Alta Leve No 0.3 Tabla 4.9: Datos para el valor nublado, del atributo clima
Temperatura (Tabla 4.12):
Alta Normal
Si 2 2 4
No 0.3 0 0.3
2.3 2 4.3 Tabla 4.10: Datos del atributo temperatura, para el valor nublado
28
(
)
(
)
Valores N y E (Tabla 4.13):
N 4.3
E 0.3 Tabla 4.11: Valores N y E, para temperatura (valor nublado)
Humedad (Tabla 4.14):
Leve Fuerte
Si 2 2 4
No 0.3 0 0.3
2.3 2 4.3 Tabla 4.12: Datos del atributo humedad, para el valor nublado
29
(
)
(
)
Valores N y E (Tabla 4.15):
N 4.3
E 0.3 Tabla 4.13: Valores N y E, para humedad (valor nublado)
30
Para Lluvia (Tabla 4.16):
CLIMA TEMPERATURA HUMEDAD CLASE PESO
Lluvia Alta Leve Si
Lluvia Normal Leve Si 1
Lluvia Normal Fuerte No 1
Lluvia Normal Leve Si 1
Lluvia Alta Fuerte Si 1
? Alta Leve No 0.4 Tabla 4.14: Datos para el valor lluvia, del atributo clima
Temperatura (Tabla 4.17):
Alta Normal
Si 2 2 4
No 0.4 1 1.4
2.4 3 5.4 Tabla 4.15: Datos del atributo temperatura, para el valor lluvia
(
)
(
)
31
Valores N y E (Tabla 4.18):
N 5.4
E 1.4 Tabla 4.16: Valores N y E, para temperatura (valor lluvia)
Humedad (Tabla 4.19):
Leve Fuerte
Si 3 1 4
No 0.4 1 1.4
3.4 2 5.4 Tabla 4.17: Datos del atributo humedad, para el valor lluvia
(
)
(
)
32
Valores N y E (Tabla 4.20):
N 5.4
E 1.4 Tabla 4.18: Valores N y E, para humedad (valor lluvia)
Luego de estos cálculos, se puede observar que para el estado NUBLADO independientemente del valor de sus otros atributos siempre se podrá jugar golf. Para el estado LLUVIA, el atributo que tiene mayor ganancia es HUMEDAD por lo cual se puede dividir por dicho atributo. Para el estado SOLEADO, el atributo con mayor ganancia es TEMPERATURA por lo cual se puede dividir por dicho atributo.
El árbol se encuentra de la siguiente manera (Figura 4.1):
Figura 4.1: Árbol de decisión generado
33
Ahora, para analizar si se puede podar el árbol generado se utilizarán los datos de N y E
(que aparecen en cada hoja del árbol) los cuáles indican los casos cubiertos por la hoja y
los casos cubiertos incorrectamente por la hoja.
Para realizar la poda, para cada nodo se debe calcular la estimación del error si no se poda
el nodo (representado por A) y la estimación del error si se poda el nodo (representado
por B). Y luego, se verifica si la estimación del error si no se poda el nodo es mayor que la
estimación del error si se poda el nodo (A>B o B<A), entonces se procede al recorte
correspondiente.
Para calcular la estimación del error si no se poda el nodo (representado por A), se hace lo
siguiente para cada nodo hoja:
Se definen los siguientes datos:
F representa la división entre E y N, donde E representa el número de datos mal
clasificados y N el número total de datos. Dicho valor se calcula utilizando la Ec. 4.6.
En el algoritmo C4.5, para la estimación del error de utiliza un intervalo de confianza de
25%, el cual con una aproximación gaussiana corresponde a Z=0.69
(Arboles_de_Decisi_n_3.pdf). Dicho valor está representado en la Ec. 4.7.
Y finalmente, N representa el número de casos cubiertos por la hoja que se está
evaluando. Este valor se puede observar en la Ec. 4.8.
(Ec. 4.6)
(Ec. 4.7)
(Ec. 4.8)
34
Y se aplica la siguiente fórmula (Ec. 4.9) de probabilidad para calcular la estimación del
error:
√
(Ec. 4.9)
Para N1:
√
Para N2:
√
35
Para N3:
√
Para N4:
√
Luego, de tener la estimación del error para cada nodo se calcula A (estimación del error si
no se poda el nodo) utilizando la Ec. 4.10:
∑
(Ec. 4.10)
36
Para calcular la estimación del error si se poda el nodo (representado por B) se hacen los
mismos cálculos anteriores para cada hoja, pero aplicado a todo el árbol (una solo hoja):
√
Luego, se calcula B (estimación del error si se poda el nodo) utilizando la Ec. 4.11:
(Ec. 4.11)
Ahora, con A=6.52023 y B=5.2458 se hace la verificación.
Como A>B es verdadera, entonces se poda el árbol, colapsándolo a una sola hoja (Figura
4.2).
37
Figura 2.2: Árbol de decisión podado
38
EJEMPLO 2: ATRIBUTOS CONTINUOS.
Casos, se muestran en la Tabla 4.21:
ID X1 X2 X3 Class
1 A 70 true C1
2 A 90 true C2
3 A 85 false C2
4 A 95 false C2
5 A 70 false C1
6 B 90 true C1
7 B 78 false C1
8 B 65 true C1
9 B 75 false C1
10 C 80 true C2
11 C 70 true C2
12 C 80 false C1
13 C 80 false C1
14 C 96 false C1
El cálculo de la entropía del conjunto se realiza con la Ec. 4.12.
∑
| | (
| |)
Ec. 4.12
: Número de muestras en S que pertenecen a la clase Ci de k
clases
|S|: Conjunto de muestras en el conjunto S
La ecuación para calcular la entropía total del conjunto es la siguiente:
Frecuencia Clase C1: 9
Frecuencia Clase C2: 5
Total: 14
Entropía del conjunto: 0.940285959
Tabla 4.19: Casos (ejemplo de atributos continuos)
39
(
)
(
)
Primero, sacamos la información de todos los atributos dados, el tributo que tenga la
mayor ganancia será el elegido para obtener el primer elemento que formará el árbol de
decisión.
Información del atributo X3 (Tabla 4.22)
Atributo X3
true false Total
C1 3 6 9
C2 3 2 5
Total 6 8 14
Entropía: 0.89215893
Ganancia: 0.04812703
Tabla 4.20: Información del atributo
La entropía para el atributo X3, al igual que la entropía total del conjunto, se calcula con la
Ec. 4.13 de la siguiente manera:
[
(
)
(
)]
[
(
)
(
)]
La ganancia se calcula con la Ec. 2.2, restando a la entropía total del conjunto, la entropía
del atributo, para este caso:
Ec 4.13
Información del atributo X1 (el procedimiento para encontrar la entropía y la
ganancia es igual al del caso anterior) (Tabla 4.23)
40
Atributo X1
A B C Total
C1 2 4 3 9
C2 3 0 2 5
Total 5 4 5 14
Entropía: 0.69353614
Ganancia: 0.24674982
Tabla 4.21: Información del atributo
Información del atributo X2
Primero, ordenamos los valores continuos en orden ascendente. Luego, para sacar los
posibles umbrales (threshold value), realizamos la siguiente operación:
Es decir, se suma el elemento a con su sucesor y se divide entre 2 tomando en cuenta las
siguientes reglas:
- No se divide el intervalo si el siguiente ejemplo pertenece a la misma clase que el actual.
-No se divide el intervalo si el siguiente ejemplo tiene el mismo valor que el actual.
Para nuestro ejemplo, los posibles umbrales son: 72.5, 79, 82.5 y 92.5. Para cada uno de
estos valores se debe sacar la información (similar a sacar la información de un atributo)
para determinar cuál es el mejor candidato (Tabla 4.22).
Atributo X2
65 70 70 70 75 78 80 80 80 85 90 90 95 96
C1 C1 C1 C2 C1 C1 C2 C1 C1 C2 C2 C1 C2 C1
72.5 79 82.5 92.5 Tabla 4.22: Posibles umbrales
41
Umbral(threshold) 72.5 valores ≤ clase C1 3
valores ≤ clase C2 1 Info(≤72.5)= 0.81127812
Total valores ≤ 4
valores ˃ clase C1 6 valores ˃ clase C2 4 Info(˃72.5)= 0.97095059
Total valores ˃ 10
Info(72.5)= 0.92532989
Ganancia= 0.01495607 Tabla 4.23: Cálculos para el umbral 72.5
Para encontrar el valor de la información para el valor 72.5 (Tabla 4.23) primero se calcula
la información para los valores menores o iguales a este y para los valores mayores con la
Ec. 4.12 de la siguiente forma:
(
)
(
)
(
)
(
)
Teniendo estos cálculos, la información para el valor 72.5 se obtiene de la siguiente
manera:
Y la ganancia al igual que los casos anteriores, se calcula con la Ec. 2.2 de la siguiente
forma:
El mismo procedimiento se sigue para los demás valores (Tabla 4.24, 4.25 y 4.26).
42
Umbral(threshold) 79 valores ≤ clase C1 5
valores ≤ clase C2 1
Info(≤ 79)= 0.65002242
valores Total ≤ 6
valores ˃ clase C1 4 valores ˃ clase C2 4
Info(˃ 79)= 1
valores Total ˃ 8
Info(72.5)= 0.85000961
Ganancia= 0.09027635 Tabla 4.24: Cálculos para el umbral 79
Umbral 82.5 valores ≤ clase
C1 7 valores ≤ clase
C2 2
Info(≤ 2.5)= 0.76420451
valores Total ≤ 9
valores ˃ clase C1 2
valores ˃ clase C2 3
Info(˃82.5)= 0.97095059
valores Total ˃ 5
Info(72.5)= 0.8380424
Ganancia= 0.10224356 Tabla 4.25: Cálculos para el umbral 82.5
Umbral 92.5 valores ≤ clase C1 8
valores ≤ clase C2 4
Info(≤82.5)= 0.91829583
valores Total ≤ 12
valores ˃ clase C1 1 valores ˃ clase C2 1
Info(˃2.5)= 1
valores Total ˃ 2
Info(72.5)= 0.92996786
Ganancia= 0.0103181 Tabla 4.26: Cálculos para el umbral 92.5
43
Una vez teniendo todos los resultados podemos determinar que el valor (de los posibles
umbrales) que tiene mayor ganancia es el 82.5. Por lo tanto, la ganancia para el atributo
X2 es 0.0103.
Una vez teniendo la información de todos los atributos, se puede ver que el atributo que
representa mayor ganancia es el atributo X1, por lo tanto, se elige este atributo para
empezar a formar el árbol que quedaría como en la Figura 4.3:
Figura 4.3: Primer división para formar el árbol de decisión
Ahora, realizamos el mismo procedimiento descrito anteriormente con cada uno de los 3
subconjuntos que resultaron para obtener las otras ramas del árbol de decisión.
Seguiremos con el subconjunto de X1 = A (Tabla 4.27).
X2 X3 Class 70 true C1 90 true C2 Frecuencia Clase C1: 2
85 false C2 Frecuencia Clase C2: 3
95 false C2 Total: 5
70 false C1
Entropía del conjunto: 0.97095059
Tabla 4.27: Subconjunto de X1
Información del atributo X3 (Tabla 4.28)
Atributo X3
true false Total
C1 1 1 2
C2 1 2 3
Total 2 3 5
Entropía: 0.9509775
Ganancia: 0.01997309
Tabla 4.28: Información del atributo
X2 X3 Class X2 X3 Class X2 X3 Class
70 true C1 90 true C1 80 true C2
90 true C2 78 false C1 70 true C2
85 false C2 65 true C1 80 false C1
95 false C2 75 false C1 80 false C1
70 false C1 96 false C1
X1
A B C
44
X2 X3 Class
70 true C1
90 true C2
85 false C2
95 false C2
70 false C1
X2
X3 Class X3 Class
true C1 false C2
false C1 true C2
false C2
≤ 77.5 ˃ 77.5
Información del atributo X2 (Tabla 4.29 y Tabla 4.30)
Para este caso, solo tenemos un posible valor umbral (threshold value) que es 77.5.
Atributo X2
70 70 85 90 95
C1 C1 C2 C2 C2
77.5 Tabla 4.29: Posibles umbrales
X2 ≤ 77.5 X2 ˃ 77.5 Total
C1 2 0 2
C2 0 3 3
Total 2 3 5
Entropía: 0
Ganancia: 0.97095059
Tabla 4.30: Información del atributo
El cálculo de la ganancia nos da como resultado 0.970, mayor a la ganancia del atributo
X3, por lo tanto el subconjunto se ramifica como se muestra en la Figura 4.4:
Quedando el árbol como en la Figura 4.5:
Figura 4.4: Ramificación por el conjunto X3
45
Figura 4.5: Árbol de decisión resultante
A continuación seguimos con el subconjunto para X1=C. Los valores con X1=B quedan tal
cual están ya que todos los valores pertenecen a la misma clase; C1 para el caso (Tabla
4.31).
X2 X3 Class 80 true C2 Frecuencia Clase C1: 3
70 true C2 Frecuencia Clase C2: 2
80 false C1 Total: 5
80 false C1 96 false C1
Entropía del conjunto: 0.97095059
Tabla 4.31: Subconjunto para X1
X1
X2 X3 Class X2 X3 Class X2 X3 Class
70 true C1 90 true C1 80 true C2
90 true C2 78 false C1 70 true C2
85 false C2 65 true C1 80 false C1
95 false C2 75 false C1 80 false C1
70 false C1 96 false C1
X2
X3 Class X3 Class
true C1 false C2
false C1 true C2
false C2
C
≤ 77.5 ˃ 77.5
A B
46
X2 X3 Class X2 X3 Class X2 X3 Class
70 true C1 90 true C1 80 true C2
90 true C2 78 false C1 70 true C2
85 false C2 65 true C1 80 false C1
95 false C2 75 false C1 80 false C1
70 false C1 96 false C1
X2 X3
X3 Class X3 Class X2 Class X2 Class
true C1 false C2 80 C2 80 C1
false C1 true C2 70 C2 80 C1
false C2 96 C1
false
X1
A B C
≤ 77.5 ˃ 77.5 true
Información del atributo X3 (Tabla 4.32)
Atributo X3
true false Total
C1 0 3 2
C2 2 0 3
Total 2 3 5
Entropía: 0
Ganancia: 0.97095059
Tabla 4.32: Información del atributo
Información del atributo X2 (Tabla 4.33)
Para este caso, no hay candidato para tomar un valor umbral, por lo tanto se selecciona al
atributo X3.
Finalmente, el árbol formado queda como se muestra en la Figura 4.6:
Atributo X2
70 80 80 80 96
C2 C2 C1 C1 C1
80 Tabla 4.33: Posibles umbrales
Figura 4.6: Árbol formado
47
Si ejecutamos el algoritmo de Quinlan con este caso de ejemplos, el árbol obtenido es
igual, excepto por una pequeña variante: la división en el atributo continuo X2 la hace con
y y no con el valor 77.5 obtenido en nuestros cálculos. El árbol generado
es el que se presenta a continuación, en la Figura 4.7:
Figura 4.7: Árbol de decisión
Haciendo una revisión exhaustiva sobre el código del algoritmo de Quinlan, se puede
determinar que los cálculos efectuados son los mismos hechos en este ejemplo. Pero una
vez hecho estos cálculos, al momento de presentar el árbol en consola y guardarlo, se
manda a llamar la función, que se presenta en la Figura 4.8, que selecciona el menor valor
más próximo al umbral (o threshold value):
48
Figura 4.8: Función que selecciona el menor umbral
Si se modifica esta función y se retorna el valor t que se recibe como segundo de la
siguiente manera (Figura 4.9):
49
Figura 4.9: Función que selecciona el menor umbral modificada
El árbol generado en este caso es exactamente igual al del ejemplo desarrollado (Figura
4.10):
Figura 4.10: Árbol de decisión generado con la función modificada
50
Una posible explicación del porqué el algoritmo de Quinlan realiza este procedimiento de
buscar al menor valor más próximo al umbral es que al momento de presentar los datos al
usuario, busca que, para los atributos continuos, el valor threshold sea un número que
este dentro de los casos del ejemplo. Para este caso, el valor 77.5 no está dentro de los
casos presentados en el atributo X2, en cambio el valor de 75 sí.
Es decir que al final el algoritmo busca presentar información que este dentro de la
misma data con la que trabaja.
Luego, de la presentación de los ejemplos para una comprensión un poco más detallada
del algoritmo se presenta la construcción de los árboles de decisión utilizando el algoritmo
C4.5 incluido en el software AIPI.
Primeramente, para incorporar el algoritmo C4.5 en el software AIPI se creó un nuevo
módulo en dicho proyecto, el cual se denominó AIPI_DecisionTree en el árbol del
proyecto. Este contiene todos los archivos necesarios (de extensión .h y .cpp) para la
implementación del algoritmo, como se muestra en la Figura 4.11:
Figura 4.11: Árbol de la solución del proyecto
51
Ahora se mostrará en la Figura 4.12, el entorno de trabajo de AIPI en el cuál se ha
implementado el algoritmo.
Como se puede observar en la Figura 4.13, las áreas marcadas con un recuadro azul son en
las que se han agregado algunos controles para la implementación del algoritmo. En el
área de menú en la opción Build se agregó la opción C4.5 con tres diferentes opciones, las
cuales permiten generar el árbol podado, el árbol no podado y las reglas de la información
que se ha cargado previamente. En las pestañas que se encuentran en la parte inferior
izquierda se muestran en cuadros de texto la información relacionada a la generación del
árbol de decisión (se incluye: error de la poda, matriz de confusión del cross validation y
las reglas). Finalmente, en el recuadro marcado en la parte inferior derecha, es dónde se
dibuja el árbol generado por el algoritmo.
Lo mencionado anteriormente se mostrará en la Figura 4.13 y Figura 4.14, ya con toda la
información correspondiente a un árbol no podado, en su respectiva área:
Figura 4.12: Entorno de trabajo
52
Continuando se mostrará en la Figura 4.15 y en la Figura 4.16 la generación de un árbol
podado, al igual que en el caso anterior:
Figura 4.13: Ejecución del algoritmo generando un árbol no podado
Figura 4.14: Generación de un árbol no podado utilizando el algoritmo C4.5
53
Figura 4.16: Generación de un árbol podado utilizando el algoritmo C4.5
Figura 4.15: Ejecución del algoritmo generando un árbol podado
54
Después de haber visto un poco del funcionamiento del algoritmo en el software AIPI, se
presentarán algunos ejemplos de generación de árboles de decisión comparándolos con el
software WEKA. Se mostrarán los árboles generados y el tiempo que se tarda cada
software en ejecutar el algoritmo para la generación del árbol de decisión.
Uno de los ejemplos se muestra en la Figura 4.17 en WEKA y en la Figura 4.18 en AIPI
donde se puede observar la generación del árbol de decisión:
Figura 4.17: Árbol de decisión del ejemplo iris generado en WEKA
55
Como se puede observar en ambas figuras los árboles de decisión generados por el
algoritmo C4.5 (llamado algoritmo J48 en WEKA) son iguales. Además, en cuánto al
tiempo de generación, del árbol de decisión, es más rápido el del software AIPI que el de
WEKA, y en ocasiones se tarda el mismo tiempo.
El siguiente ejemplo, de generación del árbol de decisión, se muestra en la Figura 4.19 el
generado por WEKA y en la Figura 4.20 el generado por AIPI:
Figura 4.18: Árbol de decisión del ejemplo iris generado por AIPI
56
Figura 4.19: Árbol de decisión del ejemplo laborneg generado en WEKA
Figura 4.20: Árbol de decisión del ejemplo laborneg generado en AIPI
57
En la Figura 4.21 y Figura 4.22, se muestra otro ejemplo que tiene más datos de entrada:
Figura 4.22: Árbol de decisión del ejemplo vote generado en AIPI
Como se puede observar en los tres ejemplos los árboles de decisión generados por el
algoritmo C4.5 (llamado algoritmo J48 en WEKA) son iguales.
Figura 4.21: Árbol de decisión del ejemplo vote generado en WEKA
58
Los resultados de los tiempos se resumen en la Tabla 4.34.
EJEMPLO TIEMPO EN WEKA (Segundos) TIEMPO EN AIPI (Segundos)
Iris 0.03 0.02
Laborneg 0.02 0.04
Vote 0.05 0.1
Tabla 4.34: Resumen de los tiempos
La diferencia en los tiempos entre ambas aplicaciones puede deberse a lo siguiente:
AIPI realiza la carga de datos al momento de construir el árbol de decisión (tiempo
que es tomado en cuenta), mientras que en WEKA se desconoce si realiza la carga
de datos al abrir los archivos o lo hace al momento de procesar el árbol de
decisión.
El tiempo tomado por AIPI es únicamente del cálculo y generación de los nodos del
árbol de decisión, en cambio WEKA (por lo que se observó) toma en cuenta el
cálculo del árbol y la impresión en consola del mismo.
Otros factores que también se deben considerar son: la carga del sistema
operativo al momento de realizar la generación del árbol de decisión, los
compiladores ya que ambos programas están desarrollados en diferentes
lenguajes y de diferente forma.
59
CAPÍTULO 5: CONCLUSIONES Y RECOMENDACIONES
5.1 CONCLUSIONES
Debido a la poca documentación existente acerca del algoritmo C4.5, durante el
desarrollo de la presente tesis, no se encontró todo lo correspondiente a las mejoras que
presenta (atributos continuos, atributos desconocidos y poda), por ello muchos detalles se
dedujeron del código original de Quinlan. Se hicieron ejemplos con cálculos hechos a
mano y se probó la veracidad de estos con el software AIPI, el WEKA y el código del
algoritmo original del C4.5 (que se encuentra en lenguaje C), obteniendo el mismo
resultado de ambas formas y comprobando de esta manera la teoría con la práctica.
Weka y el algoritmo C4.5 original hecho por Quilan, necesitan dos archivos para generar el
árbol de decisión mientras que el módulo que se implementó en AIPI ocupa sólo un
archivo. Al leer un sólo archivo se tienen algunos costos como tener que recorrer toda la
data para determinar los posibles valores de un atributo.
El algoritmo se implementó con una mejora con respecto a WEKA a la hora de leer los
datos, debido a que WEKA no se puede ejecutar si encuentra espacios en blanco en la
data, mientras que el nuevo módulo implementado del C4.5, en AIPI, no tiene ningún
problema de leer dichos espacios.
Una ventaja del módulo desarrollado en AIPI es que se pueden seleccionar los atributos
que se desean procesar, a diferencia del algoritmo original desarrollado por Quinlan.
En AIPI se optimizó el método para dibujar el árbol, el cuál posee una estructura que anteriormente se dibujaba con cada cálculo. En el nuevo módulo implementado el árbol se dibuja hasta el final de la generación de la estructura, esto permite ahorrar memoria al no crear objetos por cada cálculo. Para el módulo implementado se llegó a la conclusión que para ejemplos que tienen aproximadamente más de 31,000 registros es necesario incrementarle la memoria al stack, debido a que el espacio de memoria se acaba aproximadamente con ese número de registros. Además se investigó que por defecto el stack para las aplicaciones (en nuestro caso la aplicación AIPI) viene con un tamaño de 1MB. Por lo tanto para cargar la data de un archivo que contenga 60,000 registros se debe cambiar tamaño del stack a 3MB para que el algoritmo pueda funcionar correctamente. Cuando se modificó el algoritmo C4.5 de Quinlan, creado en C de Linux, y se migro a C++ de Microsoft, se separaron en varias funciones la matriz de confusión, el error, la poda e impresión del árbol como una mejora para la identificación de dichas partes en el código fuente.
60
La diferencia de tiempo entre la ejecución de WEKA y AIPI existe por diversos motivos
(anteriormente explicados en el capítulo de Presentación, análisis e interpretación de los
resultados). Además, no es válida debido a las condiciones de la ejecución y a que los
lenguajes en que se han programado los software son muy diferentes. Sin embargo AIPI
consta de una interfaz amigable y de muchas opciones que vuelven más completo el
software, por lo cual se considera que es mejor para la generación de árboles de desición.
5.2 RECOMENDACIONES
Cuando se utilice software para la generación de árboles de decisión es importante que la
persona indague sobre el tema, debido a que existe una amplia gama de algoritmos para
la generación de dichos árboles de inducción que permiten predecir información a partir
de los datos que se le brinde en el problema. Todo esto para que pueda elegir el algoritmo
que mejor se adapte al problema que desea resolver y que lo haga de forma eficaz.
Además, es importante mencionar que existe poca información referida al algoritmo C4.5,
lo cual no permite que la investigación sea rápida. Así como sucede este problema, con
este algoritmo, existen muchos otros algoritmos con el mismo problema. Por ello, cada
pequeño aporte de las personas que se dedican a la investigación de estos temas es muy
importante para continuar estos estudios. Y este es un pequeño aporte para dicha
investigación.
También, sería importante que en el país se realizaran investigaciones científicas sobre
temas de inteligencia artificial, las cuales puedan brindar una mayor información sobre
estos temas para que las personas se interesen en el desarrollo de software de minería de
datos (similar a AIPI). Para ello, se podrían incluir cursos relacionados al tema para que
cualquier estudiante o persona pueda conocer acerca de estos temas.
Se recomienda la utilización del software AIPI para la creación de árboles de decisión, ya
que el módulo del algoritmo C4.5 está basado en el algoritmo original de Quinlan.
Además, el software posee características especiales como la posibilidad de guardar
árboles ya generados, construir árboles a partir de data en base de datos, la posibilidad de
modificar la información antes de generar el árbol, entre otras.
61
REFERENCIAS
QUINLAN, J. ROSS (1993). C4.5_Programs_for_Machine_Learn. United States of
America: morgan kaufmann publishers,Inc.
EBooks:
Tutorial - ML_Ejercicios Algoritmo ID3.pdf, Ing. Bruno López Takeyas.
resumenArbolesInduccion.pdf (Autor: No aparece)
Árboles de Decisión (pdf), Carlos Hurtado, Departamento de Ciencias de la
Computación, Universidad de Chile.
Algoritmo-c45-Arboles-de-Decision.pdf (Autor: No aparece)
131469066-apuntesAD.pdf, José Manuel Molina López y Jesús García Herrero.
Arboles_de_Decisi_n_3.pdf, Carlos Hurtado.
Auxiliar_5_Sobreajuste_y_Poda.pdf, Carlos Hurtado, Pablo Barceló y Gonzalo Ríos.
ICR_BenjamínMoreno.pdf, Benjamín Moreno Montiel.
t10arboles.pdf, Pedro Larragaña, Iñaki Inza y Abdelmalik Moujahid.
Fuentes electrónicas (Todas vigentes desde Marzo a Julio 2013):
http://www.itnuevolaredo.edu.mx/takeyas/Apuntes/Inteligencia%20Artificial/Apuntes
/IA/ID3.pdf
http://www2.cs.uregina.ca/~dbd/cs831/notes/ml/dtrees/c4.5/tutorial.html
http://www.itnuevolaredo.edu.mx/takeyas/Apuntes/Inteligencia%20Artificial/Apuntes
/tareas_alumnos/C4.5/C4.5(2005-II-B).pdf
http://www.metaemotion.com/diego.garcia.morate/download/weka.pdf
http://www.investigacion.frc.utn.edu.ar/labsis/Publicaciones/congresos_labsis/cynthia
/CNIT_2009_Aplicacion_Algoritmos_Weka.pdf
http://programacionlogica.blogspot.com/2005/11/algoritmo-de-aprendizaje-id3.html
http://laboratorios.fi.uba.ar/lsi/servente-tesisingenieriainformatica.pdf
http://www.aipiworks.com/
http://www.proyectosagiles.org/que-es-scrum
ANEXO A
MODIFICACIÓN DE CÓDIGO
A-1
ANEXO A: MODIFICACIÓN DE CÓDIGO
Para la codificación del algoritmo C4.5 se tomó como base el código que Quinlan desarrolló
para implementar dicho algoritmo. Se hicieron muchas modificaciones y correcciones, ya
que el lenguaje de desarrollo era diferente.
A continuación, se mencionan los archivos y en algunos casos las funciones dónde se
hicieron cambios para el desarrollo del algoritmo:
Archivo getnames.h y getdata.h: declaración de nuevas funciones creadas.
Archivo getnames.cpp:
Se modificaron:
int GetNames() int Error(short n,String s1,String s2)
Se crearon: int getClassNameData(); void getAttNameData(); void getAttValNames(int indice); void myTrim(char* cad)
Archivo getdata.cpp:
Se modificaron:
Description GetDescription() int GetData(String Extension)
Se crearon: void validateData(int colSelected) void getRow(int row) void getSelectedData()
Archivo InductionTabView.h: declaración de nuevas variables utilizadas y de nuevas
funciones creadas.
Archivo InductionTabView.cpp:
Se modificaron:
virtual void DoDataExchange(CDataExchange* pDX)
afx_msg void OnSelchangeTabCtrl(NMHDR* pNMHDR, LRESULT* pResult)
A-2
Se crearon:
void mostrarMsg(CString msg)
void limpiar()
void mostrarReglas(CString msg)
void mostrarMatrizDeConfusion(CString msg)
Archivo trees.h: declaración de nuevas funciones creadas.
Archivo tres.cpp:
Se modificaron:
Se crearon:
void mostrarError(CString msg)
void limpiar()
void mostrarReglas(CString msg)
void mostrarMatrizDeConfusion(CString msg)
Archivo besttree.h: cambio en la declaración de la función modificada.
Archivo besttree.cpp:
Se modificó:
CString Evaluate(Tree tunpound,Tree *tpound)
Archivo rules.h: cambio en la declaración de la función modificada.
Archivo rules.cpp:
Se modificó:
PrintIndexedRules
Archivo genrules.h: cambio en la declaración de la función modificada.
Archivo genrules.cpp:
Se modificó:
GenerateRules(Tree T)
Archivo c45rules.h: cambio en la declaración de la función modificada.
Archivo c45rules.cpp:
A-3
Se modificó:
c45rules(Tree T)
Archivo confmat.h: cambio en la declaración de la función modificada.
Archivo confmat.cpp:
Se modificó:
PrintConfusionMatrix
Archivo testrules.h: cambio en la declaración de la función modificada.
Archivo testrules.cpp:
Se modificó:
EvaluateRuleset
Con respecto a los demás archivos que se encuentran en la carpeta Aipi_DecisionTree
todos fueron creados y modificados para el desarrollo del algoritmo. Dichos archivos no
modifican componentes externos sino que sólo los utilizan.
ANEXO B
MANUAL DE USUARIO
B-1
ANEXO B: MANUAL DE USUARIO
A continuación, se presentará la forma en que se ejecuta el módulo del algoritmo C4.5 en
el software AIPI para facilitar su uso.
Para ello se debe realizar lo siguiente:
1. Ejecutar el software AIPI, en la Figura B.1 se pueden observar las áreas
involucradas durante la ejecución del algoritmo C4.5, como son el área de datos, el
área donde se dibuja el árbol y la salida en consola.
Figura B.1: Interfaz del software AIPI
B-2
2. Para ejecutar el algoritmo C4.5 se debe elegir el archivo de ejemplo donde se
encuentran los datos a partir de los cuáles se generará el árbol de decisión, esto se
muestra en la Figura B.2:
3. Después de elegir el archivo los datos del ejemplo, estos se cargarán en un grid
que se encuentra en la pestaña Datos, como se muestra en la Figura B.3:
Figura B.2: Elección de archivo de ejemplo
Figura B.3: Carga de datos
B-3
4. Cuando los datos ya se encuentran cargados, en la pestaña Atributos se
mostrarán, como su nombre lo indica, los atributos que posee el ejemplo donde se
puede elegir cuál será el atributo de salida (Output) en la columna Input/Output
como se muestra en la Figura B.4:
5. También, en la pestaña Atributos se puede elegir el tipo de atributo, en la columna
Type, que puede ser nominal o numérico. Esto se muestra en la Figura B.5:
6. Se crea el archivo (Figura B.6) donde se generará el árbol de decisión
correspondiente a los datos previamente cargados.
Figura B.4: Selección de atributo de salida
Figura B.5: Selección de tipo de atributo
B-4
7. En el momento de crear el archivo, se mostrará el cuadro de diálogo que aparece
en la Figura B.7, donde se puede especificar el nombre del archivo y la ruta donde
será almacenado.
8. Para poder ejecutar el algoritmo, en la barra de menú en la opción Build se elige
C4.5, ahí se despliegan dos opciones para generar un árbol decisión podado o no
podado, como se muestra en la Figura B.8:
Figura B.6: Creación de archivo
Figura B.7: Especificación de nombre y ruta del archivo
B-5
9. Luego de elegir una de las opciones, para la generación del árbol, se generará el
árbol de decisión (Figura B.9) correspondiente a los datos previamente cargados.
Figura B.8: Ejecución del algoritmo C4.5
Figura B.9: Árbol de decisión generado
B-6
10. Al árbol de decisión generado se le puede cambiar la presentación, colocándolo de
forma horizontal o vertical. Esto se muestra en la Figura B.10 y Figura B.11:
Figura B.10: Opciones para cambiar presentación del árbol
Figura B.11: Árbol de decisión horizontal
B-7
11. Además de mostrar el árbol de decisión generado se muestran otros datos de
salida en la pestaña Classifier Output (Figura B.12), estos datos son: error de la
poda, matriz de confusión y reglas.
12. Finalmente, se puede guardar el árbol de decisión generado con que extensión
*.idt, como se muestra en la Figura B.13:
Figura B.12: Datos de salida
B-8
Algunas aclaraciones:
Es importante mencionar que cuando el algoritmo C4.5, implementado como
módulo en el software AIPI, trabaja con atributos desconocidos se asume que
estos están representados por el signo de cierre de interrogación (?) y la cadena
vacía (‘’). Cualquier otro símbolo es tomado como un atributo nominal.
Figura B.13: Guardar árbol de decisión
ANEXO C
DETALLE DE LAS SALIDAS QUE PRODUCE
EL ALGORITMO C4.5
C-1
ANEXO C: DETALLE DE LAS SALIDAS QUE PRODUCE EL ALGORITMO C4.5
Para tener un poco de más detalle con respecto a las salidas producidas por el algoritmo
C4.5, implementado como un nuevo módulo en AIPI, se explicará utilizando un ejemplo
clásico, para este tipo de algoritmos, que es el de jugar golf.
En la Figura C.1 se muestra el árbol generado por el algoritmo, en AIPI:
Como se puede apreciar, el árbol se dibuja de la siguiente manera:
El árbol consiste en una columna de valores de atributos que se derivan de una prueba de
atributos. Para este ejemplo, la raíz es la prueba de atributos “outlook” que tiene tres
valores: “overcast”, “rain” y “sunny”. Y para algunos se derivan subárboles.
El número que aparece entre paréntesis, después de cada hoja corresponde al número de
instancias de formación, con respecto al número de casos que se presentan en total. Este,
puede ser seguido, para algunos ejemplos, por un segundo número (4.0/2.0), el cual indica
el número de errores de clasificación (este es aparte del número total de clasificaciones
realizadas). La suma de la primera serie de números es igual a l número total de casos y la
suma de la segunda serie de números es igual al número total de errores. Por ejemplo:
para este ejemplo se tiene un total de 14 casos y este número corresponde a la suma de
los valores entre paréntesis: 4.0+3.0+2.0+2.0+3.0=14.
Figura C.1: Árbol de decisión
C-2
En la Figura C.2 se presentan los datos de salida que corresponde al error de la poda, la
matriz de confusión y las reglas generadas para el árbol de decisión de este ejemplo:
En la sección denominada Error de poda se muestra el error del árbol antes y después de
la poda. Para la primera opción (antes de la poda) se muestra el tamaño del árbol (sin
podar) que es el número de nodos que componen el árbol y los errores que son el número
de errores de clasificación y su respectivo porcentaje de error a partir del número total de
casos. La segunda opción muestra el tamaño del árbol podado, el número de errores de
clasificación junto con el respectivo porcentaje de error real después de la poda y una
estimación que es el porcentaje de error estimado del árbol después de la poda.
En la sección de Matriz de confusión se muestra dicha matriz generada que indica el
número de clasificaciones correctas e incorrectas en una tabla. En dicha tabla, las filas son
las clases disponibles para utilizar en el proceso de clasificación y las columnas son las
clases elegidas durante la clasificación. Además, hay que tener en cuenta que las celdas así
como pueden tener números pueden no tenerlos, si la celda no contiene un número es
porque no hay casos probados bajo la combinación de las clases que indican la fila y la
columna correspondiente a dicha celda y si pasa lo contrario (hay un número en la celda)
este representa el número de instancias de las clases que correspondientes a la respectiva
Figura C.2: Datos de salida
C-3
fila y columna de dicha celda. Por otra parte, es importante mencionar que la suma de
todos los números que se encuentran en la celda tiene como resultado el número total de
casos. Por ejemplo, para este caso la suma sería: 5+9=14.
En la sección Reglas se muestra el conjunto de reglas generadas. Este conjunto se genera
a partir de cada árbol de decisión podado, consiste en al menos una regla por defecto y
cada regla se compone de atributos y valores de la clasificación resultante seguido de un
porcentaje que representa la exactitud de dicha norma.