TFM: Clustering de documentos con restricciones de tamaño


Seguimos fomentando la difusión de los trabajos académicos de los alumnos, como el de Diego Valderas.
Título: Clustering de documentos con restricciones de tamaño

Resumen:

El análisis de clusters tiene por objetivo dividir objetos de datos en grupos, de tal manera que los objetos dentro de un mismo grupo sean muy similares entre sí y diferentes de los objetos de otros grupos. Tradicionalmente, el clustering es visto como un método de aprendizaje no supervisado, que agrupa los objetos de datos basándose únicamente en la información presentada en el conjunto de datos, sin información externa. El K-Medoides es uno de los más famosos y sencillos algoritmos de agrupamiento, donde el usuario define el número de clusters deseados.

En muchas aplicaciones del mundo real, tales como: codificación de imágenes, agrupamientos espaciales en geo-informática, segmentación de clientes o agrupamiento de documentos, por lo general hay restricciones o prioridades en la definición del problema que limitan, el espacio de posibles soluciones, al problema o rango de interés de las soluciones. Este tipo de problemas se tratan mediante métodos de agrupamiento semi-supervisados.

El presente trabajo pretende diseñar, implementar y probar modificaciones en los algoritmos de clustering tradicionales, para incorporar restricciones de tamaño en cada cluster. Específicamente, se proponen dos nuevos algoritmos de agrupamiento semi-supervisado, basados en: programación lineal entera binaria con restricciones del tipo cannot-link y en una variación del algoritmo K-Medoides, respectivamente.

Para mostrar la aplicabilidad de los métodos de agrupación semi-supervisados propuestos, se aborda el problema de configuración automática del programa de una conferencia, con agrupación de artículos por similitud. Se incluyen experimentos, aplicando las nuevas técnicas, sobre conjuntos de datos de conferencias reales: ICMLA-2014, AAAI-2013 y AAAI-2014. Los resultados de estos experimentos muestran que los nuevos métodos son capaces de resolver problemas prácticos y reales.

 

Adjuntos:

Descarga el TFM (PDF)