Por favor, use este identificador para citar o enlazar este ítem:
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 | |
| Aparece en las colecciones: | Doctorado en Ciencias Computacionales |
Cargar archivos:
| Fichero | Tamaño | Formato | |
|---|---|---|---|
| PerezSuA.pdf | 765.21 kB | Adobe PDF | Visualizar/Abrir |