交通數(shù)據(jù)處理-第三章-聚類(lèi)分析2

1、系統(tǒng)聚類(lèi)法的基本思想系統(tǒng)聚類(lèi)法的基本思想 先將n個(gè)樣品各自看成一類(lèi)，然后規(guī)定樣品之間的“距離”和類(lèi)與類(lèi)之間的距離。選擇距離最近距離最近的兩類(lèi)合并成一個(gè)新類(lèi)，計(jì)算新類(lèi)和其它類(lèi)（各當(dāng)前類(lèi)）的距離，再將距離最近的兩類(lèi)合并。這樣，每次合并減少一類(lèi)，直至直至所有的樣品都?xì)w成一類(lèi)為止所有的樣品都?xì)w成一類(lèi)為止。 （1）確定數(shù)據(jù)點(diǎn)之間的距離計(jì)算方法（2）確定數(shù)據(jù)分類(lèi)后類(lèi)與類(lèi)之間距離的計(jì)算方法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)成的

2、樣品對(duì)，則Y中的元素依次是(2, 1), (3, 1), , (n, 1), (3, 2), , (n, 2), , (n, n-1)Y = pdist（X, metric）輸入?yún)?shù)metric指定計(jì)算距離的方法，metric為字符串，可用的字符串如下表所示。MetricMetric參數(shù)值參數(shù)值說(shuō)明說(shuō)明euclidean歐式距離seuclidean標(biāo)準(zhǔn)化歐式距離mahalanobis馬哈拉諾比斯距離cityblock絕對(duì)值距離minkowski閔可夫斯基距離chebychev切比雪夫距離Y = pdist（X, minkowski, p）計(jì)算樣品對(duì)的閔可夫斯基距離，輸入?yún)?shù)p為閔可夫斯基距離計(jì)

3、算中的指數(shù)，默認(rèn)情況下，指數(shù)為2SquareformZ = 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。Linkage函數(shù)Z = linkage（y）利用最短距離法創(chuàng)建一個(gè)系統(tǒng)聚類(lèi)樹(shù)。輸入?yún)?shù)y是樣品對(duì)距離向量，是包含n(n-1)/2個(gè)元素的行向量，通常是pdist函數(shù)的輸出。輸出Z是一個(gè)系統(tǒng)聚類(lèi)樹(shù)矩陣，它是(n-1)*3的矩陣，這里的n是原始數(shù)

4、據(jù)中觀測(cè)樣品的個(gè)數(shù)。Z矩陣每一行對(duì)應(yīng)一次并類(lèi)，第i行上前兩個(gè)元素為第i次并類(lèi)的兩個(gè)類(lèi)的類(lèi)編號(hào)，初始類(lèi)編號(hào)為1n，以后每形成一個(gè)新類(lèi)，類(lèi)編號(hào)從n+1開(kāi)始逐次增加1.Z矩陣的第i行中的第3個(gè)元素為第i次并類(lèi)時(shí)的并類(lèi)距離Z = linkage（y, method）利用method參數(shù)制定的方法創(chuàng)建系統(tǒng)聚類(lèi)樹(shù)，method是字符串，可用的字符串如下所示MethodMethod參數(shù)值參數(shù)值說(shuō)明說(shuō)明average類(lèi)平均法centroid重心法complete最長(zhǎng)距離法median中間距離法single最短距離法ward離差平方和法weighted可變類(lèi)平均法Z = linkage（y, method, m

5、etric）metric用來(lái)指定計(jì)算點(diǎn)與點(diǎn)之間距離的方法MetricMetric參數(shù)值參數(shù)值說(shuō)明說(shuō)明euclidean歐式距離seuclidean標(biāo)準(zhǔn)化歐式距離mahalanobis馬哈拉諾比斯距離cityblock絕對(duì)值距離minkowski閔可夫斯基距離chebychev切比雪夫距離Dendrogram函數(shù)H = dendrogram（Z）由系統(tǒng)聚類(lèi)樹(shù)矩陣Z生成系統(tǒng)聚類(lèi)樹(shù)形圖。輸入?yún)?shù)Z是由linkage函數(shù)輸出的系統(tǒng)聚類(lèi)樹(shù)矩陣。輸出參數(shù)H是樹(shù)形圖中線條的句柄值向量，用來(lái)控制線條屬性。H = dendrogram（Z， p）生成一個(gè)樹(shù)形圖，通過(guò)輸入?yún)?shù)p來(lái)控制顯示的葉節(jié)點(diǎn)數(shù)。H = den

6、drogram（, orientation, orient）通過(guò)設(shè)定orientation參數(shù)及參數(shù)值orient來(lái)控制聚類(lèi)樹(shù)形圖的方向和放置葉節(jié)點(diǎn)標(biāo)簽的位置，可用參數(shù)如下所示參數(shù)值參數(shù)值說(shuō)明說(shuō)明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）通過(guò)一個(gè)字符串?dāng)?shù)組或字符串元胞數(shù)組設(shè)定每一個(gè)觀測(cè)值的標(biāo)簽。當(dāng)樹(shù)形圖中顯示了全部的葉節(jié)點(diǎn)時(shí)，葉節(jié)點(diǎn)的標(biāo)簽記為相應(yīng)觀測(cè)的標(biāo)簽；當(dāng)樹(shù)形圖中忽略了某些節(jié)點(diǎn)時(shí)，只包含單個(gè)觀測(cè)的葉節(jié)點(diǎn)的標(biāo)簽記為相應(yīng)觀測(cè)的標(biāo)簽。

7、Cophenet函數(shù)Cophenet函數(shù)用來(lái)計(jì)算系統(tǒng)聚類(lèi)樹(shù)的cophenetic相關(guān)系數(shù)Cophenetic相關(guān)系數(shù)反映了聚類(lèi)效果的好壞，cophenetic相關(guān)系數(shù)越接近于1，說(shuō)明聚類(lèi)效果越好，可通過(guò)Cophenetic相關(guān)系數(shù)對(duì)比各種不同的距離計(jì)算方法和不同的系統(tǒng)聚類(lèi)法的聚類(lèi)效果cophenetic相關(guān)系數(shù)對(duì)給定的樣本觀測(cè)矩陣X，用y = （y1,y2, , yn(n-1)/2）表示由pdist函數(shù)輸出的樣本的距離向量，用（i， j）表示由第i個(gè)樣本和第j個(gè)樣本構(gòu)成的樣本對(duì)，則y中的元素依次是樣本對(duì)（2，1），（3,1），（n, 1），（3,2），（n，2）, ，（n，n-1)的距離設(shè)d

8、= （d1, d2, , d n(n-1)/2 ）,d中元素依次是樣本對(duì)（2，1），（3,1），（n, 1），（3,2），（n，2）, ，（n，n-1)中初次并類(lèi)時(shí)的并類(lèi)距離，稱(chēng)為cophenetic距離cophenetic相關(guān)系數(shù) 是指y與d之間的線性相關(guān)系數(shù)()()()()()()()1 211 21 22211n nkkkn nn nkkkkyyddcyydd-=-=-=輊輊犏犏-犏犏犏犏臌臌邋()()1 2121n nkkyyn n-=-()()1 2121n nkkddn n-=-c = cophenet（Z, Y）在上述調(diào)用中，cophenet函數(shù)用pdist函數(shù)輸出的Y和link

9、age函數(shù)輸出的Z計(jì)算系統(tǒng)聚類(lèi)樹(shù)的cophenetic相關(guān)系數(shù)。輸出參數(shù)c為Cophenetic相關(guān)系數(shù)inconsistent函數(shù)用來(lái)計(jì)算系統(tǒng)聚類(lèi)樹(shù)矩陣Z中每次并類(lèi)得到的鏈接的不一致系數(shù)，其調(diào)用格式如下Y = inconsistent（Z）Y = inconsistent（Z，d）參數(shù)Y是一個(gè)(n-1)*4的矩陣，各列的含義如下列序號(hào)列序號(hào)說(shuō)明說(shuō)明1計(jì)算設(shè)計(jì)的所有鏈接長(zhǎng)度（即并類(lèi)距離）的均值2計(jì)算涉及的所有鏈接長(zhǎng)度的標(biāo)準(zhǔn)差3計(jì)算涉及的鏈接個(gè)數(shù)4不一致系數(shù)不一致系數(shù)可用來(lái)確定最終的分類(lèi)個(gè)數(shù)。在并類(lèi)過(guò)程中，若某一次并類(lèi)對(duì)應(yīng)的不一致系數(shù)較上一次有大幅增加，說(shuō)明該次并類(lèi)效果不好，而它上一次的并類(lèi)效果

10、使比較好的，不一致系數(shù)增加的幅度越大，說(shuō)明上一次并類(lèi)效果越好。在使得類(lèi)的個(gè)數(shù)盡量少的前提下，可參照不一致系數(shù)的變化，確定最終的分類(lèi)數(shù)。Clusterdata 函數(shù)調(diào)用了pdist、linkage和cluster函數(shù)，用來(lái)由原始眼根數(shù)據(jù)矩陣X創(chuàng)建系統(tǒng)聚類(lèi)，T = clusterdata（X， cutoff）T = clusterdata（X， param1， val1， param2， val2， ）輸出參數(shù)T包含n個(gè)元素的列向量，其元素為相應(yīng)觀測(cè)所屬類(lèi)的類(lèi)序號(hào)。Curfoo為閾值。Clusterdata函數(shù)T = clusterdata（X， cutoff）T = clusterdata（X，

11、 param1， val1， param2， val2， ）參數(shù)名參數(shù)名參數(shù)值參數(shù)值含義含義distancePdist函數(shù)所支持的metric參數(shù)的取值指定距離的計(jì)算方法linkageLinkage函數(shù)所支持的method參數(shù)的取值指定系統(tǒng)聚類(lèi)方法cutoff正實(shí)數(shù)指定不一致系數(shù)或距離的閾值maxclust正整數(shù)指定最大類(lèi)數(shù) 系統(tǒng)聚類(lèi)法是一種比較成功的聚類(lèi)方法。然而當(dāng)樣本點(diǎn)數(shù)量十分龐大時(shí)，則是一件非常繁重的工作，且聚類(lèi)的計(jì)算速度也比較慢。比如在抽樣調(diào)查中，有4萬(wàn)人就其出行方式偏好作了回答，希望能迅速將他們分為幾類(lèi)。這時(shí)，采用系統(tǒng)聚類(lèi)法就很困難，而動(dòng)態(tài)聚類(lèi)法就會(huì)顯得方便，適用。 動(dòng)態(tài)聚類(lèi)使用于大

12、型數(shù)據(jù)?；舅枷耄哼x取若干個(gè)樣品作為凝聚點(diǎn)，計(jì)算每個(gè)樣品和凝聚點(diǎn)的距離，進(jìn)行初始分類(lèi)，然后根據(jù)初始分類(lèi)計(jì)算其重心，再進(jìn)行第二次分類(lèi)，一直到所有樣品不再調(diào)整為止。K均值聚類(lèi)法又稱(chēng)為快速聚類(lèi)法，其基本步驟為1. 選擇K個(gè)樣品作為初始凝聚點(diǎn)（聚類(lèi)種子），或者將所有樣品分為k個(gè)初始類(lèi)，然后將k個(gè)類(lèi)的重心（均值）作為初始凝聚點(diǎn)。2. 對(duì)除初始凝聚點(diǎn)之外的所有樣品逐個(gè)歸類(lèi)，將每個(gè)樣品歸入離他最近的凝聚點(diǎn)所在的類(lèi)，該類(lèi)的凝聚點(diǎn)更新為這一類(lèi)目前的均值，直至所有樣品都?xì)w類(lèi)。重復(fù)步驟2，直至所有樣品不能再分配位置選擇凝聚點(diǎn)分 類(lèi)修改分類(lèi)分類(lèi)是否合理分類(lèi)結(jié)束YesNo 用一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明動(dòng)態(tài)聚類(lèi)法的工作過(guò)程。例

13、如我們要把圖中的點(diǎn)分成兩類(lèi)。快速聚類(lèi)的步驟： 1、隨機(jī)選取兩個(gè)點(diǎn) 和 作為凝聚點(diǎn)。 2、對(duì)于任何點(diǎn) ，分別計(jì)算 3、若 ，則將 劃為第一類(lèi)，否則劃給第二類(lèi)。于是得圖（b）的兩個(gè)類(lèi)。 )1 (1x)1 (2xkx),(),()1(2)1(1xxdxxdkk和),(),()1(2)1(1xxdxxdkkkx4、分別計(jì)算兩個(gè)類(lèi)的重心，則得 和 ，以其為新的凝聚點(diǎn)，對(duì)空間中的點(diǎn)進(jìn)行重新分類(lèi)，得到新分類(lèi)。)2(1x)2(2x (b) 任取兩個(gè)凝聚點(diǎn) (c) 第一次分類(lèi) (d) 求各類(lèi)中心 （a）空間的群點(diǎn) (e) 第二次分類(lèi)優(yōu)點(diǎn)：計(jì)算量小，方法簡(jiǎn)便，可以根據(jù)經(jīng)驗(yàn)，先作主觀分類(lèi)。缺點(diǎn)：結(jié)果受選擇凝聚點(diǎn)好壞

14、的影響，分類(lèi)結(jié)果不穩(wěn)定。 凝聚點(diǎn)就是一批有代表性的點(diǎn)，是欲形成類(lèi)的中心。凝聚點(diǎn)的 選擇直接決定初始分類(lèi)，對(duì)分類(lèi)結(jié)果也有很大的影響，由于凝聚點(diǎn) 的不同選擇，其最終分類(lèi)結(jié)果也將出現(xiàn)不同。故選擇時(shí)要慎重通 常選擇凝聚點(diǎn)的方法有： (1) 人為選擇人為選擇，當(dāng)人們對(duì)所欲分類(lèi)的問(wèn)題有一定了解時(shí)，根據(jù)經(jīng)驗(yàn)，預(yù)先確定分類(lèi)個(gè)數(shù)和初始分類(lèi)，并從每一類(lèi)中選擇一個(gè)有代表性的樣品作為凝聚點(diǎn)。 (2) 重心法重心法 將數(shù)據(jù)人為地分為A類(lèi)，計(jì)算每一類(lèi)的重心，將重心作為凝聚點(diǎn)。 (3) 密度法密度法以某個(gè)正數(shù)d為半徑，以每個(gè)樣品為球心，落在這個(gè)球內(nèi)的樣品數(shù)(不包括作為球心的樣品)稱(chēng)為這個(gè)樣品的密度。計(jì)算所有樣品點(diǎn)的密度后，

15、首先選擇密度最大的樣品為第一凝聚點(diǎn)。然后選出密度次大的樣品點(diǎn)，若它與第一個(gè)凝 聚點(diǎn)的距離大于2d ，則將其作為第二個(gè)凝聚點(diǎn)；否則舍去這點(diǎn)。這樣，按密度由大到小依次考查，直至全部樣品考查完畢為止此方法中，d要給得合適，太大了使凝聚點(diǎn)個(gè)數(shù)太 少，太小了使凝聚點(diǎn)個(gè)數(shù)太多。 (4) 人為地選擇一正數(shù)d，首先以所有樣品的均值作為第一凝聚點(diǎn)。然后依次考察每個(gè)樣品，若某樣品與已選定的凝聚點(diǎn)的距 離均大于d，該樣品作為新的凝聚點(diǎn)，否則考察下一個(gè)樣本。第一，選擇凝聚點(diǎn)第一，選擇凝聚點(diǎn)；第二，初始分類(lèi)；第二，初始分類(lèi)；對(duì)于取定的凝聚點(diǎn)，視每個(gè)凝聚點(diǎn)為一類(lèi)，將每個(gè)樣品根據(jù)定義的距離向最近的凝聚點(diǎn)歸類(lèi)。第三，修改分類(lèi)

16、第三，修改分類(lèi)得到初始分類(lèi)，計(jì)算各類(lèi)的重心，以這些重心作為新的凝聚點(diǎn)，重新進(jìn)行分類(lèi)，重復(fù)步驟2，3，直到分類(lèi)的結(jié)果與上一步的分類(lèi)結(jié)果相同，表明分類(lèi)已經(jīng)合理為止。動(dòng)態(tài)聚類(lèi)法的基本步驟：動(dòng)態(tài)聚類(lèi)法的基本步驟：例：某汽車(chē)4s店5位店員的月銷(xiāo)售量和受教育程度如下表：售貨員12345銷(xiāo)售量（輛）11688教育程度12320對(duì)這5位店員分類(lèi)。29505026495351341.選擇凝聚點(diǎn)選擇凝聚點(diǎn) 1 5325d為最大。可選擇2和5作為凝聚點(diǎn)。計(jì)算各樣品點(diǎn)兩兩之間的距離，得到如下的距離矩陣502613494對(duì)于取定的凝聚點(diǎn)，視每個(gè)凝聚點(diǎn)為一類(lèi)，將每個(gè)樣品根據(jù)定義的距離，向最近的凝聚點(diǎn)歸類(lèi)。1 G1 G2

17、1 3 4得到初始分類(lèi)為：1G 2 , 1：2G5 , 4 , 3：2.2.初始分類(lèi)初始分類(lèi)25. 052.4025. 018.4025.2754. 315.4956. 025.5124. 3計(jì)算G1和G2的重心：G1的重心（1,1.5），G2的重心（7.33,1.67） G1 G212345得到分類(lèi)結(jié)果：1G 2 , 1：2G5 , 4 , 3：3.3.修改分類(lèi)修改分類(lèi)以這兩個(gè)重心點(diǎn)作為凝聚點(diǎn)，再按最小距離原則重新聚類(lèi)修改前后所分的類(lèi)相同，故可停止修改。 2 , 15 , 4 , 3和。 5個(gè)售貨員可分為兩類(lèi)Kemans函數(shù)IDX = kmeans(X, k)將n個(gè)點(diǎn)分為k類(lèi)。輸入?yún)?shù)X為n

18、*p矩陣，矩陣的每一行對(duì)應(yīng)一個(gè)點(diǎn)，每一列對(duì)應(yīng)一個(gè)變量。輸出參數(shù)IDX是一個(gè)n*1的向量，其元素為每個(gè)點(diǎn)所屬類(lèi)的類(lèi)序號(hào)。IDX， C = kmeans(X, k)返回k個(gè)類(lèi)的類(lèi)重心坐標(biāo)矩陣C，C是一個(gè)k*p的矩陣，第i行的元素為第i類(lèi)的類(lèi)重心坐標(biāo)。IDX, C, sumd = kmeans(X, k)返回類(lèi)內(nèi)距離和（即類(lèi)內(nèi)個(gè)點(diǎn)與類(lèi)重心之間的距離之和）向量sumd，sumd是一個(gè)1*k的向量，第i個(gè)元素為第i類(lèi)的類(lèi)內(nèi)距離之和。Silhouette函數(shù)Silhouette函數(shù)用來(lái)根據(jù)cluster, clusterdata或者kmeans函數(shù)的聚類(lèi)結(jié)果繪制輪廓圖，從輪廓圖上可以看出每個(gè)點(diǎn)的分類(lèi)是否合

19、理。輪廓圖上第i個(gè)點(diǎn)的輪廓值是()( )( )min,1,2,.,max,minbaS iinab-=輊臌a是第i個(gè)點(diǎn)與同類(lèi)的其他點(diǎn)之間的平均距離，b為一個(gè)向量，其元素是第i個(gè)點(diǎn)與不同類(lèi)的類(lèi)內(nèi)各點(diǎn)之間的平均距離，如b的第k個(gè)元素就是第i個(gè)點(diǎn)與第k類(lèi)各點(diǎn)之間的平均距離。輪廓值S(i)的取值范圍為-1, 1，S(i)取值越大，說(shuō)明第i個(gè)點(diǎn)的分類(lèi)越合理，當(dāng)S(i)1和初始隸屬度矩陣U（0）=（uik（0）。（2）通過(guò)下式計(jì)算第l步的聚類(lèi)中心V（l）()()()()()1111,1,2,.,nmlikklkinmlikkuxvicu-=-=（3）修正隸屬度矩陣U（l），計(jì)算目標(biāo)函數(shù)J（l）()()2111,1,2,., ;1,2,.,clllmikikjkjuddic kn-=()()()()()( )()( )211,ncmlllllikikkiJUVud=邋()()llikkidxv=-（4）對(duì)給定的隸屬度終止容限0ue或者達(dá)到最大迭代步長(zhǎng)，停止迭代，否則l=l+1，轉(zhuǎn)至（2）經(jīng)過(guò)以上步驟的迭代后，可以求得最終的隸屬度矩陣U和聚類(lèi)中心V，使得目標(biāo)函數(shù)J（U， V）的值達(dá)到最小。根據(jù)最終的隸屬度矩陣U中元素的取值可以確定所有樣品的歸屬，當(dāng) 1maxjkiki cuu=將樣品xk歸為第j類(lèi)fcmcenter, U, obj_fcn =