Novas heurísticas para o agrupamento de dados pela soma mínima de distâncias quadráticas

Detalhes bibliográficos
Ano de defesa: 2017
Autor(a) principal: Pereira, Thiago Correia
Orientador(a): Aloise, Daniel
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA E DE COMPUTAÇÃO
Departamento: Não Informado pela instituição
País: Brasil
Palavras-chave em Português:
VNS
Área do conhecimento CNPq:
Link de acesso: https://repositorio.ufrn.br/jspui/handle/123456789/24010
Resumo: 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.