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

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

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

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

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

1 MCL聚類算法介紹

一個(gè)圖通常表示為G=（V，E，W），其中V是節(jié)點(diǎn)的集合，E是邊的集合，W是邊權(quán)重。圖聚類問(wèn)題就是把圖G劃分成k個(gè)互不相交的子圖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通過(guò)反復(fù)修改轉(zhuǎn)移概率矩陣來(lái)模擬圖中節(jié)點(diǎn)的轉(zhuǎn)移過(guò)程，該過(guò)程則是通過(guò)擴(kuò)展（Expansion）操作和膨脹（Inflation）操作來(lái)實(shí)現(xiàn)的。擴(kuò)展操作通過(guò)擴(kuò)展參數(shù)e來(lái)對(duì)轉(zhuǎn)移概率矩陣M進(jìn)行冪乘操作。當(dāng)擴(kuò)展參數(shù)為e時(shí)，該操作如下：

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

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

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

1）計(jì)算圖G的鄰接矩陣Α。

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

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

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

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

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

7）根據(jù)最后得到的矩陣M進(jìn)行劃分。如圖1所示，表示某一無(wú)向圖的穩(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)的動(dòng)態(tài)模型算法，實(shí)現(xiàn)過(guò)程如圖2所示，主要分為3個(gè)階段來(lái)實(shí)現(xiàn)。第一階段，構(gòu)造一個(gè)k-最近鄰居圖Gk。第二階段，將Gk劃分成有限個(gè)子圖，初步得到相對(duì)較小的子簇。第三階段，將第二階段的初始子簇合并形成最終高質(zhì)量的簇。以下著重介紹第三階段的合并準(zhǔn)則。

圖2 Chameleon算法的主要過(guò)程

2.1 相關(guān)定義

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

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

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

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

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

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

2.2 Chameleon算法

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

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

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

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

3 MCL與Chameleon的混合聚類算法

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

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

第一階段：

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

圖7 GPU和CPU計(jì)算時(shí)間對(duì)比

[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ì)算機(jī)系統(tǒng)，2010，31（8）:1643-1646.

[10]牛秦洲，陳艷.基于MCL與KNN的混合聚類算法[J].桂林理工大學(xué)學(xué)報(bào)，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é)報(bào):自然科學(xué)版，2013，49（3）:389-396.

[15]封海岳，薛安榮.基于重疊模塊度的社區(qū)離群點(diǎn)檢測(cè)[J].計(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稿件編號(hào)：201605235

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

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