大數據k-Means聚類挖掘優化算法

宋旭東，朱文輝，邱占芝

(大連交通大學 軟件學院，遼寧 大連 116028)

?

大數據k-Means聚類挖掘優化算法

宋旭東，朱文輝，邱占芝

(大連交通大學 軟件學院，遼寧 大連 116028)

基于數據規模導致難以應對的存儲量、數據規模導致傳統算法失效、大數據復雜的數據關聯性導致高復雜度的計算等問題,對大數據下的k-means聚類優化算法進行研究，給出了適用于大數據任務處理的MapReduce軟件架構的模型機制，通過改進k-means初始聚類中心的選取，提出了一種基于MapReduce模型的k-means聚類優化算法.最后將改進的算法應用于煤炭煤質的分析中，結果顯示較傳統算法，改進算法的效率有明顯提高.

大數據；數據挖掘；k-means算法；MapReduce模型

0 引言

云計算、物聯網、社交網絡等新興服務促使人類社會的數據種類和規模正以前所未有的速度增長，大數據時代已到來.大數據量可顯著提高機器學習算法的準確性；訓練數據集越大,數據分類精度越高；大數據集上的簡單算法能比小數據集上的復雜算法產生更好的結果，因此數據量足夠大時有可能使用代價很小的簡單算法來達到很好的學習精度.

然而，基于大數據的數據挖掘的研究面臨新的挑戰，主要表現在：數據規模導致難以應對的存儲量；數據規模導致傳統算法失效；大數據復雜的數據關聯性導致高復雜度的計算.

本文主要研究大數據下的聚類優化算法，主要是根據實體的特征對其進行聚類，按一定的距離或相似測度在大型多維空間數據集中標識出聚類或稠密分布的區域，將數據分成一系列相互區分的組，以期從中發現數據集的整個空間分布規律和典型模式.k-means聚類算法是數據挖掘技術中基于分裂法的一個經典的聚類算法，因為該算法的理論可靠、算法簡單、收斂迅速而被廣泛應用[1].

選擇合理的一組初始聚類中心，可以得到較高的聚類準確率.文獻[2]利用貪心算法參照數據樣本的分布特征將數據劃分為k個集合，選取各集合中數據的平均值作為初始聚類中心.文獻[3]提出了一種基于關聯圖劃分的k-means算法.該算法能夠有效地根據數據的分布特性選取初始聚類中心.文獻[4]結合密度法和最大化最小距離的思想，首先選取相互間距離最大的k對高密度點，并以這k對高密度點的均值作為聚類的初始中心，然后再進行k-Means聚類.文獻[5]針對數據對象的分布密度以及計算最近兩點的垂直中點方法來確定k個初始聚類中心 ,以獲得最優聚類.然而這些傳統的聚類挖掘優化算法在面對海量大數據時算法的時間復雜度都比較高.本文研究大數據下的k-means聚類算法，在進行改進初始聚類中心選取的基礎上，提出了一種基于MapReduce模型的k-means聚類優化算法.

1 大數據MapReduce軟件架構模型機制

Google提出的軟件架構MapReduce是一種用于大規模數據集的并行運算編程模型，在處理T級別以上巨量數據的業務上有著明顯優勢[6].

MapReduce運行機制的基本思路是將數據集分解為成百上千的小數據集split，若干個數據集交由集群的一個節點并行執行Map計算并產生中間結果，之后這些中間結果又交由大量的節點執行Reduce計算產生最終結果.

MapReduce運行機制的核心是Map和Reduce函數.Map函數功能是按照一定的規則將輸入的鍵值生成一批新的中間鍵值對.Reduce函數功能是將中間結果鍵值對按照目標要求進行計算并產生最終的結果.

MapReduce運行機制如圖1所示.

圖1 MapReduce軟件架構模型機制

2 基于MapReduce軟件架構的聚類挖掘優化算法

2.1 算法框架結構

用MapReduce處理的數據集應具備這樣的特點：它可以被分解為許多小的數據集，且每一個小的數據集可以完全并行的進行處理[7-8].基于Hadoop的k-means算法的處理過程主要有兩部分，第一部分是初始聚類中心，并把數據集樣本分為一定大小的數據塊，以便并行處理.第二部分及時啟動Map和Reduce任務進行算法的并行化處理，直至產生聚類結果.

其算法流程如圖2所示.

圖2 基于MapReduce的并行化k-means算法流程

除去對初始聚類中心選取的優化，假設每個節點處理p個任務，共有h個節點，那么優化后的算法時間復雜度為n*k*l*t/(p*h).從理論上基于MapReduce的k-means算法時間效率提高了很多.

2.2 k-means算法初始聚類中心的優化

傳統的算法初始聚類中心的選取是隨機的，這就造成聚類結果的不穩定性[9].本文采取一種初始聚類中心選取的方法，提高結果的穩定性.優化的k-means聚類算法首先根據一定的算法規則選擇k個樣本作為初始化聚類中心點，然后將k個聚類中心存放在HDFS上的一個文件中，作為全局變量[10].

設聚類樣本數據集：D={di|di∈R,i=1,2,3,…,n},k個聚類中心用c1,c2,c3,…,ck表示.具體有如下定義：

初始聚類中心算法描述如下：

輸入：終止條件ε以及聚類個數k,樣本數據的數據集D，存儲兩兩樣本點間距離dist(di,dj)的矩陣D1，集合A及聚類中心集合C.

輸出：滿足終止條件，得出k個初始聚類中心.

處理：

(1)計算數據集D中兩兩樣本點之間的距離dist(di,dj)并存入矩陣D1中.

(2)初始化集合A及聚類中心集合C，最小距離樣本點放入集合A中，并將其中心O1作為第一個初始的聚類中心存入C中.

(3)求出矩陣D1次小距離的樣本點中心，然后求出此中心與O1的距離，與averg比較；如果小于averg，則將此樣本點加入A中，再求第三距離小的樣本點，重復步驟(3)；如果大于averg，則將此中心存入C.

(4)直到集合C中個數為k.

3 算法實驗

將基于MapReduce的k-means算法應用于某大型煤炭企業.我們將一臺機器作為NameNode和JobTracter節點，其他五臺機器作為DataNode和TaskTracker節點.每臺節點硬件配置如下：CPU型號為英特爾Corei5M480 @ 2.67GHz雙核、內存為1G.硬盤容量為250G，7 200r/m，構建了基于MapReduce的k-means優化算法應用平臺，實現對煤炭特征數據的聚類分析.

應用中選取18038個煤炭數據樣本點，采用k-means傳統算法和優化算法進行試驗，設置生成4個聚類.傳統算法的聚類結果由于對初始聚類中心的依賴性導致聚類結果不穩定，不同的的試驗其產生的聚類結果也在不斷變化，而經過優化算法結果始終保持不變.本文選取了兩個傳統算法的聚類結果，及其優化算法的聚類結果如圖3所示.

從結果可以看出優化算法與傳統算法相比有更高的準確性和穩定性.

圖3 傳統算法及優化算法聚類結果

4 結論

針對大數據k-means聚類數據挖掘問題，本文給出了基于MapReduce軟件架構模型機制，完成了k-means聚類算法的初始聚類中心的選取優化，實現了基于MapReduce模型機制的k-means聚類優化算法.實驗表明，優化改進后的算法與傳統算法相比擁有較好的有效性和更高的計算效率，并且數據量越大優勢就越明顯.本文實驗表明在處理大數據時，應用MapReduce軟件架構平臺對實現包含k-means算法在內的數據挖掘算法具有現實意義.

[1]蘇錦旗,薛惠鋒,詹海亮.基于劃分的K-均值初始聚類中心優化算法[J].微電子學與計算機，2009(1):14-17.

[2]仝雪姣,孟凡榮,王志曉.對k-means初始聚類中心的優化[J].計算機工程與設計，2011(8):165-167.

[3]李正兵，羅斌，翟素蘭，等. 基于關聯圖劃分的 Kmeans 算法[EB/OL]. 計算機工程與應，2012. http://www.cnki.net/kcms/detail/11.2127.TP.20120615.1726.025.html.

[4]鄧海，覃華，孫欣. 一種優化初始中心的K-Means聚類算法[EB/OL].計算機技術與發展，2013. http://www.cnki.net/kcms/detail/61.1450.TP.20130724.0945.012.html.

[5]周煒奔,石躍祥.基于密度的K-means聚類中心選取的優化算法[J].計算機應用研究,2012(5):132-134.

[6]LAMMEL R. Google′s MapReduce Programming Model-Revisited[J]. Science of Computer Programming,2008,70(1):1-30.

[7]SATISH NARAYANA SRIRAMA, PELLE JAKOVITS, EERO VAINIKKO.Adapting scientific computing problems to clouds using MapReduce[J].Future generations computer systems,2012,28(1):184-192.

[8]劉鵬.實戰Hadoop—開啟通向云計算的捷徑[M].北京：電子工業出版社，2011：60-74.

[9]JIAWEI HAN，MICHELINE KAMBER. 數據挖掘概念與技術[M].北京：機械工業出版社，2007：2-3.

[10]周愛武，崔丹丹，潘勇.一種優化初始聚類中心的k-means聚類算法[J].微機型與應用，2011(13):1-3.

Big Data K-Means Clustering Mining Optimization Algorithm

SONG Xudong, ZHU Wenhui, QIU Zhangzhi

(Software Institute,Dalian Jiaotong University,Dalian 116028,China)

For the difficulty of storage capacity dealing with big data,failure of traditional algorithms for big scale data and high complexity computation,k-means clustering mining optimization algorithm is studied based on big data,and a MapReduce software architecture is proposed.It is suitable for large data processing mechanism, provides an improved method for selecting initial clustering centers and puts forward a k-means algorithm optimization based on MapReduce model.The improved algorithm is applied to coal quality analysis,and the result shows that compared with traditional algorithms,the optimization algorithm improves the efficiency obviously,and the accuracy is also enhanced.

big data;data mining;k-means algorithm;MapReduce model

1673-9590(2015)03-0091-04

2014-01-22

國家自然科學基金資助項目( 61074029)；大連市科技計劃資助項目(2014A11GX006)

宋旭東(1969-)，男，教授，博士，從事大數據分析、數據挖掘與決策支持的研究E-mail:xudongsong@126.com.

A