Nuevos retos en minería de reglas de asociaciónun enfoque basado en programación genética

Resumen

En la actualidad, existe un gran interés en el almacenamiento de datos de cualquier índole, tanto a nivel personal como empresarial. En ocasiones, estos datos son almacenados sin reportar ninguna información de interés, por lo que muchos de estos datos son almacenados pero nunca utilizados. La extracción de reglas de asociación es una tarea de la minería de datos que permite describir comportamientos y relaciones entre grandes conjuntos de datos. Es en esta tarea en la que se centra la presente Tesis Doctoral, dando solución a muchos de los interrogantes abiertos en el campo y que han sido previamente estudiado y analizados. En primer lugar, se ha llevado a cabo un estudio detallado del estado del arte en la campo de la minería de asociación, describiendo su origen, la evolución de las propuestas, así como los temas abiertos. Las primeras propuestas se basaron en una búsqueda exhaustiva del espacio de soluciones, por lo que el dominio de búsqueda debía ser finito. Numerosas investigaciones se han llevado a cabo en este campo, proponiendo algoritmos que permitan buscar soluciones en dominios numéricos donde las soluciones no son finitas. Sin embargo, no sólo la búsqueda en dominios numéricos es un tema de estudio en minería de asociación, sino que el uso de asociaciones negativas, o incluso raras o poco frecuentes, son temas abiertos en este área. La presente Tesis Doctoral incluye una serie de propuestas para la extracción de reglas de asociación mediante una metodología basada en programación genética gramatical. El objetivo es proponer nuevos algoritmos de asociación que permitan la extracción de reglas en un único paso y de un modo eficiente. El uso de gramáticas para la codificación de las soluciones permite que el conocimiento adquirido sea muy flexible, y que las reglas descubiertas puedan incluir condiciones tanto positivas como negativas, o incluso numéricas. En una primera propuesta, se presenta un algoritmo de programación genética gramatical para la extracción de reglas de asociación frecuentes, el cual es conocido como G3PARM. Este algoritmo ha sido espec\'ficamente dise\~nado para la tarea de asociación, incluyendo dos operadores genéticos basados en la frecuencia de aparición de las condiciones. El análisis de este algoritmo demuestra su enorme eficiencia, extrayendo reglas en un único paso y mediante un proceso evolutivo. G3PARM ha sido comparado con algoritmos clásicos o deterministas, así como con propuestas posteriores basadas en metodologías evolutivas. Dicha comparación ha sido llevada a cabo mediante un análisis estadístico, cuyos resultados corroboran la importancia de G3PARM en el campo de la minería de asociación. Debido a los buenos resultados de G3PARM, se propone un posterior modelo para la extracción de reglas asociación poco frecuentes. Este tipo de asociaciones no han sido muy estudiadas, aunque son de gran relevancia, describiendo comportamientos anómalos pero no por ello poco interesantes. Este tipo de comportamientos son realmente interesantes en medicina o en educación, donde relaciones poco frecuentes puede describir el comportamiento de personas con dificultades en su proceso de aprendizaje. En minería de asociación, existen multitud de medidas que determinan la calidad de las reglas obtenidas. Muchas de estas son contrapuestas, por lo que la optimización de una determinada medida implica la ausencia de otra medida. Existen muchos problemas donde es necesario llegar a un compromiso entre las medidas, por lo que el uso de metodologías multi-objectivo son de gran interés. La presente Tesis Doctoral describe dos algoritmos multi-objetivo que son capaces de optimizar dos medidas de asociación a la vez. Estos modelos están basados en dos modelos de gran relevancia en la optimización multi-objectivo, como son NSGA-2 y SPEA-2. Por último, una de las principales dificultades en el uso de algoritmos evolutivos es la necesidad de optimizar los parámetros que se requieren para su ejecución, lo que lleva a que la mayoría de sus usuarios son expertos en la materia. En este sentido, se proponen dos algoritmos evolutivos que auto-ajustan sus parámetros en función de las características de los datos. Estas propuestas resultan de gran interés para usuarios no expertos en el campo, permitiendo que cualquier tipo usuario pueda hacer uso de estos algoritmos y de las ventajas que conllevan. Las propuestas presentadas en esta Tesis Doctoral han sido llevadas a cabo en un campo de aplicación real. Uno de los campos de mayor interés en el descubrimiento de relaciones de interés entre patrones es el ámbito de la educación. El objetivo es descubrir relaciones que permitan describir comportamientos (tanto frecuentes como anómalos) que ayuden al profesor o tutor en su proceso de enseñanza. Estas relaciones descubiertas permite describir y ayudar a alumnos con determinados problemas en el aprendizaje y mejorar sus resultados. Todos los algoritmos propuestos en la presente Tesis Doctoral han sido estadística-mente evaluados mediante una serie de tests no paramétricos. Los algoritmos han sido comparados con otros algoritmos de reconocido prestigio dentro del campo de la minería de asociación, demostrando la enorme eficiencia de los modelos propuestos. En un capítulo final se presentan una serie de nuevas líneas de investigación que han surgido con la elaboración de la presente Tesis Doctoral. Todas estas nuevas líneas están en mayor o menor medida relacionadas con la minería de reglas de asociación. Ha surgido la necesidad de extraer reglas de asociación en entornos relacionales. El creciente interés en la recolección de datos ha dado lugar a su almacenamiento en entornos relacionales, por lo que los datos se encuentran separados en diferentes tablas o incluso diferentes localizaciones físicas. En segundo lugar, ha surgido la necesidad de extraer reglas de asociación que sean sensibles al contexto, por lo que un mismo dato puede tener connotaciones diferentes en base a su contexto. También se ha propuesto, como línea de investigación nueva, la extracción de relaciones excepcionales entre los datos. Una relación es excepcional si el comportamiento que representa es completamente opuesto al comportamiento esperado. Por último, se propone la aplicación de reglas de asociación al campo del descubrimiento de subgrupos, es decir, describir grupos de elementos cuyas características están estrechamente relacionadas.