一種基于Hadoop 的高效K -Medoids并行算法

王永貴，戴 偉，武 超

WANG Yonggui,DAI Wei,WU Chao

遼寧工程技術(shù)大學(xué) 軟件工程學(xué)院，遼寧 葫蘆島125105

College of Software,Liaoning Technical University,Huludao,Liaoning 125105,China

1 引言

在這個(gè)大數(shù)據(jù)的時(shí)代，數(shù)據(jù)量由TB 級(jí)升至PB 級(jí)快速地增長(zhǎng)，其速度遠(yuǎn)超摩爾定律的增長(zhǎng)速度[1]。面對(duì)海量的數(shù)據(jù)，如何正確處理這些數(shù)據(jù)，挖掘出有價(jià)值的信息，成為當(dāng)今主要的研究方向之一[2]。利用聚類算法進(jìn)行信息的自動(dòng)分類是處理這些數(shù)據(jù)的重要方法。

K-Medoids 算法和K-Means 都是基于劃分的聚類算法，此類算法簡(jiǎn)單，并且容易實(shí)現(xiàn)，被廣泛應(yīng)用于科學(xué)研究的各個(gè)領(lǐng)域[3-4]。但是其對(duì)初始聚類中心都比較的敏感[5]，并且無(wú)法很好地處理海量數(shù)據(jù)的聚類問(wèn)題。針對(duì)K-Medoids 算法的特點(diǎn)以及不足，有很多學(xué)者提出了各種改進(jìn)的K-Medoids 算法。文獻(xiàn)[6-7]實(shí)現(xiàn)了基于MapReduce 的K-Medoids 并行算法，用并行的計(jì)算思路解決了處理海量數(shù)據(jù)的時(shí)間問(wèn)題，但只是針對(duì)傳統(tǒng)的K-Medoids 算法進(jìn)行并行化處理，沒(méi)有解決K-Medoids算法對(duì)于初始中心敏感的問(wèn)題；文獻(xiàn)[8]根據(jù)密度信息產(chǎn)生初始中心，解決了初始中心敏感的問(wèn)題，但卻增加了算法的復(fù)雜度。其他的例如利用遺傳算法[9]，ACO[10]，人工蜂群[11]等措施來(lái)改進(jìn)算法，雖然在少量數(shù)據(jù)環(huán)境下能夠顯著提升K-Medoids 算法的性能，但卻因?yàn)轭~外的組件增加了算法的復(fù)雜性[12]，無(wú)法適應(yīng)大數(shù)據(jù)的現(xiàn)實(shí)背景。

因此，針對(duì)以上提出的問(wèn)題，結(jié)合當(dāng)前大數(shù)據(jù)的環(huán)境，本文提出了一種基于Hadoop 的高效K-Medoids 并行算法，其初始中心的選擇使用了基于樣本的預(yù)處理解決方案，簇心的替換采用了簇內(nèi)中心調(diào)整策略，計(jì)算模型選用了MapReduce 分布式計(jì)算模型，存儲(chǔ)系統(tǒng)使用了HDFS（Hadoop Distributed File System）分布式存儲(chǔ)系統(tǒng)。實(shí)驗(yàn)表明，該算法不僅延續(xù)了傳統(tǒng)K-Medoids 算法的優(yōu)勢(shì)，保證了聚類效果的優(yōu)越性與穩(wěn)定性，并且在處理海量數(shù)據(jù)時(shí)，算法的執(zhí)行效率也取得了較大程度的提高。

2 預(yù)備知識(shí)

2.1 MapReduce編程模型

MapReduce 是一種分布式編程模型，其最初是由Google 實(shí)驗(yàn)室提出的一個(gè)分布式并行計(jì)算框架，后由Apache 組織通過(guò)Hadoop 分布式計(jì)算平臺(tái)將其開(kāi)源實(shí)現(xiàn)。MapReduce 計(jì)算模型是將海量的數(shù)據(jù)進(jìn)行分割從而進(jìn)行分布式計(jì)算。其對(duì)數(shù)據(jù)的處理抽象成Map 和Reduce 兩個(gè)階段，每個(gè)階段都以鍵/值（key/value）作為輸入和輸出，即有[13]：

每一個(gè)map 以及reduce 都會(huì)分配到集群中的某一臺(tái)機(jī)器上運(yùn)行，每一臺(tái)機(jī)器的map 或reduce 操作都相互獨(dú)立，這樣就實(shí)現(xiàn)了map 之間的并行，reduce 之間的并行，以及map 和reduce之間的并行操作過(guò)程。

在初始階段，MapReduce 模型通過(guò)InputFormat 將數(shù)據(jù)切分成固定大小的片段（split）形成＜key1，value1＞的數(shù)據(jù)形式交付給map 進(jìn)行操作。map 執(zhí)行完成以后會(huì)根據(jù)相同的key 合并成＜key2，list(value2)＞的形式，然后在Partition 中使用Hash 算法將相同的key 交付給相應(yīng)的reduce 進(jìn)行處理操作，reduce 操作結(jié)束后通過(guò)OutputFormat形成＜key3，value3＞的形式存儲(chǔ)到文件中。

2.2 Top K 查詢算法

TopK算法的目的就是從海量的數(shù)據(jù)中選取最大的K個(gè)元素或記錄。其主要的基本思想就是維護(hù)一個(gè)具有K個(gè)元素的小頂堆。每當(dāng)有新的元素加入時(shí)，判斷其是否大于堆頂元素，若大于則用該元素代替堆頂元素，并重新維護(hù)小頂堆，直到處理完所有元素。

3 K -Medoids算法的介紹和分析

3.1 K -Medoids的算法思想

假設(shè)有n個(gè)h維的對(duì)象點(diǎn)，要將其聚類成k(k＜n)個(gè)簇，則將第i個(gè)對(duì)象點(diǎn)的第f維的值定義成Xif(i=1，2，…，n;f=1，2，…，h)。這里使用歐式距離來(lái)判定對(duì)象點(diǎn)之間的相似度，歐式距離越大代表相似度越小。利用歐氏距離，對(duì)象i與對(duì)象j之間的距離定義如下：

傳統(tǒng)K-Medoids算法描述如下：

輸入：聚類的個(gè)數(shù)k，包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集D。

輸出：滿足基于各聚類中心對(duì)象的距離最小標(biāo)準(zhǔn)的k個(gè)簇。

步驟1從數(shù)據(jù)集D中任意挑選k個(gè)對(duì)象作為初始中心點(diǎn)。

步驟2循環(huán)步驟3 到步驟5 直到每個(gè)聚類中心不再變化為止。

步驟3按照最短距離原則，將對(duì)象點(diǎn)分配到離其最近的簇中。

步驟4全局隨機(jī)選擇一個(gè)對(duì)象點(diǎn)Orandom作為替代簇心。

步驟5若替代簇心比原簇心的聚類效果更好，則將替代簇心作為新的聚類中心，否則跳轉(zhuǎn)到步驟2。

3.2 傳統(tǒng)K -Medoids的不足

（1）在進(jìn)行海量數(shù)據(jù)的聚類時(shí)，由于數(shù)據(jù)量巨大，無(wú)法存儲(chǔ)在單臺(tái)計(jì)算機(jī)的存儲(chǔ)器中，導(dǎo)致K-Medoids 算法無(wú)法正常進(jìn)行聚類操作。

（2）由于K-Medoids 算法自身的特性，其算法的時(shí)間復(fù)雜度較高，無(wú)法適應(yīng)大數(shù)據(jù)下的聚類操作。

（3）傳統(tǒng)K-Medoids 算法在選擇初始聚類中心時(shí)采用的是完全隨機(jī)策略，無(wú)法保證聚類結(jié)果的準(zhǔn)確性。

（4）在聚類中心的替換方法上，傳統(tǒng)K-Medoids 采用的是全局順序替換策略，這種方法雖然保證了聚類的效果，但是卻降低了算法的執(zhí)行效率，增加了算法的執(zhí)行時(shí)間。

4 改進(jìn)的K -Medoids算法

4.1 基于Top K 的并行隨機(jī)采樣

面對(duì)海量數(shù)據(jù)，初始中心的選擇顯得尤其重要，一些改進(jìn)的算法為了選出較好的初始中心而在聚類操作之前對(duì)全局?jǐn)?shù)據(jù)進(jìn)行預(yù)處理，但是隨著數(shù)據(jù)量的增大，預(yù)處理的代價(jià)也逐漸增加，降低了算法整體的運(yùn)行效率。所以本文采用了先采樣，然后在樣本內(nèi)進(jìn)行數(shù)據(jù)預(yù)處理，計(jì)算初始中心。

常用的文本隨機(jī)采樣一般分為兩種：（1）遍歷采樣（2）按字節(jié)偏移采樣。

第一種遍歷采樣方法如按行采樣，簡(jiǎn)單并且能夠保證原來(lái)的數(shù)據(jù)格式，但由于其遍歷過(guò)程隨著原數(shù)據(jù)以及采樣量的增加，時(shí)間復(fù)雜度呈線性增長(zhǎng)，對(duì)系統(tǒng)的消耗將逐漸增大，不適合大規(guī)模的采樣操作。

第二種按字節(jié)偏移的采樣方法，能夠適應(yīng)較大規(guī)模的數(shù)據(jù)采樣，但是面對(duì)海量數(shù)據(jù)的采樣操作，效率也不理想。

針對(duì)以上問(wèn)題，本文提出了一種基于TopK算法的隨機(jī)采樣過(guò)程，并利用Hadoop 平臺(tái)實(shí)現(xiàn)了對(duì)數(shù)據(jù)的并行采樣，其具體實(shí)現(xiàn)過(guò)程如下：

輸入：隨機(jī)數(shù)范圍H，樣本容量N，Reduce 的個(gè)數(shù)Rn。

輸出：N條數(shù)據(jù)樣本。

步驟1在Map 階段給每一個(gè)數(shù)據(jù)隨機(jī)產(chǎn)生一個(gè)0到H的整數(shù)作為其key 值，其數(shù)據(jù)內(nèi)容作為value 形成的鍵值對(duì)輸出。

步驟2將相同key值的數(shù)據(jù)合并成>的形式，并根據(jù)key 值進(jìn)行內(nèi)部排序。

步驟3每個(gè)Reduce輸出前N/Rn條數(shù)據(jù)。核心代碼如下所示：

（1）Map 階段：

Random rd=new Random（）；

intkey=rd.nextInt（H）；

Context.write（new IntWritable（key），value）；

（2）Reduce階段：

4.2 K -Medoids算法的改進(jìn)方案

（1）基于HDFS 的分布式存儲(chǔ)策略。因?yàn)镠DFS 是一種分布式存儲(chǔ)系統(tǒng)，其將原本需要一整塊連續(xù)存儲(chǔ)空間的數(shù)據(jù)，拆分成多個(gè)小數(shù)據(jù)塊，分別存儲(chǔ)在不同的存儲(chǔ)節(jié)點(diǎn)上。所以在面對(duì)海量數(shù)據(jù)時(shí)，也能夠?qū)?shù)據(jù)進(jìn)行高效的存取。

（2）針對(duì)傳統(tǒng)K-Medoids 算法的時(shí)間復(fù)雜度較高，無(wú)法進(jìn)行海量數(shù)據(jù)的聚類計(jì)算問(wèn)題，本文采用了基于MapReduce 的分布式計(jì)算模型，將一個(gè)大型的數(shù)據(jù)文件切分成多個(gè)小數(shù)據(jù)模塊，分別交付給多臺(tái)計(jì)算機(jī)利用MapReduce 計(jì)算模型進(jìn)行分布式計(jì)算，減少了單臺(tái)計(jì)算機(jī)的計(jì)算時(shí)間，加快了整體的計(jì)算速度。

（3）對(duì)于初始中心選取的改進(jìn)一般有兩種方案，一種是結(jié)合智能算法，第二種則是采用隨機(jī)策略。由于智能算法在大數(shù)據(jù)的環(huán)境下學(xué)習(xí)成本較高，而隨機(jī)選取策略不利于其聚類效果，所以本文結(jié)合文獻(xiàn)[14-16]提出一種更加適合MapReduce 編程模型的樣本預(yù)處理解決方案，其中采樣策略使用了4.1 節(jié)的并行隨機(jī)采樣，樣本容量（N）則根據(jù)數(shù)據(jù)對(duì)象個(gè)數(shù)（M）以及聚類數(shù)目（k）進(jìn)行動(dòng)態(tài)判定。樣本容量定義如（2）所示。

數(shù)據(jù)預(yù)處理的計(jì)算則使用了（3）中的公式，公式定義如下[9]：

（4）簇內(nèi)隨機(jī)替換策略[17-18]。由于順序替換不能夠適應(yīng)大數(shù)據(jù)的聚類計(jì)算[12]，所以采用簇內(nèi)隨機(jī)替換策略即在每個(gè)簇的內(nèi)部進(jìn)行中心點(diǎn)的隨機(jī)替換過(guò)程。實(shí)驗(yàn)表明，相比較原來(lái)的順序替換方式，此方法在處理海量數(shù)據(jù)時(shí)有更快的收斂速度。

4.3 新算法描述

改進(jìn)的K-Medoids算法的具體流程描述如下：

輸入：聚類個(gè)數(shù)k，包含N個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集，連續(xù)次數(shù)C。

輸出：滿足基于各聚類中心對(duì)象的距離最小標(biāo)準(zhǔn)的k個(gè)聚類。

處理流程：

步驟1并行隨機(jī)采樣。

步驟2樣本預(yù)處理，計(jì)算初始聚類中心，初步聚類：

步驟2-1利用MapReduce 計(jì)算模型分布式計(jì)算樣本內(nèi)每個(gè)節(jié)點(diǎn)之間的距離（dij）并保存在相應(yīng)的文件中，使用的距離測(cè)量為公式（1）的歐式距離。

步驟2-2使用上一步所保存的節(jié)點(diǎn)間距離關(guān)系，對(duì)每個(gè)節(jié)點(diǎn)j利用公式（3）計(jì)算Vj的值。

步驟2-3根據(jù)Vj按照升序進(jìn)行排序。選取序列中前k個(gè)值所對(duì)應(yīng)的k個(gè)點(diǎn)坐標(biāo)作為初始中心點(diǎn)，寫(xiě)入聚類中心文件，保存。

步驟2-4按照最短距離原則，將對(duì)象點(diǎn)分配到離其最近的聚類中心所在簇中。

步驟2-5計(jì)算各簇內(nèi)所有節(jié)點(diǎn)與其簇心的距離之和（olddistance）。

步驟3聚類中心替換

各簇內(nèi)隨機(jī)選擇一個(gè)點(diǎn)Orandom替換當(dāng)前簇心Onow，計(jì)算簇內(nèi)其他對(duì)象點(diǎn)與Orandom距離之和（newdistance），若newdistance 較olddistance 更小，則將Orandom作為當(dāng)前簇心Onow，否則保留原簇心不變。

步驟4分配節(jié)點(diǎn)，判斷終止。

步驟4-1根據(jù)當(dāng)前的聚類中心，將對(duì)象點(diǎn)分配到離其最近的聚類中心所在的簇中。

步驟4-2若k個(gè)簇心分別連續(xù)C次不變，則終止算法，否則跳轉(zhuǎn)到步驟3 中再次進(jìn)行。

核心代碼如下所示：

（1）KMMapper：map 階段。對(duì)象點(diǎn)分配到離其最近的聚類中心所在的簇中

（2）KMReduce：reduce 階段。選出Orandom，計(jì)算olddistance 以及newdistance。

（3）CenterCompare：判斷終止。比較olddistance 和newdistance的大小，重寫(xiě)簇心文件。

Hadoop 下改進(jìn)的K-Medoids算法流程如圖1 所示。

圖1 Hadoop 環(huán)境下改進(jìn)的K-Medoids算法流程圖

5 實(shí)驗(yàn)與性能分析

5.1 實(shí)驗(yàn)環(huán)境

在Linux 環(huán)境下搭建Hadoop 集群，共六臺(tái)計(jì)算機(jī)，其中一臺(tái)作為提供NameNode，ResourceManager 服務(wù)的master節(jié)點(diǎn)，其他五臺(tái)作為提供DataNode，NodeManager服務(wù)的slave 節(jié)點(diǎn)，其中作為master 節(jié)點(diǎn)的配置為：CPU型號(hào)為Intel core i5-460M；內(nèi)存為8 GB；硬盤(pán)為500 GB。其他五臺(tái)作為slave節(jié)點(diǎn)的配置為：CPU型號(hào)為Pentium?Dual-Core E6600；內(nèi)存為2 GB；硬盤(pán)為500 GB。六臺(tái)機(jī)器安裝的操作系統(tǒng)都為Ubuntu 12.04，集群上搭建的Hadoop 版本為Hadoop-2.2.0。圖2 顯示了這六臺(tái)機(jī)器之間的分布關(guān)系。

圖2 集群結(jié)構(gòu)

5.2 單機(jī)處理比較實(shí)驗(yàn)

5.2.1 收斂速度比較

實(shí)驗(yàn)內(nèi)容為比較改進(jìn)的K-Medoids 算法和傳統(tǒng)K-Medoids 算法在單機(jī)下處理相同數(shù)據(jù)時(shí)，完成聚類所需要的迭代次數(shù)及時(shí)間。其中改進(jìn)的K-Medoids 是在Hadoop 偽分布模式下運(yùn)行，傳統(tǒng)K-Medoids 是在普通串行環(huán)境下運(yùn)行。處理的數(shù)據(jù)集為6 類具有8 206 個(gè)對(duì)象的三維數(shù)據(jù)，數(shù)據(jù)集大小為0.2 MB，選取的聚類中心k為3，具體的收斂時(shí)間及迭代次數(shù)見(jiàn)表1。

表1 迭代次數(shù)及收斂速度

從表1 中可以看出，在單機(jī)偽分布環(huán)境下改進(jìn)的K-Medoids 算法平均迭代次數(shù)更少，擁有更好的全局收斂性，但是傳統(tǒng)K-Medoids串行算法所消耗的時(shí)間更少。這是因?yàn)樵谔幚砩倭繑?shù)據(jù)時(shí)，Hadoop 計(jì)算平臺(tái)并不能發(fā)揮其性能優(yōu)勢(shì)。在MapReduce 的計(jì)算框架下，不僅要經(jīng)過(guò)提交map 和reduce 作業(yè)的步驟，還要經(jīng)過(guò)將作業(yè)分片（split）、中間排序（sort）、合并（merge）、分配（partition）等過(guò)程，所以在處理少量數(shù)據(jù)的情況下，實(shí)際的計(jì)算時(shí)間在總消耗時(shí)間中所占比例較小，只有在大量數(shù)據(jù)的條件下才能更好地發(fā)揮出MapReduce計(jì)算框架的優(yōu)勢(shì)。

5.2.2 單機(jī)數(shù)據(jù)負(fù)荷測(cè)試

實(shí)驗(yàn)內(nèi)容為在不同數(shù)據(jù)負(fù)荷下，單機(jī)偽分布下改進(jìn)的K-Medoids 算法和傳統(tǒng)串行K-Medoids 算法執(zhí)行效率的比較，實(shí)驗(yàn)結(jié)果如表2，其中T1 代表傳統(tǒng)K-Medoids算法所消耗的時(shí)間，T2 代表改進(jìn)的K-Medoids 算法所消耗的時(shí)間。

從表2 可以看出，只有在數(shù)據(jù)量較小時(shí)，串行執(zhí)行的時(shí)間要少于偽分布下的執(zhí)行時(shí)間，并且在數(shù)據(jù)量達(dá)到400 MB 以上時(shí)，串行算法出現(xiàn)了內(nèi)存溢出，導(dǎo)致算法無(wú)法正常運(yùn)行，而在Hadoop 平臺(tái)下改進(jìn)的K-Medoids 算法卻能繼續(xù)執(zhí)行。

表2 單機(jī)負(fù)荷情況

因?yàn)閭鹘y(tǒng)K-Medoids 算法聚類時(shí)，數(shù)據(jù)需要讀入內(nèi)存中進(jìn)行操作，隨著數(shù)據(jù)量的增加，算法的時(shí)間復(fù)雜度也在急劇增長(zhǎng)，所以在面對(duì)海量數(shù)據(jù)的時(shí)候，傳統(tǒng)的K-Medoids 算法會(huì)導(dǎo)致內(nèi)存溢出的情況發(fā)生。而在MapReduce 分布式計(jì)算框架下結(jié)合HDFS 分布式存儲(chǔ)系統(tǒng)的支持，將計(jì)算及存儲(chǔ)過(guò)程進(jìn)行分布式處理，中間數(shù)據(jù)以流的形式傳輸，降低了單臺(tái)計(jì)算機(jī)的負(fù)擔(dān)，所以在Hadoop 平臺(tái)下改進(jìn)的K-Medoids 算法也能正常處理海量數(shù)據(jù)。

5.2.3 Iris數(shù)據(jù)集對(duì)比

本次實(shí)驗(yàn)?zāi)康氖菧y(cè)試在標(biāo)準(zhǔn)數(shù)據(jù)集下，算法的精確度，所用數(shù)據(jù)集Iris 來(lái)自UCI Repository（http：//archive.ics.uci.edu/ml/datasets/Iris）。Iris 數(shù)據(jù)集被分成了三組（Setosa，Versicolor，Virginica），每一組包含50 個(gè)數(shù)據(jù)對(duì)象，每個(gè)對(duì)象都含有4 種屬性。分別采用K-Means，傳統(tǒng)K-Medoids 以及改進(jìn)的K-Medoids 算法來(lái)測(cè)試各算法聚類的效果。這里由于數(shù)據(jù)量較小，所以不需要采樣，直接對(duì)全局?jǐn)?shù)據(jù)預(yù)處理。

表3，表4，表5分別表示K-Means，傳統(tǒng)K-Medoids以及改進(jìn)的K-Medoids算法對(duì)Iris的聚類結(jié)果。

表3 K-Means聚類結(jié)果

表4 傳統(tǒng)K-Medoids聚類結(jié)果

表5 改進(jìn)K-Medoids聚類結(jié)果

從表中可以得出，K-Means的正確率為62.7%，傳統(tǒng)K-Medoids的正確率為86.7%，改進(jìn)的K-Medoids正確率為92%，其中K-Means的正確率最低，改進(jìn)的K-Medoids正確率最高。因?yàn)閭鹘y(tǒng)的K-Medoids 和K-Means 算法初始中心的選取采用的是隨機(jī)策略，聚類效果隨初始中心的變化而波動(dòng)，并且K-Means 算法無(wú)法排除臟數(shù)據(jù)的干擾。而改進(jìn)的K-Medoids 算法初始中心的選取采用了數(shù)據(jù)預(yù)處理策略，避免了初始中心的隨機(jī)性，同時(shí)K-Medoids 算法自身的特性也能很好的避免臟數(shù)據(jù)的干擾。

5.3 集群測(cè)試

5.3.1 初始采樣測(cè)試

實(shí)驗(yàn)內(nèi)容為比較不同隨機(jī)采樣方式的效率。分別使用逐行遍歷采樣，字節(jié)偏移采樣以及基于TopK的并行隨機(jī)采樣進(jìn)行對(duì)比。其中并行采樣使用的為六臺(tái)主機(jī)所組成的Hadoop 集群，其中一臺(tái)作為NameNode和ResourceManager，其余五臺(tái)作為DataNode 和Node-Manager，選用的為1.2 GB 的數(shù)據(jù)集。實(shí)驗(yàn)結(jié)果如表6。

從表6 可以看出遍歷采樣的效率最差。抽取的樣本較少時(shí)，字節(jié)偏移采樣的效率最高，但是隨著采樣量的增加，其時(shí)間消耗呈線性增長(zhǎng)。并行采樣所耗費(fèi)時(shí)間趨于平穩(wěn)，并且在大規(guī)模數(shù)據(jù)采樣下，并行采樣所耗費(fèi)的時(shí)間最少。所以本文的并行采樣方法更適合大數(shù)據(jù)環(huán)境下的采樣操作。

表6 不同采樣所耗費(fèi)時(shí)間 s

5.3.2 人造數(shù)據(jù)集對(duì)比

實(shí)驗(yàn)內(nèi)容為在集群環(huán)境下，比較分布式K-Means算法和改進(jìn)的K-Medoids算法的聚類效果。

其中數(shù)據(jù)集使用的是四組服從二維高斯分布的人造數(shù)據(jù)集（A：紅色實(shí)心圓，B：綠色空心圓，C：藍(lán)色正三角，D：藍(lán)綠色五角星），每一組數(shù)據(jù)包含7 000 條二維坐標(biāo)，其中圖3為四組數(shù)據(jù)所組成原始數(shù)據(jù)集，圖4，圖5分別顯示的為使用分布式K-Means 算法和改進(jìn)的K-Medoids算法的聚類結(jié)果。

圖3 原始數(shù)據(jù)集

圖4 分布式K-Means聚類效果

圖中箭頭所指的點(diǎn)即為聚類后的聚類中心點(diǎn)。從圖中可以看出，在集群環(huán)境下改進(jìn)的K-Medoids 算法的聚類效果更好，并且其最終的簇心更加接近每一組數(shù)據(jù)的初始中心。而分布式K-Means 算法的聚類效果卻不理想，其A 組數(shù)據(jù)雖然比較接近原始數(shù)據(jù)，但是B、C、D 三組數(shù)據(jù)的聚類結(jié)果都有大幅度的偏差，并且C 組數(shù)據(jù)的簇心指向的是原數(shù)據(jù)集中不存在的點(diǎn)。這是因?yàn)镵-Means是根據(jù)均值來(lái)計(jì)算簇心，無(wú)法排除臟數(shù)據(jù)的干擾，導(dǎo)致其最終簇心可能指向的是原本不存在的點(diǎn)，并且由于其初始中心的隨機(jī)性，不能保證聚類結(jié)果的準(zhǔn)確性。所以在集群環(huán)境下，改進(jìn)的K-Medoids 算法的聚類效果更為精確。

圖5 改進(jìn)的K-Medoids算法聚類效果

5.3.3 集群負(fù)荷測(cè)試

實(shí)驗(yàn)內(nèi)容為在Hadoop 集群環(huán)境下，比較在不同數(shù)量的計(jì)算節(jié)點(diǎn)下，系統(tǒng)處理相同規(guī)模數(shù)據(jù)的效率。表7描述了幾組不同的實(shí)驗(yàn)數(shù)據(jù)集。每條記錄由2 維數(shù)值型數(shù)據(jù)組成，程序指定生成3 個(gè)中心(k=3)，默認(rèn)的數(shù)據(jù)分塊大小為128 MB。

表7 數(shù)據(jù)集情況

由于實(shí)驗(yàn)環(huán)境是由5 個(gè)DataNode 所組成的集群，所以分別選擇1，2，3，4，5 個(gè)DataNode 節(jié)點(diǎn)參與運(yùn)算，觀察在不同數(shù)量節(jié)點(diǎn)下，系統(tǒng)完成任務(wù)的時(shí)間，具體的實(shí)驗(yàn)結(jié)果如圖6 所示。

圖6 不同節(jié)點(diǎn)運(yùn)行時(shí)間圖

從圖6 可以看出，在數(shù)據(jù)量較小時(shí)，不同數(shù)量節(jié)點(diǎn)下的時(shí)間消耗趨于平穩(wěn)，而當(dāng)數(shù)據(jù)量較大時(shí)，隨著節(jié)點(diǎn)的增加，其收斂所消耗的時(shí)間明顯減少，說(shuō)明改進(jìn)的算法更適合應(yīng)用于大數(shù)據(jù)下的聚類操作。

5.3.4 集群環(huán)境下的加速比

加速比（speedup），是同一個(gè)任務(wù)在單處理器系統(tǒng)和并行處理器系統(tǒng)中運(yùn)行消耗的時(shí)間比率，用來(lái)衡量并行系統(tǒng)或程序并行化的性能和效果[8]。其計(jì)算公式定義為：

其中Tp表示并行算法執(zhí)行所消耗的時(shí)間，Ts表示串行算法執(zhí)行所消耗的時(shí)間，加速比越大，表示并行算法的執(zhí)行效率越高。這里實(shí)驗(yàn)仍然使用5.3.3 節(jié)中的數(shù)據(jù)集，生成4 個(gè)類別，分別采用1，2，3，4，5 個(gè)DataNode 節(jié)點(diǎn)計(jì)算其加速比，結(jié)果如圖7 所示。

圖7 加速比

從圖中可以看出每個(gè)作業(yè)的加速比都隨著節(jié)點(diǎn)數(shù)的增加而增加，尤其當(dāng)數(shù)據(jù)量較大時(shí)，增加節(jié)點(diǎn)可以顯著地提高并行執(zhí)行過(guò)程。這說(shuō)明了通過(guò)MapReduce 并行計(jì)算模型來(lái)執(zhí)行改進(jìn)的K-Medoids 算法可以有效地提高算法的執(zhí)行效率。

5.3.5 基于Hadoop 平臺(tái)的算法優(yōu)化

Hadoop 中數(shù)據(jù)是以塊（block）為單位進(jìn)行分布式處理，通常塊的個(gè)數(shù)決定了可以并行的map 個(gè)數(shù)，所以在不同塊大小時(shí)，算法執(zhí)行的效率也不相同。在Hadoop中塊大小的計(jì)算公式定義如下[19]：

其中minimumSize 默認(rèn)值為1，maxmumSize 默認(rèn)值為L(zhǎng)ong_MAXVALUE，所以可以通過(guò)修改blockSize 參數(shù)的值來(lái)改變塊的大小，從而決定map的個(gè)數(shù)。

這里通過(guò)修改blockSize 的值，分別將塊的大小設(shè)置為32 MB，64 MB，128 MB，256 MB 來(lái)比較改進(jìn)的K-Medoids 算法的執(zhí)行效率，數(shù)據(jù)使用5.3.3 節(jié)中的數(shù)據(jù)集，其分塊情況如表8 所示。

表8 不同數(shù)據(jù)集的分塊情況

不同數(shù)據(jù)集在不同數(shù)據(jù)塊大小下的運(yùn)行時(shí)間如圖8所示，運(yùn)行環(huán)境為6 臺(tái)機(jī)器所組成的Hadoop 集群，其中5 臺(tái)作為計(jì)算節(jié)點(diǎn)。

圖8 不同塊大小的執(zhí)行效率

可以看出算法執(zhí)行的效率并不完全和數(shù)據(jù)塊的大小呈正向或反向的線性關(guān)系。當(dāng)數(shù)據(jù)量較小時(shí)，block-Size 越大，相應(yīng)的map 個(gè)數(shù)越少，執(zhí)行的效率越低；數(shù)據(jù)量較大時(shí)的結(jié)果則相反。同時(shí)圖中顯示，數(shù)據(jù)集C的時(shí)間趨勢(shì)呈一個(gè)倒三角，當(dāng)blockSize 為64 MB 時(shí)，其執(zhí)行效率最高。

這是因?yàn)楫?dāng)處理的數(shù)據(jù)量較小時(shí)，較大的blockSize會(huì)減少可以并行的map 個(gè)數(shù)，無(wú)法體現(xiàn)集群并行計(jì)算的優(yōu)勢(shì)；當(dāng)處理較大數(shù)據(jù)時(shí)，如果blockSize 設(shè)置較小，雖然充分利用了集群的并行計(jì)算，但卻增加了map 任務(wù)的分配過(guò)程以及運(yùn)行作業(yè)所必須的尋址次數(shù)，增加了系統(tǒng)的總消耗，尤其在處理海量數(shù)據(jù)時(shí)，這些消耗是相當(dāng)巨大的。所以在使用Hadoop 平臺(tái)處理數(shù)據(jù)時(shí)，需要根據(jù)數(shù)據(jù)量來(lái)合理地進(jìn)行數(shù)據(jù)塊大小的設(shè)置。從以上實(shí)驗(yàn)可以得出：在當(dāng)前集群環(huán)境下，數(shù)據(jù)集和數(shù)據(jù)塊大小設(shè)置地合理比例為10∶1。

6 總結(jié)

本文在對(duì)傳統(tǒng)K-Medoids算法研究的基礎(chǔ)上，提出了一種并行的高效K-Medoids 改進(jìn)算法，并在Hadoop平臺(tái)上成功實(shí)現(xiàn)。通過(guò)標(biāo)準(zhǔn)數(shù)據(jù)集Iris 以及人造數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果，可以看出改進(jìn)的K-Medoids 算法比K-Means 以及傳統(tǒng)K-Medoids 算法有著更好的聚類精度。通過(guò)在不同大小數(shù)據(jù)集以及不同數(shù)量計(jì)算節(jié)點(diǎn)下的實(shí)驗(yàn)，表明了改進(jìn)的K-Medoids 算法在處理海量數(shù)據(jù)時(shí)較傳統(tǒng)的K-Medoids 算法有更好的收斂速度，更加適合大數(shù)據(jù)的聚類計(jì)算。最后在Hadoop 并行計(jì)算平臺(tái)下，根據(jù)其計(jì)算機(jī)制，通過(guò)調(diào)整數(shù)據(jù)塊的大小，實(shí)現(xiàn)算法的進(jìn)一步優(yōu)化。

當(dāng)然本文算法還有一些需要改進(jìn)的地方：在初始化中心節(jié)點(diǎn)時(shí)，通過(guò)保存樣本點(diǎn)之間的距離關(guān)系，使之后的計(jì)算能夠反復(fù)讀取距離值，不需要再次計(jì)算，減少了算法的計(jì)算量。但是由于沒(méi)有相關(guān)數(shù)據(jù)庫(kù)的支持，其數(shù)據(jù)的存儲(chǔ)及讀取都是基于文件操作，整體效率較低。所以下一步的目標(biāo)就是引入HBase 分布式數(shù)據(jù)庫(kù)[20]，從而提高算法的整體性能。

[1] 王珊，王會(huì)舉，覃雄派，等.架構(gòu)大數(shù)據(jù)：挑戰(zhàn)、現(xiàn)狀與展望[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（10）：1741-1752.

[2] 覃雄派，王會(huì)舉，杜小勇，等.大數(shù)據(jù)分析——RDBMS 與MapReduce的競(jìng)爭(zhēng)與共生[J].軟件學(xué)報(bào)，2012，23（1）：32-45.

[3] 孫勝，王元珍.基于核的自適應(yīng)K-Medoids 聚類[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（3）：674-675.

[4] 孟穎，羅克，劉建華，等.一種基于差分演化的K-medoids聚類算法[J].計(jì)算機(jī)應(yīng)用研究，2010，29（5）：1651-1653.

[5] Zhang Qiaoping，Couloigner I.A new and efficientK-medoid algorithm for spatial[C]//Computational Science and its Applications-ICCSA，2005：181-189.

[6] 張雪萍，龔康莉，趙廣才.基于MapReduce 的K-Medoids 并行算法[J].計(jì)算機(jī)應(yīng)用，2013，33（4）：1023-1025.

[7] 冀素琴，石洪波.基于MapReduce 的K_means 聚類集成[J].計(jì)算機(jī)工程，2013，39（9）：84-87.

[8] 姚麗娟，羅可，孟穎.一種新的k-medoids 聚類算法[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（19）：153-157.

[9] 郝占剛，王正歐.基于遺傳算法和k-medoids算法的聚類新算法[J].現(xiàn)代圖書(shū)情報(bào)技術(shù)，2006，136（5）：44-46.

[10] 孟穎，羅可，姚麗娟，等.一種基于ACO 的K-medoids 聚類算法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（16）：136-139.

[11] 李蓮，羅可，周博翔.一種改進(jìn)人工蜂群的K-medoids 聚類算法[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（16）：146-150.

[12] 夏寧霞，蘇一丹，覃希.一種高效的K-medoids聚類算法[J].計(jì)算機(jī)應(yīng)用研究，2010，27（12）：4517-4519.

[13] 虞倩倩，戴月明，李晶晶.基于MapReduce的ACO-K-means并行聚類算法[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（16）：117-120.

[14] Park Hae-Sang，Jun Chi-Hyuck.A simple and fast algorithm forK-medoids clustering[J].Expert Systems with Applications，2009，36（2）：3336-3341.

[15] Alper Z G.K-harmonic means data clustering with simulated[J].Applied Mathematics and Computation，2007，184：199-209.

[16] Pei Ying，Xu Jungang，Cen Zhiwang，et al.IKMC：An improved K-medoids clustering method for near-duplicated records detection[C]//International Conference on Computational Intelligence and Software Engineering，2009：1-4.

[17] Cardot H，Cénac P，Monnez J M.A fast and recursive algorithm for clustering large datasets with k-medians[J].Computational Statistics and Data Analysis，2012，56：1434-1449.

[18] Qiao Shaoyu，Geng Xinyu，Wu Min.An improved method for K_medoids algorithm[C]//International Conference on Business Computing and Global Informatization，2011：440-444.

[19] Tom White.Hadoop 權(quán)威指南[M].周敏奇，譯.北京：清華大學(xué)出版社，2011.

[20] 強(qiáng)彥，盧軍佐，劉濤，等.基于HBase 的并行BFS 方法[J].計(jì)算機(jī)科學(xué)，2013，40（3）：228-231.