о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 8 Vol.36 No.8 1999



GLCA㷨Է
𨡡šҦ˳
ժҪģ㷨ܹͨĿ꺯׼ȷùʽ׼򣬴ӶϺõؽ.GLCA㷨дԵģ㷨FCMȽصǣҪѡȨָѸܶ䵽ģ.ĶGLCA㷨Է֤GLCA㷨ĲԣͬʱGLCA㷨.
ؼʡGLCA㷨 ԣ Ŀ꺯
ͼšTP391
CONVERGENCE ANALYSIS OF THE G CLUSTERING ALGORITHM
LI Jing-Jiao, ZHANG Li, and YAO Tian-Shun
(School of Information Science and Engineering, Northeastern University, Shenyang 110006)
AbstractThe clustering methods can exactly describe clustering criterion with formulations by the objective function. The classification problem can be better solved. In comparison with the representative fuzzy C-means (FCM) algorithm, the advantage of the g clustering algorithm (GLCA) is that the selection of weighting exponent is not required and it extends the probability density to the fuzzy measure. In the paper here the convergence analysis of the g clustering algorithm is conducted, the divergence of the g clustering algorithm is proved, and the non-convergent example is presented.
Key wordsGLCA algorithm, convergence, objective function
ڸ־,Ŀ꺯ܹ׼ȷùʽ׼,ӦģۿʹһЩõϺĽ.ˣѧߴģ㷨о1,2,одԵ㷨BezdekFCM3ݾ㷨.ģ㷨ܹϺõؽ⣬ͼʶʸʶ4ݵȷõӦ.
ɲѧ Leszczynski5 ڡFuzzy Sets and SystemsGLCA㷨(the g clustering algorithm(GLCA)) ʹSugenog˲ȵʽо㷨BezdekFCM㷨ȽϣGLCA㷨ŵǣҪѡȨָѸܶ䵽ģ.
ʹGLCA㷨һЩоʱGLCA㷨в.˱Ĵ֤GLCA㷨Ĳԣ˲.ȼ򵥵ؽһGLCA㷨.
1GLCA㷨
LeszczynskiSugenog˲ȵģ.
1. GLCA㷨Ŀ꺯.

G={gij}ģܶȾnkǾĸdijǴxjiĵľ룬gijxjԵiĵ̶ȣ

ΪJ(GV)СֵLagrangianӼ{j}, LagrangianΪ

ʽ(3)ͣǵõ



ʽ(2)ʽ(5)ԵõjԼ

GLCA㷨£
 ÿxjĳʼֵG=gijĳʼֵֵe;
 ʽ(4)vi
 ʽ(6)ڦj
 ʽ(5)G
 ôL=L+1תڣxj,xjڵi.
2GLCA㷨Է
Ϊ֤GLCA㷨Bezdek֤FCM㷨6ķ(zangwill7)֤GLCA㷨.
GLCA㷨ģôGLCA㷨Ӧzangwill3zangwillһJ(GV)½J(GV)½Ӧó.
⣺GLCA㷨ôڸVL(G)=J(G,V),ҽʽ(5)LϸֲС.
GLCA㷨ô⽫Ҳ.
֤. ΪȥʽԼ0gij1
gij0gij1
ǿдLagrangian

LļС㣬0ô
Ҳ
(1) 
(2)(1)(2)ɵ
(3) 
ͬ˲ʽ(3)ɵ
(4) 
ȥlʹʽ(3)ɵ
(5) 
(4)ɵ
(6)
(5)(6)õ
Gʽ(5)ıҪ.
Ϊ֤ԣҪڴLĵHessianҲ


ˣLڴHessianʵԳƾ.

H()ʽǣ

Ҳ
˾H()G󣬲LϸֲС㣬ⲻ.
GLCA㷨GLCA㷨.
3ʵ


ͼ1FCM㷨ľ
ǸһGLCA㷨ʵΪͼ1ʾݷֱFCM㷨GLCA㷨оFCM㷨Ȩָm=2ֵe=0.0005GLCA㷨ֵe=0.0005).
㷨УĳʼֵV0ͬ.k=3ʱ1ʾʱ㷨ĽͬĿ꺯½.k=8ʱ2ʾFCM㷨Ŀ꺯½ģͼ1ʾGLCA㷨ĲʹóʼֵԽӰܴ󣬵ĳʼֵV0ȽϽӽսVʱGLCA㷨ܹóĿ꺯ǵݼģĳʼֵV0ʱĿ꺯ǵݼģҲ޷õȷĽ.
1Ŀ꺯J;V

FCM㷨GLCA㷨
Ŀ꺯JeĿ꺯Je
01505.34***1998.38***
1762.5190.97417606.2042.29654
2661.2040.15323598.0402.74E-02
3657.9174.99E-03598.6796.11E-04
4657.7931.88E-04589.8863.50E-04



ʼ V(0)FCM㷨GLCA㷨
V1iV2iV1iV2iV1iV2i
833.4054.7463.3494.232
18426.4863.64625.5553.306
141216.91416.55815.90616.243


2Ŀ꺯J;V

FCM㷨GLCA㷨
Ŀ꺯JeĿ꺯Je
0240.44***4.823***
1151.7170.584824.8110.806
296.4760.572615.2390.628
391.6845.23E-03183.8690.917
491.3683.46E-03567.3320.676
591.3393.12E-042026.720.720
6******507.0972.997
71560.110.675
8620.2351.515
91590.9970.6102



ʼ V(0)FCM㷨GLCA㷨
V1iV2iV1iV2iV1iV2i
241.4430.9853.8292.984
261.0347.98123.1422.062
446.5525.46523.6031.898
21221.0842.34521.9382.281
24227.1031.15921.7422.299
20428.9917.24923.2831.887
141611.57917.7824.1151.884
161620.06716.0922.2622.235


⣬ͨGLCA㷨һЩоǷֵkȡֵСʱk=2,3ܹõȷĽkֵϴʱk=6,7,8,һ㲻ܵõ.
ӱ2ĽǿGLCA㷨ܵõȷĿ꺯ҲͨӣҲ˵GLCA㷨ǲ. 
Ŀ:õȻѧ(Ŀ6968300469675019)
߼:𨣬Ů19643ڣʿоΪʶ˹ܡ˻ӿ.Ů19615ڣʿооΪʶ𡢼ѧ.Ҧ˳У19345ڣʿʦоΪ˹ܡѧ˻ӿ.
ߵλ𨡡šҦ˳ѧϢѧ빤ѧԺ110006
ο
1Hathaway J R et al. Relation duals of the c-means clustering algorithms. Pattern Recognition, 1989, 22(2):205212
2Bezdek J C et al. Numerical comparison of the RFCM and AP algorithms for clustering relational data. Pattern Recognition, 1991, 24(8):783791
3Bezdek J C. FCM: The fuzzy c-means clustering algorithm. Computers & Geosciences, 1984, 10(2):191203
4СԵ.ڷֶģC-ֵܶHMMʶģͲ. ѧѧ1997, 22(6): 550554
(Ma Xiaohui et al. The segmental fuzzy c-means algorithm for estimating parameters of continuous density hidden Markov models. ACTA Acustica (in Chinese), 1997, 22(6): 550554)
5Leszczynski K. Sugeno's fuzzy measure and clustering. Fuzzy Sets and Systems, 1985,15(1):147158
6Bezdek J C. A convergence theorem for the fuzzy ISODATA clustering algorithm. IEEE Trans on PAMI, 1980,2(1): 18
7Zangwill W. Nonlinear Programming, A Unified Approach. Englewood Cliffs, NJ: Prentice-Hall,1969
յڣ1997-11-19
޸ڣ1998-03-23
