Uma nova heurística para agrupamento de dados pela soma mínima de distâncias quadrática
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 classifica-los e processa-los. Uma técnica muito utilizada é agrupamento de dados, cujo objetivo é extrair características das entidades dividindo-as em subconjuntos homogêneos e/ou bem separados. Muitos critérios diferentes podem ser utilizados para expressar a separaçã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-squared clustering (MSSC). 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 uma nova heurística, que possui como principal característica a preocupação com a posição dos centroides durante a construção da solução, para resolver o problema MSSC. Resultados preliminares já apontam melhorias do algoritmo proposto sobre a heurística bem consolidada na literatura, J-Means. Além disso, este trabalho almeja utilizar o algoritmo proposto como busca local na metaheurística Variable Neighborhood Search (VNS), assim como combinar as duas heurísticas comparadas com o objetivo de superar as melhores soluções conhecidas na literatura.