【文章內(nèi)容簡(jiǎn)介】 X??? ? ?? 1( ) ( )rni r p p r i r p p riX X X X X X X X??? ? ? ? ? ? ?? 1111( ) ( ) ( ) ( )( ) ( ) ( ) ( )rrrrnnir p ir p ir p p riinnp r ir p p r p riiX X X X X X X XX X X X X X X X??????? ? ? ? ? ???? ? ? ? ? ????? 111( ) ( ) ( ) ( )2( ) ( ) ( ) ( )pqrnnip p ip p iq p iq piinp r ir p r p r p riX X X X X X X XX X X X n X X X X?????? ? ? ? ? ???? ? ? ? ? ???? 1( ) ( )( ) ( )qnp iq q q p iq q q pir p r p rS X X X X X X X Xn X X X X??? ? ? ? ? ? ? ??? ? ?? 1( ) ( ) ( ) ( )( ) ( )qnp iq q iq q q p q p qip p q q p p q qr p prrS X X X X n X X X Xn X n X n X n Xn X Xnn???? ? ? ? ? ? ????? ? ?? 2( ) ( ) ( ) ( )pp q q p q p q p q p qrnS S n X X X X X X X Xn??? ? ? ? ? ? ? ? ( ) ( ) ( ) ( )qpp q q p q p q p q p qrnnS S n X X X X X X X Xn??? ? ? ? ? ? ? ? ? 從而，由 （ 5 .25 ） 式知 2( ) ( )qpp q p q p qrnnD X X X Xn?? ? ? （ 5 .27 ） 那么，由（ ）式和（ 9 ）式，可以得到離差平方和法的平方距離的遞推公式為： 2( ) ( )rkk r r k r krknnD X X X Xnn?? ? ?? 2( ) ( )( ) ( ) ( ) ( )prkk p k pr k rq p qk q k q p q p qrrnnnX X X Xn n nn n nX X X X X X X Xnn??? ? ???????? ? ? ? ? ??? ( ) ( )( ) ( )( ) ( )k p k pk p k pr k p kk q k qkqkqr k q kpqkp q p qr k rn n n nX X X Xn n n nn n n nX X X Xn n n nnnnX X X Xn n n??? ? ? ?????? ? ? ????? ? ? ?? 2 2 2k p k q kk p k q p qr k r k r kn n n n nD D Dn n n n n n??? ? ?? ? ? 三、類(lèi)間距離的統(tǒng)一性 ? 上述八種系統(tǒng)聚類(lèi)法的步驟完全一樣，只是距離的遞推公式不同。蘭斯（ Lance）和威廉姆斯（ Williams）于 1967年給出了一個(gè)統(tǒng)一的公式。 () 其中 ap、 aq、 ? 、 ?是參數(shù)，不同的系統(tǒng)聚類(lèi)法，它們?nèi)〔? 同的數(shù)，詳見(jiàn)表 。 ? 這里應(yīng)該注意，不同的聚類(lèi)方法結(jié)果不一定完全相同，一般只是大致相似。如果有很大的差異，則應(yīng)該仔細(xì)考查，找到問(wèn)題所在；另外，可將聚類(lèi)結(jié)果與實(shí)際問(wèn)題對(duì)照，看哪一個(gè)結(jié)果更符合經(jīng)驗(yàn)。 2 2 2 2 2 2k r p k p q k q p q k p k qD D D D D D? ? ? ?? ? ? ? ? 方 法 p? q? ? ? 最短距離法 1/2 1/2 0 1 / 2 最長(zhǎng)距離法 1/2 1/2 0 1/2 中間距離法 1/2 1/2 1 / 4 0 重心法 prnn qrnn pq??? 0 類(lèi)平均法 prnn qrnn 0 0 可變類(lèi)平均法 ( 1 ) prnn?? ( 1 ) qrnn?? ( 1 )? ? 0 可變法 ( 1 ) / 2?? ( 1 ) / 2?? ( 1 )? ? 0 離差平方和法 ( ) ( )p k r kn n n n?? ( ) ( )q k r kn n n n?? ()k k rn n n?? 0 表 系統(tǒng)聚類(lèi)法參數(shù)表 第四節(jié) K均值聚類(lèi)分析 ? 系統(tǒng)聚類(lèi)法需要計(jì)算出不同樣品或變量的距離，還要在聚類(lèi)的每一步都要計(jì)算“類(lèi)間距離”，相應(yīng)的計(jì)算量自然比較大；特別是當(dāng)樣本的容量很大時(shí)，需要占據(jù)非常大的計(jì)算機(jī)內(nèi)存空間，這給應(yīng)用帶來(lái)一定的困難。而 K—均值法是一種快速聚類(lèi)法，采用該方法得到的結(jié)果比較簡(jiǎn)單易懂，對(duì)計(jì)算機(jī)的性能要求不高，因此應(yīng)用也比較廣泛。 ? K均值法是麥奎因（ MacQueen， 1967）提出的，這種算法的基本思想是將每一個(gè)樣品分配給最近中心（均值）的類(lèi)中，具體的算法至少包括以下三個(gè)步驟： 1．將所有的樣品分成 K個(gè)初始類(lèi)； 2．通過(guò)歐氏距離將某個(gè)樣品劃入離中心最近的類(lèi)中，并對(duì)獲得樣品與失去樣品的類(lèi)，重新計(jì)算中心坐標(biāo)； 3．重復(fù)步驟 2，直到所有的樣品都不能再分配時(shí)為止。 ? K均值法和系統(tǒng)聚類(lèi)法一樣，都是以距離的遠(yuǎn)近親疏為標(biāo)準(zhǔn)進(jìn)行聚類(lèi)的，但是兩者的不同之處也是明顯的：系統(tǒng)聚類(lèi)對(duì)不同的類(lèi)數(shù)產(chǎn)生一系列的聚類(lèi)結(jié)果，而 K—均值法只能產(chǎn)生指定類(lèi)數(shù)的聚類(lèi)結(jié)果。具體類(lèi)數(shù)的確定，離不開(kāi)實(shí)踐經(jīng)驗(yàn)的積累；有時(shí)也可以借助系統(tǒng)聚類(lèi)法以一部分樣品為對(duì)象進(jìn)行聚類(lèi)，其結(jié)果作為 K—均值法確定類(lèi)數(shù)的參考。 ? 下面通過(guò)一個(gè)具體問(wèn)題說(shuō)明 K均值法的計(jì)算過(guò)程。 ? 【 例 】 假定我們對(duì) A、 B、 C、 D四個(gè)樣品分別測(cè)量?jī)蓚€(gè)變量和得到結(jié)果見(jiàn)表 。 試將以上的樣品聚成兩類(lèi)。 樣品 變量 1X 2X A 5 3 B 1 1 C 1 2 D 3 2 表 樣品測(cè)量結(jié)果 第一步：按要求取 K=2，為了實(shí)施均值法聚類(lèi)，我們將這些樣品隨意分成兩類(lèi)，比如（ A、 B）和（ C、 D），然后計(jì)算這兩個(gè)聚類(lèi)的中心坐標(biāo)，見(jiàn)表 。 表 ，比如（ A、 B）類(lèi)的， 等等。 中心坐標(biāo) 聚類(lèi) 1X 2X （ A 、 B ） 2 2 （ C 、 D ） 1 2 表 中心坐標(biāo) 15 ( 1 ) 22X???? 第二步：計(jì)算某個(gè)樣品到各類(lèi)中心的歐氏平方距離，然后將該樣品分配給最近的一類(lèi)。對(duì)于樣品有變動(dòng)的類(lèi)，重新計(jì)算它們的中心坐標(biāo)，為下一步聚類(lèi)做準(zhǔn)備。先計(jì)算 A到兩個(gè)類(lèi)的平方距離： 由于 A到（ A、 B）的距離小于到（ C、 D）的距離，因此 A不用重新分配。計(jì)算 B到兩類(lèi)的平方距離： 10)23()25())(,( 222 ?????ABAd 61)23()15())(,( 222 ?????CDAd 10)21()21())(,( 222 ??????ABBd 9)21()11())(,( 222 ??????CDBd ? 由于 B到（ A、 B）的距離大于到（ C、 D）的距離，因此 B要分配給（ C、 D）類(lèi)，得到新的聚類(lèi)是（ A）和（ B、 C、D）。更新中心坐標(biāo)如表 。 中心坐標(biāo) 聚類(lèi) 1X 2X （ A ） 5 3 （ B 、 C 、 D ） 1 1 表 更新后的中心坐標(biāo) 第三步：再次檢查每個(gè)樣品，以決定是否需要重新分類(lèi)。計(jì)算各樣品到各中心的距離平方，得結(jié)果見(jiàn)表 。 ? 到現(xiàn)在為止，每個(gè)樣品都已經(jīng)分配給距離中心最近的類(lèi)，因此聚類(lèi)過(guò)程到此結(jié)束。最終得到 K=2的聚類(lèi)結(jié)果是 A獨(dú)自成一類(lèi)， B、 C、 D聚成一類(lèi)。 樣品到中心的距離平方 聚類(lèi) A B C D （ A ） 0 40 41 89 （ B 、 C 、 D ） 52 4 5 5 表 樣品聚類(lèi)結(jié)果 第五節(jié) 有序樣品的聚類(lèi)分析法 一 有序樣品可能的分類(lèi)數(shù)目 二 費(fèi)希爾最優(yōu)求解法 三 一個(gè)典型例子 ? 以上的系統(tǒng)聚類(lèi)和 K—均值聚類(lèi)中，樣品的地位是彼此獨(dú)立的，沒(méi)有考慮樣品的次序。但在實(shí)際應(yīng)用中，有時(shí)樣品的次序是不能變動(dòng)的，這就產(chǎn)生了有序樣品的聚類(lèi)分析問(wèn)題。例如對(duì)動(dòng)植物按生長(zhǎng)的年齡段進(jìn)行分類(lèi)，年齡的順序是不能改變的，否則就沒(méi)有實(shí)際意義了；又例如在地質(zhì)勘探中，需要通過(guò)巖心了解地層結(jié)構(gòu)，此時(shí)按深度順序取樣，樣品的次序也不能打亂。 ? 如果用 X（ 1） ， X（ 2） ， … ， X（ n） 表示 n個(gè)有序的樣品，則每一類(lèi)必須是這樣的形式，即 X（ i） ， X（ i+1)， … ， X（ j） ，其中 1 ? r ? n，且 j ? n，簡(jiǎn)記為 Gi = ｛ i， i+1， … ， j｝。在同一類(lèi)中的樣品是次序相鄰的。這類(lèi)問(wèn)題稱(chēng)為有序樣品的聚類(lèi)分析。 一、有序樣品可能的分類(lèi)數(shù)目 ? n個(gè)有序樣品分成 k類(lèi)，則一切可能的分法有 種。 ? 實(shí)際上， n個(gè)有序樣品共有（ n ?1） 個(gè)間隔，分成 k類(lèi)相當(dāng)于在這（ n ?1） 個(gè)間隔中插入 k ?1根“棍子”。由于不考慮棍子的插入順序，是一個(gè)組合問(wèn)題，共有 種插法。 圖 有序樣品的分類(lèi)法 ? 這就是 n個(gè)有序樣品分成 k類(lèi)的一切可能分法。因此，對(duì)于有限的 n和 k，有序樣品的所有可能分類(lèi)結(jié)果是有限的，可以在某種損失函數(shù)意義下，求得最優(yōu)解。所以有序樣品聚類(lèi)分析又稱(chēng)為最優(yōu)分割，該算法是費(fèi)希爾（ Fisher）最先提出來(lái)的，故也稱(chēng)之為費(fèi)希爾最優(yōu)求解法。 11??knC11??knC 二、費(fèi)希爾最優(yōu)求解法 ? 2 ．定義分類(lèi)的損失函數(shù)。費(fèi)希爾最優(yōu)求解法定義的分類(lèi)損失函數(shù)的思想類(lèi)似于系統(tǒng)聚類(lèi)分析中的 W a r d 法，即要求分類(lèi)后產(chǎn)生的離差平方和的增量最小。用),( knb表示將n個(gè)有序樣品分為k類(lèi)的某一種分法： }1,1,{ 2111 ??? iiiG ?，2 2 2 3{ , 1 , , 1 }G i i i? ? ?， ，},1,{ niiG kkk ??? 其中11 1 ki i i n? ? ? ? ?。定義上述分類(lèi)法的損失函數(shù)為 ?????ktttiiDknbL11)1,()],([ ( ) 上式中的11 ??? ni k。 對(duì)于固定的n和k，)],([( knbL越小，表示各類(lèi)的離差平方和越小，分類(lèi)就是越有效的。因此，要求尋找一種分法),( knb，使分類(lèi)的損失函數(shù))],([( knbL最小，這種最優(yōu)分類(lèi)法記為),( knp。 3 ．求最優(yōu)分類(lèi)法的遞推公式。具體計(jì)算最優(yōu)分類(lèi)的過(guò)程是通過(guò)遞推公式獲得的。 先考慮2k ?的情形 對(duì)所有的j考慮使得 , ),(),1()]2,([( njDjDnbL ??最小的*j。得到最優(yōu)分類(lèi))2,( np：}1,2,1{ *1 ?? jG ?，},{ *2 njG ??。