系統(tǒng)聚類的方法解析

1、聚類分析 1 聚類分析 一聚類分析的定義 二系統(tǒng)聚類的基本思想 三八種系統(tǒng)聚類方法 四類間距離的統(tǒng)一性 一、聚類分析的定義 “ 物以類聚，人以群分”。對事物進(jìn)行分類，是人們認(rèn) 識事物的出發(fā)點，也是人們認(rèn)識世界的一種重要方法。 因此，分類學(xué)已成為人們認(rèn)識世界的一門基礎(chǔ)科學(xué)。 聚類分析就是分析如何對樣品（或變量）進(jìn)行量化分 類的問題。通常聚類分析分為Q型聚類和R型聚類。Q 型聚類是對樣品進(jìn)行分類處理，R型聚類是對變量進(jìn)行 分類處理。 二、系統(tǒng)聚類的基本思想二、系統(tǒng)聚類的基本思想 系統(tǒng)聚類的基本思想是：距離相近的樣品（或變量）先聚成類， 距離相遠(yuǎn)的后聚成類，過程一直進(jìn)行下去，每個樣品（或變量） 總能

2、聚到合適的類中。 系統(tǒng)聚類法是諸聚類分析方法中使用最多的一種，按下列步驟 進(jìn)行： ?計算n個樣品兩兩之間的距離，構(gòu)成距離矩陣 ?合并距離最近的兩類為一新類 ?計算新類與當(dāng)前各類的距離。再合并、計算，直至只有一 類為止 ?畫聚類圖，解釋 ?將n個樣品各作為一類 三、八種系統(tǒng)聚類方法 在進(jìn)行系統(tǒng)聚類之前，我們首先要定義類與類之間的 距離，由類間距離定義的不同產(chǎn)生了不同的系統(tǒng)聚類法。 常用的類間距離定義有8種之多，與之相應(yīng)的系統(tǒng)聚類法 也有8種，分別為最短距離法、最長距離法、中間距離法、 重心法、類平均法、可變類平均法、可變法和離差平方和 法。它們的歸類步驟基本上是一致的，主要差異是類間距 離的計算

3、方法不同。以下用d ij表示樣品Xi與Xj之間距離， 用Dij表示類Gi與Gj之間的距離。 1. 最短距離法最短距離法 定義類與之間的距離為兩類最近樣品的距離，即為 (1) 設(shè)類與合并成一個新類記為，則任一類與的距離為 (2) ij GXGX ij dD jjii ? ? , min , min ikjr krij XGXG Dd ? ? , minmin,min ikjpikjq ijij XGXGxGxG dd ? ? min, kpkq DD? ?最短距離法進(jìn)行聚類分析的步驟如下： （1）定義樣品之間距離，計算樣品的兩兩距離，得一距離 陣記為D （0） ，開始每個樣品自成一類，顯然這時D

4、ij= d ij。 （2）找出距離最小元素，設(shè)為Dpq，則將Gp和Gq合并成一個 新類，記為Gr，即Gr=Gp，Gq。 （3）按（5.12）計算新類與其它類的距離。 （4）重復(fù)（2）、（3）兩步，直到所有元素。并成一類為 止。如果某一步距離最小的元素不止一個，則對應(yīng)這些 最小元素的類可以同時合并。 1. 最短距離法最短距離法 ?【例1】設(shè)有六個樣品，每個只測量一個指標(biāo)，分別是1，2， 5，7，9，10 ，試用最短距離法將它們分類。 （1）樣品采用絕對值距離，計算樣品間的距離陣D （0） ，見 表1 G1 G2 G3 G4 G5 G6 G1 0 G2 1 0 G3 4 3 0 G4 6 5 2

5、0 G5 8 7 4 2 0 G6 9 8 5 3 1 0 表 1 1. 最短距離法 （2）D （0）中最小的元素是D12 D 56 1，于是將G1和G2合 并成G7，G5和G6合并成G8，并利用（5.12）式計算新類與其 它類的距離D （1） ，見表2 G7 G3 G4 G8 G7 0 G3 3 0 G4 5 2 0 G8 7 4 2 0 表 2 1. 最短距離法 （3）在D （1）中最小值是D34 D482，由于G4與G3合并， 又與G8合并，因此G3、G4、G8合并成一個新類G9，其與其 它類的距離D （2） ，見表 3 G 7 G 9 G7 0 G9 3 0 表 3 1. 最短距離法

6、（4）最后將G7和G9合并成G10，這時所有的六個樣品聚為一 類，其過程終止。 上述聚類的可視化過程見圖1所示，橫坐標(biāo)的刻度表示并類 的距離。這里我們應(yīng)該注意，聚類的個數(shù)要以實際情況所定， 其詳細(xì)內(nèi)容將在后面討論。 圖1 最短距離聚類法的過程 1. 最短距離法 定義類 i G 與 j G 之間的距離為兩類最遠(yuǎn)樣品的距離，即 為 , max ipjq pqij XGXG Dd ? ? (3) 最長距離法與最短距離法的并類步驟完全一樣，也是將 各樣品先自成一類，然后將距離最小的兩類合并。將類 p G 與 q G 合并為 r G ，則任一類 k G 與 r G 的類間距離公 式為 2.最長距離法 最

7、長距離法 ?再找距離最小兩類并類，直至所有的樣品全歸為一類為止。 可以看出最長距離法與最短距離法只有兩點不同： 一是類與類之間的距離定義不同； 另一是計算新類與其它類的距離所用的公式不同。 , max ikjr krij XGXG Dd ? ? , maxmax,max ikjpjikjq ijij XGXGxGxG dd ? ? max, kpkq DD? （4 ） 2.最長距離法 最短、最長距離定義表示都是極端情況，我們定義類間距離 可以既不采用兩類之間最近的距離也不采用兩類之間最遠(yuǎn)的 距離，而是采用介于兩者之間的距離，稱為中間距離法。 中間距離將類G p與Gq類合并為類Gr，則任意的類G

8、k和Gr的距 離公式為 (?14 ? 0) (5) 設(shè)DkqDkp，如果采用最短距離法，則Dkr=Dkp，如果采用 最長距離法，則Dkr= Dkq。如圖2所示，(5)式就是取它們 （最長距離與最短距離）的中間一點作為計算Dkr的根據(jù)。 2222 2 1 2 1 pqkqkpkr DDDD? 3.中間距離法 中間距離法 ?特別當(dāng)?= ? 14，它表示取中間點算距離，公式為 (6) 222 4 1 2 1 2 1 pqkpkpkr DDDD? 圖2 中間距離法 3.中間距離法 4. 重心法重心法 重心法定義類間距離為兩類重心（各類樣品的均值）的距 離。重心指標(biāo)對類有很好的代表性，但利用各樣本的信息

9、 不充分。 設(shè) p G與 q G分別有樣品 p n ， q n 個， 其重心分別為 p X和 q X， 則 p G與 q G之間的距離定義為 p X和 q X之間的距離，這里 我們用歐氏距離來表示，即 2 () () pqpqpq DXXXX? (7) 設(shè)將設(shè)將 p G 和和 q G 合并為合并為 r G， 則則 r G內(nèi)樣品個數(shù)為內(nèi)樣品個數(shù)為 qpr nnn? ， 它的重心是它的重心是 )( 1 qqpp r r XnXn n X?，類 k G的重心是的重心是 k X ， 那么依據(jù)（那么依據(jù)（ 5.175.17）式它與新類）式它與新類 r G的距離為的距離為 2222 2 pqpq krkp

10、kqpq rrr nnn n DDDD nnn ? （8） 這里我們應(yīng)該注意，這里我們應(yīng)該注意， 實際上實際上（8） 式表示的類式表示的類 k G 與新類與新類 r G 的的 距離為： 2 () () krkrkr DXXXX? 11 ()() kppqqkppqq rr Xn Xn XXn Xn X nn ? 22 2 22 1 (2) pq kkkpkq rr ppppqpqqqq r nn X XX XX X nn n X Xn n X Xn X X n ? ? 利用利用 1 () kkpkkqkk r X Xn X Xn X X n ? 代入上式，有代入上式，有 2 (2) (2) (

11、2) p krkkkppp r q kkkqqq r pq pppqqq r n DX XX XX X n n X XX XX X n n n X XX XX X n ? ? ? 222 2 pqpq kpkqpq rrr nnn n DDD nnn ? （9） 類平均法定義類間距離平方為這兩類元素兩兩之間距離平方的 平均數(shù)，即為 22 1 ipjj pqij XGXG pq Dd n n ? ? ? ? (10) 設(shè)聚類的某一步將 p G 和 q G 合并為 r G，則任一類類 k G與 r G的 距離為： 22 1 ikjr krij XG XG kr Dd nn ? ? ? ? 22 1

12、 () ikjpikjq ijij XG XGXG XG kr dd nn ? ? ? ? ? 22 pq kpkq rr nn DD nn ? （11） 類平均法的聚類過程與上述方法完全類似，這里就不在詳述了。 5. 類平均法類平均法 6.可變類平均法 可變類平均法 由于類平均法中沒有反映出Gp和Gq之間的距離Dpq的影響， 因此將類平均法進(jìn)一步推廣，如果將Gp和Gq合并為新類Gr， 類Gk與新并類Gr的距離公式為： （12） 其中?是可變的且? 1，稱這種系統(tǒng)聚類法為可變類平均法。 2222 (1)() pq krkpkqpq rr nn DDDD nn ? 針對于中間法而言，如果將中間法

13、的前兩項的系數(shù)也依賴 于?，那么，如果將 p G 和 q G 合并為新類 r G，類 k G 與新 并類 r G 的距離公式為： 2222 1 () 2 krkpkqpq DDDD ? ? ? ? （13） 其中?是可變的，且1?。顯然在可變類平均法中取 1 2 pq rr nn nn ?， 即為可變法?？勺冾惼骄ㄅc可變法的分類 效果與 ? 的選擇關(guān)系很大，在實際應(yīng)用中 ? 常取負(fù)值。 7.可變法 法 該方法是Ward提出來的，所以又稱為Ward法。該方法的基 本思想來自于方差分析，如果分類正確，同類樣品的離差平 方和應(yīng)當(dāng)較小，類與類的離差平方和較大。具體做法是先將 n個樣品各自成一類，然后

14、每次縮小一類，每縮小一類，離 差平方和就要增大，選擇使方差增加最小的兩類合并，直到 所有的樣品歸為一類為止。 設(shè)將n個樣品分成k類G1，G2，Gk，用Xit表示Gt中的第I 個樣品，n t表示Gt中樣品的個數(shù)， 是Gt的重心，則Gt的樣品 離差平方和為 1 () () t n tittitt t SXXXX ? ? ? (14) t X 8.離差平方和法 離差平方和法 8.離差平方和法 離差平方和法 如果 p G 和 q G 合并為新類 r G 類內(nèi)離差平方和分別為 1 () () p n pippipp i SXXXX ? ? ? 1 () () q n qiqqiqq i SXXXX ?

15、? ? 1 () () r n rirrirr i SXXXX ? ? ? 8.離差平方和法 ? ?這種系統(tǒng)聚類法稱為離差平方和法或Ward方法。下面論證 離差平方和法的距離遞推（16）式。 它們反映了各自類內(nèi)樣品的分散程度，如果 p G 和 q G 這兩類 相距較近，則合并后所增加的離散平方和 rpq SSS? 應(yīng)較 ??；否則，應(yīng)較大。于是定義 p G 和 q G 之間的平方距離為： 2 pqrpq DSSS? (15) 其中 rpq GGG? ，可以證明類間距離的遞推公式為 2222 kpkq k krkpkqpq rkrkrk nnnn n DDDD nnnnnn ? ? ? (5.26

16、) 8.離差平方和法 離差平方和法 ?由于 1 () () r n rirrirr i SXXXX ? ? ? 1 () () r n irpprirppr i XXXXXXXX ? ? ? 11 11 () ()() () () ()() () rr rr nn irpirpirppr ii nn prirpprpr ii XXXXXXXX XXXXXXXX ? ? ? ? ? ? 11 1 () ()() () 2()()() () pq r nn ippippiqpiqp ii n prirprprpr i XXXXXXXX XXXXn XXXX ? ? ? ? ? ? 1 () ()

17、() () q n piqqqpiqqqp i rprpr SXXXXXXXX n XXXX ? ? ? ? 1 () ()() () () () q n piqqiqqqpqpq i ppqqppqq rpp rr SXXXXn XXXX n Xn Xn Xn X n XX nn ? ? ? ? ? 2 () ()() () p pqqpqpqpqpq r n SSn XXXXXXXX n ? () ()() () qp pqqpqpqpqpq r nn SSn XXXXXXXX n ? 8.離差平方和法 離差平方和法 ?從而，由（5.25）式知 2 ()() qp pqpqpq r nn

18、DXXXX n ? （5.27） 那么，由（5.27）式和（5.19）式，可以得到離差平方和法的平 方距離的遞推公式為： 2 () () rk krrkrk rk nn DXXXX nn ? ? 2 () () () ()() () p rk kpkp rkr qpq kqkqpqpq rr n nn XXXX nnn nn n XXXXXXXX nn ? ? ? ? ? ? ? ? ? 8.離差平方和法 離差平方和法 () () () () () () kpkp kpkp rkpk kqkq kqkq rkqk pq k pqpq rkr nnn n XXXX nnnn nnn n XXXX nnnn n n n XXXX nnn ? ? ? ? ? ? ? ? 222 kp