×

An aggregated clustering approach using multi-ant colonies algorithms. (English) Zbl 1095.68106

Summary: This paper presents a multi-ant colonies approach for clustering data that consists of some parallel and independent ant colonies and a queen ant agent. Each ant colony process takes different types of ants moving speed and different versions of the probability conversion function to generate various clustering results with an ant-based clustering algorithm. These results are sent to the queen ant agent and combined by a hypergraph model to calculate a new similarity matrix. The new similarity matrix is returned back to each ant colony process to re-cluster the data using the new information. Experimental evaluation shows that the average performance of the aggregated multi-ant colonies algorithms outperforms that of the single ant-based clustering algorithm and the popular \(K\)-means algorithm. The result also shows that the lowest outliers strategy for selecting the current data set has the best performance quality.

MSC:

68T10 Pattern recognition, speech recognition
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68W05 Nonnumerical algorithms

Software:

AntNet; UCI-ml; HAS-QAP
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Bonabeau, E.; Dorigo, M.; Theraulaz, G., Swarm intelligence—from natural to artificial system, (1999), Oxford University Press New York · Zbl 1003.68123
[2] Dorigo, M.; Gambardella, L.M., Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE trans. evolut. comput., 1, 53-66, (1997)
[3] Gambardella, L.M.; Taillard, E.D.; Dorigo, M., Ant colonies for the quadratic assignment problem, J. oper. res. soc., 50, 167-176, (1999) · Zbl 1054.90621
[4] Maniezzo, V.; Colrni, A., The ant system applied to the quadratic assignment problem, IEEE trans. knowledge data eng., 11, 769-778, (1999)
[5] Colrni, A.; Dorigo, M.; Maniezzo, V.; Trubian, M., Ant system for job shop scheduling, Belgian J. oper. res., 34, 39-53, (1994) · Zbl 0814.90047
[6] Caro, G.D.; Dorigo, M., Antnet: distributed stigmergic control for communication networks, J. artif. intell. res., 9, 317-355, (1998) · Zbl 0910.68182
[7] Cube, C.R.; Zhang, H., Task modeling in collective robotics, Auton robots, 4, 53-72, (1997)
[8] Deneubourg, J.L.; Goss, S.; Franks, N.; Sendova-Franks, A.; Detrain, C.; Chretien, L., The dynamics of collective sorting: robot-like ant and ant-like robot, (), 356-365
[9] E. Lumer, B. Faieta, Diversity and adaptation in populations of clustering ants, in: Proceedings of the Third International Conference on Simulation of Adaptive Behavior: From Animals to Animals, vol. 3, MIT Press, Cambridge, MA, 1994, pp.499-508.
[10] B. Wu, Z. Shi, A clustering algorithm based on swarm intelligence, in: Proceedings of the IEEE International Conferences on Info-tech & Info-net, Beijing, China, 2001, pp.58-66.
[11] J. Handl, B. Meyer, Improved ant-based clustering and sorting in a document retrieval interface. in: J.J.M. Guervos et al., (eds.), Parallel Problem Solving from Nature—PPSN VII, Seventh International Conference, Granada, Spain, 2002 [Online]. Available: http://wwwcip.informatik.uni-erlangen.de/ sijuhand/HandlMeyerPPSN2002.pdf.
[12] V. Ramos, J.J. Merelo, Self-organized stigmergic document maps: environment as a mechanism for context learning, in: E. Alba, F. Herrera, J.J. Merelo et al. (Eds.), AEB’2002—First Spanish Conference on Evolutionary and Bio-Inspired Algorithms, Centro Univ. de Mérida, Mérida, Spain, February 2002, pp. 284-293.
[13] N. Monmarché, M. Slimane, G. Venturini, Antclass: discovery of clusters in numeric data by a hybridization of an ant colony with the \(k\)-means algorithm. Internal Report No. 213, Laboratoire d’Informatique de l’Université de Tours, E3i Tours, 1999 [Online]. Available: http://www.antsearch.univ-tours.fr/publi/MonSliVen99b.pdf
[14] B. Wu, Y. Zheng, S. Liu, Z. Shi, CSIM: a document clustering algorithm based on swarm intelligence, IEEE World Congress on Computational Intelligence, Hawaiian, 2002, pp. 477-482.
[15] Y. Yang, M. Kamel, Clustering ensemble using swarm intelligence, IEEE Swarm Intelligence Symposium, Indianapolis, USA, April, 2003, pp. 65-71.
[16] Michels, R.; Middendorf, M., An ant system for the shortest common supersequence problem, (), 51-61
[17] Middendorf, M.; Reischle, F.; Schmeck, H., Multi colony ant algorithms, J. heuristic, 8, 305-320, (2002) · Zbl 1012.68792
[18] E. Talbi, O. Roux, C. Fonlupt, D. Robillard, Parallel ant colonies for combinatorial optimization problems, in: J. Rolim et al. (Eds.), Parallel and Distributed Processing, vol. 11, IPPS/SPDP’99 Workshops, Lecture Notes in Computer Science, vol. 1586, Springer, Berlin, 1999, pp. 239-247.
[19] Kawamura, H.; Yamamoto, M., Multiple ant colonies algorithm based on colony level interactions, IEICE trans. fund., E83-A, 2, 371-379, (2000)
[20] A. Strehl, J. Ghosh, Cluster ensembles—a knowledge reuse framework for combining partitionings. in: Proceedings of the Conference on Artificial Intelligence (AAAI 2002), AAAI/MIT Press, July 2002, pp. 93-98.
[21] H. Ayad, M. Kamel, Finding natural clusters using multi-clusterer combiner based on shared nearest neighbors, in: Fourth International Workshop on Multiple Classifier Systems (MCS 2003), Lecture Notes in Computer Science, vol. 2709, Springer, Berlin, 2003. · Zbl 1040.68586
[22] P.M. Murpy, D.W. Aha, UCI repository of machine learning databases. University of California, Irvine, CA, 1994. [Online]. Available: http://www.ics.uci.edu/mlearn/MLRepository.html.
[23] [Online]. Available: http://kdd.ics.uci.edu/databases/reuters21578/reuters21578.html.
[24] Y. Yang, M. Kamel, F. Jin, Topic discovery from document using ant-based clustering combination, in: Web Technologies Research and Development—APWeb 2005, 7th Asia-Pacific Web Conference, Shanghai, China, Lecture Notes in Computer Science, vol. 3399, Springer, UK, 2005, pp. 100-108.
[25] Theodoridis, S.; Koutroubas, K., Pattern recognition, (1999), Academic Press New York
[26] Halkidi, M.; Batistakis, Y.; Vazirgiannis, M., On clustering validation techniques, J. intell. inform. syst., 17, 2-3, 107-145, (2001) · Zbl 0998.68154
[27] He, J.; Tan, A.; Tan, C.; Sung, S., On quantitative evaluation of clustering systems, ()
[28] M. Halkidi, M. Vazirgiannis, Y. Batistakis, Quality scheme assessment in the clustering process, in: Proceedings of the Fourth European Conference Principles and Practice of Knowledge Discovery in Databases (PKDD), 2000, pp.165-276. · Zbl 0998.68154
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.