Novas heurísticas para o agrupamento de dados pela soma mínima de distâncias quadráticas
Heurística, VNS, MSSC, Agrupamento de dados.
Devido ao grande volume de dados gerados pelo crescimento de aplicações que provêm novas informações, tanto em volume quanto em variedade, técnicas cada vez mais eficientes são exigidas para classificá-los e processá-los. Uma técnica muito utilizada é o agrupamento de dados, cujo objetivo é extrair conhecimento dos dados através da divisão
de entidades em subconjuntos homogêneos e/ou bem separados. Muitos critérios diferentes podem ser utilizados para expressar a classificação dos dados. Dentre eles, um critério frequentemente utilizado é a soma mínima das distâncias euclidianas quadráticas, do inglês, minimun sum-of-squares clustering (MSSC). Neste critério, entidades são ele-
mentos no espaço n-dimensional. O problema de agrupamento de dados pelo MSSC é NP-árduo, logo heurísticas são técnicas extremamente úteis para este tipo de problema. Este trabalho propõe novas heurísticas, baseadas na busca de vizinhanças variáveis gerais, do inglês, general variable neighborhood search (GVNS). Também é proposto neste
trabalho, a adaptação da heurística reformulation descent (RD) para o problema MSSC,
na forma de duas variantes, de forma inédita na literatura. Os experimentos computa-
cionais mostram que as variantes GVNS propostas neste trabalho apresentam melhores
resultados, em instâncias grandes, que o atual estado da arte para este problema.