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

聚類分析2系統(tǒng)聚類法的基本思想

先將n個(gè)樣品各自看成一類，然后規(guī)定樣品之間的“距離”和類與類之間的距離。選擇距離最近的兩類合并成一個(gè)新類，計(jì)算新類和其它類（各當(dāng)前類）的距離，再將距離最近的兩類合并。這樣，每次合并減少一類，直至所有的樣品都?xì)w成一類為止。系統(tǒng)聚類法回顧（1）確定數(shù)據(jù)點(diǎn)之間的距離計(jì)算方法（2）確定數(shù)據(jù)分類后類與類之間距離的計(jì)算方法系統(tǒng)聚類法回顧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ù)中觀測(cè)樣品的個(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次并類時(shí)的并類距離系統(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’最長(zhǎng)距離法‘median’中間距離法‘single’最短距離法‘ward’離差平方和法‘weighted’可變類平均法Z=linkage（y,method,metric）metric用來指定計(jì)算點(diǎn)與點(diǎn)之間距離的方法系統(tǒng)聚類法的相關(guān)函數(shù)Metric參數(shù)值說明‘euclidean’歐式距離‘seuclidean’標(biāo)準(zhǔn)化歐式距離‘mahalanobis’馬哈拉諾比斯距離‘cityblock’絕對(duì)值距離‘minkowski’閔可夫斯基距離‘chebychev’切比雪夫距離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è)觀測(cè)值的標(biāo)簽。當(dāng)樹形圖中顯示了全部的葉節(jié)點(diǎn)時(shí)，葉節(jié)點(diǎn)的標(biāo)簽記為相應(yīng)觀測(cè)的標(biāo)簽；當(dāng)樹形圖中忽略了某些節(jié)點(diǎn)時(shí)，只包含單個(gè)觀測(cè)的葉節(jié)點(diǎn)的標(biāo)簽記為相應(yīng)觀測(cè)的標(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，說明聚類效果越好，可通過Cophenetic相關(guān)系數(shù)對(duì)比各種不同的距離計(jì)算方法和不同的系統(tǒng)聚類法的聚類效果系統(tǒng)聚類法的相關(guān)函數(shù)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=（d1,d2,…,dn(n-1)/2）,d中元素依次是樣本對(duì)（2，1），（3,1），…，（n,1），（3,2），…，（n，2）,…，（n，n-1)中初次并類時(shí)的并類距離，稱為cophenetic距離系統(tǒng)聚類法的相關(guān)函數(shù)cophenetic相關(guān)系數(shù)是指y與d之間的線性相關(guān)系數(shù)c=cophenet（Z,Y）在上述調(diào)用中，cophenet函數(shù)用pdist函數(shù)輸出的Y和linkage函數(shù)輸出的Z計(jì)算系統(tǒng)聚類樹的cophenetic相關(guān)系數(shù)。輸出參數(shù)c為Cophenetic相關(guān)系數(shù)系統(tǒng)聚類法的相關(guān)函數(shù)inconsistent函數(shù)用來計(jì)算系統(tǒng)聚類樹矩陣Z中每次并類得到的鏈接的不一致系數(shù)，其調(diào)用格式如下Y=inconsistent（Z）Y=inconsistent（Z，d）參數(shù)Y是一個(gè)(n-1)*4的矩陣，各列的含義如下系統(tǒng)聚類法的相關(guān)函數(shù)列序號(hào)說明1計(jì)算設(shè)計(jì)的所有鏈接長(zhǎng)度（即并類距離）的均值2計(jì)算涉及的所有鏈接長(zhǎng)度的標(biāo)準(zhǔn)差3計(jì)算涉及的鏈接個(gè)數(shù)4不一致系數(shù)不一致系數(shù)可用來確定最終的分類個(gè)數(shù)。在并類過程中，若某一次并類對(duì)應(yīng)的不一致系數(shù)較上一次有大幅增加，說明該次并類效果不好，而它上一次的并類效果使比較好的，不一致系數(shù)增加的幅度越大，說明上一次并類效果越好。在使得類的個(gè)數(shù)盡量少的前提下，可參照不一致系數(shù)的變化，確定最終的分類數(shù)。系統(tǒng)聚類法的相關(guān)函數(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個(gè)元素的列向量，其元素為相應(yīng)觀測(cè)所屬類的類序號(hào)。Curfoo為閾值。Clusterdata函數(shù)T=clusterdata（X，cutoff）T=clusterdata（X，param1，val1，param2，val2，…）系統(tǒng)聚類法的相關(guān)函數(shù)參數(shù)名參數(shù)值含義‘distance’Pdist函數(shù)所支持的metric參數(shù)的取值指定距離的計(jì)算方法‘linkage’Linkage函數(shù)所支持的method參數(shù)的取值指定系統(tǒng)聚類方法‘cutoff’正實(shí)數(shù)指定不一致系數(shù)或距離的閾值‘maxclust’正整數(shù)指定最大類數(shù)動(dòng)態(tài)聚類法（快速聚類法/k均值聚類法）

系統(tǒng)聚類法是一種比較成功的聚類方法。然而當(dāng)樣本點(diǎn)數(shù)量十分龐大時(shí)，則是一件非常繁重的工作，且聚類的計(jì)算速度也比較慢。比如在抽樣調(diào)查中，有4萬人就其出行方式偏好作了回答，希望能迅速將他們分為幾類。這時(shí)，采用系統(tǒng)聚類法就很困難，而動(dòng)態(tài)聚類法就會(huì)顯得方便，適用。動(dòng)態(tài)聚類使用于大型數(shù)據(jù)。動(dòng)態(tài)聚類法

基本思想：選取若干個(gè)樣品作為凝聚點(diǎn)，計(jì)算每個(gè)樣品和凝聚點(diǎn)的距離，進(jìn)行初始分類，然后根據(jù)初始分類計(jì)算其重心，再進(jìn)行第二次分類，一直到所有樣品不再調(diào)整為止。K均值聚類法又稱為快速聚類法，其基本步驟為1.選擇K個(gè)樣品作為初始凝聚點(diǎn)（聚類種子），或者將所有樣品分為k個(gè)初始類，然后將k個(gè)類的重心（均值）作為初始凝聚點(diǎn)。2.對(duì)除初始凝聚點(diǎn)之外的所有樣品逐個(gè)歸類，將每個(gè)樣品歸入離他最近的凝聚點(diǎn)所在的類，該類的凝聚點(diǎn)更新為這一類目前的均值，直至所有樣品都?xì)w類。重復(fù)步驟2，直至所有樣品不能再分配位置K均值聚類法選擇凝聚點(diǎn)分類修改分類分類是否合理分類結(jié)束YesNo

用一個(gè)簡(jiǎn)單的例子來說明動(dòng)態(tài)聚類法的工作過程。例如我們要把圖中的點(diǎn)分成兩類?？焖倬垲惖牟襟E：

1、隨機(jī)選取兩個(gè)點(diǎn)和作為凝聚點(diǎn)。

2、對(duì)于任何點(diǎn)，分別計(jì)算

3、若，則將劃為第一類，否則劃給第二類。于是得圖（b）的兩個(gè)類。4、分別計(jì)算兩個(gè)類的重心，則得和，以其為新的凝聚點(diǎn)，對(duì)空間中的點(diǎn)進(jìn)行重新分類，得到新分類。

(b)任取兩個(gè)凝聚點(diǎn)(c)第一次分類(d)求各類中心

（a）空間的群點(diǎn)(e)第二次分類動(dòng)態(tài)聚類法

優(yōu)點(diǎn)：計(jì)算量小，方法簡(jiǎn)便，可以根據(jù)經(jīng)驗(yàn)，先作主觀分類。缺點(diǎn)：結(jié)果受選擇凝聚點(diǎn)好壞的影響，分類結(jié)果不穩(wěn)定。選擇凝聚點(diǎn)和確定初始分類

凝聚點(diǎn)就是一批有代表性的點(diǎn)，是欲形成類的中心。凝聚點(diǎn)的選擇直接決定初始分類，對(duì)分類結(jié)果也有很大的影響，由于凝聚點(diǎn)的不同選擇，其最終分類結(jié)果也將出現(xiàn)不同。故選擇時(shí)要慎重．通常選擇凝聚點(diǎn)的方法有：

(1)人為選擇，當(dāng)人們對(duì)所欲分類的問題有一定了解時(shí)，根據(jù)經(jīng)驗(yàn)，預(yù)先確定分類個(gè)數(shù)和初始分類，并從每一類中選擇一個(gè)有代表性的樣品作為凝聚點(diǎn)。

(2)重心法將數(shù)據(jù)人為地分為A類，計(jì)算每一類的重心，將重心作為凝聚點(diǎn)。(3)密度法以某個(gè)正數(shù)d為半徑，以每個(gè)樣品為球心，落在這個(gè)球內(nèi)的樣品數(shù)(不包括作為球心的樣品)稱為這個(gè)樣品的密度。計(jì)算所有樣品點(diǎn)的密度后，首先選擇密度最大的樣品為第一凝聚點(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)；第二，初始分類；對(duì)于取定的凝聚點(diǎn)，視每個(gè)凝聚點(diǎn)為一類，將每個(gè)樣品根據(jù)定義的距離向最近的凝聚點(diǎn)歸類。第三，修改分類得到初始分類，計(jì)算各類的重心，以這些重心作為新的凝聚點(diǎn)，重新進(jìn)行分類，重復(fù)步驟2，3，直到分類的結(jié)果與上一步的分類結(jié)果相同，表明分類已經(jīng)合理為止。動(dòng)態(tài)聚類法的基本步驟：例：某汽車4s店5位店員的月銷售量和受教育程度如下表：售貨員12345銷售量（輛）11688教育程度12320對(duì)這5位店員分類。選擇凝聚點(diǎn)1②③④⑤①②③④為最大。可選擇2和5作為凝聚點(diǎn)。計(jì)算各樣品點(diǎn)兩兩之間的距離，得到如下的距離矩陣對(duì)于取定的凝聚點(diǎn)，視每個(gè)凝聚點(diǎn)為一類，將每個(gè)樣品根據(jù)定義的距離，向最近的凝聚點(diǎn)歸類。1②G1⑤G2134得到初始分類為：：：2.初始分類計(jì)算G1和G2的重心：G1的重心（1,1.5），G2的重心（7.33,1.67）G1G212345得到分類結(jié)果：：：3.修改分類以這兩個(gè)重心點(diǎn)作為凝聚點(diǎn)，再按最小距離原則重新聚類修改前后所分的類相同，故可停止修改。和。

5個(gè)售貨員可分為兩類Kemans函數(shù)IDX=kmeans(X,k)將n個(gè)點(diǎn)分為k類。輸入?yún)?shù)X為n*p矩陣，矩陣的每一行對(duì)應(yīng)一個(gè)點(diǎn)，每一列對(duì)應(yīng)一個(gè)變量。輸出參數(shù)IDX是一個(gè)n*1的向量，其元素為每個(gè)點(diǎn)所屬類的類序號(hào)。K均值聚類法的相關(guān)函數(shù)[IDX，C]=kmeans(X,k)返回k個(gè)類的類重心坐標(biāo)矩陣C，C是一個(gè)k*p的矩陣，第i行的元素為第i類的類重心坐標(biāo)。[IDX,C,sumd]=kmeans(X,k)返回類內(nèi)距離和（即類內(nèi)個(gè)點(diǎn)與類重心之間的距離之和）向量sumd，sumd是一個(gè)1*k的向量，第i個(gè)元素為第i類的類內(nèi)距離之和。K均值聚類法的相關(guān)函數(shù)Silhouette函數(shù)Silhouette函數(shù)用來根據(jù)cluster,clusterdata或者kmeans函數(shù)的聚類結(jié)果繪制輪廓圖，從輪廓圖上可以看出每個(gè)點(diǎn)的分類是否合理。輪廓圖上第i個(gè)點(diǎn)的輪廓值是K均值聚類法的相關(guān)函數(shù)a是第i個(gè)點(diǎn)與同類的其他點(diǎn)之間的平均距離，b為一個(gè)向量，其元素是第i個(gè)點(diǎn)與不同類的類內(nèi)各點(diǎn)之間的平均距離，如b的第k個(gè)元素就是第i個(gè)點(diǎn)與第k類各點(diǎn)之間的平均距離。輪廓值S(i)的取值范圍為[-1,1]，S(i)取值越大，說明第i個(gè)點(diǎn)的分類越合理，當(dāng)S(i)<0時(shí)，說明第i個(gè)點(diǎn)的分類不合理，還有比目前分類更合理的方案。K均值聚類法的相關(guān)函數(shù)Silhouette的調(diào)用格式Silhouette（X,clust）根據(jù)樣本觀測(cè)值矩陣X和聚類結(jié)果clust繪制輪廓圖。輸入?yún)?shù)X是一個(gè)n*p的矩陣，矩陣的每一行對(duì)應(yīng)一個(gè)觀測(cè)，每一列對(duì)應(yīng)一個(gè)變量。Clust是聚類結(jié)果，可以是由每個(gè)觀測(cè)值所屬的類序號(hào)構(gòu)成的數(shù)值向量，也可以是由類名稱構(gòu)成的字符矩陣或字符串元胞數(shù)組。默認(rèn)情況下，Silhouette函數(shù)會(huì)采用平方歐式距離K均值聚類法的相關(guān)函數(shù)s=Silhouette（X,clust）返回輪廓值向量s，它是一個(gè)n*1的向量，其元素為相應(yīng)點(diǎn)的輪廓值。此時(shí)不繪制輪廓圖。[s,h]=Silhouette（X,clust）繪制輪廓圖，并返回輪廓值向量s和圖形句柄h。x=[1,2,6,8,11]';在很多分類過程中，分類對(duì)象之間沒有明確的界限，往往具有亦此亦彼的情況。例如好與壞之間沒有明確的界限，我認(rèn)為某個(gè)人是好人，別人未必這么認(rèn)為；高與矮之間也沒有明確的界限，多高的人才算是高，可能每個(gè)人都有每個(gè)人的判斷。諸如此類的問題，如果用傳統(tǒng)的聚類方法進(jìn)行分類，把每個(gè)待分類的對(duì)象嚴(yán)格地劃分到某個(gè)類中，這也存在一定的不合理性。借助L.A.Zadeh提出的模糊集理論，人們開始應(yīng)用模糊的方法來處理聚類，并稱之為模糊聚類分析。模糊C均值聚類法模糊聚類分析作為無監(jiān)督機(jī)器學(xué)習(xí)的主要技術(shù)之一，是用模糊理論對(duì)重要數(shù)據(jù)分析和建模的方法，建立了樣本類屬的不確定性描述，能比較客觀地反映現(xiàn)實(shí)世界，它已經(jīng)有效地應(yīng)用在大規(guī)模數(shù)據(jù)分析、數(shù)據(jù)挖掘、矢量量化、圖像分割、模式識(shí)別等領(lǐng)域，具有重要的理論與實(shí)際應(yīng)用價(jià)值，隨著應(yīng)用的深入發(fā)展，模糊聚類算法的研究不斷豐富。在眾多模糊聚類算法中，模糊C-均值（FCM）算法應(yīng)用最廣泛且較成功，它通過優(yōu)化目標(biāo)函數(shù)得到每個(gè)樣本點(diǎn)對(duì)所有類中心的隸屬度，從而決定樣本點(diǎn)的類屬以達(dá)到自動(dòng)對(duì)數(shù)據(jù)樣本進(jìn)行分類的目的。把n個(gè)向量xi（i=1,2,…,n）分為c個(gè)模糊組，并求每組的聚類中心，使得非相似性指標(biāo)的價(jià)值函數(shù)達(dá)到最小。用模糊劃分，使得每個(gè)給定數(shù)據(jù)點(diǎn)用值在0，1間的隸屬度來確定其屬于各個(gè)組的程度。與引入模糊劃分相適應(yīng)，隸屬矩陣U允許有取值在0，1間的元素。不過，加上歸一化規(guī)定，一個(gè)數(shù)據(jù)集的隸屬度的和總等于1給定觀測(cè)數(shù)據(jù)矩陣X的每一行為一個(gè)樣品（或觀測(cè)），每一列為一個(gè)變量的n個(gè)觀測(cè)值。模糊聚類將n個(gè)樣品劃分為c個(gè)類（2≤c≤n）.記V={v1；v2；…；vc}為c個(gè)類的聚類中心，其中vi=（vi1,vi2,…,vip）記U=(uik)c*n為隸屬度矩陣，其中元素uik表示第k個(gè)樣本屬于第i類的隸屬度定義目標(biāo)函數(shù)U=(uik)c*n為隸屬度矩陣顯然，J（U,V）表示了各類中樣品到聚類中心的加權(quán)平方距離之和，權(quán)重是樣品xk屬于第i類的隸屬度的m次方，模糊C均值聚類法德聚類準(zhǔn)則是求U，V，使得J（U,V）取最小值。（1）確定類的個(gè)數(shù)c，冪指數(shù)m>1和初始隸屬度矩陣U（0）=（uik（0））。（2）通過下式計(jì)算第l步的聚類中心V（l）（3）修正隸屬度矩陣U（l），計(jì)算目標(biāo)函數(shù)J（l）（4）對(duì)給定的隸屬度終止容限或者達(dá)到最大迭代步長(zhǎng)，停止迭代，否則l=l+1，轉(zhuǎn)至（2）