基于相似度矩陣的K—neans算法的MapReduce并行化實現(xiàn)

曹奇敏　劉鴻霞

摘要：為了提高基于相似度矩陣的K-Means算法（SMK-means）處理大數(shù)據(jù)的能力，它使用MapReduce分布式編程模型，并結(jié)合SMK-means算法自身的特點，設計出了SMK-means算法基于MapReduce的并行化實現(xiàn)。通過設計Map和Re-duce函數(shù)實現(xiàn)了SMK-means算法的并行化。Map函數(shù)通過計算樣本和聚簇中心的相似度來確定樣本的聚簇歸屬，Re-duce函數(shù)用于完成聚簇中心的計算。實驗結(jié)果證明，基于MapReduce的并行化的SMK-means算法在保證文本挖掘性能不降的前提下，使得運行效率得到了大幅度提升。

關鍵詞：K-Means算法；相似度矩陣；MapReduce模型；并行計算；文本挖掘

中圖分類號：TP391 文獻標識碼：A 文章編號：1009-3044（2017）18-0018-03

1概述

隨著大數(shù)據(jù)時代的到來，人們所接觸到的數(shù)據(jù)量成PB級別快速增長，同時還要求快速高效地處理所得到的數(shù)據(jù)。對于數(shù)據(jù)處理有兩方面的要求，一是要比數(shù)據(jù)產(chǎn)生的速度快，二是還要達到數(shù)據(jù)使用者對處理結(jié)果的預期。盡管這兩個要求通過使用并行計算的框架得到了一定程度上的滿足，但是MPI等傳統(tǒng)的并行框架還存在不少缺點，像技術人員需要自己實現(xiàn)對任務分配、集群管理等工作的編碼，它在可擴展性上也有一定的限制等問題，這樣就直接增高了傳統(tǒng)并行框架的使用門檻，也無法將成本控制在一個較低的水平。而MapReduce等并行計算框架的出現(xiàn)較好地解決了并行計算實現(xiàn)難和成本高的問題。本文使用MapReduce并行框架，對基于相似度矩陣的K-Means算法（SMK-means）進行并行化處理。

2 MapReduce編程模型

MapReduce處理大數(shù)據(jù)集，其關鍵步驟為Map函數(shù)和Re-duce函數(shù)的設計與實現(xiàn)。用戶根據(jù)自己的要求對這兩個函數(shù)進行自定義，函數(shù)的輸入與輸出都是使用鍵值對的形式。

Map函數(shù)中，MapReduce模型首先把數(shù)據(jù)集平均分割成若干個數(shù)據(jù)塊，再把各數(shù)據(jù)塊解析成in，V_in>對的形式。各個數(shù)據(jù)塊經(jīng)過Map函數(shù)的處理得到一組相應的結(jié)果，其結(jié)果記錄為m，V_m>對。然后這些結(jié)果將會被輸入到Reduce函數(shù)中。

Reduce函數(shù)中，第一步先是把各Map函數(shù)的輸出結(jié)果進行預處理包括合并與按一定次序排列，預處理結(jié)果的形式為m，list{v_m>對，第二步則使用Reduce函數(shù)將預處理結(jié)果作為輸入執(zhí)行相應的操作，最后記錄其運行結(jié)果out，v_out>對。

3 SMK-means算法的并行化實現(xiàn)方法

3.1 SMK-means算法的基本思路

K-means算法是一種經(jīng)典的文本聚類算法，初始聚簇中心選擇的好壞與否直接影響聚類的性能，也就是說初始聚簇中心與真實的聚簇中心越接近，K-means算法的聚類準確度就會越高。SMK-means算法是在傳統(tǒng)K-means算法的基礎上進行了改進，它通過選擇合適的初始中心點來獲得較為理想的分析結(jié)果。SMK-means算法的改進部分就是通過計算相似度矩陣選取初始聚簇中心，初始聚簇中心選擇的過程中用到的計算包括對矩陣的行求和與排序。相比較傳統(tǒng)K-means算法易受初始聚簇中心選擇的影響，導致多次運行的結(jié)果差別很大，即使結(jié)果簇相對比較稀疏，SMK-means算法也能得到較好的分析結(jié)果，同時還能夠降低噪聲和孤立點這類數(shù)據(jù)對分析結(jié)果造成的影響。

3.2 SMK-means算法的MapReduce并行化方法

SMK-means算法基于MapReduce的并行化步驟如下：

1）計算相似度矩陣，通過運算相似度矩陣選取K個初始聚簇中心。

2）將數(shù)據(jù)集解析為行的表達形式，然后由MapReduce模型完成對數(shù)據(jù)集的分割。

3）為各個數(shù)據(jù)點分配聚簇，該過程的并行化由Map函數(shù)執(zhí)行。Map函數(shù)的輸入輸出的數(shù)據(jù)格式分別為<序號，數(shù)據(jù)向量>和<聚簇標號，數(shù)據(jù)向量>，其中輸入的數(shù)據(jù)為全部數(shù)據(jù)點和上一輪迭代輸出的聚簇中心（或初始聚簇中心）。運行過程中Map函數(shù)通過計算數(shù)據(jù)點與聚簇中心之間相似度將相似度最大的聚簇設置為數(shù)據(jù)點的類別標簽，然后輸出計算結(jié)果。Map函數(shù)的偽代碼如圖1所示。

4）計算各個聚簇中數(shù)據(jù)點的均值來更新聚簇中心，該過程的并行化由Reduce函數(shù)執(zhí)行。Reduce函數(shù)輸入輸出的數(shù)據(jù)格式為<聚簇標號，{數(shù)據(jù)向量}>和<聚簇標號，聚簇中心向量>。在運行過程中Reduce函數(shù)把數(shù)據(jù)按照其被分配的聚簇進行整合，使得屬于同一聚簇的數(shù)據(jù)被同一個Reduce函數(shù)接收，然后聚簇中心更新為聚簇數(shù)據(jù)點的均值。Reduce函數(shù)的偽代碼如圖2所示。

5）計算更新前后聚簇中心的距離，用以確定算法結(jié)束與否。此過程只需由一個Reduce函數(shù)來執(zhí)行。運行過程中首先計算更新前后聚簇中心的距離，然后將此距離與閥值進行比較，當兩者的距離比閥值小時，則算法結(jié)束，否則轉(zhuǎn)回3。

4實驗與結(jié)果分析

在實驗過程中，本文所選用的數(shù)據(jù)集為北京大學的人民日報語料庫。

4.1 F值對比分析

為驗證MapReduce框架下SMK-means算法的仍能保持較高的聚類F值，將其與DE+K-means算法、Filtering算法、K-means算法和SMK-means算法做了比較。實驗中，隨機地從語料的娛樂類、體育類、文化類、科技類、經(jīng)濟類和政治類數(shù)據(jù)中各取20，000篇。實驗結(jié)果如表1所示。

表1的結(jié)果表明，并行化SMK-means算法的聚類F值明顯高于DE+K-means算法、和K-means算法的F值，與Filtering算法相比其F值也有一定程度的提高。更重要的是，經(jīng)過MapRe-duce分布模型并行化處理的SMK-means算法所獲得的F值與未經(jīng)過并行化處理的SMK-means算法的F值屬于同一個級別，差別很小，這就說明了經(jīng)過MapReduce分布模型并行化處理的SMK-means算法仍能保持較好的聚類性能。

4.2聚類時間開銷對比分析

為驗證MapReduce框架下SMK-means算法的運行效率得到了大幅度提高，將其與DE+K-means算法、Filtering算法、K-means算法和SMK-means算法做了比較。實驗結(jié)果如圖3所示。

圖3的結(jié)果表明，并行化的SMK-means算法的運行效率最快，F(xiàn)iltering算法具有最高的時間開銷，與SMK-means算法和DE+K-means算法相比，K-means算法的運行時間要短一些。由于DE+K-means算法、Filtering算法和SMK-means算法這三種算法均是在K-means算法的基礎上進行的改良，計算復雜度相應的增加，因此運行時間變長了。盡管SMK-means算法在提高聚類準確度的同時一定程度上降低了運行效率，但是經(jīng)過MapReduce分布模型并行化處理后大幅度縮短了運行時間，這就說明了經(jīng)過MapReduce分布模型并行化處理的SMK-means算法確實可以提升運行效率。

總之，對SMK-means算法進行MapReduce并行化處理是一種有效的方式，它在保持較高的聚類F值的同時還大幅度地提升了運行效率。

5結(jié)束語

為了提高基于相似度矩陣的K-Means算法（SMK-means）處理大數(shù)據(jù)的能力，本文對其進行了并行化處理。文中使用MapReduce分布式編程模型，并結(jié)合SMK-means算法自身的特點，對相應的Map函數(shù)和Reduce函數(shù)進行了設計。通過實驗證明了系統(tǒng)的有效性，對SMK-means算法的并行化處理是一種有效的方式。實驗結(jié)果也表明了它在保持較高的聚類F值的同時還大幅度地提升了運行效率。