Metodologia para agrupamento de dados : uma versão da Busca Tabu para sistema R

Abstract

Metodologias não-hierárquicas para agrupamento de dados têm sido bastante estudadas e utilizadas nas últimas décadas, muitas delas buscando otimizar um critério comum que é o de minimizar a soma dos quadrados das discrepâncias internas aos grupos formados por seus procedimentos. O problema de se agrupar dados com este critério é bastante conhecido na literatura como problema MSSC (Minimum Sum of Squares Clustering). Dentre as metodologias voltadas para a resolução de problema MSSC deve-se citar a já bastante conhecida heurística K-Means. Com o mesmo propósito, muitas metodologias surgiram nas últimas décadas e, dentre as principais, destacam-se as metodologias H-Means, e mais recentemente sua forma não-degenerada H-Means+, as metodologias Tabu Search e VNS. No entanto, em ambiente computacional fortemente demandado por estatísticos, como o sistema computacional R, estas metodologias, com exceção da primeira, ainda não estão disponíveis. O presente trabalho consiste no desenvolvimento computacional, através da linguagem do sistema em referência (R Core Team, 2014), de uma versão híbrida da metodologia de agrupamento não-hierárquico Busca Tabu (ou Tabu Search) com a heurística H-Means+, esta última recentemente implementada em linguagem do sistema R. Resultados computacionais são obtidos para os bancos de dados USArrests e Íris de Fisher, ambos disponíveis no mesmo sistema em referência. Análise comparativa dos agrupamentos, obtidos pelas metodologias K-Means, H-Means+, a versão implementada e denominada HBaseTabu, e versão híbrida das duas primeiras, denominada HK-Means, é apresentada para distintos números de clusters. Os resultados apresentados são validados, no primeiro teste, através dos valores ótimos apresentados por K-Means, e por valores ótimos já conhecidos para os testes realizados com o banco de dados Iris. Através da análise dos resultados obtidos, pode-se observar que a heurística proposta e implementada neste trabalho apresenta resultados compatíveis com aqueles obtidos por K-Means e demonstra, em vários casos, superioridade sobre as heurísticas H-Means+ e HK-Means. Em situações em que o número de agrupamentos é maior que três. Em alguns casos os resultados obtidos mostraram-se melhores que os apresentados pela heurística K-Means, quando inicializou-se a metodologia implementada, HBaseTabu, com a melhor solução apresentada por K-Means, o que demonstra o poder de eficiência computacional da proposta HBaseTabu.