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

1第六講

聚類分析法

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

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

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

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

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

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

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

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

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

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

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

計(jì)算n個(gè)樣品兩兩間的距離，記作D=。2.

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

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

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

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

畫聚類譜系圖。7.

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

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

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

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

最短距離法

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

②③④⑤①②③④3.610.216.1216.499.4314.8715.6566.32

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

3.6

10.216.129.4314.876為最小，⑦=⑥⑦③⑥

6

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

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

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

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

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

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

②③④⑤①②③④6.55213013644.5110.5122.51820

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

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

6.5

52176.6744.5154.6724.67為最小，⑦=⑥⑦③⑥

24.67

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

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

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

data=文件名outtree=文件名1

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

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

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

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

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

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

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

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

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

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

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

1、隨機(jī)選取兩個(gè)點(diǎn)和作為凝聚點(diǎn)。

2、對(duì)于任何點(diǎn)，分別計(jì)算

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

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

（a）空間的群點(diǎn)(e)第二次分類動(dòng)態(tài)聚類法

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

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

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

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