Informatica

Solo disponible en BuenasTareas
  • Páginas : 17 (4238 palabras )
  • Descarga(s) : 4
  • Publicado : 7 de junio de 2010
Leer documento completo
Vista previa del texto
Algoritmo de Clustering On-Line Utilizando Metaheurísticas y Técnicas de Muestreo
María Teresa González de Lena Arantza Casillas Dpto. Informática, Estadística y Telemática, Dpto. Electricidad y Electrónica, Universidad Rey Juan Carlos Universidad del País Vasco C/ Tulipán s/n, Móstoles, Madrid, 28933 Apto. 664, Bilbao, 48940 m.t.gonzalez@escet.urjc.es arantza@we.lc.ehu.es Raquel Martínez Dpto.Informática, Estadística y Telemática, Universidad Rey Juan Carlos C/ Tulipán s/n, Móstoles, Madrid, 28933 r.martinez@escet.urjc.es

Resumen: 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ásclusters. 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álculode 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 combinanel uso de una regla de parada global, algoritmos genéticos, técnicas de muestreo estadístico y un algoritmo de clustering clásico. Palabras clave: clustering de documentos, algoritmos genéticos, clustering on-line. Abstract: 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 lesssimilars 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 samplingand one classic algorithm of clustering. Key words: clustering of documents, genetic algorithms, clustering on-line.

1 Introducción
En determinados contextos no sólo es necesario realizar el clustering de un conjunto de documentos sin conocer a priori el número de clusters, sino que, además, hay que realizarlo en un tiempo que no debe superar unos pocos segundos. El clustering de losdocumentos que devuelve un motor de búsqueda sería uno de dichos contextos. A la usual lista de relevancia se podría añadir, como salida del motor de búsqueda, la información correspondiente al resultado del clustering de los documentos. Hay un aspecto que resulta crítico en el clustering on-line de documentos, tal y como se está planteando: el desconocimiento a priori del número óptimo de clusters, k,en los que se organizará la colección de documentos. Decimos que es crítico porque dicho cálculo lleva asociado un elevado coste computacional. Aunque existen diversos métodos para calcular el número óptimo de clusters, en este trabajo nos hemos centrado en una regla de detención global (global stopping rule). Las reglas de detención globales evaluan la bondad de una medida C(k) de una partición...
tracking img