一種改進(jìn)的可并行的K-medoids聚類算法

馬曉慧

（山西大學(xué)商務(wù)學(xué)院，太原　030031）

一種改進(jìn)的可并行的K-medoids聚類算法

馬曉慧

（山西大學(xué)商務(wù)學(xué)院，太原030031）

針對K-medoids算法中初始聚類中心的結(jié)點(diǎn)的選取的隨機(jī)性導(dǎo)致影響聚類結(jié)果質(zhì)量的問題，采用標(biāo)簽共現(xiàn)原則對該算法進(jìn)行改進(jìn)。根據(jù)標(biāo)簽共現(xiàn)頻率和相似度先對標(biāo)簽進(jìn)行聚類，根據(jù)標(biāo)簽聚類結(jié)果，選取K個由其代表的資源作為聚類初始中心結(jié)點(diǎn)。通過聚類中心的優(yōu)化設(shè)置，降低了抽樣選取的隨機(jī)性。最后采用MapReduce框架對其進(jìn)行并行化，以豆瓣圖書的標(biāo)簽數(shù)據(jù)為應(yīng)用背景進(jìn)行實(shí)驗，驗證了算法的實(shí)用性。

MapReduce；K-medoids；Hadoop

0　引 言

隨著大數(shù)據(jù)時代的來臨，相伴而生的信息技術(shù)、云計算等技術(shù)的蓬勃興起，從海量的數(shù)據(jù)中精準(zhǔn)高效地提取挖掘出有用的信息，即已成為倍受各方矚目和關(guān)注的一個熱點(diǎn)課題［1-2］。聚類是一種無監(jiān)督的學(xué)習(xí)過程，可將給定數(shù)據(jù)集合劃分成若干個簇，以簇內(nèi)數(shù)據(jù)相似度高，簇間相似度低為聚類目標(biāo)。自聚類概念提出以來，已經(jīng)產(chǎn)生了諸如劃分聚類、譜聚類、層次聚類、模糊聚類等眾多算法。其中，K均值作為經(jīng)典聚類算法，則在生物信息學(xué)、圖像處理、興趣推薦等眾多領(lǐng)域獲得了廣泛應(yīng)用。但是，已有研究證明該聚類算法也存在一定問題，諸如聚類結(jié)果可能出現(xiàn)局部最優(yōu)而非全局最優(yōu)、迭代次數(shù)過高等。

面對復(fù)雜多變、以指數(shù)級別增長的大規(guī)模數(shù)據(jù)，傳統(tǒng)的聚類算法已經(jīng)在效率上遭遇瓶頸，存在著伸縮性與擴(kuò)展性較差等問題，無法滿足時下計算的性能效果要求［3］。在新的數(shù)據(jù)生產(chǎn)模式下，研究高端完善、適應(yīng)性強(qiáng)的海量數(shù)據(jù)聚類算法即已突顯其現(xiàn)實(shí)重要性。同時，針對并行計算的快速發(fā)展，在其中關(guān)于并行計算編程模型的研發(fā)提出則為問題解決提供了新的有益思路和有利支持。

1　相關(guān)背景

1.1MapReduce

Hadoop是專為分布式計算和分布式存儲而設(shè)計生成的本文算法使用歐幾里得距離衡量結(jié)點(diǎn)間距離，數(shù)學(xué)計算一個運(yùn)行大規(guī)模數(shù)據(jù)的軟件平臺，是Apache的一個使用Java實(shí)現(xiàn)的開源框架。HDFS和MapReduce是Hadoop的兩大核心。具體地，MapReduce是谷歌提出的一種編程模型，可以用來對海量數(shù)據(jù)調(diào)用完成并行計算。MapReduce將輸入數(shù)據(jù)轉(zhuǎn)成輸出數(shù)據(jù)，”Map”和”Reduce”的概念來自于函數(shù)式編程語言。映射對輸入的每條數(shù)據(jù)使用一個函數(shù)變換來創(chuàng)建一個輸出列表，元數(shù)據(jù)列表不會改變。化簡接受數(shù)據(jù)并聚合起來返回輸出值。Map函數(shù)和Reduce函數(shù)只接收Key-Value對，而不接收整型、String型的數(shù)值。有相同鍵值的數(shù)值都將傳入同一個Reduce函數(shù)實(shí)現(xiàn)自動匯總。MapReduce的工作流程如圖1所示［4］。

1.2一種改進(jìn)的K-medoids聚類算法

K-medoids聚類算法的基本思想是，給定節(jié)點(diǎn)集V，V=｛v1，v2，…，vn｝為n個結(jié)點(diǎn)的集合，其中vi=｛vi1，vi2，vi3，…，vip｝為p維數(shù)據(jù)點(diǎn)，找到k個初始結(jié)點(diǎn)作為聚類中心，判斷其他結(jié)點(diǎn)到各中心距離，將其分配到對應(yīng)類中。得到R= V′1，V′2，…，V′K，其中?Vi′，Vj′∈V，i≠j，Vi′∩Vj′=?，使得每個數(shù)據(jù)點(diǎn)vi（0≤i≤n）和其最近聚類中心的距離平方和J最小。此時，J可稱為目標(biāo)函數(shù)，數(shù)學(xué)描述可如式（1）所示。即如公式（2）所示。

其中，x=｛x1，x2，x3，…，xp｝，y=｛y1，y2，y3，…，yp｝是集合V中的p維數(shù)據(jù)點(diǎn)。

圖1　MapReduce流程圖Fig.1 Flow chart of MapReduce

綜上研究可知，初始聚類中心的結(jié)點(diǎn)選取是隨機(jī)的，有較大的盲目性，取值對聚類結(jié)果質(zhì)量影響很大，容易導(dǎo)致算法陷入局部最優(yōu)或分類準(zhǔn)確率下降等問題。針對此類問題，本文擬采用標(biāo)簽共現(xiàn)原則對該算法提出設(shè)計改進(jìn)。事實(shí)上，在協(xié)同標(biāo)記系統(tǒng)中會大量出現(xiàn)用不同標(biāo)簽標(biāo)記相同資源的現(xiàn)象，文獻(xiàn)［5］指出如果用戶使用不同標(biāo)簽來標(biāo)記相同的資源，則標(biāo)簽間一定存在著語義相關(guān)性，文獻(xiàn)［6］提出了一種基于標(biāo)簽共現(xiàn)的聚類算法來生成標(biāo)簽聚類簇。如果在同一個聚類中結(jié)點(diǎn)屬性相似度高且結(jié)構(gòu)緊密，不同聚類中結(jié)點(diǎn)屬性值差異性大，則稱為理想聚類效果［7］。本文提出的算法在對結(jié)點(diǎn)劃分的過程中，應(yīng)用了2個劃分原則［8］。原則設(shè)定可表述如下：

原則1：如果2個結(jié)點(diǎn)的屬性標(biāo)簽描述一致且同處于同一標(biāo)簽簇中，則2個結(jié)點(diǎn)應(yīng)劃分為同一結(jié)點(diǎn)簇。

原則2：如果2個結(jié)點(diǎn)的大部分鄰居結(jié)點(diǎn)相同，則這2個結(jié)點(diǎn)應(yīng)劃分為同一結(jié)點(diǎn)簇。

在此基礎(chǔ)上，根據(jù)標(biāo)簽共現(xiàn)頻率和相似度先對標(biāo)簽進(jìn)行聚類，根據(jù)不同的標(biāo)簽聚類選取K個由其代表的資源作為聚類初始中心結(jié)點(diǎn)。通過聚類中心的優(yōu)化設(shè)置，降低了抽樣選取的隨機(jī)性。

定義1（共同標(biāo)注矩陣） 如表1所示，Um×m是一個共同標(biāo)注矩陣，fij表示標(biāo)簽ti和tj共同出現(xiàn)過的頻率。頻率越高，則標(biāo)簽ti和tj相似度就越高。

研究中，利用公式（3）來計算2個標(biāo)簽的共現(xiàn)頻率，其中，w（ti，tj）代表標(biāo)簽ti和tj共同出現(xiàn)的次數(shù)。

表1　標(biāo)簽共同標(biāo)注矩陣Um×mTab.1 Tag co-occurrence matrix Um×m

至此，本文研究提出了改進(jìn)的K-medoids聚類算法1。算法內(nèi)容描述如下：

算法1 改進(jìn)的K-medoids聚類算法

輸入：帶屬性標(biāo)簽的資源節(jié)點(diǎn)集，V=｛v1，v2，…，vn｝為n個結(jié)點(diǎn)的集合，A=｛a1，a2，…，am｝為結(jié)點(diǎn)vi的m個標(biāo)簽的集合。

輸出：k個聚類結(jié)果，R=V′1，V′2，…，V′k其中，?V′i，V′j∈V，i≠j，V′i∩V′j=?。

1：數(shù)據(jù)準(zhǔn)備，標(biāo)簽預(yù)處理，根據(jù)公式（2）計算標(biāo)簽的共現(xiàn)頻率。設(shè)定閾值，將標(biāo)簽劃分為k個標(biāo)簽簇。

2：根據(jù)標(biāo)簽簇選擇k個資源結(jié)點(diǎn)作為初始聚類中心，并對k個結(jié)點(diǎn)進(jìn)行順序編號，記做（u1，u2，…，uk）。

3：根據(jù)公式（2）計算其余數(shù)據(jù)點(diǎn)與選定的k個初始聚類中心的距離，并將其劃分到對應(yīng)的最短距離類中。

4：由公式（1），得到當(dāng)前目標(biāo)函數(shù)Ec[9]值。

5：在上次的聚類結(jié)果中，順序選擇一個非中心數(shù)據(jù)點(diǎn)，重新計算目標(biāo)函數(shù)E［9］。

6：根據(jù)計算結(jié)果對類中心進(jìn)行更新，得到k個新類。

7：循環(huán)執(zhí)行步驟3～6，得到k個聚類結(jié)果，R=V′1，V′2，…，V′k。

8：結(jié)束。

2　基于并行框架的K-medoids聚類算法實(shí)現(xiàn)

對聚類算法的并行處理中，首先在HDFS上部署可以由集群中機(jī)器訪問的初始化k個類中心。在K-medoids算法中，每個資源節(jié)點(diǎn)和類中心的距離計算過程是獨(dú)立于其他資源結(jié)點(diǎn)的，不存在依賴關(guān)系。因此，在MapReduce框架下，各個資源節(jié)點(diǎn)和k個類中心距離的計算過程可以并行發(fā)生、且實(shí)現(xiàn)。基于這一思想，將算法1通過并行化得到算法2，并行算法描述如下。

算法2 改進(jìn)的可并行的K-medoids聚類算法

輸入：帶屬性標(biāo)簽的資源節(jié)點(diǎn)集，V=｛v1，v2，…，vn｝為n個結(jié)點(diǎn)的集合，A=｛a1，a2，…，am｝為結(jié)點(diǎn)vi的m個標(biāo)簽的集合。

輸出：k個聚類結(jié)果，R=V′1，V′2，…，V′k。其中，?V′i，V′j∈V，i≠j，V′i∩V′j=?。

1：數(shù)據(jù)準(zhǔn)備，標(biāo)簽預(yù)處理，根據(jù)公式（2）計算標(biāo)簽的共現(xiàn)頻率。設(shè)定閾值，將標(biāo)簽劃分為k個標(biāo)簽簇。

2：根據(jù)標(biāo)簽簇選擇k個資源結(jié)點(diǎn)作為初始聚類中心，并對k個結(jié)點(diǎn)進(jìn)行順序編號，記做（u1，u2，…，uk）。

3：Map函數(shù)將步驟2中輸出的k個結(jié)點(diǎn)作為K-medoids的初始聚類中心，結(jié)點(diǎn)表示形式為＜key，value＞，value為p維屬性結(jié)點(diǎn)形式。對于每條記錄，計算和其距離最小的聚類中心并做歸屬新類別標(biāo)記。Map的輸出結(jié)果＜key，value＞形為＜聚類類別，｛屬性向量｝＞。

4：Reduce函數(shù)接收Map函數(shù)的輸入，將同一key值下的數(shù)據(jù)點(diǎn)合并，計算Key均值并將計算結(jié)果輸出［10］。

5：結(jié)束。

3　實(shí)驗和結(jié)果

3.1實(shí)驗環(huán)境搭建

實(shí)驗平臺采用虛擬機(jī)形式，使用VMWare8.0.2和Ubuntu10.04，虛擬出4臺設(shè)備搭建Hadoop集群。其中一臺作為Master主節(jié)點(diǎn)（即NameNode和Job-Tracker），另外3臺作為slave節(jié)點(diǎn)（即DataNode或Task-Tracker），Hadoop版本為1.0.3、JDK1.6，用Java實(shí)現(xiàn)算法。

3.2實(shí)驗結(jié)果分析

如式（4）所示，加速比S是衡量并行算法性能的一個重要指標(biāo)。其中，Ts為算法串行運(yùn)行時間，Tp為算法并行運(yùn)行時間。加速比越大，效率越高。

實(shí)驗采用數(shù)據(jù)集使用Python爬取的豆瓣圖書及標(biāo)簽數(shù)據(jù)。數(shù)據(jù)集按大小劃分，DS1取5 000條，DS2取20 000條，DS3取50 000條，在這3組數(shù)據(jù)集上做聚類分析，將4個計算節(jié)點(diǎn)逐一加入計算，運(yùn)行時間對比如表2所示，加速比測試圖如圖2所示。由表2和圖2可看出，數(shù)據(jù)量較小時并行效果并不明顯，因為小數(shù)據(jù)量的實(shí)際計算時間占比有限［11］。隨著數(shù)據(jù)集規(guī)模增大，算法加速比隨著節(jié)點(diǎn)數(shù)增加而線性增加，性能則趨于提升和完善。

圖2　加速比測試結(jié)果Fig.2 Result of the speed-up ratio test

表2　算法運(yùn)行時間對比Tab.2 Comparison of the algorithm’s running time

［1］劉智慧，張泉靈.大數(shù)據(jù)技術(shù)研究綜述［J］.浙江大學(xué)學(xué)報（工學(xué)版），2014，48（6）：957-972.

［2］陳吉榮，樂嘉錦.基于Hadoop生態(tài)系統(tǒng)的大數(shù)據(jù)解決方案綜述［J］.計算機(jī)工程與科學(xué)，2013，35（10）：25-35.

［3］李榴，唐九陽，葛斌，等.K-DmeansWM：一種基于P2P網(wǎng)絡(luò)的分布式聚類算法［J］.計算機(jī)科學(xué)，2010，37（1）：39-41.

［4］劉剛.Hadoop應(yīng)用開發(fā)技術(shù)詳解［M］.北京：機(jī)械工業(yè)出版社，2014：130-192.

［5］MICHLMAYR E，CAYZER S.Learning user profiles from tagging data and leveraging them for personalized information access［C］// Proceedings of the Workshop on Tagging and Metadata for Social Information Organization.Banff，Canada：［S.l.］，2007：1-7.

［6］王萍，張際平.一種社會性標(biāo)簽聚類算法［J］.計算機(jī)應(yīng)用與軟件，2010，27（2）：126-129.

［7］吳燁，鐘志農(nóng)，熊偉，等.一種高效的屬性圖聚類方法［J］.計算機(jī)學(xué)報，2013，36（8）：1704-1713.

［8］RAGHAVAN U，ALBERT R，KUMARA S.Near linear time algorithm to detect community structures in large-scale networks［J］.Physical Review E，2007，76（3）：36-106.

［9］金冉.面向大規(guī)模數(shù)據(jù)的聚類算法研究及應(yīng)用［D］.上海：東華大學(xué)，2015：14-20.

［10］毛典輝.基于MapReduce的Canopy-Kmeans改進(jìn)算法［J］.計算機(jī)工程與應(yīng)用，2012，48（27）：22-26，68.

［11］周婷，張君瑛，羅成.基于Hadoop的K-means聚類算法的實(shí)現(xiàn)［J］.計算機(jī)技術(shù)與發(fā)展，2013，23（7）：18-21.

An improved parallel K-medoids clustering algorithm

MA Xiaohui
（Business College，Shanxi University，Taiyuan 030031，China）

The K-medoids algorithm suffered from one problem which the quality of clustering results was sensitive to the initial cluster centers selection.The paper improves the algorithm using the principle of the tag co-occurrence.According to the tag co-occurrence frequency and similarity，clustering is carried out on the tags，and K resources are selected as the initial clustering center nodes on the basis of different tag cluster.After that，the paper reduces the randomness of sampling selection by optimizing the clustering center. Furthermore，MapReduce framework is adopted to carry out the parallel algorithm.Finally through the experiment with the application background of Douban books，the experimental result verifies the practicability of the algorithm.

MapReduce；K-medoids；Hadoop

TP391

A

2095-2163（2016）03-0100-03

2016-05-31

2014年省科技廳基礎(chǔ)研究項目（2014011018-1）；2015年學(xué)院科研項目（2015009）。

馬曉慧（1982-），女，碩士，講師，主要研究方向：計算機(jī)應(yīng)用技術(shù)、信息檢索、并行算法。