Hadoop 下并行化實現文本聚類的優化算法?

王 輝 潘俊輝 Marius.Petrescu 王浩暢 張 強

（1.東北石油大學計算機與信息技術學院 大慶 163318）（2.普羅萊斯蒂石油天然氣大學 什蒂 100680）

1 引言

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

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

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

2 Hadoop平臺及文本聚類

2.1 Hadoop平臺

Hadoop 平 臺 由Apache Software Foundation 公司正式引入后迅速成為大數據分析處理的領先平臺。該平臺具有兩大核心架構，分別是底層存儲系統HDFS和上層應用MapReduce編程框架［11］。

2.1.1 HDFS

HDFS是一種分布式文件系統，以分布式的形式將劃分的數據塊存儲到多節點中。HDFS中的主節點負責分布式文件系統的命名空間，在其中保存了兩個核心的數據結構FsImage 和EditLog。從節點則是HDFS 的Slaver，其主要負責數據的存儲和讀取［12］。

2.1.2 MapReduce

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

2.2 文本聚類

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

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

3 Hadoop 平臺下并行化實現文本聚類的優化算法

3.1 文本向量化并行設計

網頁文本經預處理后，通過對得到的特征賦予權值，可建立以特征和權值為基礎的多維空間坐標系，在多維空間中，對網頁文本進行的操作可轉換為對向量進行的運算。當數據量較大時，會隨著文本向量的建立而增加向量空間的維度，進而導致計算量增加嚴重時造成機器跌宕。因此針對MapRe?duce并行處理大數據的優勢，可在進行文本聚類時將聚類中的每個步驟基于MapReduce并行計算，即將文本向量化的過程分成四個MapReduce任務，分別用來實現文本預處理、特征的選取、特征的TF-IDF值的計算和建立文本向量。

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

圖1 文本向量化過程的實現框架

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

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

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

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

3.2 優化K-means并行算法

3.1 節通過四個MapReduce Job 并行實現將文本轉換為文本向量后，本節的工作就是對3.1 節得到的文本向量采用優化算法并行進行文本聚類。本節為滿足聚類算法有較好的效率和準確率分別從并行隨機采樣、并行合并數據對象和數據對象聚類并行化三個方面對K-means算法進行了優化，最后將優化的算法基于Hadoop 進行了并行實現。圖2給出了優化K-means算法的MapReduce并行框架圖。

圖2 改進K-means算法的MapReduce框架圖

3.2.1 并行隨機采樣

本文為提高隨機采樣的效率，設計了基于Ma?pReduce 進行隨機采樣的方法。基于MapReduce的并行隨機采樣通過兩個階段實現。

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

3.2.2 并行合并數據對象

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

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

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

3.2.3 數據對象聚類并行化

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

MapReduce Job3 的Mapper 的map 函數的輸入為MapReduce Job2 的輸出，計算獲得各個聚類中心距離并根據距離最近原則將文本向量歸入到相應的簇內，然后以得到的相似度小的向量構成的聚類簇作為map 的輸出。Reduce 的任務則是計算各個聚類簇的均值，以輸出，其中num為使用Combine 函數統計得到的每個簇中的向量個數，aveVec表示聚類簇的平均值，接著reduce 負責局部匯總，如目標函數收斂則結束運算，同時輸出，CenVec 為新聚類中心；否則讀取各聚類中心作為新聚類中心，重復上述過程。

3.3 優化K-means聚類算法并行實現

基于Hadoop 的優化K-means 聚類算法的具體實現過程如下：

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

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

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

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

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

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

Step 7：為獲得其他聚類中心，重復執行Step2到Step6。

Step 8：依據密度參數進行升序排列。

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

Step 10：將Step 9 計算得到的聚類中心作為K-means的初始中心并運行該算法。

最后將優化的算法基于Hadoop 進行具體的實現。

4 實驗結果

本文對Hadoop 平臺下優化的文本聚類算法進行了實現。實驗通過采用6 臺虛擬機作為Hadoop集群的六個節點，用1 臺虛擬機作為集群中的Mas?ter 節點，剩下的5 臺虛擬機則用來作為Slaver 節點。實驗分別從聚類效率、聚類質量兩個方面進行了測試。

4.1 聚類效率實驗

對數據集S1、S2分別在1、3、6個節點構建的集群上進行了基于Hadoop 的文本向量化和基于Ha?doop 的優化K-means 文本聚類實驗，表1 和表2 分別給出了數據集S1、S2 在不同節點個數上文本聚類運行的時間。

表1 S1在不同節點進行文本聚類時的運行時間

表2 S2在不同節點進行文本聚類時的運行時間

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

4.2 聚類質量實驗

為了測試優化的K-means 并行算法的聚類質量，本實驗分別對文本向量集S1 和S2 在K-means聚類算法和優化K-means聚類算法上進行了聚類，表3和表4分別給出兩種不同聚類算法對S1和S2在五個類別上的查準率（Precision）和查全率（Recall）。

表3 數據集S1的Precision和Recall

表4 數據集S2的Precision和Recall

由表3 和表4 可見，優化K-means 并行算法在查準率和查全率上都比傳統K-means 聚類算法要高。由于數據集S2 的規模大于數據集S1，因此在S2 上的查準率和查全率無論在哪個算法上都比在S1 上的查準率和查全率要小，但在減小幅度上，優化的K-means要比K-means減小的少，由此說明優化的K-means并行算法相對更穩定。

5 結語

本文首先介紹了文本聚類和Hadoop 開源云平臺中的相關知識，針對傳統K-means聚類算法存在初始中心選取隨意而導致運行不穩定及單機串行編程對海量數據聚類效率低的缺點，提出并設計一種Hadoop 平臺下并行化實現文本聚類的優化算法，然后詳細地介紹了算法具體設計和實現的過程，文中在最后通過搭建的Hadoop 集群對數據進行測試，實驗結果表明優化的文本聚類并行算法在聚類效率和聚類質量上均有較大的提高。