基于MCL與Chameleon的混合聚類算法

楊連群，劉樹發(fā)，溫晉英，劉功申

（1.天津市濱海新區(qū)公安局 天津300450；2.天津市公安局 天津300020；3.上海交通大學(xué) 上海200240）

基于MCL與Chameleon的混合聚類算法

楊連群1，劉樹發(fā)2，溫晉英1，劉功申3

（1.天津市濱海新區(qū)公安局 天津300450；2.天津市公安局 天津300020；3.上海交通大學(xué) 上海200240）

馬爾科夫聚類算法（Markov Cluster Algorithm，MCL）是一種快速且可擴(kuò)展的無監(jiān)督圖聚類算法，Chameleon是一種新的層次聚類算法。但MCL由于過擬合會產(chǎn)生很多小聚類，Chameleon由于時間復(fù)雜度為O（N2）不利于處理大規(guī)模數(shù)據(jù)集。針對這兩個問題，提出了一種基于MCL與Chameleon相結(jié)合的混合聚類算法。該算法第一階段采用MCL算法對原始數(shù)據(jù)進(jìn)行初步聚類，第二階段利用GPU加速的Chameleon算法將第一階段產(chǎn)生的小聚類進(jìn)行歸并，從而得到質(zhì)量更高的聚類。實(shí)驗(yàn)表明，與傳統(tǒng)的MCL算法和MCL與KNN的混合聚類算法，提出的方法聚類質(zhì)量更好、計算速度更快。

MCL；Chameleon；聚類算法；圖分割算法

聚類分析是探測數(shù)據(jù)分析的關(guān)鍵步驟，在許多領(lǐng)域都得到了較為成功的應(yīng)用，如數(shù)據(jù)分析[1]、Web文檔分類[2]、異常檢測[3]等。圖聚類算法是聚類分析中研究較為廣泛的一個分支，目前已有很多關(guān)于圖聚類的算法被提出，比如譜聚類算法[4-5]，多層聚類算法（METIS）[6-7]等。但在實(shí)際運(yùn)用中仍然有很多不足之處，如：1）譜聚類算法由于需要計算相似矩陣的特征值和特征向量，導(dǎo)致計算時間太長；2）METIS將圖的權(quán)重進(jìn)行均等劃分，不適合長尾分布的數(shù)據(jù)；3）譜聚類算法和METIS都不具備智能識別圖類別數(shù)目的能力等。因此探討一種計算時間較快、分割質(zhì)量高且無需事先規(guī)定聚類數(shù)目的圖分割算法是很有必要的。

較之以上的圖聚類算法，MCL算法[8]具有以下優(yōu)勢：1）通過對轉(zhuǎn)移矩陣的反復(fù)修改來模擬隨機(jī)流，更易理解；2）不易被拓?fù)湓肼曀绊懀?）無需預(yù)先了解可能潛在的簇結(jié)構(gòu)。但MCL由于過擬合使得容易產(chǎn)生小聚類，從而影響聚類質(zhì)量。為解決這一問題，可將得到的小聚類再次進(jìn)行歸并，從而得到更高質(zhì)量的聚類結(jié)果。但現(xiàn)存的聚類算法大多只處理符合某靜態(tài)模型的簇，忽略了不同簇之間的信息。Chameleon算法[9]克服了這一限制，它是一種采用動態(tài)模型的圖層次聚類算法，在合并兩個簇時既考慮了相對互連度，又考慮了相對近似度，具有能高質(zhì)量地發(fā)現(xiàn)具有不同形狀、大小和密度的簇的能力。但Chameleon算法時間復(fù)雜度為O（N2）不適用于處理大規(guī)模數(shù)據(jù)集。

綜上，文中提出一種將MCL和Chameleon相結(jié)合的改進(jìn)圖聚類算法，達(dá)到了優(yōu)勢互補(bǔ)的效果。具體做法主要分為兩個階段，第一階段，使用MCL對原始數(shù)據(jù)集進(jìn)行初步聚類的劃分，得到互不相連的初始子簇；第二階段，利用GPU加速的Chameleon算法將初始子簇進(jìn)行歸并。實(shí)驗(yàn)表明，所提的方法是有效可行的。

1 MCL聚類算法介紹

一個圖通常表示為G=（V，E，W），其中V是節(jié)點(diǎn)的集合，E是邊的集合，W是邊權(quán)重。圖聚類問題就是把圖G劃分成k個互不相交的子圖G=（V，E，W），i=1，2，…，k。記A是圖G的鄰接矩陣，M為圖G的轉(zhuǎn)移概率矩陣，M（i，j）代表節(jié)點(diǎn)vi到節(jié)點(diǎn)vj的轉(zhuǎn)移概率，因此矩陣M每列之和為1。定義轉(zhuǎn)移概率矩陣M與鄰接矩陣A之間的關(guān)系如下：

MCL通過反復(fù)修改轉(zhuǎn)移概率矩陣來模擬圖中節(jié)點(diǎn)的轉(zhuǎn)移過程，該過程則是通過擴(kuò)展（Expansion）操作和膨脹（Inflation）操作來實(shí)現(xiàn)的。擴(kuò)展操作通過擴(kuò)展參數(shù)e來對轉(zhuǎn)移概率矩陣M進(jìn)行冪乘操作。當(dāng)擴(kuò)展參數(shù)為e時，該操作如下：

膨脹操作通過膨脹參數(shù)r對矩陣M中的每一列進(jìn)行冪乘操作，再對每一列進(jìn)行歸一化操作。當(dāng)膨脹參數(shù)為r時，該操作如下：

模擬隨機(jī)流的MCL算法[8]，具體實(shí)現(xiàn)步驟如下:

輸入：無向圖G（有權(quán)圖或無權(quán)圖均可），擴(kuò)展參數(shù)e以及膨脹參數(shù)r。

1）計算圖G的鄰接矩陣Α。

2）對每個節(jié)點(diǎn)添加自環(huán)，即Α:=Α+I，I為對角線元素為1的對角矩陣。

3）利用（1）式，計算轉(zhuǎn)移概率矩陣M。

4）利用（2）式，對M進(jìn)行擴(kuò)展操作。

5）利用（3）式，對M進(jìn)行膨脹操作。

6）重復(fù)步驟5），6），直至收斂。判斷與上次迭代的矩陣M是否有變化，若無變化，則收斂。

7）根據(jù)最后得到的矩陣M進(jìn)行劃分。如圖1所示，表示某一無向圖的穩(wěn)定的轉(zhuǎn)移概率矩陣，最后聚類結(jié)果應(yīng)為{1、6、7、10}，{2、3、5}，{4、8、9、11、12}。

圖1 矩陣M聚類結(jié)果

2 Chameleon算法介紹

Chameleon算法是一種自適應(yīng)的動態(tài)模型算法，實(shí)現(xiàn)過程如圖2所示，主要分為3個階段來實(shí)現(xiàn)。第一階段，構(gòu)造一個k-最近鄰居圖Gk。第二階段，將Gk劃分成有限個子圖，初步得到相對較小的子簇。第三階段，將第二階段的初始子簇合并形成最終高質(zhì)量的簇。以下著重介紹第三階段的合并準(zhǔn)則。

圖2 Chameleon算法的主要過程

2.1 相關(guān)定義

首先，定義兩兩簇之間的互連度和近似度，其具體描述如下。

定義1：（相對互連度）簇Ci與簇Cj之間的相對互連度為：

定義2：（相對近似度）簇Ci與簇Cj之間的相對近似度為：

其中，|Ci|表示簇i內(nèi)數(shù)據(jù)點(diǎn)的個數(shù)；EC（Ci）表示簇Ci內(nèi)所有邊的權(quán)重和；EC（Ci，Cj）表示連接兩個簇的所有邊的權(quán)重和。合并方法通過定義如下的相似度函數(shù)。

定義3：（相似度函數(shù)）相似度函數(shù)為相對互連度與相對近似度的乘積，即為：

其中，α為用戶給定的參數(shù)。

2.2 Chameleon算法

1）利用公式（4）和（5），計算兩兩簇之間的RC和RI，通過函數(shù)（6）計算相似度tempMetric。

2）找到最大的tempMetric，若最大的tempMetric超過某一相似度，將簇與此值對應(yīng)的簇合并。

3）若最大的tempMetric沒有超過閾值，則將該簇移除聚簇列表，加入到結(jié)果聚簇中。

4）重復(fù)步驟3），直到待合并簇類列表最終大小為空，得到K個簇。

3 MCL與Chameleon的混合聚類算法

MCL經(jīng)過一定步驟的膨脹和擴(kuò)展之后，會使得節(jié)點(diǎn)之間的關(guān)系出現(xiàn)偏差。由于偏差不斷地擴(kuò)大，導(dǎo)致處在同一個簇中的邊緣點(diǎn)容易被分離出來，從而形成單個的或只有兩3個節(jié)點(diǎn)的小聚類。為解決這一問題，將MCL產(chǎn)生的小聚類作為Chameleon算法的初始子簇，將每一個子簇看成是一個對象，并尋求一個最終聚類，使簇內(nèi)部連接緊密，而簇外部連接稀疏。另外，考慮到Chameleon算法的時間復(fù)雜度為O（N2），為適用海量數(shù)據(jù)處理，利用GPU的高并行執(zhí)行能力，將數(shù)據(jù)中個兩兩計算轉(zhuǎn)換為GPU線程塊中個線程執(zhí)行Chameleon算法計算。CPU時間復(fù)雜度為O（N2），而GPU只取決于耗時最長的線程時間，且GPU采用分而治之的思想，先單一GPU計算當(dāng)前模塊數(shù)據(jù)，最后匯總得到結(jié)果，再分配下一個計算數(shù)據(jù)。綜上所述，文中采用GPU加速提高了計算時間的同時還能有效地節(jié)省硬件成本，更高效地完成大規(guī)模的數(shù)據(jù)聚類分析。實(shí)現(xiàn)過程圖3所示。

綜合以上結(jié)論，文提出一種MCL與Chameleon的混合聚類算法描述如下。

第一階段：

輸入：圖G，轉(zhuǎn)移概率矩陣M（G），膨脹參數(shù)r

圖3 基于GPU加速的Chameleon算法主要實(shí)現(xiàn)過程

使用MCL算法

第二階段：輸入第一階段的簇類信息

使用基于GPU加速的Chameleon聚類算法

輸出：最后的聚類結(jié)果G={G1，G2，…，GK}

4 算法檢驗(yàn)

為檢驗(yàn)文中算法的有效性，采用Stanford大型網(wǎng)絡(luò)數(shù)據(jù)集[11]中的com_Amazon數(shù)據(jù)集進(jìn)行性能測試。Stanford大型網(wǎng)絡(luò)數(shù)據(jù)集是關(guān)于圖形的一個比較全面的數(shù)據(jù)集，且收集時間較新，因此選用該標(biāo)準(zhǔn)數(shù)據(jù)集，對算法的驗(yàn)證具有一定的說服力。com_Amazon數(shù)據(jù)集是由爬蟲Amazon網(wǎng)站獲得，表示用戶與商品之間的購買情況，如果兩位用戶買過相同的商品，則這兩位用戶是連接關(guān)系。文中實(shí)驗(yàn)硬件環(huán)境如下：Intel Core i7-4790K CPU@4.00 GHz；主存32 GB；系統(tǒng)平臺為Ubuntu14.04 LTS英文版操作系統(tǒng)；軟件實(shí)施平臺為Python 2.7.9（Anaconda 2.2.0）。

4.1 檢驗(yàn)標(biāo)準(zhǔn)

DB指標(biāo)[12-13]是常用的聚類性能度量內(nèi)部指標(biāo)，同時使用了簇間距離和簇內(nèi)離散度，DB的值越小，說明聚類效果越好，反之亦然。模塊度指標(biāo)[14-15]的物理意義為：圖中連接兩個同簇類的節(jié)點(diǎn)的邊的比例，減去在同樣的圖下任意連接這兩個節(jié)點(diǎn)的邊的比例的期望值。若模塊度指標(biāo)Q越接近1，聚類質(zhì)量越好。

4.2 實(shí)驗(yàn)分析

首先，利用MCL算法對com_Amazon數(shù)據(jù)集進(jìn)行初始劃分，其結(jié)果如圖4所示，可以看出，隨著膨脹參數(shù)r的增大，小簇的數(shù)量越多，大致呈線性增長，且在總的聚類數(shù)目中占了相當(dāng)大的比例。針對MCL算法所產(chǎn)生的小簇，為證明本文方法的有效性，將本文的方法與文獻(xiàn)[8]、[10]進(jìn)行比較，利用DB指標(biāo)和模塊度指標(biāo)Q值對聚類質(zhì)量進(jìn)行評判，其結(jié)果如圖5和圖6所示。從圖5可知，隨著聚類數(shù)目的增加，DB指標(biāo)亦逐漸增加，即聚類質(zhì)量均在下降，其中沒經(jīng)過改進(jìn)的MCL算法[8]DB指標(biāo)增加得最快，說明其聚類效果最差；文中算法DB指標(biāo)最小，這說明文中提出的改進(jìn)方法效果更好。從圖6可知，文中所提出的方法Q值下降速度最慢，這說明聚類質(zhì)量最好。從圖7可以看出，當(dāng)單一使用CPU計算時，時間呈現(xiàn)指數(shù)增長，而GPU時間消耗則較為緩慢，只是隨數(shù)據(jù)增長呈現(xiàn)梯度增加。在效率方面，單個節(jié)點(diǎn)的CPU和GPU計算效率兩者相當(dāng)，但是并行處理問題效率遠(yuǎn)遠(yuǎn)高于串行處理。算法計算過程中GPU效率比CPU整體效率高出一個數(shù)量級。

圖4 膨脹參數(shù)r值對聚類數(shù)目的影響

圖5 3種聚類算法在com_Amazon數(shù)據(jù)集的DB指標(biāo)對比

5 結(jié)束語

文中針對MCL算法由于過擬合會產(chǎn)生很多的小簇的不足，并考慮到Chameleon算法的聚類特征，提出一種MCL與Chameleon相結(jié)合的混合聚類算法。較之MCL算法和MCL與KNN的混合聚類算法，在產(chǎn)生小聚類時，所提出的算法能得到質(zhì)量更高的聚類結(jié)果，具有較好的實(shí)際應(yīng)用價值。

圖6 3種聚類算法在com_Amazon數(shù)據(jù)集Q值對比

圖7 GPU和CPU計算時間對比

[1]ZHANG Xin-yan，SUN Jian-guo.Regression analysis of clustered interval-censored failure time data with informative cluster size [J].Computational StatisticsandDataAnalysis，2010，54（7）：1817-1823.

[2]Manjot K，Navjot K.Web document clustering approaches using K-Means algorithm[J].International Journal of Advanced Research in Computer Science and Software Engineering，2013，3（5）: 861-864.

[3]LIU Bin，XU Guang，XU Qian.Outlier detection data mining oftax based on cluster[J].2012 International Conference on Medical Physics and Biomedical Engineering，2012（33）:1689-1694.

[4]Tseng，Shin-Pin.Normal spectral partition detection fitting for SAC FO-CDMA systems[J].Institute of Electrical and Electronics Engineers，2015,19（12）:2134-2137.

[5]Appalaneni K，Emily C，Anthony F.Single fiber identification with nondestructive excitation-emission spectral cluster analysis[J].Institute of Electr-icaland Electronics Engineers，2014，86（14）:5308-5315.

[6]Zheng L，Wu J，Chen Y，et al.Balanced k-Way partitioning for weighted graphs[J].Journal of Computer Research and Development，2015，52（3）:769-776.

[7]Xu J，Zhong Y，Peng B.Parallel k-Way Partitioning Approach for Large Graphs[J].Advanced Materials Research，2014，912:1309-1312.

[8]Dongen S V，Abreugoodger C.Using MCL to extract clusters from networks[J].Methods in Molecular Biology，2012，804（804）:281-95.

[9]蔣盛益，龐松觀，張黎莎.Chameleon算法的改進(jìn)[J].小型微型計算機(jī)系統(tǒng)，2010，31（8）:1643-1646.

[10]牛秦洲，陳艷.基于MCL與KNN的混合聚類算法[J].桂林理工大學(xué)學(xué)報，2015，35（1）:181-186.

[11]Jure L，Andrej K.Large network dataset collection [DB/OL].（2014-06）http://snap.stanford.edu/data.

[12]周志華.機(jī)器學(xué)習(xí)[M]，北京：清華大學(xué)出版社. 2015.

[13]Coelho G P，Barbante C C，Boccato L，et al. Automatic feature selection for BCI:An analysis using the davies-bouldin index and extreme[C]// Intemation Joint Conference on Nevral Networks，Brisbane：2012（20）:1-8.

[14]黃健斌，鐘翔，孫鶴立，等.基于相似性模塊度最大約束標(biāo)記傳播的網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法[J].北京大學(xué)學(xué)報:自然科學(xué)版，2013，49（3）:389-396.

[15]封海岳，薛安榮.基于重疊模塊度的社區(qū)離群點(diǎn)檢測[J].計算機(jī)應(yīng)用與軟件，2013，30（5）:7-10.

A hybrid clustering algorithm based on MCL and Chameleon

YANG Lian-qun1，LIU Shu-fa2，WEN Jin-ying1，LIU Gong-shen3
（1.Binhai New Area Public，Tianjin 300450，China；2.Tianjin Public Security Bureau，Tianjin 300020，China；3.Shanghai Jiaotong University，Shanghai 200240，China）

The Markov Cluster Algorithm （MCL）is a fast and scalable unsupervised clustering algorithm for graphs.Chameleon is a new hierarchical clustering algorithm.With the over-fitting of MCL computational process，MCL is prone to producing small clusters.Chameleon clustering algorithm is not suitable for large scale data sets because of the time complexity of O （N2）.In order to solve these two problems，a hybrid clusteringalgorithm based on MCL combined with Chameleon algorithm is proposed. In the first stage，MCL clustering algorithm is used for grouping the data （we call it original partition）. In the second stage，we merge small clusters with the Chameleon clustering algorithm based on GPU acceleration so that the final clusters with higher quality are obtained.Experimental results show that algorithm proposed in this paper has more preferable clustering quality and operation speed than the classical MCL algorithm and hybrid clustering algorithm based on MCL and Chameleon.

MCL；Chameleon；clustering algorithm；graph partitioning algorithm

TN0

：A

：1674－6236（2017）06-0023-04

2016-05-25稿件編號：201605235

國家自然科學(xué)基金（61472248）

楊連群（1978—），男，天津人，碩士，高級工程師。研究方向：計算機(jī)算法，網(wǎng)絡(luò)安全等。