A Survey Of Fuzzy Clustering - Old Dominion University

A Survey of Fuzzy Clustering5with U E Mfcn and a (al,. . . , a,) E (W”)” called the cluster centers. Bezdek [7] generalizedJD(U, a) to JFCM (U, a) withfor which m E (1, co) represents the degree of fuzziness. The necessary conditions for a minimizer(U’, a*) ofJFCM( ,a)areThe iterative algorithms for computing minimizers of Jpc (tY, 3) with these necessary conditionsare called the fuzzy c-means (FCM) clustering algorithms. These FCM clustering proceduresdefined by Dunn [9] and generalized by Bezdek [7] have been widely studied and applied in avariety of substantive areas. There are so many papers in the literature that concern themselveswith some aspects of the theory and applications of FCM. We give some references by the followingcategories. Interested readers may refer some of these:(4 Numerical Theorems 126-37)(b) Stochastic Theorems [34,38-411Cc)Methodologies [9,37,42-511(4 Applications(1)(2)(3)(4)Image Processing [45,52-581Engineering Systems [59-631Parameter estimation [38,64-681Others [69-74).Here we are interested in describing a variety of generalizations of FCM. These include sixgeneralizations and two variations.(A) GENERALIZATION1To add the effect of different cluster shapes, Gustafson and Kessel [47] generalized the FCMobjective function with fuzzy covariance matrices, wherej lwithU E Mfcn,a (al,. . . ,a,)i lE (R”)” and A (Al,. . . ,A,)definite s x s matrices with det(Ai) pi being fixed and ]]zj - ail]‘,for which Ai are positive (zj - oi)T Ai (zj - ai).The iterative algorithms use necessary conditions for a minimizer (U,‘a, A) of JFCM (U, a, A) asfollows:ai Pij Ai (pi det(Si))““SZ:i,where Si Cj” , jog (zj - ui) (zj - ai)‘.i l,.,c,j l,.,n.

M.-S.6YANG(B) GENERALIZATION 2JFCM (U, a) is well used to cluster the data set which has the hyper-sphericalshapes. Gustafsonand Kessel [4’7]generalized it to JFCM,, (U, 3, A) for improving the ability to detect different clustershapes (especially in different hyper-ellipsoidalshapes) in the given data set. Another attemptto improve the ability of JFCM(U, a) to detect nonhyper-ellipsoidallyshaped substructureswasproposed by Bezdek et al. [42,43], called the fuzzy c-varieties (FCV) clustering algorithms.Let us denotespannedthe linearvarietyof dimensionr(0 2 T s) in W throughthe pointa and{br, . . . , b,} byby the vectorsb,) Vr(%bl,.,yEW,y a &,&ElR.k l11If r 0, Vo {u} is a point in W; if T 1, VI L(a; b) {y E IIg’ 1y a tb, t E R} is a linein W; if T 2, Vz is a plane in W; if r 3, V, is a hyperplanein W; and V, W8. In general,the orthogonaldistance (in the A-norm on Ws for which A is a positive definite s x s matrix)from z E RS to V,, where the {bi} is an orthonormalbasis for VT, is112llX-ul 2,- ((x-a,bk)A)2DA(x,Vr) {d (x,y)} 7k lwhere (z, y)A xTAy,dA(Z,g) /Ix-Y\lA l]x]]: (&x)Aand(( - )* y))“ .functionand bk (blk,. . . , b&), k 1,. . , , T. Consider the objectiveerrors between theJFCV( ,a, by , . . . , b,) which is the total weighted sum of square orthogonallinear varieties, wheredata set X ( 1,. . . , xn} and c r-dimensionalLet a (al,., a,)JFCV(u, a, blb,) ,.)withf--j lr;Dfi,j l i rD, DA(“j , v,i) ,yE ‘]y oi tkb&,tkEll%j l,.k lThe FCV clusteringJFCV &Sfollows:algorithmsm Eare iterationswhere sik is the kth unit eigenvectorl,.,C,i Tthroughthe necessaryof the fuzzy scattermatrix,n,conditionsSi with71Si Al”c(correspondingto its k th largest2Pijp;(q- ai) (xj - ai)TA”2j leigenvalue,(Dij)2/ 1)andi l,.,c,j k i (Dkj)2’(m-1)l,.,n,k l,.,r.and[l, oo).andfor minimizersof

A Surveyof Fuzzy Clustering7(C) GENERALIZATION3Consider any probability distribution function G on W”. Let X (21,. . . , z,}be a randomsample of six n from G and let G, be the empirical distribution which puts mass l/n at eachand every point in the sample { 21, . . . , z,}. Then the FCM clustering procedures are to choosefuzzy c-partitions 1 ( 1,. . . , pc) and cluster center a to minimize the objective function GFCM('&, ) dh)Let us replace G, by G. Then we generalized the FCM with respect to G by the minimizationof JGFCM(G,cl,a),JGFCM(G,P, ) 2s ,zmb -ai(12G&).i lConsider a particular fuzzy c-partition of a in (lR”)c of the formIlz2dz,a) ij r 115-ui(121(m-l) -lflj1//2’(m-1)i l,.,c.’Define (a) (/JI(z, a), . . . , pc(z, 3)) and define that&(G,a) JGFCM(G,CL(;L), )Then, for any fuzzy c-partition p (PI(Z), . . . , p,.(z)) and a E (R ) ,JGFCA&,P( L), )5 GFCM(G,I ,; ).The reason for the last inequality is thatwhich can be seen from the simple fact thatci l for pk 0, Yk 0, k 1,. . . , C, plgradient of the Lagrangianc yyJ4j l l/Cm-l)Yj*.-772)Yi I 2PT Yii l p, 1. To claim the simple fact, we may take theand also check that the Hessian matrix of h with respect to pl, . . . ,p, will be positive definite.

M.-S.8YANGLet (/A*,a’) be a minimizer of JGFCM(G, p, a) and let b* be a minimizerJGFCM(G,p*,a*) LJGFCMof L,(G,a). Then,(G (h*),b*) L, (G,b*)I Lx (G,a*)JGFCM(G,p(a*),a*) JGFCM(G,P*, *).Thatis, JGFCM (G,p*, a*) L, (G,h*).problemTherefore,we have thatof JGFCM (G, p, a) over p and 3 is equivalentto solvingsolvingthe minimizationthe minimizationproblemof L, (G, a) over a with the specified fuzzy c-partitions (a). Based on this reduced objectivefunction L, (G, a), Yang et aZ. [39-411 created the existence and stochastic convergence propertiesThey derived the iterative algorithmsfor computingtheof the FCM clusteringprocedures.minimizerof L, (G, a) as follows:Set h (arc,. . , a,e).For k 2 1, let ak (ark,. . . , a&), where for i 1,. . . , c,with respect to anyThey extended FCM algorithmswith respect to G, to FCM algorithmsprobabilitydistributionfunction G, and also showed that the optimal cluster centers should bethe fixed points of these generalized FCM algorithms.The numerical convergence properties ofthese generalized FCM algorithms had been created in [36]. These include the global convergence,the local convergence,and its rate of convergence.(D) GENERALIZATION 4Boundarydetection is an importantstep in pattern recognitionand image processing.Thereare various methods for detecting line boundaries;see [75]. When the boundariesare curved,the detection becomes more complicatedand difficult. In this case, the Hough transform(HT)(see [76,77]) is th e only major technique available. Although the HT is a powerful technique fordetecting curve boundarieslike circles and ellipses, it requires large computer storage and highcomputingtime. The fuzzy c-shells (FCS) clustering algorithms,proposed by Dave [45,46], arefine new techniques for detecting curve boundaries,especially circular and elliptical.These FCSalgorithmshave major advantagesover the HT in the areas of computer storage requirementsand computationalrequirements.The FCS clusteringalgorithmsare used to choose a fuzzy c-partitionp ( 1,. . . , pc) andcluster centers a (al,. . . ,a,) and radius T ( 1,. . . , rc) to minimize the objective functionJFCS (p, a, T), which is the weighted sum of squared distance of data from a hyper-ellipsoidalshell prototypeJFCS(P,W) &?(lj)(11%-a&,-ri)2j li lamongall a E (IV)‘,/.LE W, and T E (lR )c with m E [l, co).The necessaryconditionsfor a

A Surveyof FuzzyClusteringminimizer( ,a*, r*) of JFCS are the followingequationssatisfiedfor a* and r*:1-withpf(zj)The FCS clustering(see [45,53]) appliedtigatedits numerical algorithmsare iterationsthrough thesethese FCS’s in digital image sary conditions.Dave et al.Bezdek and Hathaway[78] inveset al. [79) gave a new approachtothe FCS.(E) GENERALIZATION 5Trauwaertet al. [51] derived a generalizationof the FCM based on the maximumlikelihoodprinciple for the c members of mutivariatenormal distributions.Consider a log likelihood functionnormalsJFML (p, a, IV) of a random sample X {XI,. . . , 5%) from c numbers of mutivariateN(ai,Wi),i 1,. . . ,c, wherein which ml, m2, ma E [l, 00). To derive iterative algorithms for a maximizerthey further limited to the case where ml, m2, and ms are either 1 or 2.only the case of ml 2 and m2 m3 1 appeared as an acceptable basisrecognitionalgorithm.In the case of ml 2 and m2 ms 1, Trauwaertiterative algorithm as follows:’Bij (xj -.i)TW;l(xj -ai),Aij i In ]Wi],of JFML (p, a, IV),They claimed thatfor a membershipet al. [51] gave thewherei l,**.,c,j l,.,n.This general algorithmis called “fuzzy product” since it is an optimizationof the productfuzzy determinants.In the case of Ai I for all i the algorithm becomes the FCM.(F)ofGENERALIZATION 6Mixtures of distributionshave been used extensively as models in a wide variety of importantpractical situations where data can be viewed as arising from two or more subpopulationsmixed invaried proportions.Classificationmaximum likelihood (CML) procedure is a remarkable mixturemaximum likelihood approach to clustering, see [80]. Let the population of interest be known or beassumed to consist of c different subpopulations,or classes, where the density of an observationxfrom class i is fi(x; e), i 1,. . , , c for some parameter6. Let the proportionof individualsin

M.-S. YANG10the population which are from class i be denoted by oi with cri E (0,l) and x: ,1 oi 1. Letx (51,. . . , z,} be a random sample of size n from the population. The CML procedure is theoptimization problem by choosing a hard c-partition Jo* and a proportion cy* and an estimate 6’*to maximize the log likelihood I31 (CL,(Y,0) of X, whereB1(p,a,e) eC(xj;e)c71. lnwfiCCpi(q)lnaifij l(xj;e),k lin which ,Q(z) E (0,1) and pi( ) . (2) 1 for all 2 E X. Yang [37] gave a new type ofobjective function Bm , (11,Q, 0), where 1 for all z E X with the fixed constantsin which pi(z) E [0, l] and pi(z) . . . &x)m E [l,co) and w 2 0. Thus, B,,, (/J, a, e), called the fuzzy CML objective function, is a fuzzyextension of Bi (cl, (Y,0). Based on B,,, (P, (Y,e), we can derive a variety of hard and fuzzyclustering algorithms.Now we consider the fuzzy CML objective function B,,, (p, Q, 0) with the multivariate normalsubpopulation densities N (ai, Wi), i 1,. . . , c. Then, we have thatBased on B m,ul(p, a, IV), we extend the fuzzy clustering algorithms of Trauwaert et al. [51] to amore general setting by adding a penalty termw C,“ , xi , pyn(zj) In oi . The construction()of these penalized types of fuzzy clustering algorithms is similar to that of [51]. In the specialcaseofWi I,i l,.,c.Wehavethat JFCM( a) -W2 2 Py(Xj) In%.j li lSince JPFCM just adds the penalty term (-w &xk,,LL; (zj) In ai)to JFCM,JPFCMiscalled the penalized FCM objective function. We get the following necessary conditions for a

A Survey of Fuzzy Clustering11minimizer (p, a, a) of JPFCM:aj CYi )Pi(q) Thus, the penalized FCM clustering algorithms for computing the minimizer of JPFCM (p, a, CX)are iterations through these necessary conditions. By comparison between the penalized FCMand the FCM, the difference is the penalty term. This penalized FCM has been used in parameterestimation of the normal mixtures. The numerical comparison between the penalized FCM andEM algorithms for parameter estimation of the normal mixtures has been studied in [68].(G) OTHER VARIATIONSFrom (A) to (F), we give a survey of six generalizations of the FCM. These generalizations areall based on the Euclidean norm )I . )I ( i.e., Lz-norm ). In fact, we can extend these to L,-normJFCM, (uya) 22CL;&where dij (chsl(xjk - aik I”) “’ is the L,-norm of (zj - ai). When p 2 it is just the FCM.In Mathematics and its applications, there are two extreme L,-norms most concerned. These areLr-norm and L,-norm.Thus,with dij f:JFCM (U, ,) ce I;"dijj l i lnJFCM,(Vand(Sjk - a&[k lcwith dij kzy8) CCpc dijj 1 i ls ) sjk I 1aik 1.We cannot find the necessary conditions to guide numerical solutions of these nonlinear constrained objective functions JFCM and JFCM,.Bobrowski and Bezdek [44] gave a method tofind approximate minimizers of JFCM and JFCM, by using a basis exchange algorithm usedfor discriminate analysis with the perception criterion function by Bobrowski and Niemiro [Bl].Jajuga [49] also gave a method to find approximate minimizers of JFCM based on a method forregression analysis with the Li-norm by Bloomfield and Steiger 1821. Jajuga [49] gave anothersimple method to find approximate minimizers of J FCM, which we shall describe next.Recall thatJFCM W, with dij 2 2k ;dijj l i l)zjcjk -f&k).k lThen U may be a minimizer of JFCM for a being fixed only if2(dij)l -‘)k l(dkj) “(“ ‘)Pij For U being fixed, let wij ,zjkPfaik,.Then,cJFCM (w, a ci lMm 16:11-Bsck l2j l“ij(zjk -aik)‘.

M.-S. YANG12The aik may be a minimizerof JFCM (w, a) for WQ being fixed only ifaii c,“ l wiixikC&iJajuga[49] suggestedfollowingan algorithmfor findingl,.,c,k l;.approximate,s.minimizersof JFCM basedon thesteps:wij lXika,k z2Pij’“iji Pg- aikl’C,“ I“iixikEYE” ,wi.j’andi l,*.,c,(&)1-l)dij k r (dkj) llCna-l)4. FUZZYGENERALIn the conventionalnearest neighborpatternsand 0 representsthe labeling iZjk--aailc1,wherek-NEARESTj l,.,n,k l,.,s.k lNEIGHBORRULEpattern classificationproblem, X representsthe set ofvariable of c categories.We assume that a set of ncorrectly classified samples (ICI, &), (x2,6 ) , . . . , (x,, 19,) is given and follows some distributionF(z, Q), where the 5:s take values in a metric space (X,d) and the 0:s take values in the setis given, where only the measurement 0 is observableby{1,2 ,., c}. A new pair (Q,&)the statistician,and it is desired to estimate BO by utilizing the informationcontainedin theset of correctly classified points.We shall call Z; E {xl, 2,. . . ,z,} a nearest neighbor to zif d(zL,z) mind,2 ,,., n d(xi, x). The nearest neighbor rule (NNR) has been a well-knowndecision rule and perhaps the simplest nonparametricdecision rule. The NNR, first proposed byFix and Hodges [83], assigns x to the category 0; of its nearest neighbor &.Cover and Hart [84] proved that the large sample NN risk R is bounded above by twice the Bayesprobabilityof error R* under the 0- 1 loss function L, where L counts an error whenever a mistakein classificationis made. Cover [85] extended the finite-action(classification)problem of Coverand Hart [84] to the infinite-action(estimation)problem. He proved that the NN risk R is stillbounded above by twice the Bayes risk for both metric and squared-errorloss function.Moreover,Wagner [86] considered the posterior probabilityof error L, P [e; # eo ) (21, el), . . . , (xn, On)].Here L, is a random variable that is a function of the observed samples and, furthermore,0 and he proved that under some conditions, L, converges to R with probabilityEL, P[ :,# ],one as n tends to co. This obviously extended the results of Cover and Hart [84]. There are soThe k-NNR is a supervisedapproach to patternmany papers about k-NNR in the literature.recognition.Althoughk-NNR is not a clusteringalgorithm,it is always used to cluster anunlabelleddata set through the rule. In fact, Wong and Lane [87] combined clusteringwithk-NNR and developed the so-called k-NN clustering procedure.In 1982, Duin [88] first proposed strategies and examples in the use of continuouslabelingvariable.Joiwik [89] derived a fuzzy k-NNR in use of Duin’s idea and fuzzy sets. Bezdek etal. (901 generalizedk-NNR in conjunctionwith the FCM clustering.Keller et al. [91] proposedfuzzy k-NNR which assigns class membership to a sample vector rather than assigning the vectorto a particularclass. Moreover, BQreau and Dubuisson[92] gave a fuzzy extended k-NNR byBut in a sequence of study in the fuzzychoosing a particularexponentialweight function.version of k-NNR, there is no result about convergence properties.Recently, Yang and Chen [93]described a fuzzy generalized k-NN algorithm which is a unified approach to a variety of fuzzy

A Survey of Fuzzy Clusteringk-NNR’sthatand thenis, the strongcreatedthe stochasticconsistencyconvergenceof posteriorand Chen [94] gave its rate of convergence.[84], Cover [85], and Wagnerof the fuzzy generalizedrisk of the fuzzy generalizedNNR.Moreover,They showed that the rate of convergencerisk of the fuzzy generalized NNR is exponentiallycase of the fuzzy generalized Ic-NNR, the strongand Hartproperty13NNR,Yangof posteriorfast. Since the conventionalIc-NNR is a specialconsistencyin [93] extends the results of Cover[86].The fuzzy generalized Ic-NNR had been shown that it could improve the performancerate inmost instances.A lot of researchers gave numerical examples and their applications.The resultsin [93,94] just give us the theoretic foundation of the fuzzy generalized Ic-NNR. These also confirmthe value of their applications.5. CONCLUSIONSWe have already reviewed numerous fuzzy clustering algorithms.But it is necessary to preIn general, the number c should beassume the number c of clusters for all these algorithms.unknown.Therefore, the method to find optimal c is very important.This kind of problem isusually called cluster validity.If we use the objective function JFCM (or JFCV, JFC,S, etc.) as a criterion for cluster validity,it is clear that JFCM must decrease monotonicallywith c increasing.So, in some sense, if thesample of size n is really grouped into E compact, well-separatedclusters, one would expect tosee JFCM decrease rapidly until c 6, but it shall decrease much more slowly thereafter until itreaches zero at c n. This argument has been advanced for hierarchicalclustering procedures.But it is not suitable for clustering procedures based on the objective function.An effectivelyformal way to proceed is to devise some validity criteria such as a cluster separation measure or touse other techniques such as bootstrap technique.We do not give a survey here. But interestedreaders may be directed towards references [95-1031.Finally, we conclude that the fuzzy clusteringalgorithmshave obtainedgreat success in avariety of substantiveareas.Our survey may give a good extensive view of researcherswhohave concerns with applicationsin cluster analysis, or even encourage readers in the appliedmathematicscommunityto try to use these techniques of fuzzy clustering.REFERENCES1. R.O. Duda and P.E. Hart, Pattern Classification and Scene Analysis, Wiley, New York, (1973).2. P.A. Devijver and J. Kitttler, Pattern Recognition: A Statistical Approach, Prentice-Hall, Englewood Cliffs,NJ, (1982).3. A.K. Jain and R.

methods based on the fuzzy relation. These can be found in (10,12-161. Fuzzy clustering, based on fuzzy relations, was first proposed by Tamura et al. [12]. They proposed an N-step procedure by using the composition of fuzzy relations beginning with a reflexive and symmetric fuzzy relation R in X. They showed that there is an n such that