Novas heurísticas para o agrupamento de dados pela soma mínima de distâncias quadráticas - Pereira, Thiago Correia (2017)
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. Critérios 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 elementos 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 computacionais mostram que as variantes GVNS propostas neste trabalho apresentam melhores resultados, para instâncias grandes.