基于互近鄰相對距離的最小生成樹聚類算法

程汝峰， 劉奕志， 梁永全,2

(1.山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院 山東 青島 266590； 2.山東省智慧礦山信息技術(shù)重點(diǎn)實(shí)驗(yàn)室 山東 青島 266590)

基于互近鄰相對距離的最小生成樹聚類算法

程汝峰1， 劉奕志1， 梁永全1,2

(1.山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院 山東 青島 266590； 2.山東省智慧礦山信息技術(shù)重點(diǎn)實(shí)驗(yàn)室 山東 青島 266590)

針對互近鄰距離的不足，提出了互近鄰相對距離的概念，同時(shí)設(shè)計(jì)實(shí)現(xiàn)了一種新的最小生成樹聚類算法.針對某些數(shù)據(jù)的不平衡問題，提出了兼容不平衡數(shù)據(jù)的最小生成樹分割方法.算法設(shè)計(jì)簡單，易于實(shí)現(xiàn).實(shí)驗(yàn)結(jié)果表明，該算法能夠聚類任意形狀數(shù)據(jù)和兼容處理不均衡數(shù)據(jù).對于具有良好幾何形狀的數(shù)據(jù)，該算法能夠達(dá)到非常好的聚類效果，總體性能優(yōu)于其他算法.

聚類； 互近鄰相對距離； 最小生成樹； 不平衡數(shù)據(jù)

0 引言

聚類是數(shù)據(jù)挖掘領(lǐng)域的重要研究內(nèi)容之一，在識別數(shù)據(jù)的內(nèi)在結(jié)構(gòu)方面具有極其重要的作用.文獻(xiàn)[1-4]對相關(guān)算法進(jìn)行了研究.劃分方法中經(jīng)典的有K-means算法[5]、K-medoids算法[6]等；層次方法中經(jīng)典的有CHAMELEON算法[7]、BIRCH算法[8]等；基于密度的方法中經(jīng)典的有DBSCAN算法[9]、OPTICS算法[10]等；基于網(wǎng)格的方法中經(jīng)典的有STING算法[11]等.

近幾年，研究者從不同角度提出了許多優(yōu)秀的算法.例如，文獻(xiàn)[12]將密度的思想和距離相結(jié)合，提出一種快速的密度峰值聚類(DPC)算法.文獻(xiàn)[13-14]在DPC算法的基礎(chǔ)上，提出兩種基于K近鄰的樣本分配策略.文獻(xiàn)[15]提出一種基于數(shù)據(jù)點(diǎn)間信息傳遞的聚類算法(AP).針對數(shù)據(jù)的不平衡問題，文獻(xiàn)[16]將概率模型選擇和參數(shù)優(yōu)化估計(jì)的方法用于聚類，算法在不平衡數(shù)據(jù)集上有很好的表現(xiàn).此外，圖論的很多方法也被用來解決聚類問題.例如，文獻(xiàn)[17]對基于最小生成樹的圖論聚類方法進(jìn)行了分析.文獻(xiàn)[18]采用生成兩輪最小生成樹的方法，能夠?qū)Ω鞣N大小、形狀和密度的數(shù)據(jù)實(shí)現(xiàn)聚類.文獻(xiàn)[19]將最小生成樹應(yīng)用于數(shù)據(jù)的分割和合并過程，提出一種新的層次聚類算法.本文在相似性計(jì)算方法的基礎(chǔ)上，提出了一種新的非度量距離計(jì)算方法，利用最小生成樹的方法實(shí)現(xiàn)數(shù)據(jù)的聚類.算法設(shè)計(jì)簡單，易于實(shí)現(xiàn)，同時(shí)可以聚類任意形狀數(shù)據(jù)和兼容處理不均衡數(shù)據(jù).對于連通性較好的數(shù)據(jù)，算法具有很好的聚類效果.

1 算法的理論基礎(chǔ)

1.1 互近鄰相對距離

距離計(jì)算是很多學(xué)習(xí)任務(wù)的基本問題.閔可夫斯基距離提供了距離計(jì)算的一般形式，這類距離被稱為度量距離.此外還有非度量距離，互近鄰距離(mutual neighbor distance)就是其中一種.

互近鄰距離[20-21]的定義為

MND(xi,xj)=NN(xi,xj)+NN(xj,xi),

式中：NN(xi,xj)表示xi是xj的第幾近鄰點(diǎn);MND(xi,xj)表示xi與xj的互近鄰距離.顯然有MND(xi,xj)=MND(xj,xi).

互近鄰距離相對于度量距離有很多優(yōu)點(diǎn).為了將互近鄰距離與度量距離的優(yōu)點(diǎn)相結(jié)合，本文提出互近鄰相對距離(mutualneighborrelativedistance)的概念.

首先給出基距離(basedistance)的定義為

式中：d(xi,xj)表示xi與xj之間的某種距離，如常用的歐氏距離；BD(xi,k)表示xi的k近鄰基距離，代表了xi的距離衡量標(biāo)準(zhǔn).本文采用k=n，此時(shí)將xi的基距離簡記為BD(xi).

互近鄰相對距離的定義為

MNRD(xi,xj)=NNR(xi,xj)+NNR(xj,xi)，

1.2 最小生成樹聚類

許多優(yōu)化問題都可以轉(zhuǎn)化為求解最小生成樹問題[22].最小生成樹也被廣泛應(yīng)用于旅行商[23]、文本聚類[24]、基因表達(dá)數(shù)據(jù)分析[25]等領(lǐng)域.最小生成樹聚類的第一步是構(gòu)建最小生成樹，圖的節(jié)點(diǎn)對應(yīng)于被分析數(shù)據(jù)的最小單元，圖的邊(或弧)對應(yīng)于處理數(shù)據(jù)之間的相似性度量.比較經(jīng)典的最小生成樹求解算法有 prim 算法和 kruskal 算法，其中prim算法適用于邊較多的情況.得到最小生成樹后，需要對最小生成樹進(jìn)行分割.若聚成k個簇，則需要k-1次分割.對于有n個結(jié)點(diǎn)的最小生成樹，共包含n-1條邊.一般的分割策略是搜索權(quán)重最大(相似性最小)的邊進(jìn)行分割，但是這種分割不能解決數(shù)據(jù)的不平衡問題.不同的分割策略如圖1所示，雖然圖中最小生成樹的各邊權(quán)重相同，但是考慮到平衡問題，對不同邊進(jìn)行分割的結(jié)果顯然并不相同.

考慮到分割后數(shù)據(jù)的不平衡問題，需要引入平衡度的定義.數(shù)據(jù)集D包含n條數(shù)據(jù)，設(shè)分割某條邊e后新形成兩個簇為C1和C2，用a和b分別表示兩個簇中包含樣本的個數(shù)，并且a≤b，則邊e的平衡度的計(jì)算公式為

另外，數(shù)據(jù)本身也可能是不平衡的，因此需要引入平衡估計(jì)參數(shù)p，平衡估計(jì)參數(shù)根據(jù)先驗(yàn)知識設(shè)定.加入?yún)?shù)p后，相應(yīng)平衡度調(diào)整公式為

平衡度的計(jì)算如圖2所示，最小生成樹共包含10個樣本點(diǎn)，若設(shè)p=0.6，計(jì)算得到pe=1.

圖1 不同的分割策略Fig.1 Different segmentation strategies

圖2 平衡度的計(jì)算Fig.2 Calculation of equilibrium degree

將邊界權(quán)重和平衡度的乘積作為分割參數(shù)，在最小生成樹分割的過程中，每次選擇分割參數(shù)最大的邊.經(jīng)過多次分割，最終實(shí)現(xiàn)聚類.

2 算法描述

算法的核心是相似性矩陣的計(jì)算和最小生成樹的分割.聚類算法的過程如下：

輸入：數(shù)據(jù)集D，平衡參數(shù)p，簇的個數(shù)k；

輸出：聚類結(jié)果.

1： 利用互近鄰相對距離計(jì)算距離矩陣G.

2： 使用prim算法計(jì)算得到最小生成樹T；最小生成樹中邊的權(quán)重向量為VT.

3： 計(jì)算最小生成樹中每條邊的平衡度，生成向量PT.

4： 進(jìn)行k-1輪迭代.

5：VPT=VT.*PT；%“.*”表示對應(yīng)相乘.

6： 找到VPT中的最大值對應(yīng)的邊e；將邊e從T中刪除.

7： 從VT中刪除邊e對應(yīng)的權(quán)重；計(jì)算并更新PT.

8： 根據(jù)T的劃分，將數(shù)據(jù)集D劃分成k個簇.

算法主要由以下三部分組成：根據(jù)互近鄰相對距離得到鄰接矩陣，其時(shí)間復(fù)雜度為O(n2)；求解最小生成樹，假設(shè)是鄰接矩陣的存儲方式，最大時(shí)間復(fù)雜度為O(n2)；分割最小生成樹，分割之前需要計(jì)算平衡度，因此需要統(tǒng)計(jì)邊兩端的子樹分別包含多少點(diǎn).子樹包含點(diǎn)的信息可以事先計(jì)算存儲，邊分割后運(yùn)行更新即可.分割最小生成樹的時(shí)間復(fù)雜度為O(n).

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

實(shí)驗(yàn)分為人工數(shù)據(jù)集實(shí)驗(yàn)和真實(shí)數(shù)據(jù)集實(shí)驗(yàn)兩部分.對比算法分別為DPC、AP、DBSCAN、K-means、CHAMELEON和2-MSTClus[18].其中K-means算法調(diào)用Matlab中的庫函數(shù)，其他算法采用作者提供的源碼或程序.聚類效果判斷標(biāo)準(zhǔn)采用ACC、AMI和ARI評價(jià)指標(biāo).3種指標(biāo)的取值上界為1，取值越大表示聚類結(jié)果越好.對于真實(shí)數(shù)據(jù)本文進(jìn)行了預(yù)處理，均歸一化到[0,1].實(shí)驗(yàn)所用人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集如表1和表2所示.

表1 人工數(shù)據(jù)集

表2 真實(shí)數(shù)據(jù)集

3.1 人工數(shù)據(jù)集實(shí)驗(yàn)結(jié)果分析

人工數(shù)據(jù)集為2維或3維數(shù)據(jù)，方便可視化.在人工數(shù)據(jù)集上進(jìn)行測試，聚類結(jié)果以圖的方式展示，不同灰度和形狀的數(shù)據(jù)代表不同的簇.聚類數(shù)據(jù)會有多種形式，其中比較容易聚類的是明顯分離的數(shù)據(jù)，如圖3和圖4所示.對于比較復(fù)雜的數(shù)據(jù)，算法也可以很好地實(shí)現(xiàn)聚類，如圖5～圖8所示.

圖3 Twenty數(shù)據(jù)集聚類結(jié)果Fig.3 Clustering results of Twenty data set

圖4 Hypercube數(shù)據(jù)集聚類結(jié)果Fig.4 Clustering results of Hypercube data set

圖5 Compound數(shù)據(jù)集聚類結(jié)果Fig.5 Clustering results of Compound data set

圖6 Impossible數(shù)據(jù)集聚類結(jié)果Fig.6 Clustering results of Impossible data set

圖7 D31數(shù)據(jù)集聚類結(jié)果Fig.7 Clustering results of D31 data set

圖8 Q58數(shù)據(jù)集聚類結(jié)果Fig.8 Clustering results of Q58 data set

通過調(diào)節(jié)參數(shù)p，算法能夠?qū)Σ黄胶鈹?shù)據(jù)實(shí)現(xiàn)很好的聚類效果，如圖9所示.此外，對于存在較好幾何形狀的數(shù)據(jù)，算法也有很好的聚類效果.如圖10和圖11所示，算法能對數(shù)據(jù)實(shí)現(xiàn)比較好的聚類.因此，本文提出的算法具有非常好的性能，能聚類任意形狀的簇，具有較好的魯棒性，通過調(diào)節(jié)參數(shù)可以對不平衡數(shù)據(jù)實(shí)現(xiàn)較好的聚類，對具有較好幾何形狀的數(shù)據(jù)也有非常好的效果.

3.2 真實(shí)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果分析

真實(shí)數(shù)據(jù)集更能檢驗(yàn)算法的性能.選用UCI數(shù)據(jù)集和Olivetti人臉數(shù)據(jù)庫來驗(yàn)證本文算法的性能.選用的數(shù)據(jù)集從樣本規(guī)模、特征個數(shù)和類簇?cái)?shù)目都有較大差別.

3.2.1UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果分析 采用ACC、AMI和ARI評價(jià)指標(biāo)來驗(yàn)證所提出算法的性能，并與其他算法進(jìn)行比較.實(shí)驗(yàn)結(jié)果如表3～表5所示.其中由于Waveform和Waveform(noise)本身數(shù)據(jù)量較大并且屬性較多，有些算法沒有得到聚類結(jié)果，在表中用符號“-”表示.每個數(shù)據(jù)集實(shí)驗(yàn)結(jié)果的最大值都進(jìn)行了加黑標(biāo)注.早期的K-means算法相對其他算法較穩(wěn)定，善于發(fā)現(xiàn)球狀簇.其他近期的代表性算法如DPC和AP，在個別數(shù)據(jù)集上的表現(xiàn)較差，但總體表現(xiàn)要優(yōu)于其他早期算法.通過對比可以發(fā)現(xiàn)，在ACC評價(jià)指標(biāo)下，本文提出的算法具有明顯優(yōu)勢.在AMI和ARI評價(jià)指標(biāo)下，本文提出的算法在更多的數(shù)據(jù)集上取得最大值.聚類結(jié)果表明，本文提出的算法具有非常好的性能，具有較強(qiáng)魯棒性，總體聚類性能優(yōu)于其他對比算法.

圖9 算法在不平衡數(shù)據(jù)集上的實(shí)驗(yàn)Fig.9 Experiment of the algorithm on the imbalanced data set

圖10 2C數(shù)據(jù)集聚類結(jié)果Fig.10 Clustering results of 2C data set

圖11 4B數(shù)據(jù)集聚類結(jié)果Fig.11 Clustering results of 4B data set

表3 真實(shí)數(shù)據(jù)集上的ACC評價(jià)指標(biāo)比較

表4 真實(shí)數(shù)據(jù)集上的AMI評價(jià)指標(biāo)比較

表5 真實(shí)數(shù)據(jù)集上的ARI評價(jià)指標(biāo)比較

3.2.2 Olivetti數(shù)據(jù)集實(shí)驗(yàn)結(jié)果分析 Olivetti人臉數(shù)據(jù)庫是機(jī)器學(xué)習(xí)領(lǐng)域廣泛使用的數(shù)據(jù)庫，包含40個人的人臉圖像，每個人的人臉圖像是10幅不同角度的圖像.由于人數(shù)(類簇?cái)?shù))比每個人的人臉圖像數(shù)(簇內(nèi)樣本數(shù))多，給聚類算法帶來很大挑戰(zhàn).

使用本文提出的算法對Olivetti數(shù)據(jù)集進(jìn)行聚類，圖12展示了本文算法的聚類結(jié)果.其中圖12(a)為人臉數(shù)據(jù)集原圖像，每行2個簇，共10行.圖12(b)為聚類識別結(jié)果，對其中聚類識別錯誤的人臉圖像加了橫向陰影，并在左上角留白部分標(biāo)注了“×”.ACC、 AMI 和 ARI的值分別可以達(dá)到0.818、0.830和0.728.比較優(yōu)秀的算法如DPC，只能發(fā)現(xiàn)20個密度峰值點(diǎn)，即最多能夠完全聚類識別20組人臉.本文提出的算法可以聚類識別35組人臉(一組中正確標(biāo)簽超過半數(shù)).對于未能識別的人臉，經(jīng)過對比發(fā)現(xiàn)，同一簇內(nèi)的圖像本身就存在較大差異，僅僅基于距離的度量很難準(zhǔn)確識別，可通過特征提取的方式進(jìn)一步提高準(zhǔn)確率.

圖12 Olivetti數(shù)據(jù)集聚類結(jié)果Fig.12 Clustering results of Olivetti data set

4 小結(jié)

基于互近鄰距離提出了互近鄰相對距離，為距離的計(jì)算提供了一種新的非度量距離計(jì)算方式.基于互近鄰相對距離，提出了一種新的最小生成樹聚類算法.針對某些數(shù)據(jù)的不平衡問題，提出了兼容不平衡數(shù)據(jù)的最小生成樹分割方法.算法設(shè)計(jì)簡單，易于實(shí)現(xiàn).經(jīng)典人工數(shù)據(jù)集、UCI真實(shí)數(shù)據(jù)集以及Olivetti數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明，算法能夠聚類任意形狀的簇和兼容處理不均衡數(shù)據(jù)，通過調(diào)節(jié)參數(shù)可以實(shí)現(xiàn)不同的聚類效果.如果數(shù)據(jù)本身有非常好的幾何形狀，算法能夠達(dá)到非常好的聚類效果.算法性能良好，具有較強(qiáng)魯棒性，總體聚類性能優(yōu)于其他對比算法.如何使本文提出的算法適用于大數(shù)據(jù)，是需要進(jìn)一步研究的問題.

[1] 孫吉貴, 劉杰, 趙連宇. 聚類算法研究[J]. 軟件學(xué)報(bào), 2008, 19(1):48-61.

[2] 劉志勇, 鄧貴仕. 一種基于矩陣變換的層次聚類算法[J]. 鄭州大學(xué)學(xué)報(bào)(理學(xué)版), 2010, 42(2):39-42.

[3] JAIN A K. Data clustering: 50 years beyond K-means[J]. Pattern recognition letters, 2010, 31(8):651-666.

[4] HAN J W, KAMBER M, PEI J. Data mining concepts and techniques [M]. 3rd ed. San Francisco: Morgan Kaufmann Publishers, 2012.

[5] LLOYD S P. Least squares quantization in PCM[J]. IEEE transactions on information theory, 1982, 28(2):129-137.

[6] KAUFMAN L, ROUSSEEUW P J. Finding groups in data: an introduction to cluster analysis[M].Hoboken: John Wiley，1990.

[7] KARYPIS G, HAN E H, KUMAR V. CHAMELEON: a hierarchical clustering algorithm using dynamic modeling[J]. Computer, 1999, 32(8):68-75.

[8] ZHANG T, RAMAKRISHNAN R, LIVNY M. BIRCH: an efficient data clustering method for very large databases[C]∥Proceedings of the ACM SIGMOD International Conference on Management of Data. Montreal, 1996:103-114.

[9] ESTER M, KRIEGEL H P，SANDER J，et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Oregon, 1996:22-69.

[10]ANKERST M, BREUNIG M M, KRIEGEL H P, et al. OPTICS: ordering points to identify the clustering structure[C]∥Proceedings of the ACM SIGMOD International Conference on Management of Data. Philadelphia, 1999:49-60.

[11]WANG W, YANG J, MUNTZ R R. STING: a statistical information grid approach to spatial data mining[C]∥Proceedings of the 23rd International Conference on Very Large Data Bases. San Francisco, 1997:186-195.

[12]RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496.

[13]XIE J, GAO H, XIE W, et al. Robust clustering by detecting density peaks and assigning points based on fuzzy weighted K-nearest neighbors[J]. Information sciences, 2016, 354:19-40.

[14]謝娟英, 高紅超, 謝維信. K近鄰優(yōu)化的密度峰值快速搜索聚類算法[J]. 中國科學(xué)(信息科學(xué)), 2016, 46(2):258-280.

[15]FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814):972-976.

[16]FAN J, NIU Z, LIANG Y, et al. Probability model selection and parameter evolutionary estimation for clustering imbalanced data without sampling[J]. Neurocomputing, 2016, 211:172-181.

[17]ZAHN C T. Graph-theoretical methods for detecting and describing gestalt clusters[J]. IEEE transactions on computers, 1971, 20(1):68-86.

[18]ZHONG C, MIAO D, WANG R. A graph-theoretical clustering method based on two rounds of minimum spanning trees[J]. Pattern recognition, 2010, 43(3):752-766.

[19]ZHONG C, MIAO D, FRNTI P. Minimum spanning tree based split-and-merge: a hierarchical clustering method[J]. Information sciences, 2011, 181(16):3397-3410.

[20]GOWDA K C, KRISHNA G. Agglomerative clustering using the concept of mutual nearest neighbourhood[J]. Pattern recognition, 1978, 10(2):105-112.

[21]GOWDA K C, DIDAY E. Symbolic clustering using a new similarity measure[J]. IEEE transactions on systems man & cybernetics, 1991, 22(2):368-378.

[22]PREPARATA F P, SHAMOS M I. Computational geometry [M]. Berlin: Springer-Verlag, 1985.

[23]HELD M, KARP R M. The traveling-salesman problem and minimum spanning trees [J]. Mathematical programming, 1971, 1(1):6-25.

[24]WILLETT P. Recent trends in hierarchic document clustering: a critical review[J]. Information processing & management, 1988, 24(5):577-597.

[25]EISEN M B, SPELLMAN P T, BROWN P O, et al. Cluster analysis and display of genome-wide expression patterns[J]. Proceedings of the national academy of sciences, 1998, 95(25):14863-14868.

(責(zé)任編輯：孔 薇)

A Minimum Spanning Tree Clustering Algorithm Based on Mutual Neighbor Relative Distance

CHENG Rufeng1, LIU Yizhi1, LIANG Yongquan1,2

(1.CollegeofComputerScienceandEngineering,ShandongUniversityofScienceandTechnology,Qingdao266590,China; 2.KeyLaboratoryofWisdomMineInformationTechnologyofShandongProvince,Qingdao266590,China)

For the lack of mutual neighbor distance, the concept of mutual neighbor relative distance was proposed. To the problem of imbalanced data, a minimum spanning tree clustering method was proposed. This algorithm was simple and easy to implement. The experimental results showed that the algorithm could cluster arbitrary shape data, and deal with imbalanced data. For the data with good geometry, the algorithm could achieve very good clustering effect, and the overall performance was better than other algorithms.

clustering; mutual neighbor relative distance; minimum spanning tree; imbalanced data

2017-03-30

山東省高等學(xué)?？萍加?jì)劃項(xiàng)目(J14LN33)；中國博士后科學(xué)基金項(xiàng)目(2014M561949)；山東科技大學(xué)研究生科技創(chuàng)新項(xiàng)目(SDKDYC170340).

程汝峰(1992—),男,山東德州人,主要從事數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)研究，E-mail: crfsearch@163.com;通信作者：梁永全(1968—),男,山東聊城人,教授,主要從事分布式人工智能、數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)研究,E-mail：lyq@sdust.edu.cn.

TP391

A

1671-6841(2017)03-0020-08

10.13705/j.issn.1671-6841.2017066