數(shù)學(xué)建模-聚類分析

1、 聚類分析聚類分析分類l物以類聚、人以群分；物以類聚、人以群分；l但根據(jù)什么分類呢？但根據(jù)什么分類呢？l如要想把中國的縣分類，就有多種方法如要想把中國的縣分類，就有多種方法l可以按照自然條件來分，比如考慮降水、土可以按照自然條件來分，比如考慮降水、土地、日照、濕度等，地、日照、濕度等，l也可考慮收入、教育水準(zhǔn)、醫(yī)療條件、基礎(chǔ)也可考慮收入、教育水準(zhǔn)、醫(yī)療條件、基礎(chǔ)設(shè)施等指標(biāo)；設(shè)施等指標(biāo)；l既可以用某一項來分類，也可以同時考慮多既可以用某一項來分類，也可以同時考慮多項指標(biāo)來分類。項指標(biāo)來分類。 l研究對樣品或指標(biāo)進行分類的一種多元統(tǒng)計方法,是依據(jù)研究對象的個體的特征進行分類的方法。l聚類分析把分類

2、對象按一定規(guī)則分成若干類，這些類非事先給定的，而是根據(jù)數(shù)據(jù)特征確定的。在同一類中這些對象在某種意義上趨向于彼此相似，而在不同類中趨向于不相似。 聚類分析的聚類分析的基本思想基本思想是認為我們是認為我們所研究的樣本或指標(biāo)（變量）之間所研究的樣本或指標(biāo)（變量）之間存在著程度不同的相似性（親疏關(guān)存在著程度不同的相似性（親疏關(guān)系）。系）。l根據(jù)事物本身的特性研究個體分類的根據(jù)事物本身的特性研究個體分類的方法，原則是同一類中的個體有較大方法，原則是同一類中的個體有較大的相似性，不同類中的個體差異很大。的相似性，不同類中的個體差異很大。l不一定事先假定有多少類，完全可以不一定事先假定有多少類，完全可以按照

3、數(shù)據(jù)本身的規(guī)律來分類。按照數(shù)據(jù)本身的規(guī)律來分類。l按照遠近程度來聚類需要明確兩個概按照遠近程度來聚類需要明確兩個概念：一個是念：一個是點和點之間點和點之間的距離，一個的距離，一個是是類和類之間類和類之間的距離。的距離。 二、距離和相似系數(shù)二、距離和相似系數(shù) 在進行聚類分析時，樣本間的相似系數(shù)和距離有多種不同的定義，通常按特性來劃分。變量特征的測度尺度有三種類型： 間隔尺度（由連續(xù)的實值變量表示） 有序尺度（沒有明確的數(shù)量表示，只有次序關(guān)系，如產(chǎn)品等級） 名義尺度（具有某種特性，如性別）l從一組復(fù)雜數(shù)據(jù)產(chǎn)生一個相當(dāng)簡單的類結(jié)構(gòu)，必然要求進行“相關(guān)性”或“相似性”的度量。在相似性度量的選擇中，常常

4、包含許多主觀上的考慮，但最重要的考慮是指標(biāo)的性質(zhì)或觀測的尺度（名義、次序、間隔）以及相關(guān)知識。l課堂上主要討論的指標(biāo)測量為間隔尺度的情況。距離距離l每個樣本有p個指標(biāo)，因此每個樣本可以看成p維空間中的一個點，n個樣本就組成p維空間中的n個點，這時很自然想到用距離來度量n個樣本間的接近程度。l用 表示第i個樣本與第j個樣本之間的距離。一切距離應(yīng)滿足以下條件：kjidddjiddjidjidkjikijjiijijij, 0, 0對于一切，對于一切的指標(biāo)相同與樣本等價于樣本對于一切ijd常見的距離有：常見的距離有：lblock distance 絕對值距離絕對值距離：leuclidean dist

5、ance 歐式距離歐式距離lsquared euclidean distance 平方歐式距離平方歐式距離lchebychev distance 切比雪夫距離切比雪夫距離lminkowski distance 明考斯基距離明考斯基距離 （明氏距離）（明氏距離）當(dāng)當(dāng)q=1,2時，為絕對值、歐式距離；時，為絕對值、歐式距離；若趨近無窮時，則為切比雪夫距離若趨近無窮時，則為切比雪夫距離xxMaxjtittdptxxdjtit1ptjtitxxd1221ptjtitxxdptqjtitxxdq11lLanberra 蘭氏距離lMahalanobis 馬氏距離l以上都是樣本間距離的定義。ptjtitjt

6、itijxxxxpLd1)(|1)()()()()()(1)()(jijiijXXSXXMd相似系數(shù)相似系數(shù)l夾角余弦l相關(guān)系數(shù)l變量間的距離l利用相似系數(shù)來定義距離l利用樣本協(xié)差陣來定義距離l把變量Xi的n次觀測值看成n維空間的點,在n維空間中定義m個變量間的距離。l 夾角余弦 兩變量的夾角余弦定義為： l 相關(guān)系數(shù) 兩變量的相關(guān)系數(shù)定義為： 把樣本看成把樣本看成n維空間的點，而把變量看成維空間的點，而把變量看成n維空間的坐標(biāo)軸，維空間的坐標(biāo)軸，m個樣本開始時自成一類，個樣本開始時自成一類，然后規(guī)定各類之間的距離，將距離最小的一對然后規(guī)定各類之間的距離，將距離最小的一對并成一類，然后再計算距

7、離，直到所有單位全并成一類，然后再計算距離，直到所有單位全部合并為止。部合并為止。系統(tǒng)聚類法l根據(jù)一批樣本的多個觀測指標(biāo)，具體找出一些彼此之根據(jù)一批樣本的多個觀測指標(biāo)，具體找出一些彼此之間相似程度較大的樣本（或指標(biāo)）聚合為一類，把另間相似程度較大的樣本（或指標(biāo)）聚合為一類，把另外一些彼此之間相似程度較大的樣本（或指標(biāo)）又聚外一些彼此之間相似程度較大的樣本（或指標(biāo)）又聚合為另一類，關(guān)系密切的聚合到一個小的分類單位，合為另一類，關(guān)系密切的聚合到一個小的分類單位，關(guān)系疏遠的聚合到一個大的分類單位，直到把所有樣關(guān)系疏遠的聚合到一個大的分類單位，直到把所有樣本（或指標(biāo)）都聚合完畢，把不同的類型一一劃分出

8、本（或指標(biāo)）都聚合完畢，把不同的類型一一劃分出來，形成一個由小到大的分類系統(tǒng)。最后把整個分類來，形成一個由小到大的分類系統(tǒng)。最后把整個分類系統(tǒng)畫成一張譜系圖，用它把所有樣本（或指標(biāo)）間系統(tǒng)畫成一張譜系圖，用它把所有樣本（或指標(biāo)）間的親疏關(guān)系表示出來。這種方法是最常用的、最基本的親疏關(guān)系表示出來。這種方法是最常用的、最基本的一種，稱為系統(tǒng)聚類分析。的一種，稱為系統(tǒng)聚類分析。系統(tǒng)聚類法基本步驟1. 選擇樣本間距離的定義及類間距離的定義；2. 計算n個樣本兩兩之間的距離，得到距離矩陣 3. 構(gòu)造個類，每類只含有一個樣本；4. 合并符合類間距離定義要求的兩類為一個新類；5. 計算新類與當(dāng)前各類的距離。

9、若類的個數(shù)為1，則轉(zhuǎn)到步驟6，否則回到步驟4;6.畫出聚類圖； 7.決定類的個數(shù)和類。 ijdD 系統(tǒng)聚類分析的方法系統(tǒng)聚類分析的方法l系統(tǒng)聚類法的聚類原則決定于樣品間的距離以及類間距離的定義，類間距離的不同定義就產(chǎn)生了不同的系統(tǒng)聚類分析方法。l以下用dij表示樣品X(i)和X(j)之間的距離，當(dāng)樣品間的親疏關(guān)系采用相似系數(shù)Cij時，令 ；l以下用D(p,q)表示類Gp和Gq之間的距離。221ijijCd1.最短距離法(SINgle method)2.最長距離法最長距離法(COMplete method)最長距離最短距離ABCDEF3.重心法重心法(CENtroid method)4.類平均法

10、類平均法(AVErage method)中間距離5.離差平方和法離差平方和法(WARD)l基本思想來源于方差分析。它認為：如果分類正確，同類間基本思想來源于方差分析。它認為：如果分類正確，同類間的類差平方和應(yīng)較小，類與類之間的離差平方和應(yīng)較大的類差平方和應(yīng)較小，類與類之間的離差平方和應(yīng)較大.l具體做法是，先將具體做法是，先將n個樣本分成一類個樣本分成一類,然后每次縮小一類然后每次縮小一類,每縮每縮小一類離差平方和就要增大小一類離差平方和就要增大. 離差平方和法離差平方和法(WARD)系統(tǒng)聚類方法的統(tǒng)一系統(tǒng)聚類方法的統(tǒng)一 系統(tǒng)聚類法參數(shù)表系統(tǒng)聚類法參數(shù)表 類的個數(shù)的確定類的個數(shù)的確定l由適當(dāng)?shù)拈?/p>

11、值確定；l根據(jù)數(shù)據(jù)點的散布直觀地確定類的個數(shù)；l根據(jù)統(tǒng)計量確定分類個數(shù)；類的個數(shù)的確定類的個數(shù)的確定l根據(jù)譜系圖確定分類個數(shù)的準(zhǔn)則：l各類重心間的距離必須很大；l類中保包含的元素不要太多；l類的個數(shù)必須符合實際應(yīng)用；l如果采用幾種不同的聚類方法處理，則在各種聚類圖中應(yīng)該發(fā)現(xiàn)相同的類。四、系統(tǒng)聚類的參數(shù)選擇四、系統(tǒng)聚類的參數(shù)選擇聚類類別：聚類類別：統(tǒng)計統(tǒng)計圖：樹型譜系圖圖：樹型譜系圖 冰柱譜系圖冰柱譜系圖聚類方法聚類方法1.Between-groups linkage 類間平均法類間平均法 兩類距離為兩類元素兩兩之間平均平方距離兩類距離為兩類元素兩兩之間平均平方距離2.Within-groups

12、 linkage 類內(nèi)平均法類內(nèi)平均法兩類距離為合并后類中可能元素兩兩之間平均平方距離兩類距離為合并后類中可能元素兩兩之間平均平方距離3.Nearest neighbor 最短距離法最短距離法 4. Furthest neighbor 最長距離法最長距離法5.Centroid clustering 重心法重心法 (歐式距離歐式距離)6.Median clustering 中間距離法中間距離法 (歐式距離歐式距離)7.Ward Method 離差平方法離差平方法 (歐式距離歐式距離)SPSS界面指南界面指南飲料數(shù)據(jù)（drink.sav ）l16種飲料如何分類？種飲料如何分類？ k-均值聚類 lk

13、-均值聚類（均值聚類（k-means cluster，也叫，也叫快速聚類，快速聚類，quick cluster）卻要求你先）卻要求你先說好要分多少類。說好要分多少類。l假定你說分假定你說分3類，這個方法還進一步要類，這個方法還進一步要求 你 事 先 確 定求 你 事 先 確 定 3 個 點 為個 點 為 “ 聚 類 種聚 類 種子子”(SPSS軟件軟件自動自動為你選種子為你選種子)；也；也就是說，把這就是說，把這3個點作為三類中每一類個點作為三類中每一類的基石。的基石。l然后，根據(jù)和這三個點的距離遠近，把然后，根據(jù)和這三個點的距離遠近，把所有點分成三類。再把這三類的中心所有點分成三類。再把這三

14、類的中心(均值均值)作為新的基石或種子作為新的基石或種子(原來原來 “種子種子”就沒用了就沒用了)，再重新按照距離分類。，再重新按照距離分類。l如此疊代下去，直到達到停止疊代的要如此疊代下去，直到達到停止疊代的要求（比如，各類最后變化不大了，或者求（比如，各類最后變化不大了，或者疊代次數(shù)太多了）。疊代次數(shù)太多了）。l下面用飲料例的數(shù)據(jù)來做下面用飲料例的數(shù)據(jù)來做k-均值聚類。均值聚類。 假定要把這假定要把這1616種飲料分成種飲料分成3 3類。利用類。利用SPSSSPSS，只疊，只疊代了三次就達到目標(biāo)了（計算機選的種子還可代了三次就達到目標(biāo)了（計算機選的種子還可以）。這樣就可以得到最后的三類的中

15、心以及每以）。這樣就可以得到最后的三類的中心以及每類有多少點類有多少點 Final Cluster CentersFinal Cluster Centers203.1033.71107.341.654.163.4913.0510.068.763.152.692.94CALORIECAFFEINESODIUMPRICE123ClusterNumber of Cases in each ClusterNumber of Cases in each Cluster2.0007.0007.00016.000.000123ClusterValidMissing根據(jù)需要，可以輸出哪些點分在一起。根據(jù)需要，

16、可以輸出哪些點分在一起。結(jié)果是：第一類為飲料結(jié)果是：第一類為飲料1、10；第二類為；第二類為飲料飲料2、4、8、11、12、13、14；第三類；第三類為剩下的飲料為剩下的飲料3、5、6、7、9、15、16。SPSS實現(xiàn)(聚類分析)lK-均值聚類均值聚類l以數(shù)據(jù)以數(shù)據(jù)drink.sav為例，在為例，在SPSS中選擇中選擇AnalyzeClassifyK-Menas Cluster，l然后把然后把calorie（熱量）、（熱量）、caffeine（咖啡（咖啡因）、因）、sodium（鈉）、（鈉）、price（價格）選入（價格）選入Variables, l在在Number of Clusters處選

17、擇處選擇3（想要分的類（想要分的類數(shù)），數(shù)），l如果想要知道哪種飲料分到哪類，則選如果想要知道哪種飲料分到哪類，則選Save，再選再選Cluster Membership等。等。l注意注意k-均值聚類只能做均值聚類只能做Q型聚類，如要做型聚類，如要做R型型聚類，需要把數(shù)據(jù)陣進行轉(zhuǎn)置。聚類，需要把數(shù)據(jù)陣進行轉(zhuǎn)置。分層聚類 l分層聚類或系統(tǒng)聚類（分層聚類或系統(tǒng)聚類（hierarchical cluster）。開始時，有多少點就是多少）。開始時，有多少點就是多少類。類。l它第一步先把最近的兩類（點）合并成它第一步先把最近的兩類（點）合并成一類，然后再把剩下的最近的兩類合并一類，然后再把剩下的最近的兩

18、類合并成一類；成一類；l這樣下去，每次都少一類，直到最后只這樣下去，每次都少一類，直到最后只有一大類為止。越是后來合并的類，距有一大類為止。越是后來合并的類，距離就越遠。離就越遠。對于對于飲料聚類。飲料聚類。 SPSSSPSS輸出為輸出為Agglomeration ScheduleAgglomeration Schedule515139700032436.4850286969.1300010110102.6300015811150.330008516198.375101128319.77836121214322.540001236458.7950413571006.8

19、6370132121435.0768914351755.654101114236287.1751213151219406.6845140Stage123456789101112131415Cluster 1Cluster 2Cluster CombinedCoefficients Cluster 1Cluster 2Stage Cluster FirstAppearsNext StageVertical IcicleVertical IcicleXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX

20、 XXXXXXXXXXXXX XXXXXXXXXX XXXXX XXXXXXXXXXXXX XXXXXXXXXX XXXXX XXX XXXXXXXXX XXXX XXXXX XXXXX XXX XXXXXXXXX XXXX XXXXX XXX X XXX XXXXXXXXX XXXX XXXXX XXX X X X XXXXXXXXX XXXX XXXXX XXX X X X XXX XXXXX XXXX X XXX XXX X X X XXX XXXXX XXXX X XXX XXX X X X X X XXXXX XXXX X XXX XXX X X X X X XXXXX X XX X XXX X X X X X X X XXXXX X XX X XXX X X X X X X X XXX X X XX X XXX X X X X X X X X X X X XNumber of clusters1234567891011121314157 16 15 5 9 6 3 14 12 11 8 13 4 2 10 1Case“冰柱圖冰柱圖”(icicle)聚類要注意的問題 l聚類結(jié)果主要受所選擇的變量影響。聚類結(jié)果主要受所選擇的變量影響。如果去掉一