聚類分析在數(shù)學(xué)建模中的應(yīng)用

1、聚類分析,聚類分析是研究分類問題的一種多元統(tǒng)計(jì)方法。所謂類，就是指相似元素的集合 聚類分析的研究目的,把相似的東西歸成類，根據(jù)相似的程度將研究目標(biāo)進(jìn)行分類。,一、什么是聚類分析,聚類分析的研究對(duì)象 R型分析-對(duì)變量（指標(biāo)）進(jìn)行分類 Q型分析-對(duì)樣品進(jìn)行分類 聚類分析研究的主要內(nèi)容 如何度量事物之間的相似性? 怎樣構(gòu)造聚類的具體方法以達(dá)到分類的目的?,1、相似性的測度,距離：測度樣品之間的親疏程度。將每一個(gè)樣品看作 維空間的一個(gè)點(diǎn)，并用某種度量測量點(diǎn)與點(diǎn)之間的距離，距離較近的歸為一類，距離較遠(yuǎn)的點(diǎn)應(yīng)屬于不同的類。 相似系數(shù)：測度變量之間的親疏程度。,二、距離和相似系數(shù),2、常用的距離,Minko

2、wski距離,特別地，當(dāng)m1時(shí)，即為絕對(duì)值距離,(1) Minkowski距離,設(shè)原始數(shù)據(jù)為,當(dāng)m2時(shí)，即為歐氏距離,當(dāng) 時(shí)，即為切比雪夫距離,Minkowski距離,歐氏距離,切比雪夫距離,Minkowski距離有兩個(gè)缺點(diǎn)：,明氏距離的數(shù)值與指標(biāo)的量綱有關(guān)。當(dāng)各變量的測量值相差懸殊時(shí)，常發(fā)生“大數(shù)吃小數(shù)”的現(xiàn)象，為消除量綱的影響，通常先將每個(gè)變量進(jìn)行標(biāo)準(zhǔn)化。 明氏距離的定義沒有考慮各個(gè)變量之間相關(guān)性的影響。,(2) 方差加權(quán)距離（標(biāo)準(zhǔn)化的歐氏距離）,設(shè)原始數(shù)據(jù)為,標(biāo)準(zhǔn)化數(shù)據(jù),其中，,標(biāo)準(zhǔn)化數(shù)據(jù),(3)馬氏距離 由印度著名統(tǒng)計(jì)學(xué)家馬哈拉諾比斯(Mahalanobis)所定義的一種距離，其計(jì)算公

3、式為：,=,其中，S是協(xié)方差矩陣：,馬氏距離又稱為廣義歐氏距離。 馬氏距離考慮了觀測變量之間的相關(guān)性。如果假定各變量之間相互獨(dú)立，即觀測變量的協(xié)方差矩陣是對(duì)角矩陣，此時(shí)馬氏距離就是標(biāo)準(zhǔn)化的歐氏距離。 馬氏距離不受指標(biāo)量綱及指標(biāo)間相關(guān)性的影響,二、變量間相似系數(shù)的算法,（2）夾角余弦,（1）相關(guān)系數(shù),系統(tǒng)聚類法 直觀，易懂。 快速聚類法（動(dòng)態(tài)聚類法） 快速，動(dòng)態(tài)。 有序聚類法 保序(時(shí)間順序或大小順序)。,各種聚類方法,三、系統(tǒng)聚類法,系統(tǒng)聚類法的基本思想 先將n個(gè)樣品各自看成一類，然后規(guī)定樣品之間的“距離”和類與類之間的距離。選擇距離最近的兩類合并成一個(gè)新類，計(jì)算新類和其它類（各當(dāng)前類）的距離

4、，再將距離最近的兩類合并。這樣，每次合并減少一類，直至所有的樣品都?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 種方法歸類的基本步驟一致，只是類與類之間的距離有不同的定義。,最短距離法,最長距離法,中間距離法,重心距離法

5、,類平均距離法,離差平方和距離法,例 最短距離法,設(shè)抽取5個(gè)樣品，每個(gè)樣品觀察2個(gè)指標(biāo) ， ：您每月大約喝多少瓶啤酒， ：您對(duì)“飲酒是人生的快樂”這句話的看法如何？觀察數(shù)據(jù)如下，對(duì)這5個(gè)樣品分類。,2. 合并距離最小的兩類為新類，按順序定為第類。,3、計(jì)算新類與各當(dāng)前類的距離，,得距離矩陣如下：,為最小， =,4、重復(fù)步驟2、3，合并距離最近的兩類為新類，直到所有的類并為一類為止。,6、按聚類的過程畫聚類譜系圖,4,5,并類距離,3,1,2,7、決定類的個(gè)數(shù)與類。,觀察此圖，我們可以把5個(gè)樣品分為3類，,動(dòng)態(tài)聚類法,系統(tǒng)聚類法是一種比較成功的聚類方法。然而當(dāng)樣本點(diǎn)數(shù)量十分龐大時(shí)，則是一件非常繁

6、重的工作，且聚類的計(jì)算速度也比較慢。比如在市場抽樣調(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é)束,Yes,No,用一個(gè)簡單的例子來說明動(dòng)態(tài)聚類法的工作過程。例如我們要把圖中的點(diǎn)分成兩類。快速聚類的步驟： 1、隨機(jī)選取兩個(gè)點(diǎn) 和 作為凝聚點(diǎn)。 2、對(duì)于任何點(diǎn) ，分別計(jì)算

7、3、若 ，則將 劃為第一類，否則劃給第二類。于是得圖（b）的兩個(gè)類。,4、分別計(jì)算兩個(gè)類的重心，則得 和 ，以其為新的凝聚點(diǎn)，對(duì)空間中的點(diǎn)進(jìn)行重新分類，得到新分類。,(b) 任取兩個(gè)凝聚點(diǎn),（a）空間的群點(diǎn),(e) 第二次分類,動(dòng)態(tài)聚類法,優(yōu)點(diǎn)：計(jì)算量小，方法簡便，可以根據(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ì)所

8、欲分類的問題有一定了解時(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 ，則將其作為第二個(gè)凝聚點(diǎn)；否則舍去這點(diǎn)。這樣，按密度由大到小依次考查，直至全部樣品考查完畢為止此方法中，d要給得合適，太大了使凝聚點(diǎn)個(gè)數(shù)太 少，太小了使凝聚點(diǎn)個(gè)數(shù)太多。,(

9、4) 人為地選擇一正數(shù)d，首先以所有樣品的均值作為第一凝聚點(diǎn)。然后依次考察每個(gè)樣品，若某樣品與已選定的凝聚點(diǎn)的距 離均大于d，該樣品作為新的凝聚點(diǎn)，否則考察下一個(gè)樣品。,第一，選擇凝聚點(diǎn)； 第二，初始分類； 對(duì)于取定的凝聚點(diǎn)，視每個(gè)凝聚點(diǎn)為一類，將每個(gè)樣品根據(jù)定義的距離向最近的凝聚點(diǎn)歸類。 第三，修改分類 得到初始分類，計(jì)算各類的重心，以這些重心作為新的凝聚點(diǎn)，重新進(jìn)行分類，重復(fù)步驟2，3，直到分類的結(jié)果與上一步的分類結(jié)果相同，表明分類已經(jīng)合理為止。,動(dòng)態(tài)聚類法的基本步驟：,例1：某商店5位售貨員的銷售量和教育程度如下表：,對(duì)這5位售貨員分類。,選擇凝聚點(diǎn),1,為最大?？蛇x擇2和5作為凝聚點(diǎn)。

10、,計(jì)算各樣品點(diǎn)兩兩之間的距離，得到如下的距離矩陣,對(duì)于取定的凝聚點(diǎn)，視每個(gè)凝聚點(diǎn)為一類，將每個(gè)樣品根據(jù)定義的距離，向最近的凝聚點(diǎn)歸類。,1,得到初始分類為：,：,：,2.初始分類,計(jì)算G1和G2的重心：G1的重心（1,1.5）， G2的重心（7.33,1.67）,3.修改分類,以這兩個(gè)重心點(diǎn)作為凝聚點(diǎn)，再按最小距離原則重新聚類,修改前后所分的類相同，故可停止修改。,聚類分析的Matlab 程序系統(tǒng)聚類,(1)計(jì)算數(shù)據(jù)集每對(duì)元素之間的距離,對(duì)應(yīng)函數(shù)為pdistw. 調(diào)用格式：Y=pdist(X),Y=pdist(X,metric), Y=pdist(X,distfun),Y=pdist(X,mi

11、nkowski,p) 說明：X是m*n的矩陣，metric是計(jì)算距離的方法選項(xiàng)：metric=euclidean表示歐式距離（缺省值）； metric=seuclidean表示標(biāo)準(zhǔn)的歐式距離； metric=mahalanobis表示馬氏距離。 distfun是自定義的距離函數(shù)，p是minkowski距離計(jì)算過程中的冪次，缺省值為2.Y返回大小為m(m-1)/2的距離矩陣，距離排序順序?yàn)?1,2),(1,3),(m-1,m)，Y也稱為相似矩陣，可用squareform將其轉(zhuǎn)化為方陣。,（2）對(duì)元素進(jìn)行分類，構(gòu)成一個(gè)系統(tǒng)聚類樹，對(duì)應(yīng)函數(shù)為linkage. 調(diào)用格式：Z=linkage(Y),Z=

12、linkage(Y,method) 說明：Y是距離函數(shù)，Z是返回系統(tǒng)聚類樹，method是采用的算法選項(xiàng)，如下：method=single表示最短距離(缺省值)； complete表示最長距離；median表示中間距離法；centroid表示重心法；average表示類平均法；ward 表示離差平方和法（Ward法）。,（3）確定怎樣劃分系統(tǒng)聚類樹，得到不同的類，對(duì)應(yīng)的函數(shù)為cluster. 調(diào)用格式：T=cluster(Z,cutoff,c),T=cluster(Z,maxclust,n) 說明：Z是系統(tǒng)聚類樹，為(m-1)*3的矩陣，c是閾值，n是類的最大數(shù)目，maxclust是聚類的選項(xiàng)

13、，cutoff是臨界值，決定cluster函數(shù)怎樣聚類。,利用系統(tǒng)聚類法對(duì)5個(gè)變量進(jìn)行分類。,Matlab運(yùn)行程序： X=20,7;18,10;10,5;4,5;4,3; Y=pdist(X); SF=squareform(Y); Z=linkage(Y，single); dendrogram(Z);%顯示系統(tǒng)聚類樹 T=cluster(Z,maxclust,3),例1的程序設(shè)計(jì)： X=1 1;1 2;6 3;8 2;8 0; Y=pdist(X); SF=squareform(Y); Z=linkage(Y,single); dendrogram(Z)； T=cluster(Z,maxclu

14、st,3),聚類分析案例,根據(jù)第三產(chǎn)業(yè)國內(nèi)生產(chǎn)總值的9 項(xiàng)指標(biāo)，對(duì)華東地區(qū)6 省1 市進(jìn)行分類，原始數(shù)據(jù)如下表：,Matlab程序如下： X=244.42 412.04 459.63 512.21 160.45 43.51 89.93 48.55 48.63 435.77 724.85 376.04 381.81 210.39 71.82 150.64 23.74 188.28 321.75 665.80 157.94 172.19 147.16 52.44 78.16 10.90 93.50 152.29 258.60 83.42 85.10 75.74 26.75 63.47 5.89 47.02 347.25 332.59 157.32 172.48 115.16 33.80 77.2