聚類分析及MATLAB實現(xiàn)

1、4.1 樣品（變量）相近性度量樣品（變量）相近性度量 4.2 譜系聚類法及譜系聚類法及MATLAB實現(xiàn)實現(xiàn) 4.3 快速聚類法快速聚類法 統(tǒng)計方法（聚類分析）: 聚類分析所研究的樣本或者變量之間存 在程度不同的相似性，要求設法找出一些 能夠度量它們之間相似程度的統(tǒng)計量作為 分類的依據(jù)，再利用這些量將樣本或者變 量進行分類 系統(tǒng)聚類分析將n個樣本或者n個指標看 成n類，一類包括一個樣本或者指標，然 后將性質(zhì)最接近的兩類合并成為一個新類， 依此類推。最終可以按照需要來決定分多 少類，每類有多少樣本（指標） 統(tǒng)計方法（系統(tǒng)聚類分析步驟）: 系統(tǒng)聚類方法步驟： 計算n個樣本兩兩之間的距離 構(gòu)成n個類，

2、每類只包含一個樣品 合并距離最近的兩類為一個新類 計算新類與當前各類的距離（新類與當 前類的距離等于當前類與組合類中包含 的類的距離最小值），若類的個數(shù)等于 1，轉(zhuǎn)5，否則轉(zhuǎn)3 畫聚類圖 1. 決定類的個數(shù)和類。 系統(tǒng)聚類分析: 主要介紹系統(tǒng)聚類分析方法。系統(tǒng)聚類法 是聚類分析中應用最為廣泛的一種方法， 它的基本原理是：首先將一定數(shù)量的樣 品或指標各自看成一類，然后根據(jù)樣品 （或指標）的親疏程度，將親疏程度最 高的兩類進行合并。然后考慮合并后的 類與其他類之間的親疏程度，再進行合 并。重復這一過程，直至將所有的樣品 （或指標）合并為一類。 系統(tǒng)聚類分析用到的函數(shù): 函 數(shù)功 能 pdist計算

3、觀測量兩兩之間的距離 squareform 將距離矩陣從上三角形式轉(zhuǎn)換為方形 形式，或從方形形式轉(zhuǎn)換為上三角形 式 linkage 創(chuàng)建系統(tǒng)聚類樹 dendrogram 輸出冰柱圖 cophenet 計算Cophenetic相關系數(shù) cluster 根據(jù)linkage函數(shù)的輸出創(chuàng)建分類 clusterdata 根據(jù)數(shù)據(jù)創(chuàng)建分類 inconsistent 計算聚類樹的不連續(xù)系數(shù) 聚類分析 研究對研究對樣品或指標樣品或指標進行分類的一種多元統(tǒng)計方法進行分類的一種多元統(tǒng)計方法, 是依據(jù)研究對象的個體的特征進行分類的方法。是依據(jù)研究對象的個體的特征進行分類的方法。 聚類分析把分類對象按一定規(guī)則分成若干

4、類，這聚類分析把分類對象按一定規(guī)則分成若干類，這 些類些類非事先給定非事先給定的，而是根據(jù)數(shù)據(jù)特征確定的。的，而是根據(jù)數(shù)據(jù)特征確定的。 在同一類中這些對象在某種意義上趨向于彼此相在同一類中這些對象在某種意義上趨向于彼此相 似，而在不同類中趨向于不相似。似，而在不同類中趨向于不相似。 職能是建立一種能按照樣品或變量的相似程度進職能是建立一種能按照樣品或變量的相似程度進 行分類的方法。行分類的方法。 聚類分析有兩種聚類分析有兩種：一種是對樣品的分類，稱為：一種是對樣品的分類，稱為Q 型，另一種是對變量（指標）的分類，稱為型，另一種是對變量（指標）的分類，稱為R型。型。 R型聚類分析的主要作用：型聚

5、類分析的主要作用： 不但可以了解個別變量之間的親疏程度，而且可以了解不但可以了解個別變量之間的親疏程度，而且可以了解 各個變量組合之間的親疏程度。各個變量組合之間的親疏程度。 根據(jù)變量的分類結(jié)果以及它們之間的關系，可以選擇主根據(jù)變量的分類結(jié)果以及它們之間的關系，可以選擇主 要變量進行要變量進行Q型聚類分析或回歸分析。（型聚類分析或回歸分析。（R2為選擇標準）為選擇標準） Q型聚類分析的主要作用：型聚類分析的主要作用： 可以綜合利用多個變量的信息對樣本進行分析?？梢跃C合利用多個變量的信息對樣本進行分析。 分類結(jié)果直觀，聚類譜系圖清楚地表現(xiàn)數(shù)值分類結(jié)果。分類結(jié)果直觀，聚類譜系圖清楚地表現(xiàn)數(shù)值分類結(jié)

6、果。 聚類分析所得到的結(jié)果比傳統(tǒng)分類方法更細致、全面、聚類分析所得到的結(jié)果比傳統(tǒng)分類方法更細致、全面、 合理。合理。 在課堂上主要討論在課堂上主要討論Q型聚類分析型聚類分析, Q型聚類常用的統(tǒng)計量是距型聚類常用的統(tǒng)計量是距 離離. 4.1 樣品（變量）間相近性度量樣品（變量）間相近性度量 4.1.1 聚類分析的基本思想聚類分析的基本思想 在生產(chǎn)實際中經(jīng)常遇到給產(chǎn)品等級進行分類的問題，在生產(chǎn)實際中經(jīng)常遇到給產(chǎn)品等級進行分類的問題， 如一等品、二等品等，在生物學中，要根據(jù)生物的如一等品、二等品等，在生物學中，要根據(jù)生物的 特征進行分類；在考古時要對古生物化石進行科學特征進行分類；在考古時要對古生物

7、化石進行科學 分類；在球類比賽中經(jīng)常要對各球隊進行分組如何分類；在球類比賽中經(jīng)常要對各球隊進行分組如何 確定種子隊，這些問題就是聚類分析問題。隨著科確定種子隊，這些問題就是聚類分析問題。隨著科 學技術的發(fā)展，我們利用已知數(shù)據(jù)首先提取數(shù)據(jù)特學技術的發(fā)展，我們利用已知數(shù)據(jù)首先提取數(shù)據(jù)特 征，然后借助計算機依據(jù)這些特征進行分類，聚類征，然后借助計算機依據(jù)這些特征進行分類，聚類 的依據(jù)在于各類別之間的接近程度如何計量，通常的依據(jù)在于各類別之間的接近程度如何計量，通常 采取距離與相似系數(shù)進行衡量。采取距離與相似系數(shù)進行衡量。 設有設有n個樣品的個樣品的p元觀測數(shù)據(jù)組成一個數(shù)據(jù)矩陣元觀測數(shù)據(jù)組成一個數(shù)據(jù)矩

8、陣 npn2n1 2p2221 1p1211 xxx xxx xxx X 其中每一行表示一個樣品，每一列表示一個指標，其中每一行表示一個樣品，每一列表示一個指標，xij 表示第表示第i個樣品關于第個樣品關于第j項指標的觀測值，聚類分析的項指標的觀測值，聚類分析的 基本思想就是在樣品之間定義距離，在指標之間定義基本思想就是在樣品之間定義距離，在指標之間定義 相似系數(shù)，樣品之間距離表明樣品之間的相似度，指相似系數(shù)，樣品之間距離表明樣品之間的相似度，指 標之間的相似系數(shù)刻畫指標之間的相似度。將樣品標之間的相似系數(shù)刻畫指標之間的相似度。將樣品 （或變量）按相似度的大小逐一歸類，關系密切的聚（或變量）按

9、相似度的大小逐一歸類，關系密切的聚 集到較小的一類，關系疏遠的聚集到較大的一類，聚集到較小的一類，關系疏遠的聚集到較大的一類，聚 類分析通常有：類分析通常有：譜系聚類、快速聚類，我們主要介紹譜系聚類、快速聚類，我們主要介紹 譜系聚類的方法與譜系聚類的方法與MATLAB實現(xiàn)實現(xiàn) 4.1.2 樣品間的相似度量樣品間的相似度量距離距離 一一.常用距離的定義常用距離的定義 設有設有n個樣品的個樣品的p元觀測數(shù)據(jù)：元觀測數(shù)據(jù)： n21ixxxx T ipi2i1i ,),( 這時，每個樣品可看成這時，每個樣品可看成p p元空間的一個點，每兩個點之元空間的一個點，每兩個點之 間的距離記為間的距離記為 滿足

10、條件：滿足條件： ),( ji xxd jijiji xx0 xxd0 xxd當且僅當且),(,),( ),(),( ijji xxdxxd ),(),(),( jkkiji xxdxxdxxd 1.歐氏距離歐氏距離 21 p 1k 2 jkikji xxxxd / )(),( pdist(x) 2.絕對距離絕對距離 p 1k jkikji xxxxd|),(pdist(x,cityblock) 3.明氏距離明氏距離 m1 p 1k m jkikji xxxxd / |),( pdist(x,minkowski,r) 4.切氏距離切氏距離 |),( jkik pk1 ji xxmaxxxd m

11、ax(abs(xi-xj) 5.方差加權(quán)距離方差加權(quán)距離 21 p 1k 2 k 2 jkikji sxxxxd / /)(),( 將原數(shù)據(jù)標準化以后的歐氏距離將原數(shù)據(jù)標準化以后的歐氏距離 6.馬氏距離馬氏距離 T1 ijijij d(x ,x )(xx )(xx ) pdist(x,mahal) 7.蘭氏距離蘭氏距離 p 1k jkik jkik ji xx xx p 1 xxd | ),( 8.杰氏距離（杰氏距離（Jffreys x3:人均煙酒茶支出，人均煙酒茶支出， x4:人均其他副食支出人均其他副食支出,x5:人均衣著商品支出人均衣著商品支出,x6:人均人均 日用品支出，日用品支出，x

12、7:人均燃料支出，人均燃料支出，x8人均非商品支出人均非商品支出 X X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 7X X8 8 遼寧遼寧7.97.939.7739.778.498.4912.9412.9419.2719.2711.0511.052.042.0413.2913.29 浙江浙江7.687.6850.3750.3711.3511.3513.313.319.2519.2514.5914.592.752.7514.8714.87 河南河南9.429.4227.9327.938.28.28.148.1416.1716.179.429.421.551.55

13、9.769.76 甘肅甘肅9.169.1627.9827.989.019.019.329.3215.9915.999.19.11.821.8211.3511.35 青海青海10.0610.0628.6428.6410.5210.5210.0510.0516.1816.188.398.391.961.9610.8110.81 表表1 1991年五省城鎮(zhèn)居民生活月均消費（元年五省城鎮(zhèn)居民生活月均消費（元/人）人） 計算各省之間的歐氏、絕對、明氏距離計算各省之間的歐氏、絕對、明氏距離 解：解：a=7.939.778.4912.9419.2711.052.0413.29 7.6850.3711.351

14、3.319.2514.592.7514.87 9.4227.938.28.1416.179.421.559.76 9.1627.989.019.3215.999.11.8211.35 10.0628.6410.5210.0516.188.391.9610.81; d1=pdist(a);% 此時計算出各行之間的歐氏距離，此時計算出各行之間的歐氏距離， 為了得到書中的距離矩陣，我們鍵入命令：為了得到書中的距離矩陣，我們鍵入命令： D= squareform(d1), % 注意此時注意此時d1必須是一個行向量，必須是一個行向量， 結(jié)果是實對稱矩陣結(jié)果是實對稱矩陣 若想得到書中的三角陣，則有命令：若

15、想得到書中的三角陣，則有命令： S = tril(squareform(d1) S = 0 0 0 0 0 11.6726 0 0 0 0 13.8054 24.6353 0 0 0 13.1278 24.0591 2.2033 0 0 12.7983 23.5389 3.5037 2.2159 0 d2=pdist(a,cityblock); S2 = tril(squareform(d2) S2 = 0 0 0 0 0 19.89 0 0 0 0 27.2 47.05 0 0 0 24.58 43.39 4.66 0 0 26.52 42.31 8.08 5.38 0 d3=pdist(a

16、,minkowski,3); S3 = tril(squareform(d3) 序號序號國家國家199019952000 1澳大利亞澳大利亞1249.391273.611282.68 2巴西巴西821.6859.85919.73 3加拿大加拿大1641.011591.541608.32 4中國中國1330.451382.681462.08 5法國法國1546.551501.771525.95 6德國德國1656.521630.521570.69 7印度印度861.30862.51945.11 8意大利意大利1321.771232.31243.51 9日本日本1873.681949.891851

17、.20 10俄羅斯俄羅斯1475.161315.871297 11南非南非794.25787.48782.38 12英國英國1486.751441.711465.12 13美國美國2824.292659.642740.12 例例2. 13個國家個國家1990，1995，2000可持續(xù)發(fā)展可持續(xù)發(fā)展 能力如下：分成能力如下：分成4類類 采用不同的距離，得到結(jié)果如下采用不同的距離，得到結(jié)果如下 類別類別歐氏距離（最短距離）歐氏距離（最短距離） 1日本日本 2澳大利亞、加拿大、英、德、意、中、俄、法澳大利亞、加拿大、英、德、意、中、俄、法 3巴西、印度、南非巴西、印度、南非 4美國美國 類別類別歐氏

18、距離（歐氏距離（ward距離）距離） 1澳大利亞、中、意、俄澳大利亞、中、意、俄 2加拿大、英、德、法、日本加拿大、英、德、法、日本 3巴西、印度、南非巴西、印度、南非 4美國美國 類別類別馬氏距離（馬氏距離（ward距離）距離） 1日本日本 2澳大利亞、加拿大、英、德、意、南非、俄、法澳大利亞、加拿大、英、德、意、南非、俄、法 3巴西、印度、中巴西、印度、中 4美國美國 4.1.3 變量間的相似度量變量間的相似度量相似系數(shù)相似系數(shù) 當對當對p個指標變量進行聚類時，用相似系數(shù)來個指標變量進行聚類時，用相似系數(shù)來 衡量變量之間的相似程度（關聯(lián)度），若用衡量變量之間的相似程度（關聯(lián)度），若用 表表

19、 示變量之間的相似系數(shù)，則應滿足：示變量之間的相似系數(shù)，則應滿足： , C 1C1C 且,| 0kk1C, 當且僅當 CC 相似系數(shù)中最常用的是相似系數(shù)中最常用的是相關系數(shù)與夾角余弦相關系數(shù)與夾角余弦。 夾角余弦夾角余弦 兩變量的夾角余弦定義為：兩變量的夾角余弦定義為： 相關系數(shù)相關系數(shù) 兩變量的相關系數(shù)定義為：兩變量的相關系數(shù)定義為： 例例3.計算例計算例1中各指標之間的相關系數(shù)與夾角余弦中各指標之間的相關系數(shù)與夾角余弦 解：解：a=7.939.77 8.4912.94 19.27 11.052.04 13.29 7.6850.37 11.3513.319.25 14.59 2.75 14.

20、87 9.4227.93 8.28.1416.17 9.421.55 9.76 9.1627.98 9.019.3215.99 9.11.82 11.35 10.06 28.64 10.52 10.05 16.18 8.391.96 10.81; R=corrcoef(a);% 指標之間的相關系數(shù)指標之間的相關系數(shù) a1=normc(a); % 將將a的各列化為單位向量的各列化為單位向量 J=a1*a1 % 計算計算a中各列之間的夾角余弦中各列之間的夾角余弦 J = 1.0000 0.9410 0.9847 0.9613 0.9824 0.9546 0.9620 0.9695 0.9410 1

21、.0000 0.9782 0.9939 0.9853 0.9977 0.9947 0.9935 0.9847 0.9782 1.0000 0.9859 0.9911 0.9840 0.9931 0.9909 0.9613 0.9939 0.9859 1.0000 0.9944 0.9919 0.9947 0.9981 0.9824 0.9853 0.9911 0.9944 1.0000 0.9901 0.9901 0.9968 0.9546 0.9977 0.9840 0.9919 0.9901 1.0000 0.9952 0.9953 0.9620 0.9947 0.9931 0.9947

22、0.9901 0.9952 1.0000 0.9968 0.9695 0.9935 0.9909 0.9981 0.9968 0.9953 0.9968 1.0000 4.2 譜系聚類法譜系聚類法 譜系聚類法是目前應用較為廣泛的一種聚類法。譜譜系聚類法是目前應用較為廣泛的一種聚類法。譜 系聚類是根據(jù)生物分類學的思想對研究對象進行分類的系聚類是根據(jù)生物分類學的思想對研究對象進行分類的 方法。在生物分類學中，分類的單位是：門、綱、目、方法。在生物分類學中，分類的單位是：門、綱、目、 科、屬、種。其中種是分類的基本單位，分類單位越小，科、屬、種。其中種是分類的基本單位，分類單位越小， 它所包含的生物

23、就越少，生物之間的共同特征就越多。它所包含的生物就越少，生物之間的共同特征就越多。 利用這種思想，譜系聚類首先將各樣品自成一類，然后利用這種思想，譜系聚類首先將各樣品自成一類，然后 把最相似（距離最近或相似系數(shù)最大）的樣品聚為小類，把最相似（距離最近或相似系數(shù)最大）的樣品聚為小類， 再將已聚合的小類按各類之間的相似性（用類間距離度再將已聚合的小類按各類之間的相似性（用類間距離度 量）進行再聚合，隨著相似性的減弱，最后將一切子類量）進行再聚合，隨著相似性的減弱，最后將一切子類 都聚為一大類，從而得到一個按相似性大小聚結(jié)起來的都聚為一大類，從而得到一個按相似性大小聚結(jié)起來的 一個譜系圖。一個譜系圖

24、。 聚類分析的聚類分析的基本思想基本思想是認為我們所研究的樣是認為我們所研究的樣 本或指標（變量）之間存在著程度不同的相似性本或指標（變量）之間存在著程度不同的相似性 （親疏關系）。于是根據(jù)一批樣本的多個觀測指標，（親疏關系）。于是根據(jù)一批樣本的多個觀測指標， 具體找出一些彼此之間相似程度較大的樣本（或指具體找出一些彼此之間相似程度較大的樣本（或指 標）聚合為一類，把另外一些彼此之間相似程度較標）聚合為一類，把另外一些彼此之間相似程度較 大的樣本（或指標）又聚合為另一類，關系密切的大的樣本（或指標）又聚合為另一類，關系密切的 聚合到一個小的分類單位，關系疏遠的聚合到一個聚合到一個小的分類單位，

25、關系疏遠的聚合到一個 大的分類單位，直到把所有樣本（或指標）都聚合大的分類單位，直到把所有樣本（或指標）都聚合 完畢，把不同的類型一一劃分出來，形成一個由小完畢，把不同的類型一一劃分出來，形成一個由小 到大的分類系統(tǒng)。最后把整個分類系統(tǒng)畫成一張譜到大的分類系統(tǒng)。最后把整個分類系統(tǒng)畫成一張譜 系圖，用它把所有樣本（或指標）間的親疏關系表系圖，用它把所有樣本（或指標）間的親疏關系表 示出來。這種方法是最常用的、最基本的一種，稱示出來。這種方法是最常用的、最基本的一種，稱 為為系統(tǒng)聚類分析系統(tǒng)聚類分析。 4.2.1 類間距離類間距離 前面，我們介紹了兩個向量之間的距離，下面我們前面，我們介紹了兩個向

26、量之間的距離，下面我們 介紹兩個類別之間的距離：介紹兩個類別之間的距離： 設設dij表示兩個樣品表示兩個樣品xi,xj之間的距離，之間的距離，Gp,Gq分別表示兩分別表示兩 個類別，各自含有個類別，各自含有np,nq個樣品個樣品. （1）最短距離）最短距離 ij GjGi pq dminD qp , 即用兩類中樣品之間的距離最短者作為兩類間距離即用兩類中樣品之間的距離最短者作為兩類間距離 （2）最長距離）最長距離 , pq pqij i Gj G Dmax d 即用兩類中樣品之間的距離最長者作為兩類間距離即用兩類中樣品之間的距離最長者作為兩類間距離 最短距離（Nearest Neighbor)

27、 x21 x12 x22 x11 13 d 最長距離（Furthest Neighbor ） x11 x21 12 d 重心距離重心距離 11 ,x y 22 ,xy / 9 i i=1 d9 最長距離最長距離 最短距離最短距離 A B C D E F 中間距離中間距離 （3）類平均距離）類平均距離 pq GiGj ij qp pq d nn 1 D 即用兩類中所有兩兩樣品之間距離的平均作為兩類間即用兩類中所有兩兩樣品之間距離的平均作為兩類間 距離距離 （4）重心距離）重心距離 )()(),( qp T qpqppq xxxxxxdD 其中其中 分別是分別是Gp,Gq的重心，這是用兩類的重心的

28、重心，這是用兩類的重心 之間的歐氏距離作為兩類間的距離。之間的歐氏距離作為兩類間的距離。 qp xx , （5）離差平方和距離（）離差平方和距離（ward）)()( qp T qp qp qp 2 pq xxxx nn nn D 顯然，離差平方和距離與重心距離的平方成正比。顯然，離差平方和距離與重心距離的平方成正比。 4.2.2 類間距離的遞推公式類間距離的遞推公式 設有兩類設有兩類Gp,Gq合并成新的一類合并成新的一類Gr，包含了，包含了 nr=np+nq個樣品，如何計算個樣品，如何計算Gr與其他類別與其他類別Gk之間的之間的 距離，這就需要建立類間距離的遞推公式。距離，這就需要建立類間距離

29、的遞推公式。 （1）最短距離）最短距離),( qkpkrk DDminD （2）最長距離）最長距離 ),( qkpkrk DDmaxD （3）類平均距離）類平均距離 qk r q pk r p rk D n n D n n D （4）重心距離）重心距離2 pq r q r p 2 qk r q 2 pk r p 2 rk D n n n n D n n D n n D 證明：證明： r T rk T rk T krk T rk 2 rk xxxx2xxxxxxD)()( k T k r q k T k r p k T k xx n n xx n n xx () rppqq r 1 ,xn xn

30、 x n 將將 代入（代入（1） (1) _._. pqpq 2TTTT2TT2T rkkkkkkpkqppppqpqqqq 2 rrrrr nnnn 1 Dx xx x2x x2x xn x x2n n x xn x x nnnnn . . 將上式中加上再減去將上式中加上再減去 與與 ，合并同類項，合并同類項 得得 _ p T p r p xx n n q T q r q xx n n q T q r q p T p r p q T q 2 qq T pqpp T p 2 p 2 r q T qq T kk T k r q p T pp T kk T k r p 2 rk xx n n xx

31、 n n xxnxxn2nxxn n 1 xxxx2xx ( n n xxxx2xx ( n n D ) 上式第二行合并同類項，得上式第二行合并同類項，得 2 pq r q r p 2 qk r q 2 pk r p 2 rk D n n n n D n n D n n D （5）離差平方和距離）離差平方和距離 2 pq kr k2 qk kr kq 2 pk kr kp 2 rk D nn n D nn nn D nn nn D 1. 選擇樣本間距離的定義及類間距離的定義；選擇樣本間距離的定義及類間距離的定義； 2. 計算計算n n個個樣本樣本兩兩之間的距離，得到距離矩陣兩兩之間的距離，得到

32、距離矩陣 3. 構(gòu)造個類，每類只含有一個構(gòu)造個類，每類只含有一個樣本樣本； 4. 合并符合類間距離定義要求的兩類為一個新類；合并符合類間距離定義要求的兩類為一個新類； 5. 計算新類與當前各類的距離。若類的個數(shù)為計算新類與當前各類的距離。若類的個數(shù)為1 1，則轉(zhuǎn)，則轉(zhuǎn) 到步驟到步驟6 6，否則回到步驟，否則回到步驟4;4; 6.6.畫出聚類圖；畫出聚類圖； 7.7.決定類的個數(shù)和類。決定類的個數(shù)和類。 ij dD 4.2.3 4.2.3 譜系聚類法的步驟譜系聚類法的步驟 譜系聚類的步驟如下：譜系聚類的步驟如下： 系統(tǒng)聚類分析的方法系統(tǒng)聚類分析的方法 系統(tǒng)聚類法的聚類原則決定于樣品間的距離以系統(tǒng)

33、聚類法的聚類原則決定于樣品間的距離以 及類間距離的定義，及類間距離的定義，類間距離類間距離的不同定義就產(chǎn)的不同定義就產(chǎn) 生了不同的系統(tǒng)聚類分析方法。生了不同的系統(tǒng)聚類分析方法。 以下用以下用dij表示樣品表示樣品X(i)和和X(j)之間的距離，當樣品之間的距離，當樣品 間的親疏關系采用相似系數(shù)間的親疏關系采用相似系數(shù)Cij時，時， 令令 ； 以下用以下用D(p,q)表示類表示類Gp和和Gq之間的距離。之間的距離。 22 1 ijij Cd （1）n個樣品開始作為個樣品開始作為n個類，計算兩兩之間的個類，計算兩兩之間的 距離或相似系數(shù)，得到實對稱矩陣距離或相似系數(shù)，得到實對稱矩陣 nnn2n1

34、2n2221 1n1211 0 ddd ddd ddd D （2）從）從D0的非主對角線上找最?。ň嚯x）或最大的非主對角線上找最?。ň嚯x）或最大 元素（相似系數(shù)），設該元素是元素（相似系數(shù)），設該元素是Dpq，則將，則將Gp,Gq合合 并成一個新類并成一個新類Gr=（Gp,Gq），在），在D0中去掉中去掉Gp,Gq 所在的兩行、兩列，并加上新類與其余各類之間的所在的兩行、兩列，并加上新類與其余各類之間的 距離距離(或相似系數(shù)或相似系數(shù))，得到，得到n-1階矩陣階矩陣D1。 （3）從）從D1出發(fā)重復步驟（出發(fā)重復步驟（2）的做法得到）的做法得到D2，再，再 由由D2出發(fā)重復上述步驟，直到所有樣品

35、聚為一個出發(fā)重復上述步驟，直到所有樣品聚為一個 大類為止。大類為止。 （4）在合并過程中要記下合并樣品的編號及兩類合）在合并過程中要記下合并樣品的編號及兩類合 并時的水平，并繪制聚類譜系圖。并時的水平，并繪制聚類譜系圖。 例例4. 從例從例1算得的樣品間的歐氏距離矩陣出發(fā)，用算得的樣品間的歐氏距離矩陣出發(fā)，用 下列方法進行譜系聚類。下列方法進行譜系聚類。 （1）最短距離，（）最短距離，（2）最長距離）最長距離 解：我們用解：我們用1，2，3，4，5分別表示遼寧、浙江、河分別表示遼寧、浙江、河 南、甘肅和青海，將距離矩陣記為南、甘肅和青海，將距離矩陣記為D0 5 4 3 2 1 D0 02125

36、1354238012 020206241213 063248013 06711 0 54321 . . . . （1）最短距離法：將各省看成一類，即）最短距離法：將各省看成一類，即Gi=i i=1,5, 從從D0可以看出各類中距離最短的是可以看出各類中距離最短的是d43=2.20,因此將因此將 G3,G4在在2.20水平上合成一個新類水平上合成一個新類G6=3,4,計算計算G6和和 G1,G2,G5之間的最短距離之間的最短距離 ，得，得 212ddminD 0624ddminD 1213ddminD 453565 423262 413161 ., ,., ,., 將計算結(jié)果作為第一列，從將計算

37、結(jié)果作為第一列，從D0中去掉第中去掉第3、4行與行與3、 4列，剩余元素作為其余各列得到列，剩余元素作為其余各列得到D1 1 D , 5 2 1 43 023.5412.802.21 011.6724.06 013.12 0 52143, 從從D1可以看出可以看出G6與與G5的距離最小，因此在的距離最小，因此在2.21的水的水 平上將平上將G6與與G5合成一類合成一類G7，即，即G7=3，4，5計算計算 G7與與G1，G2之間的最短距離，得之間的最短距離，得 542354230624minDDminD 801280121213minDDminD 526262 516171 .,., .,.,

38、將計算結(jié)果作為第一列，從將計算結(jié)果作為第一列，從D1中劃掉中劃掉3，4與與5 所在的行與列，剩余元素作為其他列得所在的行與列，剩余元素作為其他列得 2 1 3,4,5 D2 067115423 0812 0 21543 . . , 從從D2可以看出可以看出G1,G2最接近，在最接近，在11.67的水平上合并的水平上合并 成一類成一類G8，至此只剩下，至此只剩下G7,G8兩類，他們之間的距兩類，他們之間的距 離為：離為：12.8，故在此水平上將合成一類，包含了全，故在此水平上將合成一類，包含了全 部的五個省份。部的五個省份。 最后，我們作出譜系聚類圖：最后，我們作出譜系聚類圖： 圖1 最短距離聚

39、類圖 最長距離聚類方法，同學練習最長距離聚類方法，同學練習 例 為了研究遼寧等為了研究遼寧等5省省1991年城鎮(zhèn)居民生活消費年城鎮(zhèn)居民生活消費 情況的分布規(guī)律，根據(jù)調(diào)查資料做類型分類，情況的分布規(guī)律，根據(jù)調(diào)查資料做類型分類， 用最短距離做類間分類。數(shù)據(jù)如下：用最短距離做類間分類。數(shù)據(jù)如下： x1x2x3x4x5x6x7x8 遼寧17.9039.778.4912.9419.2711.052.0413.29 浙江27.6850.3711.3513.3019.2514.592.7514.87 河南39.4227.938.208.1416.179.421.559.76 甘肅49.1627.989.01

40、9.3215.999.101.8211.35 青海510.0628.6410.5210.0516.188.391.9610.81 將每一個省區(qū)視為一個樣品，先計算將每一個省區(qū)視為一個樣品，先計算5個省區(qū)之間的歐個省區(qū)之間的歐 式距離，用式距離，用D0表示距離矩陣（對稱陣，故給出下三角表示距離矩陣（對稱陣，故給出下三角 陣）陣） 因此將因此將3.4合并為一類，為類合并為一類，為類6，替代了，替代了3、4兩類兩類 類類6與剩余的與剩余的1、2、5之間的距離分別為：之間的距離分別為： d(3,4)1=min(d31,d41)=min(13.80,13.12)=13.12 d(3,4)2=min(d3

41、2,d42)=min(24.63,24.06)=24.06 d(3,4)5=min(d35,d45)=min(3.51,2.21)=2.21 021.251.354.2380.12 020.206.2412.13 063.2480.13 067.11 0 54321 5 4 3 2 1 0 青海 甘肅 河南 浙江 遼寧 D 得到新矩陣得到新矩陣 合并類合并類6和類和類5，得到新類，得到新類7 類類7與剩余的與剩余的1、2之間的距離分別為：之間的距離分別為： d(5,6)1=min(d51,d61)=min(12.80,13.12)=12.80 d(5,6)2=min(d52,d62)=min(

42、23.54,24.06)=23.54 054.2380.1221. 25 067.1106.242 012.131 06 5216 1 G G G G GGGG D 得到新矩陣得到新矩陣 合并類合并類1和類和類2，得到新類，得到新類8 此時，我們有兩個不同的類：類此時，我們有兩個不同的類：類7和類和類8。 它們的最近距離它們的最近距離 d(7,8) =min(d71,d72)=min(12.80,23.54)=12.80 067.1154.232 080.121 07 217 2 G G G GGG D 得到矩陣得到矩陣 最后合并為一個大類。這就是按最短距離定義類間距最后合并為一個大類。這就是

43、按最短距離定義類間距 離的系統(tǒng)聚類方法。最長距離法類似！離的系統(tǒng)聚類方法。最長距離法類似！ 080.128 07 87 3 G G GG D 4.2.4 譜系聚類的譜系聚類的MATLAB實現(xiàn)：實現(xiàn)： （1）輸入數(shù)據(jù)矩陣，注意行與列的實際意義；輸入數(shù)據(jù)矩陣，注意行與列的實際意義； （2）計算各樣品之間的距離（行？列？）計算各樣品之間的距離（行？列？） 歐氏距離：歐氏距離：d=pdist(A) % 注意計算注意計算A中各行之中各行之 間的距離；間的距離； 絕對距離：絕對距離：d= pdist(A,cityblock); 明氏距離：明氏距離：d=pdist(A,minkowski,r); % r要填

44、要填 上具體的實數(shù)；上具體的實數(shù)； 方差加權(quán)距離：方差加權(quán)距離：d= pdist(A,seuclid); 馬氏距離：馬氏距離：d= pdist(A,mahal); 注意：以上命令輸出的結(jié)果是一個注意：以上命令輸出的結(jié)果是一個行向量行向量， 如果要得到距離矩陣，可以用命令：如果要得到距離矩陣，可以用命令： D= squareform(d), 若得到三角陣，可以用命令：若得到三角陣，可以用命令： D= tril(squareform(d1) (3) 選擇不同的類間距離進行聚類選擇不同的類間距離進行聚類 最短距離最短距離：z1= linkage(d) % 此處及以下的此處及以下的d 都是（都是（2）

45、中算出的距離行向量）中算出的距離行向量 最長距離：最長距離：z2= linkage(d,complete) 中間距離：中間距離：z3= linkage(d,centroid) 重心距離：重心距離：z4= linkage(d,average) 離差平方和：離差平方和：z5= linkage(d,ward) 注意：此時輸出的結(jié)果是一個注意：此時輸出的結(jié)果是一個n-1行行3列的矩陣，列的矩陣， 每一行表示在某水平上合并為一類的序號；每一行表示在某水平上合并為一類的序號； （4）作出譜系聚類圖作出譜系聚類圖 H=dendrogram(z,d) % 注意若樣本少于注意若樣本少于 30，可以省去，可以省去

46、d,否則必須填寫否則必須填寫. （5）根據(jù)分類數(shù)目，輸出聚類結(jié)果根據(jù)分類數(shù)目，輸出聚類結(jié)果 T=cluster(z,k) % 注意注意k是分類數(shù)目，是分類數(shù)目，z是（是（3） 中的結(jié)果中的結(jié)果 Find(T=k0) % 找出屬于第找出屬于第k0類的樣品編號類的樣品編號 例例5. 將例將例1 利用利用MATLAB軟件進行聚類軟件進行聚類 解：解：b=7.939.77 8.4912.94 19.27 11.052.0413.29 7.6850.37 11.3513.319.25 14.59 2.7514.87 9.4227.93 8.28.1416.17 9.421.559.76 9.1627.9

47、8 9.019.3215.99 9.11.8211.35 10.06 28.64 10.52 10.05 16.18 8.391.9610.81; 歐氏距離：歐氏距離：d1=pdist(b); %b中每行之間距離中每行之間距離 % 五種類間距離聚類五種類間距離聚類 z1=linkage(d1); z2=linkage(d1,complete); z3=linkage(d1,average); z4=linkage(d1,centroid); z5=linkage(d1,ward); 其中其中z1輸出結(jié)果為：輸出結(jié)果為： z1 = 3.0000 4.0000 2.2033 6.0000 5.00

48、00 2.2159 1.0000 2.0000 11.6726 8.0000 7.0000 12.7983 % 在在2.2033的水平，的水平，G3,G4合成一類為合成一類為G6 % 在在2.2159的水平，的水平，G6,G5合成一類為合成一類為G7 % 在在11.6726的水平，的水平，G1,G2合成一類為合成一類為G8 % 在在12.7983的水平，的水平，G7,G8合成一類合成一類 作譜系聚類圖：作譜系聚類圖：H= dendrogram(z1) % 輸出分類結(jié)果輸出分類結(jié)果 T=cluster(z1,3) T 1 2 3 3 3 圖圖2.最短距離聚類圖最短距離聚類圖 結(jié)果表明：若分為結(jié)果

49、表明：若分為 三類，則遼寧是一三類，則遼寧是一 類，浙江是一類，類，浙江是一類， 河南、青海和甘肅河南、青海和甘肅 是另一類。是另一類。 以上是樣品之間是歐氏距離，類間距離以上是樣品之間是歐氏距離，類間距離 是最短距離聚類的結(jié)果，實際上，對樣品之是最短距離聚類的結(jié)果，實際上，對樣品之 間的每一種距離，可以由五種不同的類間距間的每一種距離，可以由五種不同的類間距 離進行聚類。那么哪一種最好呢？離進行聚類。那么哪一種最好呢？為此我們?yōu)榇宋覀?可以計算復合相關系數(shù)，若該系數(shù)越接近于可以計算復合相關系數(shù)，若該系數(shù)越接近于1 則該聚類越理想。在則該聚類越理想。在MATLAB中計算復合相中計算復合相 關系

50、數(shù)的命令如下：關系數(shù)的命令如下： R=cophenet(z,d) 其中其中，z 是用某種類間距離是用某種類間距離linkage后的結(jié)果，后的結(jié)果， d是樣品之間的某種距離，是樣品之間的某種距離， 想了解利用歐氏距離聚類，那種類間距離最想了解利用歐氏距離聚類，那種類間距離最 好，可以計算五個復合相關系數(shù)：好，可以計算五個復合相關系數(shù)： R=cophenet(z1,d1),cophenet(z2,d1), cophenet(z3,d1),cophenet(z4,d1), cophenet(z5,d1) 結(jié)果為：結(jié)果為：0.8413 0.8571 0.8623 0.8622 0.8532 由于由于0

51、.8623 最大，故認為若樣品之間采用歐最大，故認為若樣品之間采用歐 氏距離，則類間距離以中間距離最好，如果我氏距離，則類間距離以中間距離最好，如果我 們要找到最理想的分類方法，可以對每一種樣們要找到最理想的分類方法，可以對每一種樣 品之間的距離，都計算上述的復合相關系數(shù)，品之間的距離，都計算上述的復合相關系數(shù)， 這樣就可以找到最理想的樣品距離與對應的類這樣就可以找到最理想的樣品距離與對應的類 間距離。間距離。 a=28 ,18,11 , 21 ,26, 20 ,16, 14, 24 ,22 29, 23, 22, 23, 29, 23, 22, 23, 29, 27 28 ,18, 16,

52、22, 26 ,22,22 ,24, 24,24; 對對a的各列進行聚類，如何計算復合相關系的各列進行聚類，如何計算復合相關系 數(shù)數(shù) d=pdist(a);pdist(a,mahal);pdist(a,cityblock); pdist(a,seuclid);pdist(a,minkowski,0.4); for i=1:5 d1=linkage(d(i,:); r1(i)=cophenet(d1,d(i,:); end for i=1:5 d2=linkage(d(i,:),complete);r2(i)=cophenet(d2,d(i,:); end for i=1:5 d3=linkag

53、e(d(i,:),average) ;r3(i)=cophenet(d3,d(i,:); end for i=1:5 d4=linkage(d(i,:),centroid);r4(i)=cophenet(d4,d(i,:); end for i=1:5 d5=linkage(d(i,:),ward);r5(i)=cophenet(d5,d(i,:); end r=r1;r2;r3;r4;r5; 4.3 快速聚類法快速聚類法 快速聚類法又稱為快速聚類法又稱為動態(tài)聚類法動態(tài)聚類法，該方法首先將樣，該方法首先將樣 品進行粗糙分類，然后依據(jù)樣品間的距離按一定規(guī)品進行粗糙分類，然后依據(jù)樣品間的距離按一定

54、規(guī) 則進行調(diào)整，直至不能調(diào)整為止則進行調(diào)整，直至不能調(diào)整為止.該方法適用于樣品該方法適用于樣品 數(shù)量較大的數(shù)據(jù)集的聚類分析，但是需要事先給定數(shù)量較大的數(shù)據(jù)集的聚類分析，但是需要事先給定 聚類數(shù)目，此數(shù)目對最終聚類結(jié)果有很大影響，實聚類數(shù)目，此數(shù)目對最終聚類結(jié)果有很大影響，實 際應用時要選擇多個數(shù)目進行分類，然后找出合理際應用時要選擇多個數(shù)目進行分類，然后找出合理 的分類結(jié)果的分類結(jié)果. 4.3.1 快速聚類的步驟快速聚類的步驟 1. 選擇聚點選擇聚點 聚點是一批有代表性的樣品，他的選擇決定了聚點是一批有代表性的樣品，他的選擇決定了 初始分類，并對最終分類有很大影響，選擇聚點初始分類，并對最終分

55、類有很大影響，選擇聚點 之前要先確定聚類數(shù)之前要先確定聚類數(shù)k. 通常，有以下確定聚點的方法：通常，有以下確定聚點的方法： 經(jīng)驗確定：對樣品非常熟悉，根據(jù)經(jīng)驗確定經(jīng)驗確定：對樣品非常熟悉，根據(jù)經(jīng)驗確定k 個樣品作為聚點個樣品作為聚點. (比如確定種子隊比如確定種子隊) 將將n個樣品隨機地分為個樣品隨機地分為k類，然后以每一類的均類，然后以每一類的均 值向量作為聚點值向量作為聚點. 最小最大原則：若最小最大原則：若n個樣品分為個樣品分為k類，先選擇所類，先選擇所 有樣品中距離最大的兩個樣品有樣品中距離最大的兩個樣品xi1, xi2為兩個初始聚為兩個初始聚 點，即點，即d(xi1,xi2)=max

56、(dij),然后選擇第然后選擇第3個聚點個聚點xi3， 使得該點到上述兩點距離最小是所有其它點到上述使得該點到上述兩點距離最小是所有其它點到上述 兩點距離最小中最大者，即兩點距離最小中最大者，即 mind(xi3,xir),r=1,2=maxmind(xj,xr),r=1,2 按照同樣的原則選取按照同樣的原則選取xi4，依次下去，直至選出，依次下去，直至選出k 個聚點個聚點xi1,xi2,xik 序號序號國家國家199019952000 1澳大利亞澳大利亞1249.391273.611282.68 2巴西巴西821.6859.85919.73 3加拿大加拿大1641.011591.541608

57、.32 4中國中國1330.451382.681462.08 5法國法國1546.551501.771525.95 6德國德國1656.521630.521570.69 7印度印度861.30862.51945.11 8意大利意大利1321.771232.31243.51 9日本日本1873.681949.891851.20 10俄羅斯俄羅斯1475.161315.871297 11南非南非794.25787.48782.38 12英國英國1486.751441.711465.12 13美國美國2824.292659.642740.12 前前 例例2中，分成中，分成4類用不同方法確定聚點類用不同方法確定聚點 人為確定：澳大利亞、中國、英國、美國人為確定：澳大利亞、中國、英國、美國 首先按照亞非洲、美洲、歐洲、大洋洲分首先按照亞非洲、美洲、歐洲、大洋洲分 為四類，以每一類的均值向量作為聚點為四類，以每一類的均值向量作為聚點. 最小最大準則最小最大準則(a為原始數(shù)據(jù)矩陣）為原始數(shù)據(jù)矩陣） m,n=size(a); for i=