宋旭東，朱文輝，邱占芝

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

?

大數(shù)據(jù)k-Means聚類挖掘優(yōu)化算法

宋旭東，朱文輝，邱占芝

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

基于數(shù)據(jù)規(guī)模導(dǎo)致難以應(yīng)對的存儲量、數(shù)據(jù)規(guī)模導(dǎo)致傳統(tǒng)算法失效、大數(shù)據(jù)復(fù)雜的數(shù)據(jù)關(guān)聯(lián)性導(dǎo)致高復(fù)雜度的計算等問題,對大數(shù)據(jù)下的k-means聚類優(yōu)化算法進(jìn)行研究，給出了適用于大數(shù)據(jù)任務(wù)處理的MapReduce軟件架構(gòu)的模型機制，通過改進(jìn)k-means初始聚類中心的選取，提出了一種基于MapReduce模型的k-means聚類優(yōu)化算法.最后將改進(jìn)的算法應(yīng)用于煤炭煤質(zhì)的分析中，結(jié)果顯示較傳統(tǒng)算法，改進(jìn)算法的效率有明顯提高.

大數(shù)據(jù)；數(shù)據(jù)挖掘；k-means算法；MapReduce模型

0 引言

云計算、物聯(lián)網(wǎng)、社交網(wǎng)絡(luò)等新興服務(wù)促使人類社會的數(shù)據(jù)種類和規(guī)模正以前所未有的速度增長，大數(shù)據(jù)時代已到來.大數(shù)據(jù)量可顯著提高機器學(xué)習(xí)算法的準(zhǔn)確性；訓(xùn)練數(shù)據(jù)集越大,數(shù)據(jù)分類精度越高；大數(shù)據(jù)集上的簡單算法能比小數(shù)據(jù)集上的復(fù)雜算法產(chǎn)生更好的結(jié)果，因此數(shù)據(jù)量足夠大時有可能使用代價很小的簡單算法來達(dá)到很好的學(xué)習(xí)精度.

然而，基于大數(shù)據(jù)的數(shù)據(jù)挖掘的研究面臨新的挑戰(zhàn)，主要表現(xiàn)在：數(shù)據(jù)規(guī)模導(dǎo)致難以應(yīng)對的存儲量；數(shù)據(jù)規(guī)模導(dǎo)致傳統(tǒng)算法失效；大數(shù)據(jù)復(fù)雜的數(shù)據(jù)關(guān)聯(lián)性導(dǎo)致高復(fù)雜度的計算.

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

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

1 大數(shù)據(jù)MapReduce軟件架構(gòu)模型機制

Google提出的軟件架構(gòu)MapReduce是一種用于大規(guī)模數(shù)據(jù)集的并行運算編程模型，在處理T級別以上巨量數(shù)據(jù)的業(yè)務(wù)上有著明顯優(yōu)勢[6].

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

MapReduce運行機制的核心是Map和Reduce函數(shù).Map函數(shù)功能是按照一定的規(guī)則將輸入的鍵值生成一批新的中間鍵值對.Reduce函數(shù)功能是將中間結(jié)果鍵值對按照目標(biāo)要求進(jìn)行計算并產(chǎn)生最終的結(jié)果.

MapReduce運行機制如圖1所示.

圖1 MapReduce軟件架構(gòu)模型機制

2 基于MapReduce軟件架構(gòu)的聚類挖掘優(yōu)化算法

2.1 算法框架結(jié)構(gòu)

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

其算法流程如圖2所示.

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

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

2.2 k-means算法初始聚類中心的優(yōu)化

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

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

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

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

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

處理：

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

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

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

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

3 算法實驗

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

應(yīng)用中選取18038個煤炭數(shù)據(jù)樣本點，采用k-means傳統(tǒng)算法和優(yōu)化算法進(jìn)行試驗，設(shè)置生成4個聚類.傳統(tǒng)算法的聚類結(jié)果由于對初始聚類中心的依賴性導(dǎo)致聚類結(jié)果不穩(wěn)定，不同的的試驗其產(chǎn)生的聚類結(jié)果也在不斷變化，而經(jīng)過優(yōu)化算法結(jié)果始終保持不變.本文選取了兩個傳統(tǒng)算法的聚類結(jié)果，及其優(yōu)化算法的聚類結(jié)果如圖3所示.

從結(jié)果可以看出優(yōu)化算法與傳統(tǒng)算法相比有更高的準(zhǔn)確性和穩(wěn)定性.

圖3 傳統(tǒng)算法及優(yōu)化算法聚類結(jié)果

4 結(jié)論

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

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

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

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

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

[5]周煒奔,石躍祥.基于密度的K-means聚類中心選取的優(yōu)化算法[J].計算機應(yīng)用研究,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]劉鵬.實戰(zhàn)Hadoop—開啟通向云計算的捷徑[M].北京：電子工業(yè)出版社，2011：60-74.

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

[10]周愛武，崔丹丹，潘勇.一種優(yōu)化初始聚類中心的k-means聚類算法[J].微機型與應(yīng)用，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

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

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

A