Ant colony metaphor in a new clustering algorithm

• Autorzy: Boryczka U.
• Języki publikacji: EN

Abstrakty

EN

Among the many bio-inspired techniques, ant clustering algorithms have received special attention, especially because they still require much investigation to improve performance, stability and other key features that would make such algorithms mature tools for data mining. Clustering with swarm-based algorithms is emerging as an alternative to more conventional clustering methods, such as k-means algorithm. This proposed approach mimics the clustering behavior observed in real ant colonies. As a case study, this paper focuses on the behavior of clustering procedures in this new approach. The proposed algorithm is evaluated on a number of well-known benchmark data sets. Empirical results clearly show that the ant clustering algorithm (ACA) performs well when compared to other techniques.

Słowa kluczowe

EN

data mining; cluster analysis; ant clustering algorithm

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2010
• Tom: Vol. 39, no 2
• Strony: 343--358
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Boryczka U.

• Institute of Computer Science, University of Silesia, Sosnowiec, Poland

Bibliografia

• BONABEAU, E. (1997) From classical models of morphogenesis to agent-based models of pattern formation. Artificial Life, 3, 191-209.
• BONABEAU, E., DORIGO,M. and THERAULAZ,G. (1999) Swarm Intelligence. From Natural to Artificial Systems. Oxford University Press, New York.
• CHRETIEN, L. (1996) Organisation Spatiale du Materiel Provenant de L’excavation du nid chez Messor Barbarus et des Cadavres d’ouvrieres chez Lasius niger Hymenopterae: Formicidae. PhD thesis, Université Libre de Bruxelles.
• DENEUBOURG, J.-L., Goss, S., FRANKS, N., SENDOVA-FRANKS, A., DETRAIN, C. and CHRETIEN, L.(1991) The dynamics of collective sorting: Robot-like ant and ant-like robot. In: J.A. Meyer and S.W. Wilson, eds., First Conference on Simulation of Adaptive Behavior. From Animals to Animats, 356-365.
• ESTER, M., KRIEGEL, H.-P,, SANDER, J. and XU, X. (1996) A density-based algorithm for discovering clusters in large spatial databases with noise. In: E. Simuoudis, J. Han and U. Fayyard, eds., Second International Conference on Knowledge Discovery and Data Mining, AAAI Press, Portland, USA, 226-231.
• FRANKS, N.R. and SENDOVA-FRANKS, A.B. (1992) Brood sorting by ants: Distributing the workload over the work surface. Behav. Ecol. Sociobiol, 30,109-123.
• GANTI, V., GEHRKE, J. and RAMAKRISHNA, R. (1999) Cactus-clustering categorical data using summaries. In: International Conference on Knowledge Discovery and Data Mining, San Diego, USA, 73-83.
• GUHA, S.. RASTOGI, R. and SHIM, K. (1998) Cure: an efficient clustering algorithm algorithm for large databases. In: ACM SIGMOD International Conference on the Management of Data, Seatle, USA, 73-84.
• GUTOWITZ, H. (1993) Complexity - Seeking Ants. Unpublished report.
• HALKIDI, M., VAZIRGIANNIS, M. and BATISTAKIS, I. (2000) Quality scheme assesment in the clustering process. In: Proceedings of the Fourth European Conference on Principles of Data Mining and Knowledge Discovery. LNCS 1910, Springer Verlag, 265-267.
• HANDL, J. and MEYER, B. (2002) Improved ant-based clustering and sorting in a document retrieval interface. In: PPSN - VII. Seventh international Conference on Parallel Problem Solving from Nature, LNCS 2439, Berlin, 913-923.
• HANDL, J., KNOWLES, J. and DORIGO, M. (2003) Ant-based clustering: a comparative study of its relative performance with respect to k-means, average link and id-som. Technical Report 24, IRIDIA, Université Libre de Bruxelles, Belgium.
• KARYPIS, G., HAN, E.-H. and KUMAR, V. (1999) Chameleon: a hierarchical clustering algorithm using dynamic modeling. Computer 32, 32-68.
• KAUFMAN, L. and RUSSEEUW, P. (1990) Finding Groups in Data: An Introduction to Cluster Analysis. John Wiley and Sons.
• LUMER, E. and FAIETA, B. (1994) Diversity and adaptation in populations of clustering ants. In: Third Intern. Conference on Simulation of Adaptive Behavior: From animals to Animats 3. MIT Press, Cambridge, 489-508.
• MACQUEEN, J. (1967) Some methods for classification and analysis of multi-variate observations. In: 5th Berkeley Symposium on Mathematics, Statistics and Probability, 281-296.
• OPRISAN, S.A., HOLBAN, V. and MOLDOVEANU, B. (1996) Functional self-organisation performing wide-sense stochastic processes. Phys. Lett. A 216,303-306.
• RIJSBERGEN, C.V. (1979) Information Retrieval, 2nd edition. Butterworth, London.
• SKINDEROWICZ, R. (2007) Zastosowanie algorytmow mrowkowych do grupowania danych. (Application of ant algorithms to data grouping; in Polish). Master’s thesis, Institute of Computer Science, University of Silesia.