×

On the efficiency of evolutionary fuzzy clustering. (English) Zbl 1180.90380

Summary: This paper tackles the problem of showing that evolutionary algorithms for fuzzy clustering can be more efficient than systematic (i.e. repetitive) approaches when the number of clusters in a data set is unknown. To do so, a fuzzy version of an Evolutionary Algorithm for Clustering (EAC) is introduced. A fuzzy cluster validity criterion and a fuzzy local search algorithm are used instead of their hard counterparts employed by EAC. Theoretical complexity analyses for both the systematic and evolutionary algorithms under interest are provided. Examples with computational experiments and statistical analyses are also presented.

MSC:

90C70 Fuzzy and other nonstochastic uncertainty mathematical programming

Software:

clusfind; NERF
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Alves, V.S., Campello, R.J.G.B., Hruschka, E.R.: A fuzzy variant of an evolutionary algorithm for clustering. In: Proc. IEEE Int. Conf. on Fuzzy Systems, London, UK, pp. 375–380 (2007)
[2] Babu, G.P., Murty, M.N.: Clustering with evolution strategies. Pattern Recognit. 27(2), 321–329 (1994)
[3] Babuška, R.: Fuzzy Modeling for Control. Kluwer, Dordrecht (1998)
[4] Backer, E., Jain, A.K.: A clustering performance measure based on fuzzy set decomposition. IEEE Trans. Pattern Anal. Mach. Intell. 3, 66–75 (1981) · Zbl 0454.62057
[5] Bandyopadhyay, S., Maulik, U.: Genetic clustering for automatic evolution of clusters and application to image classification. Pattern Recognit. 35, 1197–1208 (2002) · Zbl 1001.68926
[6] Barni, M., Cappellini, V., Mecocci, A.: A possibilistic approach to clustering. IEEE Trans. Fuzzy Syst. 4, 393–396 (1996)
[7] Bezdek, J.C.: Cluster validity with fuzzy sets. J. Cybern. 3, 58–73 (1974) · Zbl 0294.68035
[8] Bezdek, J.C.: Mathematical models for systemics and taxonomy. In: Proc. 8th Int. Conf. on Numerical Taxonomy, San Francisco, USA (1975) · Zbl 0362.62067
[9] Bezdek, J.C.: Pattern Recognition with Fuzzy Objective Function Algorithm. Plenum, New York (1981) · Zbl 0503.68069
[10] Bezdek, J.C., Dunn, J.: Optimal fuzzy partition: a heuristic for estimating the parameters in a mixture of normal distributions. IEEE Trans. Comput. C-24, 835–838 (1975) · Zbl 0308.68078
[11] Bezdek, J.C., Hathaway, R.J.: Optimization of fuzzy clustering criteria using genetic algorithms. In: Proc. IEEE WCCI, USA, Orlando, pp. 589–594 (1994)
[12] Bezdek, J.C., Pal, N.R.: Some new indexes of cluster validity. IEEE Trans. Syst. Man Cybern. B 28, 301–315 (1998)
[13] Bezdek, J.C., Hathaway, R.J., Howard, R.E., Wilson, C.A., Windham, M.P.: Local convergence analysis of a grouped variable version of coordinate descent. J. Optim. Theory Appl. 54, 471–477 (1987a) · Zbl 0597.90076
[14] Bezdek, J.C., Hathaway, R.J., Sabin, M.J., Tucker, H.T.: Convergence theory for fuzzy C-means: counterexamples and repairs. IEEE Trans. Syst. Man Cybern. SMC-17, 873–877 (1987b) · Zbl 0653.68091
[15] Campello, R.J.G.B., Hruschka, E.R.: A fuzzy extension of the silhouette width criterion for cluster analysis. Fuzzy Sets Syst. 157(21), 2858–2875 (2006) · Zbl 1103.68674
[16] Campello, R.J.G.B., Hruschka, E.R.: Fuzzy silhouette: an alternative cluster validity measure. In: Proc. 11th IFSA World Congress, Beijing, China, pp. 603–608 (2005)
[17] Cannon, R.L., Dave, J.V., Bezdek, J.C.: Efficient implementation of the fuzzy C-means clustering algorithms. IEEE Trans. Pattern Anal. Mach. Intell. PAMI-8, 248–255 (1986) · Zbl 0602.68084
[18] Cheng, T.W., Goldgof, D.B., Hall, L.O.: Fast fuzzy clustering. Fuzzy Sets Syst. 93, 49–56 (1998) · Zbl 0920.68123
[19] Davé, R.N., Krishnapuram, R.: Robust clustering methods: a unified view. IEEE Trans. Fuzzy Syst. 5, 270–293 (1997)
[20] Davis, L.: Handbook of Genetic Algorithms. International Thomson Computer Press (1996)
[21] Dumitrescu, D., Lazzerini, B., Jain, L.C.: Fuzzy Sets and their Application to Clustering and Training. CRC Press, New York (2000)
[22] Dunn, J.C.: A fuzzy relative of the isodata process and its use in detecting compact well-separated clusters. J. Cybern. 3, 32–57 (1973) · Zbl 0291.68033
[23] Egan, M.A., Krishnamoorthy, M., Rajan, K.: Comparative study of a genetic fuzzy C-means algorithm and a validity guided fuzzy C-means algorithm for locating clusters in noisy data. In: Proc. IEEE WCCI, Anchorage, USA, pp. 440–445 (1998)
[24] El-Sonbaty, Y., Ismail, M.A.: Fuzzy clustering for symbolic data. IEEE Trans. Fuzzy Syst. 6, 195–204 (1998) · Zbl 0921.68082
[25] Eschrich, S., Ke, J., Hall, L.O., Goldgof, D.B.: Fast accurate fuzzy clustering through data reduction. IEEE Trans. Fuzzy Syst. 11, 262–270 (2003)
[26] Everitt, B.S., Landau, S., Leese, M.: Cluster Analysis, 4th edn. Arnold, Paris (2001) · Zbl 1205.62076
[27] Falkenauer, E.: Genetic Algorithms and Grouping Problems. Wiley, New York (1998) · Zbl 0803.68037
[28] Fogel, D.B.: Evolutionary Computation: Toward a New Philosophy of Machine Intelligence. IEEE Press, New York (1995) · Zbl 0926.68052
[29] Fogel, D.B., Simpson, P.K.: Evolving fuzzy clusters. In: Proc. IEEE Int. Conf. on Neural Networks, San Francisco, USA, pp. 1829–1834 (1993)
[30] Gath, I., Geva, A.B.: Unsupervised optimal fuzzy clustering. IEEE Trans. Pattern Anal. Mach. Intell. 11, 773–781 (1989) · Zbl 05111845
[31] Gustafson, D.E., Kessel, W.C.: Fuzzy clustering with a fuzzy covariance matrix. In: Proc. IEEE Conf. on Decision and Control, San Diego, USA, pp. 761–766 (1979) · Zbl 0448.62045
[32] Halkidi, M., Batistakis, Y., Vazirgiannis, M.: On clustering validation techniques. J. Intell. Inf. Syst. 17, 107–145 (2001) · Zbl 0998.68154
[33] Hall, L.O., Özyurt, B.: Scaling genetically guided fuzzy clustering. In: Proc. ISUMA-NAFIPS, Maryland, USA, pp. 328–332 (1995)
[34] Hall, L.O., Bezdek, J.C., Boggavarpu, S., Bensaid, A.: Genetic fuzzy clustering. In: Proc. NAFIPS, San Antonio, USA, pp. 411–415 (1994)
[35] Hall, L.O., Özyurt, I.B., Bezdek, J.C.: Clustering with a genetically optimized approach. IEEE Trans. Evol. Comput. 3(2), 103–112 (1999) · Zbl 05451964
[36] Hathaway, R.J., Bezdek, J.C.: NERF C-means: non-euclidean relational fuzzy clustering. Pattern Recognit. 27, 429–437 (1994)
[37] Hathaway, R.J., Bezdek, J.C.: Optimization of clustering criteria by reformulation. IEEE Trans. Fuzzy Syst. 3, 241–245 (1995)
[38] Hathaway, R.J., Bezdek, J.C.: Fuzzy C-means clustering of incomplete data. IEEE Trans. Syst. Man Cybern. Part B 31, 735–744 (2001)
[39] Hathaway, R.J., Devenport, J.W., Bezdek, J.C.: Relational dual of the C-means clustering algorithms. Pattern Recognit. 22, 205–212 (1989) · Zbl 0673.62050
[40] Hathaway, R.J., Bezdek, J.C., Hu, Y.: Generalized fuzzy C-means clustering strategies using L p norm distances. IEEE Trans. Fuzzy Syst. 8, 576–582 (2000)
[41] Höppner, F.: Speeding up fuzzy C-means: using a hierarchical data organization to control the precision of membership calculation. Fuzzy Sets Syst. 128, 365–376 (2002) · Zbl 0999.62045
[42] Höppner, F., Klawonn, F., Kruse, R., Runkler, T.: Fuzzy Cluster Analysis: Methods for Classification, Data Analysis and Image Recognition. Wiley, New York (1999) · Zbl 0944.65009
[43] Hruschka, E.R., Ebecken, N.F.F.: A genetic algorithm for cluster analysis. Intell. Data Anal. 7(1), 15–25 (2003)
[44] Hruschka, E.R., Campello, R.J.G.B., de Castro, L.N.: Evolutionary search for optimal fuzzy C-means clustering. In: Proc. Int. Conf. on Fuzzy Systems, Budapest, Hungary, pp. 685–690 (2004a)
[45] Hruschka, E.R., de Castro, L.N., Campello, R.J.G.B.: Evolutionary algorithms for clustering gene-expression data. In: Proc. IEEE Int. Conf. on Data Mining, Brighton, England, pp. 403–406 (2004b)
[46] Hruschka, E.R., Campello, R.J.G.B., de Castro, L.N.: Evolving clusters in gene-expression data. Inf. Sci. 176, 1898–1927 (2006) · Zbl 05061785
[47] Hruschka, E.R., de Castro, L.N., Campello, R.J.G.B.: Clustering gene-expression data: a hybrid approach that iterates between k-means and evolutionary search. In: Grosan, C., Abraham, A., e Ishibuchi, A. (eds.) Hybrid Evolutionary Algorithms, vol. 75, pp. 313–335. Springer (2007)
[48] Hung, M.-C., Yang, D.-L.: An efficient fuzzy C-means clustering algorithm. In: Proc. IEEE Int. Conf. on Data Mining (2001)
[49] Jain, A.K., Dubes, R.C.: Algorithms for Clustering Data. Prentice-Hall, Englewood Cliffs (1988) · Zbl 0665.62061
[50] Kamel, M.S., Selim, S.Z.: New algorithms for solving the fuzzy clustering problem. Pattern Recognit. 27, 421–428 (1994)
[51] Kaufman, L., Rousseeuw, P.J.: Finding Groups in Data–An Introduction to Cluster Analysis. Wiley Series in Probability and Mathematical Statistics (1990) · Zbl 1345.62009
[52] Kaymak, U., Setnes, M.: Fuzzy clustering with volume prototypes and adaptive cluster merging. IEEE Trans. Fuzzy Syst. 10, 705–712 (2002)
[53] Kersten, P.R.: Implementing the fuzzy C-medians clustering algorithm. In: Proc. IEEE Int. Conf. on Fuzzy Systems, Barcelona, Spain, pp. 957–962 (1997)
[54] Klawonn, F.: Fuzzy clustering with evolutionary algorithms. In: Proc. of 7th IFSA World Congress, Prague, Czech Republic, pp. 312–323 (1997)
[55] Kolen, J.F., Hutcheson, T.: Reducing the time complexity of the fuzzy C-means algorithm. IEEE Trans. Fuzzy Syst. 10, 263–267 (2002)
[56] Krishnapuram, R., Freg, C.-P.: Fitting an unknown number of lines and planes to image data through compatible cluster merging. Pattern Recognit. 25, 385–400 (1992)
[57] Krishnapuram, R., Keller, J.M.: A possibilistic approach to clustering. IEEE Trans. Fuzzy Syst. 1, 98–110 (1993)
[58] Krishnapuram, R., Keller, J.M.: The possibilistic C-means algorithm: insights and recommendations. IEEE Trans. Fuzzy Syst. 4, 385–393 (1996)
[59] Krishnapuram, R., Joshi, A., Yi, L.: A fuzzy relative of the k-medoids algorithm with application to web document and snippet clustering. In: Proc. IEEE Int. Conf. on Fuzzy Systems, Seoul, Korea, pp. 1281–1286 (1999)
[60] Liu, H., Li, J., Chapman, M.A.: Automated road extraction from satellite imagery using hybrid genetic algorithms and cluster analysis. J. Environ. Inf. 1(2), 40–47 (2003)
[61] Liu, J., Xie, W.: A genetics-based approach to fuzzy clustering. In: Proc. Int. Conf. on Fuzzy Systems, Yokohama, Japan, pp. 2233–2240 (1995)
[62] Maulik, U., Bandyopadhyay, S.: Fuzzy partitioning using real coded variable length genetic algorithm for pixel classification. IEEE Trans. Geosci. Remote Sens. 41(5), 1075–1081 (2003)
[63] Miyamoto, S., Augusta, Y.: Efficient algorithms for L p fuzzy C-means and their termination properties. Control Cybern. 25, 421–436 (1995) · Zbl 0852.62058
[64] Pakhira, M.K., Bandyopadhyay, S., Maulik, U.: A study of some fuzzy cluster validity indices, genetic clustering and application to pixel classification. Fuzzy Sets Syst. 155, 191–214 (2005) · Zbl 02209233
[65] Pal, N.R., Bezdek, J.C.: On cluster validity for the fuzzy C-means model. IEEE Trans. Fuzzy Syst. 3, 370–379 (1995)
[66] Pal, N.R., Bezdek, J.C.: Complexity reduction for ’large image’ processing. IEEE Trans. Syst. Man Cybern. Part B 32, 598–611 (2002)
[67] Pal, N.R., Pal, K., Bezdek, J.C.: A mixed C-means clustering model. In: Proc. IEEE Int. Conf. on Fuzzy Systems, Barcelona, Spain, pp. 11–21 (1997)
[68] Pal, N.R., Pal, K., Keller, J.M., Bezdek, J.C.: A possibilistic fuzzy C-means clustering algorithm. IEEE Trans. Fuzzy Syst. 13, 517–530 (2005) · Zbl 05452585
[69] Park, H.-S., Yoo, S.-H., Cho, S.-B.: Evolutionary fuzzy clustering algorithm with knowledge-based evaluation and applications for gene expression profiling. J. Comput. Theor. Nanosci. 2, 1–10 (2005)
[70] Rezaee, M.R., Lelieveldt, B.P.F., Reiber, J.H.C.: A new cluster validity index for the fuzzy c-mean. Pattern Recognit. Lett. 19, 237–246 (1998) · Zbl 0905.68127
[71] Ruspini, E.: Numerical methods for fuzzy clustering. Inf. Sci. 2, 319–350 (1970) · Zbl 0205.21301
[72] Timm, H., Borgelt, C., Döring, C., Kruse, R.: An extension to possibilistic fuzzy cluster analysis. Fuzzy Sets Syst. 147, 3–16 (2004) · Zbl 1068.68139
[73] Triola, M.F.: Elementary Statistics. Addison Wesley Longman (1999) · Zbl 0990.62500
[74] Van Le, T.: Evolutionary fuzzy clustering. In: Proc. IEEE Int. Conf. on Evolutionary Computation, Perth, Australia, pp. 753–758 (1995)
[75] Windham, M.P.: Cluster validity for fuzzy clustering algorithms. Fuzzy Sets Syst. 5, 177–185 (1981) · Zbl 0456.62053
[76] Xie, X.L., Beni, G.: A validity measure for fuzzy clustering. IEEE Trans. Pattern Anal. Mach. Intell. 13, 841–847 (1991) · Zbl 05112080
[77] Yuan, B., Klir, G.J., Swan-Stone, J.F.: Evolutionary fuzzy C-means clustering algorithm. In: Proc. Int. Conf. on Fuzzy Systems, Yokohama, Japan, pp. 2221–2226 (1995)
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.