第四章 聚類分析

第四章聚類分析聚類分析(clusteranalysis)是研究分類問題的多元數(shù)據(jù)分析方法。聚類分析有極其廣泛的分類背景。在經(jīng)濟學(xué)中，為了了解不同地區(qū)城鎮(zhèn)居民的收入及消費情況，往往需要劃分不同的類型去研究；在產(chǎn)品質(zhì)量管理中，要根據(jù)各產(chǎn)品的某些重要指標(biāo)而將其分為一等品、二等品等；在生物學(xué)中，要根據(jù)各生物體的綜合特征進行分類；又如在考古學(xué)中，要對某些古生物化石進行科學(xué)的分類，等等．隨著人類社會的發(fā)展與科學(xué)技術(shù)的進步，對分類學(xué)的要求也越來越高。只憑經(jīng)驗或?qū)I(yè)知識對研究對象進行分類，往往很不夠，有時不能進行確切的分類。于是數(shù)學(xué)被引進分類學(xué)中，形成了數(shù)值分類學(xué)。隨著多元數(shù)據(jù)分析方法研究的深入，在數(shù)值分類學(xué)中形成了聚類分析這一分支。聚類分析是多元數(shù)據(jù)分析的重要組成部分?！?.1聚類的目的多元數(shù)據(jù)形成數(shù)據(jù)矩陣，見表4.1。共有n個樣品，p個指標(biāo)x1,x2,…xp。聚類分析有2兩種類型：對樣品聚類或?qū)ψ兞?指標(biāo))聚類。表4.1

數(shù)據(jù)矩陣指標(biāo)樣品

x1

x2…xj

…xp12…i…n

x11

x12…x1j

…x1px21

x22…x1j…x2p……………….

xi1

xi2…xij…xip………………xk1

xk2…xkj…xnp注意：變量(指標(biāo))的選取，取決于聚類的目的。數(shù)據(jù)的類型有間隔尺度、有序尺度和名義尺度，主要討論間隔尺度。聚類分析的基本思想是在樣品之間定義距離，在變量之間定義相似系數(shù),距離或相似系數(shù)代表樣品或變量之間的相似程度。按相似程度的大小,將樣品(或變量)逐一歸類，形成一個表示親疏關(guān)系的聚類圖，依次按照某些要求對樣品(或變量)進行分類。聚類分析的方法很多,如系統(tǒng)聚類法、動態(tài)聚類法、分解法、加入法、模糊聚類法、有序樣品聚類法等，我們重點介紹系統(tǒng)聚類法和快速(動態(tài))聚類法。作為聚類分析的出發(fā)點，先介紹分類統(tǒng)計量—距離與相似系數(shù)。每個樣品可看成p維空間的一個點，n個樣品組成p維空間的n個點。我們自然用各點之間的距離來衡量樣品之間的相似程度（或靠近程度）?！?.2距離和相似系數(shù)定義4.1

設(shè)E是一個點的集合,d.,.是E到[0,∞]的函數(shù),滿足：a.dij≥0，i,jE;b.dij=0

,當(dāng)且僅當(dāng)i=j;d.dijdik+dkj

，i,j,kE。則稱dij為i與j之間的距離。c.dij=dji，i,jE;定義4.1

設(shè)E是一個點的集合,d.,.是E到[0,∞]的函數(shù),滿足：a.dij≥0，i,jE;b.dij=0

,當(dāng)且僅當(dāng)i=j;d.dijdik+dkj

，i,j,kE。則稱dij為i與j之間的距離。c.dij=dji，i,jE;當(dāng)條件加強為d.dijmax{dik,dkj}時，相應(yīng)的距離稱為極端距離。常用的距離是明考斯基(Minkowski)距離當(dāng)q=1,2,∞時分別得到Chebyshev(切比雪夫)

距離歐氏距離絕對距離以上距離與各變量指標(biāo)的量綱有關(guān)，為消除量綱的影響，有時應(yīng)先對數(shù)據(jù)進行標(biāo)準(zhǔn)化，然后用標(biāo)準(zhǔn)化數(shù)據(jù)計算距離。標(biāo)準(zhǔn)化數(shù)據(jù)樣品之間聚類主要用到以上提到的各種距離。樣品聚類通常稱為Q型聚類。在SAS系統(tǒng)中，采用歐氏距離聚類或先將數(shù)據(jù)標(biāo)準(zhǔn)化，再計算歐氏距離進行聚類。

當(dāng)對p個指標(biāo)變量進行聚類時，用相似系數(shù)來衡量變量之間相似程度(或關(guān)聯(lián)性程度)。相似系數(shù)中最常用的是相關(guān)系數(shù)與夾角余弦。變量xi,xj的夾角余弦為

變量xi,xj的相關(guān)系數(shù)為

變量聚類通常稱為R型聚類。有時變量之間也可以用距離來描述他們的接近程度。實際上距離和相似系數(shù)之間可以相互轉(zhuǎn)化。若dij是一個距離，則是相似系數(shù)，若dij是相似系數(shù)，則可令或這樣轉(zhuǎn)換得到的距離不一定符合距離定義，但用它可以實現(xiàn)聚類?！?.3類和類的特征一、類用G表示類。設(shè)G中有k個元素，用i,j等簡示。定義4.2

T為一給定的閾值，如果對任意的i,jG有

dij≤T，則稱G為一個類。定義4.3對閾值T，如果對每個iG有則稱G為一個類。定義4.4對閾值T、V,如果則稱G為一個類。二、類的特征類G的元素用X1,X2,…,Xm表示,m為G內(nèi)的樣品數(shù)(或變量數(shù)),可從不同的角度刻畫G的特征,常用的特征有(1)均值或稱為類G的重心(2)樣本散布陣及協(xié)方差陣(3)G的直徑有多種定義，例如三、類與類之間的距離設(shè)兩個類Gp,Gq分別含有np和nq個樣品，它們之間的距離用D(p,q)表示，下面是一些常用的定義：（1）最短距離法它等于Gp和Gq中最近的兩個樣品的距離。（1）最短距離法（2）最長距離法它等于Gp和Gq中最近的兩個樣品的距離。它等于Gp和Gq中最遠的兩個樣品的距離。（3）重心法它等于兩重心和之間的距離。（5）最小方差法（離差平方和法）它與重心法只差一個常數(shù)倍。離差平方和法是由Ward提出，又稱Ward法。（4）類平均距離法它等于Gp和Gq中任兩個樣品距離的平均。四、類間距離的遞推公式設(shè)類Gr由類Gp,Gq合并所得，則Gr包含nr=np+nq個樣品。我們的問題是：如何由類Gp和Gq計算其他類Gk與Gr之間的距離。即建立類間距離的遞推公式。（1）最短距離法（2）最長距離法（3）類平均距離法

（4）重心法（5）離差平方和法當(dāng)樣品間采用歐氏距離時,則上述類間距離的遞推公式有如下的統(tǒng)一形式:其參數(shù)見下表。這種形式為編程提供了極大方便。

方法pq最短距離法最長距離法類平均法重心法離差平方和法1/21/2np/nrnp/nr(nk+np)/(nk+nr)1/21/2nq/nrnq/nr(nk+nq)/(nk+nr)000pq-nk/(nk+nr)-1/21/2000其參數(shù)見下表。這種形式為編程提供了極大方便?！?.4系統(tǒng)聚類法一、系統(tǒng)聚類法的步驟(A)計算n個樣品兩兩間的距離{dij}，記作D=(dij)；(B)構(gòu)造n個類，每個類只包含一個樣品；(C)合并距離最近的兩類為一新類；(D)計算新類與當(dāng)前各類的距離。若類的個數(shù)等于1，轉(zhuǎn)到步驟(E)，否則回到步驟(C)；(E)畫聚類圖；(F)決定類的個數(shù)和類。每一種類間距離用到上述系統(tǒng)聚類程序中就得到一種系統(tǒng)聚類法。通過一個例子來說明系統(tǒng)聚類法。

例4.1

為研究遼寧、浙江、河南、甘肅、青海5省份1991年城鎮(zhèn)居民生活消費規(guī)律，需要利用調(diào)查資料對這5個省份分類。指標(biāo)變量共8個，含義如下:數(shù)據(jù)如下表。將每個省份的數(shù)據(jù)看成一個樣品，計算樣品之間的歐氏距離矩陣。

x1:人均糧食支出，x2:人均副食支出，

x3:人均煙酒茶支出，

x4:人均其他副食支出，

x5:人均衣著商品支出，

x6:人均日用品支出，

x7:人均燃料支出，x8:人均非商品指出。1991年5省城鎮(zhèn)居民月均消費(單位：元／人)

指標(biāo)省份

x1

x2

x3

x4

x5

x6

x7

x8遼寧浙江河南甘肅青海

7.9039.778.4912.9419.2711.052.0413.297.6850.3711.3513.3019.2514.592.7514.879.4227.938.208.1416.179.421.559.769.1627.989.019.3215.999.101.8211.3510.0628.6410.5210.0516.188.391.9610.81解:

以1,2,3,4,5分別表示遼寧、浙江、河南、甘肅、青海5個省(樣品),計算每兩個樣品之間的歐氏距離。如從而得初始距離矩陣如下：將5個省各看成一類，即Gi={i},i=1,2,3,4,5。有Dij=dij從D(0)看出，d43=2.20最小，故將G3,G4合并成一個新類G6={3，4}。計算G6與G1,G2,G5之間的距離得

{1}{2}{3}{4}{5}{1}{2}{3}{4}{5}D61=min{d31,d41}={13.80,13.12}=13.12D62=min{d32,d42}={24.63,24.06}=24.06D65=min{d35,d45}={3.51,2.21}=2.21(為簡單記Ds(p,q)為Dpq)從而得D(1)G6={3,4}{1}{2}{5}{3,4}=G6{1}{2}{5}D61=min{d31,d41}={13.80,13.12}=13.12D62=min{d32,d42}={24.63,24.06}=24.06D65=min{d35,d45}={3.51,2.21}=2.21從D(1)看出，G6到G5的距離2.21為最小，故將G6,G5合并成一個新類G7={G6，G5}。計算G7與G1,G2之間的距離得G6={3,4}{1}{2}{5}{3,4}=G6{1}{2}{5}D71=min{d61,d51}={13.12,12.80}=12.80D72=min{d62,d52}={24.06,23.54}=23.54從D(1)看出，G6到G5的距離2.21為最小，故將G6,G5合并成一個新類G7={G6，G5}。計算G7與G1,G2之間的距離得從而得D(2)G7={3,4,5}{1}{2}{3,4,5}=G7{1}{2}D71=min{d61,d51}={13.12,12.80}=12.80D72=min{d62,d52}={24.06,23.54}=23.54從D(2)看出，G1到G2的距離11.67為最小，故將G1,G2合并成一個新類G8={G1，G2}={1,2}。計算G8與G7之間的距離得從而得D(2)D87=min{d17,d27}={12.80,23.54}=12.80G7={3,4,5}{1,2}=G8{3,4,5}=G7{1,2}=G8最后將G7,G8合并成一類G9={G7,G8}={1,2,3,4,5}。按照上述聚類過程，畫聚類圖。從而得D(3)D87=min{d17,d27}={12.80,23.54}=12.80(1)G6={G3,G4}，距離=2.20；(2)G7={G6,G5}，距離=2.21；(3)G8={G1,G2}，距離=11.67;(4)G9={G7,G8}，距離=12.80。(1)G6={G3,G4}，距離=2.20；(2)G7={G6,G5}，距離=2.21；(3)G8={G1,G2}，距離=11.67;(4)G9={G7,G8}，距離=12.80。1遼寧2浙江3河南4甘肅5青海02468101214距離同理，可用最長距離法進行聚類，可作為練習(xí)。系統(tǒng)聚類可用SAS過程cluster來實現(xiàn)。上例的SAS程序如下：dataex4_1;inputprovince$x1-x8;cards;遼寧7.9039.778.4912.9419.2711.052.0413.29浙江7.6850.3711.3513.3019.2514.592.7514.87河南9.4227.938.208.1416.179.421.559.76甘肅9.1627.989.019.3215.999.101.8211.35青海10.0628.6410.5210.0516.188.391.9610.81;procclustermethod=sinnonormouttree=ex4_1t;varx1-x8;idprovince;proctreedata=ex4_1thorizontal;idprovince;run;過程步說明：procclustermethod=sinnonormouttree=ex4_1t;varx1-x8;idprovince;proctreedata=ex4_1thorizontal;idprovince;run;method=聚類方法；ave—

類平均法；cen—

重心法;com—最長距離法;sin—最短距離法;war—

Ward法。nonorm—數(shù)據(jù)不變換；std—對數(shù)據(jù)標(biāo)準(zhǔn)化變換。outtree=數(shù)據(jù)集名，畫聚類圖時使用。id樣品變量名。tree畫聚類圖過程；horizontal畫水平聚類圖，缺省為垂直聚類圖。輸出結(jié)果：（1）聚類過程（2）聚類圖(sin最短距離法)（2）聚類圖(com最長距離法)（2）聚類圖(ave類平均法)（2）聚類圖(cen重心法)（2）聚類圖(ward離差平方和法)聚類方法不同，聚類結(jié)果也不盡相同。二、系統(tǒng)聚類法的統(tǒng)計量聚類分析中，分多少類合適，是我們關(guān)心的問題。一個較好的聚類應(yīng)該是類內(nèi)各樣品盡可能相似，類間差異較大。下面介紹幾種有助于分類的統(tǒng)計量。Sk越小，說明Gk中各樣品越相似。記設(shè)在某水平上分為G個類，類Gk中樣品的類內(nèi)離差平方和為1.R2統(tǒng)計量類內(nèi)離差平方和為1.R2統(tǒng)計量總離差平方和為則R2統(tǒng)計量為R2=1-PG/T顯然0R21則R2統(tǒng)計量為R2=1-PG/T顯然0R21當(dāng)n個樣品各自為一類時，R2=1；當(dāng)n個樣品合并成一類時，R2=0。

R2的值隨分類個數(shù)的減少而減小，當(dāng)R2由平緩減小到“突變”減小時的G，G即為分類個數(shù)的參考值。設(shè)類Gp，Gq的離差平方和分別為2.半偏相關(guān)統(tǒng)計量設(shè)類Gp，Gq的離差平方和分別為2.半偏相關(guān)統(tǒng)計量將Gp，Gq合并成Gr后的離差平方和為合并后離差平方和的增加量為Wpq=Sr-Sp-Sq由類Gp,Gq合并成Gr時半偏相關(guān)統(tǒng)計量SPRSQ為SPRSQ=Wpq/T當(dāng)SPRSQ值越大時，說明上一次合并效果越好。偽F統(tǒng)計量PSF是3.偽F統(tǒng)計量PSF值越大，表示這些樣品可顯著地分為G類。偽t2

統(tǒng)計量PST2是PST2值越大，表示上一次聚類效果越好。4.偽t2統(tǒng)計量例4.2

山東省2000年17地市農(nóng)村居民和城鎮(zhèn)居民消費水平如下表，試對17個地市進行分類。表42000年17地市居民消費水平(絕對額，單位：元）資料來源：《山東省統(tǒng)計年鑒》，2001序號地農(nóng)村居城鎮(zhèn)居區(qū)民(x1)民(x2)序號地農(nóng)村居城鎮(zhèn)居區(qū)民(x1)民(x2)123456789濟南市22988182青島市26417983淄博市25855333棗莊市26085172東營市20858171煙臺市32297173濰坊市23256590濟寧市19064906泰安市209465641011121314151617威海市29527734日照市21655258萊蕪市21125629臨沂市16894593德州市11574218聊城市12974371濱州市22685267菏澤市12573310dataex4_2;inputgroup$x1-x2;cards;濟南市22988182青島市26417983…………菏澤市12573310;procclustermethod=avestdrsqpseudoouttree=ex4_2t;varx1-x2;idgroup;run;proctreedata=ex4_2thorizontal;idgroup;run;rsq—R2統(tǒng)計量和半偏相關(guān)統(tǒng)計量SPRSQ；pseudo—偽F統(tǒng)計量和偽t2統(tǒng)計量。解SAS程序如下：輸出結(jié)果：類平均法聚類統(tǒng)計量從R2(RSQ)看，從2類至1類下降最大(0.578~0.000),又G=1時，SPRSQ達最大，說明分2類合適。類平均法聚類圖§4.4

快速聚類法系統(tǒng)聚類法的缺點是計算量大。所以產(chǎn)生了快速聚類法，也稱動態(tài)聚類法。目前在數(shù)據(jù)挖掘中應(yīng)用較為廣泛。快速聚類法先將樣品粗略地分一下類，然后按照某種原則進行調(diào)整，直至分類比較合理為止。動態(tài)聚類框圖如下：選擇聚點初始分類分類是否合理最終分類修改分類合理不合理動態(tài)聚類法要先給定分類數(shù)k，選擇k個聚點(種子)，即有代表性的樣品。選擇聚點(初始聚點)的方法有：

(1)經(jīng)驗選擇。(2)將n個樣品隨機分為k類，每類的重心作為聚點。

(3)最小最大原則。（略）

SAS系統(tǒng)的fastclus過程中，分類數(shù)k給定后，種子自動確定。然后按照一定的規(guī)則（略）進行聚類。例4.3

從12個不同地區(qū)測得了某樹種的平均發(fā)芽率x1與發(fā)芽勢x2，數(shù)據(jù)見下表，距離采用歐氏距離，將12個地區(qū)用快速聚類法聚為2類。例4.3

從12個不同地區(qū)測得了某樹種的平均發(fā)芽率x1與發(fā)芽勢x2，數(shù)據(jù)見下表，距離采用歐氏距離，將12個地區(qū)用快速聚類法聚為2類。地區(qū)

x1

x2