An annealing-evolution technique for clustering

• Autorzy: Pakhira M. K. , Bandyopadhyay S. , Maulik U.
• Języki publikacji: EN

Abstrakty

EN

An efficient partitional clustering technique, called Annealing-Evolution-clustering (ANEV-clustering), and its fuzzy version, that integrate the power of simulated annealing for obtaining minimum energy configuration, and the searching capability of evolutionary programming are proposed in this article. Two other evolutionary programming based clustering techniques are also developed where Gauss and Cauchy mutation strategies have been used. The clustering methodology is used to search for appropriate cluster centers in multi-dimensional feature space such that a similarity metric of the resulting clusters is optimized. In ,AN.EV-clustering, data points are redistributed among the clusters probabilistically in the mutation phase of the evolution process, so that points that are farther away from the cluster center have higher probabilities of migrating to other clusters than those which are closer to it. The superiority of the AN EV -clustering algorithm over the widely used fc-means algorithm, simulated annealing and conventional evolutionary programming based clustering algorithms is extensively demonstrated for artificial and real life data sets. For the fuzzy clustering algorithm, we have compared the results with the well known fuzzy c-means algorithm. The proposed crisp clustering method is also used for classifying the pixels of a satellite image of a part of the city of Kolkata.

Słowa kluczowe

EN

clustering; annealing-evolution technique

PL

grupowanie danych

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2004
• Tom: Vol. 29, No. 4
• Strony: 345--372
• Opis fizyczny: Bibliogr. 27 poz.

Twórcy

autor

Pakhira M. K.

• Dept. of Computer Science and Engineering, Kalyani Govt. Engg. College, Kalyani 741235, India

autor

Bandyopadhyay S.

• Machine Intelligence Unit, Indian Statistical Institute, 203, B.T. Road, Calcutta 700 108, India

autor

Maulik U.

• Dept. of Computer Science, Jadavpur University, Kolkata 700 032, India

Bibliografia

• [1] J. T. Toil and R. C. Gonzalez, Pattern Recognition Principles. Reading: Addison-Wesley, 1974.
• [2] J. A. Hartigan, Clustering Algorithms. Wiley, 1975.
• [3] P. A. Devijver and J. Kittler, Pattern Recognition : A Statistical Approach. London: Prentice-Hall, 1982.
• [4] A. K. Jain and R. C. Dubes, Algorithms for Clustering Data. Englewood Cliffs, NJ: Prentice-Hall, 1988.
• [5] M. R. Anderberg, Cluster Analysis for Application. Academic Press, 1973.
• [6] S. Z. Selim and M. A. Ismail, "K-means type algorithms : A generalized convergence theorem and characterization of local optimality," IEEE Trans. Pattern Anal. Mach. Intell., vol. 6, 1984, pp. 81-87.
• [7] S. Kirkpatrik, C. Gelatt, and M. Vecchi, "Optimization by simulated annealing," Science, vol. 220, 1983, pp. 671-680.
• [8] Z. Michalewicz, Genetic Algorithm + Data Structure = Evolution Program. New York: Springer-Verlag, 1992.
• [9] T. Bäck, Evolutionary algorithms in theory and practice. New York: Oxford University Press, 1996.
• [10] S. Bandyopadhyay, U. Maulik, and M. K. Pakhira, "Partitional clustering using simulated annealing with probabilistic redistribution," International Journal Pattern Recognition and Artificial Intelligence, vol. 15, 2001, pp. 269-285.
• [11] M. Jianchiang and A. K. Jain, "A self organizing network for hyperellipsoidal clustering (HEC)," in IEEE World Congress on Computational Intelligence, vol. 5, 1994, pp. 2967-2972.
• [12] K. Younis, M. Karim, R. Hardie, J. Loomis, and S. Rogers, "Clustering merging based on weighted mahalanobis distance with application in digital mammograph," in Proc. IEEE 1998 National Aerospace and Electronics Conference NAECON, 1998, pp. 525-530.
• [13] H. Spath, Cluster Analysis Algorithms. Chichester, UK: Ellis Horwood, 1989.
• [14] J. C. Bezdek, Fuzzy mathematics in pattern classification. PhD thesis, Cornell University, Ithaca, NY, 1973.
• [15] N. R. Pal and J. C. Bezdek, "On cluster validity for the fuzzy c-means model," IEEE Transaction on Fuzzy Systems, vol. 3, no. 3, 1995, pp. 370-379.
• [16] X. Yao, Y. Liu, and G. Lin, "Evolutionary programming made faster," IEEE Transaction on Evolutionary Computation, vol. 3, no. 2, 1999, pp. 82-102.
• [17] S. K. Pal and D. D. Majumder, "Fuzzy sets and decision making approaches in vowel and speaker recognition," IEEE Trans. Syst., Man, Cybern., vol. SMC-7, 1977, pp. 625-629.
• [18] R. A. Fisher, "The use of multiple measurements in taxonomic problems," Annals of Eugenics, vol. 3, 1936, pp. 179-188.
• [19] R. A. Johnson and D. W. Wichern, Applied Multivariate Statistical Analysis. Prentice-Hall, 1982.
• [20] D. P. Mandal, C. A. Murthy, and S. K. Pal, "Analysis of IRS imagery for detecting man-made objects with a multivalued recognition system," IEEE Trans, on Syst., Man, Cybern., Part A, vol. 26, 1996, pp. 241-247.
• [21] S. Bandyopadhyay and S. K. Pal, "Pixel classification using variable string genetic algorithms with chromosome differentiation," IEEE Trans. on Geosciences and Remote Sensing, vol. 39, 2001, pp. 303-308.
• [22] S. Bandyopadhyay, C. A. Murthy, and S. K. Pal, "Supervised pattern classification by surface fitting with genetic algorithm," Journal of PINSA, vol. 67-A, 2001, pp. 295-314.
• [23] S. K. Pal, A. Ghosh, and B. Umashankar, "Segmentation with remotely sensed images with fuzzy thresholding, and quantitative evaluation," International Journal of Remote Sensing, vol. 21, 2000, pp. 2269-2300.
• [24] J. C. Bezdek, "Cluster validity with fuzzy sets," Journal of Cybernetics, vol. 3, 1974, pp. 58-73.
• [25] D. L. Davies and D. W. Bouldin, "A cluster separation measure," IEEE Trans. on Patt. Anal. Mach. Intell., vol. 1, 1979, pp. 224-227.
• [26] J. C. Dunn, "A fuzzy relative of the isodata process and its use in detecting compact well separated clusters," Journal of Cybernetics, vol. 3, 1973, pp. 32-57.
• [27] J. C. Bezdek and N. R. Pal, "Some new indexes of cluster validity," IEEE Trans. Syst, Man, Cyberns., vol. 28, 1998, pp. 301-315.