MapReduce模型下的模糊C均值算法研究

王永貴,李鴻緒,宋 曉

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

MapReduce模型下的模糊C均值算法研究

王永貴,李鴻緒,宋 曉

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

針對(duì)模糊C均值算法需要不斷迭代來計(jì)算樣本數(shù)據(jù)的隸屬度值以及聚類中心的特點(diǎn),利用MapReduce模型解決海量數(shù)據(jù)下的模糊C均值問題,進(jìn)而提出高效的模糊C均值算法。在Map階段和Reduce階段分別完成隸屬度和聚類中心的計(jì)算,每次迭代都需要啟動(dòng)一次完整的MapReduce執(zhí)行過程。通過多次迭代計(jì)算出隸屬度值以及聚類中心,并更新聚類中心文件,供下一輪作業(yè)使用,重復(fù)執(zhí)行這一過程直至得到最終聚類結(jié)果。實(shí)驗(yàn)結(jié)果表明,該算法能夠有效減少M(fèi)apReduce計(jì)算過程中的迭代次數(shù),從而提高整體執(zhí)行效率。

模糊C均值算法;MapReduce模型;海量數(shù)據(jù);高效;迭代

1 概述

模糊均值C(Fuzzy C-means,FCM)算法是由Dunn最先提出的,隨后被廣泛應(yīng)用于數(shù)據(jù)挖掘等領(lǐng)域。模糊C均值算法是聚類分析和模糊理論的結(jié)合體,聚類分析是對(duì)原有數(shù)據(jù)按照某種規(guī)律來進(jìn)行數(shù)據(jù)分類的一個(gè)過程,模糊理論是進(jìn)行描述和分析人類語言的模棱兩可的理論。模糊C均值在處理少量維度低的數(shù)據(jù)時(shí)是有效的[1],但是在處理大量的高維度數(shù)據(jù)時(shí),不能夠在有效的時(shí)間內(nèi)計(jì)算出聚類結(jié)果[2]。隨著網(wǎng)絡(luò)信息技術(shù)的發(fā)展,人們可以采集并利用的數(shù)據(jù)越來越多,因此,如何處理海量數(shù)據(jù)下的模糊C均值是迫切需要解決的問題。Google提出的MapReduce[3]并行編程框架,在處理海量數(shù)據(jù)問題上具有顯著的優(yōu)勢(shì)[4],該模型具有良好的擴(kuò)展性及容錯(cuò)性[5],能夠滿足人們對(duì)海量數(shù)據(jù)處理的需要[6],在大數(shù)據(jù)處理中起著重要的作用[7]。Apache推出的Hadoop平臺(tái)[8]實(shí)現(xiàn)了MapReduce模型,其將Hadoop分布式文件系統(tǒng)(Hadoop Distributed File System,HDFS)和MapReduce模型有效的結(jié)合為大數(shù)據(jù)處理提供了方便的平臺(tái)[9],并且該平臺(tái)得到了廣泛的推廣和應(yīng)用[10]。因此,可以通過改進(jìn)傳統(tǒng)的模糊C均值算法,使其適應(yīng)MapReduce并行編程模型,從而能夠有效地解決海量數(shù)據(jù)下的模糊C均值問題。文獻(xiàn)[1]中針對(duì)模糊C均值算法需要不斷迭代來計(jì)算樣本數(shù)據(jù)的隸屬度值以及聚類中心的特點(diǎn),提出了利用MapReduce模型來解決海量數(shù)據(jù)下的模糊C均值問題,Map階段完成隸屬度的計(jì)算, Reduce階段完成聚類中心的計(jì)算,每一次迭代需要啟動(dòng)一次MapReduce執(zhí)行過程。

本文針對(duì)文獻(xiàn)[1]中提出的MapReduce模型下的模糊均值C算法進(jìn)行改進(jìn),使其減少M(fèi)apReduce計(jì)算過程中的迭代次數(shù),提高算法的整體執(zhí)行效率。

2 模糊C均值算法

模糊均值C算法:{di,i=1,2,…,n}作為原始數(shù)據(jù)樣本的集合[11],其中,di為第i個(gè)樣本數(shù)據(jù);n代表原始數(shù)據(jù)樣本的總個(gè)數(shù),n≥2;聚類類別個(gè)數(shù)c, 2≤c≤n;{li,i=1,2,…,n}是聚類中心集合,li為第i個(gè)聚類中心的值,n≥1;χj(di)代表第i個(gè)樣本數(shù)據(jù)對(duì)于第j類隸屬度的函數(shù)[12];Tf為聚類損失函數(shù),可通過隸屬度函數(shù)表示為:

其中,m＞1是一個(gè)常數(shù),控制聚類結(jié)果的模糊程度。

最小化式(1)得到的損失函數(shù)與隸屬度函數(shù)的定義有密切關(guān)系,不同的隸屬度函數(shù)定義會(huì)得到不同的損失函數(shù)。模糊C均值要求樣本數(shù)據(jù)對(duì)于每個(gè)聚類中心的隸屬度值的和為1,表示為:

通過式(1)與式(2)結(jié)合求損失函數(shù)的極小值,令Tf對(duì)li和χj(di)的偏導(dǎo)數(shù)為0,可得必要條件如下:

模糊C均值算法的核心是用迭代的方式求解式(3)和式(4),具體步驟如下[13]:

步驟1 初始化聚類中心個(gè)數(shù)c和模糊程度常數(shù)m;

步驟2 初始化聚類中心li和迭代停止閾值ε;

步驟3 將當(dāng)前的聚類中心帶入式(4)求得隸屬度值;

步驟4 將當(dāng)前的隸屬度值帶入式(3)計(jì)算并更新的聚類中心,若計(jì)算得到的隸屬度值穩(wěn)定,相鄰的2次隸屬度值之差小于ε則停止迭代,算法結(jié)束,否則,返回步驟3繼續(xù)執(zhí)行。

3 MapReduce模型

MapReduce是目前較為流行的用于大數(shù)據(jù)處理的并行編程模型,Hadoop開源平臺(tái)實(shí)現(xiàn)了這一模型,并得到了廣泛應(yīng)用[14]。圖1為 MapReduce模型,模型中包含了1個(gè)Master節(jié)點(diǎn)和若干個(gè)Slave節(jié)點(diǎn),其中,Master節(jié)點(diǎn)負(fù)責(zé)控制及調(diào)度MapReduce的整個(gè)運(yùn)作流程;Master節(jié)點(diǎn)根據(jù)用戶提出的需求,將任務(wù)分配給Slave節(jié)點(diǎn)。Slave節(jié)點(diǎn)分為2個(gè)主要的執(zhí)行過程,分別是Map階段和Reduce階段,Slave節(jié)點(diǎn)接收到任務(wù)后,首先讀取原始數(shù)據(jù),原始數(shù)據(jù)被劃分為若干個(gè)數(shù)據(jù)分片,并最終以＜key,value＞鍵值對(duì)的形式由Map函數(shù)讀入,Map函數(shù)通過預(yù)設(shè)的函數(shù)來處理輸入數(shù)據(jù),同樣產(chǎn)生＜key,value＞鍵值對(duì)形式的輸出,供Reduce階段使用,Reduce函數(shù)接收到Map的中間結(jié)果后,將最終處理得到的結(jié)果輸出。Slave節(jié)點(diǎn)在執(zhí)行任務(wù)的過程中會(huì)不斷地與Master節(jié)點(diǎn)進(jìn)行交互,Master節(jié)點(diǎn)則根據(jù)當(dāng)前系統(tǒng)的運(yùn)行狀況來調(diào)節(jié)各個(gè)Slave節(jié)點(diǎn),使得任務(wù)能夠順利完成。關(guān)于MapReduce的研究目前主要在MapReduce模型的改進(jìn)和通過MapReduce模型處理具體問題這2個(gè)方面,文獻(xiàn)[15]提出了Hadoop++,通過改進(jìn)自定義函數(shù)來提高M(jìn)apReduce的性能。文獻(xiàn)[16]提出HaLoop,該版本是對(duì)Hadoop的改進(jìn),使其能有效地處理迭代的問題。盡管MapReduce已經(jīng)成為熱點(diǎn)研究對(duì)象,但是有關(guān)利用MapReduce框架處理具體問題,還有待于繼續(xù)學(xué)習(xí)和探討。

圖1 MapReduce模型

4 MapReduce模型下的模糊C均值算法

高效迭代模糊C均值算法的原理為:模糊均值C算法要求多次迭代計(jì)算出隸屬度值以及聚類中心,因此每一次迭代需要一個(gè)完整的MapReduce計(jì)算過程來實(shí)現(xiàn),Map讀取待分類的數(shù)據(jù)以及各個(gè)聚類中心的值,Map任務(wù)根據(jù)讀入的帶分類數(shù)據(jù)以及各個(gè)聚類中心,計(jì)算出新的隸屬度值,并通過該隸屬度值計(jì)算出新的聚類中心值,將新的聚類中心值更新到聚類中心文件中,當(dāng)其他Map任務(wù)進(jìn)行計(jì)算時(shí),直接讀取更新后的聚類中心文件,當(dāng)所有Map任務(wù)完成計(jì)算后,將隸屬度值作為輸出結(jié)果傳遞給Reduce任務(wù),Reduce任務(wù)根據(jù)待分類的數(shù)據(jù)以及Map輸出的隸屬度值,計(jì)算出新的聚類中心,并更新到聚類中心文件,供下一輪作業(yè)使用,重復(fù)執(zhí)行這一過程直到得到最后的聚類結(jié)果。

圖2描述了高效迭代模糊C均值算法的基本原理。

圖2 高效迭代模糊C均值算法流程

4.1 Map階段的設(shè)計(jì)

Map階段具體設(shè)計(jì)如下:

步驟1 Map函數(shù)以待分類數(shù)據(jù)集合DATA_LIST作為輸入,形式為(key,value),其中,key為數(shù)據(jù)的行偏移量;value為行記錄,并讀取聚類中心集合CLUSTER_LIST,Map函數(shù)根據(jù)集合DATA_LIST和CLUSTER_LIST按照式(4)計(jì)算出點(diǎn)的隸屬度值,并做好相應(yīng)的類別標(biāo)記。

步驟2 判斷新計(jì)算出的中心與當(dāng)前的聚類中心之間的差值是否小于指定的閾值,若小于閾值范圍則執(zhí)行步驟6,否則執(zhí)行步驟3。

步驟3 判斷該Map階段是否為第1輪作業(yè)的執(zhí)行過程,若是則執(zhí)行步驟5,否則執(zhí)行步驟4。

步驟4 將步驟1計(jì)算出的隸屬度值帶入式(3)得到新的聚類集合,并更新CLUSTER_LIST。

步驟5 輸出隸屬度值,供Reduce階段使用,輸出形式為(CLUNUMi,(LINNUM,MEi)),其中,CLUNUMi為第i個(gè)聚類中心的序號(hào);LINNUM為當(dāng)前數(shù)據(jù)的行偏移量;MEi為當(dāng)前數(shù)據(jù)到第i個(gè)聚類中心的隸屬度值,本輪Map任務(wù)結(jié)束。

步驟6 輸出中間結(jié)果(CLUNUMi,(LINNUM,DATA)),DATA為當(dāng)前的數(shù)據(jù)記錄值。

4.2 Reduce階段的設(shè)計(jì)

Reduce階段具體設(shè)計(jì)如下:

步驟1 判斷新計(jì)算出的中心與當(dāng)前的聚類中心之間的差值是否小于指定的閾值,若小于閾值范圍則執(zhí)行步驟4,否則執(zhí)行步驟2。

步驟2 Reduce函數(shù)以Map輸出的中間結(jié)果作為輸入,即Reduce的輸入為(CLUNUMi,(LINNUM,MEi)),CLUNUMi相同的記錄會(huì)被分配到同一個(gè)Reduce任務(wù),Reduce函數(shù)根據(jù)每一個(gè)數(shù)據(jù)對(duì)各個(gè)聚類中心的隸屬度值來計(jì)算出新的聚類中心。

步驟3 輸出聚類結(jié)果,輸出形式為(CLUNUMi,CLUSTERi),CLUSTERi為第i個(gè)聚類中心的值,更新聚類中心集合,本輪任務(wù)結(jié)束,啟動(dòng)下一輪MapReduce任務(wù)。

步驟4 Reduce函數(shù)以Map輸出的中間結(jié)果作為輸入,即Reduce的輸入為(CLUNUMi,(LINNUM,DATA)),計(jì)算最后的聚類結(jié)果并輸出,輸出的形式為(CLUNUMi,DATALISTi),DATALISTi為屬于第i類聚類的所有數(shù)據(jù)集合,任務(wù)結(jié)束。

5 實(shí)驗(yàn)與結(jié)果分析

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

本文實(shí)驗(yàn)環(huán)境是由9臺(tái)高速千兆網(wǎng)絡(luò)連接的PC機(jī)組成,每個(gè)PC機(jī)的配置為Intel Core Duo 2.10 GHz CPU,內(nèi)存為4 GB,操作系統(tǒng)為Ubuntu 12.10。其中,一臺(tái)機(jī)器作為Master節(jié)點(diǎn);其他8臺(tái)機(jī)器作為Slave節(jié)點(diǎn),圖3為集群配置。本文采用的Hadoop平臺(tái)版本為1.1.2,代碼編譯采用JDK1.6。

圖3 集群配置

實(shí)驗(yàn)所用到的數(shù)據(jù)集由文獻(xiàn)[7]中的標(biāo)準(zhǔn)數(shù)據(jù)生成工具生成,實(shí)驗(yàn)數(shù)據(jù)的條數(shù)從2×105條～10×105條不等,實(shí)驗(yàn)數(shù)據(jù)的維度從2～8不等,要求生成8個(gè)～12個(gè)聚類類別,初始聚類中心值隨機(jī)產(chǎn)生。在實(shí)驗(yàn)中,首先用文獻(xiàn)[1]提出的基于MapReduce的并行模糊 C均值算法(BC)與 Intel Parallel Amplifier下多核平臺(tái)上的并行模糊 C均值算法(IC)進(jìn)行對(duì)比,然后用本文提出的MapReduce模型下的高效模糊C均值算法(HC)與BC算法進(jìn)行對(duì)比,具體工作如下:

(1)算法性能隨著數(shù)據(jù)維度變化情況;

(2)算法性能隨著數(shù)據(jù)量的變化情況;

(3)算法性能隨著任務(wù)節(jié)點(diǎn)數(shù)量的變化情況。

5.2 不同模型下的FCM算法比較

在本文實(shí)驗(yàn)中,對(duì)IC,BC以及HC 3種算法執(zhí)行效率進(jìn)行比較,由于IC算法是將多核技術(shù)實(shí)現(xiàn)到模糊C均值算法的并行化中,因此實(shí)驗(yàn)采用一臺(tái)雙核機(jī)器進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)數(shù)據(jù)量從1×103～10×103不等,數(shù)據(jù)維度為4。表1為實(shí)驗(yàn)的結(jié)果,從表中可以看出隨著數(shù)據(jù)量的增加,BC和HC算法的執(zhí)行效率明顯高于IC的執(zhí)行效率,因此可以得出MapReduce模型下的模糊C均值算法具有更高的執(zhí)行效率。

表1 模糊C均值算法運(yùn)行時(shí)間比較 s

5.3 FCM算法性能隨數(shù)據(jù)維度的變化情況

圖4表示模糊C均值算法的性能隨數(shù)據(jù)維度變化的情況,實(shí)驗(yàn)數(shù)據(jù)條數(shù)為10×105,任務(wù)節(jié)點(diǎn)數(shù)為8。圖4表示模糊C均值算法運(yùn)行時(shí)間的測(cè)試結(jié)果。可以看出,2個(gè)模糊C均值算法的執(zhí)行時(shí)間在低維度時(shí)相差不大,在數(shù)據(jù)維度達(dá)到8時(shí),算法執(zhí)行時(shí)間差距明顯增大,原因是隨著數(shù)據(jù)維度的增大,算法執(zhí)行時(shí)的計(jì)算量開始增大,迭代次數(shù)也隨之增加,而本文提出的HC算法能夠有效降低迭代次數(shù),所以執(zhí)行效率相對(duì)較高。

圖4 模糊C算法運(yùn)行時(shí)間與數(shù)據(jù)維度的關(guān)系

5.4 FCM算法性能隨數(shù)據(jù)量的變化情況

圖5表示模糊C均值算法性能隨著數(shù)據(jù)量變化的情況,實(shí)驗(yàn)的數(shù)據(jù)維度為8,任務(wù)節(jié)點(diǎn)數(shù)為8,可以看出,隨著數(shù)據(jù)量的增大,模糊C均值算法的運(yùn)行時(shí)間增加,因?yàn)殡S著數(shù)據(jù)量的增加,算法的計(jì)算量開始增大,迭代次數(shù)開始增多,使得算法的開銷增大,本文實(shí)驗(yàn)的數(shù)據(jù)量是從2×105～10×105,能夠說明算法對(duì)海量數(shù)據(jù)處理的能力?？梢钥闯?BC算法的運(yùn)行時(shí)間高于本文的HC算法,原因是本文的HC算法通過Map階段計(jì)算結(jié)果的回帶有效地降低了算法的整體迭代次數(shù),從而提高了算法的執(zhí)行效率。

圖5 模糊C算法運(yùn)行時(shí)間與數(shù)據(jù)量的關(guān)系

5.5 FCM算法性能隨任務(wù)節(jié)點(diǎn)數(shù)量的變化情況

圖6表示模糊C均值算法的性能與任務(wù)節(jié)點(diǎn)數(shù)變化的關(guān)系,實(shí)驗(yàn)的數(shù)據(jù)條數(shù)為10×105,數(shù)據(jù)維度為2?？梢缘贸?隨著任務(wù)節(jié)點(diǎn)數(shù)量的增加,2個(gè)模糊C均值算法的運(yùn)行時(shí)間都呈現(xiàn)下降的趨勢(shì),因?yàn)殡S著任務(wù)節(jié)點(diǎn)數(shù)量的增加,系統(tǒng)的并行處理能力隨之增強(qiáng),所以處理相同的數(shù)據(jù)其所消耗的時(shí)間也越來越少。

圖6 模糊C均值算法運(yùn)行時(shí)間與節(jié)點(diǎn)數(shù)的關(guān)系

本文算法在Map任務(wù)階段需要根據(jù)隸屬度值計(jì)算出新的聚類中心,并更新到聚類中心文件中,供其他的Map任務(wù)使用,在此階段會(huì)有部分提前運(yùn)行的Map任務(wù)未能接收到更新后的聚類中心文件,隨著Map任務(wù)節(jié)點(diǎn)的數(shù)量增大,同時(shí)開始的Map進(jìn)程個(gè)數(shù)將增大,因此更多的Map進(jìn)程將不能獲得更新后的聚類中心,但通過實(shí)驗(yàn)比較,如圖6所示,本文算法仍具有較高的效率,該情況不會(huì)影響算法的整體執(zhí)行效率。

6 結(jié)束語

本文針對(duì)如何利用MapReduce模型實(shí)現(xiàn)海量數(shù)據(jù)下的模糊C均值算法進(jìn)行研究。分析了文獻(xiàn)[1]提出的基于MapReduce的并行模糊C均值算法的不足并對(duì)其進(jìn)行改進(jìn),進(jìn)而提出MapReduce模型下的高效模糊C均值算法,通過實(shí)驗(yàn)對(duì)比可知,本文提出的算法能夠更有效地解決海量數(shù)據(jù)下的模糊C均值問題,具有較高的準(zhǔn)確性和可用性。

[1] 虞倩倩,戴月明.基于MapReduce的并行模糊C均值算法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(14):133-137,151.

[2] 胡 磊,牛秦洲,陳 艷.模糊C均值與支持向量機(jī)相結(jié)合的增強(qiáng)聚類算法[J].計(jì)算機(jī)應(yīng)用,2013,33 (4):991-993.

[3] Highland F,Stephenson J.Fitting the Problem to the Paradigm:Algorithm Characteristics Required for Effective Use of MapReduce[J].Procedia Computer Science,2012,12:212-217.

[4] Polo J,CarreraD.Performance-driven Task Coscheduling for MapReduce Environments[C]//Proc.of IEEE Network Operations and Management Symposium. [S.l.]:IEEE Press,2010:373-380.

[5] Marozzo F,Talia D,Trunfio P.P2P-MapReduce:Parallel Data Processing in Dynamic Cloud Environments[J]. Journal of Computer and System Sciences,2011,78(5): 1382-1402.

[6] 李建江,崔 健,王 聃,等.MapReduce并行編程模型研究綜述[J].電子學(xué)報(bào),2011,39(11):2635-2642.

[7] 林 彬,李?yuàn)檴?廖湘科,等 .Seadown:一種異構(gòu)MapReduce集群中面向SLA的能耗管理方法[J].計(jì)算機(jī)學(xué)報(bào),2013,36(5):977-987.

[8] 趙彥榮,王偉平,孟 丹,等.基于Hadoop的高效連接查詢處理算法CHMJ[J].軟件學(xué)報(bào),2012,23(8): 2032-2041.

[9] Shafer J,Rixner S,Cox A L.The Hadoop Distributed Filesystem:Balancing Portability and Performance[C]// Proc.of 2010 IEEE International Symposium on Performance Analysis of Systems&Software.Washington D.C., USA:IEEE Computer Society,2010:122-133.

[10] 廖 彬,于 炯,張 陶,等.基于分布式文件系統(tǒng)HDFS的節(jié)能算法[J].計(jì)算機(jī)學(xué)報(bào),2013,36(5): 1047-1064.

[11] 王 駿,王士同.基于混合距離學(xué)習(xí)的雙指數(shù)模糊C均值算法[J].軟件學(xué)報(bào),2010,21(8):1878-1888.

[12] 肖立中,邵志清,馬漢華,等.網(wǎng)絡(luò)入侵檢測(cè)中的自動(dòng)決定聚類數(shù)算法[J].軟件學(xué)報(bào),2008,19(8): 2140-2148.

[13] 武小紅,周建江.可能性模糊C-均值聚類新算法[J].電子學(xué)報(bào),2008,36(10):1996-2000.

[14] 欒亞建,黃翀民,龔高晟,等.Hadoop平臺(tái)的性能優(yōu)化研究[J].計(jì)算機(jī)工程,2010,36(4):262-264.

[15] Dittrich J,Quiane R J A,Jindal A,et al.Hadoop++: Making a Yellow Elephant Run Like a Cheetah(Without It Even Noticing)[J].VLDB Endowment,2010,3(1/ 2):518-529.

[16] Bu Y,Howe B,Balazinska M,et al.HaLoop:Efficient It Erative Data Processing on Large Clusters[C]//Proc.of the 36th International Conference on Very Large Data Bases.Singapore:[s.n.],2010:285-296.

編輯 陸燕菲

Research on Fuzzy C-means Algorithm on MapReduce Model

WANG Yong-gui,LI Hong-xu,SONG Xiao
(College of Software,Liaoning Technical University,Huludao 125105,China)

Fuzzy C-means(FCM)algorithm requires constant iteration to calculate the characteristics of the membership value of the sample data and cluster center,using MapReduce model to solve the FCM under massive data.Map stage calculates membership degree,and Reduce stage completes computing cluster center.Each iteration needs to start a MapReduce implementation process.Through multiple iterations,it calculates the value of membership and cluster center, and updates cluster center file for the use of next round job.Repeat this process until get the final clustering results. Experimental results show that the algorithm can effectively reduce the number of iterations during the calculation and improve the overall efficiency of the implementation.

Fuzzy C-means(FCM)algorithm;MapReduce model;mass data;high efficiency;iteration

1000-3428(2014)10-0047-05

A

TP391.41

10.3969/j.issn.1000-3428.2014.10.010

國(guó)家自然科學(xué)基金資助項(xiàng)目(60903082);遼寧省教育廳基金資助項(xiàng)目(L2012113)。

王永貴(1967-),男,教授、碩士,主研方向:云計(jì)算,綠色計(jì)算,數(shù)據(jù)挖掘;李鴻緒、宋 曉,碩士研究生。

2013-09-29

2013-11-29E-mail:theone_theone@163.com

中文引用格式:王永貴,李鴻緒,宋 曉.MapReduce模型下的模糊C均值算法研究[J].計(jì)算機(jī)工程,2014, 40(10):47-51.

英文引用格式:Wang Yonggui,Li Hongxu,Song Xiao.Research on Fuzzy C-means Algorithm on MapReduce Model[J]. Computer Engineering,2014,40(10):47-51.