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

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

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

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

設(shè)原始數(shù)據(jù)為明氏距離當k＝2時，即為歐氏距離當k＝∞時，即為切比雪夫距離123452018104471055325.236.328.911.517歐氏距離切比雪夫距離明考夫斯基距離有以下兩個缺點：①明氏距離的數(shù)值與指標的量綱有關(guān)。當各變量的測量值相差懸殊時，常發(fā)生“大數(shù)吃小數(shù)”的現(xiàn)象，為消除量綱的影響，通常先將每個變量進行標準化。②明氏距離的定義沒有考慮各個變量之間相關(guān)性的影響。年齡收入家庭人口數(shù)甲3030001乙4032003當xi>0時(i=1,2,…,n;k=1,2,…,p)，第i個樣品Xi和Xj之間的蘭氏距離表示為蘭氏（Lance和Williams）距離蘭氏距離與各變量的單位無關(guān)，對大的異常值不敏感，故適用于高度偏斜的數(shù)據(jù)馬氏距離由印度著名統(tǒng)計學(xué)家馬哈拉諾比斯(Mahalanobis)所定義的一種距離，其計算公式為：

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

先將n個樣品各自看成一類，然后規(guī)定樣品之間的“距離”和類與類之間的距離。選擇距離最近的兩類合并成一個新類，計算新類和其它類（各當前類）的距離，再將距離最近的兩類合并。這樣，每次合并減少一類，直至所有的樣品都歸成一類為止。最終形成一個親疏關(guān)系圖譜（聚類樹形圖或譜系圖），通常從圖上可清洗地看出應(yīng)分為幾類以及每一類中所包含的樣品（或變量）。除此之外也可借助統(tǒng)計量確定分類結(jié)果系統(tǒng)聚類法的基本思想在聚類分析中，通常用G表示類，將定G中有m個元素（即樣品或變量），不失一般化，用列向量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合并成一個新類，記為k，則k與任一類r的距離是pqkr定義類與類之間的距離為兩類最近樣品間的距離，即最短距離法若某一步類GK與類GL聚成一個新類，記為GM，類GM與任意已有的類GJ之間的距離為聚類步驟如下將初始的每個樣品（或變量）各自作為一類，并規(guī)定樣品（或變量）之間的距離，通常采用歐式距離。計算n個樣品（或p個變量）的距離矩陣D(0)，它是一個對稱矩陣。尋找D(0)中最小元素，設(shè)為DKL，將GK和GL聚成一個新類，記為GM，即GM={GK，GL}計算新類GM與任一類GJ之間距離的遞推公式為最短距離法對距離矩陣D(0)進行修改，將GK和GL所在的行和列合并成一個新行新列，對應(yīng)GM，新行和新列上的新距離由上式計算，其余行列上的值不變，這樣得到新的距離矩陣記為D(1)對D(1)重復(fù)上述對D(0)的操作，得到距離矩陣D(2)，如此進行下去，直至所有元素合并成一類為止。最短距離法設(shè)有5個樣品，每個只測量了一個指標，指標值分別是1,2,6,8,11.若樣品間采用絕對值距離，下面用最短距離法對這五個樣品進行聚類，過程如下將五個樣品各自作為一類，分別記為G1,G2,G3,G4,G5。計算樣品間的初始距離矩陣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，這是所有五個樣品聚為一類，聚類結(jié)束。例

最短距離法

設(shè)抽取5個樣品，每個樣品觀察2個指標，：某路段上年均交通事故發(fā)生數(shù)：某路段上年均因交通事故受傷人數(shù)1234520181044710553

②③④⑤①②③④3.610.216.1216.499.4314.8715.6566.32

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

3.6

10.216.129.4314.876為最小，⑦=⑥⑦③⑥

6

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

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

觀察此圖，我們可以把5個樣品分為3類，、、。???x11?x21????二、最長距離法定義類p與q之間的距離為兩類最遠樣品的距離，即設(shè)類p與q合并成一個新類，記為k，則k與任一類r的距離是pqkr

②③④⑤①②③④3.610.216.1216.499.4314.8715.6566.32

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

3、計算新類⑥與各當前類的距離，得距離矩陣如下：②③⑥①②③

3.6

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

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

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

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

②③④⑤①②③④13104260272892212453640

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

3、計算新類⑥與各當前類的距離，得距離矩陣如下：②③⑥①②③

13

1042658923237為最小，⑦=⑥⑦③⑥

37

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

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

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

、個，

②③④⑤①②③④13104260272892212453640

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

3、計算新類⑥與各當前類的距離，得距離矩陣如下：②③⑥①②③

13

1042658923237為最小，⑦=⑥⑦③⑥

37

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

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

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

②③④⑤①②③④13104260272892212453640

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

3、計算新類⑥與各當前類的距離，得距離矩陣如下：②③⑥①②③

13

1042668923338為最小，⑦=⑥⑦③⑥

38

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

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

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