基于向量空間模型的文檔聚類研究

摘要:文檔聚類在Web文本挖掘中占有重要地位，是聚類分析在文本處理領域的應用。文章介紹了基于向量空間模型的文本表示方法，分析并優化了向量空間模型中特征詞條權重的評價函數，使基于距離的相似性度量更為準確。重點分析了Web文檔聚類中普遍使用的基于劃分的k-means算法，對于k-means算法隨機選取初始聚類中心的缺陷，詳細介紹了采用基于最大最小距離法的原則，結合抽樣技術思想，來穩定初始聚類中心的選取，改善聚類結果。

關鍵詞:文檔聚類;k-means算法;向量空間模型;權重評價函數;最大最小距離

中圖分類號:TP311文獻標識碼:A文章編號:1009-3044(2009)25-7281-03

Vector Space Model-Based Document Clustering Research

XU Wei-jia

(School of Software Engineering， Tongji University， Shanghai 201804， China)

Abstract: Document clustering plays an important role in web text mining， which is applied in the fields of text processing. In this paper， first introduces the Vector Space Model which is aiming at how to define documents as vectors (or points) in a multidimensional space. In order to improve the accuracy of similarity measurement for different documents， defines a more reasonable way to evaluate the weight of terms contained in certain document. Then， detailed analyzes the partitioning-based K-means algorithm which is widely used in document clustering. Considering that K-means has deficiency in selecting initial start points randomly， adopts the iterative max-min distance method combined with sampling techniques to optimize the initial clustering points selection， which contributes to improve the final clustering result.

Key words: document clustering; k-means algorithm; Vector Space Model; term weight evaluation; max-min distance means

近年來，隨著Internet的快速發展，使得Web上的文檔資源呈現爆炸式的增長，這些文檔信息數據量大，內容繁雜而且處于不斷變化之中。與數據庫中結構化的信息相比，非結構化或半結構化的web文檔信息更加豐富和繁雜。為了充分有效地利用這些文檔資源，使用戶能夠快速有效的找到需要的信息，并且提取其中潛在的有價值的知識，需要對這些文檔進行聚類，因此用于文本挖掘和信息檢索領域的文檔聚類技術日益成為一個熱點。

文檔聚類的主要應用點包括:1)文檔聚類可以作為多文檔自動文摘等自然語言處理應用的預處理步驟。2)對搜索引擎返回的結果進行聚類，使用戶迅速定位到所需要的信息。3)對用戶感興趣的文檔(如用戶瀏覽器cache中的網頁)聚類，從而發現用戶的興趣模式并用于信息過濾和信息主動推薦等服務。4)可以用來改善文本分類的結果。5)文檔集合的自動整理。

1 文檔聚類

文檔聚類是無監督方式的組織文檔的最關鍵技術之一[1]，不依賴任何關于集合劃分的先驗知識，而僅僅根據集合內部的文檔對象彼此之間的相似度按照某種準則對文檔集合進行劃分。要求同一簇內文檔內容的相似度盡可能地大， 而不同簇間的相似度盡可能地小。

1.1 文檔聚類模型

文檔聚類的具體過程如圖1所示。

文檔預處理通常包括如下環節:去掉某些特定文檔中的格式標記;去除停用詞、進行數字合并、詞根還原;分詞、詞性標注、短語識別;詞頻統計;進行數據清洗以去除不合適的噪聲文檔或文檔中的垃圾數據。

文本的特征選擇和抽取:為了提高文本聚類的效率，減少計算復雜度，從而盡可能移除原始特征中權值過小的特征詞，以達到降低特征空間維數的目的。特征選擇一般是通過設置閾值來控制的。特征抽取是將原始特征項合并或轉換而得到新的特征項，從而實現文本對象表達從原始特征空間到低維特征空間的轉換過程。

文檔內容的特征表示采用向量空間模型[2]，將在下文詳述。

1.2 文檔聚類方法

目前，基于距離的文本聚類比較成熟的方法大致可分為兩種類型:層次凝聚法和平面劃分法[3]。

層次凝聚法的具體過程為構造出一棵生成樹，其中包含了簇的層次信息，以及所有簇內和簇間的相似度。層次聚類方法是比較常用的聚類方法，它能夠生成層次化的嵌套簇，但在每次合并簇時，需要全局地比較所有簇之間的相似度，并選擇出最佳的兩個簇，因此運行速度較慢，不適合于大量文檔的集合[4]。平面劃分法與層次凝聚法的區別在于，它將文檔集合水平地分割為若干個簇， 而不是生成層次化的嵌套，該方法的運行速度較快，因而更加適合像文檔聚類這種運算時間開銷較大的應用[5]。

典型的基于劃分的方法有k-means算法[6-7]。k-means算法具有可伸縮性和效率高的優點，具有線性的時間復雜度，從而被廣泛的應用于大文檔集的處理。但該算法對初值的依賴性很強，不同初始聚類中心的選擇往往會導致不同的聚類結果;同時，對于如何選擇初始聚類個數k，對最終的聚類結果也有較大影響。

另一方面，k-means算法采用向量空間模型來表示文檔，由于該算法使用基于距離的相似性度量，而文檔的特征向量又通過特征詞條的權重來表示，權值的大小反映了特征項對于文本的重要程度，如果不能合理的計算特征詞條的權值，則不同文檔間的基于距離的相似性度量就不那么準確有效，直接影響k-means算法執行的最終結果。

針對以上兩個方面，下文對特征詞條權重計算函數進行了詳細分析，并結合Web文檔結構的特性，重新定義權重評價函數;采用最大最小距離法思想，結合抽樣技術，來穩定初始聚類中心的選擇。

2 文本的特征表示及權重評價函數分析

2.1 向量空間模型(Vector Space Model)

向量空間模型[2-3]是目前廣泛采用且效果較好的一種文本表示方法，其思想是將Web文檔分解為由詞條特征構成的向量，把文檔看作是由一組正交詞條矢量所張成的矢量空間，將每篇文檔表示為其中的一個范化特征矢量，即用特征詞條及其權值表示文檔信息。文檔docj可以表示為公式(1):

docj==(w1j，w2j，…，wij，…，wmj)(1)

其中m為文檔中所有特征詞條的數目;wij(i=1，2，…，m)表示詞條ti在文檔docj中的權值。

2.2 特征詞條權重計算

在文本向量空間表示中，每個特征項都有一個權值，權值的大小反映了特征項對于文本的重要程度，即一個特征項在多大程度上能將其所在文本與其它文本區分開來。特征詞條的權重計算方法有多種，通常采用經典的TF-IDF[6]方法，比較常用的公式形式如(2)所示:

(2)

其中，wij表示特征詞條ti在文檔dj中的權重;TF(ti，dj)表示詞條ti在文檔dj中出現的頻數，記為tfij;IDF(ti)稱為逆文檔頻率，表示詞ti的縮放因子或重要性;N表示文檔集中的文檔總數;dti表示文檔集中包含詞條ti的文檔數。引入IDF[8](逆文檔頻率)的原因在于，如果特征詞出現在許多文檔中，由于其區分能力減弱，則它的重要性也降低，它能夠弱化一些在大多數文檔中都出現的高頻特征項的重要度。

2.3 特征詞條權重評價函數的優化

從上一節的公式可以看出，這種特征權重的計算方法是把文檔看成由一組無序特征詞條組成，詞條特征權重只是體現了該詞條是否出現以及出現次數多少的信息，而對于詞條在文檔中的位置，不同位置對文檔內容的決定程度不同這一方面卻未加考慮。

Web文檔數據與文本數據不同，是一種半結構化的數據。在網頁中，除了正文內容外，HTML文件的標簽信息對文檔的類別有很大貢獻[6]。一般來說，一個文檔的標題，摘要，關鍵詞以及特殊標識中出現的詞條對整個文檔內容有較大的決定作用。分析HTML文件的格式，可以發現諸如題頭

經過上面的分析，為TF-IDF引入Web文檔結構信息，定義標簽集合S={TITLE，H1，H2，H3，B，STRONG，U，I，META，BIG}。當特征詞條出現在標簽位置時，該特征詞對網頁類別的區分能力要大于在網頁正文中出現的同一個特征詞對網頁類別的區分能力，因此需要把出現在標簽中的特征詞賦予較高的權值。不同標簽及其相應權重如表1所示。

默認在Web文檔正文中(非標簽)出現的特征詞的權值賦為1。

根據以上分析，對TF(ti，dj)的改進如下公式(3)所示:

(3)

其中，tfij'表示詞條ti在文檔dj正文中(非標簽)出現的次數，tagweightq表示標簽q的權重，thiq'表示詞條ti出現在文檔dj中的特定標簽q中的次數。

同時，考慮到文本長度的不同對特征詞條權值的影響，將每個文檔向量進行歸一化處理，則可得到改進后的TF-IDF特征項權值計算公式(4)表示為:

(4)

其中TF(ti，dj)為公式(3)所描述。ti(i=1，2，…，m)為文檔dj的特征詞條。

k-means算法使用基于距離的相似性度量，文檔向量之間的相似性通過計算文檔向量之間的距離來表示，如下公式(5)所示:

(5)

則有余弦距離:Dis(di，dj)=1-sim(di，dj)

式中wij為改進后的特征項權值。可見，余弦相似度越大，文檔向量間的距離越小。

3 k-means聚類算法的分析

3.1 k-means算法分析

k-means算法的基本思想[1，6]是:隨機選取k個對象作為初始聚類中心;對剩余的每個對象，計算其到聚類中心的距離，把對象歸到離它最近的那個聚類中心所在的簇;對調整后的新簇，重新計算每個簇的新聚類中心;不斷重復這個過程，直到相鄰兩次的聚類中心沒有任何變化或聚類準則函數收斂。算法框架如下:

輸入:簇的數目k，包含n個對象的數據集

輸出:k個簇的集合

1) 令I=1，從D中任意選擇K個對象作為初始聚類中心yj(I)，j=1，2，…，k;

2) 計算每個對象與聚類中心的距離D(xi，yj(I))，(i=1，2，…，n，j=1，2，…，k)，如果滿足D(xi，yk(I))=min{D(xi，yj(I))，j=1，2，…，k}，則xi∈Sk，Sj表示劃分形成的簇;

3) 計算K個簇新的聚類中心:，j=1，2，…k，nj表示簇Sj的個數，xi表示簇Sj中的元素;

4) 判斷:若yj(I+1)≠yj(I)，j=1，2，…，k，則I=I+1，返回2);否則，算法結束。

從上面對算法的分析可知，k個初始聚類中心點的選取對聚類結果具有較大影響，因為在該經典算法中是隨機的選取任意k個點作為初始聚類中心。算法采用兩階段反復循環過程，算法結束的條件是不再有數據元素被重新分配。

對于一個大小為n的數據集，指定的聚類數為k，d是數據對象的維數，則一次迭代的時間耗費為:將每一個數據對象歸到離它最近的聚類中心所在的類，需要時間O(ndk);新類產生以后計算新的聚類中心所需的時間O(nd);而迭代次數則由數據集大小、聚類數以及數據分布情況決定，算法總的時間復雜度為O(ndk)。可見，k-means算法具有線性的時間復雜度，對于大數據集的處理，該算法是高效的，同時具有較好的可伸縮性。

但該算法主要面臨的問題為以下兩個方面:

1)在k-means算法中聚類數目k的確定十分重要，但這個k值的選定是非常難以估計的，很多時候我們事先并不知道給定的數據集應該分成多少個類別才最合適。

2)在k-means算法中，首先需要根據初始聚類中心來確定一個初始劃分，然后對初始劃分進行優化，這個初始聚類中心的選擇對聚類結果有較大影響。一旦初始值選擇的不好，算法極易陷入局部極小值點。

3.2k-means算法中初始聚類中心的選取

針對k-means算法隨機選取k個初始聚類中心的缺陷，有以下一些各種不同的初始聚類中心選取方法:

1)憑經驗知識選取有代表性的點作為起始聚類中心。根據個體性質，觀察數據結構，選出比較合適的代表點。

2)隨機選取不同的初始值多次執行算法，然后根據聚類準則函數，選取最好的結果。

3)采用多次取樣數據集二次聚類以獲取最優初值的思想[9](對多次提取的樣本聚類產生新的多組聚類中心，并對這些聚類中心再次聚類，比較聚類結果從而得到最優的初值)。

4)由K-1類聚類問題解出K類問題的代表點。例如，先把全部樣本看成一個類，樣本總均值點就是第1類的初始聚類中心;然后，由一類的初始聚類中心和離它最遠的一個樣本作為兩類的初始聚類中心;依此類推，由K-1類的代表點和離他們最遠的一個樣本點作為K類問題的初始聚類中心。

5)按最大最小距離聚類法思想，尋找聚類中心的方法確定初始聚類中心[10](下文詳述)。

3.3 最大最小距離法確定初始聚類中心

最大最小距離法[10]是一種基于試探的算法，思想是取盡可能離得遠的對象作為初始聚類中心，避免了k-means算法隨機初值選取時可能出現的聚類種子過于鄰近的情況，不僅智能地確定初始聚類種子的個數，而且得到數據集一個比較好的初始劃分。最大最小距離法確定初始聚類中心的過程如下:

給定N個對象數據集，Sn={Z1，Z2，…，Zn}

1)任取一個對象，例如Z1。把Z1作為第一個類的中心，從集合Sn中找出到Z1距離最大的對象作為Z2。

2)對Sn中剩余對象Zi，分別計算到Z1，Z2的距離。令其中較小的那個為DZi。

3)計算maxSn{DZi}。若maxSn{DZi}>θ×(|Z2-Z1|)，則取Zi為新的聚類中心。θ為最大最小距離法參數，通常取(0.5≤θ<1)。

4)重復同樣的處理，直到再找不到符合條件的新的聚類中心。

設樣本規模為N，每次尋找新的聚類中心時，要進行N次距離計算。若共找到K個聚類中心，則算法結束時共進行的計算次數為 。最大最小距離法的計算量取決于N的規模，若直接將最大最小距離法用于初始數據集，執行效率很低。

利用文獻[9，11]中抽取樣本集的思想，將最大最小距離法與抽樣技術相結合，以此來減小計算規模。樣本集的代表性和規模簡約性，使得基于最大最小距離的初始中心優化方法的優點充分發揮出來，得出的最佳初始聚類中心能很好地逼近全局最小值。

為了盡可能使取樣后的數據既不失真，又能充分體現和代表數據集的原始分布特征，對原數據集采用T次取樣，得到T個樣本數據{S1，S2，…，St}，分別在每個樣本集上采用最大最小距離法得到T組近似初始聚類中心，再將T組聚類中心合并，在該集合上再次運用最大最小距離法得到K個最佳初始聚類中心。初始聚類中心選取方法流程圖如圖2所示。

將通過上述方法得出的k個初始聚類中心作為k-means算法的輸入，可得到更為穩定且有效的聚類結果，因為聚類中心不再是隨機選取，而是以一定的準則進行多次抽樣、計算和選擇。采用最大最小距離法搜索的初始聚類中心的個數，可能比預期的簇的個數k要大，因此可將相對臨近的初始中心合并，該算法可以發現延伸狀或不規則狀的簇，而傳統的k-means算法對此效果不佳，只適合發現球狀簇的數據集。

4 結束語

文檔聚類技術在文本挖掘和信息檢索領域中占有重要地位，這也是本文研究的價值所在。本文首先給出一個文檔聚類過程的模型，然后對基于向量空間的文本特征表示進行了詳細介紹，并對特征詞條權重評價函數進行了分析，結合Web文檔結構特性，根據特征詞條的不同位置對文檔內容的決定程度不同，對詞條權重評價函數進行了優化。重點分析了適合大量文檔處理的基于劃分的聚類算法——k-means算法的優缺點，介紹了采用基于最大最小距離法的思想并結合抽樣技術，來選擇初始聚類中心，以此作為k-means算法的輸入，從而改善最終的聚類結果。

參考文獻:

[1] Han J W，Kamber M.數據挖掘概念與技術[M].范明，孟小峰，譯.2版.北京:機械工業出版社，2007:251-272，401-410.

[2] Salton G，Wong A，Yang C S.A Vector Space Model for Automatic Indexing[J].Communications of the ACM，1975，18(11):613-620.

[3] 姚清耘，李功申，李翔.基于向量空間模型的文本聚類算法[J].計算機工程，2008，34(18):39-41，44.

[4] 王繼成，潘金貴，張福炎.Web文本挖掘技術研究[J].計算機研究與發展，2000，37(5):513-520.

[5] Larsen B，Aone C.Fast and effective text mining using linear-time document clustering[C].San Diego，CA:Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，1999:16-22.

[6] Markov Z，Daniel T.Larose.Data Mining the Web:Uncovering Patterns in Web Content，Structure，and Usage[M].New Jersey:John Wiley sons，Inc，2007:13-42，61-85.

[7] Kanungo T，Mount D M，Netanyahu N S.An efficient K-means clustering algorithm:analysis and implementation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24(7):881-892.

[8] Papineni K.Why inverse document frequency[C].2nd Meeting of the North American Chapter of the Association for Computational Linguistics on Language Technologies，Pittsburgh，2001:l-8.

[9] Fayyed U，Reina C，Bradley P S.Initialization of Iterative Refinement Clustering Algorithms[R].Microsoft Research Technical Report MSR-TR-98-38，1998.

[10] 周涓，熊忠陽，張玉芳，等.基于最大最小距離法的多中心聚類算法[J].計算機應用，2006，26(6):1425-1427.

[11] Bradley P，Fayyad U.Refining initial points for K-means clustering[C].15th International Conference on Machine Learning.San Francisco，1998:91-99.

[12] 王子興，馮志勇.Web文檔聚類中K-means算法的一種改進算法[J].微型電腦應用:研究與設計，2007，23(8):6-8.