Algoritmo de clustering on-line utilizando metaheurísticas y técnicas de muestreo

Abstract

El clustering de un conjunto de documentos consiste en dividirlo en conjuntos disjuntos de clusters (subconjuntos), tales que los documentos pertenecientes al mismo cluster sean "similares" entre sí y sean menos "similares" a los pertenecientes a los demás clusters. En determinadas condiciones el clustering es una tarea computacionalmente muy costosa, verbigracia; trabajar con una colección extensa de documentos sin conocer a priori el número de clusters en los que se agruparán. Si, además, el contexto en el que se va a realizar el clustering requiere una solución en un tiempo que no supere unos pocos segundos, los métodos convencionales de cálculo de un valor óptimo para el número de clusters resultan inadecuados. En este artículo se propone un algoritmo para realizar el clustering de un conjunto de documentos, sin conocer a priori el número de clusters. El énfasis se ha puesto en la reducción del tiempo de cálculo, por lo que podemos afirmar que nuestro algoritmo es capaz de realizar un clustering on-line. Las técnicas utilizadas combinan el uso de una regla de parada global, algoritmos genéticos, técnicas de muestreo estadístico y un algoritmo de clustering clásico.

Document clustering involves dividing a set of documents into separate clusters (subsets), so that the documents are similar to other documents in the same cluster, and less similars or different from documents in other clusters. In certain conditions the clustering is a computational expensive task, for example: working with a huge collection of documents without prior knowlegdge of the appropriate number of clusters. In addition, if it is necessary a solution in few seconds, the conventional methods of calculation of the optimum number of clusters are unacceptable. In this paper we propose an algorithm for clustering a set of documents, without prior knowlegdge of the appropriate number of clusters. The emphasis has been done in the reduction of the calculation time, reason why we be able to say that our algorithm can achieve a clustering on-line. Our algorithm combines the use of a global stopping rule, genetic algorithms, techniques of statistical sampling and one classic algorithm of clustering.