徐晨凱，高茂庭

上海海事大學(xué)信息工程學(xué)院，上海 201306

改進(jìn)的最小生成樹自適應(yīng)分層聚類算法

徐晨凱，高茂庭

上海海事大學(xué)信息工程學(xué)院，上海 201306

1 引言

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

本文通過分析最小生成樹邊集內(nèi)邊的關(guān)系，提出一種改進(jìn)的最小生成樹自適應(yīng)分層聚類算法，根據(jù)最近鄰關(guān)系劃分最小生成樹的邊集，為每個(gè)聚類簇自動(dòng)生成合適的相對(duì)閾值來確定不一致邊；通過多次迭代去除不同邊的相互干擾；同時(shí)該算法能夠自適應(yīng)生成聚類數(shù)目，無需事先給定。在迭代過程中，因?yàn)樽罱応P(guān)系不再改變，所以大大加快了計(jì)算速度。實(shí)驗(yàn)驗(yàn)證了這種方法的有效性。

2 基本概念

2.1 最小生成樹聚類算法

傳統(tǒng)最小生成樹聚類算法[13]是一種基于圖論的全局聚類算法，一般算法如下：將全局?jǐn)?shù)據(jù)看成是一個(gè)完全圖，將數(shù)據(jù)作為結(jié)點(diǎn)，將數(shù)據(jù)與數(shù)據(jù)的距離作為權(quán)值，則根據(jù)最小生成樹算法得到一棵最小生成樹，再將這棵最小生成樹中權(quán)重大于閾值的邊刪除，剩余連通結(jié)點(diǎn)作為一類，即得聚類結(jié)果。

2.21 -NN分類算法

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

對(duì)于兩個(gè)結(jié)點(diǎn)，若這兩個(gè)結(jié)點(diǎn)互為最近鄰關(guān)系，則稱連接這兩個(gè)結(jié)點(diǎn)的邊為雙向最近鄰邊；若只存在某個(gè)結(jié)點(diǎn)是另一結(jié)點(diǎn)的最近鄰關(guān)系，則稱連接這兩個(gè)結(jié)點(diǎn)的邊為單向最近鄰邊；若這兩個(gè)結(jié)點(diǎn)不存在最近鄰關(guān)系則稱連接這兩個(gè)結(jié)點(diǎn)的邊為非最近鄰邊。

2.3 最小生成樹性質(zhì)

性質(zhì)1以某個(gè)端點(diǎn)為頂點(diǎn)的所有邊中，定有一條的另一個(gè)端點(diǎn)是該端點(diǎn)的最近鄰。

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

性質(zhì)2所得到的最小生成樹定有度為1的結(jié)點(diǎn)。

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

性質(zhì)3度為1的結(jié)點(diǎn)v1與所連接邊的另一個(gè)端點(diǎn)v2，則定有v2是v1的最近鄰。

證明：由性質(zhì)1，由于其相連接的點(diǎn)是唯一的，則該點(diǎn)定是其最近鄰結(jié)點(diǎn)。

2.4 最小生成樹聚類算法與1-NN分類算法的關(guān)系

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

3 基于最小生成樹的自適應(yīng)分層聚類算法

基于最小生成樹的自適應(yīng)分層聚類算法，以下簡稱TDMST，通過最近鄰邊關(guān)系，動(dòng)態(tài)地計(jì)算每個(gè)聚類簇的閾值，從而獲得較好的聚類結(jié)果。

3.1 基本概念

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

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

定義2對(duì)于一棵樹Tsub，若其結(jié)點(diǎn)集合是MSTobjs結(jié)點(diǎn)集的子集，其邊集也是MSTobjs邊集的子集，則稱該樹為MSTobjs的子樹，使用MSTsubobjs表示，其結(jié)點(diǎn)集用Vsub表示，邊集用EsubMST表示。即

顯然MSTobjs是一棵MSTsubobjs。

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

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

則根據(jù)一個(gè)控制參數(shù)ρ＞0，按計(jì)算方式：

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

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

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

3.2 基本性質(zhì)

性質(zhì)4按雙向最近鄰邊、單向最近鄰邊、無最近鄰關(guān)系區(qū)分最小生成樹的邊集EMST中的邊，所得集合為最小生成樹的邊集EMST的一個(gè)集合劃分。

證明：根據(jù)定義可得，對(duì)于一條邊，要么存在最近鄰關(guān)系，要么不存在最近鄰關(guān)系，當(dāng)存在最近鄰關(guān)系時(shí)，要么是單向的，要么是雙向的，又因?yàn)殡p向最近鄰邊、單向最近鄰邊、無最近鄰的前件是相互排斥的，所以不存在一條同時(shí)滿足兩個(gè)或兩個(gè)以上邊的條件，故最小生成樹的每一條邊存在且僅存在一個(gè)關(guān)系集合當(dāng)中。

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

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

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

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

3.3 算法思想

由上述定義可得，求數(shù)據(jù)集的聚類過程，實(shí)際上就是求解一個(gè)聚類簇集的過程，其中每一個(gè)MSTfinal對(duì)應(yīng)一個(gè)聚類簇。對(duì)于每一個(gè)MSTsubobjs均存在一個(gè)閾值Θsubobjs，則可以根據(jù)其閾值Θsubobjs判斷其是否穩(wěn)定。而根據(jù)最小樹性質(zhì)3中的證明，在MSTobjs中，以v為頂點(diǎn)的邊中，定有邊enear與其最近鄰相連，故對(duì)于任意一個(gè)頂點(diǎn)，定滿足性質(zhì)5或者性質(zhì)6的情況發(fā)生。為了保持最近鄰關(guān)系，所以應(yīng)該優(yōu)先去除非最近鄰邊，其次去除單向最近鄰邊，無需去除雙向最近鄰邊，根據(jù)以上優(yōu)先次序，當(dāng)一個(gè)MSTsubobjs的邊集要?jiǎng)h除一條雙向最近鄰邊時(shí)，其邊集內(nèi)定所有的邊均已是雙向最近鄰邊，而根據(jù)定理5，則此時(shí)所有邊權(quán)值定相等，則定不會(huì)大于閾值，故無需刪除雙向最近鄰邊，而對(duì)于一個(gè)MSTsubobjs的邊數(shù)總是有限的，故算法定可以收斂。

3.4 算法步驟

3.4.1 TDMST算法

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

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

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

（3）若隊(duì)列QueueMST為空，則執(zhí)行（6），否則執(zhí)行（4）。

（4）取出隊(duì)列QueueMST中的隊(duì)首MSTsubobjs，根據(jù)MSTsubobjs計(jì)算其閾值Θsubobjs，檢查該MSTsubobjs是否穩(wěn)定，若穩(wěn)定則將此MSTsubobjs作為MSTfinal放入到聚類結(jié)果集SetCluster中，執(zhí)行（3），否則執(zhí)行（5）。

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

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

3.4.2 子樹分裂算法

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

（1）SubMSTSet置為空。

（2）根據(jù)所得MSTsubobjs計(jì)算其閾值Θsubobjs，根據(jù)優(yōu)先級(jí)別去掉超過閾值的邊。

（3）重新遍歷一次MSTsubobjs，相互連接的結(jié)點(diǎn)作為新的MSTsubobjs，加入到SubMSTSet。

（4）返回SubMSTSet。

3.5 算法復(fù)雜度分析

對(duì)于初始MSTobjs的計(jì)算必須涉及關(guān)系完全圖G(V,E)，則設(shè)V的個(gè)數(shù)為N，則由于是完全圖，所以所需要計(jì)算的E的個(gè)數(shù)是N(N-1)/2；而對(duì)于最小生成樹算法，若使用Prim算法[14]的復(fù)雜度為O(N2)，使用Kruskal算法[14]的度為O(N2lbN)；對(duì)于計(jì)算閾值的復(fù)雜度為O(N)，而對(duì)于是否超過閾值也需要O(N)的復(fù)雜度；對(duì)于子樹分裂算法的復(fù)雜估計(jì)如下，因?yàn)橐豢脴渥疃酁镹-1條邊，刪去這些邊的算法復(fù)雜度至多為O(N)，后尋找連通的點(diǎn)的復(fù)雜度至多為O(N)，得分裂算法的復(fù)雜度至多為O(N)；而TDMST算法最多調(diào)用2K次分裂算法，其中K為聚類簇?cái)?shù)，所以TDMST的算法復(fù)雜度為O(NK)。

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)設(shè)計(jì)思路

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

4.2 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)設(shè)置采用二維點(diǎn)集，具體見描述表1，數(shù)據(jù)分布可視化顯示見圖1、圖2、圖3。

表1 實(shí)驗(yàn)數(shù)據(jù)集

圖1 Set1數(shù)據(jù)分布

圖2 Set2數(shù)據(jù)分布

圖3 Set3數(shù)據(jù)分布

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

4.3 實(shí)驗(yàn)準(zhǔn)確度測量方法

對(duì)于實(shí)驗(yàn)數(shù)據(jù)的聚類準(zhǔn)確度計(jì)算方法使用方法采用常見的查準(zhǔn)率（Precision）[17]，使用p表示。查準(zhǔn)率能夠較為直觀地反映出聚類結(jié)果和實(shí)際真實(shí)結(jié)果之間的差異，計(jì)算方法如下：

p=聚類簇正確數(shù)據(jù)點(diǎn)數(shù)/實(shí)際該類數(shù)據(jù)點(diǎn)總數(shù)

4.4 實(shí)驗(yàn)結(jié)果

各聚類算法實(shí)驗(yàn)最佳聚類結(jié)果見表2，同時(shí)本文還可視化了TDMST對(duì)各類數(shù)據(jù)的聚類結(jié)果，詳見圖4、圖5、圖6。

表2 各算法對(duì)實(shí)驗(yàn)數(shù)據(jù)的最佳聚類準(zhǔn)確度

圖4 TDMST對(duì)Set1的聚類結(jié)果

圖5 TDMST對(duì)Set2的聚類結(jié)果

圖6 TDMST對(duì)Set2的聚類結(jié)果

對(duì)于Set1數(shù)據(jù)集，與MST算法、DBSCAN算法相比，TDMST算法與k-means算法更能夠?qū)et1數(shù)據(jù)集進(jìn)行較為準(zhǔn)確的聚類，并且TDMST算法準(zhǔn)確度為100%。對(duì)于DBSCAN而言，由于類1的密度要小于類2和類3合并后的密度，所以導(dǎo)致若要合并類1，則類2和類3定合并，若要分開類2和類3，則類1也定被拆分成多個(gè)類；對(duì)于傳統(tǒng)的最小生成樹MST算法，由于簡單地使用一個(gè)全局閾值，類1的類內(nèi)距離大于類2和類3間的距離，從而導(dǎo)致與DBSCAN算法一樣的情況；但是實(shí)際上，類1與類2、類3的類間距離要遠(yuǎn)遠(yuǎn)大于類1的類內(nèi)距離，其類邊界非常明顯，而正是因?yàn)槭褂昧巳珠撝挡艜?huì)導(dǎo)致算法對(duì)類1、類2及類3無法準(zhǔn)確區(qū)分的現(xiàn)象發(fā)生。雖然k-means算法的準(zhǔn)確度非常高，但是由于k-means非常依賴初始位置[17]，所以其要取得如此高的準(zhǔn)確度要求較高。

對(duì)于Set2數(shù)據(jù)集，k-means算法只適合區(qū)分凸形狀的聚類簇[17]，所以在這個(gè)實(shí)驗(yàn)集上準(zhǔn)確度較低，而TDMST算法和DBSCAN算法都適合區(qū)分任意形狀的聚類簇，所以準(zhǔn)確度達(dá)到100%，同樣，雖然MST也可以區(qū)分任意形狀的聚類簇，但是由于其使用全局的閾值，所以造成了一些數(shù)據(jù)點(diǎn)的誤分。

對(duì)于Set3數(shù)據(jù)集，由于k-means算法對(duì)于噪聲點(diǎn)敏感[15]，所以在這個(gè)實(shí)驗(yàn)集上準(zhǔn)確度依然不高；DBSCAN算法由于噪聲的影響，會(huì)導(dǎo)致密度的改變[16]，從而影響聚類結(jié)果。

對(duì)于TDMST而言，其表現(xiàn)最重要的還是閾值的選取，閾值的大小決定了聚類的靈敏度，閾值較小時(shí)，不滿足的閾值邊就多，導(dǎo)致聚類簇的數(shù)目的增加。

4.5 實(shí)驗(yàn)結(jié)論

由實(shí)驗(yàn)結(jié)果可知：

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

（2）雖然TDMST算法對(duì)于閾值的選取更多是憑借經(jīng)驗(yàn)，但是實(shí)際中是借用了統(tǒng)計(jì)學(xué)上的顯著性的概念，所以具有一定的數(shù)學(xué)意義[3]。

（3）由于TDMST采用的是距離判斷，所以TDMST能夠很好地適應(yīng)空間數(shù)據(jù)分布不均的現(xiàn)象，可以發(fā)現(xiàn)任意形狀的聚類簇。

（4）由于TDMST算法本質(zhì)上采用的是最近鄰思想，即“一個(gè)數(shù)據(jù)點(diǎn)與其最近鄰?fù)瑢儆谝粋€(gè)類別”，算法建立在該假設(shè)基礎(chǔ)上，這就注定了其算法本身更適合低維空間。

5 結(jié)束語

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

[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]葉青，唐鵬舉.一種改進(jìn)的基于MST的聚類算法[J].計(jì)算機(jī)與現(xiàn)代化，2011（8）：17-22.

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

[6]陳新泉.一種基于MST的自適應(yīng)優(yōu)化相異性度量的半監(jiān)督聚類方法[J].計(jì)算機(jī)工程與科學(xué)，2011，33（10）：154-158.

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

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

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

[10]金欣，王晶，沈奇威.分布式最小生成樹聚類的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2011，20（7）：69-75.

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

[12]歐陽浩，肖建華.基于網(wǎng)格的最小生成樹聚類算法[J].計(jì)算機(jī)與現(xiàn)代化，2006（12）：81-83.

[13]Jain A，Murty M，F(xiàn)lynn 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].軟件學(xué)報(bào)，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

針對(duì)傳統(tǒng)最小生成樹聚類算法需要事先知道聚類數(shù)目和使用靜態(tài)全局分類依據(jù)，導(dǎo)致聚類密度相差較大時(shí)，算法有效性下降，計(jì)算復(fù)雜度大等問題，提出一種改進(jìn)的最小生成樹自適應(yīng)分層聚類算法，根據(jù)最近鄰關(guān)系，自動(dòng)為每個(gè)聚類簇設(shè)定獨(dú)立的閾值，使之適應(yīng)分布密度相差較大的情況，并能自動(dòng)確定聚類數(shù)目。實(shí)驗(yàn)表明，算法具有較好的性能，尤其對(duì)數(shù)據(jù)密度分布不均勻的情況也能得到較好的聚類結(jié)果。

最近鄰；自適應(yīng)聚類；最小生成樹；聚類分析

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.

上海市科委科技創(chuàng)新項(xiàng)目（No.12595810200）；上海海事大學(xué)科研項(xiàng)目。

徐晨凱（1989—），男，碩士研究生，CCF學(xué)生會(huì)員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘；高茂庭（1963—），男，博士，教授，系統(tǒng)分析員，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，數(shù)據(jù)庫與信息系統(tǒng)。E-mail：kk9265w@gmail.com

2012-12-21

2013-04-01

1002-8331（2014）22-0149-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-04-18,http://www.cnki.net/kcms/detail/11.2127.TP.20130418.1618.021.html