ѧ
JOURNAL OF SOFTWARE
1999 6 10 Vol.10 No.6 1999



һȷ˻ľģ㷨о*
ġˡ֣γ
ժҪԴͳģ͵ȱ,ȷ˻һ־ģͼ㷨.ģͿ˾Ľ,ǰһЩģ.¶Ȳ,Ѿ⿴һϵͳ,ŽתΪģ¶ȱ仯ϵͳƽ̬.ͨһϵ¶ȱ仯ϵͳܺľֲСģϵͳƽ̬,մﵽϵͳĻ̬,Ž.
ؼʡȷ˻,,,ԭ.
ͼšTP18

Research of a Clustering Model and Algorithm by Use of Deterministic Annealing
YANG Guang-wen1WANG Ding-xing1ZHENG Wei-min1 LI Xiao-ming2
1 (Department of Computer Science and Technology Tsinghua University Beijing 100084)
2(Department of Computer Science Beijing University Beijing 100871) 
Abstract Aiming at the defects of traditional clustering model, a kind of clustering model and algorithm are put forward and researched by use of deterministic annealing. The model takes account of the interactions of clusters, some models which were put forward previously are special cases of this one. Temperature parameter is introduced, and the clustering problem as a physical system is considered. Finding the optimal solution to clustering problem is transformed into simulating the equilibrium state of a physical system. The equilibrium state is simulated by solving a series of problems to minimize the free energy which varies with temperature, and finally, the ground state of the system is attained. That is the optimal solution of clustering problem.
Key wordsDeterministic annealing, clustering, free energy, the principle of maximum entropy.
ǽݷҪ,㷺Ӧ๤̺Ϳѧ.ݵʽݷֳһЩۺ,ÿһۺеԪؾܵؾͬ.ڶݲκμ½зĹ.˹ܺģʽʶ,Ϊѧϰ,ǻѧϰ֪ʶȡҪ.
־෽ͨÿģʽı,ģʽ֯һЩۺ,ģʽ.־෽ʽΪ:nάģʽռNģʽX={x1,x2,...,xN},NģʽֳMģʽӼC1,C2,...,CM,ʹһۺеģʽ˴ʮ,һ,.־෽һ׼:ȫ׼ÿһۺΪһԪ,ÿһģʽ,ĳһۺĴԪƳ̶Ⱦһۺ;ֲ׼ݵľֲṹģʽ,,ͨģʽռеĸܶγɾۺ,һģʽڽɸģʽΪһۺ.׼ʱ,㷨ȷһַ,пܵģʽľ,ʹ׼ŵľ.
ķĲͬ.Ϣ,жԱLloyd㷨1ݣԺֶԸ÷ƹ㣬õGLA㷨2.ģʽʶ,ISODATA㷨3ԼFuzzyչһЩ㷨4,5.
ͳľģ,ǿɹΪ⼫С:
(1) 

Żȫŵy1,y2,...,yMΪ,ɽX.,ʽ(1)Ϊһ͹Ż,ĿǰûʮЧİ취ȫŽ.
ͳģ㷨ȱݣ6:(1) ԳʼΪ,Ϊѡʵľϰ;(2) Ŀǰľ㷨õľŵ;(3) ģģʽĽ;(4) ݰ,ͳķΪ;(5) ޷жġʵϷ.
оڶѧ,θľģͼ㷨,һҪ.
Ŀǰ,ϳһЩģȻĳֿ͹۹һЩϵͳ⡱㷨,Ȼ㡱(physical computation).G.C.Foxģ7.FoxĶǣȻѧ˼뷽䴫ͳӦ֮,ԭ˼뷽ıȡ,ڽе⡱.ȷ˻ѧԺK.Roseʿ1990ģ8,ǰȻһҪ֧7.ף9ϸȷ˻,õһЩȽ۽.
1 ȷ˻
˻Уϵͳÿһ¶´ﵽƽ̬Ĺ̶Ӧѭܼٶ,ϵͳ״̬Է仯ǳܼٵķ.ܴﵽСֵʱ,ϵͳﵽƽ̬.
ȷ˻,ǻ˼.⼫С,
min E=E(x). (2)

,xġɢĻϵ,E(x)ĳһϵͳ.ĿǰûʮЧķʽ(2).С(ʽ(2))һϵͳС״̬,ȹһܺF(x,T).Ϸ֪,ĳһ¶,ϵͳ״̬ı仯ǳܼٵķ,ϵͳﵽƽ̬ʱܺﵽС.ף9֤˵F(x,T)Ϊӳʱ,ȫּСxmin(T)ΪTӳ.T=ʱ,F(x,T)ȫŵ㼫,F(x,0)=E(x).ȷ˻,ÿһ¶T,ϵͳT=T+TʱܺС״̬xmin(T+T)Ϊʼ,ͨminF(x,T)ļСģϵͳﵽƽ̬Ĺ.TļС,F(x,T)ȫּС㲻ϱ仯,Tı仯TСʱ,Ϊxmin(T)λxmin(T+T)ڵľֲС,¶T,xmin(T+T)ΪʼF(x,T)ļСֵ.TСٶȺʱ,ΪlimT0xmin(T)Ϊʽ2ȫּС.
2 ģ͵һʽ
ڸy1,y2,...,yM,ji{1,2,...,M},xiCjiݱʾxiCjiһ¼,ĸΪp(yj1,yj2,...,yjN)=p(x1Cj1,x2Cj2,...,xnCjn.Ϊy1,y2,...,yMp(yj1,yj2,...,yjN)(ji=1,2,...,M,i=1,2,...,),ʹ
(3)

С.D(yj1,yj2,...,yjN)Ϊĳһ֪,ǵxiCji(i)ʱʧ.
D(yj1,yj2,...,yjN)ʽɸʵʱѡȡ,ΪһĳЩԵһ㺯.ȡD(yj1,yj2,...,yjN)=d(yj1,yj2,...,yjN)TAd(yj1,yj2,...,yjN),ʽAΪyj1,yj2,...,yjNһNNd(yj1,yj2,...,yjN)ΪNά,ȡd(yj1,yj2,...,yjN)=(d(x1,yji),d(x2,yj2),...,d(xN,yjN))T.Aѡȡ,԰xе㡢༰֮һЩ.رǣȡA=aijNN,.d(xk,yjk),ʽΪxiCjݣi=1,2,...,N,j=1,2,...,Mʱʧ,ʽаһЩ.
ȡaij=0(ij),ʱУxiCj໥,aii(i=1,2,...,N)Ĳͬ,ʾxиҪ̶Ȳһһaii0).ʱ.ڸxiCj໥,,

һaii=1(i),ʱʽ(3)ľģͼΪף8ᵽ.

ʽ(3)ģͼΪʽ(1)ģ,۵һģͼΪͳľģ., ʽ(3)ľģ;зḻں,һЩ,ͳһЩģͿΪģ͵.
ģеp(yj1,yj2,...,yjN),û֪ʶ,ʲ ȷʽ,ͳļԭȷģеĸʷֲp(yj1,yj2,...,yjN).
ڹ̶yj1,yj2,...,yjM,غֱΪ

üԭ,ͨ
(4)

ɵõ
(5)

Цʽ4ȷ,һ¶ȳȵĲ.
3 ܺȷ
Y={y1,y2,...,yM}J={j1,j2,...,jN},ʽ(5)õp(yj1,yj2,...,yjN),ǰһĲԿɵõһн.{Y,J}Ϊһʵ.¶T,⿴һϵͳ,ϵͳȡʵ{Y,J}ĸΪP(Y,J).
ϵͳغֱΪ
(6)
(7)

ÿһ̶¶T,üԭ,ʹHȡĸʷֲP(Y,J)Ϊϵͳƽ̬,ʹP(Y,J)ȡʵ{Y,J}Ϊϵͳɼʵ.ʽ(6)Լ,üԭɵ
(8)

Цʽ(6)ȷ.ʵ,.ʽ(8)ȷP(Y,J)Ϊ¶Tʱϵͳƽ̬.
ھӦϵͳ,ƽ̬ʽ8.Եֲ







Ӷ
(9)

ʽ(9)ȷĺΪӦϵͳܺ,һ
(10)

ʽ10֪,ʹP(Y)y1,y2,...,yMӦʹF(y1,y2,...,yM,)ȡС.ʹʷֲy1,y2,...,yMΪϵͳ¶TʱɼṹУ.,ǿͨܺF(y1,y2,...,yM,)ļСþϵͳĽ.
4 㷨
ʽ(9)ľϵͳܺF(y1,y2,...,yM,),Ƶ

һٶD(z1,z2,...,zN)z1,z2,...,zNΪ͹,F(y1,y2,...,yM,0)Ϊy1,y2,...,yM͹,ɴͳŻܺļС.һ,
(11)

,ܺȷ˻Ҫ,ͨһϵ¶TӦڦ£仯ܺļС.
㷨:
(1) ȡ0=0,k=0,min F(y1,y2,...,yM,k),ŽΪ;
(2) (k+1)=u(k)(uΪ),Ϊʼmin F(y1,y2,...,yM,k+1),ŽΪ;
(3) ж׼Ƿ,,Ϊžģת(5);,ת(4);
(4) k=k+1,ת(2);
(5) ļk+1,ʽ8ʷֲp(yj1,yj2,...,yjN),ݴ˽x,,.
м˵:
(1) 㷨,׼ǵ,һȶʱ,㷨ֹ;
(2) Mѡȡ,һֻҪʹM㹻ٴʵĿ.MԽ,Խ,Խ;
(3) õ,ͬĿܴͬһ,ݲͬľ⼰㷨ֳȷʵĿԼͬһӦĲͬԪ;
(4)㷨ĵ5{x1Cj1,x2Cj2,...,xnCjn}ĸ,Ҫһÿһxiһ,һ.
5 
ڸxiCj໥ȡ,ǽ˴ģʵ.ڶάռ,ɲͬ״ͬܶȵȸָݼ,ñĵľ㷨˴,õ˽ϺõĽ.ڲȵľ塢Բɷֺŵľ,ȡM㹻ͬһвͬĴԪʱ,ɵõȷĽ.رǶɵĶֲ̬Ȼľ,,ʹͳľ෽Ըֲ̬Ϊʼ,ĺֵҲñķõպֵҪ.ף6ݵĹ,෽ʵԺǿ,رڴģݴ.
Ķģʽʶй㷺Ӧõľ,һһģ.ģͿģʽģʽģʽࡢ֮Ľ.һЩͳľģͿΪĵ.¶Ȳ,⿴һϵͳ,ͨģϵͳƽ̬õĽ.ʹȡļһ,ɴͳ㷨ΪһЩ.
߼顡,1963,ʿ,,ҪоΪм, .
,1937,,ʿʦ,ҪоΪ/ .
֣γ,1946,,ʿʦ,ҪоΪ/ֲ .
,1957,ʿ,,ʿʦ,ҪоΪ/ .
ͨѶϵ:, 100084,廪ѧѧ뼼ϵ
ߵλġˡ֣γ(廪ѧѧ뼼ϵ  100084)
(ѧѧϵ  100871)
ο
1Lloyd S P. Least squares quantization in PCM. IEEE Transactions on Information Theory, 1982,28(1):129137
2Lind Y, Buzo A, Gray R M. Algorithm for vector quantization. IEEE Transactions on Communication, 1980,28(1):8495
3 Ball G, Hall D. A clustering technique for summarizing multivariate data. Behavioral Science, 1967,12:153155,
4Bezdek J C. Pattern Recognition with Fuzzy Objective Function Algorithms. New York: Penum, 1981
5Gath I, Geva A B. Unsupervised optimal fuzzy clustering. IEEE Transactions on Pattern and Machine Intelligent, 1989,11(7):773781
6Wong Yui-fai. Clustering data by melting. Neural Computation, 1993,5(1):89104
7Fox G C. Physical computation. Concurrency: Practice and Experience, 1991,3(6):627653
8Rose K, Gurewitz E, Fox G C. Statistical mechanics and phase transition in clustering. Physical Review Letters, 1990,65:945948
9,.ȷ˻.ѧ,1998,21(8):765768
(Yang Guang-wen, Li Xiao-ming, Wang Yi-he. Deterministic annealing. Chinese Journal of Computers, 1998,21(8):765768)
1998-04-21յԭ,1998-07-02յ޸ĸ
