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

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

(1.山東科技大學 計算機科學與工程學院 山東 青島 266590； 2.山東省智慧礦山信息技術重點實驗室 山東 青島 266590)

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

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

(1.山東科技大學 計算機科學與工程學院 山東 青島 266590； 2.山東省智慧礦山信息技術重點實驗室 山東 青島 266590)

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

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

0 引言

聚類是數據挖掘領域的重要研究內容之一，在識別數據的內在結構方面具有極其重要的作用.文獻[1-4]對相關算法進行了研究.劃分方法中經典的有K-means算法[5]、K-medoids算法[6]等；層次方法中經典的有CHAMELEON算法[7]、BIRCH算法[8]等；基于密度的方法中經典的有DBSCAN算法[9]、OPTICS算法[10]等；基于網格的方法中經典的有STING算法[11]等.

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

1 算法的理論基礎

1.1 互近鄰相對距離

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

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

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

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

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

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

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

互近鄰相對距離的定義為

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

1.2 最小生成樹聚類

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

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

另外，數據本身也可能是不平衡的，因此需要引入平衡估計參數p，平衡估計參數根據先驗知識設定.加入參數p后，相應平衡度調整公式為

平衡度的計算如圖2所示，最小生成樹共包含10個樣本點，若設p=0.6，計算得到pe=1.

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

圖2 平衡度的計算Fig.2 Calculation of equilibrium degree

將邊界權重和平衡度的乘積作為分割參數，在最小生成樹分割的過程中，每次選擇分割參數最大的邊.經過多次分割，最終實現聚類.

2 算法描述

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

輸入：數據集D，平衡參數p，簇的個數k；

輸出：聚類結果.

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

2： 使用prim算法計算得到最小生成樹T；最小生成樹中邊的權重向量為VT.

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

4： 進行k-1輪迭代.

5：VPT=VT.*PT；%“.*”表示對應相乘.

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

7： 從VT中刪除邊e對應的權重；計算并更新PT.

8： 根據T的劃分，將數據集D劃分成k個簇.

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

3 實驗與結果

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

表1 人工數據集

表2 真實數據集

3.1 人工數據集實驗結果分析

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

圖3 Twenty數據集聚類結果Fig.3 Clustering results of Twenty data set

圖4 Hypercube數據集聚類結果Fig.4 Clustering results of Hypercube data set

圖5 Compound數據集聚類結果Fig.5 Clustering results of Compound data set

圖6 Impossible數據集聚類結果Fig.6 Clustering results of Impossible data set

圖7 D31數據集聚類結果Fig.7 Clustering results of D31 data set

圖8 Q58數據集聚類結果Fig.8 Clustering results of Q58 data set

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

3.2 真實數據集實驗結果分析

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

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

圖9 算法在不平衡數據集上的實驗Fig.9 Experiment of the algorithm on the imbalanced data set

圖10 2C數據集聚類結果Fig.10 Clustering results of 2C data set

圖11 4B數據集聚類結果Fig.11 Clustering results of 4B data set

表3 真實數據集上的ACC評價指標比較

表4 真實數據集上的AMI評價指標比較

表5 真實數據集上的ARI評價指標比較

3.2.2 Olivetti數據集實驗結果分析 Olivetti人臉數據庫是機器學習領域廣泛使用的數據庫，包含40個人的人臉圖像，每個人的人臉圖像是10幅不同角度的圖像.由于人數(類簇數)比每個人的人臉圖像數(簇內樣本數)多，給聚類算法帶來很大挑戰(zhàn).

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

圖12 Olivetti數據集聚類結果Fig.12 Clustering results of Olivetti data set

4 小結

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

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

[2] 劉志勇, 鄧貴仕. 一種基于矩陣變換的層次聚類算法[J]. 鄭州大學學報(理學版), 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]. 中國科學(信息科學), 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.

(責任編輯：孔 薇)

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

山東省高等學校科技計劃項目(J14LN33)；中國博士后科學基金項目(2014M561949)；山東科技大學研究生科技創(chuàng)新項目(SDKDYC170340).

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

TP391

A

1671-6841(2017)03-0020-08

10.13705/j.issn.1671-6841.2017066