Downloads:

• Java source code of the algorithm described by Handl and Meyer (2002). Includes a visualization of the clustering process.

• C++ source code of the algorithm described by Handl, Knowles and Dorigo (2005). Includes retrieval of clusters off the grid and measures for the computation of clustering quality.

Ant-based clustering

Julia Handl, Joshua Knowles, Bernd Meyer and Marco Dorigo

Keywords: ant-based clustering, ant algorithm, ant-based heuristic, data-mining, determination of the number of clusters

Ant-based clustering and sorting has been first introduced by Deneubourg et al to explain different types of naturally-occurring emergent phenomena. It is an instance of the broad category of ant algorithms, that is, algorithms that model some behavior observed in real ants. In the case of ant-based clustering and sorting, two related types of natural ant behavior are modeled. When clustering, ants gather items to form heaps; an example of this being the cemetery formation (i.e., the clustering of dead corpses) observed in the species Pheidole pallidula. And when sorting, ants discriminate between different kinds of items and spatially arrange them according to their properties; a type of activity that can, for example, be observed in nests of Leptothorax unifasciatus where larvae are arranged as a function of their size.

In their paper, Deneubourg et al proposed a continuous model to describe these behaviors. From this, a discrete Monte Carlo model was derived, which was experimentally validated. In the computer simulation ants were represented as simple agents, which randomly moved in their environment, a square grid with periodic boundary conditions. Items that were scattered within this environment could be picked up, transported and dropped by the agents. These operations were biased by the distribution of items within the agents' local neighborhoods, such that items that were either isolated or surrounded by dissimilar ones were more likely to be picked up, and then tended to be dropped again in the vicinity of similar ones. As a result, a clustering and sorting of the items on the grid was obtained.

Publications:

1. Handl, J., Knowles, J., and Dorigo, M. (2005). Ant-based clustering and topographic mapping. Artificial Life 12(1) PDF

2. Handl, J., Knowles, J., and Dorigo, M. (2004). Strategies for the increased robustness of ant-based clustering. In Engineering Self-Organising Systems, Vol. 2977 of Lecture Notes in Computer Science (pp. 90--104). Heidelberg, Germany: Springer-Verlag. PDF

3. Handl, J. Ant-based methods for tasks of clustering and topographic mapping: extensions, analysis and comparison with alternative techniques. (2003) Masters Thesis, Universität Erlangen-Nürnberg, Erlangen, Germany. PDF

4. Handl, J., Knowles, J., and Dorigo, M. (2003). On the performance of ant-based clustering. In Design and Application of Hybrid Intelligent Systems, Vol. 104 of Frontiers in Artificial Intelligence and Applications (pp. 204-213). Amsterdam, The Netherlands: IOS Press. PDF

5. 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 1D-som. Technical Report TR/IRIDIA/2003-24. IRIDIA, Universite Libre de Bruxelles, Belgium. PDF

6. Handl, J. and Meyer, B. (2002). Improved ant-based clustering and sorting in a document retrieval interface. In Proceedings of the Seventh International Conference on Parallel Problem Solving from Nature, Vol. 2439 of Lecture Notes in Computer Science (pp. 913-923). Berlin, Germany: Springer-Verlag. PDF

7. Handl, J. Visualizing Internet-Queries using Ant-based Heuristics. (2001) Honours Thesis, Monash University, Melbourne, Australia. PDF