一種改進的基于大數據集的混合聚類算法*

張 曉，王 紅

(1.山東師范大學信息科學與工程學院，山東 濟南 250014;2.山東省分布式計算機軟件重點實驗室，山東 濟南 250014)

一種改進的基于大數據集的混合聚類算法*

張 曉，王 紅

(1.山東師范大學信息科學與工程學院，山東 濟南 250014;2.山東省分布式計算機軟件重點實驗室，山東 濟南 250014)

針對k-means算法過度依賴初始聚類中心、收斂速度慢等局限性及其在處理海量數據時存在的內存不足問題，提出一種新的針對大數據集的混合聚類算法super-k-means，將改進的基于超網絡的高維數據聚類算法與k-means相結合，并經過MapReduce并行化后部署在Hadoop集群上運行。實驗表明，該算法不僅在收斂性以及聚類精度兩方面得到優化，其加速比和擴展性也有了大幅度的改善。

k-means；超網絡；頻繁項集；超圖劃分；MapReduce

1 引言

大數據聚類是當前聚類研究的重點。在海量數據的聚類中，現有的聚類算法在時間復雜性和空間復雜性上都存在一定的局限，解決這個問題的一種途徑就是引用并行處理技術，設計出高效的并行聚類算法，來提高算法性能。目前，MapReduce是最主流且實用的并行化模型。

k-means算法是傳統的經典聚類算法，但是該算法對初始值具有很強的依賴性[1]，即算法的魯棒性不高。此外，k-means算法在串行計算方法中的時間復雜度比較高，處理能力難以滿足需求。目前，對與k-means算法相結合的混合聚類算法及其并行化方面已經取得了較為理想的研究成果。賴玉霞等人[2]提出的一種優化的基于密度的算法有效地解決了k-means算法過度依賴初始值的問題。田森平等人[3]提出了自動獲取最佳k值的算法。畢曉君等人[4]提出一種結合人工蜂群和k-均值的混合聚類算法，使得聚類效果有了明顯改善。Fagin R等人[5]提出了一種結合遺傳算法和k-means的混合聚類方法，該方法能有效地解決k-means過于依賴初始值的瓶頸問題，但是串行依然會增加算法運行的時間復雜度。Ngazimbi M等人[6]利用Apache Hadoop MapReduce框架實現了k-means、Greedy Agglomerative和Expectation Maximization聚類算法。

針對k-means聚類算法應用在大數據集上的不足，本文提出一種新的針對大數據集的混合聚類算法super-k-means，首先，將高維數據映射到一個大規模帶權超網絡中；其次，定義超網絡中邊的權重；再次，采用優化的超圖劃分方法劃分帶權超網絡；最后，將得到的k個劃分作為k-means算法的k個初始聚類中心，通過MapReduce并行化后部署在Hadoop集群上運行。這樣既能有效地過濾掉聚類中的噪聲數據，又克服了傳統k-means算法穩定性差的缺點。實驗表明，本文提出的算法super-k-means行之有效。

2 相關工作

2.1 k-means算法的基本原理

k-means算法是1967年由MacQueen首次提出的一種經典算法， K-means算法的處理流程[7]如下：

(1)在所有的n個數據點中隨機選取k個點作為初始簇中心；

(2)將k個選擇點之外的每個數據點，根據它們與k個初始簇中心的相似度(歐氏距離)，分別分配到與其最相似的(歐氏距離最小)簇；

(3)重新計算得出新聚類的中心對象(均值)；

(4)迭代該過程至聚類質量檢測函數收斂。

k-means聚類算法的偽代碼如下所示：

算法k-means

輸入：數據集D，劃分簇的個數k;

輸出：k個簇的集合。

(1)Initially choosekpoints that are likely to be in different clusters;

(2)Make these points the centroids of their clusters;

(3)FOR each remaining pointpDO

(4) find the centroid to whichpis closest;

(5) Addpto the cluster of that centroid;

(6) Adjust the centroid of that cluster to account forp;

(7)END;

k-means算法通常使用誤差平方和SSE(Sum of Squared Error)[7]來檢測聚類質量。其形式化的定義如下所示：

(1)

其中，d()表示兩個對象之間的距離(通常采用歐氏距離)。k值相同時，SSE越小說明簇內對象越集中，對于不同的k值，k值越大對應的SSE值越小。

2.2 基于超網絡的數據聚類算法流程

對于大規模的高維數據,由于維度災難的影響,若采用傳統的基于降維的算法進行聚類,會出現的一個共同問題是損失一部分有用的信息，而這會影響聚類結果。利用超網絡方法進行高維數據聚類，能有效過濾掉聚類中的噪聲數據，保證數據聚類的質量。超網絡的拓撲結構即超圖。

一個超圖[8]：

H=(V，E)

(2)

由一個頂點集(V)和一個邊集(E)構成。權重超圖就是帶權圖的擴充，超邊可以連接多于兩個以上的頂點。在這類圖模型中，頂點集V表示將要聚類的數據類的集，而每個超邊e∈E連著相關類的集。

聚類實現步驟如下:

步驟1使用經典的 Apriori 算法挖掘出所有頻繁的超邊，即找出所有支持度大于設定的最小閾值的超邊。對每條超邊，找到其頻繁項集中包含的支持度和置信度分別滿足最小閾值的關聯規則，從而計算每條超邊的權重。這里將采用支持度與置信度的乘積作為權重。

步驟2通常采用的超圖分割算法是hMETIS。其基本思想:將建立的超圖模型通過粗化、初始劃分、遷移優化三個階段尋找權重最小的邊并將它切割，不斷反復直到得到k個有效劃分。hMETIS能在幾分鐘內在包含超過100 000個點的大規模線路中找到非常好的劃分。特別對k方式劃分來說，hMETIS的復雜性是O((|V|+|E|)lgk)，其中|V|是頂點數，|E|是邊數。

步驟3由上個步驟得到k個簇，然后通過評價函數來確定符合要求的聚類結果。

Figure 1 Basic flowchart of the algorithm

2.3 改進的兩階段混合聚類算法

本文提出的這種聚類算法super-k-means，先通過第一階段的超圖聚類得到k個簇，作為第二階段k-means聚類算法的k個初始中心進行聚類，通過兩階段的混合聚類既克服了k-means算法過度依賴初始聚類中心、穩定性差的缺點，又汲取了超圖模型適用于大規模的高維數據聚類的優點。同時，基于Hadoop平臺的并行化處理也大大縮短了程序的運行時間。該算法的主要流程如圖2所示。

Figure 2 Flowchart of the super-k-means algorithm

3 super-k-means算法的MapReduce并行化實現

由上述super-k-means的實現流程可見串行實現算法的時間復雜度比較高，與O(super-k-means)、N(數據記錄總個數)、N(期望得到的聚類的個數)、N(算法迭代次數)、T(計算待分配的數據到中心點距離)等變量之間存在線性關系。如果要將M個數據對象聚成N個簇，那么在一次迭代中就需要完成MN次記錄到中心點的距離的計算操作，雖然這類計算操作最耗時，但也最容易并行處理：各個記錄與k個聚類中心的距離進行比較的操作可以同時進行。

從k-means算法流程中可以看出，主要的計算工作是將每個數據對象分配到跟其相似度最高(距離最近)的簇，并且該操作是相互獨立的，所以在每次MapReduce job中，這一步驟super-k-means算法可以通過分別執行相同的Map和Reduce操作得到并行處理。

3.1 MapReduce模型

MapReduce編程模型[9]的基本思路：Hadoop MapReduce是當前最主流的分布式計算框架，基于該框架的應用程序能夠運行在由數臺普通計算機組成的大型集群上，并能容錯地并行處理大規模數據。MapReduce框架運行在〈key,value〉上，Map是把原始輸入數據分解成一組中間的〈key,value〉對，Reduce把結果合成最終輸出。

這樣一項包含若干項任務(Task)的工作在MapReduce中被稱為作業(Job)。任務又包含若干map任務和若干reduce任務,先由map任務并行地處理這些〈key,value〉鍵值對，然后MapReduce框架會將map的輸出結果進行一系列復制、分組、排序等處理之后輸出給reduce任務。

Map函數和Reduce函數[10]是由程序員提供的， map和reduce任務分布在集群節點上運行，并把結果存儲在分布式文件系統上。整個MapReduce對任務進行調度和監控，以及重新執行失敗的任務。MapReduce框架是由一個主JobTracker和分布在每個集群節點的一個個從屬的TaskTracker組成。如圖3所示。

Figure 3 MapReduce job schematic

3.2 Map函數和Reduce函數的設計

Map函數：計算各個數據對象到中心點的距離并對該數據屬于的新類別重新標記。將所有數據對象和上一輪Job的聚類中心作為Map函數的輸入，輸入數據鍵值對形式為〈row number,record number〉；按照讀入的簇中心記錄文件，Map函數計算出到每個輸入數據記錄距離最近的簇中心，并作出新的標記；輸出中間結果鍵值對的形式為〈cluster category ID,records attribute vector〉。

Reduce函數：通過Map函數得到的結果計算出新的聚類中心，供下一輪Job使用。輸入數據鍵值對的形式為〈cluster category ID,{record attribute vector set}〉所有key相同的記錄送給同一個Reduce，累加key相同的點個數和各記錄分量并求出各分量的均值，并生成新的簇中心記錄；輸出結果鍵值對的形式為〈cluster category ID,mean vector〉。

Job結束之后，計算該輪新的聚類中心偏離誤差并進行判斷。如果小于給定的閾值則算法結束；反之，用新的簇中心記錄文件覆蓋上一輪的文件，并啟動新Job。

super-k-means算法在MapReduce框架下的運行流程及算法偽代碼如下所示。

Figure 4 Super-k-means parallel implementation based on MapReduce

算法偽代碼如下：

Job：計算新的聚類中心

Map階段：

輸入：〈Object，一條數據〉

輸出：〈所屬類Ci，數據〉

public voidmap(Objectkey,Textvalue,

OutputCollector〈IntWritable,Text〉output,Reporterreporter) {

Stringline=value.toString().trim();

intsort=0;//聚類類別

doubleminDis=Double.MAX_VALUE;

for (inti=1;i<=k;i++) {

doubletmpDis=calDis(i,line);/*數據和類i間的距離*/

if (tmpDis

sort=i;

minDis=tmpDis;

}

}

output.collect(new IntWritable(sort),value);

}

Reduce階段：

輸入：〈Ci，相應數據的集合〉

輸出：〈Ci,新的聚類中心〉

public voidreduce(IntWritablekey,Iterator〈Text〉values,OutputCollector〈IntWritable,Text〉output,Reporterreporter) {

introws=0,i=0;//rows表示數據條數

doublerecords[]=new double[COLS];/*COLS為全局變量，表示屬性的個數*/

while (values.hasNext()) {

rows++;

Stringtmp=values.next().toString();

StringTokenizeritr=newStringTokenizer(tmp);

i=0;

while (itr.hasMoreTokens()&&i

records[i++] += Double.parseDouble(itr.nextToken());

}

}

Stringline="";

for (i=0;i

line+=records[i]/rows+ " ";

}

output.collect(key,newText(line));

迭代Job，直至連續兩次聚類中心偏離距離小于給定的閾值。

4 實驗

實驗環境：本文采用由九臺普通PC機搭建的Hadoop集群進行實驗，測試super-k-means并行聚類算法，其中一臺作為master,其他8臺作為slaves。軟件配置如下： JDK 1.6.0.29；Hadoop 0.20.2，master節點上部署Hadoop的NameNode和JobTracker，slaves節點上部署TaskTracker和DataNode。每臺節點的硬件配置如下：CPU為雙核2.4 GHz；物理內存為4 GB；硬盤為2 TB。實驗數據集主要是人工數據以及聯合聚類算法的標準測試數據集(http://www.datatang.com/data/44245)。數據維度為6。每組實驗均采用平均執行多次取平均值的方法作為實驗結果。

4.1 單機處理對比實驗

4.1.1 聚類精確度對比

實驗內容：在處理相同數據的條件下，super-k-means 聚類算法與k-means聚類算法各自完成聚類結果的精確度對比。從實驗數據中構造數據記錄數依次為500、2 000、5 000的數據集Data1、Data2、Data3。分別采用三種算法進行聚類，用6次的平均值作為最終實驗結果。如表1所示。

Table 1 Accuracy comparison of different clustering algorithms表1 聚類精確度對比

由表1可以看出，在處理小的數據集時，k-means算法所得到的結果也不太理想，而在用改進后的super-k-means(超網絡聚類與k-means相結合)算法后聚類效果明顯得到了改善。采用并行super-k-means后，隨著處理的數據集規模的不斷增大，所得到的聚類結果和串行的算法相比較也進一步有了明顯的改善。這主要是因為超網絡聚類算法在較大規模數據聚類方面具有一定的優勢，并且通過超網絡聚類算法幫助k-means確定了初始聚類中心，從而收斂到了較好的結果。

4.1.2 單機處理對比實驗

實驗內容：在相同配置環境下處理相同規模數據時，比較集群中的一個節點與單機super-k-means算法完成聚類所需要的時間。本實驗中Java虛擬機JVM(Java Virtual Machine)的內存設置為1 GB。實驗結果如表2所示。

Table 2 Single processing experimental results表2 單機處理實驗結果

其中，r1為單機上使用super-k-means聚類算法所用的時間；r2為集群中一個節點完成super-k-means聚類算法所用時間。實驗中，隨著數據量的急劇增大，super-k-means算法的時間復雜度會急劇增大并會產生內存溢出。實驗表明，當數據規模很小時，單機運行的super-k-means 聚類算法的運算能力要大大高于Hadoop集群中單節點，這是因為與實際的計算時間相比較而言，MapReduce 每次啟動 map 和 reduce 占據的時間比例較大。但是，當單機super-k-means聚類算法因為內存不足而停止計算時，Hadoop單節點仍能正常完成聚類運算，由此初步可見， super-k-means聚類算法在經 MapReduce并行化之后在處理大數據方面有了一定的優勢。

4.2 小型集群加速比實驗

實驗1加速比(Speedup)。

(3)

其中，Sn是加速比。

從實驗數據中構建大小依次為60 GB、40 GB、20 GB的DataA、DataB、DataC三個用于并行算法的大規模數據集。

將集群中所有節點按需要逐漸參與計算，并觀察每個節點的加速比。實驗中，集群中每個節點上運行時的最大map數和最大reduce 數可以根據數據規模大小調節，可以更大限度地調用 Hadoop集群的能力。實驗結果如圖5 所示。從圖5中可以看出，隨著節點數的增加，每個Job運行的時間降低，對相同規模數據來說，隨著節點數的增加，系統的處理能力有了顯著的提高，這說明集群在處理super-k-means算法時具有良好的加速比?？舍槍Ω鞣N指標對不同聚類算法進行對比驗證分析。

Figure 5 Super-k-means acceleration ratio experiment based on MapReduce

實驗2分別進行三組實驗測試super-k-means聚類算法的擴展性：第一組，數據集大小為2 GB、4 GB、8 GB、16 GB對應1、2、4、8個節點；第二組，數據集大小為4 GB、8 GB、16 GB、32 GB對應1、2、4、8個節點；第三組，數據集大小為8 GB、16 GB、32 GB、64 GB對應1、2、4、8個節點。實驗結果如圖6所示。從圖6中可以看出，當節點數和數據規模同比例增長時，算法的整體擴展性是逐漸降低的，主要是因為隨著節點數的增加，系統節點間的通訊開銷增大，從而導致算法的整體運行速度變慢。但是，隨著數據規模的逐漸增大，算法的擴展性越來越好，是由于數據規模越大越能充分調動集群中每個節點的處理能力，此時節點間的通訊開銷減少的比例也越來越高。因此，第三組中算法的擴展性大于第一組和第二組，更適合處理大規模數據集。

Figure 6 Super-k-means scalability experiment based on MapReduce

5 結束語

將兩種不同的聚類算法相結合可以互相取長補短，從而提高聚類效果，但同時又會產生算法時間復雜度高的問題。Super-k-means算法在Hadoop平臺下的并行化設計和實現，不僅提高了算法運行的時間效率而且也改善了算法運行的結果。

對于如何改進基于超網絡的聚類算法從而提高超網絡模型的劃分精確度，以及對k-means算法中如何確定最佳的k值從而避免陷入局部最優，加快收斂速度，這些都是有待于以后進行研究的問題。

[1] Li Qun,Yuan Jin-sheng. Optimal density text clustering algorithm based on DBSCAN [J]. Computer Engineering and Design,2012,33(4):1409-1413.(in Chinese)

[2] Lai Yu-xia,Liu Jian-ping. Optimal study on initial center ofk-means algorithm [J]. Computer Engineering and Applications,2008,44(10):147-149. (in Chinese)

[3] Tian Sen-ping,Wu Wen-liang. Algorithm of automatic gained parameter valuekbased on dynamick-means [J]. Computer Engineering and Design,2011,32(1):274-276.(in Chinese)

[4] Bi Xiao-jun，Gong Ru-jiang.Hybrid clustering algorithm based

on artificial bee colony andk-means algorithm [J]. Application Research of Computers, 2012，29(6):2040-2045.(in Chinese)

[5] Fagin R，Kolaitis P G，Pops L． Data exchange:Getting to the core[J]． ACM TODS，2005，30(1):147-210．

[6] Ngazimbi M.Data clustering using MapReduce[D]. Idaho：BosieState University，2009.

[7] Sun Ji-gui,Liu Jie. Clustering algorithms research[J]. Journal of Software,2008，22(19)：48-61.(in Chinese)

[8] Wang Zhi-ping,Wang Zhong-tuo. Super network theory and its application[M]. Beijing:Science Press,2008.(in Chinese)

[9] Verma A，Llorae X，Goldberg D E．Scaling genetic algorithms using MapReduce[C]∥Proc of International Conference on Intelligent Systems Design and Applications,2009:1.

[10] Jin C，Vecchiola C，Buyya R．Mrpga：An extension of MapReduce for parallelizing genetic algorithms[C]∥Proc of IEEE the 4th International Conference on Science，2008：214-221.

附中文參考文獻

[1] 李群，袁金生. 基于DBSCAN的最優密度文本聚類算法[J]. 計算機工程與設計，2012，33(4):1409-1413.

[2] 賴玉霞，劉建平.k-means算法的初始聚類中心的優化[J]．計算機工程與應用，2008，44(10)：147-149．

[3] 田森平，吳文亮．自動獲取k-means聚類參數k值的方法[J]. 計算機工程與設計，2011,32(1):274-276.

[4] 畢曉君，宮汝江. 一種結合人工蜂群和k-均值的混合聚類算法[J]. 計算機應用研究，2012，29(6)：2040-2045.

[7] 孫吉貴,劉杰. 聚類算法研究[J]. 軟件學報，2008，22(19)：48-61.

[8] 王志平,王眾托. 超網絡理論及其應用[M]. 北京：科學出版社,2008.

張曉(1988-),女,山東萊蕪人，碩士生，CCF會員(E200037819G),研究方向為復雜網絡和大數據。E-mail:970790885@qq.com

ZHANG Xiao,born in 1988,MS candidate,CCF member(E200037819G),her research interests include complex network, and big data.

王紅(1966-),女,天津人，博士，教授，研究方向為復雜網絡和大數據。E-mail:1456029328@qq.com

WANG Hong,born in 1966,PhD,professor,her research interests include complex network, and big data.

An improved hybrid clustering algorithm based on large data sets

ZHANG Xiao,WANG Hong

(1.School of Information Science and Engineering,Shandong Normal University,Jinan 250014;2.Key Laboratory of Distributed Computer Software in Shandong Province,Jinan 250014,China)

Aiming at the following three problems of thek-means algorithm:excessive dependence on the initial clustering center, slow convergence speed and insufficient memory when dealing with huge amounts of data, we present a new hybrid clustering algorithm called super-k-means for large data sets. The algorithm combines thek-means algorithm with the improved high-dimensional data clustering algorithm based on the super-network. We run it on the Hadoop clusters after the MapReduce parallel processing, and an ideal effect of clustering is achieved. Experimental results show that the algorithm not only improves the convergence and the clustering accuracy but also has high speedup and scalability performance.

k-means;super network;frequent itemsets；hypergraph partitioning;MapReduce

1007-130X(2015)09-1621-06

2014-09-28;

2014-12-16基金項目：國家自然科學基金資助項目(61373149,61472233)；山東省科技計劃項目(2012GGX10118，2014GGX101026)

TP391

A

10.3969/j.issn.1007-130X.2015.09.003

通信地址：250014 山東省濟南市歷下區文化東路88號山東師范大學信息科學與工程學院

Address:School of Information Science and Engineering,Shandong Normal University,Jinan 250014,Shandong,P.R.China