圖論在聚類分析中的應(yīng)用.pdf

1、該文討論聚類分析中的系統(tǒng)聚類法、模糊聚類法和灰色聚類法,著重探討其聚類的圖論方法.第一章介紹聚類分析的基本知識.第二章討論系統(tǒng)聚類分析及其中著名的最短距離法,指出了最短距離法即為圖論中求賦權(quán)連通圖最小支撐樹Kruskal算法的變形,得到了最短距離法的優(yōu)良性質(zhì):定理2.1 max{s(p′<,k+1>):p′<,k+1>∈ <,k+1>}=s(P<,k+1>)=M<,mst>(C<,s> ∪ C<,t>)=M<,mst>(P<,k>)=m

2、in{M<,mst>(P′<,k>):P′<,k>∈( )<,k>}對最短距離法和k=n-1,n-2,…,1成立.它說明最短距離法得到的系統(tǒng)H=(P<,n>,P<,n-1>…,P<,1>)對每個m=n-1,n-2,…2,P<,m>既是分離性最好的m-剖分,又是相似性最好的m-剖分.第三章討論模糊聚類分析及其常用的傳遞閉包法,指出這種聚類方法的復(fù)雜性,定義了模糊關(guān)系圖G=(X,E,R)及其中兩點u,v間的連通強度S(u,v),證明了S是X

3、上的模糊等價關(guān)系、G=(X,E,R)的最大支撐樹具有如下性質(zhì):定理3.2設(shè)T是模糊關(guān)系圖G=(X,E,R)的一棵支撐樹,則以下陳述等價:(1)T是G的最大支撐樹;(2)對于任意的e′∈E(T),從T中移出e′得T<,1>,T<,2>,則w(e′)=<,e∈[T<,1>,T<,2>]G>Vw(e);(3)對任意的u,vv∈X(u≠v),T中u,v之間的惟一路是G中最優(yōu)(u,v)路.并建立了G=(X,E,R)中任兩點的連通強度和R的傳遞閉包

4、t(R)之間的關(guān)系:定理3.3設(shè)X={x<,1>,x<,2>,…,x<,n>},R=(r<,ij>)<,nxn>是X上的模糊相似關(guān)系,R的傳遞閉包t(R)=R<'n>=(r<,ij><'(n)>)<,nxn>,G=(X,E,R)是與〈X,R〉相對應(yīng)的模糊關(guān)系圖,則t(R)(x<,i>,x<,j>)=r<,ij><'(n)>=S(x<,i>,x<,j>).由此仿照圖論中求賦權(quán)連通圖最小支撐樹的Dijkstra算法,給出了模糊聚類的最大支撐

5、樹算法如下:設(shè)模糊相似矩陣R=(r<,ij>)<,nxn>,聚類水平為λ,令A(yù)<,k>表示樹的結(jié)點集,記r<,ij>=r(x<,i>,x<,j>).(1)任選一點v<,1>∈X,記A<,1>={v<,1>},令l(v<,1>)=0,p(v<,1>)=φ,l(v):=r(v<,1>,v),p(v):=v<,1>(Vv∈X\A<,1>),k:=1.(2)算max<,v∈X\A<,k>> l(v)設(shè)=l(v<'*>),令A(yù)<,k+1>=A<,

6、k> ∪{v<'*>},對每個v∈X\A<,k+1>,若r(v<'*>,v)>l(v),則l(v)=r(v<'*>,v),p(v)=v<'*>.(3)若k=n-1,據(jù)指針p(·)倒向追蹤得最大支撐樹T;T去掉w(e)<λ的所有邊e后的各連通分支即為X在λ水平上的一個分類,停.否則,令k:=k+1,回(2).而且其復(fù)雜性僅為O(n<'2>),最后通過實例進行了驗證.第四章討論灰色關(guān)聯(lián)聚類分析及其傳統(tǒng)的逐行檢查法,分析用這種方法進行灰色關(guān)聯(lián)

7、聚類的復(fù)雜性為O(m<'4>).仿照模糊聚類分析的最大支撐樹方法中連通強度的定義和相關(guān)結(jié)論,給出了賦權(quán)圖G=(V,E,D)中兩點u,v間的連通強度S(u,v)及其最大支撐樹的一個性質(zhì).定義了G=(V,E,D)的λ-截圖G<,λ>和連通閉包G兩個概念,得到了如下結(jié)論:定理4.2設(shè)賦權(quán)圖G=(V,E,D),則任取λ∈[0,1],G<,λ>=G<,λ>.由此分析說明了指標(biāo)集X中兩點u,v在λ水平上能夠歸為一類,等價于它們在關(guān)聯(lián)圖G=(X,E,