系統(tǒng)工程第6講系統(tǒng)模型化之聚類分析

1第六講

聚類分析法

聚類分析是研究分類問題的一種多元統(tǒng)計方法。所謂類，就是指相似元素的集合聚類分析的研究目的

把相似的東西歸成類，根據(jù)相似的程度將研究目標(biāo)進行分類?！?什么是聚類分析聚類分析的研究對象R型分析----對變量進行分類Q型分析----對樣品進行分類聚類分析研究的主要內(nèi)容如何度量事物之間的相似性?怎樣構(gòu)造聚類的具體方法以達(dá)到分類的目的?

例對10位應(yīng)聘者做智能檢驗。3項指標(biāo)X、Y和Z分別表示數(shù)學(xué)推理能力、空間想象能力和語言理解能力。其得分如下，選擇合適的統(tǒng)計方法對應(yīng)聘者進行分類。應(yīng)聘者12345678910X28181121262016142422Y29232223292322232927Z28181622262222242424我們的問題是如何來選擇樣品間相似性的測度指標(biāo)，如何將相似的類連接起來？一、相似性的測度

距離：測度樣品之間的親疏程度。將每一個樣品看作p維空間的一個點，并用某種度量測量點與點之間的距離，距離較近的歸為一類，距離較遠(yuǎn)的點應(yīng)屬于不同的類。相似系數(shù)：測度變量之間的親疏程度§2距離和相似系數(shù)2、常用的距離明氏距離特別地，當(dāng)k＝1時，即為絕對值距離(1)明氏距離令表示樣品與的距離

設(shè)原始數(shù)據(jù)為明氏距離當(dāng)k＝2時，即為歐氏距離當(dāng)k＝∞時，即為切比雪夫距離明考夫斯基距離有以下兩個缺點：①明氏距離的數(shù)值與指標(biāo)的量綱有關(guān)。當(dāng)各變量的測量值相差懸殊時，常發(fā)生“大數(shù)吃小數(shù)”的現(xiàn)象，為消除量綱的影響，通常先將每個變量進行標(biāo)準(zhǔn)化。②明氏距離的定義沒有考慮各個變量之間相關(guān)性的影響。年齡收入家庭人口數(shù)甲3030001乙4032003(2)標(biāo)準(zhǔn)化的歐氏距離設(shè)原始數(shù)據(jù)為

(3)馬氏距離由印度著名統(tǒng)計學(xué)家馬哈拉諾比斯(Mahalanobis)所定義的一種距離，其計算公式為：

=馬氏距離又稱為廣義歐氏距離。馬氏距離考慮了觀測變量之間的相關(guān)性。如果假定各變量之間相互獨立，即觀測變量的協(xié)方差矩陣是對角矩陣，此時馬氏距離就是標(biāo)準(zhǔn)化的歐氏距離。馬氏距離不受指標(biāo)量綱及指標(biāo)間相關(guān)性的影響

二、變量間相似系數(shù)的算法變量和的相關(guān)系數(shù)：

（2）夾角余弦（1）相關(guān)系數(shù)系統(tǒng)聚類法直觀，易懂。快速聚類法（動態(tài)聚類法）快速，動態(tài)。有序聚類法保序(時間順序或大小順序)。各種聚類方法§3

系統(tǒng)聚類法系統(tǒng)聚類法的基本思想

先將n個樣品各自看成一類，然后規(guī)定樣品之間的“距離”和類與類之間的距離。選擇距離最近的兩類合并成一個新類，計算新類和其它類（各當(dāng)前類）的距離，再將距離最近的兩類合并。這樣，每次合并減少一類，直至所有的樣品都?xì)w成一類為止。系統(tǒng)聚類法的基本步驟：1.

計算n個樣品兩兩間的距離，記作D=。2.

構(gòu)造n個類，每個類只包含一個樣品。3.

合并距離最近的兩類為一新類。4.

計算新類與各當(dāng)前類的距離。5.

重復(fù)步驟3、4，合并距離最近的兩類為新類，直到所有的類并為一類為止。6.

畫聚類譜系圖。7.

決定類的個數(shù)和類。

最短距離法最長距離法中間距離法重心法類平均法

離差平方和法（Ward法）系統(tǒng)聚類方法：

上述6種方法歸類的基本步驟一致，只是類與類之間的距離有不同的定義。定義類p與q之間的距離為兩類最近樣品的距離，即xq1?xp2?xq2?xp1?xq3?一、最短距離法設(shè)類p與q合并成一個新類，記為k，則k與任一類r的距離是pqkr例

最短距離法

設(shè)抽取5個樣品，每個樣品觀察2個指標(biāo)，：您每月大約喝多少瓶啤酒，：您對“飲酒是人生的快樂”這句話的看法如何？觀察數(shù)據(jù)如下，對這5個樣品分類。1234520181044710553

②③④⑤①②③④3.610.216.1216.499.4314.8715.6566.32

2計算5個樣品兩兩之間的距離記為距離矩陣（采用歐氏距離），2.合并距離最小的兩類為新類，按順序定為第６類。⑥＝3、計算新類⑥與各當(dāng)前類的距離，得距離矩陣如下：②③⑥①②③

3.6

10.216.129.4314.876為最小，⑦=⑥⑦③⑥

6

9.4314.874、重復(fù)步驟2、3，合并距離最近的兩類為新類，直到所有的類并為一類為止。

為最小，⑧=5、6、按聚類的過程畫聚類譜系圖45⑥⑨⑧并類距離312⑦7、決定類的個數(shù)與類。

觀察此圖，我們可以把5個樣品分為3類，、、。???x11?x21????二、最長距離法定義類p與q之間的距離為兩類最遠(yuǎn)樣品的距離，即設(shè)類p與q合并成一個新類，記為k，則k與任一類r的距離是pqkr三、中間距離法定義類與類之間的距離既不采用兩類之間最近的距離，也不采用兩類之間最遠(yuǎn)的距離，而是采用介于兩者之間的距離，故稱為中間距離法。???rpqk四、重心法（Centroid)??和類與類之間的距離就考慮用重心之間的距離表示。設(shè)p與q的重心分別是，則類p和q的距離為將p和q合并為k，則k類的樣品個數(shù)為它的重心是某一類r的重心是，它與新類k的距離是經(jīng)推導(dǎo)可以得到如下遞推公式：設(shè)聚類到某一步，類p與q分別有樣品

、個，五、類平均法（Average)定義兩類之間的距離平方為這兩類元素兩兩之間距離平方的平均?????pq將p和q合并為k，則k類的樣品個數(shù)為設(shè)聚類到某一步，類p與q分別有樣品、個，k類與任一類r的距離為六、差平方和法（Ward法）

反映樣品之間的差異程度設(shè)變量X的n個樣品觀察值為：n個樣品的離差平方和為：???????????q?????????????pk設(shè)類p和q分別含有np、nq個樣品，其離差平方和分別記為和直觀上容易想到把兩群樣品聚為一大群，大群的離差平方和將超過原來兩個群的離差平方和之和。

如果將p和q并類得到新類k，則類k的離差平方和為把增加的量記為定義類p和q之間的距離為：設(shè)類p和q分別含有np、nq個樣品，其離差平方和分別記為和可以推得新類k與任一類r的距離：

②③④⑤①②③④6.55213013644.5110.5122.51820

2計算5個樣品兩兩之間的距離記為距離矩陣（采用歐氏距離），2.合并距離最小的兩類為新類，按順序定為第６類。⑥＝例離差平方和法（Ward法）

兩樣品間的距離的平方恰為它們之間歐氏距離平方的一半。3、計算新類⑥與各當(dāng)前類的距離，得距離矩陣如下：②③⑥①②③

6.5

52176.6744.5154.6724.67為最小，⑦=⑥⑦③⑥

24.67

62.17245.264、重復(fù)步驟2、3，合并距離最近的兩類為新類，直到所有的類并為一類為止。

為最小，⑧=5、6、按聚類的過程畫聚類譜系圖45⑥⑨⑧并類距離312⑦7、決定類的個數(shù)與類。

觀察此圖，我們可以把5個樣品分為3類，、、。最短距離法最長距離法中間距離法重心法類平均法離差平方和法Procclustermethod=選項

data=文件名outtree=文件名1

standard;varvariable-list;idvariable;run;Proctreedata=文件名1

horizontalgraphics;idvariable;run;Method＝選項single最短距離法complete最長距離法median中間距離法centroid重心法average類平均法ward離差平方和法（Ward法）SAS程序聚類分析案例

為了解我國城鎮(zhèn)居民的生活質(zhì)量，對全國各地區(qū)（除內(nèi)蒙古和西藏）進行聚類分析。選用了4個指標(biāo)：X1：全年人均消費支出X2：全年人均可支配收入X3：人均居住面積X4：人均公共綠地面積甘肅青海陜西河南吉林江西黑龍江寧夏山西重慶福建云南江蘇四川廣西湖南山東湖北海南安徽貴州遼寧新疆河北浙江天津廣東上海北京MedianDistance012由聚類譜系圖，29個地區(qū)可分四類：

第一類：｛北京、上海、廣東｝，生活質(zhì)量好。第二類：｛浙江、天津｝，生活質(zhì)量較好。第三類：｛河北、新疆、遼寧、貴州、安徽、海南、湖北、江蘇、云南、福建、山東、湖南、廣西、四川、重慶｝，生活質(zhì)量一般。第四類：｛山西、寧夏、黑龍江、江西、吉林、河南、陜西、青海、甘肅｝，生活質(zhì)量差。重慶四川廣西湖南山東福建云南江蘇甘肅青海陜西河南吉林江西黑龍江寧夏山西湖北海南安徽貴州遼寧新疆河北浙江天津廣東上海北京DistanceBetweenClusterCentroids01229個地區(qū)可分為四類：第一類：｛北京、上海、廣東｝，生活質(zhì)量好。第二類：｛浙江、天津｝，生活質(zhì)量較好。第三類：｛江蘇、云南、福建、山東、湖南、廣西、四川、重慶｝，生活質(zhì)量一般。第四類：｛河北、新疆、遼寧、貴州、安徽、海南、湖北、山西、寧夏、黑龍江、江西、吉林、河南、陜西、青海、甘肅｝，生活質(zhì)量差

29個地區(qū)可分為四類：第一類：｛北京、上海、廣東｝，生活質(zhì)量好。第二類：｛浙江、天津｝，生活質(zhì)量較好。第三類：｛江蘇、云南、福建、山東、湖南、廣西、四川、重慶｝，生活質(zhì)量一般。第四類：｛河北、新疆、遼寧、貴州、安徽、海南、湖北、山西、寧夏、黑龍江、江西、吉林、河南、陜西、青海、甘肅｝，生活質(zhì)量差

綜合以上分析結(jié)果和實際情況，29個地區(qū)城鎮(zhèn)居民的生活質(zhì)量分為五類比較合適：第一類：｛北京、上海、廣東｝，生活質(zhì)量好。第二類：｛浙江、天津｝，生活質(zhì)量較好。第三類：｛江蘇、云南、福建、山東、湖南、廣西、四川、重慶｝，生活質(zhì)量一般。第四類：｛河北、新疆、遼寧、貴州、安徽、海南、湖北｝，生活質(zhì)量較差。第五類：｛山西、寧夏、黑龍江、江西、吉林、河南、陜西、青海、甘肅｝，生活質(zhì)量差。

根據(jù)美國等20個國家和地區(qū)的信息基礎(chǔ)設(shè)施的發(fā)展?fàn)顩r進行分類。Call—每千人擁有的電話線數(shù)；movecall—每千人戶居民擁有的蜂窩移動電話數(shù)；fee—高峰時期每三分鐘國際電話的成本；computer—每千人擁有的計算機數(shù)；mips—每千人計算機功率（每秒百萬指令）；net—每千人互聯(lián)網(wǎng)絡(luò)戶主數(shù)。

數(shù)據(jù)摘自《世界競爭力報告——1997》數(shù)據(jù)見sasuser.cluli01第Ⅰ類：美國、瑞典、丹麥，發(fā)達(dá)國家，信息基礎(chǔ)設(shè)施發(fā)展良好第Ⅱ類：日本、中國臺灣、韓國、德國、法國、瑞士、新加坡、英國，新興工業(yè)化國家，信息基礎(chǔ)設(shè)施發(fā)展較好第Ⅲ類：巴西、墨西哥、波蘭、匈牙利、馬來西亞、智利、俄羅斯、泰國、印度，發(fā)展中國家，基礎(chǔ)設(shè)施薄弱某公司下屬30個企業(yè)，公司為了考核下屬企業(yè)的經(jīng)濟效益，設(shè)計了8個指標(biāo)。為了避免重復(fù)，需要對這8個指標(biāo)進行篩選，建立一個恰當(dāng)?shù)慕?jīng)濟效益指標(biāo)體系。通過計算30個企業(yè)8個指標(biāo)的相關(guān)系數(shù)距離，數(shù)據(jù)是1-r2。得如下表:

x1x2

x3

x4x5

x6

x7

x8

x10

0.600

0.430.460

0.470.450.120

0.570.450.230.220

0.380.400.210.290.220

0.310.790.650.700.800.660

0.450.450.270.230.140.190.770

試將它們聚類。x2

x3x4x5

x6

x7

x8對變量聚類動態(tài)聚類法

系統(tǒng)聚類法是一種比較成功的聚類方法。然而當(dāng)樣本點數(shù)量十分龐大時，則是一件非常繁重的工作，且聚類的計算速度也比較慢。比如在市場抽樣調(diào)查中，有4萬人就其對衣著的偏好作了回答，希望能迅速將他們分為幾類。這時，采用系統(tǒng)聚類法就很困難，而動態(tài)聚類法就會顯得方便，適用。動態(tài)聚類使用于大型數(shù)據(jù)。動態(tài)聚類法

基本思想：選取若干個樣品作為凝聚點，計算每個樣品和凝聚點的距離，進行初始分類，然后根據(jù)初始分類計算其重心，再進行第二次分類，一直到所有樣品不再調(diào)整為止。選擇凝聚點分類修改分類分類是否合理分類結(jié)束YesNo

用一個簡單的例子來說明動態(tài)聚類法的工作過程。例如我們要把圖中的點分成兩類?？焖倬垲惖牟襟E：

1、隨機選取兩個點和作為凝聚點。

2、對于任何點，分別計算

3、若，則將劃為第一類，否則劃給第二類。于是得圖（b）的兩個類。4、分別計算兩個類的重心，則得和，以其為新的凝聚點，對空間中的點進行重新分類，得到新分類。

(b)任取兩個凝聚點(c)第一次分類(d)求各類中心

（a）空間的群點(e)第二次分類動態(tài)聚類法

優(yōu)點：計算量小，方法簡便，可以根據(jù)經(jīng)驗，先作主觀分類。缺點：結(jié)果受選擇凝聚點好壞的影響，分類結(jié)果不穩(wěn)定。選擇凝聚點和確定初始分類

凝聚點就是一批有代表性的點，是欲形成類的中心。凝聚點的選擇直接決定初始分類，對分類結(jié)果也有很大的影響，由于凝聚點的不同選擇，其最終分類結(jié)果也將出現(xiàn)不同。故選擇時要慎重．通常選擇凝聚點的方法有：

(1)人為選擇，當(dāng)人們對所欲分類的問題有一定了解時，根據(jù)經(jīng)驗，預(yù)先確定分類個數(shù)和初始分類，并從每一類中選擇一個有代表性的樣品作為凝聚點。

(2)重心法將數(shù)據(jù)人為地分為A類，計算每一類的重心，將重心作為凝聚點。(3)密度法以某個正數(shù)d為半徑，以每個樣品為球心，落在這個球內(nèi)的樣品數(shù)(不包括作為球心的樣品)稱為這個樣品的密度。計算所有樣品點的密度后，首先選擇密度最大的樣品為第一凝聚點。然后選出密度次大的樣品點，若它與第一個凝聚點的距離大于2d