Melhorando o desempenho da técnica de clusterização hierárquica Single Linkage utilizando a Metaheurística GRASP (Atena Editora)

Abstract

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.