Aprendizaje de sistemas basados en reglas difusas compactos y precisos con programación genética

Resumen

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, como un proceso de inducción predictiva que intenta obtener conocimiento que permita pronosticar el comportamiento futuro según los datos disponibles, o desde el punto de vista descriptivo, 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 predictiva se realiza bajo enfoques como la clasificación, la regresión o el análisis de series temporales. La clasificación es un tipo de inducción predictiva en la que los datos son objetos caracterizados por atributos que pertenecen a diferentes clases definidas, y el objetivo es inducir un modelo (un Clasificador o Sistema de Clasificación) capaz de predecir la clase a la cual pertenece un nuevo objeto dado los valores de sus atributos. En determinados problemas de clasificación tales como el diagnóstico de enfermedades o el reconocimiento de rasgos faciales, entre otros, interviene información compleja, incompleta, imprecisa o con incertidumbre, que los expertos humanos procesan de forma robusta, pero que es difícil representar y procesar en un Sistema de Clasificación. Para diseñar un esquema de clasificación robusto y con un rendimiento e interpretabilidad altos, es conveniente el uso de una herramienta para tratar con este tipo de información presente en la mayoría de los procesos de clasificación: la Lógica Difusa. La teoría de conjuntos difusos permite manejar imprecisión y tratar el conocimiento humano de una forma sistemática. En el campo de la clasificación, el papel fundamental de los conjuntos difusos es hacer transparentes los esquemas de clasificación que utilizan normalmente los seres humanos a través del desarrollo de un marco formal implementable en un ordenador. Si a la utilización de la Lógica Difusa en un Sistema de Clasificación unimos el diseño de un sistema basado en reglas, entonces obtendremos un Sistema de Clasificación Basado en Reglas Difusas (SCBRD), el cual está formado por un conjunto de modelos simples locales, verbalmente interpretables y con un rango de aplicación muy amplio. Los SCBRDs permiten la incorporación en el modelo de toda la información disponible, tanto de la que proviene de expertos humanos que expresan su conocimiento sobre el sistema en lenguaje natural, como de la que tiene su origen en medidas empíricas y modelos matemáticos. Este es un aspecto fundamental en la era de la información en la que nos encontramos, donde el conocimiento humano y su representación e interpretación en los sistemas a desarrollar es cada vez más importante. En definitiva, el uso de la Lógica Difusa hace posible el tratamiento de información con incertidumbre, muy común en problemas reales de clasificación, y permite el procesamiento de forma eficaz de la información experta disponible. Por otra parte, las reglas difusas permiten representar el conocimiento de una forma comprensible para los usuarios del sistema. En el proceso de extracción de conocimiento existen distintas tareas o problemas que se pueden enfocar y resolver como problemas de optimización y búsqueda. Los Algoritmos Evolutivos (AEs), entre los que se encuentran los Algoritmos Genéticos y la Programación Genética (PG), imitan los principios de la evolución natural para formar procedimientos de búsqueda y optimización global, lo que les convierte en herramientas especialmente adecuadas para resolver problemas presentes en las distintas etapas del proceso de descubrimiento de conocimiento. En procesos de extracción de reglas, los AEs 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. Por ello, en los últimos años los AEs han sido ampliamente utilizados como herramienta para derivar automáticamente la totalidad o una parte de los SCBRDs, dando lugar a los denominados Sistemas de Clasificación Basados en Reglas Difusas Evolutivos. En el diseño de un algoritmo de aprendizaje de SCBRDs, existen dos objetivos principales (y opuestos) que se deben maximizar: la precisión y la interpretabilidad del conocimiento extraido en forma de reglas difusas. Aunque inicialmente se prestó una mayor atención a la mejora de la precisión (mejora que se consiguió a consta de sacrificar la interpretabilidad de los SCBRDs), se ha puesto de manifiesto la necesidad de la existencia de un equilibrio entre la interpretabilidad y la precisión del conocimiento extraido a la hora de diseñar métodos de aprendizaje de SCBRDs. No obstante, este equilibrio es más dificil de lograr cuando el problema que ha de resolverse presenta una alta dimensionalidad, es decir, un elevado número de variables o características de entrada. El principal inconveniente viene dado por el crecimiento exponencial que se produce en el espacio de búsqueda de reglas difusas con un aumento lineal en el número de variables, lo que popularmente se conoce como el problema de la explosión combinacional de reglas. Dicho crecimiento hace que el proceso de aprendizaje se vuelva más complicado, y en la mayoría de los casos, lleva al aprendizaje de un SCBRD que presenta un elevado nivel de complejidad (con respecto al número de reglas, y de variables y etiquetas incluidas en cada regla). En el diseño de un SCBRD preciso, compacto e interpretable es muy importante la definición adecuada de la semántica de los conjuntos difusos asociados a las etiquetas lingüísticas. Un proceso de aprendizaje que extraiga la mejor base de reglas difusas para una partición lingüística prefijada, puede estar limitado por esta. El aprendizaje de forma simultánea tanto de la base de reglas como de la partición difusa puede permitir extraer un SCBRD con mejor comportamiento. Para que el SCBRD resultante sea lingüístico, esta definición debe ser común para todas las reglas y el proceso de aprendizaje debe verificar algunas restricciones que el modelo de representación de conjuntos difusos basado en 2-tuplas respeta. Para este aprendizaje conjunto de dos partes de un problema muy dependientes, los Algoritmos Coevolutivos son herramientas muy adecuadas puesto que permiten evolucionar de forma independiente ambas partes del problema. El objetivo de esta tesis es estudiar el aprendizaje de SCBRDs en problemas que presentan una alta dimensionalidad (con respecto al número de variables de entrada), y desarrollar nuevos algoritmos basados en el uso de la PG y de los Algoritmos Coevolutivos para la extracción de conocimiento en forma de reglas difusas que presenten un alto nivel de compacticidad y precisión en problemas con una alta dimensionalidad. Para desarrollar este objetivo general, definimos los siguientes objetivos particulares: - Realizar una revisión de los distintos algoritmos de aprendizaje de SCBRDs existentes, prestando especial atención a aquellos que hacen uso de la PG como herramienta para extraer el conocimiento. Como el objetivo es diseñar nuevos algoritmos de aprendizaje de SCBRDs compactos y precisos en problemas con una alta dimensionalidad, el estudio de los sistemas actuales nos servirá para determinar las características más importantes en esta tarea, sus componentes fundamentales y sus objetivos. - Analizar los problemas a resolver en el diseño de algoritmos evolutivos de extracción de reglas difusas con un buen equilibrio entre interpretabilidad y precisión en problemas con una alta dimensionalidad. Algunos de los aspectos más relevantes son la elección de un esquema de representación de reglas adecuado, el uso de algún mecanismo que mejore la diversidad dentro de la población de reglas, o el uso de medidas de calidad apropiadas para determinar la bondad de la solución. - Desarrollar un modelo evolutivo basado en PG para el aprendizaje de SCBRDs compactos y precisos en problemas que presentan una alta dimensionalidad. Este modelo permitirá la extracción de reglas difusas 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. - Analizar los principales componentes del modelo desarrollado, para obtener un sistema eficaz para la tarea del aprendizaje de SCBRDs compactos y precisos en problemas que presentan una alta dimensionalidad. Para esto se aplicará el modelo a diversos conjuntos de datos de prueba que presenten una alta dimensionalidad, se estudiará la elección de algunos de sus principales componentes y se analizarán los resultados obtenidos comparándolos con los proporcionados por otros modelos de aprendizaje de SCBRDs existentes en la literatura especializada. - Desarrollar un modelo coevolutivo para el diseño de SCBRDs compactos y precisos en problemas de alta dimensionalidad. Este modelo aprenderá no sólo el mejor conjunto de reglas difusas sino que también obtendrá la mejor definición para los conjuntos difusos asociados a las mismas, con el objetivo de mejorar los resultados obtenidos por el modelo anterior, tanto desde el punto de vista de compacticidad como de la precisión de los SCBRDs aprendidos. Para abordar estos objetivos, esta tesis está dividida en cuatro capítulos cuyo contenido se describe brevemente a continuación. En el Capítulo 1 se introducen los conceptos de extracción de conocimiento en bases de datos y minería de datos, y se describe en profundidad la tarea de inducción predictiva de clasificación. Posteriormente, se describe la computación flexible centrándonos, dentro de las distintas técnicas que la componen, en la descripción de los AEs y la Lógica Difusa. A continuación se introducen los SCBRDs, describiéndose con detalle sus distintos componentes y se presenta una revisión de las propuesta evolutivas basadas en PG para el aprendizaje de SCBRDs. Finalmente, se introduce el problema de la alta dimensionalidad en el aprendizaje de SCBRDs y se muestran las principales propuestas existentes en la literatura para abordar su solución. En el Capítulo 2 se presenta una propuesta basada en PG para la extracción de reglas difusas de clasificación compactas y precisas en notación DNF. Se ha realizado un análisis de diversos componentes de dicha propuesta para comprobar su adecuación. Además, se han comparado los resultados de nuestra propuesta con los obtenidos por otros algoritmos de aprendizaje de SCBRDs utilizando problemas que presentan alta dimensionalidad. Finalmente, los resultados obtenidos tanto en precisión como en compacticidad han sido validados mediante el uso de tests estadísticos no paramétricos. En el Capítulo 3 se presenta una propuesta coevolutiva para el aprendizaje simultaneo de un conjunto de reglas difusas de clasificación compactas y precisas, y de la mejor definición de los conjuntos difusos asociados a las mismas. Para ello, se introducen el paradigma de la coevolución, así como el uso del esquema de representación de 2-tuplas lingüísticas que permite aprender los paramétros de los conjuntos difusos sin que esto suponga una perdida en la interpretabilidad del sistema. A continuación se aplica esta propuesta sobre diferentes problemas que presentan una alta dimensionalidad, y se comparan sus resultados con los del modelo propuesto en el capítulo anterior, describiendo las ventajas que aporta. Por último señalar, que al igual que en capítulo anterior, los resultados obtenidos se han validado mediante el uso de tests estadísticos no paramétricos. En el Capítulo 4 se resume el trabajo realizado y los resultados obtenidos en esta tesis, se presentan las conclusiones extraídas sobre los mismos, y se plantean trabajos futuros derivados de la misma. Por último, se incluye un apéndice con la descripción de los tests estadísticos utilizados en esta tesis. La tesis termina con una recopilación bibliográfica que recoge las contribuciones más destacadas en la materia estudiada.