Aprendizaje evolutivo de reglas difusas para descripción de subgrupos

Abstract

Actualmente se ha incrementado de forma paralela tanto la cantidad de información almacenada como la necesidad de desarrollar algoritmos que permitan extraer conocimiento útil de la misma de forma automática, Estos algoritmos se incluyen dentro del área de extracción de conocimiento en bases de datos (KDD, Knowledge Discovery in Databases). La extracción de conocimiento se puede abordar, en función del problema a resolver, desde dos perspectivas distintas: desde el punto de vista predictivo, en el que se intenta obtener conocimiento para clasificación o predicción, o desde el punto de vista descriptivo, como un proceso inducción descriptiva cuyo objetivo fundamental es descubrir conocimiento de interés dentro de los datos, intentando obtener información que describa el modelo que existe detrás de los datos. La inducción descriptiva se realiza bajo enfoques como la extracción de reglas de asociación , el descubrimiento de cláusulas , el descubrimiento de dependencias en bases de datos o el descubrimiento de subgrupos, entre otros. El descubrimiento de subgrupos (SD, Subgroup Discovery) es un tipo de inducción descriptiva que ha recibido recientemente mucha atención por parte de los investigadores. El concepto fue formulado inicialmente por Klösgen en su algoritmo de aprendizaje EXPLORA y por Wrobel en el algoritmo MIDOS , modelos en los que se utiliza un método de extracción de reglas basado en árboles de decisión, para obtener los mejores subgrupos de entre la población. MIDOS amplía el enfoque de EXPLORA al problema de descubrimiento en bases de datos multi-relacionales. La idea del descubrimiento de subgrupos se basa en, dado un conjunto de datos y una propiedad de esos datos en la que esté interesado el usuario, buscar subgrupos que sean interesantes para el usuario en el sentido de que tengan una distribución estadística inusual respecto a la propiedad resaltada por el usuario. A diferencia de la mayoría de las tareas de minería de datos, el objetivo del descubrimiento de subgrupos no es ni puramente predictivo (utilizar los resultados de la minería de datos para predecir o clasificar casos futuros) ni exclusivamente descriptivo (utilizarlos para describir un dominio o, más específicamente, la estructura de dependencia dominante entre las variables del dominio, de forma que sea interpretable por los usuarios finales). El objetivo del descubrimiento de subgrupos es descubrir propiedades características de subgrupos construyendo reglas individuales sencillas (con una estructura comprensible y en las que intervengan pocas variables), altamente significativas y con un alto soporte (que cubran muchas instancias de la clase objetivo). En un algoritmo de descubrimiento de subgrupos se extraen reglas o patrones de interés que representen el conocimiento de forma simbólica y que sean lo suficientemente sencillos y descriptivos como para ser reconocibles y utilizados por el usuario final. El uso de la lógica difusa para el tratamiento de variables continuas ayuda a expresar el conocimiento extraído de forma fácilmente interpretable por el experto, además de hacer posible el tratamiento de información con incertidumbre, muy común en problemas reales, y de permitir el procesamiento eficaz de la información experta disponible. Los algoritmos evolutivos , y en particular los algoritmos genéticos (AGs) tienen un carácter de búsqueda global que hace que sean especialmente adecuados para resolver distintos problemas presentes en cualquier proceso de descubrimiento de conocimiento. En procesos de extracción de reglas, los AGs tratan de forma adecuada las interacciones entre atributos porque evalúan una regla como un todo mediante la función de adaptación, en lugar de evaluar el impacto de añadir o eliminar una condición de una regla, como ocurre en los procesos de búsqueda local incluidos en la mayoría de los algoritmos de inducción de reglas y árboles de decisión. Los AGs se han utilizado mucho en procesos de inducción predictiva y en inducción descriptiva, fundamentalmente en reglas de asociación. Sin embargo, hasta donde sabemos, no se han aplicado algoritmos evolutivos ni lógica difusa para la tarea de descubrimiento de subgrupos. Por este motivo, en esta memoria se abordará el diseño de algoritmos de extracción de reglas de descubrimiento de subgrupos. Para ello se utilizarán las dos herramientas mencionadas, la lógica difusa para la representación del conocimiento y razonamiento muy cercana a los esquemas humanos, y los AGs como técnica de búsqueda, en lo que se denominan modelos evolutivos de extracción de reglas difusas que aúnan las ventajas de ambas herramientas. Los modelos desarrollados hasta ahora para realizar la tarea de inducción descriptiva de extracción de reglas de descripción de subgrupos son modificaciones de algoritmos clásicos de clasificación o de extracción de reglas de asociación para esta tarea. El objetivo de esta memoria es estudiar el problema de la extracción de reglas de descripción de subgrupos y desarrollar nuevos modelos basados en la computación flexible, concretamente modelos evolutivos de extracción de reglas difusas. Para desarrollar este objetivo general, definimos los siguientes objetivos particulares: a) Realizar una revisión de los distintos modelos existentes de descubrimiento de subgrupos. Como el objetivo es diseñar nuevos modelos evolutivos de extracción de reglas difusas para descubrimiento de subgrupos, el estudio de los sistemas actuales servirá para determinar las características de la tarea de descubrimiento de subgrupos, sus componentes fundamentales y sus objetivos. b) Analizar los problemas a resolver en el diseño de algoritmos de extracción de reglas de descripción de subgrupos. Uno de los aspectos más relevantes son las medidas de calidad consideradas durante el proceso de extracción de reglas y en la evaluación final de las reglas obtenidas. En esta memoria se realizará un estudio sobre este problema. c) Desarrollar un modelo evolutivo de extracción de reglas difusas para el descubrimiento de reglas de descripción de subgrupos. Este modelo permitirá la extracción de dos tipos de reglas: reglas canónicas en las que el antecedente está formado por una conjunción de parejas atributo/valor, y reglas en forma normal disyuntiva (DNF, Disjunctive Normal Form) en las que cada atributo que interviene en la regla puede tomar más de un valor. d) Analizar los componentes del modelo desarrollado, para obtener un sistema eficaz para la tarea de descubrimiento de subgrupos. Para esto se aplicará el modelo a diversos conjuntos de datos de prueba con distintas combinaciones de componentes y se analizarán los resultados obtenidos por cada uno de ellos. e) Diseñar y desarrollar un modelo evolutivo multiobjetivo. Este modelo servirá para resolver las dificultades del modelo mono-objetivo debidas a la agregación de los distintos objetivos en uno solo. Para el desarrollo del modelo, se estudiarán previamente las propuestas existentes de algoritmos evolutivos multiobjetivo. f) Aplicar los modelos desarrollados a problemas reales para comprobar la aplicabilidad de las propuestas y obtener conclusiones respecto a los resultados obtenidos. Para abordar estos objetivos, esta memoria está dividida en cuatro capítulos cuyo contenido se describe brevemente a continuación. En el Capítulo 1 se introduce el concepto de minería de datos y se describe en profundidad la tarea de inducción descriptiva de descubrimiento de subgrupos, incluyendo los distintos modelos existentes y las medidas de calidad utilizadas. Posteriormente, se describe la computación flexible centrándonos, dentro de las distintas técnicas que la componen, en la descripción de los algoritmos evolutivos y la lógica difusa. Finalmente, se propone el desarrollo de nuevos modelos para el desarrollo de la tarea de descubrimiento de subgrupos utilizando computación flexible. En el Capítulo 2 presentamos una propuesta de algoritmo genético para la extracción de reglas difusas de descripción de subgrupos, que puede extraer conocimiento utilizando dos tipos de reglas, canónicas y DNF. La propuesta se ha desarrollado utilizando distintas medidas de calidad, y se ha realizado un análisis de componentes para determinar las mejores alternativas, aplicando la propuesta con distintas medidas de calidad sobre distintos conjuntos de datos sintéticos. Se han comparado además los resultados de nuestra propuesta con los obtenidos por otros algoritmos de descubrimiento de subgrupos. Finalmente hemos aplicado las propuestas sobre dos problemas reales, el primero de los cuales es un problema de marketing y el segundo relacionado con los datos de utilización de un sistema de e learning. En el Capítulo 3 presentamos el problema de optimización multiobjetivo, y los distintos modelos que se han aplicado para su resolución. Describimos distintos enfoques de algoritmos evolutivos multiobjetivo, y presentamos un modelo de algoritmo evolutivo multiobjetivo para la extracción de reglas difusas de descripción de subgrupos. A continuación se aplica este modelo a diferentes problemas sintéticos, y comparamos el modelo propuesto con el modelo mono-objetivo, describiendo las ventajas que aporta. Por último se aplica la propuesta a los problemas de marketing y e-learning introducidos en el capítulo anterior. En el Capítulo 4 resumimos el trabajo realizado y los resultados obtenidos en esta memoria, presentamos las conclusiones extraídas sobre los mismos, y planteamos trabajos futuros derivados de la misma. Por último, los Apéndices incluyen la descripción de los conjuntos de datos empleados, tablas adicionales de resultados, la descripción de los algoritmos empleados para las comparaciones con nuestras propuestas, y la descripción de las variables del problema de marketing.