Estudo comparativo de heurísticas para resolução de problemas MSSC utilizando o Sistema de Operação 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 estudo dessas novas heurísticas e na modificação da versão implementada da Busca Tabu e H-Means para melhorar os resultados já conhecidos com alguns bancos de dados. 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, a versão implementada e modificada da HBaseTabu e do H-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 implementada neste trabalho apresenta resultados melhores daqueles obtidos por K-Means e demonstram, em vários casos, superioridade sobre as demais heurísticas, o que mostra o poder de e ciência das mudanças realizadas na implementação computacional desse novo algoritmo.