聚類分析簡單例子.ppt

一、系統(tǒng)聚類的基本思想,系統(tǒng)聚類的基本思想是：距離相近的樣品（或變量）先聚成類，距離相遠的后聚成類，過程一直進行下去，每個樣品（或變量）總能聚到合適的類中。系統(tǒng)聚類過程是：假設總共有n個樣品（或變量），第一步將每個樣品（或變量）獨自聚成一類，共有n類；第二步根據所確定的樣品（或變量）“距離”公式，把距離較近的兩個樣品（或變量）聚合為一類，其它的樣品（或變量）仍各自聚為一類，共聚成n1類；第三步將“距離”最近的兩個類進一步聚成一類，共聚成n2類；，以上步驟一直進行下去，最后將所有的樣品（或變量）全聚成一類。為了直觀地反映以上的系統(tǒng)聚類過程，可以把整個分類系統(tǒng)畫成一張譜系圖。所以有時系統(tǒng)聚類也稱為譜系分析。除系統(tǒng)聚類法外，還有有序聚類法、動態(tài)聚類法、圖論聚類法、模糊聚類法等，限于篇幅，我們只介紹系統(tǒng)聚類方法。,二、類間距離與系統(tǒng)聚類法,在進行系統(tǒng)聚類之前，我們首先要定義類與類之間的距離，由類間距離定義的不同產生了不同的系統(tǒng)聚類法。常用的類間距離定義有8種之多，與之相應的系統(tǒng)聚類法也有8種，分別為最短距離法、最長距離法、中間距離法、重心法、類平均法、可變類平均法、可變法和離差平方和法。它們的歸類步驟基本上是一致的，主要差異是類間距離的計算方法不同。以下用dij表示樣品Xi與Xj之間距離，用Dij表示類Gi與Gj之間的距離。,1.最短距離法定義類Gi與Gj之間的距離為兩類最近樣品的距離，即為(5.11)設Gk類與合并成一個新類記為Gr，則任一類與的距離為(5.12),最短距離法進行聚類分析的步驟如下：（1）定義樣品之間距離，計算樣品的兩兩距離，得一距離陣記為D（0），開始每個樣品自成一類，顯然這時Dij=dij。（2）找出距離最小元素，設為Dpq，則將Gp和Gq合并成一個新類，記為Gr，即Gr=Gp，Gq。（3）按（5.12）計算新類與其它類的距離。（4）重復（2）、（3）兩步，直到所有元素。并成一類為止。如果某一步距離最小的元素不止一個，則對應這些最小元素的類可以同時合并。,【例5.1】設有六個樣品，每個只測量一個指標，分別是1，2，5，7，9，10，試用最短距離法將它們分類。（1）樣品采用絕對值距離，計算樣品間的距離陣D（0），見表5.1,表5.1,（2）D（0）中最小的元素是D12D561，于是將G1和G2合并成G7，G5和G6合并成G8，并利用（5.12）式計算新類與其它類的距離D（1），見表5.2,表5.2,（3）在D（1）中最小值是D34D482，由于G4與G3合并，又與G8合并，因此G3、G4、G8合并成一個新類G9，其與其它類的距離D（2），見表5.3,表5.3,（4）最后將G7和G9合并成G10，這時所有的六個樣品聚為一類，其過程終止。上述聚類的可視化過程見圖5.1所示，橫坐標的刻度表示并類的距離。這里我們應該注意，聚類的個數要以實際情況所定，其詳細內容將在后面討論。,圖5.1最短距離聚類法的過程,再找距離最小兩類并類，直至所有的樣品全歸為一類為止?？梢钥闯鲎铋L距離法與最短距離法只有兩點不同：一是類與類之間的距離定義不同；另一是計算新類與其它類的距離所用的公式不同。,3.中間距離法最短、最長距離定義表示都是極端情況，我們定義類間距離可以既不采用兩類之間最近的距離也不采用兩類之間最遠的距離，而是采用介于兩者之間的距離，稱為中間距離法。中間距離將類Gp與Gq類合并為類Gr，則任意的類Gk和Gr的距離公式為(140)(5.15)設DkrDkp，如果采用最短距離法，則Dkr=Dkp，如果采用最長距離法，則Dkr=Dkq。如圖5.2所示，(5.15)式就是取它們（最長距離與最短距離）的中間一點作為計算Dkr的根據。,特別當=14，它表示取中間點算距離，公式為(5.16),圖5.2中間距離法,【例5.2】針對例5.1的數據，試用重心法將它們聚類。（1）樣品采用歐氏距離，計算樣品間的平方距離陣D2（0），見表5.4所示。,表5.4,（2）D2（0）中最小的元素是D212D2561，于是將G1和G2合并成G7，G5和G6合并成G8，并利用（5.18）式計算新類與其它類的距離得到距離陣D2（1），見表5.5：其中，其它結果類似可以求得,（3）在D2（1）中最小值是D2344，那么G3與G4合并一個新類G9，其與與其它類的距離D2（2），見表5.6：,表5.6,（4）在中最小值是12.5，那么與合并一個新類，其與與其它類的距離，見表5.7：,表5.7,（5）最后將G7和G10合并成G11，這時所有的六個樣品聚為一類，其過程終止。上述重心法聚類的可視化過程見圖5.3所示，橫坐標的刻度表示并類的距離。,圖5.3重心聚類法的過程,6.可變類平均法由于類平均法中沒有反映出Gp和Gq之間的距離Dpq的影響，因此將類平均法進一步推廣，如果將Gp和Gq合并為新類Gr，類Gk與新并類Gr的距離公式為：（5.22）其中是可變的且<1，稱這種系統(tǒng)聚類法為可變類平均法。,8.離差平方和法該方法是Ward提出來的，所以又稱為Ward法。該方法的基本思想來自于方差分析，如果分類正確，同類樣品的離差平方和應當較小，類與類的離差平方和較大。具體做法是先將n個樣品各自成一類，然后每次縮小一類，每縮小一類，離差平方和就要增大，選擇使方差增加最小的兩類合并，直到所有的樣品歸為一類為止。設將n個樣品分成k類G1，G2，Gk，用Xit表示Gt中的第I個樣品，nt表示Gt中樣品的個數，是Gt的重心，則Gt的樣品離差平方和為,這種系統(tǒng)聚類法稱為離差平方和法或Ward方法。下面論證離差平方和法的距離遞推（5.26）式。,由于,三、類間距離的統(tǒng)一性,上述八種系統(tǒng)聚類法的步驟完全一樣，只是距離的遞推公式不同。蘭斯（Lance）和威廉姆斯（Williams）于1967年給出了一個統(tǒng)一的公式。(5.28)其中ap、aq、是參數，不同的系統(tǒng)聚類法，它們取不同的數，詳見表5.8。這里應該注意，不同的聚類方法結果不一定完全相同，一般只是大致相似。如果有很大的差異，則應該仔細考查，找到問題所在；另外，可將聚類結果與實際問題對照，看哪一個結果更符合經驗。,表5.8系統(tǒng)聚類法參數表,【例5.3】假定我們對A、B、C、D四個樣品分別測量兩個變量和得到結果見表5.9。試將以上的樣品聚成兩類。,表5.9樣品測量結果,動態(tài)聚類法,第一步：按要求取K=2，為了實施均值法聚類，我們將這些樣品隨意分成兩類，比如（A、B）和（C、D），然后計算這兩個聚類的中心坐標，見表5.10所示。表5.10中的中心坐標是通過原始數據計算得來的，比如（A、B）類的，等等。,表5.10中心坐標,第二步：計算某個樣品到各類中心的歐氏平方距離，然后將該樣品分配給最近的一類。對于樣品有變動的類，重新計算它們的中心坐標，為下一步聚類做準備。先計算A到兩個類的平方距離：由于A到（A、B）的距離小于到（C、D）的距離，因此A不用重新分配。計算B到兩類的平方距離：,由于B到（A、B）的距離大于到（C、D）的距離，因此B要分配給（C、D）類，得到新的聚類是（A）和（B、C、D）。更新中心坐標如表5.11所示。,表5.11更新后的中心坐標,第三步：再次檢查每個樣品，以決定是否需要重新分類。計算各樣品到各中心的距離平方，得結果見表5.12。到現在為止，每個樣品都已經分配給距離中心最近的類，因此聚類過程到此結束。最終得到K=2的聚類結果是A獨自成一類，B、C、D聚成一類。,表5.12樣品聚類結果,