PERFORMANCE ANALYSIS OF A PROPOSED ANT-BASED CLUSTERING ALGORITHM

Ano: 2011 | Volume: 3 | Número: 1

Autores: Rosangela Villwock, Maria Teresinha Arns Steiner

Palavras-chave: Mineração de Dados, Agrupamento de Padrões, Metaheurística

Resumo Português:

No algoritmo de Agrupamento baseado em Formigas, os padrões são espalhados
numa grade e a cada formiga é atribuído um padrão. As formigas são responsáveis por
carregar, transportar e descarregar os padrões na grade. Após a convergência do algoritmo de
agrupamento, a recuperação dos grupos é feita usando-se as posições dos padrões na grade. O
objetivo do presente estudo foi avaliar o desempenho de um Algoritmo de Agrupamento
baseado em Formigas Proposto (ACAP), comparativamente ao Algoritmo de Agrupamento
baseado em Formigas Modificado (ACAM). As principais modificações foram: substituição
do padrão carregado pela formiga caso este não seja descarregado em 100 iterações
consecutivas; comparação da probabilidade de descarregar um padrão na posição de sorteio
com a probabilidade de descarregar este padrão em sua posição atual; avaliação da
probabilidade de descarregar um padrão em uma nova posição, caso o padrão não seja
descarregado na posição de sorteio e sim numa posição vizinha. Para a avaliação do
desempenho do algoritmo aqui proposto foram utilizados dois exemplos reais: ÍRIS e WINE.
Os resultados mostram que o ACAP deste estudo foi melhor do que o ACAM para os dois
exemplos.

Resumo Inglês:

In the Ant-Based Clustering Algorithm, patterns are spread throughout a grid
and each ant is assigned a pattern. The ants are responsible for picking, transporting and
dropping patterns on the grid. After the clustering algorithm converges, cluster recovery is
done by using the positions of patterns on the grid. The purpose with this study was to
evaluate the performance of the Ant-based Clustering Algorithm Proposed (ACAP) compared
to the Ant-based Clustering Algorithm – Modified version (ACAM). The major changes
were: replacement of the pattern carried by an ant in case it was not dropped within 100
consecutive iterations, comparing the probability of dropping a pattern at a random position
with the probability of dropping this pattern at its current position; evaluate the probability of
dropping a pattern at a new position, if the pattern is not dropped at a random position, but at
a neighboring position. To assess the performance of the algorithm thus proposed, two real
examples were used: ÍRIS and WINE. The results show that the ACAP in this study was
better than the ACAM for the two examples.