Please use this identifier to cite or link to this item: http://inaoe.repositorioinstitucional.mx/jspui/handle/1009/714
Algoritmos dinámicos para el agrupamiento con traslape
AIREL PEREZ SUAREZ
JOSE FRANCISCO MARTINEZ TRINIDAD
Acceso Abierto
Atribución-NoComercial-SinDerivadas
Data mining
Algorithm theory
Graph theory
Clustering is a Data Mining and Machine Learning technique that has been used in several areas like medicine, marketing, social network analysis and bioinformatics, among others. Although, several clustering algorithms have been proposed, they have some drawbacks that are solved through this PhD research. Most clustering algorithms do not allow building overlapping clusterings. However, there are several applications like topics detection, document segmentation, information organization and news analysis, among others, where it is common for objects to belong to more than one cluster; these applications need clustering algorithms able to build overlapping clusters. The majority of the current overlapping clustering algorithms have some drawbacks which can reduce their usefulness in practical applications. These limitations are mainly related with: (a) the necessity of tuning several parameters whose values depend on the collection to cluster, (b) the production of a large number of clusters, usually with a low average of elements per cluster, and (c) the production of clusters with high overlapping. Besides, most of overlapping clustering algorithms are unable to satisfy new requirements such as: (i) the necessity of updating the clustering when the collection changes and (ii) the necessity of building hierarchies of clusters, in which the overlapping among the clusters of the same level are allowed. This PhD research introduces two new overlapping clustering algorithms, DClustR and DHClustR, both satisfy the requirements above mentioned and solve the limitations a), b) and c). DClustR is a dynamic and non-hierarchical algorithm, based on concepts of graph theory, which builds a set of overlapping clusters. DClustR introduces a new strategy for building the clustering and also it introduces a new strategy for updating this clustering when the collection changes, due to multiple additions, eliminations or modifications of objects. On the other hand, DHClustR is a dynamic agglomerative hierarchical clustering algorithm which builds a hierarchy of overlapping clusters, using the DClustR algorithm for building the clustering of each level. For building the clustering of the first level, DClustR is applied over the collection of objects; from this point on, the objects to be clustered at each level are the clusters of the previous level.
El agrupamiento es una técnica del Aprendizaje Automático y de la Minería de Datos, que ha sido utilizada en varias áreas como la medicina, el marketing, el análisis de redes sociales y la bioinformática, entre otras. A pesar de los resultados que se han alcanzado hasta el momento en el estudio y desarrollo de nuevos algoritmos de agrupamiento, todavía existen algunas limitaciones en los mismos, que son solucionadas en el marco de esta investigación doctoral. La mayoría de los algoritmos de agrupamiento no permiten formar grupos con traslape. Sin embargo, existen varias aplicaciones como la detección de tópicos, la segmentación de documentos, la organización de información y el análisis de noticias, entre otras, donde los objetos pueden pertenecer a más de un grupo; este tipo de aplicaciones necesitan de algoritmos de agrupamiento que permitan formar grupos con traslape. Los algoritmos traslapados que se han propuesto hasta el momento, tienen un conjunto de limitaciones que pueden reducir su utilidad en ciertos problemas prácticos. Estas limitaciones están relacionadas principalmente con: (a) la necesidad de ajustar varios parámetros cuyos valores dependen de la colección a agrupar, (b) la construcción de un gran número de grupos, generalmente con un bajo promedio de elementos por grupo y (c) la obtención de agrupamientos con un alto nivel de traslape. Adicionalmente, la mayoría de los algoritmos de agrupamiento traslapado son incapaces de satisfacer nuevos requerimientos tales como: (i) la necesidad de actualizar el agrupamiento previamente construido, cuando cambia la colección y (ii) la necesidad de crear estructuras jerárquicas, en las cuales sea permitido el traslape entre los grupos de un mismo nivel. En este trabajo de investigación doctoral se introducen dos nuevos algoritmos de agrupamiento traslapado, DClustR y DHClustR, que abordan los requerimientos anteriormente comentados y que además, solucionan las limitaciones a), b) y c). DClustR es un algoritmo dinámico no jerárquico, que se basa en conceptos de Teoría de grafos para formar un conjunto de grupos con traslape. DClustR introduce una nueva estrategia para la formación del agrupamiento, así como una nueva estrategia para la actualización de este conjunto de grupos, cuando ocurren múltiples adiciones, eliminaciones y modificaciones de objetos de la colección.
Instituto Nacional de Astrofísica, Óptica y Electrónica
2011
Tesis de doctorado
Español
Estudiantes
Investigadores
Público en general
Perez-Suarez A.
CIENCIA DE LOS ORDENADORES
Versión aceptada
acceptedVersion - Versión aceptada
Appears in Collections:Doctorado en Ciencias Computacionales

Upload archives


File SizeFormat 
PerezSuA.pdf765.21 kBAdobe PDFView/Open