• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    基于Spark的大規(guī)模文本k-means并行聚類算法

    2017-10-11 07:10:09滕家雨丁恩杰
    中文信息學(xué)報 2017年4期
    關(guān)鍵詞:內(nèi)存聚類向量

    劉 鵬, 滕家雨,丁恩杰,孟 磊

    (1. 中國礦業(yè)大學(xué) 物聯(lián)網(wǎng)(感知礦山)研究中心,江蘇 徐州 221008;2. 礦山互聯(lián)網(wǎng)應(yīng)用技術(shù)國家地方聯(lián)合工程實(shí)驗(yàn)室,江蘇 徐州 221008;3. 中國礦業(yè)大學(xué) 信息與電氣工程學(xué)院,江蘇 徐州 221116)

    基于Spark的大規(guī)模文本k-means并行聚類算法

    劉 鵬1,2, 滕家雨1,3,丁恩杰1,2,孟 磊1,2

    (1. 中國礦業(yè)大學(xué) 物聯(lián)網(wǎng)(感知礦山)研究中心,江蘇 徐州 221008;2. 礦山互聯(lián)網(wǎng)應(yīng)用技術(shù)國家地方聯(lián)合工程實(shí)驗(yàn)室,江蘇 徐州 221008;3. 中國礦業(yè)大學(xué) 信息與電氣工程學(xué)院,江蘇 徐州 221116)

    互聯(lián)網(wǎng)文本數(shù)據(jù)量的激增使得對其作聚類運(yùn)算的處理時間顯著加長,雖有研究者利用Hadoop架構(gòu)進(jìn)行了k-means并行化研究,但由于很難有效滿足k-means需要頻繁迭代的特點(diǎn),因此執(zhí)行效率仍然不能讓人滿意。該文研究提出了基于新一代并行計(jì)算系統(tǒng)Spark的k-means文本聚類并行化算法,利用RDD編程模型充分滿足了k-means頻繁迭代運(yùn)算的需求。實(shí)驗(yàn)結(jié)果表明,針對同一聚類文本大數(shù)據(jù)集和同樣的計(jì)算環(huán)境,基于Spark的k-means文本聚類并行算法在加速比、擴(kuò)展性等主要性能指標(biāo)上明顯優(yōu)于基于Hadoop的實(shí)現(xiàn),因此能更好地滿足大規(guī)模文本數(shù)據(jù)挖掘算法的需求。

    k-means;并行化;文本聚類;Spark;RDD;Hadoop;MapReduce

    Abstract: Due to sharp increase of internet texts, the processing of k-means on such data is incredibly lengthened. Some classic parallel architectures, such as Hadoop, have not improved the execution efficiency of K-means, because the frequent iteration in such algorithms is hard to be efficiently handled. This paper proposed a parallelization algorithm of k-means based on Spark. It makes full use of in-memory-computing RDD model of Spark so as to well meet the frequent iteration requirement of k-means. Experimental results show that k-means executes much more efficiently in Spark than in Hadoop on the same datasets and the same computing environments.

    Key words: k-means;parallelization;text clustering;Spark;RDD;Hadoop;MapReduce

    收稿日期: 2015-02-05 定稿日期: 2015-03-30

    基金項(xiàng)目: 國家自然科學(xué)基金(41302203)

    1 引言

    隨著互聯(lián)網(wǎng)信息量的迅猛增加,如何對海量網(wǎng)絡(luò)文本信息進(jìn)行有效處理及價值挖掘已成為當(dāng)今中文信息處理的研究熱點(diǎn)之一,大規(guī)模文本聚類便是其中一個重要的研究領(lǐng)域。由于在互聯(lián)網(wǎng)信息海洋中,人們不會事先對數(shù)據(jù)進(jìn)行類別標(biāo)注,也無法確定數(shù)據(jù)應(yīng)歸屬的類別總數(shù),這樣就很難采用基于類別標(biāo)注的挖掘算法(如支持向量機(jī))對數(shù)據(jù)進(jìn)行處理。而聚類技術(shù)[1]不需要知道數(shù)據(jù)的類別標(biāo)注,也不需要任何訓(xùn)練數(shù)據(jù),便可以直接對目標(biāo)數(shù)據(jù)集進(jìn)行挖掘處理,其應(yīng)用更加便捷、高效。在互聯(lián)網(wǎng)大規(guī)模信息挖掘處理中,聚類可應(yīng)用于文本語義分析、文檔相似性分析、語料分類分析及主題分析等多個領(lǐng)域[2-4],另外,在很多算法的預(yù)處理階段,例如文本分割及多文檔文摘抽取,聚類技術(shù)也可以發(fā)揮重要的作用。但是目前可用的聚類算法基本都僅適于處理小規(guī)模的數(shù)據(jù),而在當(dāng)今互聯(lián)網(wǎng)信息爆炸的背景下,網(wǎng)絡(luò)數(shù)據(jù)文檔數(shù)量呈指數(shù)性增長,文本特征空間的維度也急劇增大,這都會嚴(yán)重降低聚類算法的類別劃分能力,同時也大大延長了算法的運(yùn)行時間,這顯然不適合實(shí)際應(yīng)用。因此,如何能夠?qū)Υ笠?guī)模文本數(shù)據(jù)進(jìn)行快速、有效的并行聚類計(jì)算,將是一個很有價值的研究方向。

    作為傳統(tǒng)的并行計(jì)算方法,20世紀(jì)末出現(xiàn)的MPI(message passing interface)[5]、21世紀(jì)初出現(xiàn)的網(wǎng)格計(jì)算[6]等,存在開發(fā)復(fù)雜、擴(kuò)展性不好等問題,已無法滿足日益增長的互聯(lián)網(wǎng)大規(guī)模數(shù)據(jù)處理的需求。面對挑戰(zhàn),“云計(jì)算[7]” 應(yīng)運(yùn)而生,Map-Reduce(MR)即是其最受關(guān)注的關(guān)鍵技術(shù)之一。Map-Reduce是由Google公司開發(fā)的一個用于大規(guī)模數(shù)據(jù)處理的分布式計(jì)算模型[8-10],具有編程簡單、易于擴(kuò)展、容錯性好等特點(diǎn),極大地簡化了集群上的海量數(shù)據(jù)并行處理實(shí)現(xiàn)。除Google外,MapReduce已有多種實(shí)現(xiàn)版本,其中最經(jīng)典的是Hadoop[10],它是一個由Java語言編寫的開源分布式計(jì)算框架,提供了以MapReduce為核心的編程接口和分布式文件系統(tǒng)HDFS(Hadoop distributed file system),能夠處理多至百萬個節(jié)點(diǎn)和ZB量級的數(shù)據(jù)。

    但是越來越多的研究證明[11-12],Hadoop的MapReduce計(jì)算模型比較簡單,適合數(shù)據(jù)量大但核心計(jì)算并不復(fù)雜的處理作業(yè),而對于較復(fù)雜的計(jì)算模型,譬如遞歸、迭代、嵌套調(diào)用等,利用MapReduce實(shí)現(xiàn)不但編程復(fù)雜,而且處理效率也很難讓人滿意。下面以迭代計(jì)算為例說明MapReduce模型的局限性。

    目前為止,我們能看到的MapReduce版本實(shí)現(xiàn)都沒有針對迭代計(jì)算進(jìn)行相應(yīng)優(yōu)化,在運(yùn)行迭代型作業(yè)時,存在以下四個主要問題[12]:

    (1) 盡管每次迭代所進(jìn)行的操作都一樣,但每一次迭代都是作為獨(dú)立作業(yè)(job)重新進(jìn)行處理,需要重新初始化和讀寫、傳輸數(shù)據(jù),這會導(dǎo)致大量不必要的系統(tǒng)開銷。

    (2) 雖然大量數(shù)據(jù)在迭代循環(huán)時很可能是不變的,但在每次迭代時仍會被重新載入和處理,這將浪費(fèi)掉大量的I/O、CPU資源和網(wǎng)絡(luò)帶寬。

    (3) 每次迭代都需要一個額外的MapReduce Job作業(yè)來檢測迭代終止條件,這又會消耗掉額外的任務(wù)調(diào)度、磁盤數(shù)據(jù)讀取和網(wǎng)絡(luò)傳輸。

    (4) 必須在前一次迭代全部結(jié)束,輸出數(shù)據(jù)全部寫入分布式文件系統(tǒng),并完成迭代終止條件檢測之后,下一次迭代才可以開始,而下一次迭代又需要先從分布式文件系統(tǒng)讀取數(shù)據(jù),這使得數(shù)據(jù)的讀寫過于集中,而相對應(yīng)地,空閑時的系統(tǒng)I/O、CPU和網(wǎng)絡(luò)帶寬等資源則被浪費(fèi)掉了。

    因此,MapReduce在進(jìn)行迭代型數(shù)據(jù)處理時性能比較低下,而迭代計(jì)算在數(shù)據(jù)處理中是一類非常重要的應(yīng)用模型,尤其在數(shù)據(jù)挖掘、信息檢索、機(jī)器學(xué)習(xí)等領(lǐng)域,大量算法都是運(yùn)用多次迭代實(shí)現(xiàn)的[13]。作為主要創(chuàng)作動機(jī)之一,基于內(nèi)存計(jì)算的新一代并行計(jì)算框架Spark[14],力求能很好地解決此類頻繁迭代問題。本文提出了基于Spark的k-means本文聚類算法并行設(shè)計(jì)與實(shí)現(xiàn),并使用相同樣本集、計(jì)算環(huán)境進(jìn)行實(shí)驗(yàn),對比分析Hadoop和Spark環(huán)境下的并行k-means文本聚類算法執(zhí)行效率及性能差異,對并行聚類技術(shù)在大規(guī)模文本分類中的作用做了有益的探討。

    本文后續(xù)部分安排如下,首先介紹文本聚類整體流程及k-means串行算法,接著分別設(shè)計(jì)及實(shí)現(xiàn)了基于Hadoop和Spark的k-means并行化算法,最后通過實(shí)驗(yàn)在加速比、擴(kuò)展比等主要性能指標(biāo)上進(jìn)行比較并得出實(shí)驗(yàn)結(jié)論。

    2 文本聚類整體流程

    為了能夠?qū)ξ谋拘畔⑦M(jìn)行聚類分析,必須首先對非結(jié)構(gòu)化文本進(jìn)行預(yù)處理,包括分詞、去停用詞、詞頻統(tǒng)計(jì)、特征降維和構(gòu)建文本表示模型等步驟,需要量化為數(shù)值的形式才能便于計(jì)算機(jī)進(jìn)行聚類分析,整個文本聚類分析流程如圖1所示,這其中由于聚類分析需要頻繁迭代,因此會占據(jù)大部分處理時間,

    圖1 文本聚類分析整體流程

    所以本文的重點(diǎn)是研究如何通過并行處理提高聚類分析部分的效率。在此之前,先簡要介紹下預(yù)處理階段的工作內(nèi)容(本文文本聚類預(yù)處理使用的工具包為中科院計(jì)算所研發(fā)的ICTCLAS分詞系統(tǒng))。

    2.1 文本聚類預(yù)處理

    文本主要記錄和存儲文字信息,是非結(jié)構(gòu)化的數(shù)據(jù),不能直接對文本信息進(jìn)行數(shù)據(jù)挖掘處理,應(yīng)該對文本信息進(jìn)行預(yù)處理,最終把文本信息轉(zhuǎn)化為一種結(jié)構(gòu)化的形式(便于計(jì)算機(jī)處理),然后再對預(yù)處理數(shù)據(jù)進(jìn)行聚類。文本預(yù)處理是聚類分析的首要步驟,預(yù)處理的質(zhì)量直接決定著聚類分析的效果。預(yù)處理過程的一般步驟包括分詞、去停用詞、詞頻統(tǒng)計(jì)、特征選擇。

    預(yù)處理的第一個關(guān)鍵步驟就是分詞[15]。不同于英文文本,在中文文本中,詞與詞之間是連續(xù)的,沒有空格間隔,因此必須對文本進(jìn)行分詞處理。所謂分詞,就是將文檔按照詞的含義進(jìn)行切分。在文本信息處理的過程中,可以用字、詞或者詞組作為文本的特征項(xiàng)。但是用字作為特征項(xiàng)會導(dǎo)致特征向量維數(shù)龐大,并且字所包含的信息量有限。詞組雖然包含信息量多,但是在文本中出現(xiàn)的頻率極少,用詞組作為特征向量會導(dǎo)致特征向量稀少。因此,選用詞作為特征向量既能夠包含足夠的信息,又能夠得到較合適的特征維數(shù)。

    文本聚類中,從文本得到的單詞集還不能作為特征集來表示文本,因?yàn)樗谋炯黝愇谋局衅毡槌霈F(xiàn)的通用詞和弱詞性詞,這些停用詞幾乎出現(xiàn)在任何一個文本中,但是對表達(dá)文本內(nèi)容幾乎沒有任何貢獻(xiàn),這些詞更多的作用是在語法上,被稱為停用詞。因此,需要建立一個停用詞表,并按照此表從單詞集中過濾掉所有的停用詞,從而降低特征空間維數(shù),減少噪聲。

    2.2 文本表示

    文本是一種無結(jié)構(gòu)的數(shù)據(jù),要進(jìn)行聚類,必須把文本表示成為計(jì)算機(jī)能夠識別和處理的形式。本文采用最常用的向量空間模型(VSM)[16],向量的每一維由特征項(xiàng)及其權(quán)重組成,特征項(xiàng)的權(quán)重用TF-IDF[17-18]方法來計(jì)算:

    (1)

    其中,w(ti,d)為特征項(xiàng)ti在文檔d中的權(quán)重;tf(ti,d)為特征項(xiàng)ti在文檔d中的詞頻;N為訓(xùn)練文本的總數(shù);ni為訓(xùn)練文本集中出現(xiàn)特征項(xiàng)ti的文本數(shù),分母為歸一化因子,即文檔dj的向量化表示,為dj=(tj1:wj1,tj2:wj2,…,tji:wji,…,tjm:wjm),即tji表示第j個文檔的第i個特征項(xiàng),wji表示該特征項(xiàng)的權(quán)重,m表示向量中特征項(xiàng)的個數(shù)。

    3 串行k-means文本聚類算法

    串行k-means聚類算法[19]基本思想如下: 以空間中的k個點(diǎn)為聚類中心,對最靠近它們的對象歸類,具體計(jì)算過程通過迭代的方法,逐次更新各聚類中心的值,直到最后收斂得到最優(yōu)的聚類結(jié)果,其目的就是為了使簇內(nèi)數(shù)據(jù)對象之間的相似性盡可能大,而簇間數(shù)據(jù)對象的相似性盡可能小。在每次迭代后需驗(yàn)證聚類的準(zhǔn)則函數(shù)是否收斂來確定算法是否應(yīng)該結(jié)束,如果不收斂,就繼續(xù)對數(shù)據(jù)對象進(jìn)行聚類;否則,聚類完成,算法結(jié)束。

    運(yùn)用k-means算法進(jìn)行文本聚類,首先需要對文本建立文本表示模型,向量空間模型是一種常用的文本表示模型。VSM模型用向量表示文本,文本轉(zhuǎn)換成向量數(shù)據(jù),可以利用k-means算法實(shí)現(xiàn)文本聚類。算法具體描述如下:

    輸入: 文本向量集D={d1,d2,…,dn},聚類個數(shù)k

    輸出:k個聚類

    (1) 從文本向量集D中隨機(jī)選取k個向量作為k個聚類的初始中心;

    (2) 在第c次迭代中,對任意一個向量di,求其到k個中心的相似度,將di歸到最相似的類;

    (3) 利用均值方法更新該類的中心值;

    (4) 對所有的k個聚類中心,利用上述兩步的迭代更新后,求得式(4)的J值,若不再發(fā)生明顯變化,則判定收斂,迭代結(jié)束;或者達(dá)到設(shè)定的最大迭代次數(shù),迭代也結(jié)束。否則轉(zhuǎn)(2)繼續(xù)迭代。

    k-means算法用來計(jì)算文本向量相似度的標(biāo)準(zhǔn)通常是使用歐氏距離,其定義如下:

    (2)

    其中,x=(x1,x2,…,xp)和y=(y1,y2,…,yp)是數(shù)據(jù)集中兩個p維的數(shù)據(jù)對象。

    更新聚類中心的計(jì)算方法,定義如下:

    (3)

    其中,Ci表示某個簇,m表示屬于Ci簇的數(shù)據(jù)個數(shù)。

    評價k-means劃分聚類效果的聚類準(zhǔn)則函數(shù)J定義為:

    (4)

    4 基于Hadoop的k-means文本聚類算法并行化

    基于Hadoop的核心就是將串行的k-means任務(wù)通過MapReduce模型進(jìn)行并行化設(shè)計(jì),由于Hadoop沒有針對迭代計(jì)算作特殊優(yōu)化,在使用MapReduce模型求解問題時,運(yùn)行一趟MapReduce過程無法完成整個求解過程。將串行算法的每次迭代設(shè)計(jì)成一趟MapReduce過程,也就是一個k-means作業(yè)[20]。每次迭代完成樣本數(shù)據(jù)到聚類中心的計(jì)算及聚類中心的更新。聚類整體迭代過程中,需要進(jìn)行多次MapReduce過程,直到滿足迭代條件。

    圖2描述了MapReduce主程序首先從HDFS讀取數(shù)據(jù)集并進(jìn)行采樣隨機(jī)生成k個樣本作為初始聚類中心,之后啟動相應(yīng)的k-means作業(yè)。每次迭代計(jì)算過程包括Map和Reduce兩部分,Map執(zhí)行局部操作,進(jìn)行數(shù)據(jù)對象的本地局部劃分聚類,Reduce接收來自Map的中間結(jié)果,匯總操作執(zhí)行全局的聚類,計(jì)算并更新該類的聚類中心,具體實(shí)現(xiàn)如算法2-1所示。當(dāng)一次迭代計(jì)算完成后,根據(jù)當(dāng)前輸出結(jié)果執(zhí)行收斂條件判斷。如果聚類結(jié)果未達(dá)到收斂條件,Hadoop會再次啟動新的k-means作業(yè),把上一次MapReduce任務(wù)的輸出作為當(dāng)前任務(wù)的輸入,重復(fù)執(zhí)行,直到結(jié)果滿足收斂條件或者達(dá)到最大迭代次數(shù)為止[21]。

    圖2 基于Hadoop的k-means并行算法實(shí)現(xiàn)總流程圖

    算法2-1 k-means作業(yè)的MapReduce化算法

    Map部分

    輸入: 中心點(diǎn)列表,數(shù)據(jù)對象的偏移量,數(shù)據(jù)對象

    輸出: ,k1為點(diǎn)簇的索引值,v1為數(shù)據(jù)點(diǎn)的特征值

    FOR每個文本向量i=1,…,ndo:

    FOR每個聚類中心j=1,…,kdo:

    計(jì)算每個文本向量與每個聚類中心相似度;

    比較上述相似度;

    將此向量歸納到相似度高的那個聚類中心所屬的類;

    將<所屬類別,數(shù)據(jù)對象>寫入中間文件;

    Reduce部分

    輸入: ,k2為點(diǎn)簇的索引值,list[v2]為數(shù)據(jù)對象列表

    輸出: ,k3為點(diǎn)簇的索引值,v3為新的中心點(diǎn)

    FOR對于key相同的所有文本向量(它們屬于同一個簇):

    求所有文本向量的均值,得出新的聚類中心

    輸出新的聚類中心

    5 基于Spark的k-means文本聚類算法并行化

    5.1 Spark架構(gòu)和彈性分布式數(shù)據(jù)集RDD Spark由加州大學(xué)伯克利分校AMPLab開發(fā),主要目的是用來構(gòu)建大型的、低延遲的數(shù)據(jù)分析應(yīng)用程序,由于引進(jìn)了彈性分布式數(shù)據(jù)塊RDD(resilient distributed dataset)[22]的概念,Spark可在集群計(jì)算中將數(shù)據(jù)集分布式緩存在各節(jié)點(diǎn)內(nèi)存中,省去大量的磁盤IO操作,從而大大縮短訪問延遲。作為Spark架構(gòu)的核心機(jī)制,RDD是一種基于分布式內(nèi)存的并行數(shù)據(jù)結(jié)構(gòu),它能將用戶數(shù)據(jù)存儲在內(nèi)存中,并控制分區(qū)劃分以優(yōu)化數(shù)據(jù)分布。數(shù)據(jù)存儲在內(nèi)存中,尤其對于需要多次迭代使用的數(shù)據(jù),省去了多次載入到內(nèi)存和存儲到磁盤的過程,大大加快了處理速度。Spark支持RDD的顯式緩存(cache)及持久化(persistence)存儲,即在初次使用RDD時,可以將所需數(shù)據(jù)對象緩存在本地內(nèi)存,而且可以將RDD對象持久化到本地文件系統(tǒng)或HDFS中。

    Spark運(yùn)行架構(gòu)如圖3所示,在該圖中描述了當(dāng)一個應(yīng)用程序在Spark集群上運(yùn)行時的基本組成部分。驅(qū)動程序用來協(xié)調(diào)集群上任務(wù)執(zhí)行調(diào)度,可以與三類集群資源管理器(Standalone、Mesos或YARN)相連接,本文選擇的是Standalone模式,集群資源管理器的作用為在不同Spark應(yīng)用間分配資源。Spark在執(zhí)行程序時,需要將應(yīng)用代碼發(fā)送給工作節(jié)點(diǎn)的執(zhí)行器去執(zhí)行任務(wù),以盡可能實(shí)現(xiàn)數(shù)據(jù)的本地化計(jì)算[23]。

    圖3 Spark運(yùn)行架構(gòu)圖

    與上文所述的Hadoop處理迭代運(yùn)算的方式不同,利用新一代并行計(jì)算機(jī)架構(gòu)Spark實(shí)現(xiàn)k-means,只需將迭代計(jì)算的數(shù)據(jù)塊定義為RDD,以分區(qū)(partitions)的形式分布存儲在不同節(jié)點(diǎn)的內(nèi)存中,再由位于這些節(jié)點(diǎn)的任務(wù)針對本地內(nèi)存分區(qū)重復(fù)完成迭代計(jì)算即可,中間完全無需和磁盤進(jìn)行交互,從而大大加快執(zhí)行速度,這也是以RDD內(nèi)存計(jì)算為核心的Spark的最大優(yōu)勢。

    5.2 基于Spark的k-means文本聚類并行化設(shè)計(jì)

    利用Spark并行實(shí)現(xiàn)k-means,總體上也是采用“Map”和“Reduce”的思想,即在每次迭代中,先用“Map”計(jì)算所有樣本和中心點(diǎn)距離并歸類,再用“Reduce”分類求均值算得新的中心點(diǎn)。然而與Hadoop的MapReduce最大的不同是,Spark對所有中心點(diǎn)的所有次迭代運(yùn)算都在內(nèi)存中對RDD計(jì)算完成,中間不需要與磁盤交互,而Hadoop的這個過程則要與磁盤有(迭代次數(shù)×分類數(shù))次的交互[21]。

    基于Spark的k-means文本聚類在實(shí)現(xiàn)時,先從HDFS上讀取所有的數(shù)據(jù)(已經(jīng)預(yù)處理過的文件)并形成RDD對象,由于這些數(shù)據(jù)不只使用一次,所以可在本地緩存RDD數(shù)據(jù)以便下次直接使用。之后進(jìn)行Map操作,對本地局部數(shù)據(jù)按類劃分,Reduce操作匯總中間結(jié)果數(shù)據(jù),計(jì)算得到全局的聚類中心。聚類算法的并行化執(zhí)行由Spark框架自動完成,自動將數(shù)據(jù)集及執(zhí)行任務(wù)分配到不同工作節(jié)點(diǎn),并行執(zhí)行聚類計(jì)算,Spark并行化的核心就是使用RDD,算法在邏輯上與串行算法差不多。算法總流程如圖4所示。

    圖4 基于Spark的k-means算法總體流程圖

    5.3 基于Spark的k-means文本聚類算法并行化實(shí)現(xiàn) Spark實(shí)現(xiàn)k-means并行化算法如算法3-1所示,首先執(zhí)行Spark集群環(huán)境的初始化;從HDFS中載入原始數(shù)據(jù),創(chuàng)建形成Hadoop RDD對象,對RDD進(jìn)行Map生成新的RDD對象,并用cache操作將其緩存于各worker節(jié)點(diǎn)本地內(nèi)存;而后在各worker節(jié)點(diǎn)先執(zhí)行算法中(1)~(5),完成第一輪迭代,接著重復(fù)執(zhí)行(2)~(5),直到滿足收斂條件或者到達(dá)最大迭代次數(shù),聚類操作結(jié)束。

    算法3-1 基于Spark的k-means算法

    程序輸入: Context(arg0),Input(arg1),numSplits(arg2),k(arg3),convergeDist(arg4),MaxIter(arg5)。其中Context為Spark環(huán)境參數(shù),Input為數(shù)據(jù)集輸入路徑,numSplits為數(shù)據(jù)的分片數(shù), K為聚類個數(shù),convergeDist為聚類準(zhǔn)則值J,MaxIter為最大迭代次數(shù)

    程序輸出:k個聚類中心。核心步驟如下:

    (1) 隨機(jī)抽樣產(chǎn)生k個初始的聚類中心:

    o1~ok∈文檔向量集D

    (2) FOR j=1 tondo:

    計(jì)算所有的RDD文本向量與k個聚類中心的相似度d(xi,yj),并得出最近的聚類索引號,格式形如(id,(point,1))

    (3) FORi=1 tokdo:

    (5) untilJ不再發(fā)生明顯變化或者達(dá)到最大迭代次數(shù)

    Spark實(shí)現(xiàn)k-means并行化的代碼使用scala語言編寫,Scala語言表現(xiàn)力強(qiáng)大,代碼相比Java、C#等要簡潔許多[24]。算法3-1所用Scala主要代碼解釋如下:

    1. Spark集群環(huán)境的初始化

    1. val sc=new SparkContext(args(0), "SparkK-Means")

    2. 從HDFS讀入已處理過的文本向量

    2. val lines=sc.sequenceFile[Text,VectorWritable](args(1),args(2).toInt)

    3~5. 輸入?yún)?shù)賦值給相應(yīng)變量

    3. valK=arg(3)

    4. val convergeDist=arg(4)

    5. val MaxIter=arg(5)

    6. 將每個數(shù)據(jù)點(diǎn)RDD化

    6. val data=lines.map{ case (category,instances)=>

    (category.toString.split("/")(1),Vectors.sparse(instances.get.size,instances.get.all.asScala.map(_.get).zipWithIndex.map(e => (e._2,e._1)).filter(_._2!=0.0).toArray))}.cache()

    7. 隨機(jī)抽樣產(chǎn)生k個初始聚類中心

    7. varkPoints = data.takeSample(false,K, 42).map{ pair => pair._2}.toArray

    8~9. 聚類準(zhǔn)則比較變量和迭代次數(shù)中間變量的初始化

    8. vartempDist = 1.0

    9. var tempIter=0

    10. 實(shí)現(xiàn)算法3-1中(2)~(5)部分,為k-means核心代碼,具體如下:10.0 當(dāng)聚類準(zhǔn)則比較變量大于聚類準(zhǔn)則值,并且迭代次數(shù)不到最大迭代次數(shù)時,執(zhí)行循環(huán)內(nèi)容{10.1求數(shù)據(jù)的局部聚類,通過closestPoint函數(shù)求得文本向量p與哪個類中心相似度高,標(biāo)記所屬類別,每個點(diǎn)p映射成(id,(point,1))。10.2 pointStats對相同id的向量p進(jìn)行歸約求和,為(point特征值求和,point數(shù)量和)。10.3 newPoints是所求的新聚類中心點(diǎn),鍵值對形如(id,point特征值求和/ point數(shù)量和)。10.4 tempDist聚類準(zhǔn)則變量置零。10.5 新舊中心點(diǎn)的差平方和。10.6 更新聚類中心。10.7 已迭代次數(shù)更新。}

    10.0 while(tempDist>convergeDist&&tempIter

    {

    10.1 val closest = data.map (p => (closestPoint(p._2, kPoints), (p._2, 1)))

    10.2 val pointStats = closest.reduceByKey{case ((x1, y1), (x2, y2)) => (plus(x1 + x2), y1 + y2)}

    10.3 valnewPoints = pointStats.map {pair._1 =>(pair._2._1, scaleDivde(pair._2._1 / pair._2._2))}.collectAsMap()

    10.4 tempDist = 0.0

    10.5 for (i<- 0 until K){

    10.5.1 tempDist += kPoints(i).squaredDist(newPoints(i))}

    10.6 for (newP<- newPoints) {

    10.6.1 kPoints(newP._1) = newP._2}

    10.7 tempIter=tempIter+1

    }

    6 實(shí)驗(yàn)設(shè)計(jì)與分析

    本實(shí)驗(yàn)平臺的集群由一個控制節(jié)點(diǎn)(namenode)和十臺計(jì)算節(jié)點(diǎn)(datanode1~10)組成,所有節(jié)點(diǎn)配置都相同,有2核CPU(主頻: 1.86GHz)、4GB內(nèi)存和60GB硬盤,控制節(jié)點(diǎn)和計(jì)算節(jié)點(diǎn)間以千兆以太網(wǎng)互聯(lián)。Hadoop的版本為1.2.1,Spark的版本為0.8.1,Hadoop程序使用Java編寫,Java版本1.7,Spark程序使用Scala編寫,版本2.9.3。本文的語料庫采用的是搜狗實(shí)驗(yàn)室提供的中文語料庫SogouC,它包括九個文本類別集合: 財(cái)經(jīng),IT,健康,體育,旅游,教育,招聘,文化,軍事。數(shù)據(jù)集的規(guī)模如表1所示。

    表1 實(shí)驗(yàn)使用的數(shù)據(jù)集的規(guī)模

    實(shí)驗(yàn)分別在Hadoop和Spark集群平臺上進(jìn)行,共進(jìn)行了三類實(shí)驗(yàn):

    (1) 基于Spark平臺的并行k-means算法加速比測試;

    (2) 基于Spark平臺的并行k-means算法擴(kuò)展比測試;

    (3) 基于Spark與Hadoop平臺,從首次和后續(xù)迭代執(zhí)行時間來比較運(yùn)行效率。

    6.1 k-means算法的加速比分析

    加速比是指通過并行計(jì)算使運(yùn)行時間減少所獲得的性能提升,它是驗(yàn)證并行計(jì)算性能的一個重要指標(biāo),其計(jì)算公式為Sd=Ts/Td,其中Ts表示串行算法(即在單節(jié)點(diǎn)上)計(jì)算所消耗的時間,Td表示并行算法(即在d個相同節(jié)點(diǎn)上)計(jì)算所消耗的時間。加速比越大,表明并行計(jì)算消耗的相對時間越少,并行效率和性能提升越高。為了評估在Spark下的加速比,使用表1中DATA1、DATA2、DATA3、DATA4文本集,指定聚類的個數(shù)為10,分別測試這些文本集在單機(jī)環(huán)境下的執(zhí)行時間及Spark環(huán)境下的并行聚類算法的執(zhí)行時間。根據(jù)測試結(jié)果繪制如圖5所示的加速比曲線圖。從圖中可以看出,隨著計(jì)算節(jié)點(diǎn)從1增加到10,文本集為DATA1或DATA2的加速比接近于1,曲線持平;當(dāng)文本集為DATA3或DATA4時,算法的加速比都大于1。在數(shù)據(jù)量很小的情況下,加速比不明顯;但是隨著數(shù)據(jù)量的增加,在相同數(shù)據(jù)量的情況下加速比曲線隨著節(jié)點(diǎn)數(shù)增加逐漸上升。實(shí)驗(yàn)表明Spark下的k-means文本聚類具有較好的加速比[21]。

    圖5 Spark環(huán)境下的加速比

    6.2 k-means算法的擴(kuò)展比分析

    當(dāng)集群中的計(jì)算節(jié)點(diǎn)的數(shù)目不斷增加時,并行算法的加速比并不能無限地增大,此時僅用“加速比”已不能反映集群的利用率,因此引入了擴(kuò)展比的概念,即擴(kuò)展比表示并行算法執(zhí)行過程中集群的利用率情況,其公式為J=Sd/d,其中Sd表示算法的加速比,d表示計(jì)算節(jié)點(diǎn)數(shù)。圖6描述了在Spark環(huán)境下的并行聚類算法執(zhí)行的擴(kuò)展比,隨著數(shù)據(jù)量的增大和節(jié)點(diǎn)數(shù)量的增多,擴(kuò)展比逐漸下降并趨于穩(wěn)定,而且文本集DATA1和DATA2較DATA3和DATA4擴(kuò)展比曲線下降更快。這說明在Spark環(huán)境下,k-means文本聚類具有良好的擴(kuò)展性,相對來說,小數(shù)據(jù)集的擴(kuò)展性表現(xiàn)差一些[21]。

    圖6 Spark環(huán)境下的擴(kuò)展比

    6.3 Hadoop和Spark環(huán)境下k-means并行算法的比較 在本次實(shí)驗(yàn)中,選定聚類樣本為DATA4,設(shè)置計(jì)算節(jié)點(diǎn)數(shù)為10,指定的聚類個數(shù)為10,聚類的閾值J為0.5。我們將分別比較Hadoop和Spark平臺下算法執(zhí)行時每次迭代的執(zhí)行時間。實(shí)驗(yàn)時隨機(jī)選擇10個樣本向量作為初始聚類中心。因?yàn)閗-means聚類是典型的迭代算法,我們將第一次迭代(含從磁盤讀數(shù)據(jù)的開銷)和除第一次外所有迭代(在Spark環(huán)境下,只從內(nèi)存讀數(shù)據(jù);Hadoop下依然每次都要從磁盤讀數(shù)據(jù))的均值分開描述比較,以更清楚地展現(xiàn)Spark基于內(nèi)存計(jì)算的強(qiáng)大優(yōu)勢,實(shí)驗(yàn)結(jié)果如圖7所示。

    圖7 每次迭代時間比較

    在第一次迭代中,兩個系統(tǒng)都是從磁盤文件系統(tǒng)HDFS中讀取數(shù)據(jù),實(shí)驗(yàn)數(shù)據(jù)顯示Spark比Hadoop稍快,原因是Hadoop程序開始和終止的心跳機(jī)制開銷略大于Spark程序。

    除第一次迭代外其他所有迭代運(yùn)行時間的均值,Spark比第一次迭代執(zhí)行時間少了一半,而Hadoop與第一次迭代執(zhí)行時間相差不大。原因是Hadoop不支持?jǐn)?shù)據(jù)緩存及作業(yè)之間的數(shù)據(jù)共享,而k-means的每次迭代都以獨(dú)立作業(yè)的形態(tài)存在,因此每次迭代都需要訪問HDFS,將相關(guān)的數(shù)據(jù)集載入到本地內(nèi)存中;而Spark支持?jǐn)?shù)據(jù)的緩存,在首次迭代時將數(shù)據(jù)cache到內(nèi)存,再次迭代時可以直接從緩存中讀取數(shù)據(jù),從而大幅度減少了磁盤I/O操作的時間,而且節(jié)省了執(zhí)行器啟動任務(wù)的時間。因此在后續(xù)迭代過程中,Spark相比Hadoop環(huán)境下的迭代時間得到顯著縮減[21]。

    圖8給出了隨著計(jì)算節(jié)點(diǎn)的增加,Hadoop和Spark完成一次迭代的平均執(zhí)行時間(不含首次迭代)比較,從圖中可以看出,相比Hadoop,Spark的執(zhí)行效率得到了大幅度的提升。

    圖8 平均迭代時間比較

    7 結(jié)語

    基于內(nèi)存計(jì)算的新一代并行計(jì)算框架Spark被人寄予厚望,希望能針對Hadoop的弱點(diǎn),切實(shí)提高具有復(fù)雜計(jì)算模式的大數(shù)據(jù)文本處理效率。本文以具有頻繁迭代計(jì)算特點(diǎn)的k-means算法并行化為切入點(diǎn),基于Spark平臺,利用其以RDD為核心的內(nèi)存計(jì)算模型,設(shè)計(jì)并實(shí)現(xiàn)了并行化k-means算法。通過實(shí)驗(yàn)驗(yàn)證了基于Spark的應(yīng)用在處理需頻繁迭代的大規(guī)模文本數(shù)據(jù)計(jì)算時,具有優(yōu)良的加速比和擴(kuò)展比,與傳統(tǒng)大數(shù)據(jù)平臺Hadoop相比,處理效率得到顯著提升,因此適合未來大規(guī)模數(shù)據(jù)挖掘及其他需要頻繁迭代的數(shù)據(jù)處理工作。

    [1] 何婷婷,戴文華,焦翠珍.基于混合并行遺傳算法的文本聚類研究[J].中文信息學(xué)報, 2007,21(4): 55-60.

    [2] 陳德華, 韓忠明, 樂嘉錦.基于XML文檔相似性的構(gòu)件聚類分析[J].計(jì)算機(jī)工程與設(shè)計(jì), 2009,30(2): 507-510.

    [3] 袁冬.基于海量文本的語義構(gòu)建方法研究[D].中國海洋大學(xué)博士學(xué)位論文,2012.

    [4] 石晶,胡明, 戴國忠.基于小世界模型的中文文本主題分析[J].中文信息學(xué)報,2007,21(3): 69-74.

    [5] Quinn M J, 奎因, 文光, 等. MPI與OpenMP并行程序設(shè)計(jì): C語言版[M]. 清華大學(xué)出版社, 2004.

    [6] 趙念強(qiáng), 鞠時光. 網(wǎng)格計(jì)算及網(wǎng)格體系結(jié)構(gòu)研究綜述[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2006, 27(5): 728-730.

    [7] 陳康, 鄭緯民. 云計(jì)算: 系統(tǒng)實(shí)例與研究現(xiàn)狀[J]. Journal of Software, 2009, 20(5): 1337-1348.

    [8] Dean J, Ghemawat S. MapReduce: simplified data processing on large clusters [J]. Communications of the ACM, 2008, 51(1): 107-113.

    [9] 王凱. MapReduce集群多用戶作業(yè)調(diào)度方法的研究與實(shí)現(xiàn) [D]. 國防科學(xué)技術(shù)大學(xué)碩士學(xué)位論文, 2010.

    [10] 劉鵬. 實(shí)戰(zhàn) Hadoop: 開啟通向云計(jì)算的捷徑[M]. 北京: 電子工業(yè)出版社, 2011.

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

    [12] Srirama S N, Batrashev O, Jakovits P, et al. Scalability of parallel scientific applications on the cloud[J]. Scientific Programming, 2011, 19(2): 91-105.

    [13] Fox G C. Data intensive applications on clouds[C]//Proceedings of the 2nd International Workshop on Data Intensive Computing in the Clouds. ACM, 2011: 1-2.

    [14] Zaharia M, Chowdhury M, Franklin M J, et al. Spark: cluster computing with working sets[C]//Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing.2010: 10-10.

    [15] 黃昌寧, 趙海.中文分詞十年回顧[J].中文信息學(xué)報, 2007,21(3): 8-19.

    [16] G. Salton, et al.. Vector-space model for automatic indexing [J]. Communications of the Acm, 1975(18): 613-620.

    [17] 徐建民,王金化,馬偉瑜.利用本體關(guān)聯(lián)度改進(jìn)的TF-IDF特征詞提取方法[J].情報科學(xué),2011,29(2): 279-283.

    [18] 黃承慧,印鑒,侯昉. 一種結(jié)合詞項(xiàng)語義信息和TF-IDF方法的文本相似度量方法[J].計(jì)算機(jī)學(xué)報,2011,34(5): 856-864.

    [19] 韓曉紅, 胡彧. K-means 聚類算法的研究[J]. 太原理工大學(xué)學(xué)報, 2009,(3): 236-239.

    [20] 江小平, 李成華, 向文, 等. K-means聚類算法的MapReduce并行化實(shí)現(xiàn)[J]. 華中科技大學(xué)學(xué)報(自然科學(xué)版), 2011, 39(1): 120-124.

    [21] 滕家雨. 云框架下的文本挖掘算法并行化研究[D].中國礦業(yè)大學(xué)碩士學(xué)位論文, 2015.

    [22] Zaharia M, Chowdhury M, Das T, et al. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[C]//Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation. USENIX Association, 2012: 2-2.

    [23] Apache Spark. Spark [EB/OL]. http://spark.incubator.apache.org.html,2014-02-10.

    [24] Scala programming language [EB/OL]. http://www.scala-lang.org, 2014.

    劉鵬(1972—),博士,副教授,主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)及其并行化技術(shù)、大數(shù)據(jù)處理技術(shù)及其在礦山物聯(lián)網(wǎng)的應(yīng)用等。

    E-mail: liupeng@cumt.edu.cn

    滕家雨(1988—),碩士研究生,主要研究領(lǐng)域?yàn)椴⑿袡C(jī)器學(xué)習(xí)算法及其在大規(guī)模文本處理中的應(yīng)用。

    E-mail: 294315013@qq.com

    丁恩杰(1962—),通信作者,博士,教授,博士生導(dǎo)師,主要研究領(lǐng)域?yàn)榇髷?shù)據(jù)處理技術(shù)、礦山物聯(lián)網(wǎng)等。

    E-mail: enjied@cumt.edu.cn

    Parallel K-means Algorithm for Massive Texts on Spark

    LIU Peng1,2, TENG Jiayu1,3, DING Enjie1,2, MENG Lei1,2

    (1. Internet of Things Perception Mine Research Centre, China University of Mining and Technology, Xuzhou, Jiangsu 221008, China;2. National and Local Joint Engineering Laboratory of Internet Application Technology on Mine, Xuzhou, Jiangsu 221008, China;3. School of Information and Electrical Engineering, China University of Mining and Technology, Xuzhou, Jiangsu 221116,China)

    1003-0077(2017)04-0145-09

    TP311

    A

    猜你喜歡
    內(nèi)存聚類向量
    向量的分解
    聚焦“向量與三角”創(chuàng)新題
    “春夏秋冬”的內(nèi)存
    基于DBSACN聚類算法的XML文檔聚類
    電子測試(2017年15期)2017-12-18 07:19:27
    向量垂直在解析幾何中的應(yīng)用
    基于改進(jìn)的遺傳算法的模糊聚類算法
    向量五種“變身” 玩轉(zhuǎn)圓錐曲線
    一種層次初始的聚類個數(shù)自適應(yīng)的聚類方法研究
    自適應(yīng)確定K-means算法的聚類數(shù):以遙感圖像聚類為例
    基于內(nèi)存的地理信息訪問技術(shù)
    日土县| 阿拉善左旗| 获嘉县| 介休市| 辛集市| 芜湖县| 嵩明县| 江城| 上林县| 普宁市| 大竹县| 江西省| 九寨沟县| 广宁县| 威宁| 巩义市| 金昌市| 塘沽区| 荆州市| 广宗县| 宁乡县| 通州区| 南溪县| 芮城县| 基隆市| 台北市| 盐津县| 兴山县| 屯留县| 静海县| 玛沁县| 松潘县| 蓝田县| 许昌市| 阳泉市| 历史| 嘉黎县| 吕梁市| 昌宁县| 长葛市| 泰来县|