司福明，卜天然

(安徽機(jī)電職業(yè)技術(shù)學(xué)院 信息工程系，安徽 蕪湖 241000)

?

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

司福明，卜天然

(安徽機(jī)電職業(yè)技術(shù)學(xué)院 信息工程系，安徽 蕪湖 241000)

摘要:為了提高聚類的準(zhǔn)確度，對傳統(tǒng)聚類挖掘算法進(jìn)行分析、改進(jìn)和優(yōu)化，在云計(jì)算Hadoop平臺上進(jìn)行DBIK-means算法的并行化，降低了算法的時(shí)間復(fù)雜度，提高了計(jì)算效率.通過實(shí)驗(yàn)驗(yàn)證，結(jié)果表明DBIK-means算法具有高效、準(zhǔn)確、穩(wěn)定、安全等特性，適合大規(guī)模數(shù)據(jù)集的聚類挖掘.

關(guān)鍵詞:Hadoop；云計(jì)算平臺；大數(shù)據(jù)；聚類挖掘算法；并行化

大數(shù)據(jù)技術(shù)、物聯(lián)網(wǎng)、云計(jì)算是當(dāng)今IT產(chǎn)業(yè)具有顛覆性的技術(shù)革命.大數(shù)據(jù)時(shí)代的到來對人們的生活方式、商業(yè)模式上都產(chǎn)生了重要影響.大數(shù)據(jù)的提出，給信息技術(shù)產(chǎn)業(yè)帶來了新的發(fā)展機(jī)遇，尤其對數(shù)據(jù)挖掘技術(shù)影響更為明顯[1].數(shù)據(jù)挖掘技術(shù)已經(jīng)進(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ì)算平臺將改進(jìn)后的聚類挖掘算法進(jìn)行并行化實(shí)驗(yàn).改進(jìn)型的聚類算法具有較好的理論和實(shí)用價(jià)值，可在大數(shù)據(jù)集的應(yīng)用平臺進(jìn)行廣泛推廣和應(yīng)用.

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

1.1基于Hadoop的云計(jì)算平臺

(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)、平臺即服務(wù)(PaaS)、基礎(chǔ)實(shí)施即服務(wù)(IaaS)三種.

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

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

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

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

E.g.,:<1,"abcd">,<2,"cde">,<3,"acd">,…..

:<'a',2>,<'b',1>,<'c',3>,……

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

E.g.,:<'a',list(1,2,3)>:<'a',6>

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

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

大數(shù)據(jù)技術(shù)(Big Data)，因近年來互聯(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].

1.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).

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

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

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

算法過程如下：

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

②測量剩余的每一個(gè)文檔至質(zhì)心距離，同時(shí)將其歸至最近質(zhì)心的類；

③再重新進(jìn)行計(jì)算已獲得的每個(gè)類質(zhì)心；

④迭代第二和第三步直到新質(zhì)心和原質(zhì)心小于或等于指定的閾值；

⑤算法全部結(jié)束.

具體算法描述如下：

輸入：k,data[n];

①選擇k個(gè)初始的中心點(diǎn)，例如c[0]=data[0],…c[k-1]=data[k-1]；

②對于data[0]….data[n]，分別與c[0]…c[k-1]進(jìn)行相比較，先假定其與c[i]差值最少，標(biāo)記為i；

③對全部標(biāo)記為i點(diǎn)，再重新進(jìn)行計(jì)算c[i]={所有標(biāo)記為i的data[j]之和}/標(biāo)記為i的個(gè)數(shù)；

④重復(fù)②③，直至所有c[i]值的變化小于給定的閾值.

2.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í)間開銷就會(huì)非常大.所以需對算法時(shí)間復(fù)雜度做一定程度的改進(jìn)[4].

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

改進(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)的密度

{

p=getPoint(i，Y)；//從數(shù)據(jù)集Y中取出第i條記錄

if centerPoint為空then

p作為一個(gè)簇的中心點(diǎn)放入centerPoint中；

else

if p與簇中心點(diǎn)之間的相異度不大于Eps,則將p劃分到與其相異度最小的簇中；

else

p作為一個(gè)簇的中心點(diǎn)放入centerPoint中；

}

for i=1 to centerPoint.size()//密度不小于minPts的點(diǎn)及其密度范圍內(nèi)的點(diǎn)組合成簇

{

p=centerPoint.get(i)；//從centerPoint中得到第i個(gè)中心點(diǎn)ifp的密度不小于minPts then以p點(diǎn)為中心，在p點(diǎn)Eps鄰域范圍內(nèi)的點(diǎn)組合成簇，并計(jì)算簇中與p距離最遠(yuǎn)的點(diǎn)與p的相異度，將p以及與簇相關(guān)的屬性放入clusters中；

}

do{//合并滿足條件的簇

flag=false；//標(biāo)記變量，用于標(biāo)記是否有簇被合并

for i=1 to clusters.size()

{

for j=i+1 to clusters.size()

{

if簇i，j中心點(diǎn)之間的相異度不大于2*max(i.Di，j.Dj)

{

flag=true；break；//合并簇i，j兩個(gè)簇

}

}

If flag==true

break；

}

}while(flag)

//將集合Y中沒有劃分到任意簇的點(diǎn)劃分到與其相異度最近的簇中；計(jì)算簇的中心點(diǎn)之間的距離的均值Dave；

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

{

p=get(X-Y，i)；//計(jì)算p與各個(gè)簇之間的相異度，并得到最小相異度的值Dmin；

if Dmin>Dave

//以p為中心點(diǎn)，生成一個(gè)新簇加入clusters中；

else

將p劃分到與其相異度最小的簇中；

重新計(jì)算Dave的值；

}

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

3DBIK-means在云計(jì)算Hadoop平臺設(shè)計(jì)

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

聚類算法在Hadoop平臺上的實(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ù)，包括輸入和輸出鍵值對的類型，以及map和Reduce函數(shù)的具體邏輯等.

(1)map函數(shù)設(shè)計(jì).map函數(shù)的輸入包括一組鍵值對的集合和密度閾值minPts，其中是MapReduce框架默認(rèn)的格式，key表示當(dāng)前數(shù)據(jù)集合相對于輸入數(shù)據(jù)文件起始點(diǎn)的偏移量，value為對應(yīng)的數(shù)據(jù)；函數(shù)的輸出是一組鍵值對的集合，其中key1表示簇的編號，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ù)[5].函數(shù)的偽代碼如下：

void map(LongWritable key,Text value){

minDist=-1.0D;

dis=getEuclideanDistance

(this.centers[i],onesample);

For(i=0;i

If(dis

minDis=dis;

clusterID=i;

}

}

intermediate(clusterID,value);

}

(2)combine函數(shù)設(shè)計(jì).combine函數(shù)的輸入為一組鍵值對的集合，key1和value1的含義同map函數(shù)中的鍵值對中的key1和value1一樣.combine的偽代碼如下：

void combine(Object key,Iterator values){

while(values.hasNext()){

inst=values.next();

for(i=1;i

value=new Object(featureitems[i]);

if(features.size()

features.add(value);

else{

features.set(i-1,(value+features.get(i-1));

}

}

}

}

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

void reduce(Object key,Iterator values){

float sum=0.of;

long sampNum=0;

PKmeansWritable myWritable=null;

While(values.hasNext()){

myWritable=values.next();

sum+=myWritable.getValue();

sampNum=myWritable.getCounter();

samp=sum/samNum;

}

}

3.2Hadoop平臺搭建與完全分布式實(shí)現(xiàn)

(1)Hadoop平臺配置.采用完全分布模式才能真正體現(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可以不在同一臺機(jī)器上[6].

文章采用開源的分布式軟件Hadoop來搭建實(shí)驗(yàn)用的云計(jì)算平臺，用于測試DBIK-means聚類算法的性能.共使用四臺計(jì)算機(jī)進(jìn)行測試分析，操作系統(tǒng)均安裝fedora 9，一臺機(jī)器為master，其余三臺機(jī)器slave，在測試hdfs分布式存儲(chǔ)時(shí)，數(shù)據(jù)備份成三份，測試時(shí)關(guān)閉其中一臺slave機(jī)器觀察是否影響整體的文件系統(tǒng)運(yùn)行.

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

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

系統(tǒng)配置：

四臺機(jī)器的具體網(wǎng)絡(luò)配置見表1：

①進(jìn)入到hadoop目錄下，配置conf目錄下的hadoop-env.sh中的JAVA_HOME cd /usr/local/hadoop sudogedit conf/hadoop-env.sh；然后在等號后面填寫你的jdk路徑，完全按此文檔來的話應(yīng)改為 “export JAVA_HOME=/usr/Java/jdk1.6.0_23”).

表1　四臺機(jī)器的網(wǎng)格配置

②配置conf目錄下的core-site.xml sudo gedit conf/core-site.xml(打開后標(biāo)簽中是空的，所以在空的地方加入如下配置).

Xml代碼如下：

③配置conf目錄下的mapred-site.xml sudo gedit conf/mapred-site.xml (打開后標(biāo)簽中也是空的，添加如下配置)

Xml代碼如下：

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].

(2)實(shí)驗(yàn)分析及小結(jié).對DBIK-means聚類算法進(jìn)行仿真實(shí)驗(yàn)，在數(shù)據(jù)集的規(guī)模處于穩(wěn)定的情況下，DBIK-means算法運(yùn)行時(shí)間隨著DataNode增加而逐漸降低.隨著集群中DataNode個(gè)數(shù)的增加，算法在數(shù)據(jù)集C上的執(zhí)行時(shí)間顯著降低，并且降低的幅度比數(shù)據(jù)集A和B明顯.從算法處理數(shù)據(jù)集A的運(yùn)行時(shí)間可以看出，對于一定規(guī)模的數(shù)據(jù)集A，有一個(gè)與之對應(yīng)的最有效的DataNode節(jié)點(diǎn)個(gè)數(shù)，使Hadoop集群在處理A時(shí)，既能提高

Hadoop集群資源的利用率，又能使處理時(shí)間達(dá)到最低.

實(shí)驗(yàn)表明，DBIK-means聚類算法在處理大數(shù)據(jù)時(shí)，有更好的聚類結(jié)果和更短的運(yùn)行時(shí)間，數(shù)據(jù)量越大，時(shí)間性能優(yōu)勢越明顯，借助云平臺能夠獲得更好的加速比.由此可以得出結(jié)論：運(yùn)用DBIK-means聚類算法在Hadoop集群上處理大數(shù)據(jù)時(shí)，能夠獲得較好的加速比，可有效降低時(shí)間復(fù)雜度.但改進(jìn)算法對于具有密集噪聲點(diǎn)等方面數(shù)據(jù)處理時(shí)仍然存在一定的局限性，需要加以進(jìn)一步完善.

參考文獻(xiàn)：

[1]陳如明.大數(shù)據(jù)時(shí)代的挑戰(zhàn),價(jià)值與應(yīng)對策略[J].移動(dòng)通信,2012(17):14-15.

[2]孟小峰,慈祥.大數(shù)據(jù)管理:概念、技術(shù)與挑戰(zhàn)[J]計(jì)算機(jī)技術(shù)與發(fā)展,2013,50(1):146-169.

[3]孫吉貴,劉杰,趙連宇.聚類算法研究[J].軟件學(xué)報(bào),2008,19(1):48-61.

[4]石偉.無線傳感網(wǎng)絡(luò)機(jī)器人定位導(dǎo)航在減災(zāi)救災(zāi)中的應(yīng)用[D].北京：北京郵電大學(xué),2012.

[5]張石磊，等.一種基于Hadoop云計(jì)算平臺的聚類算法優(yōu)化的研究[J].計(jì)算機(jī)科學(xué),2012,39(10):115-118.

[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 Big Data Clustering Algorithm Based on Hadoop Cloud Computing Platform

SI Fu-ming1, BU Tian-ran2

(AnhuiTechnicalCollegeofMechanicalandElectricalEngineering,Wuhu,Anhui241000,China)

Abstract:In order to improve the accuracy of clustering, the paper analyzes and optimizes the traditional clustering mining algorithm and tries to realize the parallelization of DBIK-means algorithm based on the Hadoop platform. The experiment shows that DBIK-means algorithm is efficient, accurate, stable and safe, and more suitable for the clustering mining of Big data.

Key words:Hadoop; Cloud Computing Platform; Bid data; Clustering Mining Algorithm; parallelization

DOI:10.13877/j.cnki.cn22-1284.2016.04.003

*收稿日期：2015-11-08

基金項(xiàng)目：安徽省教育廳2016年度高校自然科學(xué)研究重點(diǎn)項(xiàng)目“大中型企業(yè)員工績效評價(jià)理論模型信息化研究與實(shí)現(xiàn)”(KJ2016A134)

作者簡介：司福明，男，安徽蕪湖人，講師.

中圖分類號：TP274

文獻(xiàn)標(biāo)志碼：A

文章編號：1008-7974(2016)02-0009-05