Web文檔聚類中k-means算法的改進

介紹了Web文檔聚類中普遍使用的、基于分割的k-means算法,分析了k-means算法所使用的向量空間模型和基于距離的相似性度量的局限性,從而提出了一種改善向量空間模型以及相似性度量的方法。

　　關鍵詞: 文檔聚類 k-means算法 向量空間模型 相似性度量

　　Internet的快速發展使得Web上電子文檔資源在幾年間呈爆炸式增長,與數據庫中結構化的信息相比,非結構化的Web文檔信息更加豐富和繁雜。如何充分有效地利用Web上豐富的文檔資源,使用戶能夠快速有效地找到需要的信息已經成為迫切需要解決的問題。

　　聚類能夠在沒有訓練樣本的條件下自動產生聚類模型。作為數據挖掘的一種重要手段,聚類在Web文檔的信息挖掘中也起著非常重要的作用。文檔聚類是將文檔集合分成若干個簇,要求簇內文檔內容的相似性盡可能大,而簇之間文檔的相似性盡可能小。文檔聚類可以揭示文檔集合的內在結構,發現新的信息,因此廣泛應用于文本挖掘與信息檢索等方面。

　　文檔聚類算法一般分為分層和分割二種,普遍采用的是基于分割的k-means算法。

　　k-means算法具有可伸縮性和效率極高的優點,從而被廣泛地應用于大文檔集的處理。針對k-means算法的缺點,許多文獻提出了改進方法,但是這些改進大多以犧牲效率為代價,且只對算法的某一方面進行優化,從而使執行代價很高。

　　k-means算法中文檔表示模型采用向量空間模型(VSM),其中的詞條權重評價函數用TF*IDF表示。然而實際上這種表示方法只體現了該詞條是否出現以及出現多少次的信息,而沒有考慮對于該詞條在文檔中出現的位置及不同位置對文檔內容的決定程度不同這一情況。另一方面,k-means算法使用基于距離的相似性度量,然而文檔的特征向量一般超過萬維,有時可達到數十萬維,這種高維度使得這種度量方法不再有效。針對以上問題,本文提出相應的解決方法,即改進的k-means算法。實驗表明改進后的k-means算法不僅保留了原算法效率高的優點,而且聚類的平均準確度有了較大提高。

1k-means算法簡介

　　k-means算法是一種基于分割的聚類算法。基于分割的聚類算法可以簡單描述為:對一個對象集合構造一個劃分,形成k個簇,使得評價函數最優。不同的評價函數將產生不同的聚類結果,k-means算法通常使用的評價函數為:

　　k-means算法的具體過程如下:

　　(1)選取k個對象作為初始的聚類種子;

　　(2)根據聚類種子的值,將每個對象重新賦給最相似的簇;

　　(3)重新計算每個簇中對象的平均值,用此平均值作為新的聚類種子;

　　(4)重復執行(2)、(3)步,直到各個簇不再發生變化。

　　k-means算法的復雜度為:O(nkt)。其中:n為對象個數,k為聚類數,t為迭代次數。通常k、t n,所以k-means算法具有很高的效率。同時k-means算法具有較強的可伸縮性,除了生成k個聚類外,還生成每個聚類的中心,因此被廣泛應用。