Novas abordagens heurísticas baseadas em Busca em Vizinhança Variávelpara Agrupamento Balanceado de Dados
clustering; otimização; data mining
Após vários avanços na tecnologia de captação e armazenamento de dados e do crescimento de aplicações que provêm novas informações, o número de elementos informacionais disponíveis é enorme tanto em volume quanto em variedade. Com esse aumento na quantidade de informações, a necessidade de entendê-los e resumi-los se tornou cada vez mais urgente. O Agrupamento Balanceado de Dados, do inglês Balanced Clustering (BC), visa encontrar grupos de entidades similares que possuam aproximadamente o mesmo tamanho. Neste trabalho, são propostas novas abordagens heurísticas baseadas na metaheurística Busca em Vizinhança Variável, do inglês Variable Neighborhood Search (VNS), para o problema NP-árduo de agrupamento de dados usando o critério da soma mínima quadrática com restrição de balanceamento dos grupos. A primeira heuristica VNS utiliza como busca local o processo de resolver um problema não linear inteiro misto com o auxilio do solver SNOPT. A segunda usa como busca local uma vizinhança de trocas de elementos entre grupos. Os algoritmos encontrados na literatura não são escaláveis ao passo que aumentamos o tamanho do problema para além de 5000 elementos. Os resultados preliminares, que fizeram uso de instâncias difundidas na literatura, já mostram resultados melhores do que os encontrados pelos algoritmos estado da arte.