Algoritmos de agrupamiento sobre grafos y su paralelización

Abstract

Esta tesis se centra en el problema del agrupamiento, En la misma se presentan y evalúan diferentes algoritmos de agrupamiento basados en grafos, tanto secuenciales como paralelos y se proponen soluciones a los tres problemas de clasificación que pueden presentarse en la práctica; la obtención de participaciones o grupos disjuntos, la obtención de cubrimientos o grupos solapados y la construcción de jerarquías de grupos. Proponemos tres algoritmos de agrupamiento secuenciales y cuatro paralelos. Se presenta a demás un marco general capaz de generar diversos algoritmos jerárquicos aglomerativos, tanto estáticos como dinámicos. Todos los algoritmos propuestos en la tesis pueden utilizarse como rutinas de cubrimientos en este marco. Los distintos algoritmos secuenciales y paralelos desarrollados se aplican a la resolución de un problema concreto; el agrupamiento de documentos. La experimentación realizada con varias colecciones de documentos demuestra que nuestros algoritmos obtienen grupos con una calidad comparable a los mejores algoritmos propuestos en la literatura. Esto se logra con ventajas adicionales como no restringir el espacio de representación de los objetos ni la función de semejanza entre ellos, tener un solo parámetro, ser independientes del orden, entre otras. Por otro lado, los algoritmos paralelos logran buenas aceleraciones y escalabilidad isotemporal. A pesar de que los utilizamos en el agrupamiento de documentos, su uso no está restringido a esta área, pues pueden utilizarse en cualquier problema del Reconocimiento de Patrones donde se necesite agrupar objetos de cualquier naturaleza.