Cluster-Analysis(聚類分析).ppt

1、經(jīng)濟管理類研究生專業(yè)學(xué)位課,Multivariate Statistics Analysis 多元統(tǒng)計分析,第2講 聚類分析,2.1 聚類分析的基本思想,2.2 相似性的度量,2.3 類和類的特征,2.4 系統(tǒng)聚類法,2.5 非系統(tǒng)聚類法簡介,2.1 聚類分析的基本思想,1.什么是聚類分析？ 所謂“類”就是相似元素的集合。 聚類就是根據(jù)研究對象某一方面的相似性將其歸類，使得同一類中的對象之間的相似性比與其他類的對象的相似性更強?；蛘呤诡悆?nèi)對象的同質(zhì)性最大化和類間對象的異質(zhì)性最大化。 2.基本思想 根據(jù)研究對象的多個觀測指標，具體地找出一些能夠度量各對象之間相似程度的統(tǒng)計量，然后利用統(tǒng)計量將樣品

2、或指標進行歸類。把相似的樣品或指標歸為一類，把不相似的歸為其他類。直到把所有的樣品（或指標）聚合完畢.,2.1 聚類分析的基本思想,3、聚類分析的類型： 對樣品分類，稱為Q型聚類分析 對變量分類，稱為R型聚類分析 Q型聚類是使具有相似性特征的樣品聚集在一起，使差異性大的樣品分離開來。 R型聚類是使具有相似性的變量聚集在一起，差異性大的變量分離開來。 R型聚類可在相似變量中選擇少數(shù)具有代表性的變量參與其他分析，實現(xiàn)減少變量個數(shù)，達到變量降維的目的。,2.2 相似性的度量,一、樣本或變量的相似性程度的數(shù)量指標： 1、相似系數(shù) 性質(zhì)越接近的變量或樣品，它們的相似系數(shù)越接近于1或一l，而彼此無關(guān)的變量

3、或樣品，它們的相似系數(shù)則越接近于0，相似的為一類，不相似的為不同類； 2、距離 它是將每一個樣品看作p維空間的一個點，并用某種度量方法測量點與點之間的距離，距離較近的歸為一類，距離較遠的點應(yīng)屬于不同的類。 樣品分類（Q型聚類）常以距離刻畫相似性 變量分類(R型聚類)常以相似系數(shù)刻畫相似性,距離和相似系數(shù)有著各種不同的定義，而這些定義與變量類型有著非常密切的關(guān)系。 變量可分為定性變量和定量變量。若按測量尺度的不同可以分為： （1）間隔尺度變量：變量用連續(xù)的量來表示，包括定距和定比尺度，如長度、重量、速度、溫度等。 （2）有序尺度變量：變量度量時不用明確的數(shù)量表示，而是用等級來表示，如產(chǎn)品分為一等

4、品、二等品、三等品等有次序關(guān)系。 （3）名義尺度變量：變量用既沒有數(shù)量關(guān)系也沒有次序關(guān)系，只有一些特性狀態(tài)，如性別、職業(yè)、產(chǎn)品的型號等。 對于間隔尺度變量，聚類時數(shù)據(jù)單位往往不同，為為使不同量綱、不同數(shù)量級的數(shù)據(jù)能在一起比較，通常需要先進數(shù)據(jù)變換處理,3.常用的數(shù)據(jù)變換方法,(1) 中心化變換 變換后數(shù)據(jù)的均值為0，而協(xié)差陣不變. (2) 標準化變換 變換后的數(shù)據(jù),每個變量的樣本均值為0,標準差為1, 且標準化變換后的數(shù)據(jù)x*ij與變量的量綱無關(guān). (3) 極差標準化變換 變換后的數(shù)據(jù),每個變量的樣本均值為0,極差為1,變換后的數(shù)據(jù)也是無量綱的量.,(4) 極差正規(guī)化變換(規(guī)格化變換) 變換后

5、的數(shù)據(jù)0 x*ij 1;極差為1,也是無量綱的量. (5) 對數(shù)變換 可將具有指數(shù)特征的數(shù)據(jù)結(jié)構(gòu)化為線性數(shù)據(jù)結(jié)構(gòu).,二、樣品間相似性的度量：距離,設(shè)有n個樣品，每個樣品測有p個指標（變量），原始資料陣為： 每個樣品都可以看成p維空間中的一點，n個樣品就是p維空間中的n個點 第i個樣品與第j個樣品之間的距離記為,1、距離公理：,第i個和第j個樣品之間的距離 滿足如下四個性質(zhì)：,2、常用距離：,（1）明考夫斯基距離(Minkowski distance) 明氏距離有三種特殊形式： （1a）絕對距離（Block距離）:當q=1時,（1b)歐氏距離(Euclidean distance):當q=2時

6、（1c)切比雪夫距離:當 時,缺點:(1) 與各變量的量綱有關(guān); (2) 沒有考慮指標間的相關(guān)性; (3) 沒有考慮各變量方差的不同.如歐氏距離,變差大的變量在距離中的作用(貢獻)就會大,這是不合適的. 合理的方法就是對各變量加權(quán),如用1/s2 作為權(quán)數(shù)可得出“統(tǒng)計距離”:,當各變量的單位不同或測量值范圍相差很大時，不應(yīng)直接采用明氏距離，而應(yīng)先對各變量的數(shù)據(jù)作標準化處理，然后用標準化后的數(shù)據(jù)計算距離。常用的標準化處理： 其中 為第j個變量的樣本均值； 為第j個變量的樣本方差。,（2）蘭氏距離 當 時：,克服量綱的影響,未考慮指標間相關(guān)性的影響,適用于變量之間互不相關(guān)的情形,(3) 斜交空間距離

7、 在m維空間中,為使具有相關(guān)性變量的譜系結(jié)構(gòu)不發(fā)生變形,采用斜交空間距離,即,在數(shù)據(jù)標準化處理下,rkl為變量Xk和Xl之間的相關(guān)系數(shù),（4）馬氏距離,克服量綱的影響,克服指標間相關(guān)性的影響,缺點：協(xié)方差矩陣難以確定,三、變量間相似性的度量：相似系數(shù),相似系數(shù)（或其絕對值）越大，變量之間的相似性程度越高；反之，越低。聚類時，相似的變量歸為一類，不太相似的變量歸為不同的類。 變量 與 的相似系數(shù)用 表示，滿足以下三個條件：,1、夾角余弦,從向量集合的角度所定義的一種測度變量之間親疏程度的相似系數(shù)。設(shè)在n維空間的向量,2、相關(guān)系數(shù),設(shè) 和 是第 和 個變量的觀測值，則二者之間的相似 測度為:,相關(guān)

8、系數(shù)就是對數(shù)據(jù)作中心化或標準化處理后的夾角余弦.,至此，我們可以根據(jù)所選擇的距離構(gòu)成樣本點間的距離表：,2.3 類和類的特征,一、類的定義： 用G表示類，設(shè)G中有n個元素，dij表示元素i與j之間的距離 類的定義： T為一個給定的閾值，若對于任意的i，jG，有dij T，則稱G為一個類。,二、類的特征： 設(shè)類G中有樣品 。n為G內(nèi)的樣品數(shù)。 （1）類均值（或稱為重心） （2）離差、協(xié)方差矩陣,(3)類G的直徑,(4)類的離差平方和 對于聚類前的n個樣品，可以證明： n個樣品總離差平方和聚成k類后各類內(nèi)離差平方 之和類間離差平方和 令T為總離差平方和，Pk為分為K類的類內(nèi)離差平方之和。,其中,2

9、.4 系統(tǒng)聚類法,一、系統(tǒng)聚類法的基本思想和步驟 1.是一種其聚類過程可以用所謂的譜系結(jié)構(gòu)或樹形結(jié)構(gòu)來描繪的方法。事先不用確定分多少類 2.基本思想： 先所有的研究對象各自算作一類，將最“靠近” 的兩個類首先聚類，再將這個新類和其余類中最“靠近”的類合并，每次縮小一類，直至所有的對象都合并為一類為止。,系統(tǒng)聚類法的聚類原則決定于樣品間的距離(或相似系數(shù))及類間距離的定義,類間距離的不同定義就產(chǎn)生了不同的系統(tǒng)聚類分析方法.,幾個記號: 用dij表示樣品X(i)和X(j)之間的距離, 當樣品間的親疏關(guān)系采用相似系數(shù)Cij 時, 令 dij=1-|Cij| (或 d2ij=1-C2ij); 用Dij

10、表示類Gi和Gj間的距離.,3.系統(tǒng)聚類法的基本步驟（以Q型聚類為例）,二、最短距離（Nearest Neighbor),1.含義： 類間距離定義為兩類中距離最近樣品之間的距離。,類Gp與類Gq之間的距離Dpq (d(xi,xj)表示點xi Gp和xj Gq之間的距離),2.應(yīng)用,對5個樣品測量了兩個指標，數(shù)據(jù)如下表： 定義樣品間距離為絕對距離，用最短距離法聚類,根據(jù)并類過程繪制的譜系聚類圖,三、最長距離（Furthest Neighbor）,1.含義： 定義類間距離為兩類中距離最遠的樣品的距離,例題：數(shù)據(jù)如前,四、中間距離法,最長距離,最短距離,中間距離,中間距離法的遞推公式,若在某步聚類中

11、將類p與q合并為類r，則任一類k與新類r的距離： 當=-0.25時，為三角形中線：,五、重心法（Centroid clustering):,含義： 兩類間的距離定義為兩類重心(均值點)之間的的距離,例題：數(shù)據(jù)如前,樣品間距離為歐氏距離時的遞推公式,Gr,Gt,重心法雖有較好的代表性,但并未充分利用各個樣品的信息.比如下面兩組類按重心法類間距離相等,這是不合理的.,六、類平均法(Between-group Linkage),含義：類間距離為所有樣品對間的平均距離。,利用了所有樣品對距離的信息,類與類之間的距離平方為兩類樣品兩兩之間的距離平方的平均,即,類平均法的類間距離：,合并新類的距離遞推公式

12、： 設(shè)某一步將Gp和Gq合并成Gr,它們所包含的樣品個數(shù)分別為np ,nq和nr(nr=np+nq).Gr與其他類Gk的類間距離的遞推公式為,七.離差平方和法 (Wards method ),類似于方差分析的想法，如果類分得恰當，同類內(nèi)的樣品之間的離差平方和應(yīng)較小，而類間的離差平方和應(yīng)當較大。,其中 是由Gp和Gq合并成的Gr類的類內(nèi)離差平方和?？梢宰C明離差平方和法的類間遞推公式為,例題：數(shù)據(jù)如前,八、系統(tǒng)聚類法的軟件實現(xiàn)SPSS,以教材88頁例題1為例，SPSS處理： 1、AnalyzeClassifyHierarchical Cluster 2、把dxbz、czbz、wmbz選入Varia

13、bles 3、若對樣品聚類（Q型聚類）：在Cluster選Cases； 若對變量聚類（R型聚類）則在Cluster選Variables 4、選Plots，再點Dendrogram，則畫出樹狀圖； 若點Icicle，則畫出冰掛圖，其中Orientation中（Vertical為縱向冰掛圖；Horizontal為橫向冰掛圖）。 .,九、 系統(tǒng)聚類法的基本性質(zhì),（一） 單調(diào)性 在聚類分析過程中，并類距離分別為l k（k=1，2，3，）若滿足 ，則稱該聚類方法具有單調(diào)性?？梢宰C明除了重心法和中間距離法之外，其他的系統(tǒng)聚類法均滿足單調(diào)性的條件。,（二）空間的濃縮和擴張,1、定義矩陣的大小 設(shè)同階矩陣D（

14、A）和D（B），如果D（A）的每一個元素 小于D（B）的每一個元素，則記為 。,2、空間的濃縮和擴張 設(shè)有兩種系統(tǒng)聚類法A和B，他們在第i步的距離矩陣分別為Ai和Bi（I=1，2，3），若AiBi ，則稱第一種方法A比第二種方法B使空間擴張，或第二種方法比第一種方法濃縮。,3、方法的比較,D（短） D（平），D（重） D（平）； D（長） D（平）； 當 ，D（變平） D（平）； 當 ，D（變平） D（平）。,1.由適當?shù)拈撝荡_定 介紹系統(tǒng)聚類法的基本步驟時,由譜系聚類圖及臨界值,即可給出分類結(jié)果. 2.根據(jù)數(shù)據(jù)點的散布圖直觀地確定類的個數(shù) 3.根據(jù)譜系圖確定分類個數(shù)的準則 4.根據(jù)統(tǒng)計量確定

15、分類個數(shù),十、確定類個數(shù)的幾種常見方法：,黛米爾曼（Demirmen,1972)提出依據(jù)樹狀結(jié)構(gòu)圖分類的準則：,由 Rk2的定義 可知 , Rk2值越大，也就是Pk/T越小，表示k個類內(nèi)離差平方和之和Pk在總離差平方和T中占的比例越小,這說明k個類區(qū)分得越開. Rk2的值總是在0和1之間，而且Rk2的值總是隨著分類個數(shù)k的減少而變小,十一、聚類效果評價統(tǒng)計量,所以我們只能取合適的K，使得R2足夠大，而K本身較小，且隨著K的增加， R2的增幅不大。,1、Rk2統(tǒng)計量,用于評價聚為K個類的效果。如果聚類的效果好，類間的離差平方和相對于類內(nèi)的離差平方和應(yīng)比較大，所以應(yīng)該取偽F統(tǒng)計量較大而類數(shù)較小的聚

16、類水平。,2.偽F統(tǒng)計量,其中WK和WL分別是類K、L的類內(nèi)離差平方和，BKL是將K和L合并為第M類所增加離差平方和 BKL = WM - WK - WL 為合并導(dǎo)致的類內(nèi)離差平方和的增量。用它評價合并第K和L類的效果，偽 統(tǒng)計量大說明不應(yīng)該合并這兩類，應(yīng)該取合并前的水平。,3.偽 統(tǒng)計量,2.5 非系統(tǒng)聚類法簡介,動態(tài)聚類法:也叫做逐步聚類法、k-均值聚類法、或快速聚類法。事先要確定分多少類,選擇凝聚點,分 類,修改分類,分類是否合理,分類結(jié)束,Yes,No,用一個簡單的例子來說明動態(tài)聚類法的工作過程。例如我們要把圖中的點分成兩類?？焖倬垲惖牟襟E： 1、隨機選取兩個點 和 作為聚核。 2、對

17、于任何點 ，分別計算 3、若 ，則將 劃為第一類，否則劃給第二類。于是得圖（c）的兩個類。,4、分別計算兩個類的重心，則得 和 ，以其為新的聚核，對空間中的點進行重新分類，得到新分類。,（a）空間的群點 (b) 任取兩個聚核,(c) 第一次分類 (d) 求各類中心,(e) 第二次分類,如此疊代下去，直到達到停止疊代的要求（比如，各類最后變化不大了，或者疊代次數(shù)太多了）。 下面用一個例子來做k-均值聚類。,【例】假定我們對A、B、C、D四個樣品分別測量兩個變量和得到結(jié)果見下表 試將以上的樣品聚成兩類。,第一步：按要求取K=2，為了實施K均值法聚類，我們將這些樣品隨意分成兩類，比如（A、B）和（C

18、、D），然后計算這兩個聚類的中心坐標，見下表所示。 表中的中心坐標是通過原始數(shù)據(jù)計算得來的，比如（A、 B）類的， 等等。,第二步：計算某個樣品到各類中心的歐氏平方距離，然后將該樣品分配給最近的一類。對于樣品有變動的類，重新計算它們的中心坐標，為下一步聚類做準備。先計算A到兩個類的平方距離： 由于A到（A、B）的距離小于到（C、D）的距離，因此A不用重新分配。計算B到兩類的平方距離：,由于B到（A、B）的距離大于到（C、D）的距離，因此B要分配給（C、D）類，得到新的聚類是（A）和（B、C、D）。更新中心坐標如下表所示。,第三步：再次檢查每個樣品，以決定是否需要重新分類。計算各樣品到各中心的距離平方，得結(jié)果見下表。 到現(xiàn)在為止，每個樣品都已經(jīng)分配給距離中心最近的類，因此聚類過程到此結(jié)束。最終得到K=2的聚類結(jié)果是A獨自成一類，B、C、D聚成一類。,表 樣品聚類結(jié)果,K-均值聚類SPSS處理： 1、AnalyzeClassifyK-Menas Cluster 2、Variables： 3、Number of Clusters處選擇3（想要分的類數(shù)） 4、如果想要知道每個樣品分到哪類，則選Save