文件聚類可以作為多文件自動文摘等自然語言處理應用的預處理步驟，可以將重要新聞文字進行聚類處理，是一種處理文字資訊的重要手段。
文字聚類開題報告
基於K―Mean文字聚類的研究
摘 要 文字聚類能夠把相似性大的文字聚到同一類中。K-Means常用來聚類文字，但是由於聚類中心的選取對聚類結果有影響，導致聚類不穩定，因此採用一種基於聚類中心的改進演算法分析文字，通過實驗，驗證演算法的有效性。
中國論文網
關鍵詞 文字聚類;k-means;相似性;度量準則
中圖分類號：TP391 文獻標識碼：B
文章編號：1671-489X(2014)18-0050-03
Research for Text Clustering based on K-Mean//ZHANG Yue， LI Baoqing， HU Lingfang， MENG Li
Abstract Text clustering can make the text similarity large clustered into the same class， K-Means usually is used in text clustering， because of impacting on the cluster center， which results in the clustering instability. Therefore， this paper uses a text analysis of improved algorithm based on the clustering center， through the experiment， it verifies the effectiveness of the improved algorithm.
Key words text clustering; k-means; similarity; measure criterion
文字聚類是把不同的文字分別聚在不同的類別中，是文字挖掘的重要技術，它是一種無監督的學習技術，每個類中包含的文字之間具有較大的相似性，不同類間的文字相似性比較小。文字聚類是資料探勘的重要分支，它應用神經網路、機器學習等技術，能夠自動地對不同文字進行分類。
在文字聚類分析中，文字特徵表示一般採用向量空間模型[1]，這種模型能更好表現文字。在對文字聚類的研究中，Steinbach等人研究了基於劃分的方法和基於層次的方法在文字聚類中的適用程度[2-3]，得出結論：採用K-Means演算法進行聚類，不僅聚類結果較好，而且適用於資料量比較大的聚類場合。在文章中根據研究者對K-Means的發現，結合實際研究，採用一種基於K-Means的改進演算法來聚類。Dhillod等人對文字聚類進行研究發現，採用餘弦夾角作為相似性度量比採用歐氏距離度量的結果好很多[4]。
1 文字聚類
文字聚類的方法很多，主要分為基於層次的方法、基於劃分的方法、基於密度的方法、基於模型的方法、基於網格的方法[5]。在這些聚類方法中，基於劃分的K-Mean是最常用也是很多改進方法的基礎，文章中採取的改進方法也是基於K-Mean的。
K-Mean首先由MacQueent[6]提出。它能在大資料集中廣泛被使用，因為演算法效率較高、演算法執行過程理解容易。當前進行的很多研究都是以K-Mean為基礎開展進行的，它的計算複雜度低，具有與文件數量成線性關係的特性，計算效率不僅高，而且伸縮性較強，適應大資料集的能力也很強。K-Mean以k為初始聚類數，然後把n個文字分到k個聚類中，這樣類內的文字具有較高的相似度，不同類間的相似度較小。
K-Mean具體的演算法過程如下：
1)首先給定n個數據文字，從其中任選k個文字，這k個數據文字初始地代表了k個類的資料中心;
2)對剩餘的每個文字計算其到每個中心的距離，並把它歸到最近的中心類中;
3)重新計算已經得到的各個類的中心，通常計算中心的準則函式採用平方誤差準則，這個準則能夠使生成的結果類儘可能地獨立和緊湊;
4)迭代執行第二步和第三步的動作直至新的中心與原中心相等或小於指定閾值，直到演算法結束。
具體的演算法流程如圖1所示。
2 改進的聚類演算法
雖然使用K-Mean演算法進行文字聚類時，具有計算複雜度低，計算效率不僅高，而且伸縮性較強，適應大資料集的能力也很強的優點，但是實驗發現，不僅初始聚類中心的選取對聚類結果有影響，孤立點的存在對文字的相似性的判斷也有很大的影響，這就導致聚類判斷不穩定。基於此，文章採用一種改進的方法來進行文字聚類，改進關鍵點在於聚類中心的計算，用與原聚類中心相似的文字資料來計算平均值作為該聚類中心。
改進的K-Means演算法描述如下所示：
1)首先給定n個數據文字，從其中任選k個文字，這k個數據文字初始地代表了k個類的資料中心;
2)對剩餘的每個文字計算其到每個中心的距離，並把它歸到最近的中心類中，記作means;
3)選擇類中與類中心大於等於(1+a)*means的文字集合{D1，D2，...，Dk}，其中a∈[-0.31，0.31]，重新計算新文字集中的`類中心;
4)迭代執行第2步和第3步的動作直至新的中心與原中心相等或小於指定閾值，直到演算法結束。
3 相似度計算
文字聚類中涉及文字的相似性計算，只有相似性大的文字才能聚到同一類中，因此，相似性的度量對文字的聚類很關鍵。在文字聚類中，相似度度量方式一般有曼哈頓距離、Cosine距離、歐式距離，其中Cosine距離更能體現文字的相似性。本文主要採用Cosine距離，當兩個文字之間的文字相似度越大，它們之間的相關性越強。文字集用向量空間模型表示後，文字的相似度採用向量之間距離表示：
(1) 4 評價標準
文字聚類的有效性需要進行驗證，文章中主要採用F度量、平均純度來對聚類結果進行評價。
1)F度量。F度量把召回率和評價標準準確率結合在一起。
準確率：P(i，r)=nir/nr (2)
召回率：R(i，r)=nir/ni (3)
其中nir是類別r中包含類別i中的文字的個數，nr是類別r中實際文字的數目，ni是原本類別i中應有的文字數，F值的計算公式：
(4)
由公式(4)最後得到評價函式為：
(5)
其中n為文字的總數。從公式看出F值越高，聚類效果越好。
2)平均純度。除了用F度量來評價聚類，文章中還使用平均純度來度量文字聚類質量好壞[7]。設類ci的大小為ni，則該類的純度為：
(6)
其中nj表示類ci與第j類的交集大小，則平均純度公式為：
(7)
其中k為最終的聚類數目。一般說來純度越高聚類效果越好。
5 聚類實驗結果分析
文章中採用的實驗資料主要是搜狗語料庫。搜狗語料庫主要包括10種文字類別：軍事、招聘、IT、文化、健康、汽車、體育、旅遊、財經、教育。搜狗語料庫包含了每一類的資料夾，在資料夾中都是txt文字。為了驗證改進後的演算法比原演算法更有效，進行了多次實驗，最終選取了其中一次實驗結果為例子，對兩種演算法的F度量和純度進行比較，分別如表1和表2所示。
從表1可以看出，改進聚類中心的K-Means演算法在純度方面相對有一些提高;從表2可以看到F值提高明顯;從兩個表中的實驗結果可以看到改進的演算法是有效的。
6 結論
基於文字的聚類分析能夠對大量的文字進行聚類，分析中採用的聚類演算法的改進能在很大程度上提高聚類的準確性。實驗證明達到設計的效果，同時也為後期的各種資料探勘工作打下基礎。
參考文獻
[1]Salton G， Wong A， Yang C S. A vector space model for automatic indexing[J]. ACM，1975，18(11)：613-620.
[2]Steinbach M， KaryPis G， Kumar V. A comparison of document clustering techniques[C]eedings of KDD 2000 Workshop on Text Mining.2000：1-20.
[3]Ying Zhao， KaryPis G. Hierarchical Clustering Algorithms for Document Datasets[J]eedings of Data Mining and Knowledge Discovery，2005，10(2)：141-168.
[4]Dhillon I S， Modha D S. Concept decompositions for large sparse text data using clustering[J]ine Learning，2001，
42(1)：143-175.
[5]邵峰晶，於忠清.資料探勘原理與演算法[M].北京：中國水利水電出版社，2003.
[6]MacQueen J. Some methods for classification and analysis
of multivariate observations[C]//Proceedings of 5th Berkeley
Symposium on Mathematics. Statistics and Science.1967：281-
296.
[7]Hammouda K， Kamel M. Collaborative document clu-stering[C]//2006 SIAM Conference on Data Mining (SDM06).
2006：453-463.