交通數(shù)據(jù)處理與分析 第三章 聚類分析

聚類分析分類物以類聚、人以群分；但根據(jù)什么分類呢？如要想把中國的縣分類，就有多種方法可以按照自然條件來分，比如考慮降水、土地、日照、濕度等，也可考慮收入、教育水準(zhǔn)、醫(yī)療條件、基礎(chǔ)設(shè)施等指標(biāo)；既可以用某一項(xiàng)來分類，也可以同時(shí)考慮多項(xiàng)指標(biāo)來分類。聚類分析是研究分類問題的一種多元統(tǒng)計(jì)方法。所謂類，就是指相似元素的集合聚類分析的研究目的

把相似的東西歸成類，根據(jù)相似的程度將研究目標(biāo)進(jìn)行分類。什么是聚類分析聚類分析對(duì)一個(gè)數(shù)據(jù)，既可以對(duì)變量(指標(biāo))進(jìn)行分類(相當(dāng)于對(duì)數(shù)據(jù)中的列分類)，也可以對(duì)觀測值(事件，樣品)來分類(相當(dāng)于對(duì)數(shù)據(jù)中的行分類)。當(dāng)然，不一定事先假定有多少類，完全可以按照數(shù)據(jù)本身的規(guī)律來分類。本章要介紹的分類的方法稱為聚類分析（clusteranalysis）。聚類分析原理介紹聚類分析中“類”的特征：聚類所說的類不是事先給定的，而是根據(jù)數(shù)據(jù)的相似性和距離來劃分聚類分析原理介紹我們看看以下的例子：有16張牌如何將他們分為一組一組的牌呢？AKQJ聚類分析原理介紹分成四組每組里花色相同組與組之間花色相異AKQJ花色相同的牌為一副Individualsuits聚類分析原理介紹分成四組符號(hào)相同的牌為一組AKQJ符號(hào)相同的的牌Likefacecards聚類分析原理介紹這個(gè)例子告訴我們，分組的意義在于我們怎么定義并度量“相似性”AKQJ聚類分析的研究對(duì)象R型分析----對(duì)變量進(jìn)行分類Q型分析----對(duì)樣品進(jìn)行分類聚類分析研究的主要內(nèi)容如何度量事物之間的相似性?怎樣構(gòu)造聚類的具體方法以達(dá)到分類的目的?如何度量距離遠(yuǎn)近？如果想要對(duì)100個(gè)學(xué)生進(jìn)行分類，而僅知道他們的數(shù)學(xué)成績，則只好按照數(shù)學(xué)成績分類；這些成績在直線上形成100個(gè)點(diǎn)。這樣就可以把接近的點(diǎn)放到一類。如果還知道他們的物理成績，這樣數(shù)學(xué)和物理成績就形成二維平面上的100個(gè)點(diǎn)，也可以按照距離遠(yuǎn)近來分類。如何度量距離遠(yuǎn)近？三維或者更高維的情況也是類似；只不過三維以上的圖形無法直觀地畫出來而已。兩個(gè)距離概念按照遠(yuǎn)近程度來聚類需要明確兩個(gè)概念：一個(gè)是點(diǎn)和點(diǎn)之間的距離，一個(gè)是類和類之間的距離。點(diǎn)間距離有很多定義方式。最簡單的是歐氏距離。當(dāng)然還有一些和距離相反但起同樣作用的概念，比如相似性等，兩點(diǎn)越相似度越大，就相當(dāng)于距離越短。兩個(gè)距離概念由一個(gè)點(diǎn)組成的類是最基本的類；如果每一類都由一個(gè)點(diǎn)組成，那么點(diǎn)間的距離就是類間距離。但是如果某一類包含不止一個(gè)點(diǎn)，那么就要確定類間距離，類間距離是基于點(diǎn)間距離定義的：比如兩類之間最近點(diǎn)之間的距離可以作為這兩類之間的距離，也可以用兩類中最遠(yuǎn)點(diǎn)之間的距離或各類的中心之間的距離來作為類間距離。一、相似性的測度

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

設(shè)原始數(shù)據(jù)為明氏距離當(dāng)k＝2時(shí)，即為歐氏距離當(dāng)k＝∞時(shí)，即為切比雪夫距離123452018104471055325.236.328.911.517歐氏距離切比雪夫距離明考夫斯基距離有以下兩個(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)性的影響。年齡收入家庭人口數(shù)甲3030001乙4032003當(dāng)xi>0時(shí)(i=1,2,…,n;k=1,2,…,p)，第i個(gè)樣品Xi和Xj之間的蘭氏距離表示為蘭氏（Lance和Williams）距離蘭氏距離與各變量的單位無關(guān)，對(duì)大的異常值不敏感，故適用于高度偏斜的數(shù)據(jù)馬氏距離由印度著名統(tǒng)計(jì)學(xué)家馬哈拉諾比斯(Mahalanobis)所定義的一種距離，其計(jì)算公式為：

=馬氏距離又稱為廣義歐氏距離。馬氏距離考慮了觀測變量之間的相關(guān)性。如果假定各變量之間相互獨(dú)立，即觀測變量的協(xié)方差矩陣是對(duì)角矩陣，此時(shí)馬氏距離就是標(biāo)準(zhǔn)化的歐氏距離。馬氏距離不受指標(biāo)量綱及指標(biāo)間相關(guān)性的影響夾角余弦相似系數(shù)相關(guān)系數(shù)相似系數(shù)由相似系數(shù)還可定義變量之間的距離相似系數(shù)間隔尺度變量變量用連續(xù)的量來表示，如長度、重量、速度、流量有序尺度變量變量度量時(shí)不用明確的數(shù)量表示，而是用等級(jí)來表示，如產(chǎn)品的等級(jí)，交通的擁堵程度等。名義尺度變量變量用一些類表示，這些類之間既無等級(jí)關(guān)系，也無數(shù)量關(guān)系，如性別，車型等。變量類型系統(tǒng)聚類法系統(tǒng)聚類法的基本思想

先將n個(gè)樣品各自看成一類，然后規(guī)定樣品之間的“距離”和類與類之間的距離。選擇距離最近的兩類合并成一個(gè)新類，計(jì)算新類和其它類（各當(dāng)前類）的距離，再將距離最近的兩類合并。這樣，每次合并減少一類，直至所有的樣品都?xì)w成一類為止。最終形成一個(gè)親疏關(guān)系圖譜（聚類樹形圖或譜系圖），通常從圖上可清洗地看出應(yīng)分為幾類以及每一類中所包含的樣品（或變量）。除此之外也可借助統(tǒng)計(jì)量確定分類結(jié)果系統(tǒng)聚類法的基本思想在聚類分析中，通常用G表示類，將定G中有m個(gè)元素（即樣品或變量），不失一般化，用列向量xi（i=1，2，…，m）來表示，dij表示元素xi與xj之間的距離。DKL表示類GK與GL之間的距離。類與類之間用不同的方法定義距離，產(chǎn)生了以下不同的系統(tǒng)聚類方法系統(tǒng)聚類法的基本思想

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

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

上述6種方法歸類的基本步驟一致，只是類與類之間的距離有不同的定義。定義類p與q之間的距離為兩類最近樣品的距離，即xq1?xp2?xq2?xp1?xq3?最短距離法設(shè)類p與q合并成一個(gè)新類，記為k，則k與任一類r的距離是pqkr定義類與類之間的距離為兩類最近樣品間的距離，即最短距離法若某一步類GK與類GL聚成一個(gè)新類，記為GM，類GM與任意已有的類GJ之間的距離為聚類步驟如下將初始的每個(gè)樣品（或變量）各自作為一類，并規(guī)定樣品（或變量）之間的距離，通常采用歐式距離。計(jì)算n個(gè)樣品（或p個(gè)變量）的距離矩陣D(0)，它是一個(gè)對(duì)稱矩陣。尋找D(0)中最小元素，設(shè)為DKL，將GK和GL聚成一個(gè)新類，記為GM，即GM={GK，GL}計(jì)算新類GM與任一類GJ之間距離的遞推公式為最短距離法對(duì)距離矩陣D(0)進(jìn)行修改，將GK和GL所在的行和列合并成一個(gè)新行新列，對(duì)應(yīng)GM，新行和新列上的新距離由上式計(jì)算，其余行列上的值不變，這樣得到新的距離矩陣記為D(1)對(duì)D(1)重復(fù)上述對(duì)D(0)的操作，得到距離矩陣D(2)，如此進(jìn)行下去，直至所有元素合并成一類為止。最短距離法設(shè)有5個(gè)樣品，每個(gè)只測量了一個(gè)指標(biāo)，指標(biāo)值分別是1,2,6,8,11.若樣品間采用絕對(duì)值距離，下面用最短距離法對(duì)這五個(gè)樣品進(jìn)行聚類，過程如下將五個(gè)樣品各自作為一類，分別記為G1,G2,G3,G4,G5。計(jì)算樣品間的初始距離矩陣D(0)，如下表所示最短距離法G1G2G3G4G5G10G210G3540G47620G5109530D(0)中最小元素是D12=1，于是將G1和G2合并成G6，得到距離矩陣D(1)最短距離法

G6G3G4G5G60G340G4620G59530D(1)中最小元素是D34=2，于是將G3和G4合并成G7，得到距離矩陣D(2)最短距離法G6G7G5G60G740G5930D(2)中最小元素是D57=3，于是將G5和G7合并成G8，得到距離矩陣D(3)最短距離法G6G8G60G840最后將G6和G8合并成G9，這是所有五個(gè)樣品聚為一類，聚類結(jié)束。例

最短距離法

設(shè)抽取5個(gè)樣品，每個(gè)樣品觀察2個(gè)指標(biāo)，：某路段上年均交通事故發(fā)生數(shù)：某路段上年均因交通事故受傷人數(shù)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

②③④⑤①②③④3.610.216.1216.499.4314.8715.6566.32

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

3、計(jì)算新類⑥與各當(dāng)前類的距離，得距離矩陣如下：②③⑥①②③

3.6

10.216.499.4315.656.32為最小，⑦=⑥⑦③⑥6.32

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

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

觀察此圖，我們可以把5個(gè)樣品分為3類，、、。三、中間距離法定義類與類之間的距離既不采用兩類之間最近的距離，也不采用兩類之間最遠(yuǎn)的距離，而是采用介于兩者之間的距離，故稱為中間距離法。???rpqk

②③④⑤①②③④13104260272892212453640

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

3、計(jì)算新類⑥與各當(dāng)前類的距離，得距離矩陣如下：②③⑥①②③

13

1042658923237為最小，⑦=⑥⑦③⑥

37

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

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

觀察此圖，我們可以把5個(gè)樣品分為3類，、、。四、重心法（Centroid)??和類與類之間的距離就考慮用重心之間的距離表示。設(shè)p與q的重心分別是，則類p和q的距離為將p和q合并為k，則k類的樣品個(gè)數(shù)為它的重心是某一類r的重心是，它與新類k的距離是經(jīng)推導(dǎo)可以得到如下遞推公式：設(shè)聚類到某一步，類p與q分別有樣品

、個(gè)，

②③④⑤①②③④13104260272892212453640

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

3、計(jì)算新類⑥與各當(dāng)前類的距離，得距離矩陣如下：②③⑥①②③

13

1042658923237為最小，⑦=⑥⑦③⑥

37

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

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

觀察此圖，我們可以把5個(gè)樣品分為3類，、、。五、類平均法（Average)定義兩類之間的距離平方為這兩類元素兩兩之間距離平方的平均?????pq將p和q合并為k，則k類的樣品個(gè)數(shù)為設(shè)聚類到某一步，類p與q分別有樣品、個(gè)，k類與任一類r的距離為

②③④⑤①②③④13104260272892212453640

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

3、計(jì)算新類⑥與各當(dāng)前類的距離，得距離矩陣如下：②③⑥①②③

13

1042668923338為最小，⑦=⑥⑦③⑥

38

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

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

觀察此圖，我們可以把5個(gè)樣品分為3類，、、。系統(tǒng)聚類法的不同之處在于類間距離的計(jì)算方法不同，Wishart將不同的距離計(jì)算公式統(tǒng)一為系統(tǒng)聚類法的統(tǒng)一同樣的觀測數(shù)據(jù)，應(yīng)用不同的聚類方法進(jìn)行聚類，可能得到不同的結(jié)果。通常從兩個(gè)方面進(jìn)行評(píng)價(jià)單調(diào)性空間的濃縮與擴(kuò)張系統(tǒng)聚類法的評(píng)價(jià)單調(diào)性令Di是系統(tǒng)聚類過程中第i次并類時(shí)的距離，若有D1≤D2≤…≤Di，則成次系統(tǒng)聚類法具有單調(diào)性。在上述聚類方法中，最短距離法、最長距離法、中間距離法、類平均法和離散平方和法具有單調(diào)性，而中間距離法和重心法不具有單調(diào)性。系統(tǒng)聚類法的評(píng)價(jià)空間的濃縮與擴(kuò)張針對(duì)同一問題，用不同系統(tǒng)聚類法進(jìn)行聚類，做出的聚類樹形圖的橫坐標(biāo)（并類距離）的范圍相差很大。范圍小的方法區(qū)別類的靈敏度差，而范圍太大的方法靈敏度又過高設(shè)有甲、乙兩類聚類方法，第i步的距離矩陣分別為Ai和Bi，若Ai≥Bi，則稱甲方法比乙方法更使空間擴(kuò)張，或稱乙方法比甲方法更使空間濃縮。系統(tǒng)聚類法的評(píng)價(jià)與類平均法相比，最短距離法和重心法使空間濃縮，最長距離法和離差平方和法是空間擴(kuò)張。太濃縮的方法不夠靈敏，太擴(kuò)張的方法又容易失真，而類平均法相對(duì)比較適中。系統(tǒng)聚類法的評(píng)價(jià)PdistY=pdist（X）計(jì)算樣品對(duì)的歐式距離。輸入?yún)?shù)X是nхp的矩陣，矩陣的每一行對(duì)應(yīng)一個(gè)樣品，每一列對(duì)應(yīng)一個(gè)變量。輸出參數(shù)Y是包含n(n-1)/2個(gè)元素的行向量，用(i,j)表示第i個(gè)樣品和第j個(gè)樣品構(gòu)成的樣品對(duì)，則Y中的元素依次是(2,1),(3,1),…,(n,1),(3,2),…,(n,2),…,(n,n-1)系統(tǒng)聚類法的相關(guān)函數(shù)Y=pdist（X,metric）輸入?yún)?shù)metric指定計(jì)算距離的方法，metric為字符串，可用的字符串如下表所示。系統(tǒng)聚類法的相關(guān)函數(shù)Metric參數(shù)值說明‘euclidean’歐式距離‘seuclidean’標(biāo)準(zhǔn)化歐式距離‘mahalanobis’馬哈拉諾比斯距離‘cityblock’絕對(duì)值距離‘minkowski’閔可夫斯基距離‘chebychev’切比雪夫距離Y=pdist（X,‘minkowski’,p）計(jì)算樣品對(duì)的閔可夫斯基距離，輸入?yún)?shù)p為閔可夫斯基距離計(jì)算中的指數(shù)，默認(rèn)情況下，指數(shù)為2系統(tǒng)聚類法的相關(guān)函數(shù)SquareformZ=squareform(y)Z=squareform(y,‘tomatrix’)y=squareform(Z)y=squareform(Z,‘tovector’)前兩種調(diào)用時(shí)把pdist函數(shù)輸出的距離向量y轉(zhuǎn)為距離矩陣Z，而后兩種調(diào)用則是把距離矩陣Z轉(zhuǎn)換為pdist函數(shù)輸出的距離向量y。系統(tǒng)聚類法的相關(guān)函數(shù)Linkage函數(shù)Z=linkage（y）利用最短距離法創(chuàng)建一個(gè)系統(tǒng)聚類樹。輸入?yún)?shù)y是樣品對(duì)距離向量，是包含n(n-1)/2個(gè)元素的行向量，通常是pdist函數(shù)的輸出。輸出Z是一個(gè)系統(tǒng)聚類樹矩陣，它是(n-1)*3的矩陣，這里的n是原始數(shù)據(jù)中觀測樣品的個(gè)數(shù)。Z矩陣每一行對(duì)應(yīng)一次并類，第i行上前兩個(gè)元素為第i次并類的兩個(gè)類的類編號(hào)，初始類編號(hào)為1~n，以后每形成一個(gè)新類，類編號(hào)從n+1開始逐次增加1.Z矩陣的第i行中的第3個(gè)元素為第i次并類是的并類距離系統(tǒng)聚類法的相關(guān)函數(shù)Z=linkage（y,method）利用method參數(shù)制定的方法創(chuàng)建系統(tǒng)聚類樹，method是字符串，可用的字符串如下所示系統(tǒng)聚類法的相關(guān)函數(shù)Method參數(shù)值說明‘a(chǎn)verage’類平均法‘centroid’重心法‘complete’最長距離法‘median’中間距離法‘single’最短距離法‘ward’離差平方和法‘weighted’可變類平均法Z=linkage（y,method,metric）metric用來制定計(jì)算距離的方法系統(tǒng)聚類法的相關(guān)函數(shù)Dendrogram函數(shù)H=dendrogram（Z）由系統(tǒng)聚類樹矩陣Z生成系統(tǒng)聚類樹形圖。輸入?yún)?shù)Z是由linkage函數(shù)輸出的系統(tǒng)聚類樹矩陣。輸出參數(shù)H是樹形圖中線條的句柄值向量，用來控制線條屬性。系統(tǒng)聚類法的相關(guān)函數(shù)H=dendrogram（Z，p）生成一個(gè)樹形圖，通過輸入?yún)?shù)p來控制顯示的葉節(jié)點(diǎn)數(shù)。系統(tǒng)聚類法的相關(guān)函數(shù)H=dendrogram（…,‘orientation’,‘orient’）通過設(shè)定’orientation’參數(shù)及參數(shù)值’orient’來控制聚類樹形圖的方向和放著葉節(jié)點(diǎn)標(biāo)簽的位置，可用參數(shù)如下所示參數(shù)值說明‘top’從上至下，葉節(jié)點(diǎn)標(biāo)簽在下方，為默認(rèn)情況‘bottom’從下至上，葉節(jié)點(diǎn)標(biāo)簽在上方‘left’從左至右，葉節(jié)點(diǎn)標(biāo)簽在右邊‘right’從右至左，葉節(jié)點(diǎn)標(biāo)簽在左邊H=dendrogram（…,‘labels’,S）通過一個(gè)字符串?dāng)?shù)組或字符串元胞數(shù)組設(shè)定每一個(gè)觀測值的標(biāo)簽。當(dāng)樹形圖中顯示了全部的葉節(jié)點(diǎn)時(shí)，葉節(jié)點(diǎn)的標(biāo)簽記為相應(yīng)觀測的標(biāo)簽；當(dāng)樹形圖中忽略了某些節(jié)點(diǎn)時(shí)，只包含單個(gè)觀測的葉節(jié)點(diǎn)的標(biāo)簽記為相應(yīng)觀測的標(biāo)簽。系統(tǒng)聚類法的相關(guān)函數(shù)Cophenet函數(shù)Cophenet函數(shù)用來計(jì)算系統(tǒng)聚類樹的cophenetic相關(guān)系數(shù)Cophenetic相關(guān)系數(shù)反映了聚類效果的好壞，cophenetic相關(guān)系數(shù)越接近于1，