基于WEKA平臺的文本聚類研究與實現

[摘 要] 文本聚類是文本挖掘領域的一個重要研究分支，是聚類方法在文本處理領域的應用。本文首先對基于空間向量模型的文本聚類過程做了較深入的討論和總結。另外，本文回顧了現有的文本聚類算法，以及常用的文本聚類效果評價指標。在研究了已有成果的基礎上，本文利用20 Newsgroup文本語料庫，針對向量空間表示模型，在開源的數據挖掘平臺WEKA上實現了文本預處理和k-means聚類算法，并根據實際聚類效果，就文本表示、特征選擇、特征降維等方面提出優化方案。

[關鍵詞]文本挖掘;文本聚類;向量空間模型;WEKA

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2009 . 21 . 003

[中圖分類號]TP393[文獻標識碼]A[文章編號]1673 - 0194(2009)21 - 0009 - 04

1引 言

近年來，隨著互聯網的大規模普及和社會信息化程度的提高，非結構化的文本數據成為了信息最重要的載體，研究表明信息有80%包含在文本數據中[1]，這使文本挖掘[2]成為數據挖掘領域中一個日益流行且重要的研究方向。在日常工作中，人們經常遇到的一個問題就是，如何對文本進行分類、比較，評估文本的相關性和重要性，以及發現眾多文本的模式與趨勢。延續數據挖掘的思想，人們自然將解決這一問題的目光投向文本挖掘中與分類相關的技術。

要實現對大量文本的自動分類，可以采用文本分類和文本聚類兩種方法。在信息瞬息萬變的今天，經常會出現新的數據很難用已有的分類體系來處理，如果重新進行分類，就必須重新建立分類好的訓練文檔集，而獲得大量帶有類別標注的樣本的代價是很大的。這時使用聚類的方法就顯得很重要，因為作為一種無監督的機器學習方法，文本聚類由于不需要訓練過程，以及不需要預先對文檔手工標注類別，具有一定的靈活性和較高的自動化處理能力[3]。據數據挖掘著名網站Kdnuggets的調查，在最近的6個月中，使用開源的數據挖掘工具的人(占使用商業和開源工具總數的36%)，其中的5%左右在使用WEKA工具進行數據挖掘，11%左右在使用基于WEKA構建的RapidMiner工具，如圖1所示。由此可見，WEKA作為基于Java環境下開源的機器學習和數據挖掘工具的元老，英勇不減當年。本文基于開源的WEKA機器學習平臺，探索了利用WEKA進行文本聚類的全過程。

圖 1 數據挖掘工具的使用情況調查

2文本聚類概述

2.1 文本聚類的基本思想

文本挖掘(Text Mining)[4]是指從大量文本數據中抽取事先未知的可理解的最終可用的知識的過程。作為文本挖掘的重要分支，文本聚類主要是依據Hearst等人證明的“聚類假設”:同類的文本相似度較大，而不同類的文本相似度較小[5]。

2.2 文本聚類的過程

目前，文本聚類的途徑一般是將非結構化問題結構化，利用現有的數據挖掘技術進行聚類。該途徑的基本思路是:首先進行分詞、特征表示、提取等處理，將文本用結構化的形式來描述;然后根據應用需求，選擇或設計聚類算法;最后將所得到聚類效果進行評估，不斷改進聚類過程。具體過程如圖2所示。

圖 2 文本聚類的過程

3文本聚類技術研究

3.1文本預處理

文本預處理是把文本表示成聚類算法可以處理的形式，包含特征表示和特征提取兩個階段。

目前文本特征表示模型有向量空間模型、布爾模型、概率檢索模型、語言模型等，其中向量空間模型最為流行。

在向量空間模型中，文檔集C中的每個文檔Dj都是向量空間中的一個特征向量，且所有文檔的特征向量都具有相同的維數n，該維數是所有文檔中不同特征項的總數目。文檔Dj的特征向量可以用文檔中的特征項Ti及其權重Wij來表示:

V(Dj) = {T1，W1j;T2，W2j;…;Tn，Wnj｝

特征項Ti的權重Wij的計算采用TF-IDF方法的標準定義:

Wij = TFij × IDFi = TFij × logN/DFi

其中，N為文檔集C中的文檔總數目，TFij為特征項Ti在文檔Dj中出現的次數，DFi為文檔集C中包含Ti的文檔數目。

特征提取也被稱為特征降維，分為特征選擇和特征抽取兩種主要方法。在對文本挖掘過程中，需要考慮多個因素的影響，將特征選擇和特征抽取有效地結合起來，聯合降低特征維數。

3.2 文本聚類算法

目前有多種文本聚類算法，根據算法的思想大致可分為:

3.2.1劃分方法(Partitioning Method)

k-means算法是最常見的劃分方法，比較著名的算法還有PAM、CLARA、CLARANS和EM等。

3.2.2 層次方法(Hierarchical Method)

層次聚類可以分為兩種:凝聚層次聚類和劃分層次聚類。近年來出現的新算法包括CURE、ROCK、Chameleon和BIRCH。

3.2.3 基于密度的方法(Density-Based Method)

為了發現任意形狀的聚類結果，提出了基于密度的方法，它將簇看作是數據空間中被低密度區域分割開的高密度區域。常見的方法有DBSCAN、OPTICS和DENCLUE等。

3.2.4 基于網格的方法(Grid-Based Method)

基于網格的聚類算法是采用一個多分辨率的網格數據結構，將數據空間量化為若干單元，形成一個網格結構，所有的聚類操作都在此網格上進行。典型的基于網格的聚類方法有STING、WaveCluste和CLIQUE等。

3.2.5基于模型的方法(Model-Based Method)

典型的基于模型的聚類方法有統計學方法COBWEB和CLASSIT、AutoClass，神經網絡方法SOM、ATR和LVQ。

其他常見方法還有基于圖論的聚類算法、基于核的聚類算法、模糊聚類算法等。文獻[6]對聚類算法做了全面的描述。

3.3 文本聚類效果評估

在文本聚類算法實施之后，需要對聚類效果進行評估。常用評測指標是查準率、查全率及F值[7]。本文用F值指標來評價文本聚類的效果。

F值組合了信息檢索中查準率與查全率的思想，需要查準率和查全率都很高時，F值才能得到較高的值。對于一個聚類i和一個分類j的P(precision)與R(recall)定義為:P = Precision(i，j) = Nij/Ni，R = recall(i，j) = Nij /Nj 。

其中， Nij是在聚類i中分類j的數目;Ni是聚類i中所有對象的數目;Nj是分類j中所有對象的數目。

則分類j的F值定義為:F( j) = 。

對分類j而言，哪個聚類的F值高，就認為該聚類代表分類j的映射。對聚類結果來說，其總F值可由每個分類j的F值加權平均得到:F =。

其中，| j |為分類j中所有對象的數目。F值越高，說明聚類的效果越好。

4基于WEKA的文本聚類

4.1WEKA概述

WEKA作為一個開源的數據挖掘工作平臺，集合了大量能承擔數據挖掘任務的機器學習算法，包括對數據進行預處理、分類、回歸、聚類、關聯規則以及在新的交互式界面上的可視化。WEKA提供了4種用戶界面，分別是Explorer、Experimenter、Knowledge Flow和Simple CLI。

4.2數據的準備

本次實驗采用的語料庫是20Newsgroups的一部分，從其中選擇了3類文本數據，每類中都隨機選擇了100篇文檔。由于本實驗是利用WEKA進行文本聚類，因此需將文本數據轉換成WEKA所能識別和處理的ARFF格式。

ARFF(Attribute-Relation File Format)[8]文件是WEKA的文件格式。將文本數據轉化為ARFF格式需要用到WEKA中的TextDirectoryLoader轉換器。

4.3 文本預處理

WEKA中的StringToWordVector過濾器能將ARFF文件中的文本數據轉換為空間向量模型，它同時擁有分詞、特征表示、特征提取等功能。在Explorer中的Reprocess界面導入ARFF文件，選擇StringToWordVector過濾器，再設置相關參數。本文通過兩次實驗，設置不同參數，尤其是對特征降維參數的調整，得到兩個預處理結果供文本聚類算法使用。將兩種參數分別應用到ARFF文件后，就會生成用向量空間模型表示的新的文件。去除類標記后，分別保存。

4.4 聚類算法

本實驗嘗試用k-means算法進行本文聚類。進入Explorer中的Cluster界面，選擇WEKA提供的聚類算法Clusters> SimpleKMeans，然后設置參數為SimpleKMeans -N 3 -A \"weka.core. EuclideanDistance -R first-last\" -I 500 -S 10，應用后，右鍵點擊兩次聚類結果的Visualize cluster assignments分別出現圖3和圖4所示的結果。

圖 3 實驗1聚類效果圖

圖 4 實驗2聚類效果圖

4.5 聚類評估

用F值對兩次實驗的聚類結果進行評估，首先計算查準率和查全率，如表1所示。

表 1 查準率和查全率的計算結果

然后計算各類的F值，加權平均后得到聚類結果的總F值，如表2所示。

表 2 F值的計算結果

5實驗結果分析

從聚類評估的結果可以看出，實驗2在對實驗1的文本預處理階段進行了參數調整，特別是在特征降維上的參數調整，使F值得到了提高，即聚類效果得到了提高。因此，我們基本上驗證了文獻[9]的結論:用向量空間模型得到的特征向量的維數往往很高，高維的特征對即將進行的文本聚類未必全是重要的和有益的，而且還會加劇機器學習的負擔。

6結束語

文本聚類是文本挖掘中一些關鍵技術的基礎，在文本挖掘領域有著十分重要的作用。將來需要做的工作有:①發展全新的非結構化文本的聚類算法;②對WEKA進行二次開發，探索將新的文本聚類算法嵌入到WEKA，并與平臺上原有聚類算法進行性能對比;③將文本挖掘與中文自然語言處理、計算語言學等有效集成，能有效地處理中文文本數據。

主要參考文獻

[1]Ah-Hwee Tan. Text Mining: The State of the Art and the Challenges[C]//Proceedings of the PAKDD， 1999.

[2]Feldman R， Dagan I. Knowledge Discovery in Textual Databases (KDT)[C]//Proceedings of the First International Conference on Knowledge Discovery and Data Mining (KDD-95)， Montreal， Canada，AAAI Press，1995:112-117.

[3]郭建永.聚類分析在文本挖掘中的應用與研究[D].無錫:江南大學，2008.

[4]Michael W Berry， Malu Castellanos. Survey of Text Mining II: Clustering， Classification， and Retrieval[M]. NewYork:Springer， 2007.

[5]Marti Hearst and Jan Pedersen， Reexamining the Cluster Hypothesis: Scatter/Gather on Retrieval Results[C]//Proceedings of the 19th Annual International ACM/SIGIR Conference， Zurich， August 1996.

[6]R Xu， D Wunsch. Survey of Clustering Algorithms[J]. IEEE Transactions on Neural Networks， 2005，16(3).

[7]Ayad H， Kamel MS. Topic Discovery from Text Using Aggregation of Different Clustering Methods[M]. London:Springer， 2002.

[8]Witten IH， Frank E. Data Mining Practical Machine Learning Tools and Techniques[M].2nd Edition. Morgan Kaufmann，2005.

[9]Lee JM， Calvo RA. Scalable Document Classification[J]. Intelligent Data Analysis， 2005， 9(4):65-80.

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文

The Research and Implementation of Text Clustering Based on WEKA

CHEN Jia-yong

(School of Economics and Management， University of Science and Technology Beijing， Beijing 100083，China)

Abstract:Text clustering， one of the most important research braches of text mining， is the application of clustering algorithm in text processing. Firstly， this paper makes relatively deep discussion and summary in the field of VSM-based text clustering process. Moreover， it also discusses with the text clustering algorithm and introduces basic knowledge of clustering validity. On the basis of these works， by doing research with the open source corpus of 20 Newsgroup， this paper implements text preprocessing and k-means clustering algorithm based on the open source data mining tool of WEKA. According to the effects of clustering of the corpus， it presents optimization of text clustering algorithm， including feature representation， dimensionality reduction etc.optimizations of text clustering algorithm， including feature representation， dimensionality reduction etc.

Key words: Text Mining; Text Clustering; Vector Space Model; WEKA