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

1、系統(tǒng)聚類法的基本思想系統(tǒng)聚類法的基本思想 先將n個樣品各自看成一類，然后規(guī)定樣品之間的“距離”和類與類之間的距離。選擇距離最近距離最近的兩類合并成一個新類，計算新類和其它類（各當前類）的距離，再將距離最近的兩類合并。這樣，每次合并減少一類，直至直至所有的樣品都歸成一類為止所有的樣品都歸成一類為止。 （1）確定數(shù)據(jù)點之間的距離計算方法（2）確定數(shù)據(jù)分類后類與類之間距離的計算方法PdistY = pdist（X） 計算樣品對的歐式距離。輸入?yún)?shù)X是n p的矩陣，矩陣的每一行對應一個樣品，每一列對應一個變量。輸出參數(shù)Y是包含n(n-1)/2個元素的行向量，用(i,j)表示第i個樣品和第j個樣品構(gòu)成的

2、樣品對，則Y中的元素依次是(2, 1), (3, 1), , (n, 1), (3, 2), , (n, 2), , (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為閔可夫斯基距離計

3、算中的指數(shù)，默認情況下，指數(shù)為2SquareformZ = 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。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ù)

4、據(jù)中觀測樣品的個數(shù)。Z矩陣每一行對應一次并類，第i行上前兩個元素為第i次并類的兩個類的類編號，初始類編號為1n，以后每形成一個新類，類編號從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, m

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

6、drogram（, orientation, orient）通過設定orientation參數(shù)及參數(shù)值orient來控制聚類樹形圖的方向和放置葉節(jié)點標簽的位置，可用參數(shù)如下所示參數(shù)值參數(shù)值說明說明top從上至下，葉節(jié)點標簽在下方，為默認情況bottom從下至上，葉節(jié)點標簽在上方left從左至右，葉節(jié)點標簽在右邊right從右至左，葉節(jié)點標簽在左邊H = dendrogram（, labels, S）通過一個字符串數(shù)組或字符串元胞數(shù)組設定每一個觀測值的標簽。當樹形圖中顯示了全部的葉節(jié)點時，葉節(jié)點的標簽記為相應觀測的標簽；當樹形圖中忽略了某些節(jié)點時，只包含單個觀測的葉節(jié)點的標簽記為相應觀測的標簽。

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

8、= （d1, d2, , d n(n-1)/2 ）,d中元素依次是樣本對（2，1），（3,1），（n, 1），（3,2），（n，2）, ，（n，n-1)中初次并類時的并類距離，稱為cophenetic距離cophenetic相關系數(shù) 是指y與d之間的線性相關系數(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計算系統(tǒng)聚類樹的cophenetic相關系數(shù)。輸出參數(shù)c為Cophenetic相關系數(shù)inconsistent函數(shù)用來計算系統(tǒng)聚類樹矩陣Z中每次并類得到的鏈接的不一致系數(shù)，其調(diào)用格式如下Y = inconsistent（Z）Y = inconsistent（Z，d）參數(shù)Y是一個(n-1)*4的矩陣，各列的含義如下列序號列序號說明說明1計算設計的所有鏈接長度（即并類距離）的均值2計算涉及的所有鏈接長度的標準差3計算涉及的鏈接個數(shù)4不一致系數(shù)不一致系數(shù)可用來確定最終的分類個數(shù)。在并類過程中，若某一次并類對應的不一致系數(shù)較上一次有大幅增加，說明該次并類效果不好，而它上一次的并類效果

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

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

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

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

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

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

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

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

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

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