王紅勤 潘正軍 袁麗娜

摘要：在深入分析傳統(tǒng)數(shù)據(jù)挖掘方案已經(jīng)不能滿足大數(shù)據(jù)的挖掘任務(wù)的基礎(chǔ)上，為了提高大數(shù)據(jù)環(huán)境下的數(shù)據(jù)挖掘速度，對(duì)分布式計(jì)算構(gòu)架 Hadoop 進(jìn)行分析與研究。文中搭建了Hadoop云計(jì)算平臺(tái)的數(shù)據(jù)挖掘系統(tǒng)，對(duì)數(shù)據(jù)挖掘算法中聚類(lèi)算法K-Means進(jìn)行了設(shè)計(jì)，在Hadoop平臺(tái)上實(shí)現(xiàn)了K-Means算法的優(yōu)化，使用Hadoop分布式系統(tǒng)進(jìn)行數(shù)據(jù)挖掘任務(wù)具有良好的效率，分析結(jié)果表明了其具有較大的潛力。

關(guān)鍵詞：數(shù)據(jù)挖掘算法;大數(shù)據(jù);Hadoop平臺(tái)

中圖分類(lèi)號(hào)：TP391? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）23-0009-03

開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

隨著移動(dòng)互聯(lián)網(wǎng)的發(fā)展，每日所產(chǎn)生地?cái)?shù)據(jù)量呈現(xiàn)指數(shù)級(jí)增長(zhǎng)，對(duì)于海量的非結(jié)構(gòu)的數(shù)據(jù)來(lái)說(shuō)，傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)已經(jīng)無(wú)能為力。如何從這些數(shù)據(jù)中獲取有用的信息，便成了關(guān)鍵問(wèn)題。開(kāi)源云計(jì)算平臺(tái)Hadoop的出現(xiàn)，適應(yīng)了這種海量數(shù)據(jù)挖掘的需求。

根據(jù)大數(shù)據(jù)環(huán)境的特點(diǎn)，為進(jìn)一步提升數(shù)據(jù)挖掘的效率，研究相應(yīng)的數(shù)據(jù)挖掘算法變得十分的迫切。本文選擇將數(shù)據(jù)挖掘的算法運(yùn)行在Hadoop分布式[1]云計(jì)算平臺(tái)上，對(duì)聚類(lèi)算法K-Means進(jìn)行研究，并且在該平臺(tái)上實(shí)現(xiàn)了K-Means算法[2]，由于較合適的初始K值難以確定，在Hadoop平臺(tái)上對(duì)該算法進(jìn)行改進(jìn)，改進(jìn)后的K-Means算法，計(jì)算速度快，可以高效地處理海量數(shù)據(jù)[3]。

1 相關(guān)技術(shù)介紹

1.1 Hadoop簡(jiǎn)介

Hadoop是一款穩(wěn)定的、可擴(kuò)展的、可用于分布式計(jì)算的開(kāi)源軟件。它是一個(gè)允許使用簡(jiǎn)單編程模型實(shí)現(xiàn)跨越計(jì)算機(jī)集群進(jìn)行分布式大型數(shù)據(jù)集處理的框架。Hadoop結(jié)構(gòu)如圖1所示，Hadoop核心模塊主要由HDFS、MapReduce兩大模塊組成，其中HDFS實(shí)現(xiàn)多臺(tái)機(jī)器上的數(shù)據(jù)存儲(chǔ)，MapReduce實(shí)現(xiàn)多臺(tái)機(jī)器上數(shù)據(jù)的計(jì)算[4]。

Hadoop 2時(shí)代中，HDFS（Hadoop Distributed File System，Hadoop分布式文件系統(tǒng)）與資源管理器YARN（Yet Another Resource Negotiator）結(jié)合，使得HDFS上存儲(chǔ)的內(nèi)容可以被更多的框架使用，提高資源利用率，YARN也為MapReduce大型數(shù)據(jù)集并行處理技術(shù)提供了便利。

MapReduce是一種分布式計(jì)算框架，它用于并行地處理大規(guī)模的數(shù)據(jù)集，它利用Map和Reduce函數(shù)來(lái)完成復(fù)雜的并行計(jì)算。MapReduce在處理數(shù)據(jù)時(shí)，首先從HDFS中取出數(shù)據(jù)塊，進(jìn)行分片，每個(gè)分片對(duì)應(yīng)一個(gè)Mapper任務(wù)，Mapper計(jì)算的結(jié)果通過(guò)Reducer進(jìn)行匯總，得出最終的結(jié)果進(jìn)行輸出。Hadoop的MapReduce工作過(guò)程如圖2所示。

1.2 數(shù)據(jù)挖掘

數(shù)據(jù)挖掘是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中提取有用的信息。通常數(shù)據(jù)挖掘需要有數(shù)據(jù)清理、數(shù)據(jù)變換、數(shù)據(jù)挖掘?qū)嵤┻^(guò)程、模式評(píng)估和知識(shí)表示等8個(gè)步驟。數(shù)據(jù)挖掘的過(guò)程需要反復(fù)執(zhí)行，從而達(dá)到提取有用數(shù)據(jù)的目的。

數(shù)據(jù)挖掘根據(jù)數(shù)據(jù)的類(lèi)型和數(shù)據(jù)的特點(diǎn)，選擇相應(yīng)的挖掘算法。常用的數(shù)據(jù)挖掘算法有K-Means，C4.5，SVM，Apriori， PageRank等等。

2 基于Hadoop平臺(tái)的K-Means挖掘算法

2.1 Hadoop數(shù)據(jù)挖掘平臺(tái)的搭建

數(shù)據(jù)挖掘接合Hadoop平臺(tái)，采用并行化計(jì)算的思維，構(gòu)建Hadoop集群的數(shù)據(jù)挖掘平臺(tái)，該平臺(tái)集成了數(shù)據(jù)的存儲(chǔ)、分析與處理過(guò)程。基于的Hadoop 集群的數(shù)據(jù)挖掘平臺(tái)如圖3所示。

該平臺(tái)引入的HDFS分布式存儲(chǔ)模式，主要對(duì)海量數(shù)據(jù)進(jìn)行挖掘。數(shù)據(jù)挖掘初期，對(duì)數(shù)據(jù)進(jìn)行查詢、分析，接下來(lái)對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，任務(wù)分配，在Hadoop大數(shù)據(jù)處理層，采用MapReduce、HDFS，使用相應(yīng)的數(shù)據(jù)挖掘算法（算法層主要包括K-Means、SVM等算法），進(jìn)行數(shù)據(jù)建模，從海量的數(shù)據(jù)中，挖掘出有用的數(shù)據(jù)。經(jīng)數(shù)據(jù)挖掘后，再進(jìn)行數(shù)據(jù)分析，可以發(fā)現(xiàn)重要的數(shù)據(jù)流，得出一些重要的結(jié)論，

2.2 聚類(lèi)算法K-Means

聚類(lèi)是將一組數(shù)據(jù)按照相似性歸成若干類(lèi)別，這樣的一組數(shù)據(jù)對(duì)象的集合叫作簇，對(duì)每一個(gè)這樣的簇都要進(jìn)行描述。它的目的是使得屬于同一類(lèi)別的數(shù)據(jù)之間的距離盡可能小而不同類(lèi)別上的個(gè)體間的距離盡可能的大。

K-means算法， 也被稱(chēng)為K-平均或K-均值算法，是一種得到最廣泛使用的聚類(lèi)算法。 它是將各個(gè)聚類(lèi)子集內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類(lèi)的代表點(diǎn)，算法的主要思想是通過(guò)迭代過(guò)程把數(shù)據(jù)集劃分為不同的類(lèi)別，使得評(píng)價(jià)聚類(lèi)性能的準(zhǔn)則函數(shù)達(dá)到最優(yōu)（平均誤差準(zhǔn)則函數(shù)E），從而使生成的每個(gè)聚類(lèi)（又稱(chēng)簇）內(nèi)緊湊，類(lèi)間獨(dú)立。

K-means聚類(lèi)算法使用平均誤差準(zhǔn)則函數(shù)來(lái)評(píng)價(jià)其聚類(lèi)性能，給定數(shù)據(jù)集X，其中只包含描述屬性，不包含類(lèi)別屬性。假設(shè)X包含k個(gè)聚類(lèi)子集X1，X2，…XK;各個(gè)聚類(lèi)子集中的樣本數(shù)量分別為n1，n2，…nk;各個(gè)聚類(lèi)子集的均值代表點(diǎn)（也稱(chēng)聚類(lèi)中心）分別為m1，m2，…mk。E代表所有對(duì)象的平方誤差總和，P代表數(shù)據(jù)對(duì)象，mi是數(shù)據(jù)集Xi的平均值。E值越小，說(shuō)明聚類(lèi)的結(jié)果質(zhì)量越高。誤差平方和準(zhǔn)則函數(shù)公式如（1）所示。

[E=i=1kp∈Xip-mi2]? ? ? ? ? ? ? ? ? ? ? ? （1）

3 改進(jìn)后K-Means算法的設(shè)計(jì)與實(shí)現(xiàn)

由于原K-Means算法存在一些問(wèn)題，如K值人工輸入、K個(gè)中心的初始位置難以確定、孤立點(diǎn)會(huì)使類(lèi)聚結(jié)果偏離中心等。我們將對(duì)K-Means算法進(jìn)行優(yōu)化，基于Hadoop，對(duì)其實(shí)現(xiàn)并行化優(yōu)化。

3.1 K-Means算法的設(shè)計(jì)與實(shí)現(xiàn)過(guò)程

在Hadoop集群環(huán)境中，使用K-Means算法，并行化處理該流程。K-Means算法的并行化處理的過(guò)程：將所有的數(shù)據(jù)，分布到不同的節(jié)點(diǎn)上，每個(gè)節(jié)點(diǎn)只對(duì)自己的數(shù)據(jù)進(jìn)行計(jì)算，每個(gè)節(jié)點(diǎn)能夠讀取上一次迭代生成的聚類(lèi)中心，并計(jì)算本節(jié)點(diǎn)里的數(shù)據(jù)應(yīng)該屬于哪一個(gè)聚類(lèi)中心，每一個(gè)節(jié)點(diǎn)迭代中根據(jù)自己的數(shù)據(jù)，產(chǎn)生新的聚類(lèi)中心。

K-Means算法的并行處理是一個(gè)不斷循環(huán)迭代的過(guò)程，分為三個(gè)階段：Map階段、Combine階段和Reduce階段。

Map階段：該過(guò)程主要讀取數(shù)據(jù)文件，且讀取上一次迭代結(jié)果中的聚類(lèi)中心值，編寫(xiě)map（）函數(shù)處理，并產(chǎn)生新的聚類(lèi)中心。在map（）函數(shù)，構(gòu)造全局變量centerString，centerString用于保存上一次迭代的聚類(lèi)中心值，讀取一個(gè)數(shù)據(jù)，函數(shù)就計(jì)算一次數(shù)據(jù)與原聚類(lèi)中心的距離，將其中的最小值賦值給centerpoint，計(jì)算出來(lái)的centerpoint是新的聚類(lèi)中心。

Map階段的主要部分代碼如下：

String str=value.toString（）;

String[] centerString=str.split（"| | | | "）;

double[] centerpoint=new double[m];

System.out.println（pointString.length）;

if （pointString.length==60） {

for （int i = 0; i < m; i++） {

centerpointt[i]=Double.parseDouble（str[i]）;

}

int minCent=-1;

double distance=0.0d;

double minDistance=Double.MAX_VALUE;

System.out.println（minDistance）;

Combine階段：在此階段，將Map階段處理后的聚類(lèi)進(jìn)行處理 ，求出所有聚類(lèi)中心的平均值，當(dāng)數(shù)據(jù)處理完成后，MapTask對(duì)所有的平均值進(jìn)行一次合并，生成整個(gè)簇的平均值，即為整個(gè)簇的均值。

Reduce階段：每個(gè)reduce收到某一個(gè)簇的信息，包括該簇 的id以及該簇的數(shù)據(jù)點(diǎn)的均值及對(duì)應(yīng)于該均值的數(shù)據(jù)點(diǎn)的個(gè)數(shù)pointNum，經(jīng)過(guò)Reduce后，輸出當(dāng)前的迭代計(jì)數(shù)、均值及屬于該質(zhì)心的數(shù)據(jù)點(diǎn)的個(gè)數(shù)。

Reduce階段主要部分代碼如下：

String strSting;

String[] pointString;

double[] center=new double[m];

for （int i = 0; i < m; i++） {

center[i]=0;

}

int pointNum=0;

for （Text vaule：values） {

line=values.toString（）;

pointString=line.split（"| | | | | |"）;

for （int i = 0; i < m; i++） {

center[i]=Double.parseDouble（pointString[i]）;

pointNum++;

}

for （int i = 0; i < m; i++） {

center[i]/=pointNum;

result=result+point[i];

}

result=result+Key.toString（）;

context.write（NullWritable.get，new Text（result））;

}

}

3.2 實(shí)驗(yàn)結(jié)果

為了測(cè)試改進(jìn)后的K-Means算法的性能，實(shí)驗(yàn)中分別設(shè)定10000、100000、1000000、2000000、3000000條記錄的數(shù)據(jù)來(lái)進(jìn)行測(cè)試，對(duì)每一組實(shí)驗(yàn)重復(fù)執(zhí)行30次，計(jì)算平均值作為最終的結(jié)果。為了實(shí)驗(yàn)結(jié)果的準(zhǔn)確性，實(shí)驗(yàn)采用由5臺(tái)機(jī)器構(gòu)成的集群環(huán)境和3臺(tái)機(jī)器構(gòu)成的集群環(huán)境進(jìn)行測(cè)試，測(cè)試的結(jié)果如表1所示。

實(shí)驗(yàn)結(jié)果表明，在Hadoop集群環(huán)境中，使用優(yōu)化后的K-Means算法，運(yùn)行的效率遠(yuǎn)遠(yuǎn)高于傳統(tǒng)的算法。數(shù)據(jù)規(guī)模越大，性能就越好。

為了驗(yàn)證數(shù)據(jù)的可伸縮性，實(shí)驗(yàn)將選擇5組不同數(shù)目的節(jié)點(diǎn)進(jìn)行實(shí)驗(yàn)，他們分別是1個(gè)、3個(gè)、5個(gè)、7個(gè)和9個(gè)。觀察實(shí)驗(yàn)結(jié)果，我們會(huì)發(fā)現(xiàn)，隨著節(jié)點(diǎn)數(shù)目地増加，完成算法的所用時(shí)間如圖4所示，實(shí)驗(yàn)測(cè)試結(jié)果中，橫坐標(biāo)表示節(jié)點(diǎn)數(shù)，縱坐標(biāo)表示完成時(shí)間且單位為103s。

從實(shí)驗(yàn)的運(yùn)行結(jié)果可以看出，隨著Hadop集群中節(jié)點(diǎn)數(shù)的不斷增多，每個(gè)任務(wù)所需要的時(shí)間在逐漸減少。通過(guò)實(shí)驗(yàn)，說(shuō)明優(yōu)化后的算法，能夠有效用于大數(shù)據(jù)的處理。

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

大數(shù)據(jù)時(shí)代已經(jīng)到來(lái)，為了提高大數(shù)據(jù)環(huán)境下的數(shù)據(jù)挖掘速度，本文設(shè)計(jì)了基于 Hadoop平臺(tái)的數(shù)據(jù)挖掘環(huán)境，研究了K-Means算法原理和執(zhí)行流程，并使用MapReduce編程思想，對(duì)K-Means算法進(jìn)行了優(yōu)化，并通過(guò)實(shí)驗(yàn)證明了，在云計(jì)算平臺(tái)的集群中，使用K-Means算法進(jìn)行數(shù)據(jù)挖掘的處理，具有較好的挖掘高效率和良好的擴(kuò)展性能。

參考文獻(xiàn)：

[1] 王宏志，李春靜.Hadoop集群程序設(shè)計(jì)與開(kāi)發(fā)[M].人民郵電出版社，2018：32.

[2] 韓雅雯.kmeans 聚類(lèi)算法的改進(jìn)及其在信息檢索系統(tǒng)中的應(yīng)用[D].云南大學(xué)，2016.

[3] 黃奇鵬，盧山.海量關(guān)系數(shù)據(jù)去重處理技術(shù)研究與優(yōu)化[J].計(jì)算機(jī)與數(shù)字工程，2018，10.

[4] 魯焱.大數(shù)據(jù)共享平臺(tái)的系統(tǒng)架構(gòu)與建設(shè)思路[J].圖書(shū)館理論與實(shí)踐，2017（04）：86-90.

[5] 徐浙君.云計(jì)算下的一種數(shù)據(jù)挖掘算法的研究[J].科技通報(bào)，2018（11） ：209.

[6] Issa J.Performance characterization and analysis for Hadoop K-Means iteration[J].Journal of Cloud Computing 2016，5 （1）：1-15.

【通聯(lián)編輯：代影】