UN AMBIENTE INTEGRADO DE CLASIFICACION, SELECCION Y PONDERACION DE REGLAS BASADO EN SISTEMAS INTELIGENTES TESIS DE GRADO EN INGENIERIA EN INFORMATICA

FACULTAD DE INGENIERIA UNIVERSIDAD DE BUENOS AIRES

TESISTA: Sr. Gastón Schulz

DIRECTORES: Prof. M. Ing. Paola Britos Prof. Ing. Arturo Servetto

Laboratorio de Sistemas Inteligentes

2

UN AMBIENTE INTEGRADO DE CLASIFICACION, SELECCION Y PONDERACION DE REGLAS BASADO EN SISTEMAS INTELIGENTES TESIS DE GRADO EN INGENIERIA EN INFORMATICA

Laboratorio de Sistemas Inteligentes

FACULTAD DE INGENIERIA UNIVERSIDAD DE BUENOS AIRES

3

4

Resumen Actualmente no existe un ambiente que integre y complemente las funciones de clasificación de instancias, extracción o inducción de reglas de decisión y ponderación de estas reglas, para lograr una profunda y completa investigación de las características de las poblaciones que se desean estudiar. Esta falencia hace que cada vez que se quiera, por ejemplo, extraer las reglas de producción que dan como consecuencia la clasificación de una población, se necesite primero clasificar a los individuos de una población en un ambiente de clasificación, para luego ingresar a estos individuos clasificados en un ambiente diferente, capaz de inducir y extraer las reglas. Aquí se propone desarrollar un ambiente capaz de integrar las tres funciones, para que se complementen unas con otras. Palabras clave: Data mining, ambiente integrado, clasificación de instancias, reglas de decisión, ponderación de reglas.

Abstract Actually there not exists a ambient capable to integrate the mechanisms of classification of instances, selection and weighting of rules, and that uses each one of these mechanisms as a complement one of the other, to obtain a complete investigation of the characteristics of the populations that are desired to study. This does that whenever it is wanted, for example, to extract the rules that give the classification of a population, it is needed first to classify the individuals of the population in a classification ambient, and then to enter these classified individuals in a different ambient, able to induce and to extract the rules. Here we propose to develop a tool able to integrate these three mechanisms, to let then complement one with each other. Key words: Data mining, integrated ambient, clasification of instances, decision rules, weighting of rules.

5

ÍNDICE 1. INTRODUCCIÓN ______________________________________________ 9 2. ESTADO DEL ARTE __________________________________________ 11 2.1. Ambientes de minería de datos actuales _____________________________________________ 11 2.2. Redes neuronales competitivas en la clasificación de instancias__________________________ 13 2.2.1. Introducción _________________________________________________________________ 13 2.2.2. Redes SOM (Self Organizing Maps) ______________________________________________ 14 2.3. Árboles de decisión e inducción de reglas ____________________________________________ 2.3.1. Inducción de árboles de decisión._________________________________________________ 2.3.2. La familia TDIDT de sistemas de aprendizaje_______________________________________ 2.3.3. Árboles de decisión____________________________________________________________ 2.3.4. La tarea de inducir ____________________________________________________________ 2.3.5. Tamaño correcto del árbol de decisión. Poda _______________________________________ 2.3.6. ID3_________________________________________________________________________ 2.3.7. Incorporando valores continuos __________________________________________________

22 22 23 25 27 30 31 40

2.4. Redes Bayesianas y ponderación de reglas ___________________________________________ 2.4.1. Teorema de Bayes_____________________________________________________________ 2.4.2. Introducción a redes Bayesianas _________________________________________________ 2.4.3. Estimación de la estructura de la red Bayesiana _____________________________________ 2.4.4. Clasificadores basados en redes Bayesianas ________________________________________

41 41 44 46 48

3. DESCRIPCIÓN DEL PROBLEMA ________________________________ 55 3.1. Generalidades ___________________________________________________________________ 55 3.2. El problema a resolver ____________________________________________________________ 55

4. SOLUCIÓN PROPUESTA ______________________________________ 59 4.1. El ambiente integrado ____________________________________________________________ 59 4.2. Representación de los datos de entrada ______________________________________________ 64 4.2.1. El Standard XML _____________________________________________________________ 65 4.3. Características necesarias de los datos de entrada _____________________________________ 72

5. DISEÑO DEL AMBIENTE. LA METODOLOGÍA UML ________________ 75 5.1. Generalidades ___________________________________________________________________ 75 5.2. Casos de Uso ____________________________________________________________________ 5.2.1. Población____________________________________________________________________ 5.2.2. Clasificador __________________________________________________________________ 5.2.3. Selector _____________________________________________________________________ 5.2.4. Ponderador __________________________________________________________________ 5.2.5. El menú _____________________________________________________________________

75 76 78 80 82 85

7

5.3. Transición de estados en el ambiente ________________________________________________ 88 5.4. La interfase grafica_______________________________________________________________ 5.4.1. Población____________________________________________________________________ 5.4.2. Clasificador __________________________________________________________________ 5.4.3. Selector _____________________________________________________________________ 5.4.4. Ponderador __________________________________________________________________

90 90 91 92 94

5.5. Casos de Prueba _________________________________________________________________ 96 5.5.1. Población____________________________________________________________________ 96 5.5.2. Clasificador __________________________________________________________________ 98 5.5.3. Selector ____________________________________________________________________ 100 5.5.4. Ponderador _________________________________________________________________ 103 5.5.5. El menú ____________________________________________________________________ 105

6. COMPARACIÓN EXPERIMENTAL CON OTROS AMBIENTES _______ 109 6.1. Introducción ___________________________________________________________________ 109 6.2. Clasificador de instancias ________________________________________________________ 110 6.3. Inducción de reglas ______________________________________________________________ 111 6.4. Ponderación de reglas ___________________________________________________________ 116

7. CONCLUSIONES ____________________________________________ 119 BIBLIOGRAFÍA _______________________________________________ 121

8

1. Introducción Actualmente no existe un ambiente capaz de integrar y complementar las funciones de clasificación de instancias, inducción o selección de reglas de decisión y ponderación de estas reglas, para lograr una profunda y completa investigación de las características de las poblaciones que se desean estudiar. Esta falencia hace que cada vez que se quiera, por ejemplo, extraer las reglas de producción que dan como consecuencia la clasificación de una población, se necesite primero clasificar a los individuos de una población en un ambiente de clasificación, para luego ingresar a estos individuos clasificados en un ambiente diferente, capaz de inducir y extraer las reglas. La misma necesidad haría falta si se quieren ponderar luego esas reglas obtenidas.

Aquí se propone desarrollar un ambiente capaz de integrar las tres funciones, y hacer además que estas funciones logren complementarse. Esta tesis se encuentra estructurada a lo largo de 7 capítulos.

El capítulo 2 describe el estado actual de los campos de estudio relacionados con esta tesis. En la sección 2.1 se presenta un listado de las herramientas actuales más conocidas o utilizadas en el mercado para el estudio de poblaciones con sus características, la sección 2.2 presenta los conceptos y teorías importantes relativas a las redes competitivas en general y a las SOM en particular, utilizadas para la clasificación de individuos. A lo largo de la sección 2.3 se presentan los árboles de decisión, dándole una especial atención a los ID3. En la sección 2.4 se presentan las redes Bayesianas, y junto con ellas se da una introducción a la utilización de estas redes como clasificadoras, describiéndose las características de las redes Naive Bayes y TAN.

En el capítulo 3 se presenta el contexto de nuestro problema de interés.

En el capítulo 4 se presentan todos los aspectos relativos de la solución propuesta. En la sección 4.1 se describen las características y el flujo de procesos que conformarán el ambiente integrado propuesto como solución. En la sección 4.2 se

9

describe el estándar XML, utilizado para la representación de los datos de entrada que serán analizados por el ambiente y ya en la sección 4.3 se describen y especifican las características que deben cumplir (dentro del estándar XML) los datos de entrada que serán analizados.

En el capitulo 5 se desarrolla la metodología de diseño y desarrollo de sistemas denominada UML aplicada al diseño y desarrollo del ambiente a implementar. Primeramente, en la sección 5.1, se hace una reseña del lenguaje utilizado, ambientes de desarrollo y demás características del software utilizado para la construcción y compilado del software. En la sección 5.2 se presentan los casos de uso. Luego, en la sección 5.3 se presenta la transición de estados en el ambiente, y en la sección 5.4 se presenta el diseño de las distintas pantallas desarrolladas. A continuación, en la sección 5.5, se describen las pruebas que se realizaron sobre los casos de uso, para evaluar la efectividad de la solución propuesta.

En el capitulo 6 se realiza una comparación entre los resultados experimentales obtenidos con el ambiente desarrollado y otros ambientes existentes, respecto a cada una de las funciones que el ambiente desarrollado provee.

Y por último, en el capitulo 7, se describen las conclusiones obtenidas.

10

2. Estado del arte Este capítulo presenta el estado actual de los aspectos relacionados con el estudio de esta tesis. Se comienza dando una reseña respecto a los diferentes ambientes de minería de datos actualmente disponibles en el mercado (Sección 2.1). Luego, se presenta el estado actual de las redes competitivas, y en especial a las redes denominadas mapas autoorganizados, utilizadas como redes clasificadoras de datos (Sección 2.2).

Se comienza dando una introducción de lo que son las redes

competitivas (Sección 2.2.1) en general, para después detallar a las redes SOM en particular (Sección 2.2.2). A continuación se presentan los árboles de decisión, utilizados como solución a la inducción de reglas (Sección 2.3). Primero se explica el concepto de inducción mediante árboles de decisión (Sección 2.3.1). Después se presenta a la familia TDDI de árboles de decisión (Sección 2.3.2). Luego se detallan puntualmente los árboles de decisión (Sección 2.3.3) para después explicar a que se refiere la tarea de inducir dentro de los árboles (Sección 2.3.4), continuar explicando lo que es la poda en árboles de decisión (Sección 2.3.5) y finalizar dando una reseña, dentro de la familia TDDI, al algoritmo ID3 (Sección 2.3.6). Se describe luego un método probabilístico para lograr la ponderación de las reglas inducidas, como son las redes Bayesianas (Sección 2.4), presentado también diferentes algoritmos de redes Bayesianas utilizadas como clasificadoras de datos (Sección 2.4.3), detallando puntualmente las Naive Bayes y las TAN.

2.1. Ambientes de minería de datos actuales Existen numerosos ambientes utilizados en forma exitosa tanto para clasificar a una población de individuos, para inducir reglas inherentes a las características de una población o para ponderar reglas. Sistemas que utilizan a las redes neuronales son un ejemplo de eso, ya que dependiendo de la arquitectura de redes que utilicen, se comportan muy bien como clasificadores de elementos de un dominio; los sistemas que implementan árboles de decisión tales como ID3 [Quinlan, 1986] o C4.5 [Quinlan, 1993], por otro lado, son también muy comunes en lo que se refiere a la extracción de

11

reglas de dominios; y también están aquellos sistemas que utilizan a las redes Bayesianas como modelos de ponderación de reglas.

A continuación se detallan varios

ambientes actualmente disponibles en el

mercado, junto con una pequeña reseña de las funciones que proveen y de las técnicas utilizadas para brindar esas características.

AMBIENTE DESCRIPCION AC2 AC2 es un ambiente de data mining diseñado para usuarios conocedores de la materia. AC2 tiene un modelado grafico orientado a objetos y librerías en C y C++. Soporta la edición interactiva del árbol que se genera. Se comporta como una librería multiplataforma de funciones de data mining. Provee como funciones: clusterización, clasificación, predicción, segmentación. Utiliza como técnica árboles de decisión [AC2]. AnswerTree

AnswerTree es un ambiente de SPSS utilizado para construir árboles de decisión. Como ambiente de data mining apunta perfilar a grupos para la comercialización y las ventas. Utiliza cuatro algoritmos de árboles de decisión. Incluidos están dos algoritmos CHAID, los cuales SPSS ha extendido para manejar categorización nominal, ordinal y variables continuas dependientes. Provee como funciones: Clasificación. Utiliza como técnicas: Árboles de decisión (CHAID, CHAID Exhaustivo, C&RT (variación de CART), QUEST). [AnswerTree]

CART

CART es un ambiente de árbol de decisión que utiliza el algoritmo CART. Para poder manejar la falta de información, los datos son manejados a través de reglas de backup que no siempre asumen que todos los datos de un atributo incierto es el mismo. Se utilizan siete criterios diferentes de splitting (incluyendo el Gini). Debido al uso del motor de traducción de datos, DBMS/Copy, se pueden utilizar datos de diferentes tipos de formato (incluyendo Excel, Informix, Lotus, Oracle). Provee como funciones: Clasificación. Utiliza como técnicas: Árboles de decisión (CART). [CART], [Breiman L, 1984]. Clementine utiliza iconos descriptivos como interfaz, el usuario crea descripciones de flujos de datos de las funciones que se realizarán. Cada icono representa un paso en el proceso total de minería de datos. Existen incluidos iconos para funciones tales como el acceso a datos, preparación de datos, visualización y modelado. Para asistir a la creación de secuencias, Clementine utiliza Capri. Además puede utilizar grandes conjuntos de datos usando un modelo de cliente/ servidor. Cuando es posible, el servidor convierte peticiones del acceso a los datos en las consultas SQL, que pueden entonces tener acceso a una base de datos emparentada. Provee como funciones: Reglas de asociación, clasificación, clusterización, análisis de factor, pronostico, predicción. Utiliza como técnicas: Apriori, BIRCH, CARMA, árboles

Clementine

12

AMBIENTE DESCRIPCION de decisión (C5.0, C&RT variación de CART), clusterización K-means, redes neuronales (Kohonen, MLP, RBFN), regresión (lineal, logística) inducción de reglas (C5.0, GRI). [Clementine] Elvira El programa Elvira está destinado a la edición y evaluación de modelos gráficos probabilistas, concretamente redes Bayesianas y diagramas de influencia. Elvira cuenta con un formato propio para la codificación de los modelos, un lector-intérprete para los modelos codificados, una interfaz gráfica para la construcción de redes, con opciones específicas para modelos canónicos (puertas OR, AND, MAX, etc.), algoritmos exactos y aproximados (estocásticos) de razonamiento tanto para variables discretas como continuas, métodos de explicación del razonamiento, algoritmos de toma de decisiones, aprendizaje de modelos a partir de bases de datos, fusión de redes, etc. [Elvira] Sipina Sipina está diseñado especialmente para la inducción de árboles de decisión. Sipina es un software con el cual se puede extraer conocimiento de los datos. Sipina aprende tanto de datos cualitativos como cuantitativos, y produce un grafico enrejado. Los algoritmos que provee Sipina para la generación de árbol de decisión son: SIPINA, ID3, C4.5, CART, Chi2-link, Elisee, QR_MDL y WDTaiqm. [Sipina] Weka Weka contiene y se focaliza en algoritmos de clasificación, regresión, y clusterización de patrones. Weka es un software gratuito y open-source bajo la licencia al público en general del GNU (GLP). Las técnicas que utiliza son: Naïve Bayes, Nearest neighbor, Linear models, OneR, Decision trees, Covering rules, K-means, EM, Cobweb. [Weka]

2.2. Redes neuronales competitivas en la clasificación de instancias 2.2.1. Introducción En las redes neuronales con aprendizaje competitivo y cooperativo, las neuronas compiten y cooperan unas con otras con el fin de llevar a cabo una tarea dada. Con este tipo de aprendizaje se pretende que cuando se presente a la red cierta información de entrada, solo una de las neuronas de salida de la red se active o alcance su valor de respuesta máximo. Es por eso que las neuronas compiten para activarse, quedando finalmente una como neurona ganadora, mientras que el resto quedan anuladas. Como se mencionó anteriormente, el objetivo de este aprendizaje es clusterizar los datos que se introducen en la red. Debido a esto, los individuos con características similares son clasificados formando parte de la misma categoría y por lo tanto deben activar la misma

13

neurona de salida. Un punto que vale la pena destacar es el hecho de que en este tipo de redes las clases o categorías que la red clasificará deberán ser creadas por la propia red, puesto que se trata de un aprendizaje no supervisado a través de las correlaciones entre los datos de entrada. Las clases o categorías en las que se va a dividir el conjunto de entrada están directamente relacionadas con la estructura que tenga la red competitiva, ya que la cantidad de nodos que tenga la red dará lugar a la cantidad máxima de clases en las que ésta podrá clusterizar a las entradas.

2.2.2. Redes SOM (Self Organizing Maps) Una de las implementaciones que más se destacan en este tipo de redes son los mapas autoorganizados (SOM., Self Organizing Maps). Esta implementación permite a la red clasificar entradas en las cuales las neuronas que estuviesen en un vecindario cercano a la neurona ganadora, respondieran a entradas similares.

Los mapas autoorganizados están compuestos por un conjunto de nodos definidos por un vector de pesos, y una topología que indica la vecindad de los nodos entre sí. Todos los nodos reciben el mismo vector de entradas, y su salida es la distancia euclídea entre el vector de entradas y el de pesos. De todos los nodos que forman el mapa, solo uno será el responsable de generar la salida, y será aquel cuyo vector de pesos sea el más parecido a la entrada actual. Esta red utiliza un aprendizaje no supervisado de tipo competitivo.

En cuanto a la topología de vecindad entre los nodos, esta puede ser muy variada:

14

-

lineal,

-

lineal en forma de anillo,

-

plana con retículo rectangular,

-

plana con retículo hexagonal,

-

toroidal

En la Figura 1 se muestran algunos ejemplos de vecindad en los mapas autoorganizados. Es posible también tener mapas autoorganizados con topologías de dimensiones más altas, pero la utilización, y sobre todo la representación de los resultados en dimensiones superiores a dos resulta más incómoda, o impracticable.

Figura 1. Ejemplos de vecindad en los mapas autoorganizado

El aspecto geométrico de la disposición de las neuronas de una red en los mapas autoorganizados o SOM es la base de un caso particular de aprendizaje competitivo introducido por Kohonen en 1982 [Kohonen, 1982], el cual es aplicado a una disposición bidimensional de las neuronas de salida, que permiten obtener mapas topológicos o topográficos en los que de algún modo estarían representadas las características principales de las informaciones presentadas a la red. La idea es que si la red recibe informaciones con características similares, se generarán mapas parecidos, debido a que serían afectadas neuronas de salidas próximas entre sí, y no solo la neurona supuestamente ganadora.

15

El modelo presentado por Kohonen se trataba de un modelo de red neuronal con capacidad para formar mapas de características de manera similar a como ocurre en el cerebro; el objetivo de Kohonen era demostrar que un estímulo externo o información de entrada por sí solo, suponiendo una estructura propia y una descripción del comportamiento de la red, era suficiente para forzar la formación de los mapas. En la etapa de aprendizaje de este tipo de redes, se distinguen dos etapas: una etapa de entrenamiento y una etapa de funcionamiento.

En la etapa de entrenamiento se fijan los valores de las conexiones (feedfordward) entre la capa de entrada y la de salida. Esta red utiliza un aprendizaje no supervisado de tipo competitivo, las neuronas de la capa de salida compiten por activarse y sólo una de ellas permanece activa ante una determinada información de entrada a la red, los pesos de las conexiones se ajustan en función de la neurona que haya resultado vencedora.

Durante la etapa de entrenamiento, se le presenta a la red un conjunto de información de entrada para que ésta establezca en función de la semejanza entre los datos las diferentes categorías, las cuales serán una por neurona de salida, que servirán durante la etapa de funcionamiento para realizar clasificaciones de nuevos datos que se le presenten a la red. En el caso de existir más patrones de entrenamiento que neuronas de salida, es lógico pensar que más de un patrón deberá asociarse con la misma neurona, o sea pertenecerán a la misma clase.

En este modelo el aprendizaje no concluye después de presentarle una vez todos los patrones de entrada, sino que habrá que repetir el proceso varias veces para refinar el mapa topológico de salida, de tal forma que cuantas más veces se presenten los datos, tanto más se reducirán las zonas de neuronas que se deben activar ante entradas parecidas, consiguiendo que la red pueda realizar una clasificación más selectiva.

Como se mencionó anteriormente, un concepto muy importante en la red de Kohonen es la zona de vecindad, o vecindario alrededor de la neurona vencedora i*. Los pesos de las neuronas que se encuentran en esta zona, a la que se le dará el nombre de

16

X(q), serán actualizados junto con el peso de la neurona ganadora, en un claro ejemplo de aprendizaje cooperativo.

El algoritmo de aprendizaje utilizado para establecer los valores de los pesos de las conexiones entre las N neuronas de entrada y las M de salida es el siguiente:

1. En primer lugar se inicializan los pesos wij con valores aleatorios pequeños y se fija la zona de vecindad entre las neuronas de salida.

2. A continuación se presenta a la red una información de entrada, la cual deberá aprender, en forma de vector p=(p1,p2,…,pn), cuyas componentes pi serán valores continuos.

3. Puesto que se trata de un aprendizaje competitivo, se determina la neurona vencedora de la capa de salida. Ésta será aquella cuyo vector de pesos wi será el más parecido a la información de entrada p. Para ello se calculan las distancias o diferencias entre ambos vectores, considerando una por una todas las neuronas de salida. Suele utilizarse la distancia euclídea o la siguiente expresión, muy similar: di = ∑ (pj - wij)2 1