基于Hadoop的數(shù)據(jù)聚類算法研究

徐正巧　趙德偉

摘要：聚類算法一直備受研究者青睞。隨著信息技術(shù)和數(shù)據(jù)技術(shù)的發(fā)展，數(shù)據(jù)的種類和數(shù)量急劇增長，云計(jì)算平臺Hadoop成為這些數(shù)據(jù)存儲和處理的新平臺，基于云計(jì)算平臺Hadoop的聚類算法逐漸成為熱門。針對數(shù)據(jù)挖掘中的聚類問題，依托云計(jì)算模式及Hadoop平臺，研究了Kmeans算法，有效改變了現(xiàn)有算法的局限性。

關(guān)鍵詞關(guān)鍵詞：云計(jì)算；Hadoop；聚類分析；MapReduce

DOIDOI：10.11907/rjdk.143858

中圖分類號：TP301.6

文獻(xiàn)標(biāo)識碼：A文章編號文章編號：16727800（2015）002000402

基金項(xiàng)目基金項(xiàng)目：四川省教育廳科研項(xiàng)目（12ZB144）；西華師范大學(xué)?；痦?xiàng)目（12A038）

作者簡介作者簡介：徐正巧（1982-），女，寧夏鹽池人，碩士，西華師范大學(xué)實(shí)驗(yàn)中心講師，研究方向?yàn)閿?shù)據(jù)挖掘與智能計(jì)算。

0引言

隨著信息技術(shù)和電子商務(wù)的飛速發(fā)展，數(shù)據(jù)正以驚人的速度劇增，無論是數(shù)據(jù)量還是數(shù)據(jù)種類都越來越豐富。這些海量的數(shù)據(jù)中隱藏著大量有價值的信息，如何存儲、處理這些海量數(shù)據(jù)，從這些海量數(shù)據(jù)中挖掘出有用信息，利用已有數(shù)據(jù)進(jìn)行預(yù)測是目前的研究熱點(diǎn)。

海量數(shù)據(jù)分布在不同的計(jì)算機(jī)中，分布式計(jì)算和大規(guī)模異構(gòu)系統(tǒng)資源共享是實(shí)現(xiàn)海量數(shù)據(jù)挖掘的關(guān)鍵技術(shù)，云計(jì)算技術(shù)為這一問題提供了理想的技術(shù)解決方案，云計(jì)算平臺滿足了用戶“按需使用，按量付費(fèi)，即需即用”的服務(wù)需求，有效解決了計(jì)算機(jī)中海量數(shù)據(jù)的存儲與處理問題。

1云計(jì)算

1.1云計(jì)算概念

云計(jì)算（Cloud Computing）是將存儲于電腦、移動電話和智能通訊設(shè)備上的大量信息和處理器資源集中在一起進(jìn)行工作的超級計(jì)算機(jī)模式。它將要完成的任務(wù)分布在大量計(jì)算機(jī)構(gòu)成的資源池上，各種應(yīng)用系統(tǒng)能夠根據(jù)需要從資源池中獲取計(jì)算力、存儲空間和各種軟件服務(wù)＼[1＼]。

云計(jì)算是集群計(jì)算（Cluster Computing）、分布式處理 （Distributed Computing）、并行計(jì)算（Parallel Computing）和網(wǎng)格計(jì)算（Grid Computing）的發(fā)展＼[2＼]。云計(jì)算采用計(jì)算機(jī)集群構(gòu)成數(shù)據(jù)中心和資源池，使用戶能夠利用互聯(lián)網(wǎng)隨時隨地、按實(shí)際需要共享云資源。

1.2云計(jì)算特點(diǎn)

云計(jì)算以其超大規(guī)模、高可擴(kuò)展性、高可靠性、虛擬化、按需分配、廉價性和通用性等優(yōu)勢，使普通用戶在普通計(jì)算機(jī)上都能享受到高性能計(jì)算機(jī)的存儲、計(jì)算能力，給人類生活和工作帶來了極大便利。目前Google、IBM、Microsoft等大型互聯(lián)網(wǎng)企業(yè)都部署有云計(jì)算平臺，供用戶分享云技術(shù)帶來的好處。

1.3云計(jì)算平臺

云計(jì)算系統(tǒng)主要由云平臺、云終端、云存儲和云安全4部分組成，其中云平臺是云計(jì)算系統(tǒng)的核心，它整合了多個數(shù)據(jù)中心的資源，統(tǒng)一分配和調(diào)度計(jì)算機(jī)資源、存儲資源和網(wǎng)絡(luò)資源，為用戶提供了良好的計(jì)算環(huán)境、開發(fā)平臺和應(yīng)用軟件等多種服務(wù)＼[3＼]。

云計(jì)算平臺可以劃分為存儲型云平臺、計(jì)算型云平臺以及綜合云計(jì)算平臺。其中，存儲型云平臺主要以數(shù)據(jù)存儲為主，計(jì)算型云平臺主要進(jìn)行數(shù)據(jù)處理，綜合云計(jì)算平臺則兼顧計(jì)算和數(shù)據(jù)存儲。

Hadoop是一個易開發(fā)及并行處理海量數(shù)據(jù)的云計(jì)算平臺，主要由兩部分組成：分布式文件系統(tǒng)HDFS（Hadoop Distributed File System）和MapReduce計(jì)算模型＼[45＼]，HDFS為海量數(shù)據(jù)提供存儲，是分布式計(jì)算的基石，采用了M/S架構(gòu)，主要執(zhí)行的操作有創(chuàng)建、刪除、移動或重命名等，架構(gòu)類似于傳統(tǒng)的分級文件系統(tǒng)；而MapReduce則為海量數(shù)據(jù)提供計(jì)算。

2數(shù)據(jù)聚類分析

聚類分析（Clastering Analysis）以對象的相似性為基礎(chǔ)，在聚類模式之間具有更多的相似性，是數(shù)據(jù)挖掘的重要技術(shù)之一。聚類是將物理或抽象對象的集合分成由類似的對象組成多個類的過程，是現(xiàn)實(shí)世界中普遍存在的現(xiàn)象，作為統(tǒng)計(jì)學(xué)的一個分支，其應(yīng)用非常廣泛。

在數(shù)據(jù)挖掘之前，對象類劃分的數(shù)據(jù)量與類型均是未知的，因此在數(shù)據(jù)挖掘后一般需要對數(shù)據(jù)挖掘結(jié)果進(jìn)行合理的分析與解釋。聚類算法可分為劃分法、層次法、基于網(wǎng)格方法、基于密度方法、圖論聚類法等。數(shù)據(jù)聚類分析主要有4個步驟，如圖1所示。

圖1聚類分析步驟

3基于Hadoop的數(shù)據(jù)聚類算法

數(shù)據(jù)挖掘的特點(diǎn)就是從海量數(shù)據(jù)中提取有價值的規(guī)則和信息。隨著數(shù)據(jù)量和種類的急劇增加，傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)已經(jīng)很難滿足數(shù)據(jù)挖掘的需求。在云計(jì)算時代，海量的數(shù)據(jù)分布在不同地理位置的計(jì)算機(jī)上，現(xiàn)有聚類算法在時間復(fù)雜性和空間復(fù)雜性上都無法很好地解決此問題。研究思路就是將并行處理技術(shù)應(yīng)用到現(xiàn)有的聚類算法中，降低聚類算法的時間復(fù)雜度和空間復(fù)雜度，節(jié)約聚類時間。

并行聚類算法能夠在多臺計(jì)算機(jī)上同時運(yùn)行，滿足云計(jì)算需求，節(jié)約了大量計(jì)算機(jī)資源。目前，并行聚類算法有：并行聚類算法PWIDE、并行KMeans算法、基于密度和密度可達(dá)并行聚類算法PCADD等＼[6＼]。

KMeans算法是最著名和最常用的聚類算法。Kmeans算法以k為輸入?yún)?shù)，把n個對象分為k個簇，使得簇內(nèi)具有較高的相似度，簇間具有較低的相似度。相似度的計(jì)算根據(jù)一個簇中對象的平均值（被稱為簇的重心或簇心）進(jìn)行。本文聚類算法采用均方差作為標(biāo)準(zhǔn)測度函數(shù)：

E=∑ki=1∑Pcip-mi2（1）

其中，E為所有數(shù)據(jù)對象的均方差之和；P代表對象空間中的一個點(diǎn)；mi為聚類均值。

并行Kmeans算法采用數(shù)據(jù)并行的設(shè)計(jì)思想，首先把整個空間數(shù)據(jù)按照計(jì)算機(jī)的節(jié)點(diǎn)數(shù)量對海量的數(shù)據(jù)集X進(jìn)行劃分，形成N個子數(shù)據(jù)樣本集X1，X2，X3……XN（N為計(jì)算機(jī)節(jié)點(diǎn)個數(shù)），每個節(jié)點(diǎn)上分別對應(yīng)自己的數(shù)據(jù)集，然后對每個子數(shù)據(jù)集進(jìn)行獨(dú)立的數(shù)據(jù)聚類，形成數(shù)據(jù)集的簇{C11，C12，……，C1M}，{C21，C22，……，C2O}，……，{Cn1，Cn2，……，CnQ}（其中M，O，Q為聚類簇的個數(shù)，N為數(shù)據(jù)集的個數(shù)），最后把聚類結(jié)果發(fā)送到主節(jié)點(diǎn)上，主節(jié)點(diǎn)再把各個聚類結(jié)果匯總，輸出最終的聚類結(jié)果。

Hadoop平臺主要有HDFS和MapReduce兩部分，并行Kmeans聚類算法，在每次迭代過程中分別執(zhí)行Map和Reduce操作。

在Hadoop平臺中，HDFS負(fù)責(zé)存儲海量數(shù)據(jù)，并管理數(shù)據(jù)文件，記錄數(shù)據(jù)文件分布在哪個節(jié)點(diǎn)上，從哪個數(shù)據(jù)節(jié)點(diǎn)上獲得，并記錄數(shù)據(jù)的初始中心。 Map函數(shù)的任務(wù)是完成每個記錄員到中心點(diǎn)距離的計(jì)算并重新標(biāo)記其新的類別，其輸入為待聚類所有數(shù)據(jù)和上一輪聚類中心，輸入數(shù)據(jù)聚類<行，記錄>。Reduce函數(shù)的任務(wù)是根據(jù)Map函數(shù)得到的中間計(jì)算結(jié)果，計(jì)算出新類的聚類中心并發(fā)送給各節(jié)點(diǎn)，更新HDFS到文件然后進(jìn)行下一次迭代直到收斂。

并行Kmeans聚類算法步驟如下：①任意選擇K個樣本作為初始的中心點(diǎn)；②迭代并執(zhí)行Map和Reduce操作；③直到收斂。

4結(jié)語

利用云計(jì)算技術(shù)和Hadoop平臺，獲得強(qiáng)大的計(jì)算能力、存儲能力以及基礎(chǔ)設(shè)施服務(wù)能力，有效解決了分析與處理海量數(shù)據(jù)面臨的問題，降低了終端設(shè)備要求，提高了數(shù)據(jù)處理能力。本文基于云計(jì)算平臺Hadoop，對海量數(shù)據(jù)聚類的并行算法Kmeans進(jìn)行了深入的研究和探討，以期對聚類發(fā)展起到推動作用。

參考文獻(xiàn)參考文獻(xiàn)：

＼[1＼]黃成云，左明章，榮先海. 基于云計(jì)算的移動學(xué)習(xí)系統(tǒng)設(shè)計(jì)＼[J＼]. 現(xiàn)代教育技術(shù)，2010，20 （8）：102105.

＼[2＼]侯建， 帥仁俊， 侯文. 基于云計(jì)算的海量數(shù)據(jù)存儲模型＼[J＼].通信技術(shù)，2011，44（5）：163165.

＼[3＼]吳功，吳英.物聯(lián)網(wǎng)導(dǎo)論＼[M＼].北京：機(jī)械工業(yè)出版社，2012.

＼[4＼]趙衛(wèi)中，馬慧芳，傅燕翔，等. 基于云計(jì)算平臺Hadoop的并行kmeans聚類算法設(shè)計(jì)研究＼[J＼].計(jì)算科學(xué)，2011， 38 （10）：166176.

＼[5＼]GHEMAWAT S，GOBIOFF H，LEUNG S. The google file system ＼[J＼]. SACM SIGOPS Operating Systems Review， 2003，37（5）：2943.

＼[6＼]張強(qiáng)，趙鄭.WIDE：海量數(shù)據(jù)的聚類算法＼[J＼]. 天津大學(xué)學(xué)報(bào)， 2006（7）：3339.

責(zé)任編輯（責(zé)任編輯：杜能鋼）