一種基于Hadoop 的高效K -Medoids并行算法
2015-04-17 02:45:02王永貴
計算機工程與應用 2015年16期
王永貴，戴 偉，武 超
WANG Yonggui,DAI Wei,WU Chao
遼寧工程技術大學 軟件工程學院，遼寧 葫蘆島125105
College of Software,Liaoning Technical University,Huludao,Liaoning 125105,China
1 引言
在這個大數據的時代，數據量由TB 級升至PB 級快速地增長，其速度遠超摩爾定律的增長速度[1]。面對海量的數據，如何正確處理這些數據，挖掘出有價值的信息，成為當今主要的研究方向之一[2]。利用聚類算法進行信息的自動分類是處理這些數據的重要方法。
K-Medoids 算法和K-Means 都是基于劃分的聚類算法，此類算法簡單，并且容易實現，被廣泛應用于科學研究的各個領域[3-4]。但是其對初始聚類中心都比較的敏感[5]，并且無法很好地處理海量數據的聚類問題。針對K-Medoids 算法的特點以及不足，有很多學者提出了各種改進的K-Medoids 算法。文獻[6-7]實現了基于MapReduce 的K-Medoids 并行算法，用并行的計算思路解決了處理海量數據的時間問題，但只是針對傳統的K-Medoids 算法進行并行化處理，沒有解決K-Medoids算法對于初始中心敏感的問題；文獻[8]根據密度信息產生初始中心，解決了初始中心敏感的問題，但卻增加了算法的復雜度。其他的例如利用遺傳算法[9]，ACO[10]，人工蜂群[11]等措施來改進算法，雖然在少量數據環境下能夠顯著提升K-Medoids 算法的性能，但卻因為額外的組件增加了算法的復雜性[12]，無法適應大數據的現實背景。
因此，針對以上提出的問題，結合當前大數據的環境，本文提出了一種基于Hadoop 的高效K-Medoids 并行算法，其初始中心的選擇使用了基于樣本的預處理解決方案，簇心的替換采用了簇內中心調整策略，計算模型選用了MapReduce 分布式計算模型，存儲系統使用了HDFS（Hadoop Distributed File System）分布式存儲系統。實驗表明，該算法不僅延續了傳統K-Medoids 算法的優勢，保證了聚類效果的優越性與穩定性，并且在處理海量數據時，算法的執行效率也取得了較大程度的提高。
2 預備知識
2.1 MapReduce編程模型
MapReduce 是一種分布式編程模型，其最初是由Google 實驗室提出的一個分布式并行計算框架，后由Apache 組織通過Hadoop 分布式計算平臺將其開源實現。MapReduce 計算模型是將海量的數據進行分割從而進行分布式計算。其對數據的處理抽象成Map 和Reduce 兩個階段，每個階段都以鍵/值（key/value）作為輸入和輸出，即有[13]：
每一個map 以及reduce 都會分配到集群中的某一臺機器上運行，每一臺機器的map 或reduce 操作都相互獨立，這樣就實現了map 之間的并行，reduce 之間的并行，以及map 和reduce之間的并行操作過程。
在初始階段，MapReduce 模型通過InputFormat 將數據切分成固定大小的片段（split）形成＜key1，value1＞的數據形式交付給map 進行操作。map 執行完成以后會根據相同的key 合并成＜key2，list(value2)＞的形式，然后在Partition 中使用Hash 算法將相同的key 交付給相應的reduce 進行處理操作，reduce 操作結束后通過OutputFormat形成＜key3，value3＞的形式存儲到文件中。
2.2 Top K 查詢算法
TopK算法的目的就是從海量的數據中選取最大的K個元素或記錄。其主要的基本思想就是維護一個具有K個元素的小頂堆。每當有新的元素加入時，判斷其是否大于堆頂元素，若大于則用該元素代替堆頂元素，并重新維護小頂堆，直到處理完所有元素。
3 K -Medoids算法的介紹和分析
3.1 K -Medoids的算法思想
假設有n個h維的對象點，要將其聚類成k(k＜n)個簇，則將第i個對象點的第f維的值定義成Xif(i=1，2，…，n;f=1，2，…，h)。這里使用歐式距離來判定對象點之間的相似度，歐式距離越大代表相似度越小。利用歐氏距離，對象i與對象j之間的距離定義如下：
傳統K-Medoids算法描述如下：
輸入：聚類的個數k，包含n個數據對象的數據集D。
輸出：滿足基于各聚類中心對象的距離最小標準的k個簇。
步驟1從數據集D中任意挑選k個對象作為初始中心點。
步驟2循環步驟3 到步驟5 直到每個聚類中心不再變化為止。
步驟3按照最短距離原則，將對象點分配到離其最近的簇中。
步驟4全局隨機選擇一個對象點Orandom作為替代簇心。
步驟5若替代簇心比原簇心的聚類效果更好，則將替代簇心作為新的聚類中心，否則跳轉到步驟2。
3.2 傳統K -Medoids的不足
（1）在進行海量數據的聚類時，由于數據量巨大，無法存儲在單臺計算機的存儲器中，導致K-Medoids 算法無法正常進行聚類操作。
（2）由于K-Medoids 算法自身的特性，其算法的時間復雜度較高，無法適應大數據下的聚類操作。
（3）傳統K-Medoids 算法在選擇初始聚類中心時采用的是完全隨機策略，無法保證聚類結果的準確性。
（4）在聚類中心的替換方法上，傳統K-Medoids 采用的是全局順序替換策略，這種方法雖然保證了聚類的效果，但是卻降低了算法的執行效率，增加了算法的執行時間。
4 改進的K -Medoids算法
4.1 基于Top K 的并行隨機采樣
面對海量數據，初始中心的選擇顯得尤其重要，一些改進的算法為了選出較好的初始中心而在聚類操作之前對全局數據進行預處理，但是隨著數據量的增大，預處理的代價也逐漸增加，降低了算法整體的運行效率。所以本文采用了先采樣，然后在樣本內進行數據預處理，計算初始中心。
常用的文本隨機采樣一般分為兩種：（1）遍歷采樣（2）按字節偏移采樣。
第一種遍歷采樣方法如按行采樣，簡單并且能夠保證原來的數據格式，但由于其遍歷過程隨著原數據以及采樣量的增加，時間復雜度呈線性增長，對系統的消耗將逐漸增大，不適合大規模的采樣操作。
第二種按字節偏移的采樣方法，能夠適應較大規模的數據采樣，但是面對海量數據的采樣操作，效率也不理想。
針對以上問題，本文提出了一種基于TopK算法的隨機采樣過程，并利用Hadoop 平臺實現了對數據的并行采樣，其具體實現過程如下：
輸入：隨機數范圍H，樣本容量N，Reduce 的個數Rn。
輸出：N條數據樣本。
步驟1在Map 階段給每一個數據隨機產生一個0到H的整數作為其key 值，其數據內容作為value 形成
步驟2將相同key值的數據合并成
步驟3每個Reduce輸出前N/Rn條數據。核心代碼如下所示：
（1）Map 階段：
Random rd=new Random（）；
intkey=rd.nextInt（H）；
Context.write（new IntWritable（key），value）；
（2）Reduce階段：
4.2 K -Medoids算法的改進方案
（1）基于HDFS 的分布式存儲策略。因為HDFS 是一種分布式存儲系統，其將原本需要一整塊連續存儲空間的數據，拆分成多個小數據塊，分別存儲在不同的存儲節點上。所以在面對海量數據時，也能夠對數據進行高效的存取。
（2）針對傳統K-Medoids 算法的時間復雜度較高，無法進行海量數據的聚類計算問題，本文采用了基于MapReduce 的分布式計算模型，將一個大型的數據文件切分成多個小數據模塊，分別交付給多臺計算機利用MapReduce 計算模型進行分布式計算，減少了單臺計算機的計算時間，加快了整體的計算速度。
（3）對于初始中心選取的改進一般有兩種方案，一種是結合智能算法，第二種則是采用隨機策略。由于智能算法在大數據的環境下學習成本較高，而隨機選取策略不利于其聚類效果，所以本文結合文獻[14-16]提出一種更加適合MapReduce 編程模型的樣本預處理解決方案，其中采樣策略使用了4.1 節的并行隨機采樣，樣本容量（N）則根據數據對象個數（M）以及聚類數目（k）進行動態判定。樣本容量定義如（2）所示。
數據預處理的計算則使用了（3）中的公式，公式定義如下[9]：
（4）簇內隨機替換策略[17-18]。由于順序替換不能夠適應大數據的聚類計算[12]，所以采用簇內隨機替換策略即在每個簇的內部進行中心點的隨機替換過程。實驗表明，相比較原來的順序替換方式，此方法在處理海量數據時有更快的收斂速度。
4.3 新算法描述
改進的K-Medoids算法的具體流程描述如下：
輸入：聚類個數k，包含N個數據對象的數據集，連續次數C。
輸出：滿足基于各聚類中心對象的距離最小標準的k個聚類。
處理流程：
步驟1并行隨機采樣。
步驟2樣本預處理，計算初始聚類中心，初步聚類：
步驟2-1利用MapReduce 計算模型分布式計算樣本內每個節點之間的距離（dij）并保存在相應的文件中，使用的距離測量為公式（1）的歐式距離。
步驟2-2使用上一步所保存的節點間距離關系，對每個節點j利用公式（3）計算Vj的值。
步驟2-3根據Vj按照升序進行排序。選取序列中前k個值所對應的k個點坐標作為初始中心點，寫入聚類中心文件，保存。
步驟2-4按照最短距離原則，將對象點分配到離其最近的聚類中心所在簇中。
步驟2-5計算各簇內所有節點與其簇心的距離之和（olddistance）。
步驟3聚類中心替換
各簇內隨機選擇一個點Orandom替換當前簇心Onow，計算簇內其他對象點與Orandom距離之和（newdistance），若newdistance 較olddistance 更小，則將Orandom作為當前簇心Onow，否則保留原簇心不變。
步驟4分配節點，判斷終止。
步驟4-1根據當前的聚類中心，將對象點分配到離其最近的聚類中心所在的簇中。
步驟4-2若k個簇心分別連續C次不變，則終止算法，否則跳轉到步驟3 中再次進行。
核心代碼如下所示：
（1）KMMapper：map 階段。對象點分配到離其最近的聚類中心所在的簇中
（2）KMReduce：reduce 階段。選出Orandom，計算olddistance 以及newdistance。
（3）CenterCompare：判斷終止。比較olddistance 和newdistance的大小，重寫簇心文件。
Hadoop 下改進的K-Medoids算法流程如圖1 所示。
圖1 Hadoop 環境下改進的K-Medoids算法流程圖
5 實驗與性能分析
5.1 實驗環境
在Linux 環境下搭建Hadoop 集群，共六臺計算機，其中一臺作為提供NameNode，ResourceManager 服務的master節點，其他五臺作為提供DataNode，NodeManager服務的slave 節點，其中作為master 節點的配置為：CPU型號為Intel core i5-460M；內存為8 GB；硬盤為500 GB。其他五臺作為slave節點的配置為：CPU型號為Pentium?Dual-Core E6600；內存為2 GB；硬盤為500 GB。六臺機器安裝的操作系統都為Ubuntu 12.04，集群上搭建的Hadoop 版本為Hadoop-2.2.0。圖2 顯示了這六臺機器之間的分布關系。
圖2 集群結構
5.2 單機處理比較實驗
5.2.1 收斂速度比較
實驗內容為比較改進的K-Medoids 算法和傳統K-Medoids 算法在單機下處理相同數據時，完成聚類所需要的迭代次數及時間。其中改進的K-Medoids 是在Hadoop 偽分布模式下運行，傳統K-Medoids 是在普通串行環境下運行。處理的數據集為6 類具有8 206 個對象的三維數據，數據集大小為0.2 MB，選取的聚類中心k為3，具體的收斂時間及迭代次數見表1。
表1 迭代次數及收斂速度
從表1 中可以看出，在單機偽分布環境下改進的K-Medoids 算法平均迭代次數更少，擁有更好的全局收斂性，但是傳統K-Medoids串行算法所消耗的時間更少。這是因為在處理少量數據時，Hadoop 計算平臺并不能發揮其性能優勢。在MapReduce 的計算框架下，不僅要經過提交map 和reduce 作業的步驟，還要經過將作業分片（split）、中間排序（sort）、合并（merge）、分配（partition）等過程，所以在處理少量數據的情況下，實際的計算時間在總消耗時間中所占比例較小，只有在大量數據的條件下才能更好地發揮出MapReduce計算框架的優勢。
5.2.2 單機數據負荷測試
實驗內容為在不同數據負荷下，單機偽分布下改進的K-Medoids 算法和傳統串行K-Medoids 算法執行效率的比較，實驗結果如表2，其中T1 代表傳統K-Medoids算法所消耗的時間，T2 代表改進的K-Medoids 算法所消耗的時間。
從表2 可以看出，只有在數據量較小時，串行執行的時間要少于偽分布下的執行時間，并且在數據量達到400 MB 以上時，串行算法出現了內存溢出，導致算法無法正常運行，而在Hadoop 平臺下改進的K-Medoids 算法卻能繼續執行。
表2 單機負荷情況
因為傳統K-Medoids 算法聚類時，數據需要讀入內存中進行操作，隨著數據量的增加，算法的時間復雜度也在急劇增長，所以在面對海量數據的時候，傳統的K-Medoids 算法會導致內存溢出的情況發生。而在MapReduce 分布式計算框架下結合HDFS 分布式存儲系統的支持，將計算及存儲過程進行分布式處理，中間數據以
5.2.3 Iris數據集對比
本次實驗目的是測試在標準數據集下，算法的精確度，所用數據集Iris 來自UCI Repository（http：//archive.ics.uci.edu/ml/datasets/Iris）。Iris 數據集被分成了三組（Setosa，Versicolor，Virginica），每一組包含50 個數據對象，每個對象都含有4 種屬性。分別采用K-Means，傳統K-Medoids 以及改進的K-Medoids 算法來測試各算法聚類的效果。這里由于數據量較小，所以不需要采樣，直接對全局數據預處理。
表3，表4，表5分別表示K-Means，傳統K-Medoids以及改進的K-Medoids算法對Iris的聚類結果。
表3 K-Means聚類結果
表4 傳統K-Medoids聚類結果
表5 改進K-Medoids聚類結果
從表中可以得出，K-Means的正確率為62.7%，傳統K-Medoids的正確率為86.7%，改進的K-Medoids正確率為92%，其中K-Means的正確率最低，改進的K-Medoids正確率最高。因為傳統的K-Medoids 和K-Means 算法初始中心的選取采用的是隨機策略，聚類效果隨初始中心的變化而波動，并且K-Means 算法無法排除臟數據的干擾。而改進的K-Medoids 算法初始中心的選取采用了數據預處理策略，避免了初始中心的隨機性，同時K-Medoids 算法自身的特性也能很好的避免臟數據的干擾。
5.3 集群測試
5.3.1 初始采樣測試
實驗內容為比較不同隨機采樣方式的效率。分別使用逐行遍歷采樣，字節偏移采樣以及基于TopK的并行隨機采樣進行對比。其中并行采樣使用的為六臺主機所組成的Hadoop 集群，其中一臺作為NameNode和ResourceManager，其余五臺作為DataNode 和Node-Manager，選用的為1.2 GB 的數據集。實驗結果如表6。
從表6 可以看出遍歷采樣的效率最差。抽取的樣本較少時，字節偏移采樣的效率最高，但是隨著采樣量的增加，其時間消耗呈線性增長。并行采樣所耗費時間趨于平穩，并且在大規模數據采樣下，并行采樣所耗費的時間最少。所以本文的并行采樣方法更適合大數據環境下的采樣操作。
表6 不同采樣所耗費時間 s
5.3.2 人造數據集對比
實驗內容為在集群環境下，比較分布式K-Means算法和改進的K-Medoids算法的聚類效果。
其中數據集使用的是四組服從二維高斯分布的人造數據集（A：紅色實心圓，B：綠色空心圓，C：藍色正三角，D：藍綠色五角星），每一組數據包含7 000 條二維坐標，其中圖3為四組數據所組成原始數據集，圖4，圖5分別顯示的為使用分布式K-Means 算法和改進的K-Medoids算法的聚類結果。
圖3 原始數據集
圖4 分布式K-Means聚類效果
圖中箭頭所指的點即為聚類后的聚類中心點。從圖中可以看出，在集群環境下改進的K-Medoids 算法的聚類效果更好，并且其最終的簇心更加接近每一組數據的初始中心。而分布式K-Means 算法的聚類效果卻不理想，其A 組數據雖然比較接近原始數據，但是B、C、D 三組數據的聚類結果都有大幅度的偏差，并且C 組數據的簇心指向的是原數據集中不存在的點。這是因為K-Means是根據均值來計算簇心，無法排除臟數據的干擾，導致其最終簇心可能指向的是原本不存在的點，并且由于其初始中心的隨機性，不能保證聚類結果的準確性。所以在集群環境下，改進的K-Medoids 算法的聚類效果更為精確。
圖5 改進的K-Medoids算法聚類效果
5.3.3 集群負荷測試
實驗內容為在Hadoop 集群環境下，比較在不同數量的計算節點下，系統處理相同規模數據的效率。表7描述了幾組不同的實驗數據集。每條記錄由2 維數值型數據組成，程序指定生成3 個中心(k=3)，默認的數據分塊大小為128 MB。
表7 數據集情況
由于實驗環境是由5 個DataNode 所組成的集群，所以分別選擇1，2，3，4，5 個DataNode 節點參與運算，觀察在不同數量節點下，系統完成任務的時間，具體的實驗結果如圖6 所示。
圖6 不同節點運行時間圖
從圖6 可以看出，在數據量較小時，不同數量節點下的時間消耗趨于平穩，而當數據量較大時，隨著節點的增加，其收斂所消耗的時間明顯減少，說明改進的算法更適合應用于大數據下的聚類操作。
5.3.4 集群環境下的加速比
加速比（speedup），是同一個任務在單處理器系統和并行處理器系統中運行消耗的時間比率，用來衡量并行系統或程序并行化的性能和效果[8]。其計算公式定義為：
其中Tp表示并行算法執行所消耗的時間，Ts表示串行算法執行所消耗的時間，加速比越大，表示并行算法的執行效率越高。這里實驗仍然使用5.3.3 節中的數據集，生成4 個類別，分別采用1，2，3，4，5 個DataNode 節點計算其加速比，結果如圖7 所示。
圖7 加速比
從圖中可以看出每個作業的加速比都隨著節點數的增加而增加，尤其當數據量較大時，增加節點可以顯著地提高并行執行過程。這說明了通過MapReduce 并行計算模型來執行改進的K-Medoids 算法可以有效地提高算法的執行效率。
5.3.5 基于Hadoop 平臺的算法優化
Hadoop 中數據是以塊（block）為單位進行分布式處理，通常塊的個數決定了可以并行的map 個數，所以在不同塊大小時，算法執行的效率也不相同。在Hadoop中塊大小的計算公式定義如下[19]：
其中minimumSize 默認值為1，maxmumSize 默認值為Long_MAXVALUE，所以可以通過修改blockSize 參數的值來改變塊的大小，從而決定map的個數。
這里通過修改blockSize 的值，分別將塊的大小設置為32 MB，64 MB，128 MB，256 MB 來比較改進的K-Medoids 算法的執行效率，數據使用5.3.3 節中的數據集，其分塊情況如表8 所示。
表8 不同數據集的分塊情況
不同數據集在不同數據塊大小下的運行時間如圖8所示，運行環境為6 臺機器所組成的Hadoop 集群，其中5 臺作為計算節點。
圖8 不同塊大小的執行效率
可以看出算法執行的效率并不完全和數據塊的大小呈正向或反向的線性關系。當數據量較小時，block-Size 越大，相應的map 個數越少，執行的效率越低；數據量較大時的結果則相反。同時圖中顯示，數據集C的時間趨勢呈一個倒三角，當blockSize 為64 MB 時，其執行效率最高。
這是因為當處理的數據量較小時，較大的blockSize會減少可以并行的map 個數，無法體現集群并行計算的優勢；當處理較大數據時，如果blockSize 設置較小，雖然充分利用了集群的并行計算，但卻增加了map 任務的分配過程以及運行作業所必須的尋址次數，增加了系統的總消耗，尤其在處理海量數據時，這些消耗是相當巨大的。所以在使用Hadoop 平臺處理數據時，需要根據數據量來合理地進行數據塊大小的設置。從以上實驗可以得出：在當前集群環境下，數據集和數據塊大小設置地合理比例為10∶1。
6 總結
本文在對傳統K-Medoids算法研究的基礎上，提出了一種并行的高效K-Medoids 改進算法，并在Hadoop平臺上成功實現。通過標準數據集Iris 以及人造數據集的實驗結果，可以看出改進的K-Medoids 算法比K-Means 以及傳統K-Medoids 算法有著更好的聚類精度。通過在不同大小數據集以及不同數量計算節點下的實驗，表明了改進的K-Medoids 算法在處理海量數據時較傳統的K-Medoids 算法有更好的收斂速度，更加適合大數據的聚類計算。最后在Hadoop 并行計算平臺下，根據其計算機制，通過調整數據塊的大小，實現算法的進一步優化。
當然本文算法還有一些需要改進的地方：在初始化中心節點時，通過保存樣本點之間的距離關系，使之后的計算能夠反復讀取距離值，不需要再次計算，減少了算法的計算量。但是由于沒有相關數據庫的支持，其數據的存儲及讀取都是基于文件操作，整體效率較低。所以下一步的目標就是引入HBase 分布式數據庫[20]，從而提高算法的整體性能。
[1] 王珊，王會舉，覃雄派，等.架構大數據：挑戰、現狀與展望[J].計算機學報，2011，34（10）：1741-1752.
[2] 覃雄派，王會舉，杜小勇，等.大數據分析——RDBMS 與MapReduce的競爭與共生[J].軟件學報，2012，23（1）：32-45.
[3] 孫勝，王元珍.基于核的自適應K-Medoids 聚類[J].計算機工程與設計，2009，30（3）：674-675.
[4] 孟穎，羅克，劉建華，等.一種基于差分演化的K-medoids聚類算法[J].計算機應用研究，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].計算機應用，2013，33（4）：1023-1025.
[7] 冀素琴，石洪波.基于MapReduce 的K_means 聚類集成[J].計算機工程，2013，39（9）：84-87.
[8] 姚麗娟，羅可，孟穎.一種新的k-medoids 聚類算法[J].計算機工程與應用，2013，49（19）：153-157.
[9] 郝占剛，王正歐.基于遺傳算法和k-medoids算法的聚類新算法[J].現代圖書情報技術，2006，136（5）：44-46.
[10] 孟穎，羅可，姚麗娟，等.一種基于ACO 的K-medoids 聚類算法[J].計算機工程與應用，2012，48（16）：136-139.
[11] 李蓮，羅可，周博翔.一種改進人工蜂群的K-medoids 聚類算法[J].計算機工程與應用，2013，49（16）：146-150.
[12] 夏寧霞，蘇一丹，覃希.一種高效的K-medoids聚類算法[J].計算機應用研究，2010，27（12）：4517-4519.
[13] 虞倩倩，戴月明，李晶晶.基于MapReduce的ACO-K-means并行聚類算法[J].計算機工程與應用，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 權威指南[M].周敏奇，譯.北京：清華大學出版社，2011.
[20] 強彥，盧軍佐，劉濤，等.基于HBase 的并行BFS 方法[J].計算機科學，2013，40（3）：228-231.
