Dra. Sara Elena Garza Villarreal

La Dra. Sara Elena Garza Villarreal es profesora e investigadora asociada a la Facultad de Ingeniería Mecánica y Eléctrica (FIME) de la Universidad Autónoma de Nuevo León (UANL) y miembro del sistema nacional de investigadores (SNI) nivel 1. Cuenta con un doctorado en tecnologías de información y comunicaciones con especialidad en sistemas inteligentes por parte del Instituto Tecnológico y de Estudios Superiores de Monterrey en México (mención honorífica). Sus áreas de interés son: community detection, text mining, machine-learning, evolutionary computing, entre otras.

   

Agrupamiento de picos de densidad con detección automática de centros basada en brechas

 19/feb/2021  Seminario PISIS-UANL 2021      Asistencia : 27

Introducción

En esta ocasión la Dra. Sara Garza nos habla sobre el clustering (agrupamiento), que consiste en definir y asociar los elementos de una colección a grupos, de tal manera que aquellos objetos que se parezcan más entre sí estén dentro del mismo grupo y a su vez los que menos se parecen entre ellos se encuentren en diferentes. En el agrupamiento los objetos pueden representarse por sus características en un espacio multidimensional, donde cada característica es representada en una dimensión. El agrupamiento cuenta con numerosas aplicaciones, entre las que se destacan: la segmentación de imágenes, recomendación, análisis de sentimiento, análisis de expresión de genes, entre otras. En esta charla se presentó una metodología original, desarrollada por la Dra. Sara Garza y su alumna de doctorado Kathia G. Flores, de obtención de los centros de los agrupamientos utilizando las mayores diferencias (brechas) entre las densidades de los grupos.

Resumen

En la actualidad los métodos de agrupamiento son muy variados, tenemos por ejemplo los algoritmos basados en densidad como el DBSCAN, que han dado buenos resultados sobre algoritmos clásicos como el k-means, sobre todo en el manejo de puntos anómalos o outliers. Recientemente, se ha estudiado la agrupación basada en picos de densidad (DPC), cuyos algoritmos han demostrado mayor eficiencia en el procesamiento, debido a que se puede realizar la asignación de grupos en una sola iteración. Su éxito radica en que el usuario debe de escoger manualmente los centros de los grupos apoyándose de una “gráfica de decisión”, lo que puede hacer subjetiva la elección de los centros, además de cortar la fluidez del algoritmo e introducir inestabilidad.

Con el objetivo de solventar la elección manual de los centros en los algoritmos DPC, se aprovechan las diferencias entre las regiones de alta densidad y baja densidad para identificar brechas entre los centros de densidad y agrupar o estratificar regiones. El algoritmo desarrollado consta de los siguientes pasos generales: detectar puntos que serán candidatos a centros de densidad, ordenar candidatos de acuerdo a una función de evaluación gamma, calcular distancias entre parejas de candidatos consecutivos, detectar brechas y finalmente establecer un umbral.

El algoritmo desarrollado se probó con 14 conjuntos de datos en dos dimensiones, entre los que se usaron shape sets y bases de datos de UCI. Con respecto a otros algoritmos presentes en la literatura el DPC presenta una calidad superior, al detectar una mayor cantidad correcta de agrupamientos en los conjuntos de datos. Además, se utilizaron dos líneas de base relacionadas con el estado del arte como son el índice Rand Ajustado y la Medida F; y algoritmos como el de las k-medias y DBSCAN.

Conclusiones

El algoritmo presentado basado en densidad es capáz de encontrar grupos con formas arbitrarias. Además, fue diseñado pensando en no agregar más parámetros ni aumentar la complejidad y aún así seguir obteniendo resultados de calidad en cuanto a agrupación y a estimación de los grupos requeridos. Por otra parte, el algoritmo es dependiente del valor de la distancia de corte (dc) proporcionada, se debe elegir un valor adecuado, de lo contrario se puede influir negativamente en la detección de los centros. Como trabajo a futuro se tiene la automatización del parámetro (dc) y la consideración de una la mezcla de grupos como post-procesamiento.

Enlaces relevantes

Reseñas anteriores