Índices de validación para algoritmos de agrupamiento

Abstract

External validation indexes allow similarities between two clustering solutions to be quantified. With classical external indexes, it is possible to quantify how similar two disjoint clustering solutions are, where each object can only belong to a single cluster. However, in practical applications, it is common for an object to have more than one label, thereby belonging to overlapped clusters; for example, subjects that belong to multiple communities in social networks. In this thesis, we propose a new index based on an intuitive probabilistic approach that is applicable to overlapped clusters. Given that recently there has been a remarkable increase in the analysis of data with naturally overlapped clusters, this new index allows to comparing clustering algorithms correctly. After presenting the new index, experiments with artificial and real datasets are shown and analyzed. Results over a real social network are also presented and discussed. The results indicate that the new index can correctly measure the similarity between two partitions of the dataset when there are different levels of overlap in the analyzed clusters.

Los índices de validación externa permiten medir y cuantificar la similaridad entre soluciones de agrupamiento. Con la ayuda de los índices clásicos de validación externa, es posible medir que tan similares son dos soluciones de agrupamiento con grupos disjuntos, donde cada objeto pertenece a un único grupo. Sin embargo, en situaciones prácticas, es común que un objeto pertenezca a más de un grupo, perteneciendo así a grupos solapados. Por ejemplo, personas que pertenezcan a varias comunidades en una red social. En ésta tesis, se propone un nuevo índice basado en una idea intuitiva para estimar la probabilidad de pertenencia de un objeto a un grupo, aplicable a grupos solapados. Dado que recientemente ha habido un incremento notable en el análisis de datos con grupos naturalmente solapados, éste nuevo índice permite comparar soluciones de agrupamiento de manera correcta. Luego de presentar el índice, se muestran y analizan experimentos con conjuntos de datos reales y artificiales. Además se analiza y discute la aplicación del índice al agrupamiento de una red social. Los resultados indican que el nuevo índice puede medir correctamente la similitud entre dos soluciones de agrupamiento cuando existen distintos niveles de solapamiento entre los grupos.