Algoritmo genético híbrido aplicado ao problema de agrupamento de dados

AUTOR(ES)
FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

31/08/2009

RESUMO

Agrupamento de dados é uma tarefa que divide um conjunto de dados em subconjuntos de forma que elementos associados a um mesmo grupo sejam mais similares entre si do que em relação a elementos de outros grupos. Ao organizar os dados em grupos é possível identificar similaridades e diferenças entre eles, extrair informações relevantes e inferir conclusões úteis a respeito das características dos dados. O problema de agrupamento de dados pode ser considerado como uma tarefa de otimização, uma vez que se pretende encontrar a melhor combinação de partições dentre todas as combinações possíveis. Uma abordagem que pode ser aplicada para resolver o problema de agrupamento é o uso de metaheurísticas, que são procedimentos capazes de escapar de ótimos locais, pois o uso de métodos exatos se torna computacionalmente inviável. Entretanto, a maioria das metaheurísticas aplicadas ao problema de agrupamento não são escalonáveis para bases reais e comerciais, são mais efetivas nos casos em que a instância do problema é menor. O custo computacional necessário para calcular as soluções se torna maior em instâncias maiores do problema. Por esse motivo, procedimentos híbridos que exploram a combinação de metaheurísticas representam uma abordagem promissora para a resolução do problema de agrupamento. Este trabalho apresenta uma proposta de Algoritmo Genético Híbrido de Agrupamento que associa ao processo de busca global uma heurística de busca local e cuja população inicial é gerada por técnicas de agrupamento. Tais melhorias têm como objetivo direcionar a busca para soluções mais próximas do ótimo global. É realizada uma avaliação experimental em bases de dados reais e sintéticas com o objetivo de verificar se a abordagem proposta apresenta uma melhoria em relação aos algoritmos avaliados. O resultado dessa análise mostra que o algoritmo proposto apresenta um desempenho melhor do que quatro entre os seis algoritmos avaliados. Para complementar a análise é realizada uma avaliação do tempo de execução, cujo objetivo é quantificar a diferença entre a abordagem proposta e os demais algoritmos avaliados. O resultado mostra que o tempo de execução da abordagem proposta é viável, porém é consideravelmente maior do que os tempos de execução dos algoritmos considerados de rápida convergência

ASSUNTO(S)

programação heurística algoritmos genéticos análise por agrupamento heuristic programming genetic algorithms cluster analysis combinatorial optimization otimização combinatória ciencia da computacao

ACESSO AO ARTIGO

Documentos Relacionados