Dynamic Clustering using Particle Swarm Optimization with Application in Unsupervised Image Classification

Authors: Mahamed G.H. Omran, Andries P Engelbrecht, Ayed Salman

Abstract:

A new dynamic clustering approach (DCPSO), based on Particle Swarm Optimization, is proposed. This approach is applied to unsupervised image classification. The proposed approach automatically determines the "optimum" number of clusters and simultaneously clusters the data set with minimal user interference. The algorithm starts by partitioning the data set into a relatively large number of clusters to reduce the effects of initial conditions. Using binary particle swarm optimization the "best" number of clusters is selected. The centers of the chosen clusters is then refined via the Kmeans clustering algorithm. The experiments conducted show that the proposed approach generally found the "optimum" number of clusters on the tested images.

Keywords: Clustering Validation, Particle Swarm Optimization, Unsupervised Clustering, Unsupervised Image Classification.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1078219

References:

[1] A.K. Jain, M.N. Murty, P.J. Flynn, Data Clustering: A Review, ACM Computing Surveys, vol. 31(3), 264-323,1999.
[2] A.K. Jain, R. Duin, J. Mao, Statistical Pattern Recognition: A Review, IEEE Transactions on Pattern Analysis and Machine Intellgence, vol. 22 (1), 4-37, 2000.
[3] D. Judd, P. Mckinley, A.K. Jain, Large-scale Parallel Data Clustering, IEEE Transactions on Pattern Analysis and Machine Intellgence, vol. 20 (8), 871-876, 1998.
[4] H.M. Abbas, M.M. Fahmy, Neural Networks for Maximum Likelihood Clustering, Signal Processing, vol. 36(1), 111-126, 1994.
[5] G.B. Coleman, H.C. Andrews, Image Segmentation by Clustering, Proc. IEEE, vol. 67, 773-785, 1979.
[6] A.K. Jain, R.C. Dubes, Algorithms for Clustering Data, New Jersey, Prentice Hall, 1988.
[7] S. Ray, R.H. Turi, Determination of Number of Clusters in K-Means Clustering and Application in Colour Image Segmentation, Proceedings of the 4th International Conference on Advances in Pattern Recognition and Digital Techniques (ICAPRDT'99), Calcutta, India, 137-143, 1999.
[8] C. Carpineto, G. Romano, A Lattice Conceptual Clustering System and Its Application to Browsing Retrieval, Machine Learning, vol. 24(2), 95- 122, 1996.
[9] C.-Y. Lee, E.K. Antonsson, Dynamic Partitional Clustering Using Evolution Strategies, In The Third Asia-Pacific Conference on Simulated Evolution and Learning, 2000.
[10] G. Hamerly, C. Elkan, Learning the K in K-means, 7th Annual Conference on Neural Information Processing Systems, 2003.
[11] H. Frigui and R. Krishnapuram, A Robust Competitive Clustering Algorithm with Applications in Computer Vision, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 21(5), 450-465, 1999.
[12] Y. Leung, J. Zhang, Z. Xu, Clustering by Space-Space Filtering, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22(12), 1396-1410, 2000.
[13] M. Halkidi, Y. Batistakis, M. Vazirgiannis, On Clustering Validation Techniques, Intelligent Information Systems Journal, Kluwer Pulishers, vol. 17(2-3), 107-145, 2001.
[14] S. Theodoridis and K. Koutroubas, Pattern Recognition, Academic Press, 1999.
[15] C. Rosenberger and K. Chehdi, Unsupervised Clustering Method with Optimal Estimation of the Number of Clusters: Application to Image Segmentation, International Conference on Pattern Recognition (ICPR'00), vol. 1, 1656-1659 (2000).
[16] L. Kuncheva and J. Bezdek, Nearest Prototype Classification: Clustering, Genetic Algorithms, or Random Search?, IEEE Transactions on Systems, Man, and Cybernetics-Part C: Applications and Reviews, vol. 28(1), 160-164, 1998.
[17] G. Ball and D. Hall, A Clustering Technique for Summarizing Multivariate Data, Behavioral Science, vol. 12, 153-155, 1967.
[18] K. Huang, A Synergistic Automatic Clustering Technique (Syneract) for Multispectral Image Analysis, Photogrammetric Engineering and Remote Sensing, vol. 1(1), 33-40, 2002.
[19] D. Pelleg, A. Moore, X-means: Extending K-means with efficient estimation of the number of clusters, Proceedings of the 17th International Conference on Machine Learning, 727-734, Morgan Kaufmann, San Francisco, CA, 2000.
[20] R. Kass, L. Wasserman, A reference Bayesian test for nested hypotheses and its relationship to the Schwarz criterion, Journal of the American Statistical Association, vol. 90(431), 928-934, 1995.
[21] G. Hamerly, Learning structure and concepts in data using data clustering, PhD Thesis, University of California, San Diego, 2003.
[22] C.S. Wallace, D.L. Dowe, Intrinsic classification by MML - the snob program, Proceedings 7th Australian Joint Conference on Artificial Intelligence, UNE, Armidale, NSW, Australia, 37-44, 1994.
[23] C.S. Wallace, An improved program for classification, Technical Report No. 47, Department of Computer Science, Monash University, Australia, 1984.
[24] R.H. Turi, Clustering-Based Colour Image Segmentation, PhD Thesis, Monash University, Australia, 2001.
[25] C.S. Wallace, D.M. Boulton, An information measure for classification, The Computer Journal, vol. 11, 185-194, 1968.
[26] J.J. Oliver, D. Hand, Introduction to minimum encoding inference, Technical Report No. 94/205, Department of Computer Science, Monash University, Australia, 1994.
[27] H. Bischof, A. Leonardis, A. Selb, MDL principle for robust vector quantization, Pattern analysis and applications, 2, 59-72, 1999.
[28] I. Gath, A. Geva, Unsupervised Optimal Fuzzy Clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 11(7), 773-781, 1989.
[29] A. Lorette, X. Descombes, J. Zerubia, Fully Unsupervised Fuzzy Clustering with Entropy Criterion, International Conference on Pattern Recognition (ICPR'00), vol. 3, 3998-4001, 2000.
[30] N. Boujemaa, On Competitive Unsupervised Clustering, International Conference on Pattern Recognition (ICPR'00), vol. 1, 1631-1634, 2000.
[31] H. Frigui and R. Krishnapuram, Clustering by Competitive Agglomeration, Pattern Recognition Letters, vol. 30(7), 1109-1119, 1997.
[32] H. Frigui and R. Krishnapuram, A Robust Competitive Clustering Algorithm with Applications in Computer Vision, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 21(5), 450-465, 1999.
[33] T. Kohonen, Self-Organizing Maps, Springer Series in Information Sciences, 30, Springer-Verlag, N.Y., 1995.
[34] K. Mehrotra, C. Mohan, Rakka, Elements of Artificial Neural Networks, MIT Press, 1997.
[35] A. Pandya, R. Macy, Pattern Recognition with Neural Networks in C++, CRC Press, 1996.
[36] M. Halkidi, M. Vazirgiannis, Clustering Validity Assessment: Finding the Optimal Partitioning of a data set, Proceedings of ICDM Conference, CA (USA), Nov. 2001.
[37] J. Kennedy, R. Eberhart, Particle Swarm Optimization, Proceedings of IEEE International Conference on Neural Networks, Perth, Australia, vol. 4, 1942-1948, 1995.
[38] J. Kennedy, R. Eberhart, Swarm Intelligence, Morgan Kaufmann, 2001.
[39] A. Engelbrecht, Computational Intelligence: An Introduction, John Wiley and Sons, 2002.
[40] Y. Shi, R. Eberhart, Parameter Selection in Particle Swarm Optimization, Evolutionary Programming VII: Proceedings of EP 98, 591-600, 1998.
[41] P. Suganthan, Particle Swarm Optimizer with Neighborhood Optimizer, Proceedings of the Congress on Evolutionary Computation, 1958-1962, 1999.
[42] Y. Shi, R. Eberhart, A Modified Particle Swarm Optimizer, Proceedings of the IEEE International Conference on Evolutionary Computation, Piscataway, NJ, 69-73, 1998.
[43] J. Kennedy, Small Worlds and Mega-Minds: Effects of Neighborhood Topology on Particle Swarm Performance, Proceedings of the Congress on Evolutionary Computation, 1931-1938, 1999.
[44] J. Kennedy, R. Mendes, Population Structure and Particle Performance, Proceedings of the IEEE Congress on Evolutionary Computation, Honolulu, Hawaii, 2002.
[45] F. Van den Bergh, An Analysis of Particle Swarm Optimizers, PhD Thesis, Department of Computer Science, University of Pretoria, 2002.
[46] F. van den Bergh, A.P. Engelbrecht, A New Locally Convergent Particle Swarm Optimizer, Proceedings of the IEEE Conference on Systems, Man, and Cybernetics, Hammamet, Tunisia, 2002.
[47] J. Kennedy, R. Eberhart, A Discrete Binary Version of the Particle Swarm Algorithm, Proceedings of the Conference on Systems, Man, and Cybernetics, 4104-4109, 1997.