Hadoop 下并行化實(shí)現(xiàn)文本聚類的優(yōu)化算法?

王 輝 潘俊輝 Marius.Petrescu 王浩暢 張 強(qiáng)

（1.東北石油大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 大慶 163318）（2.普羅萊斯蒂石油天然氣大學(xué) 什蒂 100680）

1 引言

目前互聯(lián)網(wǎng)上產(chǎn)生了海量的數(shù)據(jù)，而單機(jī)串行處理海量數(shù)據(jù)時(shí)存在瓶頸，因此使用云計(jì)算、大數(shù)據(jù)對海量數(shù)據(jù)進(jìn)行挖掘的技術(shù)不斷涌現(xiàn)［1］。文本聚類可將相似的文本進(jìn)行歸類處理，提取出文本中的關(guān)鍵信息，該技術(shù)目前被廣泛地應(yīng)用在眾多領(lǐng)域［2］。針對目前互聯(lián)網(wǎng)上的海量數(shù)據(jù)，采用Hadoop對海量數(shù)據(jù)并行化實(shí)現(xiàn)文本聚類可有效地解決單機(jī)處理數(shù)據(jù)效率低的缺點(diǎn)。

目前，國內(nèi)外的一些學(xué)者對文本聚類的算法進(jìn)行了研究。國內(nèi)的胥桂仙等人重點(diǎn)對中文文本挖掘中的特征表示及聚類方法進(jìn)行了相應(yīng)的研究和改進(jìn)［3~4］；而趙慶等利用Hadoop 云計(jì)算平臺(tái)實(shí)現(xiàn)了K-means 聚類算法［5］；還有一些學(xué)者將聚類算法移植到了MapReduce 下進(jìn)行了設(shè)計(jì)和實(shí)現(xiàn)［6~7］；國外的Yoon提出了一種使用k-均值聚類方法測量數(shù)據(jù)異常點(diǎn)的檢測方法［8~9］；為了確定K-means 算法中的K 個(gè)初始值，消除其敏感性，一些學(xué)者提出了改進(jìn)的K-means 算法從而快速定位最優(yōu)初始聚類數(shù)值［10］。

本文針對K-means 聚類算法存在初始中心選取不當(dāng)導(dǎo)致運(yùn)行不穩(wěn)定的缺點(diǎn)以及單機(jī)串行編程對海量數(shù)據(jù)聚類效率低的問題，提出了一種Ha?doop 平臺(tái)下并行化實(shí)現(xiàn)文本聚類的優(yōu)化算法。該算法首先通過自定義的Mapper 和Reducer 任務(wù)對文本向量化過程進(jìn)行了并行化的實(shí)現(xiàn)，然后采用基于密度和最大最小距離的算法選取初始質(zhì)心作為K-means算法的初始中心，并將該優(yōu)化方法應(yīng)用到K-means 算法中，最后基于MapReduce 框架設(shè)計(jì)Mapper 和Reducer 各階段實(shí)現(xiàn)對文本的并行聚類。文中在最后通過搭建的Hadoop 集群對數(shù)據(jù)進(jìn)行測試，實(shí)驗(yàn)結(jié)果表明優(yōu)化的文本聚類并行算法在聚類效率和聚類質(zhì)量上均有較大的提高。

2 Hadoop平臺(tái)及文本聚類

2.1 Hadoop平臺(tái)

Hadoop 平 臺(tái) 由Apache Software Foundation 公司正式引入后迅速成為大數(shù)據(jù)分析處理的領(lǐng)先平臺(tái)。該平臺(tái)具有兩大核心架構(gòu)，分別是底層存儲(chǔ)系統(tǒng)HDFS和上層應(yīng)用MapReduce編程框架［11］。

2.1.1 HDFS

HDFS是一種分布式文件系統(tǒng)，以分布式的形式將劃分的數(shù)據(jù)塊存儲(chǔ)到多節(jié)點(diǎn)中。HDFS中的主節(jié)點(diǎn)負(fù)責(zé)分布式文件系統(tǒng)的命名空間，在其中保存了兩個(gè)核心的數(shù)據(jù)結(jié)構(gòu)FsImage 和EditLog。從節(jié)點(diǎn)則是HDFS 的Slaver，其主要負(fù)責(zé)數(shù)據(jù)的存儲(chǔ)和讀取［12］。

2.1.2 MapReduce

MapReduce核心是Map函數(shù)和Reduce函數(shù)［13］。Map 函數(shù)可將輸入數(shù)據(jù)以的形式切分成獨(dú)立的小數(shù)據(jù)塊，并以的形式輸出同時(shí)提供給Reduce 函數(shù)；Reduce 函數(shù)接收到Map處理的中間結(jié)果后，將相同的鍵值進(jìn)行合并，最后輸出結(jié)果并寫入到底層分布式文件系統(tǒng)［14］。

2.2 文本聚類

文本聚類是指將無序的對象作為輸入，使用相似性度量函數(shù)計(jì)算未知類別文本的相似性，輸出則為相似性文本組成的簇集［15］。其聚類過程采用數(shù)學(xué)形式表示為設(shè)文本數(shù)據(jù)集：D={d1,d2,…di,…,dn}，di為數(shù)據(jù)集中的文本，n 為總文本數(shù)，聚類之后得到的簇集為E={e1,e2,…,ej…,ek}，ej為相似文本聚成的簇，k為聚類個(gè)數(shù)。當(dāng)滿足條件?di(di?D),?ej(ej?E),di?ej，將語料庫D分為k個(gè)簇，使其滿足如下公式：，且ei∩ej=?。

文本聚類的過程包括四個(gè)步驟，第一步采用分詞、去噪的方法對文本進(jìn)行預(yù)處理；第二步依據(jù)頻率選取文本中的關(guān)鍵詞完成對文本特征的提取；第三步將文本由自然語言文字進(jìn)行文本向量化；最后一步使用聚類算法進(jìn)行文本的相似度計(jì)算最終實(shí)現(xiàn)聚類。

3 Hadoop 平臺(tái)下并行化實(shí)現(xiàn)文本聚類的優(yōu)化算法

3.1 文本向量化并行設(shè)計(jì)

網(wǎng)頁文本經(jīng)預(yù)處理后，通過對得到的特征賦予權(quán)值，可建立以特征和權(quán)值為基礎(chǔ)的多維空間坐標(biāo)系，在多維空間中，對網(wǎng)頁文本進(jìn)行的操作可轉(zhuǎn)換為對向量進(jìn)行的運(yùn)算。當(dāng)數(shù)據(jù)量較大時(shí)，會(huì)隨著文本向量的建立而增加向量空間的維度，進(jìn)而導(dǎo)致計(jì)算量增加嚴(yán)重時(shí)造成機(jī)器跌宕。因此針對MapRe?duce并行處理大數(shù)據(jù)的優(yōu)勢，可在進(jìn)行文本聚類時(shí)將聚類中的每個(gè)步驟基于MapReduce并行計(jì)算，即將文本向量化的過程分成四個(gè)MapReduce任務(wù)，分別用來實(shí)現(xiàn)文本預(yù)處理、特征的選取、特征的TF-IDF值的計(jì)算和建立文本向量。

本節(jié)主要介紹如何對文本向量化過程進(jìn)行并行化的設(shè)計(jì)，從而得到所需的文本向量，圖1 給出了文本向量化過程的實(shí)現(xiàn)框架。計(jì)算特征的TF-IDF 值需計(jì)算四個(gè)參數(shù)：count(dj) 、count(ti,dj)、N和count(ti_in_dj)。N是文本數(shù)，其余三個(gè)參數(shù)需通過三個(gè)MapReduce Job計(jì)算。

圖1 文本向量化過程的實(shí)現(xiàn)框架

框架圖中的MapReduce Job1 的工作是基于MapReduce 使用分詞器對文本進(jìn)行分詞和去停用詞等文本的預(yù)處理，并計(jì)算特征在文本中出現(xiàn)的次數(shù)。它的Mapper 階段，map 函數(shù)會(huì)以的形式輸入，并行執(zhí)行分詞，過濾停用詞的操作，然后以作為中間結(jié)果。它的Re?ducer階段，會(huì)以作為輸入，然后并行統(tǒng)計(jì)出特征在同一文本中出現(xiàn)的次數(shù)，記做count(ti,dj)，則Reducer 階段的輸出為。

MapReduce Job2 的工作是計(jì)算特征的TF。Mapper 階段，map 函數(shù)會(huì)以的形式作為輸入，然后指定分隔符對字符串進(jìn)行分割，并行轉(zhuǎn)換鍵值對之間的對應(yīng)關(guān)系，然后以作為中間結(jié)果。Reducer 階段則通過將相同文本編號(hào)的值相加，計(jì)算出文本具有的總特征數(shù)count(dj)，然后結(jié)合Job1 中計(jì)算得到的count(ti,dj)，并行計(jì)算得到特征TF，則Reducer階段的輸出記做。

MapReduce Job3 的工作是并行計(jì)算出每個(gè)特征的TF-IDF 值。Mpper 階段以Job2 的輸出作為輸入，其中tfij=count(ti,dj)/count(dj)，然后通過轉(zhuǎn)換鍵值對的形式分離特征和docID 得到該階段的輸出。Reduc?er 階段首先統(tǒng)計(jì)出具有相同特征的文本個(gè)數(shù)count(ti_in_d j)，然后計(jì)算特征頻率DF，判斷DF是否在給定的閾值區(qū)間內(nèi)，如不在區(qū)間內(nèi)進(jìn)行刪除，對在區(qū)間內(nèi)的特征根據(jù)公式TF-IDF=tfij*idfj計(jì)算特征的TF-IDF 值，Reducer 階段的輸出為，并將結(jié)果寫入HDFS中。

前述三個(gè)MapReduce Job 完成后，接下來就是并行實(shí)現(xiàn)文本向量化。文本向量化由MapReduce Job4 通過將MapReduce Job3 的輸出轉(zhuǎn)換為向量實(shí)現(xiàn)。Mpper 階段的map 函數(shù)會(huì)以Job3 的輸出作為輸入，通過轉(zhuǎn)換以的形式輸出。而Reducer 階段會(huì)對特征重新排序，合成文本向量，以形式輸出。以上的四個(gè)MapReduce Job并行處理文本數(shù)據(jù)集，得到文本向量。

3.2 優(yōu)化K-means并行算法

3.1 節(jié)通過四個(gè)MapReduce Job 并行實(shí)現(xiàn)將文本轉(zhuǎn)換為文本向量后，本節(jié)的工作就是對3.1 節(jié)得到的文本向量采用優(yōu)化算法并行進(jìn)行文本聚類。本節(jié)為滿足聚類算法有較好的效率和準(zhǔn)確率分別從并行隨機(jī)采樣、并行合并數(shù)據(jù)對象和數(shù)據(jù)對象聚類并行化三個(gè)方面對K-means算法進(jìn)行了優(yōu)化，最后將優(yōu)化的算法基于Hadoop 進(jìn)行了并行實(shí)現(xiàn)。圖2給出了優(yōu)化K-means算法的MapReduce并行框架圖。

圖2 改進(jìn)K-means算法的MapReduce框架圖

3.2.1 并行隨機(jī)采樣

本文為提高隨機(jī)采樣的效率，設(shè)計(jì)了基于Ma?pReduce 進(jìn)行隨機(jī)采樣的方法。基于MapReduce的并行隨機(jī)采樣通過兩個(gè)階段實(shí)現(xiàn)。

并行隨機(jī)采樣的第一個(gè)階段多次對樣本集進(jìn)行并行采樣。Mapper 的map 會(huì)以作為輸入從總文本n中抽取符合要求的S（S=n/m，m為map 任務(wù)的數(shù)量）個(gè)向量并以的形式輸出。Reducer會(huì)以Mapper的輸出為輸入，然后將所有輸入都為null的向量均歸入同一Reduce 中，執(zhí)行最大最小距離算法后得到聚類中心并以作為reduce的輸出。對上述的方法需要多次進(jìn)行抽樣。另一個(gè)階段則通過計(jì)算點(diǎn)的密度參數(shù)來評估候選聚類中心之間是否相鄰，對于相鄰的向量進(jìn)行合并，然后計(jì)算出每個(gè)合并類的平均值，作為最終選取的初始聚類中心，由于計(jì)算密度參數(shù)時(shí)需要半徑R的值，因此該作業(yè)中的Reducer階段需要計(jì)算得到候選聚類中心點(diǎn)之間的平均距離用aveDis 表示，最終要以<-1，ave?Dis>作為輸出。

3.2.2 并行合并數(shù)據(jù)對象

經(jīng)過并行隨機(jī)采樣得到候選聚類中心后，由于從整體上來說，這些候選的聚類中心可能存在距離較近的對象，因此應(yīng)從候選聚類中心找出高密度鄰域內(nèi)的對象并進(jìn)行合并。并行合并候選聚類中心則由該過程中的MapReduce Job2具體實(shí)現(xiàn)。

MapReduce Job2 的Mapper 階段，會(huì)以并行隨機(jī)采樣得到的輸出和<-1，aveDis>作為輸入，首先判斷鍵是否為-1，如為-1 計(jì)算得到候選聚類中心的均值用R表示，如鍵為null 需要計(jì)算出所有候選聚類中心點(diǎn)之間的距離，得到距離矩陣用M表示，然后采用如下方法初始化M。

將M中的分量依次與半徑R進(jìn)行比較，若大于R，值為1，否則值為0。然后計(jì)算各對象的密度參數(shù)并按照從大到小的順序排序，遍歷矩陣M，合并對象，直到所有對象歸入到不同簇內(nèi)，最后得到MapReduce Job2 的Reduce 的 輸 出 為，可為K-means 聚類算法的初始中心點(diǎn)，其中IniVec 表示簇中心，CluID 則為簇中心對應(yīng)的文本編號(hào)。

3.2.3 數(shù)據(jù)對象聚類并行化

通過并行隨機(jī)采樣和并行合并數(shù)據(jù)對象操作后，會(huì)得到初始聚類中心，得到的初始中心不再由K-means 隨機(jī)選取。圖2 中的MapReduce Job3 的工作就是計(jì)算文本集中其他文本向量到已經(jīng)選擇的聚類中心的距離，然后根據(jù)計(jì)算選擇距離聚類中心最小的文本向量歸類到所在的簇中，同時(shí)計(jì)算簇均值，得到新的聚類中心。

MapReduce Job3 的Mapper 的map 函數(shù)的輸入為MapReduce Job2 的輸出，計(jì)算獲得各個(gè)聚類中心距離并根據(jù)距離最近原則將文本向量歸入到相應(yīng)的簇內(nèi)，然后以得到的相似度小的向量構(gòu)成的聚類簇作為map 的輸出。Reduce 的任務(wù)則是計(jì)算各個(gè)聚類簇的均值，以輸出，其中num為使用Combine 函數(shù)統(tǒng)計(jì)得到的每個(gè)簇中的向量個(gè)數(shù)，aveVec表示聚類簇的平均值，接著reduce 負(fù)責(zé)局部匯總，如目標(biāo)函數(shù)收斂則結(jié)束運(yùn)算，同時(shí)輸出，CenVec 為新聚類中心；否則讀取各聚類中心作為新聚類中心，重復(fù)上述過程。

3.3 優(yōu)化K-means聚類算法并行實(shí)現(xiàn)

基于Hadoop 的優(yōu)化K-means 聚類算法的具體實(shí)現(xiàn)過程如下：

Step 1：對于在3.1節(jié)中MapReduce Job4計(jì)算得到的文本向量集D={di|di?Rp,i=1,2,…,n}，通過采用等概率抽樣的方法對D多次進(jìn)行采樣，得到樣本集表示為S1,S2,…,Sn。

Step 2：隨機(jī)從Si中選擇文本向量dj，把dj看作第一聚類中心e1。計(jì)算D中其他的向量到dj的歐式距離，選擇最遠(yuǎn)距離所對應(yīng)的向量dk作為第二聚類中心e2。

Step 3：分別計(jì)算D中剩余向量di和e1、e2之間的距離，分別記做di1和di2，從中找出最小值min(di1,di2)。

Step 4：比較di1和di2，找出較大者max(min(di1,di2))，對應(yīng)向量用dm表示。

Step 5：如果max(min(di1,di2))≥t|e1,e2|，t的范圍為，這時(shí)取dm作為第三個(gè)聚類中心。

Step 6：當(dāng)選取Si中的第n+1 個(gè)向量作為聚類中心時(shí)，計(jì)算并找到剩余向量到已知聚類中心的距離max(min(di1,di2,…,dim))所對應(yīng)的向量，如果滿足公式，則對應(yīng)的向量作為第n+1個(gè)聚類中心。

Step 7：為獲得其他聚類中心，重復(fù)執(zhí)行Step2到Step6。

Step 8：依據(jù)密度參數(shù)進(jìn)行升序排列。

Step 9：合并具有最大密度參數(shù)對應(yīng)向量的半徑R內(nèi)的所有向量為簇，將訪問過的向量標(biāo)記好，然后重復(fù)步驟選擇密度參數(shù)最大的向量，直到所有向量均被處理，得到各個(gè)簇的平均值，作為最終初始聚類中心。

Step 10：將Step 9 計(jì)算得到的聚類中心作為K-means的初始中心并運(yùn)行該算法。

最后將優(yōu)化的算法基于Hadoop 進(jìn)行具體的實(shí)現(xiàn)。

4 實(shí)驗(yàn)結(jié)果

本文對Hadoop 平臺(tái)下優(yōu)化的文本聚類算法進(jìn)行了實(shí)現(xiàn)。實(shí)驗(yàn)通過采用6 臺(tái)虛擬機(jī)作為Hadoop集群的六個(gè)節(jié)點(diǎn)，用1 臺(tái)虛擬機(jī)作為集群中的Mas?ter 節(jié)點(diǎn)，剩下的5 臺(tái)虛擬機(jī)則用來作為Slaver 節(jié)點(diǎn)。實(shí)驗(yàn)分別從聚類效率、聚類質(zhì)量兩個(gè)方面進(jìn)行了測試。

4.1 聚類效率實(shí)驗(yàn)

對數(shù)據(jù)集S1、S2分別在1、3、6個(gè)節(jié)點(diǎn)構(gòu)建的集群上進(jìn)行了基于Hadoop 的文本向量化和基于Ha?doop 的優(yōu)化K-means 文本聚類實(shí)驗(yàn)，表1 和表2 分別給出了數(shù)據(jù)集S1、S2 在不同節(jié)點(diǎn)個(gè)數(shù)上文本聚類運(yùn)行的時(shí)間。

表1 S1在不同節(jié)點(diǎn)進(jìn)行文本聚類時(shí)的運(yùn)行時(shí)間

表2 S2在不同節(jié)點(diǎn)進(jìn)行文本聚類時(shí)的運(yùn)行時(shí)間

由表1 和表2 可見，對S1、S2 進(jìn)行操作時(shí)，Ha?doop集群節(jié)點(diǎn)個(gè)數(shù)越多，程序無論在文本向量化還是在聚類上運(yùn)行所需時(shí)間均在減少，節(jié)點(diǎn)個(gè)數(shù)增加越多，程序運(yùn)行所需時(shí)間越少，并且隨著數(shù)據(jù)集規(guī)模增加，算法運(yùn)行時(shí)消耗的時(shí)間減少的也越多，由此表明基于Hadoop 的多節(jié)點(diǎn)的集群更適合處理大數(shù)據(jù)集，特別在節(jié)點(diǎn)個(gè)數(shù)達(dá)到6 個(gè)時(shí)，算法運(yùn)行效率大大提高。

4.2 聚類質(zhì)量實(shí)驗(yàn)

為了測試優(yōu)化的K-means 并行算法的聚類質(zhì)量，本實(shí)驗(yàn)分別對文本向量集S1 和S2 在K-means聚類算法和優(yōu)化K-means聚類算法上進(jìn)行了聚類，表3和表4分別給出兩種不同聚類算法對S1和S2在五個(gè)類別上的查準(zhǔn)率（Precision）和查全率（Recall）。

表3 數(shù)據(jù)集S1的Precision和Recall

表4 數(shù)據(jù)集S2的Precision和Recall

由表3 和表4 可見，優(yōu)化K-means 并行算法在查準(zhǔn)率和查全率上都比傳統(tǒng)K-means 聚類算法要高。由于數(shù)據(jù)集S2 的規(guī)模大于數(shù)據(jù)集S1，因此在S2 上的查準(zhǔn)率和查全率無論在哪個(gè)算法上都比在S1 上的查準(zhǔn)率和查全率要小，但在減小幅度上，優(yōu)化的K-means要比K-means減小的少，由此說明優(yōu)化的K-means并行算法相對更穩(wěn)定。

5 結(jié)語

本文首先介紹了文本聚類和Hadoop 開源云平臺(tái)中的相關(guān)知識(shí)，針對傳統(tǒng)K-means聚類算法存在初始中心選取隨意而導(dǎo)致運(yùn)行不穩(wěn)定及單機(jī)串行編程對海量數(shù)據(jù)聚類效率低的缺點(diǎn)，提出并設(shè)計(jì)一種Hadoop 平臺(tái)下并行化實(shí)現(xiàn)文本聚類的優(yōu)化算法，然后詳細(xì)地介紹了算法具體設(shè)計(jì)和實(shí)現(xiàn)的過程，文中在最后通過搭建的Hadoop 集群對數(shù)據(jù)進(jìn)行測試，實(shí)驗(yàn)結(jié)果表明優(yōu)化的文本聚類并行算法在聚類效率和聚類質(zhì)量上均有較大的提高。