基于Hadoop平臺的一種改進K-means文本聚類算法

潘俊輝， 王輝， 張強， 王浩暢

(東北石油大學,計算機與信息技術學院,黑龍江，大慶 163318)

0 引言

目前隨著互聯網的發展，加快了數據量的積累，而其中的文本數據維度高、數據量大，同時又記錄著有價值的信息，因此，可采用文本聚類方法將相似的文本進行歸類處理，提取文本中的關鍵信息可以為智能化推薦等眾多領域提供基礎，從而實現資源的有效利用[1]。傳統的串行文本聚類方法對于海量的文本數據難以進行高效的處理。隨著云計算技術的出現，在Hadoop平臺下實現分布式文本聚類是一個值得研究的方向。

國內外的諸多學者為提高聚類算法的性能進行了大量的研究。國內的黃劍等學者在Hadoop平臺下并行實現了K-means聚類算法[2]；高見文等通過MapReduce對海量數據以迭代的方式進行了并行聚類的實現[3]；國外的Shikai Jin等提出了一種并行化的改進K-means方法，實驗表明該方法既可減少開銷，同時可提高效率[4]；文獻[5]的作者通過采用最大最小距離確定聚類方法的初始中心，從而可消除K-means對初始值敏感的缺點，同時在Hadoop平臺下得以實現，可消耗更少的時間。

針對經典K-means算法中每個屬性對樣本的影響均相同，而許多改進算法中對于屬性權值的確定需要依賴先驗知識的缺點，本文通過引入屬性權重提出了一種改進型的K-means聚類算法(ImprovedK-means Algorithm,IKA)，同時為了提高該算法的效率，應用Hadoop平臺完成了實現。通過實驗對該算法進行了測試，結果表明Hadoop平臺下實現的文本聚類改進型算法具有良好的聚類效果。

1 Hadoop平臺及文本聚類

1.1 文本聚類

文本聚類是指通過對文本進行預處理后，將得到的結構化數據進行聚類在一起成簇，從而使同一簇中的文本盡可能地相似，而不同簇的文本盡可能不同。其中文本預處理階段的工作主要是通過提取出文本中的特征詞并計算其權重，從而得到結構化的數據，并且該階段的結果直接影響整個文本聚類的結果；而聚類分析階段的工作則是通過聚類算法將文本數據劃分到不同類別的文本集合中[6]。

1.2 Hadoop平臺

Hadoop平臺是實現分布式計算的一種開源框架，該平臺主要包括兩部分，分別是HDFS和MapReduce編程框架[7]。

HDFS主要的工作就是以分布式的形式存儲大規模的海量數據。HDFS中的NameNode主要負責分布式文件系統的命名空間。DataNode則是HDFS的工作節點，主要負責數據的存儲和讀取。

MapReduce核心是Map函數和Reduce函數。Map函數可將輸入數據以〈key,value〉的形式切分成獨立的小數據塊，并以〈key,value〉的形式輸出，并同時提供給Reduce函數；Reduce函數接收到Map處理的中間結果后，將相同的鍵值進行合并，最后輸出結果并寫入到HDFS[7]。

2 Hadoop平臺上實現文本聚類的改進型算法

2.1 K-means算法

K-means算法通過將距離作為相似性的評價指標，采用式(1)的誤差平方和作為K-means算法的聚類準則函數。由于算法中初始聚類中心的選取是隨機的，因此會直接影響文本聚類的結果。

(1)

K-means算法的執行流程如下。

Step1:隨機從數據集中選取K個樣本作為算法的初始簇心。

Step2:使用距離計算式，計算每個樣本與K個聚類中心的歐式距離。

Step3：按照距離遠近，將樣本歸入到距其最近的聚類中心所在簇中。

Step4：對各簇的樣本均值進行計算，從而得到新的聚類中心。

Step5:若算法迭代次數達到最大值，或評價指標值與上次的評價指標值的差小于最小精度確定的值，算法結束，否則轉向Step2，執行相關操作。

2.2 改進型K-means聚類算法

使用K-means算法進行聚類時，假設數據集為X，具有P個屬性，要將數據集分成K類，通過不斷調整聚類簇心，從而使式(1)具有最小值，其中uj，j=1,2,…,K為簇心，如式(2)。

(2)

式中，d(Xi,uj)是指樣本Xi與簇心uj間的歐式距離，權重系數為1，意味著在算法中每個屬性的作用是同等的，而在實際中每個屬性對樣本的作用是不同的。由此為了把每個屬性對樣本的作用不同的特點體現出來，使算法具有更好的聚類效果，本文在K-means算法中引入了權值，從而使聚類準則函數發生變化，新的函數如式(3)。

(3)

(4)

由式(4)可知，當各類中的類內樣本與簇心的距離和最小且不發生變化時，V(P,λ)具有最小值。由此本文通過分析采用拉格朗日函數法計算在約束條件下每個屬性的權重。

構造拉格朗日函數如式(5),

(5)

(6)

(7)

由此可得到基于屬性權重的改進算法IKA的實現步驟如下。

Step 1：隨機從數據集中選擇K個樣本作為簇心；

Step 2：計算出每個樣本與K個簇心間的距離，從中得到距離最小的簇心(uj，j=1,2,…,K)，然后歸入該類中；

Step 3：根據權值計算式(7)計算得到每個屬性的權值；

Step 4：根據計算得到的各類的屬性權值，重新對各類的簇心進行計算；

Step 5：若算法迭代次數達到最大值，或評價指標值與上次的評價指標值的差小于最小精度確定的值，算法結束，否則轉向Step2，執行相關操作。

2.3 基于Hadoop平臺的改進型文本聚類算法(H-IKA)

通過IKA算法的實現步驟可看出該算法是串行迭代的，而計算每個樣本的最近簇心卻是獨立的，因此可對其并行執行，由此在Hadoop平臺下對IKA算法并行進行了實現。在H-IKA算法中，有3個關鍵函數需要執行，分別為Map、Combine和Reduce函數。其中屬性權重的引入是在Reduce函數中進行的，因此對Reduce函數進行了改進。

改進后的Reduce函數其功能是用來計算各類的屬性權重，然后利用得到的屬性權重計算新類的簇心。Reduce函數的輸入中key表示樣本所在類的序號，value值代表樣本屬性值；Reduce函數的輸出中key’表示樣本所在類的序號，value’則代表新種群的簇心。以下為Reduce函數的偽代碼：

reduce(〈key,value〉,〈key’,value’〉)

{

初始化存儲各維坐標累加值的數組，分量初值均為0;

初始化記錄相同簇的樣本個數Num=0;

while(value.hasNext()){

解析得到num和樣本的各維坐標;

累加各維坐標到數組(va)對應的分量中;

將求得的各維坐標與類簇心各維坐標差的平方和累加到數組(va1)對應的分量中;

將求得的各樣本與類簇心間距離的平方累加到分量(va2)中;

Num+=num;}

相乘va中各坐標分量，然后開p次方;所得值與分量va2相除，得到各類屬性權重;

va1中每個分量除以Num，將結果與屬性權重的各維分量相乘，得到新中心點坐標;

key’=key;

構造具有新中心點各維坐標信息得字符串，value’=字符串;

輸出〈key’,value’〉

}

3 實驗結果

實驗采用8臺相同的計算機搭建了實驗平臺。構造了大小分別為16G和32G的48維的數據集，在構造的數據集中，數據的屬性對分類的影響較大。實驗分別從收斂速度和聚類精度兩方面對基于Hadoop的K-means算法和基于Hadoop的IKA算法進行了測試，表1和表2分別給出了收斂速度和聚類精度的比較結果。

表1 收斂速度比較

表2 聚類精度比較

由表1和表2可見，分別對16G和32G的數據集進行操作時，基于Hadoop的IKA算法的平均迭代次數最小，聚類結果的準確性更高，表明基于Hadoop的IKA算法優于基于Hadoop的K-means算法，更適合處理大數據集的數據，其原因為在H-IKA算法中考慮了屬性權重的影響。

4 總結

本文針對K-means算法中由于每個屬性作用均等而導致聚類效果受到影響的缺點，通過引入屬性權重提出了一種改進型的K-means聚類算法，同時為提高算法效率，將其遷移到Hadoop平臺上進行實現。最后通過實驗對算法進行測試，實驗結果表明Hadoop平臺下實現文本聚類的改進型算法在收斂速度和聚類精度上具有較大的提高。