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

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

先將n個樣品各自看成一類，然后規(guī)定樣品之間的“距離”和類與類之間的距離。選擇距離最近的兩類合并成一個新類，計算新類和其它類（各當(dāng)前類）的距離，再將距離最近的兩類合并。這樣，每次合并減少一類，直至所有的樣品都?xì)w成一類為止。系統(tǒng)聚類法回顧（1）確定數(shù)據(jù)點之間的距離計算方法（2）確定數(shù)據(jù)分類后類與類之間距離的計算方法系統(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’標(biāo)準(zhǔn)化歐式距離‘mahalanobis’馬哈拉諾比斯距離‘cityblock’絕對值距離‘minkowski’閔可夫斯基距離‘chebychev’切比雪夫距離Y=pdist（X,‘minkowski’,p）計算樣品對的閔可夫斯基距離，輸入?yún)?shù)p為閔可夫斯基距離計算中的指數(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)用時把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ù)Metric參數(shù)值說明‘euclidean’歐式距離‘seuclidean’標(biāo)準(zhǔn)化歐式距離‘mahalanobis’馬哈拉諾比斯距離‘cityblock’絕對值距離‘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）生成一個樹形圖，通過輸入?yún)?shù)p來控制顯示的葉節(jié)點數(shù)。系統(tǒng)聚類法的相關(guān)函數(shù)H=dendrogram（…,‘orientation’,‘orient’）通過設(shè)定’orientation’參數(shù)及參數(shù)值’orient’來控制聚類樹形圖的方向和放置葉節(jié)點標(biāo)簽的位置，可用參數(shù)如下所示參數(shù)值說明‘top’從上至下，葉節(jié)點標(biāo)簽在下方，為默認(rèn)情況‘bottom’從下至上，葉節(jié)點標(biāo)簽在上方‘left’從左至右，葉節(jié)點標(biāo)簽在右邊‘right’從右至左，葉節(jié)點標(biāo)簽在左邊H=dendrogram（…,‘labels’,S）通過一個字符串?dāng)?shù)組或字符串元胞數(shù)組設(shè)定每一個觀測值的標(biāo)簽。當(dāng)樹形圖中顯示了全部的葉節(jié)點時，葉節(jié)點的標(biāo)簽記為相應(yīng)觀測的標(biāo)簽；當(dāng)樹形圖中忽略了某些節(jié)點時，只包含單個觀測的葉節(jié)點的標(biāo)簽記為相應(yīng)觀測的標(biāo)簽。系統(tǒng)聚類法的相關(guān)函數(shù)Cophenet函數(shù)Cophenet函數(shù)用來計算系統(tǒng)聚類樹的cophenetic相關(guān)系數(shù)Cophenetic相關(guān)系數(shù)反映了聚類效果的好壞，cophenetic相關(guān)系數(shù)越接近于1，說明聚類效果越好，可通過Cophenetic相關(guān)系數(shù)對比各種不同的距離計算方法和不同的系統(tǒng)聚類法的聚類效果系統(tǒng)聚類法的相關(guān)函數(shù)cophenetic相關(guān)系數(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)的距離設(shè)d=（d1,d2,…,dn(n-1)/2）,d中元素依次是樣本對（2，1），（3,1），…，（n,1），（3,2），…，（n，2）,…，（n，n-1)中初次并類時的并類距離，稱為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計算系統(tǒng)聚類樹的cophenetic相關(guān)系數(shù)。輸出參數(shù)c為Cophenetic相關(guān)系數(shù)系統(tǒng)聚類法的相關(guān)函數(shù)inconsistent函數(shù)用來計算系統(tǒng)聚類樹矩陣Z中每次并類得到的鏈接的不一致系數(shù)，其調(diào)用格式如下Y=inconsistent（Z）Y=inconsistent（Z，d）參數(shù)Y是一個(n-1)*4的矩陣，各列的含義如下系統(tǒng)聚類法的相關(guān)函數(shù)列序號說明1計算設(shè)計的所有鏈接長度（即并類距離）的均值2計算涉及的所有鏈接長度的標(biāo)準(zhǔn)差3計算涉及的鏈接個數(shù)4不一致系數(shù)不一致系數(shù)可用來確定最終的分類個數(shù)。在并類過程中，若某一次并類對應(yīng)的不一致系數(shù)較上一次有大幅增加，說明該次并類效果不好，而它上一次的并類效果使比較好的，不一致系數(shù)增加的幅度越大，說明上一次并類效果越好。在使得類的個數(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個元素的列向量，其元素為相應(yīng)觀測所屬類的類序號。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ù)的取值指定距離的計算方法‘linkage’Linkage函數(shù)所支持的method參數(shù)的取值指定系統(tǒng)聚類方法‘cutoff’正實數(shù)指定不一致系數(shù)或距離的閾值‘maxclust’正整數(shù)指定最大類數(shù)動態(tài)聚類法（快速聚類法/k均值聚類法）

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

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

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

1、隨機(jī)選取兩個點和作為凝聚點。

2、對于任何點，分別計算

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

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

（a）空間的群點(e)第二次分類動態(tài)聚類法

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

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

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

(2)重心法將數(shù)據(jù)人為地分為A類，計算每一類的重心，將重心作為凝聚點。(3)密度法以某個正數(shù)d為半徑，以每個樣品為球心，落在這個球內(nèi)的樣品數(shù)(不包括作為球心的樣品)稱為這個樣品的密度。計算所有樣品點的密度后，首先選擇密度最大的樣品為第一凝聚點。然后選出密度次大的樣品點，若它與第一個凝聚點的距離大于2d，則將其作為第二個凝聚點；否則舍去這點。這樣，按密度由大到小依次考查，直至全部樣品考查完畢為止．此方法中，d要給得合適，太大了使凝聚點個數(shù)太少，太小了使凝聚點個數(shù)太多。

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

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