Publicado em 23 de fevereiro de 2023.

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.