司福明，卜天然（安徽機(jī)電職業(yè)技術(shù)學(xué)院信息工程系，安徽 蕪湖 241000）

一種基于Hadoop云計(jì)算平臺(tái)大數(shù)據(jù)聚類算法設(shè)計(jì)*1

司福明，卜天然
（安徽機(jī)電職業(yè)技術(shù)學(xué)院信息工程系，安徽 蕪湖 241000）

傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)由于受到編程模型等的約束，產(chǎn)生了不同瓶頸，聚類算法的研究面臨著海量的大數(shù)據(jù)處理與分析的挑戰(zhàn)，新興計(jì)算模型Hadoop作為一種可并行處理的云計(jì)算平臺(tái)得到了廣泛應(yīng)用。文章對傳統(tǒng)聚類挖掘算法進(jìn)行改進(jìn)和優(yōu)化，在Hadoop云計(jì)算平臺(tái)上進(jìn)行K-means算法的并行化實(shí)現(xiàn)，降低算法的時(shí)間復(fù)雜度，提高了計(jì)算效率。實(shí)踐證明，改進(jìn)的K-means算法適合大規(guī)模數(shù)據(jù)集的聚類挖掘，具有高效、準(zhǔn)確、穩(wěn)定、安全等特性，適合于海量數(shù)據(jù)的分析和處理。

Hadoop；云計(jì)算平臺(tái)；大數(shù)據(jù)；聚類挖掘算法；并行化

1　引言

大數(shù)據(jù)技術(shù)、物聯(lián)網(wǎng)、云計(jì)算是當(dāng)今IT產(chǎn)業(yè)具有顛覆性的技術(shù)革命。大數(shù)據(jù)時(shí)代的到來對人們的生活方式、商業(yè)模式都發(fā)生著重要影響。隨著大數(shù)據(jù)的提出，給信息技術(shù)產(chǎn)業(yè)帶來了新的發(fā)展機(jī)遇，尤其對數(shù)據(jù)挖掘技術(shù)影響更為明顯。數(shù)據(jù)挖掘技術(shù)進(jìn)入一個(gè)新的發(fā)展階段，要提高大數(shù)據(jù)的準(zhǔn)確性，大數(shù)據(jù)的挖掘算法對大數(shù)據(jù)處理結(jié)果的誤差率必須在可接受的范圍內(nèi)，這就需要對傳統(tǒng)數(shù)據(jù)挖掘算法進(jìn)行改進(jìn)。文章以提高大數(shù)據(jù)挖掘效率和準(zhǔn)確度為目標(biāo)，將面向大數(shù)據(jù)的聚類挖掘算法準(zhǔn)確度和效率作為研究重點(diǎn)，對傳統(tǒng)的聚類算法進(jìn)行了必要的改進(jìn)并利用云計(jì)算平臺(tái)將改進(jìn)后的聚類挖掘算法進(jìn)行并行化實(shí)驗(yàn)。改進(jìn)型的聚類算法具有較好的理論和實(shí)用價(jià)值，可在大數(shù)據(jù)集的應(yīng)用平臺(tái)進(jìn)行廣泛推廣和應(yīng)用［1］。

2　關(guān)鍵技術(shù)概述

2.1基于hadoop的云計(jì)算平臺(tái)

2.1.1云計(jì)算技術(shù)

云計(jì)算作為一種基于互聯(lián)網(wǎng)的服務(wù)交付和使用模式，是指通過網(wǎng)絡(luò)以按需、易擴(kuò)展的方式獲得所需服務(wù)。它的核心思想是將大量用網(wǎng)絡(luò)連接起來的計(jì)算資源統(tǒng)一管理和調(diào)度，構(gòu)成一個(gè)資源池向用戶提供按需服務(wù)。云計(jì)算為用戶提供了最可靠、最安全的數(shù)據(jù)存儲(chǔ)中心，用戶可不再顧慮數(shù)據(jù)丟失、病毒入侵等問題。云計(jì)算的應(yīng)用模式主要有：軟件即服務(wù) （SaaS）、平臺(tái)即服務(wù)（PaaS）、基礎(chǔ)實(shí)施即服務(wù) （IaaS）三種。

2.1.2Hadoop

Hadoop是一個(gè)開源的、可以編寫和運(yùn)行分布式應(yīng)用來處理大規(guī)模數(shù)據(jù)的框架 （平臺(tái)）。其主要特點(diǎn)是用戶可以在不了解分布式底層細(xì)節(jié)的情況下，開發(fā)分布式程序充分利用集群的威力進(jìn)行高速運(yùn)算和存儲(chǔ)。

（1）HDFS（Hadoop Distributed File System）：分布式文件系統(tǒng)，可實(shí)現(xiàn)分布式存儲(chǔ)；

（2）MapReduce：分布式程序框架，可實(shí)現(xiàn)分布式計(jì)算。MapReduce程序框架如下：

Map函數(shù)：鍵/值對映射

＜k1，v1＞→＜k2，v2＞

E.g.：＜k1，v1＞：＜1，“abcd”＞，＜2，“cde”＞，＜3，“acd”＞，…..

＜k2，v2＞：＜‘a(chǎn)’，2＞，＜‘b’，1＞，＜‘c’，3＞，……

Reduce函數(shù)：規(guī)約

＜k2，list（v2）＞→＜k3，v3＞

E.g.：＜k2，list（v2） ＞：＜‘a(chǎn)’，list（1，2，3） ＞＜k3，v3＞：＜‘a(chǎn)’，6＞

基于Hadoop云計(jì)算平臺(tái)，建立HDFS分布式文件系統(tǒng)存儲(chǔ)海量文本數(shù)據(jù)集，通過文本詞頻利用MapReduce原理建立分布式索引，以分布式數(shù)據(jù)庫HBase存儲(chǔ)關(guān)鍵詞索引，并提供實(shí)時(shí)檢索，從而可實(shí)現(xiàn)對海量數(shù)據(jù)進(jìn)行的分布式并行處理。

2.2大數(shù)據(jù)技術(shù)

Big Data（大數(shù)據(jù)技術(shù)），因近年來互聯(lián)網(wǎng)、云計(jì)算、移動(dòng)和物聯(lián)網(wǎng)的迅猛發(fā)展而成為廣為關(guān)注的熱點(diǎn)話題。大數(shù)據(jù)是一種規(guī)模大到在獲取、存儲(chǔ)、管理、分析方面大大超出了傳統(tǒng)數(shù)據(jù)庫軟件工具能力范圍的數(shù)據(jù)集合，具有海量的數(shù)據(jù)規(guī)模、快速的數(shù)據(jù)流轉(zhuǎn)、多樣的數(shù)據(jù)類型和價(jià)值密度低四大特征。從技術(shù)層面來看，大數(shù)據(jù)與云計(jì)算的關(guān)系是密不可分的。大數(shù)據(jù)在使用過程中必須采用分布式架構(gòu)，其特點(diǎn)在于對海量數(shù)據(jù)進(jìn)行分布式的數(shù)據(jù)挖掘。但它必須依托云計(jì)算的分布式處理、分布式數(shù)據(jù)庫和云存儲(chǔ)、虛擬化技術(shù)［2］。

2.3聚類挖掘技術(shù)

聚類分析是數(shù)據(jù)挖掘采用的核心技術(shù)，聚類分析基于“物以類聚”的樸素思想，根據(jù)事物的特征對其進(jìn)行聚類或分類。從隱性層面來看，聚類分析的結(jié)果將會(huì)得到一組數(shù)據(jù)對象的集合，我們稱其為簇。在簇中的對象是彼此相似的，而其他簇中的對象則是相異的。在許多應(yīng)用中，可以將一個(gè)簇中的數(shù)據(jù)對象作為一個(gè)整體來對待。

聚類挖掘技術(shù)最早在統(tǒng)計(jì)學(xué)和人工智能等領(lǐng)域得到廣泛的研究。近年來，隨著數(shù)據(jù)挖掘的發(fā)展，聚類以其特有的優(yōu)點(diǎn)，成為數(shù)據(jù)挖掘研究領(lǐng)域一個(gè)非?；钴S的研究課題。在數(shù)據(jù)挖掘領(lǐng)域內(nèi)，經(jīng)常面臨含有海量數(shù)據(jù)的數(shù)據(jù)庫，因此，要不斷改進(jìn)面向大規(guī)模數(shù)據(jù)庫的聚類方法，以適應(yīng)新問題帶來的挑戰(zhàn)。

3　改進(jìn)K-means聚類算法研究

3.1K-means聚類算法基本思想與方法

K-means算法是很典型的基于距離的聚類分析算法，它采用距離作為相似性評價(jià)的指標(biāo)，即：如果兩個(gè)對象的距離越近，則它的相似度就越大。這種算法是認(rèn)為簇是由距離靠近的對象而組成的，因此它把能夠得到緊湊并且獨(dú)立的簇作為最終的目標(biāo)［3］。

算法過程如下：

（1）從N個(gè)文檔中隨機(jī)地選取K個(gè)文檔作為質(zhì)心

（2）測量剩余的每一個(gè)文檔到每個(gè)質(zhì)心的距離，同時(shí)將它歸到最近質(zhì)心的類

（3）再進(jìn)行重新計(jì)算已經(jīng)獲得的每個(gè)類的質(zhì)心

（4）迭代第二和第三步直到新質(zhì)心和原質(zhì)心相等或小于指定閾值

（5）算法完成

具體算法描述如下：

輸入：k，data［n］；

（1）選擇k個(gè)初始中心點(diǎn)，例如c［0］ =data［0］，…c［k-1］ =data［k-1］；

（2）對于data［0］….data［n］，分別與c［0］…c［k-1］比較，假定與c［i］差值最少，就標(biāo)記為i；

（3）對于所有標(biāo)記為i點(diǎn)，重新計(jì)算c［i］ =｛所有標(biāo)記為i的data［j］之和｝/標(biāo)記為i的個(gè)數(shù)；

（4）重復(fù) （2）（3），直到所有c［i］值的變化小于給定閾值。

3.2基于密度的增量的DBIK-means改進(jìn)方法

k-means算法缺點(diǎn)：在K-means算法中，K往往是給定的，因此，K值的選定是很難估計(jì)的。在運(yùn)算之前，不清楚給定的數(shù)據(jù)集應(yīng)該分成多少種類別才最恰當(dāng)。在K-means算法中，需要根據(jù)初始聚類中心來確定初始劃分，然后進(jìn)行優(yōu)化。這種選擇對聚類分析的結(jié)果會(huì)產(chǎn)生比較大的影響，如果初始值選擇不好，則有可能無法獲取有效的聚類結(jié)果。此外，在K-means算法框架中可以發(fā)現(xiàn)，當(dāng)運(yùn)算的數(shù)據(jù)量較大時(shí)，算法的時(shí)間開銷則非常之大。所以需要對算法的時(shí)間復(fù)雜度進(jìn)行一定程度的改進(jìn)［4］。

綜合k-means聚類算法的缺點(diǎn)，結(jié)合密度增量的基本思想，文章提出基于密度的增量kmeans聚類算法。

改進(jìn)的k-means算法以基于密度的k-means聚類結(jié)果為依據(jù)，對X-Y數(shù)據(jù)集合聚類。作為相異度的計(jì)算公式，DBIK-means聚類算法的偽代碼如下：

輸入：數(shù)據(jù)集合X，密度閾值minPts

輸出：若干任意形狀的簇

步驟：

從集合X中隨機(jī)取小部分?jǐn)?shù)據(jù)集Y，YX，同時(shí)計(jì)算Eps的大小

List centerPoint=null，clusters=null；//初始中心點(diǎn)集合，簇的集合都為空

for i=1 to|Y|//|Y|表示數(shù)據(jù)集合Y的大小，for循環(huán)用于計(jì)算數(shù)據(jù)點(diǎn)的密度

將集合Y中沒有劃分到任意簇的點(diǎn)劃分到與其相異度最近的簇中；

計(jì)算簇的中心點(diǎn)之間的距離的均值Dave；

for i=1 to|X-Y|//將集合X-Y中的點(diǎn)劃分到與其相異度最小的簇中

DBIK-means聚類算法可以發(fā)現(xiàn)若干任意形狀的簇，在準(zhǔn)確率和時(shí)間復(fù)雜度方面，算法對數(shù)據(jù)的輸入順序和minPts參數(shù)不敏感，DBIK-means算法可以有效處理高維混合屬性的數(shù)據(jù)集。

4　DBIK-means在云計(jì)算hadoop平臺(tái)設(shè)計(jì)

4.1DBIK-means聚類算法基于hadoop的并行優(yōu)化設(shè)計(jì)

聚類算法在Hadoop平臺(tái)上的實(shí)現(xiàn)過程比較復(fù)雜，需要實(shí)現(xiàn)map和reduce函數(shù)。DBIK-means聚類算法在Hadoop上的具體實(shí)現(xiàn)分為兩個(gè)階段。其設(shè)計(jì)最主要的內(nèi)容就是設(shè)計(jì)和實(shí)現(xiàn)map和Reduce函數(shù)，包括輸入和輸出 ＜key，value＞鍵值對的類型以及 map和 Reduce函數(shù)的具體邏輯等［5］。

（1）map函數(shù)設(shè)計(jì)

map函數(shù)的輸入包括一組＜key，value＞鍵值對的集合和密度閾值minPts，其中＜key，value＞是MapReduce框架默認(rèn)的格式，key表示當(dāng)前數(shù)據(jù)集合相對于輸入數(shù)據(jù)文件起始點(diǎn)的偏移量，value為對應(yīng)的數(shù)據(jù)；函數(shù)的輸出是一組＜key1，value1＞鍵值對的集合，其中key1表示簇的編號(hào)，value1表示屬于第key1個(gè)簇的相關(guān)屬性，包括簇的中心點(diǎn)、簇中點(diǎn)的個(gè)數(shù)Num、簇中所有點(diǎn)的和Sum以及簇中與中心點(diǎn)最遠(yuǎn)的點(diǎn)與中心點(diǎn)的相異度，i的取值范圍為1到k，k表示簇的個(gè)數(shù)。函數(shù)的偽代碼如下：

（2）combine函數(shù)設(shè)計(jì)

combine函數(shù)的輸入為一組＜key1，value1＞鍵值對的集合，key1和value1的含義同map函數(shù)中的＜key1，value1＞鍵值對中的key1和value1一樣。combine的偽代碼如下：

（3）reduce函數(shù)設(shè)計(jì)

reduce函數(shù)的功能是將同一個(gè)DataNode中的多個(gè)map函數(shù)生成的＜key，value＞鍵值對集合進(jìn)行合并，同時(shí)以JSON的格式持久化到分布式數(shù)據(jù)庫中，其偽代碼如下：

4.2hadoop平臺(tái)搭建與完全分布式實(shí)現(xiàn)

4.2.1hadoop平臺(tái)配置

采用完全分布模式才能真正體現(xiàn)Hadoop框架的優(yōu)勢所在。在綜合考慮資源使用效率和實(shí)驗(yàn)中PC數(shù)量有限的情況下，采用將U0作為JobTracker和NameNode，U1至U4作為TaskTracker和DataNode的方式來實(shí)現(xiàn)完全分布模式的配置。從分布式存儲(chǔ)的層面考慮，Hadoop集群由三個(gè)部分組成，包括兩個(gè)必選部分即一個(gè)NameNode和若干個(gè)DataNode，和一個(gè)可選部分即Secondary NameNode；為了確保Hadoop集群的可靠性，Secondary NameNode作為NameNode的備份，當(dāng)且僅當(dāng)NameNode出現(xiàn)異常時(shí)，采用Secondary NameNode重新啟動(dòng)整個(gè)Hadoop集群。從分布式應(yīng)用的層面考慮，Hadoop集群由一個(gè)JobTracker和若干個(gè)TaskTracker兩個(gè)必選部分組成，前者負(fù)責(zé)任務(wù)的調(diào)度管理，后者負(fù)責(zé)任務(wù)的并行執(zhí)行。為了便于進(jìn)行數(shù)據(jù)的讀取和本地的計(jì)算，JobTracker最好運(yùn)行在DataNode上，JobTracker和NameNode可以不在同一臺(tái)機(jī)器上［6］。

文章采用開源的分布式軟件Hadoop來搭建實(shí)驗(yàn)用的云計(jì)算平臺(tái)，用于測試DBIK-means聚類算法的性能。使用四臺(tái)機(jī)器，都安裝fedora 9一個(gè)master三個(gè)slave這么做是為了測試hdfs分布式存儲(chǔ)時(shí)備份成三份，關(guān)掉某一臺(tái)slave看是否影響整體的文件系統(tǒng)。

虛擬機(jī)：VMware-workstation-6.0.5-109488；

操作系統(tǒng)：操作系統(tǒng)fedora 9

系統(tǒng)配置：

四臺(tái)機(jī)器的具體網(wǎng)絡(luò)配置為：

Hostname　IP　Use master　192.168.213.170　NameNode，JobTracker slave1　192.168.213.172　DataNode，TaskTracker slave2　192.168.213.173　DataNode，TaskTracker slave3　192.168.213.175　DataNode，TaskTracker

（1）進(jìn)入到hadoop目錄下，配置conf目錄下的hadoop-env.sh中的JAVA_HOME的jdk路徑，例如："export JAVA_HOME=/usr/Java/jdk1.6.0_23"。

（2）配置conf目錄下的core-site.xm l，在標(biāo)簽＜configuration＞＜/configuration＞中添加如下配置：

Xm l代碼如下：

（3）配置conf目錄下的mapred-site.xm l在標(biāo)簽＜configuration＞＜/configuration＞中添加如下配置：

Xm l代碼如下：

4.2.2實(shí)驗(yàn)分析及小結(jié)

Hadoop配置好之后，在NameNode即U0機(jī)器的終端中執(zhí)行start-all.sh，啟動(dòng)Hadoop進(jìn)程。當(dāng)?shù)谝淮螁?dòng)Hadoop時(shí)，需要運(yùn)行Hadoop namenode-format命令對系統(tǒng)進(jìn)行格式化。Hadoop啟動(dòng)之后，會(huì)自動(dòng)啟動(dòng)瀏覽器，顯示NameNode的管理頁面，集群中各個(gè)DadaNode節(jié)點(diǎn)的狀態(tài)、已用存儲(chǔ)空間、剩余存儲(chǔ)空間和blocks數(shù)目等［7］。在完全分布式環(huán)境下對DBIK-means聚類算法進(jìn)行仿真實(shí)驗(yàn)，通過實(shí)驗(yàn)驗(yàn)證了DBIK-means聚類算法在處理大數(shù)據(jù)時(shí)，能夠得到更好的聚類結(jié)果和更短的運(yùn)行時(shí)間，數(shù)據(jù)量越大，時(shí)間性能優(yōu)勢越明顯，借助云平臺(tái)能夠獲得更好的加速比。但改進(jìn)算法對于具有密集噪聲點(diǎn)等方面的數(shù)據(jù)處理仍然存在局限性，需要進(jìn)一步加以完善。

［1］周愛武，崔丹丹，潘勇.一種優(yōu)化初始聚類中心的K-means聚類算法 ［J］.微型機(jī)與應(yīng)用，2011，30（13）：1—3，9.

［2］江小平，李成華，等.K-means聚類算法的MapReduce并行化實(shí)現(xiàn)［J］.華中科技大學(xué)學(xué)報(bào)，2011，39（S1）：120—124.

［3］孫吉貴，劉杰，趙連宇.聚類算法研究［J］.軟件學(xué)報(bào)，2008，19（1）：48—61.

［4］Dean J，Ghemawat S.MapReduce：simplified data processing on large clusters［J］.Communications of the ACM，2008，51（1）：107—113.

［5］趙衛(wèi)中，馬慧芳，傅燕翔，等.基于云計(jì)算平臺(tái)Hadoop的并行k-means聚類算法設(shè)計(jì)研究［J］.計(jì)算機(jī)科學(xué)，2011，38（10）：166—168.

［6］張琳，陳燕，汲業(yè)，等.一種基于密度的K-means算法研究［J］.計(jì)算機(jī)應(yīng)用研究，2011，28（11）：71-73.

［7］Chang F，Dean J，Ghemawat S，et al.Bigtable：A distributed storage system for structured data ［J］.ACM Transactions on Computer Systems（TOCS），2008，26（2）：1—4.

（責(zé)任編輯劉洪基）

Design of a Large Data Clustering Algorithm Based on Hadoop Cloud Computing Platform

SIFuming&BU Tianran
（Dept.，of Information Engineering，Anhui Technical College of Mechanical and Electrical Engineering，Wuhu，241000，Anhui Province）

The traditional datamining technology due to the constraint programmingmodel，resulting in a bottleneck，clustering algorithm research faces the challenge ofmass of data processing and analysis，the emerging computingmodel Hadoop as a parallel processing of cloud computing platform has been widely used in many fields.In this paper，the traditional clusteringmining algorithm is improved and optimized. The K-means algorithm is implemented on Hadoop cloud computing platform，which can reduce the time complexity and improve the computational efficiency.Practice has proved that the improved K-means algorithm is suitable for large-scale data sets clustering mining，with high efficiency，accuracy，stability，security and other haracteristics，suitable for the analysis and processing ofmassive data.

Hadoop；cloud computing platform；big data；Clustering Mining Algorithm；Parallel

TP301.6

A

1671-7406（2016）03-0049-07

安徽省教育廳2016年度高校自然科學(xué)研究項(xiàng)目，項(xiàng)目編號(hào)：KJ2016A134。

2015-12-10

司福明 （1983—），男，講師，碩士研究生，研究方向：數(shù)據(jù)挖掘技術(shù)，網(wǎng)絡(luò)化應(yīng)用系統(tǒng)。