改進的最小生成樹自適應分層聚類算法

徐晨凱，高茂庭

上海海事大學信息工程學院，上海 201306

改進的最小生成樹自適應分層聚類算法

徐晨凱，高茂庭

上海海事大學信息工程學院，上海 201306

1 引言

聚類是將物理或者抽象的集合分組成為由類似的對象組成的多個類的過程[1]，其中最小生成樹聚類方法已被廣泛地研究[2-12]，而如何快速準確地確定不一致邊是一個關鍵問題。文[2]中使用全局靜態閾值確定不一致邊，當聚類簇密度相差較大時，聚類效果并不理想；文[3]中使用相對閾值來確定不一致邊，但是往往受到不同邊的相互干擾，從而使聚類結果不準確；文[4]使用影響域來確定不一致邊，但是計算量稍大；文[9]結合了密度的方法來加強聚類的準確度；文[11]添加控制點及優先級的方法來優化聚類結果，但增加控制點需要更多的先驗知識；文[12]結合網格的方法增強抵抗噪聲的能力。

本文通過分析最小生成樹邊集內邊的關系，提出一種改進的最小生成樹自適應分層聚類算法，根據最近鄰關系劃分最小生成樹的邊集，為每個聚類簇自動生成合適的相對閾值來確定不一致邊；通過多次迭代去除不同邊的相互干擾；同時該算法能夠自適應生成聚類數目，無需事先給定。在迭代過程中，因為最近鄰關系不再改變，所以大大加快了計算速度。實驗驗證了這種方法的有效性。

2 基本概念

2.1 最小生成樹聚類算法

傳統最小生成樹聚類算法[13]是一種基于圖論的全局聚類算法，一般算法如下：將全局數據看成是一個完全圖，將數據作為結點，將數據與數據的距離作為權值，則根據最小生成樹算法得到一棵最小生成樹，再將這棵最小生成樹中權重大于閾值的邊刪除，剩余連通結點作為一類，即得聚類結果。

2.21 -NN分類算法

1-NN分類算法就是k-NN算法當k=1的情況，所以1-NN算法的算法思想和k-NN算法思想是一樣的，即在訓練樣本中找到最近樣本的k個最近鄰。所謂最近鄰，即為到該點距離最小的點稱為該點的最近鄰。對于距離[12]計算方法有很多，常見的如歐氏距離、曼哈頓距離、余弦距離等，本文使用的是歐氏距離，以下簡稱距離。

對于兩個結點，若這兩個結點互為最近鄰關系，則稱連接這兩個結點的邊為雙向最近鄰邊；若只存在某個結點是另一結點的最近鄰關系，則稱連接這兩個結點的邊為單向最近鄰邊；若這兩個結點不存在最近鄰關系則稱連接這兩個結點的邊為非最近鄰邊。

2.3 最小生成樹性質

性質1以某個端點為頂點的所有邊中，定有一條的另一個端點是該端點的最近鄰。

證明：假設v1是v2的最近鄰，則e(v1,v2)比e(v1,vn)都小，而v1,v2在其最小生成樹T內卻沒有邊，則v2顯然定在最小生成樹T內，故一定存在e(vk,v2)(k≠1)，則先將T中e(vk,v2)移除，添加e(v1,v2)，則顯然所得也是一棵生成樹，且其權值和小于T的權值和，這與T是最小生成樹矛盾[3]。

性質2所得到的最小生成樹定有度為1的結點。

證明：結點數為n的圖的最小生成樹邊數為n-1，而度為邊數的2倍，則該圖的度為2n-1，若所有結點的度大于1，則該圖的度至少為2n矛盾，即可證明。

性質3度為1的結點v1與所連接邊的另一個端點v2，則定有v2是v1的最近鄰。

證明：由性質1，由于其相連接的點是唯一的，則該點定是其最近鄰結點。

2.4 最小生成樹聚類算法與1-NN分類算法的關系

由上述幾個性質可得，若每次都將度為1的點移除，若最后出現兩個點一條邊的情況，則任意移除一個點，即可得一個以最近鄰為關系的序列，由于結點數為n，邊數為n-1，定能留下一個結點，然后以該結點為起始點，反向使用前面所得的最近鄰序列，可以發現，其實際上就是1-NN算法的步驟。所以，可以這樣近似地認為，最小生成樹全局聚類算法就是1-NN分類算法在聚類上的實現，最小生成樹算法思想中包含最近鄰規則。而從關系的角度，可以發現，最小生成樹是1-NN關系圖的一個子圖，所以最小生成樹是最近鄰關系的一個簡化。

3 基于最小生成樹的自適應分層聚類算法

基于最小生成樹的自適應分層聚類算法，以下簡稱TDMST，通過最近鄰邊關系，動態地計算每個聚類簇的閾值，從而獲得較好的聚類結果。

3.1 基本概念

定義1計算實體兩兩之間的距離可以得到一個完全圖G(V,E)，其中V為G的點集，E為G的邊集，一條邊e的權重用W(e)表示，則對于G所對應的權值和最小的生成樹稱為該圖的最小生成樹[14]，用MSTobjs表示。其中objs為實體集合，即

其中EMST是最小生成樹中的邊集。

定義2對于一棵樹Tsub，若其結點集合是MSTobjs結點集的子集，其邊集也是MSTobjs邊集的子集，則稱該樹為MSTobjs的子樹，使用MSTsubobjs表示，其結點集用Vsub表示，邊集用EsubMST表示。即

顯然MSTobjs是一棵MSTsubobjs。

定義3若一個集合內的所有元素都是同一個MSTobjs的MSTsubobjs，并且所有MSTsubobjs的點集相交為空，則稱該集合為MSTobjs的子樹集，使用SubMSTSet表示，即

定義4對于一棵MSTsubobjs，使用矩估計方法來估計其邊e的均值，計算方式：

則根據一個控制參數ρ＞0，按計算方式：

所得值Θ作為這棵MSTsubobjs閾值，用Θsubobjs表示。

定義5對于一棵MSTsubobjs，若其所有邊都小于等于其閾值，則稱為穩定子樹，用MSTfinal表示，即

定義6若一個SubMSTSet集合內的所有MSTsubobjs均為MSTfinal，則稱該子樹集為聚類簇集，用ClusterSet表示，即

3.2 基本性質

性質4按雙向最近鄰邊、單向最近鄰邊、無最近鄰關系區分最小生成樹的邊集EMST中的邊，所得集合為最小生成樹的邊集EMST的一個集合劃分。

證明：根據定義可得，對于一條邊，要么存在最近鄰關系，要么不存在最近鄰關系，當存在最近鄰關系時，要么是單向的，要么是雙向的，又因為雙向最近鄰邊、單向最近鄰邊、無最近鄰的前件是相互排斥的，所以不存在一條同時滿足兩個或兩個以上邊的條件，故最小生成樹的每一條邊存在且僅存在一個關系集合當中。

性質5若頂點v∈V，設以v作為頂點的邊有e1,e2,…,en，其中ed(1≤d≤n)為雙向最近鄰邊，則有以下關系：

證明：假設存在ei(1≤i≤n)，W(ei)＜W(ed)，則ed的另一個端點不是v的最近鄰，這與ed是雙向最近鄰邊矛盾。

性質6若頂點v∈V，設以v作為頂點的邊有e1,e2,…,en，其中es(1≤s≤n)是單向最近鄰邊，并且該邊表示為v的最近鄰，則有以下關系：

證明：假設存在ei(1≤i≤n)，W(ei)＜W(es)，則ed的另一個端點不是v的最近鄰，這與es是單向向最近鄰邊矛盾。

3.3 算法思想

由上述定義可得，求數據集的聚類過程，實際上就是求解一個聚類簇集的過程，其中每一個MSTfinal對應一個聚類簇。對于每一個MSTsubobjs均存在一個閾值Θsubobjs，則可以根據其閾值Θsubobjs判斷其是否穩定。而根據最小樹性質3中的證明，在MSTobjs中，以v為頂點的邊中，定有邊enear與其最近鄰相連，故對于任意一個頂點，定滿足性質5或者性質6的情況發生。為了保持最近鄰關系，所以應該優先去除非最近鄰邊，其次去除單向最近鄰邊，無需去除雙向最近鄰邊，根據以上優先次序，當一個MSTsubobjs的邊集要刪除一條雙向最近鄰邊時，其邊集內定所有的邊均已是雙向最近鄰邊，而根據定理5，則此時所有邊權值定相等，則定不會大于閾值，故無需刪除雙向最近鄰邊，而對于一個MSTsubobjs的邊數總是有限的，故算法定可以收斂。

3.4 算法步驟

3.4.1 TDMST算法

TDMST算法需要調用子樹分裂算法，通過子樹分裂算法將MSTsubobjs中超過閾值Θsubobjs的邊去除，分裂成若干個新的MSTsubobjs。算法分成以下幾個步驟：

（1）初始化，將用來存放最終聚類結果的集合ClusterSet置為空，使用一個隊列QueueMST用來存放待檢測的MSTsubobjs是否為MSTfinal，置空QueueMST。

（2）計算實體間的距離，構成關系完全圖G(V,E,W)，使用最小生成樹算法得到G的一個MSTobjs，將其作為起始的MSTsubobjs加入到隊列QueueMST。

（3）若隊列QueueMST為空，則執行（6），否則執行（4）。

（4）取出隊列QueueMST中的隊首MSTsubobjs，根據MSTsubobjs計算其閾值Θsubobjs，檢查該MSTsubobjs是否穩定，若穩定則將此MSTsubobjs作為MSTfinal放入到聚類結果集SetCluster中，執行（3），否則執行（5）。

（5）將MSTsubobjs作為參數傳給子樹分裂算法，后將子樹分裂算法返回的SubMSTSet中所有的MSTsubobjs放入到隊列QueueMST中，執行（3）。

（6）將集合SetCluster作為結果返回，算法結束。

3.4.2 子樹分裂算法

子樹分裂算法是將一個MSTsubobjs變成若干個MSTsubobjs的方法，具體步驟如下：

（1）SubMSTSet置為空。

（2）根據所得MSTsubobjs計算其閾值Θsubobjs，根據優先級別去掉超過閾值的邊。

（3）重新遍歷一次MSTsubobjs，相互連接的結點作為新的MSTsubobjs，加入到SubMSTSet。

（4）返回SubMSTSet。

3.5 算法復雜度分析

對于初始MSTobjs的計算必須涉及關系完全圖G(V,E)，則設V的個數為N，則由于是完全圖，所以所需要計算的E的個數是N(N-1)/2；而對于最小生成樹算法，若使用Prim算法[14]的復雜度為O(N2)，使用Kruskal算法[14]的度為O(N2lbN)；對于計算閾值的復雜度為O(N)，而對于是否超過閾值也需要O(N)的復雜度；對于子樹分裂算法的復雜估計如下，因為一棵樹最多為N-1條邊，刪去這些邊的算法復雜度至多為O(N)，后尋找連通的點的復雜度至多為O(N)，得分裂算法的復雜度至多為O(N)；而TDMST算法最多調用2K次分裂算法，其中K為聚類簇數，所以TDMST的算法復雜度為O(NK)。

4 實驗與分析

4.1 實驗設計思路

本文設計了三個對照實驗，將本文算法與傳統最小生成樹MST算法[2]、k-means算法[15]、DBSCAN算法[16]進行比較，從而驗證本文算法在聚類密度相差較大時依然可以有效聚類；同時對于傳統基于最小生成樹算法適用的情況本文算法同樣適用。實驗一主要驗證在聚類密度相差較大時本文算法依然可以得到較好的聚類結果，而其他傳統聚類算法無法適應；實驗二驗證本文算法和其他部分傳統聚類算法一樣可以區分任意形狀；實驗三驗證本文算法能夠在一定的噪聲影響下，取得較理想的聚類結果。

4.2 實驗數據

實驗設置采用二維點集，具體見描述表1，數據分布可視化顯示見圖1、圖2、圖3。

表1 實驗數據集

圖1 Set1數據分布

圖2 Set2數據分布

圖3 Set3數據分布

由圖可較為直觀地得到Set1中共4個類別，其中類別1較為稀疏；類別2和類別3較為緊密，并且類間距離較小；類別4是一些孤立點。Set2中共有5個類別，其中類別1和類別2呈螺旋狀；類3較為分散；類4較為緊密；類5是一個孤立點。Set3共有4類，其中類1，類2，類3，類4分別代表圖形數字1，2，3，4，并有其他離散點作為噪聲，隨機分布在該4類點集周圍。

4.3 實驗準確度測量方法

對于實驗數據的聚類準確度計算方法使用方法采用常見的查準率（Precision）[17]，使用p表示。查準率能夠較為直觀地反映出聚類結果和實際真實結果之間的差異，計算方法如下：

p=聚類簇正確數據點數/實際該類數據點總數

4.4 實驗結果

各聚類算法實驗最佳聚類結果見表2，同時本文還可視化了TDMST對各類數據的聚類結果，詳見圖4、圖5、圖6。

表2 各算法對實驗數據的最佳聚類準確度

圖4 TDMST對Set1的聚類結果

圖5 TDMST對Set2的聚類結果

圖6 TDMST對Set2的聚類結果

對于Set1數據集，與MST算法、DBSCAN算法相比，TDMST算法與k-means算法更能夠對Set1數據集進行較為準確的聚類，并且TDMST算法準確度為100%。對于DBSCAN而言，由于類1的密度要小于類2和類3合并后的密度，所以導致若要合并類1，則類2和類3定合并，若要分開類2和類3，則類1也定被拆分成多個類；對于傳統的最小生成樹MST算法，由于簡單地使用一個全局閾值，類1的類內距離大于類2和類3間的距離，從而導致與DBSCAN算法一樣的情況；但是實際上，類1與類2、類3的類間距離要遠遠大于類1的類內距離，其類邊界非常明顯，而正是因為使用了全局閾值才會導致算法對類1、類2及類3無法準確區分的現象發生。雖然k-means算法的準確度非常高，但是由于k-means非常依賴初始位置[17]，所以其要取得如此高的準確度要求較高。

對于Set2數據集，k-means算法只適合區分凸形狀的聚類簇[17]，所以在這個實驗集上準確度較低，而TDMST算法和DBSCAN算法都適合區分任意形狀的聚類簇，所以準確度達到100%，同樣，雖然MST也可以區分任意形狀的聚類簇，但是由于其使用全局的閾值，所以造成了一些數據點的誤分。

對于Set3數據集，由于k-means算法對于噪聲點敏感[15]，所以在這個實驗集上準確度依然不高；DBSCAN算法由于噪聲的影響，會導致密度的改變[16]，從而影響聚類結果。

對于TDMST而言，其表現最重要的還是閾值的選取，閾值的大小決定了聚類的靈敏度，閾值較小時，不滿足的閾值邊就多，導致聚類簇的數目的增加。

4.5 實驗結論

由實驗結果可知：

（1）TDMST算法的聚類效果要好于傳統最小生成樹MST算法，在大部分情況下優于DBSCAN，在不同形狀的聚類上，其聚類結果比k-means算法更優。并且TDMST算法的控制參數只有一個，在使用上比需要設置兩個參數的DBSCAN更為方便，并且不受初始值的影響。

（2）雖然TDMST算法對于閾值的選取更多是憑借經驗，但是實際中是借用了統計學上的顯著性的概念，所以具有一定的數學意義[3]。

（3）由于TDMST采用的是距離判斷，所以TDMST能夠很好地適應空間數據分布不均的現象，可以發現任意形狀的聚類簇。

（4）由于TDMST算法本質上采用的是最近鄰思想，即“一個數據點與其最近鄰同屬于一個類別”，算法建立在該假設基礎上，這就注定了其算法本身更適合低維空間。

5 結束語

本文提出了一種基于最小生成樹的自適應閾值自頂向下分層聚類算法，該算法基于最小生成樹，簡化最近鄰關系，并且統計當前最小生成樹邊集的均值及方差來計算得出閾值，有效地獲取了聚類結果。一方面，由于最近鄰思想在高維數據無法有效地應用，所以對高維數據而言，聚類之前應該先做一個合適的降維過程，以減少維數對于算法的影響，同時有效地降低算法計算量；另一方面，TDMST算法的優勢在于能夠自動確定閾值，是否可以結合一些有效的聚類模型從而進行高維的聚類，將是下一步的工作。

[1]Han J W，Kamber M.Data mining：concepts and techniques[M]. San Francisco：Morgan Kaufmann，2000.

[2]Gygorash O，Zhou Yan，Jorgensen Z.Minimum spanning tree based clustering algorithms[C]//18th IEEE International Conference on Tools with Artificial Intelligence，2006：73-81.

[3]Zahn C T.Graph-theoretical methods for detecting and describing gestalt clusters[J].IEEE Transactions on Computers，1971，20（1）：68-86.

[4]葉青，唐鵬舉.一種改進的基于MST的聚類算法[J].計算機與現代化，2011（8）：17-22.

[5]王小樂，劉青寶，陸昌輝.一種最小生成樹聚類算法[J].小型微型計算機系統，2009，30（5）：877-882.

[6]陳新泉.一種基于MST的自適應優化相異性度量的半監督聚類方法[J].計算機工程與科學，2011，33（10）：154-158.

[7]李密青，鄭金華，羅彪.一種基于最小生成樹的多目標進化算法[J].計算機研究與發展，2009，46（5）：803-813.

[8]毛韶陽，李肯立，王志和.最小生成樹聚類方法研究[J].懷化學院學報，2007，26（5）：38-39.

[9]崔光照，曹玲芝，張勛才，等.基于密度的最小生成樹聚類算法研究[J].計算機工程與應用，2006（5）：156-158.

[10]金欣，王晶，沈奇威.分布式最小生成樹聚類的設計與實現[J].計算機系統應用，2011，20（7）：69-75.

[11]汪閩，周成虎，裴韜，等.一種帶控制節點的最小生成樹聚類算法[J].中國圖象圖形學報，2002，8（7）：765-770.

[12]歐陽浩，肖建華.基于網格的最小生成樹聚類算法[J].計算機與現代化，2006（12）：81-83.

[13]Jain A，Murty M，Flynn P.Data clustering：A review[J]. ACM Computing Surveys，1999，31（3）：264-323.

[14]Graham R L，Hell Pavol.On the History of the Minimum SpanningTreeProblem[J].AnnalsoftheHistoryof Computing，1985，7（1）：43-57.

[15]Macqueen J.Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th BerkeleySymposiumonMathematicalStatisticsand Probability，1967：281-297.

[16]Ester M，Kriegel H P，Sander J，et al.A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceeding the 2nd International Conference on Knowledge Discovery and Data Mining（KDD），Portland，1996：226-231.

[17]孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學報，2008，19（1）：48-61.

XU Chenkai,GAO Maoting

College of Information Engineering,Shanghai Maritime University,Shanghai 201306,China

Classical clustering algorithm based on the minimum spanning tree often needs to know the number of clusters beforehand and use static global threshold to cluster,which leads to the performance of the algorithm low and the computation complex for the uneven distributed data.An improved adaptive hierarchical clustering algorithm based on minimum spanning tree is proposed,which automatically generates different thresholds for every cluster to adapt for the uneven distributed data according to the nearest neighbor relationship and adaptively determines the number of clusters.Experiments demonstrate that this algorithm has good performance,especially could cluster effectively for the uneven distributed data. Key words：nearest neighbor;adaptive clustering;minimum spanning tree;clustering analysis

針對傳統最小生成樹聚類算法需要事先知道聚類數目和使用靜態全局分類依據，導致聚類密度相差較大時，算法有效性下降，計算復雜度大等問題，提出一種改進的最小生成樹自適應分層聚類算法，根據最近鄰關系，自動為每個聚類簇設定獨立的閾值，使之適應分布密度相差較大的情況，并能自動確定聚類數目。實驗表明，算法具有較好的性能，尤其對數據密度分布不均勻的情況也能得到較好的聚類結果。

最近鄰；自適應聚類；最小生成樹；聚類分析

A

TP311

10.3778/j.issn.1002-8331.1212-0253

XU Chenkai,GAO Maoting.Improved adaptive hierarchical clustering algorithm based on minimum spanning tree.Computer Engineering and Applications,2014,50（22）：149-153.

上海市科委科技創新項目（No.12595810200）；上海海事大學科研項目。

徐晨凱（1989—），男，碩士研究生，CCF學生會員，主要研究領域為數據挖掘；高茂庭（1963—），男，博士，教授，系統分析員，CCF高級會員，主要研究領域為數據挖掘，數據庫與信息系統。E-mail：kk9265w@gmail.com

2012-12-21

2013-04-01

1002-8331（2014）22-0149-05

CNKI網絡優先出版：2013-04-18,http://www.cnki.net/kcms/detail/11.2127.TP.20130418.1618.021.html