王紅勤 潘正軍 袁麗娜

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

關鍵詞：數(shù)據(jù)挖掘算法;大數(shù)據(jù);Hadoop平臺

中圖分類號：TP391? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2019）23-0009-03

開放科學（資源服務）標識碼（OSID）：

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

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

1 相關技術介紹

1.1 Hadoop簡介

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

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

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

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

數(shù)據(jù)挖掘是從大量的、不完全的、有噪聲的、模糊的、隨機的數(shù)據(jù)中提取有用的信息。通常數(shù)據(jù)挖掘需要有數(shù)據(jù)清理、數(shù)據(jù)變換、數(shù)據(jù)挖掘實施過程、模式評估和知識表示等8個步驟。數(shù)據(jù)挖掘的過程需要反復執(zhí)行，從而達到提取有用數(shù)據(jù)的目的。

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

2 基于Hadoop平臺的K-Means挖掘算法

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

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

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

2.2 聚類算法K-Means

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

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

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

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

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

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

3.1 K-Means算法的設計與實現(xiàn)過程

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

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

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

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階段處理后的聚類進行處理 ，求出所有聚類中心的平均值，當數(shù)據(jù)處理完成后，MapTask對所有的平均值進行一次合并，生成整個簇的平均值，即為整個簇的均值。

Reduce階段：每個reduce收到某一個簇的信息，包括該簇 的id以及該簇的數(shù)據(jù)點的均值及對應于該均值的數(shù)據(jù)點的個數(shù)pointNum，經(jīng)過Reduce后，輸出當前的迭代計數(shù)、均值及屬于該質心的數(shù)據(jù)點的個數(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 實驗結果

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

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

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

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

4 結束語

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

參考文獻：

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

[2] 韓雅雯.kmeans 聚類算法的改進及其在信息檢索系統(tǒng)中的應用[D].云南大學，2016.

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

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

[5] 徐浙君.云計算下的一種數(shù)據(jù)挖掘算法的研究[J].科技通報，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)編輯：代影】