Resumen de Minería de reglas de asociación mediante adaptación de la meta-heurística optimización por mallas variables
Ivan Fredy Jaramillo Chuqui
La presente tesis se enmarca en el contexto de las técnicas de minería de datos, específicamente la minería de reglas de asociación cuantitativa, campo de estudio que se enfoca en la extracción de asociaciones entre los datos y que son representado en forma de reglas. En este trabajo se estudia una propuesta para el descubrimiento de reglas de asociación de calidad, el problema se aplica a conjuntos de datos que contienen variables tanto numéricas como categóricas, además que sus tiempos de respuesta sean aceptables, para esto, una forma muy posible de alcanzar es mediante la adaptación de un nuevo algoritmo.
El trabajo realizado durante la presente tesis se centra en la adaptación del algoritmo VMO (Optimización por Mallas Variables) y su posterior evaluación de la calidad. Como primer eslabón para alcanzar los objetivos planteados en esta tesis es muy necesario acudir a la literatura existente. Trabajos referentes a esta temática han comenzado hace aproximadamente treinta años, y es notable el surgimiento de diferentes líneas de investigación en el campo de la minería de reglas de asociación.
Una de las líneas que ha sido relevante y ha despertado el interés para este trabajo, son las brechas que aún existen entre la aplicación de algoritmos evolutivos y la optimización de las reglas de asociación. Un enfoque que ya tiene considerable literatura, pero que dado la continua evolución de las tecnologías y modelos de optimización, aún son objeto de investigación y experimentaciones con el propósito de alcanzar técnicas de mayor calidad. Variedades de algoritmos evolutivos han sido utilizados para resolver problemas de descubrimiento de reglas de asociación, cada uno de ellos con diferentes enfoques sobre la problemática. Los problemas de nuestro entorno pueden tener diferentes formas de representación, así pueden ser aplicados modelos de optimización cuando es posible la definición de funciones de calidad. Es así que, un algoritmo puede ser adaptado para la resolución de problemas que cumplan con las condiciones de optimización. En este trabajo la adaptación del algoritmo VMO se ha alcanzado con éxito, para ello ha sido necesario trabajar sobre un ambiente de desarrollo denominado QUANTMINER. Las funciones básicas que se encuentran en este entorno reduce significativamente las implementaciones que pueden considerarse irrelevantes a la problemática de tal manera que permite focalizar el esfuerzo en los componentes esenciales de la solución, pero además de estos beneficios, las herramientas traen implementaciones de otros algoritmos que sirven como referentes en una evaluación comparativa.
La técnica propuesta en este trabajo se ha denominado QARM_VMO (Minería de Reglas de Asociación Cuantitativas mediante algoritmo VMO) basado en el algoritmo VMO para optimización continua. El algoritmo es capaz de trabajar con datos representados en forma tabular que incluyen variables tanto numéricas como categóricas. Un esquema de regla debe ser definido por el usuario para comenzar el proceso de exploración de reglas, en el esquema se especifican las variables tanto del antecedente como del consecuente de la regla.
Adicional a esto se requieren de parámetros tales como los umbrales mínimos de soporte y confianza, también se puede personalizar valores referentes a la población y al número de evaluaciones.
Los resultados obtenidos por QARM_VMO han sido satisfactorios, en las pruebas experimentales el algoritmo demostró alta precisión en la identificación de reglas de asociación importantes, dentro de conjuntos de datos tanto sintéticos como reales. Las pruebas comparativas de rendimiento fueron efectuados con diez conjuntos de datos reales y seis algoritmos para extracción de reglas, este grupo se compone del tradicional APRIORI, dos algoritmos evolutivos multi-objetivo MODENAR-A y QAR_CIP_NSGAII-A, dos algoritmos mono objetivo GAR y GENAR, también se agrega la versión genética de QUANTMINER. Se consiguió integrar los resultados de las pruebas en la herramienta R project mediante el uso de la librería RKeel, que tienen las implementaciones de los algoritmos en el segmento de reglas de asociación, mientras que para QUANTMINER y QARM_VMO los datos fueron generados desde Java y pasados a R project.
Entre los algoritmos evolutivos mono-objetivo, QARM_VMO alcanzó el valor más alto de calidad obtenido por la función de ajuste, la misma que fue implementada como una función adicional en R-project para el cálculo en las otras técnicas probadas. En comparación con el algoritmo GAR, para el peor de los casos QARM_VMO está 1.31 unidades por encima, en el conjunto de datos basketball, y en el mejor de los casos está 146.95 unidades por encima en el conjunto de datos abalone. En relación al algoritmo GENAR, este algoritmo obtuvo valores muy bajos para el función de ajuste, cediendo ventaja considerable a QARM_VMO. En lo referente a la versión genética de QUANTMINER, este se encuentra ligeramente por debajo de QARM_VMO, en la mayor parte de casos con una diferencia menor a uno, y en dos conjuntos de datos de los diez, QUANTMINER resulta ligeramente superior.
Para la función de calidad implementada en la técnica propuesta y normalizada en el resto de técnicas probadas. Por una parte, en comparación con las versiones genéticas mono-objetivo, QARM_VMO demuestra superioridad en comparación a GAR y GENAR. En lo referente a QUANTMINER, aunque es ligeramente superior en los resultados, no tiene una diferencia significativa.
Por otro lado con respecto al algoritmo clásico APRIORI se evidencia que QARM_VMO es superior, y finalmente en comparación con dos técnicas multi-objetivo, se pudo evidenciar que es superior a MODENAR, y no hay diferencia significativa con QAR_CIP_NSGAII-A.
