基于Hadoop平臺(tái)的聚類K-means算法的研究

汪一百

（長沙醫(yī)學(xué)院,湖南 長沙 410219）

1 前言

隨著通信技術(shù)的迅速發(fā)展,如何從海量、復(fù)雜、多樣的網(wǎng)絡(luò)數(shù)據(jù)中挖掘出有價(jià)值的信息,是當(dāng)前IT行業(yè)面臨的難題。數(shù)據(jù)挖掘技術(shù)是利用統(tǒng)計(jì)學(xué)理論和人工智能技術(shù)的一門綜合性學(xué)科,其中聚類分析、遺傳算法及神經(jīng)網(wǎng)絡(luò)等算法已經(jīng)被廣泛應(yīng)用在大型數(shù)據(jù)集上。Hadoop平臺(tái)整合了數(shù)據(jù)倉儲(chǔ)、云計(jì)算管理、數(shù)據(jù)庫等一系列平臺(tái),是當(dāng)前學(xué)術(shù)界和工業(yè)界研究云計(jì)算的標(biāo)準(zhǔn)平臺(tái),運(yùn)行傳統(tǒng)的數(shù)據(jù)挖掘算法在該平臺(tái)上,可以有效提高數(shù)據(jù)挖掘的效率,對(duì)于云計(jì)算的研究具有積極的作用。

2 Hadoop平臺(tái)

2.1 Hadoop架構(gòu)

Hadoop從2005年作為Apache Lucene的子項(xiàng)目開始,經(jīng)過十幾年發(fā)展,形成了可以在存儲(chǔ)大數(shù)據(jù)集群上進(jìn)行分布式計(jì)算、開源的框架,具有高可靠性、高效性、高擴(kuò)展性及高容錯(cuò)性的優(yōu)點(diǎn)。

Hadoop架構(gòu)在不斷完善更新,其子項(xiàng)目的數(shù)量不斷增加,但最核心的是編程模型mapReduce和負(fù)責(zé)文件存儲(chǔ)系統(tǒng)HDFS機(jī)制。Hadoop架構(gòu)如圖1所示。

圖1 Hadoop架構(gòu)

(1)編程模型MapReduce

編程模型MapReduce是將映射（map）和規(guī)約（Reduce）有效地結(jié)合在一起,其作用是劃分任務(wù),匯聚結(jié)果。具體的過程是:首先將輸入Hadoop平臺(tái)的數(shù)據(jù)按照用戶自己的需求劃分為等長的數(shù)據(jù)塊,將劃分的數(shù)據(jù)塊分配一個(gè)map,然后重新對(duì)數(shù)據(jù)進(jìn)行整理,最后將多任務(wù)的結(jié)果進(jìn)行匯總,得出分析結(jié)果。

(2)HDFS機(jī)制

傳統(tǒng)的文件存儲(chǔ)系統(tǒng)無法滿足當(dāng)前海量數(shù)據(jù)信息的存儲(chǔ)工作,采用跨設(shè)備的分布式文件系統(tǒng)HDFS機(jī)制可以將數(shù)據(jù)有效地存儲(chǔ)在不同的工作單元上。HDFS集群由多個(gè)數(shù)據(jù)節(jié)點(diǎn)和一個(gè)名稱節(jié)點(diǎn)組成,其中數(shù)據(jù)節(jié)點(diǎn)主要負(fù)責(zé)文件系統(tǒng)客戶端的讀寫請(qǐng)求,名稱節(jié)點(diǎn)主要負(fù)責(zé)文件系統(tǒng)的命名空間及客戶端對(duì)文件的訪問。

2.2 Hadoop平臺(tái)的搭建

本實(shí)驗(yàn)搭建的Hadoop平臺(tái)硬件主要由三臺(tái)電腦、一個(gè)名稱節(jié)點(diǎn)和三個(gè)數(shù)據(jù)節(jié)點(diǎn)組成,電腦的配置如表1所示:

表1 平臺(tái)的硬件環(huán)境配置

平臺(tái)的軟件環(huán)境采用的操作系統(tǒng)是Ubuntu 11.10,并在此操作系統(tǒng)上安裝Hadoop2.7.5,JDK1.7和Mahout0.8等版本的軟件。

搭建的集群主要由三臺(tái)電腦,其IP地址的分配如下:

名稱節(jié)點(diǎn)192.168.1.33

數(shù)據(jù)節(jié)點(diǎn)192.168.1.33

數(shù)據(jù)節(jié)點(diǎn)192.168.1.66

數(shù)據(jù)節(jié)點(diǎn)192.168.1.88

3 K-means算法

3.1 Hadoop平臺(tái)下算法設(shè)計(jì)思想

1967年,MacQueen J.提出了基于距離的聚類K-Means算法,該算法具有較高的效率,在工業(yè)和科學(xué)領(lǐng)域有較強(qiáng)的影響力。

在Hadoop平臺(tái)上,K-Means算法的設(shè)計(jì)思想如下:

（1）將數(shù)據(jù)集群劃分為N個(gè)數(shù)據(jù)塊,分布式存儲(chǔ)在各個(gè)節(jié)點(diǎn)上；

（2）通過函數(shù)map()對(duì)每個(gè)數(shù)據(jù)塊進(jìn)行處理；

（3）計(jì)算所有節(jié)點(diǎn)到質(zhì)心的距離,把具體節(jié)點(diǎn)的結(jié)果附給最近的聚類,輸出該節(jié)點(diǎn)新的坐標(biāo)和聚類號(hào)；

（4）在Reduce端對(duì)上步的結(jié)果通過函數(shù)reduce()重新計(jì)算質(zhì)心,輸出新的質(zhì)心及新的聚類號(hào)；

（5）比較前后輸出的結(jié)果,如果兩者不同,則重新執(zhí)行（3）和（4）,否則,表示聚類已經(jīng)完成。

3.2 算法描述

K-means算法是一個(gè)反復(fù)不斷的直至準(zhǔn)則函數(shù)收斂的聚類算法。

（1）從數(shù)據(jù)集D中明確所需聚類的數(shù)目K,隨機(jī)選擇K個(gè)對(duì)象作為中心；

（2）通過中心與數(shù)據(jù)集中其他數(shù)據(jù)的距離對(duì)D進(jìn)行分類；

（3）對(duì)準(zhǔn)則函數(shù)（公式1）進(jìn)行計(jì)算；

其中,E為所有數(shù)據(jù)的平方誤差總和,mi為每個(gè)聚類塊的平均值,p為數(shù)據(jù)對(duì)象。

（4）判斷準(zhǔn)則函數(shù)是否滿足閾值,假如不滿足,則直接跳轉(zhuǎn)至步驟（2）,否則,直接結(jié)束。

K-means算法的具體流程如圖2所示:

圖2 K-means算法流程

4 基于Hadoop平臺(tái)上K-means算法的實(shí)現(xiàn)

4.1 算法實(shí)現(xiàn)

通過Hadoop平臺(tái)進(jìn)行K-means算法的實(shí)驗(yàn),算法的各個(gè)步驟是相互獨(dú)立的,通過把聚簇中心的數(shù)據(jù)緩存到平臺(tái)的分布式文件系統(tǒng)中,可以大大減少算法的執(zhí)行時(shí)間,進(jìn)而提高系統(tǒng)的效率。

算法的核心代碼如下所示:

SetZjdian=new HashSet();

for(int m=0;m

{

Setzhongxin=new HashSet();

//對(duì)聚類中心進(jìn)行重新計(jì)算

for(int j=0;j

{

Listdianshu=cluster.get(j).getMembers();

int juli=dianshu.juli();

if(juli<3)

{

zhongxin.add(cluster.get(j).getZhongxin());

continue;

}

//計(jì)算各個(gè)數(shù)據(jù)與中心的距離

double x=0.0,y=0.0;

for(int k1=0;k1

{

x+=dianshu.get(k1).getX();

y+=dianshu.get(k1).getY();

}

//得到新的中心點(diǎn)

Point th=new Point(-1,x/juli,y/juli,false);

zhongxin.add(th);

}

if(Zjdian.containsAll(zhongxin))

break;//判斷中心點(diǎn)是否發(fā)生變化

Zjdian=zhongxin;

cluster=clustering(zhongxin,prepare(zhongxin));

for(int nz=0;nz

cw+=cluster.get(nz).getCw();

}

return cluster;

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

本實(shí)驗(yàn)分別采用開源數(shù)據(jù)挖掘工具Weka和Hadoop平臺(tái)實(shí)現(xiàn)K-means算法,實(shí)驗(yàn)的結(jié)果如表2所示。

實(shí)驗(yàn)結(jié)果表明:當(dāng)數(shù)據(jù)集較小時(shí),Weka的執(zhí)行時(shí)間相對(duì)較少,但隨著數(shù)據(jù)規(guī)模的不斷增大,Weka的執(zhí)行效率下降,直至內(nèi)存空間不足,而無法順利地完成算法；而在Hadoop平臺(tái)上,數(shù)據(jù)規(guī)模較小時(shí),其運(yùn)行的效率較低,隨著數(shù)據(jù)規(guī)模的增加,運(yùn)行的效率并沒有明顯下降。

表2 實(shí)驗(yàn)結(jié)果分析

在當(dāng)今數(shù)據(jù)規(guī)模不斷爆炸式增長的環(huán)境下,Hadoop平臺(tái)良好的擴(kuò)展性和加速比對(duì)實(shí)現(xiàn)K-means聚類算法具有較強(qiáng)的實(shí)際意義。

5 結(jié)語

隨著數(shù)據(jù)規(guī)模的不斷擴(kuò)大,單機(jī)的運(yùn)算模式已經(jīng)不能滿足當(dāng)前社會(huì)的計(jì)算需求?；贖adoop平臺(tái)的聚類算法研究表明,當(dāng)數(shù)據(jù)規(guī)模越大,其系統(tǒng)的工作效率明顯優(yōu)于單機(jī)系統(tǒng),這給我們處理海量的數(shù)據(jù)提供了良好的平臺(tái)。本文由于篇幅所限,對(duì)于K-means算法的優(yōu)化工作沒有描述,在未來的工作中,將進(jìn)一步研究。

[1]方新麗.淺議數(shù)據(jù)挖掘技術(shù)在計(jì)算機(jī)審計(jì)中的應(yīng)用[J]. 電腦知識(shí)與技術(shù),2013,9(15):3445-3446.

[2]陳慧萍,林莉莉,王建東,等.Weka數(shù)據(jù)挖掘平臺(tái)及其二次開發(fā)內(nèi)[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(19):76-79.

[3]周兵,馮中慧,王和興.集群環(huán)境下的并行聚類算法之研究陽[J].計(jì)算機(jī)科學(xué),2004,30(7):20-21.

[4]郝水俠,許金超.云計(jì)算中相似驅(qū)動(dòng)的并行任務(wù)劃分方法[J].計(jì)算機(jī)科學(xué)與探索,2012,06(8):752-759.