O problema de clusterização (agrupamento) consiste em, a partir de uma base de dados,
agrupar os elementos de modo que os mais similares fiquem no mesmo cluster (grupo),
e os elementos menos similares fiquem em clusters distintos. Há várias maneiras de se
realizar esses agrupamentos. Uma das mais populares é a hierárquica, onde é criada uma
hierarquia de relacionamentos entre os elementos. Há vários métodos de se analisar a
similaridade entre elementos no problema de clusterização. O mais utilizado entre eles é o
método single linkage, que agrupa os elementos que apresentarem menor distância entre si.
Para se aplicar a técnica em questão, uma matriz de distâncias é a entrada utilizada. Esse
processo de agrupamento gera ao final uma árvore invertida conhecida como dendrograma.
O coeficiente de correlação cofenética (ccc), obtido após a construção do dendrograma,
é utilizado para avaliar a consistência dos agrupamentos gerados e indica o quão fiel o
dendrograma está em relação aos dados originais. Dessa forma, um dendrograma apresenta
agrupamentos mais consistentes quando o ccc for o mais próximo de um (1) . O problema
de clusterização em todas as suas vertentes, inclusive a clusterização hierárquica (objeto
de estudo nesse trabalho), pertence a classe de problemas NP-Completo. Assim sendo, é
comum o uso de heurísticas para obter soluções de modo eficiente para esse problema. Com
o objetivo de gerar dendrogramas que resultem em melhores ccc, é proposto no presente
trabalho um novo algoritmo que utiliza os conceitos da metaheurística GRASP. Também
é objetivo deste trabalho implementar tal solução em computação paralela em um cluster
computacional, permitindo assim trabalhar com matrizes de dimensões maiores. Testes
foram realizados para comprovar o desempenho do algoritmo proposto, comparando os
resultados obtidos com os gerados pelo software R. / The problem of clustering (grouping) consists of, from a database, group the elements so
that more queries are in the same cluster (group) and less similar elements are different
clusters. There are several ways to accomplish these groupings. One of the most popular is
the hierarchical, where a hierarchical relationships between the elements is created. There
are several methods of analyzing the similarity between elements in the clustering problem.
The most common among them is the single linkage method, which brings together the
elements that are experiencing less apart. To apply the technique in question, distance
matrix is the input used. This grouping process generates the end an inverted tree known
as dendrogram. The cophenetic correlation coefficient (ccc), obtained after the construction
of the dendrogram is a measure used to evaluate the consistency of the clusters generated
and indicates how faithful he is in relation to the original data. Thus, a dendrogram gives
more consistent clusters when the ccc is closer to one (1). The clustering problem in all
its aspects, including hierarchical clustering (object of study in this work), belongs to
the class of NP-complete problems. Therefore, it is common to use heuristics for efficient
solutions to this problem. In order to generate dendrograms that result in better ccc, it is
proposed in this paper a new algorithm that uses the concepts of GRASP metaheuristic.
It is also objective of this work to implement such a solution in parallel computing in a
computer cluster, thus working with arrays larger. Tests were conducted to confirm the
performance of the proposed algorithm, comparing the results with those generated by
the software R.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.uft.edu.br:11612/974 |
| Date | 30 March 2016 |
| Creators | Ribeiro Filho, Napoleão Póvoa |
| Contributors | Rocha, Marcelo Lisboa |
| Publisher | Universidade Federal do Tocantins, Palmas, Programa de Pós-Graduação em Modelagem Computacional de Sistemas - PPGMCS, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Repositório Institucional da UFT, instname:Universidade Federal do Tocantins, instacron:UFT |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0029 seconds