Tesis "Agrupamiento Automático Evolutivo con Adaptación del Criterio de Similitud Basado en Análisis del Tipo de Separabilidad de los Datos"
Sustentante: Adán José García
Director: Dr. Wilfrido Gómez Flores
Sinodales: Dr. José Torres Jiménez, Dr. José Juan García Hernández, Dr. Edwyn Javier Aldana Bobadilla, Dr. Alan Díaz Manríquez
Resumen:
El agrupamiento automático de datos consiste en revelar la estructura subyacente de los patrones en grupos y simultáneamente determinar el número de grupos. Esta tarea se ha abordado mediante algoritmos de agrupamiento metaheurísticos (AAMs), los cuales utilizan como función objetivo un índice de validez de grupos (IVG). Comúnmente, los IVGs cuantifican dos criterios de agrupamiento: separación intergrupo y dispersión intragrupo, donde un criterio de similitud, generalmente la distancia Euclidiana, determina la cercanía entre patrones. Ambos criterios de agrupamiento se satisfacen cuando los datos son linealmente separables, es decir, se pueden generar grupos compactos y separados; por tanto, el IVG es capaz de distinguir entre soluciones inferiores y superiores. Sin embargo, en el caso de datos no linealmente separables, la distancia Euclidiana solo medirá la proximidad entre patrones sin considerar el grado de conectividad entre ellos. Consecuentemente, el IVG pierde su capacidad discriminante, debido a que ambos criterios de agrupamiento no se satisfacen simultáneamente. En la práctica, se desconoce el tipo de separabilidad de los datos; por tanto, en este trabajo de investigación se propone adaptar el criterio de similitud en el IVG en función del tipo de separabilidad de los datos para incrementar el desempeño de un algoritmo de agrupamiento evolutivo.
El enfoque propuesto está compuesto de dos partes principales: un selector del criterio de similitud y un algoritmo de agrupamiento automático basado en evolución diferencial, denominado CADE. Además, se consideran dos criterios de similitud: distancia Euclidiana y distancia de la arista máxima (MED), los cuales miden proximidad y conectividad, respectivamente. El índice Silhouette (Sil) se eligió como el IVG que guía la búsqueda de soluciones de agrupamiento potenciales en el algoritmo CADE. Por otro lado, mediante aprendizaje supervisado, se entrenó el selector del criterio de similitud para distinguir entre datos linealmente separables sin traslape (G1), linealmente separables con traslape (G2), y no linealmente separables (G3) con base en sus propiedades de dispersión intragrupo. De este modo, datos clasificados como G1 y G3 se agrupan usando distancia MED, mientras que datos clasificados como G3 se agrupan usando distancia Euclidiana.
En la experimentación se consideraron 180 conjuntos de datos sintéticos y reales, lo cuales incluyen los tipos de separabilidad G1, G2 y G3. Además, el enfoque propuesto se comparó contra cuatro algoritmos de agrupamiento convencionales: K-means, Single-linkage, WARD y DBSCAN. Los resultados mostraron que los algoritmos convencionales obtuvieron un buen desempeño de agrupamiento para un tipo de separabilidad en específico, mientras que CADE fue capaz de resolver adecuadamente el agrupamiento de todos los tipos de separabilidad. Por otro lado, el selector del criterio de similitud junto con el índice Sil fueron incorporados en cuatro AAMs del estado del arte: CDE, ACDE, MEPSO y TGCA. Los AAMs obtuvieron un buen desempeño de agrupamiento en todos los tipos de separabilidad, aunque en general CADE obtuvo mejores desempeños en términos de calidad del agrupamiento, número de grupos y velocidad de convergencia. Como prueba de concepto, CADE se utilizó para la segmentación automática de imágenes de textura, mostrando su capacidad de segmentar adecuadamente las regiones de textura y estimar el número correcto de regiones.
Los resultados obtenidos sugieren que la adaptación del criterio de similitud en el IVG de acuerdo al tipo de separabilidad de los datos es una estrategia adecuada para incrementar el desempeño de agrupamiento de los AAMs. Por tanto, es recomendable continuar los esfuerzos en el diseño de nuevos IVGs y criterios de similitud considerando estos hallazgos..