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

宋旭東，朱文輝，邱占芝

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

?

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

宋旭東，朱文輝，邱占芝

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

基于數(shù)據(jù)規(guī)模導(dǎo)致難以應(yīng)對(duì)的存儲(chǔ)量、數(shù)據(jù)規(guī)模導(dǎo)致傳統(tǒng)算法失效、大數(shù)據(jù)復(fù)雜的數(shù)據(jù)關(guān)聯(lián)性導(dǎo)致高復(fù)雜度的計(jì)算等問題,對(duì)大數(shù)據(jù)下的k-means聚類優(yōu)化算法進(jìn)行研究，給出了適用于大數(shù)據(jù)任務(wù)處理的MapReduce軟件架構(gòu)的模型機(jī)制，通過改進(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 引言

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

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

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

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

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

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

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

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

MapReduce運(yùn)行機(jī)制如圖1所示.

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

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

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

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

其算法流程如圖2所示.

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

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

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

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

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

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

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

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

處理：

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

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

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

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

3 算法實(shí)驗(yàn)

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

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

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

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

4 結(jié)論

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

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

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

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

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

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

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

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

國(guó)家自然科學(xué)基金資助項(xiàng)目( 61074029)；大連市科技計(jì)劃資助項(xiàng)目(2014A11GX006)

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

A