Por favor, use este identificador para citar o enlazar este ítem:
http://inaoe.repositorioinstitucional.mx/jspui/handle/1009/552| Algoritmos de agrupamiento para la generación de cubrimiento en colecciones de documentos | |
| AIREL PEREZ SUAREZ | |
| JOSE FRANCISCO MARTINEZ TRINIDAD | |
| Acceso Abierto | |
| Atribución-NoComercial-SinDerivadas | |
| Data mining Text mining Clustering | |
| Clustering is the process of grouping a set of prototypes objects into a set of meaningful
subclasses, called clusters, such that prototypes belonging to the same cluster have a
higher similarity in comparison to prototypes that belonging to different clusters.
One important aspect to consider, in document clustering, is how will be the resulting
clusters, i.e. they will be disjoint or overlapped. Usually, there are many topics included
in a single document; therefore, this document should belong to more than one cluster.
However, most of document clustering algorithms produce disjoint clusters.
In this thesis, a new graph-based clustering algorithm called CStar is presented. The
CStar algorithm builds a set of clusters, from one document collection, where a document
may belong to more than one cluster. In CStar algorithm, a new type of star-shaped subgraph
and a new heuristic that allows obtaining a cover of the thresholded similarity graph
representing the document collection, are introduced. The heuristic followed by CStar
avoids the chaining effect presented in some algorithms like Single-link and it reduces
some drawbacks presented in some graph-based algorithms like Star, Extended Star and
Generalized Star.
The experimentation using two standard document collections, considering internal
and external evaluation measures, showed that CStar outperforms other graph-based algorithms
and some widely used hierarchical algorithms. Besides, CStar obtains fewer clusters
than most of the aforementioned algorithms and, in almost all cases, their clusters
have more elements.
Additionally, in this thesis, an improved version of CStar algorithm called CStar+ is
presented. This version allows, through the detection of some types of connected components
in the thresholded similarity graph, to increase the internal cohesion of the resulting
clustering and to reduce algorithm’s processing.
El agrupamiento es el proceso de organizar o estructurar una colección de objetos en clases o clusters de forma tal que exista una semejanza relativamente alta (o mínima distancia) entre los objetos del mismo grupo en contraposición con la existente entre objetos de grupos diferentes. Un aspecto a tener en cuenta, en el caso del agrupamiento de documentos, es cómo será considerada la pertenencia de un documento a los grupos. Es muy común que un documento no trate de un único tema o tópico en particular sino que en el mismo estén presentes varios tópicos; este documento debería pertenecer a cada uno de los grupos que representan a estos tópicos. No obstante, la mayoría de los algoritmos de agrupamiento de documentos producen particiones, es decir grupos disjuntos. En esta tesis se presenta un nuevo algoritmo de agrupamiento basado en grafos denominado CStar, el cual permite generar cubrimientos en bases documentales considerando que un documento pueda pertenecer a más de un grupo. El algoritmo CStar define un nuevo tipo de sub-grafo llamado sub-grafo en forma de estrella condensada y aplica una heurística, a partir de la cual obtiene un cubrimiento del grafo que representa la colección utilizando sub-grafos de este tipo. La heurística que sigue CStar para obtener el agrupamiento evita el efecto de encadenamiento entre documentos, el cual es común en muchos algoritmos como el Single-Link. CStar también reduce limitaciones presentes en algoritmos basados en grafos como Star, Extended Star y Generalized Star. Los experimentos realizados en colecciones estándar de documentos, considerando varias medidas de calidad externas e internas, mostraron que CStar obtiene mejores resultados que los algoritmos basados en grafos y que los algoritmos jerárquicos más usados para el agrupamiento de documentos. Además, CStar reduce la cantidad de grupos generados por la mayoría de los algoritmos y obtiene grupos más densos igualmente en la mayoría de los casos. Adicionalmente, se propone una variante del algoritmo CStar denominada CStar+ que permite, a través de la detección de algunos tipos de componentes conexas, aumentar la cohesiٔón del agrupamiento y reducir el procesamiento del algoritmo. | |
| Instituto Nacional de Astrofísica, Óptica y Electrónica | |
| 2008 | |
| Tesis de maestría | |
| Español | |
| Estudiantes Investigadores Público en general | |
| Pérez-Suárez A | |
| BANCOS DE DATOS | |
| Versión aceptada | |
| acceptedVersion - Versión aceptada | |
| Aparece en las colecciones: | Maestría en Ciencias Computacionales |
Cargar archivos:
| Fichero | Tamaño | Formato | |
|---|---|---|---|
| PerezSA.pdf | 534.74 kB | Adobe PDF | Visualizar/Abrir |