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

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

2、分類。對一個數(shù)據(jù)，既可以對變量對一個數(shù)據(jù)，既可以對變量( (指標指標) )進行進行分類分類( (相當于對數(shù)據(jù)中的列分類相當于對數(shù)據(jù)中的列分類) )，也可，也可以對觀測值以對觀測值( (事件，樣品事件，樣品) )來分類來分類( (相當相當于對數(shù)據(jù)中的行分類于對數(shù)據(jù)中的行分類) )。當然，不一定事先假定有多少類，完當然，不一定事先假定有多少類，完全可以按照數(shù)據(jù)本身的規(guī)律來分類。全可以按照數(shù)據(jù)本身的規(guī)律來分類。本章要介紹的分類的方法稱為聚類分本章要介紹的分類的方法稱為聚類分析（析（cluster analysiscluster analysis）。）。聚類分析中“類”的特征： 聚類所說的類不是事先給

3、定的，而是根據(jù)數(shù)據(jù)的相似性和距離來劃分我們看看以下的例子：有16張牌如何將他們分為 一組一組的牌呢？AKQJ分成四組每組里花色相同組與組之間花色相異AKQJ花色相同的牌為一副花色相同的牌為一副Individual suits分成四組符號相同的牌為一組AKQJ符號相同的的牌符號相同的的牌Like face cards這個例子告訴我們，分組的意義在于我們怎么定義并度量“相似性”AKQJ聚類分析的研究對象 R型分析-對變量進行分類 Q型分析-對樣品進行分類聚類分析研究的主要內(nèi)容n如何度量事物之間的相似性 ?n怎樣構(gòu)造聚類的具體方法以達到分類的目的?如果想要對如果想要對100100個學(xué)生進行分類，個學(xué)

4、生進行分類，而僅知道他們的數(shù)學(xué)成績，則只好而僅知道他們的數(shù)學(xué)成績，則只好按照數(shù)學(xué)成績分類；這些成績在直按照數(shù)學(xué)成績分類；這些成績在直線上形成線上形成100100個點。這樣就可以把個點。這樣就可以把接近的點放到一類。接近的點放到一類。如果還知道他們的物理成績，這樣如果還知道他們的物理成績，這樣數(shù)學(xué)和物理成績就形成二維平面上數(shù)學(xué)和物理成績就形成二維平面上的的100100個點，也可以按照距離遠近個點，也可以按照距離遠近來分類。來分類。三維或者更高維的情況也是類似；三維或者更高維的情況也是類似；只不過三維以上的圖形無法直觀地只不過三維以上的圖形無法直觀地畫出來而已。畫出來而已。 按照遠近程度來聚類需要

5、明確兩按照遠近程度來聚類需要明確兩個概念：一個是個概念：一個是點和點之間點和點之間的距的距離，一個是離，一個是類和類之間類和類之間的距離。的距離。點間距離點間距離有很多定義方式。最簡有很多定義方式。最簡單的是歐氏距離。單的是歐氏距離。當然還有一些和距離相反但起同當然還有一些和距離相反但起同樣作用的概念，比如相似性等，樣作用的概念，比如相似性等，兩點越相似度越大，就相當于距兩點越相似度越大，就相當于距離越短。離越短。由一個點組成的類是最基本的類；如由一個點組成的類是最基本的類；如果每一類都由一個點組成，那么點間果每一類都由一個點組成，那么點間的距離就是類間距離。但是如果某一的距離就是類間距離。但

6、是如果某一類包含不止一個點，那么就要確定類類包含不止一個點，那么就要確定類間距離，間距離，類間距離類間距離是基于點間距離定義的：比是基于點間距離定義的：比如如兩類之間最近點之間的距離兩類之間最近點之間的距離可以作可以作為這兩類之間的距離，也可以用為這兩類之間的距離，也可以用兩類兩類中最遠點之間的距離中最遠點之間的距離或各類的中心之或各類的中心之間的距離來作為類間距離。間的距離來作為類間距離。距離距離：測度樣品之間的親疏程度。將每一個樣品看作p 維空間的一個點，并用某種度量測量點與點之間的距離，距離較近的歸為一類，距離較遠的點應(yīng)屬于不同的類。相似系數(shù)相似系數(shù)：測度變量之間的親疏程度距離距離和相似

7、系數(shù)和相似系數(shù)kplkjlilijxxd11)|(pljlilijxxd1明氏距離明氏距離特別地，當k1時，即為絕對值距離絕對值距離(1) (1) 明氏距離（明氏距離（Minkowski）ixjxijd令表示樣品與的距離 npnnppxxxxxxxxx212222111211設(shè)原始數(shù)據(jù)為kplkjlilijxxd11)|(pljlilijxxd12)(明氏距離明氏距離當k2時，即為歐氏距離歐氏距離當k時，即為切比雪夫距離切比雪夫距離jlilplijxxd1max123452018104471055325.236.328.911.5171x2x3x3124224)(lllxxd222)5 .11

8、3 .36()510()418(歐氏距離歐氏距離切比雪夫距離切比雪夫距離lllxxd423124max8 .245 .113 .3624d計算 明氏距離的數(shù)值與指標的量綱量綱有關(guān)。當各變量的測量值相差懸殊時，常發(fā)生“大數(shù)吃小數(shù)”的現(xiàn)象，為消除量綱的影響，通常先將每個變量進行標準化。 明氏距離的定義沒有考慮各個變量之間相關(guān)性的影響。年齡收入家庭人口數(shù)甲3030001乙4032003222) 31 ()32003000()4030(d 當xi0時(i=1,2,n; k= 1,2, p)，第i個樣品Xi和Xj之間的蘭氏距離表示為( )1,1,2,., ;1,2,.,pikjkijkikjkxxdLi

9、njnxx=-=+ 蘭氏距離與各變量的單位無關(guān)，對大的異常值不敏感，故適用于高度偏斜的數(shù)據(jù)馬氏距離馬氏距離 由印度著名統(tǒng)計學(xué)家馬哈拉諾比斯(Mahalanobis)所定義的一種距離，其計算公式為： ijd21221112211,pjpijijipjpijijixxxxxxSxxxxxx =211jijixxSxxn馬氏距離又稱為廣義歐氏距離。n馬氏距離考慮了觀測變量之間的相關(guān)性。如果假定各變量之間相互獨立，即觀測變量的協(xié)方差矩陣是對角矩陣，此時馬氏距離就是標準化的歐氏距離。n馬氏距離不受指標量綱量綱及指標間指標間相關(guān)性相關(guān)性的影響 夾角余弦()11 222111,1,2,., ;1,2,.,n

10、kikjkijnnkikjkkx xCip jpxx=輊驏驏鼢瓏犏鼢瓏鼢犏瓏鼢桫桫臌邋相關(guān)系數(shù)( )()()()()122112,1,2,. ;1,2,.nkiikjiknnkiikjjkkxxxxCin jnxxxx=-=輊輊犏犏-犏犏臌臌邋1111,1,2,., ;1,2,.,nnikijkjkkxxxxin jnnn=邋由相似系數(shù)還可定義變量之間的距離11,2,., ;1,2,.,ijijdCin jn=-=間隔尺度變量 變量用連續(xù)的量來表示，如長度、重量、速度、流量有序尺度變量 變量度量時不用明確的數(shù)量表示，而是用等級來表示，如產(chǎn)品的等級，交通的擁堵程度等。名義尺度變量 變量用一些類表

11、示，這些類之間既無等級關(guān)系，也無數(shù)量關(guān)系，如性別，車型等。系統(tǒng)聚類法的基本思想系統(tǒng)聚類法的基本思想 先將n個樣品各自看成一類，然后規(guī)定樣品之間的“距離”和類與類之間的距離。選擇距離最近距離最近的兩類合并成一個新類，計算新類和其它類（各當前類）的距離，再將距離最近的兩類合并。這樣，每次合并減少一類，直至所有的樣品都歸成一類為直至所有的樣品都歸成一類為止止。 最終形成一個親疏關(guān)系圖譜（聚類樹形圖或譜系圖），通常從圖上可清洗地看出應(yīng)分為幾類以及每一類中所包含的樣品（或變量）。除此之外也可借助統(tǒng)計量確定分類結(jié)果在聚類分析中，通常用G表示類，將定G中有m個元素（即樣品或變量），不失一般化，用列向量xi（

12、i = 1，2，m）來表示，dij表示元素xi與xj之間的距離。DKL表示類GK與GL之間的距離。類與類之間用不同的方法定義距離，產(chǎn)生了以下不同的系統(tǒng)聚類方法1. 最短距離法2. 最長距離法3. 中間距離法4. 重心法5. 類平均法 6.6. 離差平方和法（離差平方和法（WardWard法法）系統(tǒng)聚類方法：系統(tǒng)聚類方法： 上述 6 種方法歸類的基本步驟一致基本步驟一致，只是類與類之間的距離類與類之間的距離有不同的定義。定義類p與q之間的距離為兩類最近樣品的距離，即 ,minpqijip j qDd撾=xq1xp2xq2xp1pqDxq3最短距離法最短距離法min,krprqrDDD=設(shè)類p與

13、q合并成一個新類，記為k，則k與任一類r 的距離是pqkr定義類與類之間的距離為兩類最近樣品間的距離，即min:,KLijiKjKDdxGxG=撾若某一步類GK與類GL聚成一個新類，記為GM，類GM與任意已有的類GJ之間的距離為min,MJKJLJDDDJK L=聚類步驟如下將初始的每個樣品（或變量）各自作為一類，并規(guī)定樣品（或變量）之間的距離，通常采用歐式距離。計算n個樣品（或p個變量）的距離矩陣D(0)，它是一個對稱矩陣。尋找D(0)中最小元素，設(shè)為DKL，將GK和GL聚成一個新類，記為GM，即GM=GK，GL計算新類GM與任一類GJ之間距離的遞推公式為,minminmin,minmin,

14、iMjJikjJiLjJMJijijijKJLJxGxGxGxGxGxGDdddDD撾撾撾=對距離矩陣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)，如下

15、表所示G1G1G2G2G3G3G4G4G5G5G10G210G3540G47620G5109530D(0)中最小元素是D12=1，于是將G1和G2合并成G6，得到距離矩陣D(1)G6G6G3G3G4G4G5G5G60G340G4620G59530D(1)中最小元素是D34=2，于是將G3和G4合并成G7，得到距離矩陣D(2)G6G6G7G7G5G5G60G740G5930D(2)中最小元素是D57=3，于是將G5和G7合并成G8，得到距離矩陣D(3)G6G6G8G8G60G840最后將G6和G8合并成G9，這是所有五個樣品聚為一類，聚類結(jié)束。例例 最短距離法最短距離法 設(shè)抽取5個樣品，每個樣品

16、觀察2個指標 ， ：某路段上年均交通事故發(fā)生數(shù) ：某路段上年均因交通事故受傷人數(shù)1x2x12345201810447105531x2x 3.6 10.2 16.12 16.49 9.43 14.87 15.65 6 6.32 2ijdnnijdD)(1.計算5個樣品兩兩之間的距離記為距離矩陣（采用歐氏距離），452D=為最小，2. 合并距離最小的兩類為新類，按順序定為第類。5 , 4624252min,min 14.87,15.6514.87Ddd=634353min,6Ddd=614151min,min 16.12,16.4916.12Ddd=3、計算新類與各當前類的距離，得距離矩陣如下：3

17、.6 10.2 16.12 9.43 14.87 6731323min,9.43Ddd=761626min,14.87Ddd=6 . 312d 2 , 1為最小， = 6 9 .43 14.87 4、重復(fù)步驟2、3，合并距離最近的兩類為新類，直到所有的類并為一類為止。 43. 9,min673787ddd 636d6 , 3為最小，=5、6、按聚類的過程畫聚類譜系圖 45并類距離3127、決定類的個數(shù)與類。 觀察此圖，我們可以把5個樣品分為3類， 2 , 1 35 , 4、。43. 966 . 328 ,76, 32, 15 , 4ddddx11x2112d二、最長距離法二、最長距離法定義類p

18、與q之間的距離為兩類最遠樣品的距離，即 ijqjpipqdd,max設(shè)類p與 q合并成一個新類，記為k，則k與任一類r 的距離是pqkrqrprkrddd,max 3.6 10.2 16.12 16.49 9.43 14.87 15.65 6 6.32 2ijdnnijdD)(1.計算5個樣品兩兩之間的距離記為距離矩陣（采用歐氏距離），為最小，245d2. 合并距離最小的兩類為新類，按順序定為第類。5 , 4例例 最長距離法最長距離法 65.1565.15,87.14max,max524262ddd32. 6,max534363ddd49.1649.16,12.16max,max514161d

19、dd3、計算新類與各當前類的距離，得距離矩陣如下：3.6 10.2 16.49 9.43 15.65 6.322 .10,max231373ddd49.16,max261676ddd6 . 312d 2 , 1為最小， = 6.32 10 .2 16.494、重復(fù)步驟2、3，合并距離最近的兩類為新類，直到所有的類并為一類為止。 49.16,max673787ddd 32. 636d6 , 3為最小，=5、6、按聚類的過程畫聚類譜系圖 45并類距離3127、決定類的個數(shù)與類。 觀察此圖，我們可以把5個樣品分為3類， 2 , 1 35 , 4、。49.1632. 66 . 328 ,76, 32,

20、 15 , 4dddd三、中間距離法三、中間距離法定義類與類之間的距離既不采用兩類之間最近的距離，也不采用兩類之間最遠的距離，而是采用介于兩者之間的距離，故稱為中間距離法。 krdr rp pq qk k2222412121pqqrprkrdddd 13 104 260 272 89 221 245 36 40 4ijdnnijdD)(1.計算5個樣品兩兩之間的距離記為距離矩陣（采用歐氏距離），為最小，4245d2. 合并距離最小的兩類為新類，按順序定為第類。5 , 4例例 中間距離法中間距離法 2ijd3、計算新類與各當前類的距離，得距離矩陣如下： 13 104 265 89 232 372

21、654412722126021412121245251241261dddd2324412452122121412121245252242262dddd3744140213621412121245253243263dddd2ijd13212d 2 , 1為最小， = 37 93.25 245.25 4、重復(fù)步驟2、3，合并距離最近的兩類為新類，直到所有的類并為一類為止。 37236d6 , 3為最小，=5、25.931341892110421412121212223213273dddd25.24513412322126521412121212226216276dddd2ijd160374125.

22、2452125.9321412121236267237287dddd6、按聚類的過程畫聚類譜系圖 45并類距離3127、決定類的個數(shù)與類。 觀察此圖，我們可以把5個樣品分為3類， 2 , 1 35 , 4、。65.1208. 66 . 328 ,76, 32, 15 , 4dddd四、重心法四、重心法（Centroid)11,x y22,xypx和qxqpxxpqdd類與類之間的距離就考慮用重心之間的距離表示。設(shè)p與q的重心分別是，則類p和q的距離為qpknnnqqppkkxnxnnx1rkrkkrxxxxd22222pqkqkpqrkqprkpkrdnnnndnndnnd將p和q合并為k，則

23、k類的樣品個數(shù)為它的重心是rx某一類 r 的重心是，它與新類k的距離是經(jīng)推導(dǎo)可以得到如下遞推公式：pnqn設(shè)聚類到某一步，類p與 q分別有樣品 、個， 13 104 260 272 89 221 245 36 40 4ijdnnijdD)(1.計算5個樣品兩兩之間的距離記為距離矩陣（采用歐氏距離），為最小，4245d2. 合并距離最小的兩類為新類，按順序定為第類。5 , 4例例 重心法重心法 2ijd3、計算新類與各當前類的距離，得距離矩陣如下： 13 104 265 89 232 372654412722126021412121245251241261dddd2324412452122121

24、412121245252242262dddd3744140213621412121245253243263dddd2ijd13212d 2 , 1為最小， = 37 93.25 245.25 4、重復(fù)步驟2、3，合并距離最近的兩類為新類，直到所有的類并為一類為止。 37236d6 , 3為最小，=5、25.931341892110421412121212223213273dddd25.24513412322126521412121212226216276dddd2ijd36.186379225.2453225.9331923231236267237287dddd6、按聚類的過程畫聚類譜系圖 4

25、5并類距離3127、決定類的個數(shù)與類。 觀察此圖，我們可以把5個樣品分為3類， 2 , 1 35 , 4、。65.1308. 66 . 328 ,76, 32, 15 , 4dddd五、類平均法五、類平均法（Average)定義兩類之間的距離平方為這兩類元素兩兩之間距離平方的平均 piqjijqppqdnnd221p pq qqpknnn將p和q合并為k，則k類的樣品個數(shù)為pnqn設(shè)聚類到某一步，類p與 q分別有樣品、個，rikjijrkkrdnnd221ripjriqjijijrkddnn221)(122qrrqprrprkdnndnnnnk類與任一類 r 的距離為22qrkqprkpdnn

26、dnn 13 104 260 272 89 221 245 36 40 4ijdnnijdD)(1.計算5個樣品兩兩之間的距離記為距離矩陣（采用歐氏距離），為最小，4245d2. 合并距離最小的兩類為新類，按順序定為第類。5 , 4例例 類平均法類平均法 2ijd3、計算新類與各當前類的距離，得距離矩陣如下： 13 104 266 89 233 3826627221260212121251241261ddd23324521221212121252242262ddd38402136212121253243263ddd2ijd13212d 2 , 1為最小， = 38 96.5 249.5 4、重

27、復(fù)步驟2、3，合并距離最近的兩類為新類，直到所有的類并為一類為止。 38236d6 , 3為最小，=5、5 .968921104212121223213273ddd5 .24923221265212121226216276ddd2ijd5 .19825.2453225.93313231267237287ddd6、按聚類的過程畫聚類譜系圖 45并類距離3127、決定類的個數(shù)與類。 觀察此圖，我們可以把5個樣品分為3類， 2 , 1 35 , 4、。09.1416. 66 . 328 ,76, 32, 15 , 4dddd系統(tǒng)聚類法的不同之處在于類間距離的計算方法不同，Wishart將不同的距離計

28、算公式統(tǒng)一為222222MJKKJLLJKLKJLJDDDDDDaabg=+同樣的觀測數(shù)據(jù)，應(yīng)用不同的聚類方法進行聚類，可能得到不同的結(jié)果。通常從兩個方面進行評價 單調(diào)性 空間的濃縮與擴張單調(diào)性 令Di是系統(tǒng)聚類過程中第i次并類時的距離，若有D1D2 Di，則成次系統(tǒng)聚類法具有單調(diào)性。在上述聚類方法中，最短距離法、最長距離法、中間距離法、類平均法和離散平方和法具有單調(diào)性，而中間距離法和重心法不具有單調(diào)性?？臻g的濃縮與擴張針對同一問題，用不同系統(tǒng)聚類法進行聚類，做出的聚類樹形圖的橫坐標（并類距離）的范圍相差很大。范圍小的方法區(qū)別類的靈敏度差，而范圍太大的方法靈敏度又過高設(shè)有甲、乙兩類聚類方法，第

29、i步的距離矩陣分別為Ai和Bi，若AiBi，則稱甲方法比乙方法更使空間擴張，或稱乙方法比甲方法更使空間濃縮。與類平均法相比，最短距離法和重心法使空間濃縮，最長距離法和離差平方和法是空間擴張。太濃縮的方法不夠靈敏，太擴張的方法又容易失真，而類平均法相對比較適中。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), ,

30、(n, n-1)Y = pdist（X, metric）輸入?yún)?shù)metric指定計算距離的方法，metric為字符串，可用的字符串如下表所示。MetricMetric參數(shù)值參數(shù)值說明說明euclidean歐式距離seuclidean標準化歐式距離mahalanobis馬哈拉諾比斯距離cityblock絕對值距離minkowski閔可夫斯基距離chebychev切比雪夫距離Y = pdist（X, minkowski, p）計算樣品對的閔可夫斯基距離，輸入?yún)?shù)p為閔可夫斯基距離計算中的指數(shù)，默認情況下，指數(shù)為2SquareformZ = squareform(y)Z = squareform(y

31、, tomatrix)y = squareform(Z)y = squareform(Z, tovector) 前兩種調(diào)用時把pdist函數(shù)輸出的距離向量y轉(zhuǎn)為距離矩陣Z，而后兩種調(diào)用則是把距離矩陣Z轉(zhuǎn)換為pdist函數(shù)輸出的距離向量y。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次并類的兩個類的類編號，初始類編號為1n，以后每

32、形成一個新類，類編號從n+1開始逐次增加1.Z矩陣的第i行中的第3個元素為第i次并類是的并類距離Z = linkage（y, method）利用method參數(shù)制定的方法創(chuàng)建系統(tǒng)聚類樹，method是字符串，可用的字符串如下所示MethodMethod參數(shù)值參數(shù)值說明說明average類平均法centroid重心法complete最長距離法median中間距離法single最短距離法ward離差平方和法weighted可變類平均法Z = linkage（y, method, metric）metric用來制定計算距離的方法Dendrogram函數(shù)H = dendrogram（Z）由系統(tǒng)聚類樹矩

33、陣Z生成系統(tǒng)聚類樹形圖。輸入?yún)?shù)Z是由linkage函數(shù)輸出的系統(tǒng)聚類樹矩陣。輸出參數(shù)H是樹形圖中線條的句柄值向量，用來控制線條屬性。H = dendrogram（Z， p）生成一個樹形圖，通過輸入?yún)?shù)p來控制顯示的葉節(jié)點數(shù)。H = dendrogram（, orientation, orient）通過設(shè)定orientation參數(shù)及參數(shù)值orient來控制聚類樹形圖的方向和放著葉節(jié)點標簽的位置，可用參數(shù)如下所示參數(shù)值參數(shù)值說明說明top從上至下，葉節(jié)點標簽在下方，為默認情況bottom從下至上，葉節(jié)點標簽在上方left從左至右，葉節(jié)點標簽在右邊right從右至左，葉節(jié)點標簽在左邊H = dendrogram（, labels, S）通過一個字符串數(shù)組或字符串元胞數(shù)組設(shè)定每一個觀測值的標簽。當樹形圖中顯示了全部的葉節(jié)點時，葉節(jié)點的標簽記為相應(yīng)觀測的標簽；當樹形圖中忽略了某些節(jié)點時，只包含單個觀測的葉節(jié)點的