聚類分析2系統聚類法的基本思想

先將n個樣品各自看成一類，然后規定樣品之間的“距離”和類與類之間的距離。選擇距離最近的兩類合并成一個新類，計算新類和其它類（各當前類）的距離，再將距離最近的兩類合并。這樣，每次合并減少一類，直至所有的樣品都歸成一類為止。系統聚類法回顧（1）確定數據點之間的距離計算方法（2）確定數據分類后類與類之間距離的計算方法系統聚類法回顧PdistY=pdist（X）計算樣品對的歐式距離。輸入參數X是nхp的矩陣，矩陣的每一行對應一個樣品，每一列對應一個變量。輸出參數Y是包含n(n-1)/2個元素的行向量，用(i,j)表示第i個樣品和第j個樣品構成的樣品對，則Y中的元素依次是(2,1),(3,1),…,(n,1),(3,2),…,(n,2),…,(n,n-1)系統聚類法的相關函數Y=pdist（X,metric）輸入參數metric指定計算距離的方法，metric為字符串，可用的字符串如下表所示。系統聚類法的相關函數Metric參數值說明‘euclidean’歐式距離‘seuclidean’標準化歐式距離‘mahalanobis’馬哈拉諾比斯距離‘cityblock’絕對值距離‘minkowski’閔可夫斯基距離‘chebychev’切比雪夫距離Y=pdist（X,‘minkowski’,p）計算樣品對的閔可夫斯基距離，輸入參數p為閔可夫斯基距離計算中的指數，默認情況下，指數為2系統聚類法的相關函數SquareformZ=squareform(y)Z=squareform(y,‘tomatrix’)y=squareform(Z)y=squareform(Z,‘tovector’)前兩種調用時把pdist函數輸出的距離向量y轉為距離矩陣Z，而后兩種調用則是把距離矩陣Z轉換為pdist函數輸出的距離向量y。系統聚類法的相關函數Linkage函數Z=linkage（y）利用最短距離法創建一個系統聚類樹。輸入參數y是樣品對距離向量，是包含n(n-1)/2個元素的行向量，通常是pdist函數的輸出。輸出Z是一個系統聚類樹矩陣，它是(n-1)*3的矩陣，這里的n是原始數據中觀測樣品的個數。Z矩陣每一行對應一次并類，第i行上前兩個元素為第i次并類的兩個類的類編號，初始類編號為1~n，以后每形成一個新類，類編號從n+1開始逐次增加1.Z矩陣的第i行中的第3個元素為第i次并類時的并類距離系統聚類法的相關函數Z=linkage（y,method）利用method參數制定的方法創建系統聚類樹，method是字符串，可用的字符串如下所示系統聚類法的相關函數Method參數值說明‘average’類平均法‘centroid’重心法‘complete’最長距離法‘median’中間距離法‘single’最短距離法‘ward’離差平方和法‘weighted’可變類平均法Z=linkage（y,method,metric）metric用來指定計算點與點之間距離的方法系統聚類法的相關函數Metric參數值說明‘euclidean’歐式距離‘seuclidean’標準化歐式距離‘mahalanobis’馬哈拉諾比斯距離‘cityblock’絕對值距離‘minkowski’閔可夫斯基距離‘chebychev’切比雪夫距離Dendrogram函數H=dendrogram（Z）由系統聚類樹矩陣Z生成系統聚類樹形圖。輸入參數Z是由linkage函數輸出的系統聚類樹矩陣。輸出參數H是樹形圖中線條的句柄值向量，用來控制線條屬性。系統聚類法的相關函數H=dendrogram（Z，p）生成一個樹形圖，通過輸入參數p來控制顯示的葉節點數。系統聚類法的相關函數H=dendrogram（…,‘orientation’,‘orient’）通過設定’orientation’參數及參數值’orient’來控制聚類樹形圖的方向和放置葉節點標簽的位置，可用參數如下所示參數值說明‘top’從上至下，葉節點標簽在下方，為默認情況‘bottom’從下至上，葉節點標簽在上方‘left’從左至右，葉節點標簽在右邊‘right’從右至左，葉節點標簽在左邊H=dendrogram（…,‘labels’,S）通過一個字符串數組或字符串元胞數組設定每一個觀測值的標簽。當樹形圖中顯示了全部的葉節點時，葉節點的標簽記為相應觀測的標簽；當樹形圖中忽略了某些節點時，只包含單個觀測的葉節點的標簽記為相應觀測的標簽。系統聚類法的相關函數Cophenet函數Cophenet函數用來計算系統聚類樹的cophenetic相關系數Cophenetic相關系數反映了聚類效果的好壞，cophenetic相關系數越接近于1，說明聚類效果越好，可通過Cophenetic相關系數對比各種不同的距離計算方法和不同的系統聚類法的聚類效果系統聚類法的相關函數cophenetic相關系數對給定的樣本觀測矩陣X，用y=（y1,y2,…,yn(n-1)/2）表示由pdist函數輸出的樣本的距離向量，用（i，j）表示由第i個樣本和第j個樣本構成的樣本對，則y中的元素依次是樣本對（2，1），（3,1），…，（n,1），（3,2），…，（n，2）,…，（n，n-1)的距離設d=（d1,d2,…,dn(n-1)/2）,d中元素依次是樣本對（2，1），（3,1），…，（n,1），（3,2），…，（n，2）,…，（n，n-1)中初次并類時的并類距離，稱為cophenetic距離系統聚類法的相關函數cophenetic相關系數是指y與d之間的線性相關系數c=cophenet（Z,Y）在上述調用中，cophenet函數用pdist函數輸出的Y和linkage函數輸出的Z計算系統聚類樹的cophenetic相關系數。輸出參數c為Cophenetic相關系數系統聚類法的相關函數inconsistent函數用來計算系統聚類樹矩陣Z中每次并類得到的鏈接的不一致系數，其調用格式如下Y=inconsistent（Z）Y=inconsistent（Z，d）參數Y是一個(n-1)*4的矩陣，各列的含義如下系統聚類法的相關函數列序號說明1計算設計的所有鏈接長度（即并類距離）的均值2計算涉及的所有鏈接長度的標準差3計算涉及的鏈接個數4不一致系數不一致系數可用來確定最終的分類個數。在并類過程中，若某一次并類對應的不一致系數較上一次有大幅增加，說明該次并類效果不好，而它上一次的并類效果使比較好的，不一致系數增加的幅度越大，說明上一次并類效果越好。在使得類的個數盡量少的前提下，可參照不一致系數的變化，確定最終的分類數。系統聚類法的相關函數Clusterdata函數調用了pdist、linkage和cluster函數，用來由原始眼根數據矩陣X創建系統聚類，T=clusterdata（X，cutoff）T=clusterdata（X，param1，val1，param2，val2，…）輸出參數T包含n個元素的列向量，其元素為相應觀測所屬類的類序號。Curfoo為閾值。Clusterdata函數T=clusterdata（X，cutoff）T=clusterdata（X，param1，val1，param2，val2，…）系統聚類法的相關函數參數名參數值含義‘distance’Pdist函數所支持的metric參數的取值指定距離的計算方法‘linkage’Linkage函數所支持的method參數的取值指定系統聚類方法‘cutoff’正實數指定不一致系數或距離的閾值‘maxclust’正整數指定最大類數動態聚類法（快速聚類法/k均值聚類法）

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

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

用一個簡單的例子來說明動態聚類法的工作過程。例如我們要把圖中的點分成兩類。快速聚類的步驟：

1、隨機選取兩個點和作為凝聚點。

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

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

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

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

優點：計算量小，方法簡便，可以根據經驗，先作主觀分類。缺點：結果受選擇凝聚點好壞的影響，分類結果不穩定。選擇凝聚點和確定初始分類

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

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

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

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

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