Web文檔聚類中k-means算法的改進(jìn)

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

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

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

　　聚類能夠在沒有訓(xùn)練樣本的條件下自動產(chǎn)生聚類模型。作為數(shù)據(jù)挖掘的一種重要手段,聚類在Web文檔的信息挖掘中也起著非常重要的作用。文檔聚類是將文檔集合分成若干個簇,要求簇內(nèi)文檔內(nèi)容的相似性盡可能大,而簇之間文檔的相似性盡可能小。文檔聚類可以揭示文檔集合的內(nèi)在結(jié)構(gòu),發(fā)現(xiàn)新的信息,因此廣泛應(yīng)用于文本挖掘與信息檢索等方面。

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

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

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

1k-means算法簡介

　　k-means算法是一種基于分割的聚類算法?；诜指畹木垲愃惴梢院唵蚊枋鰹?對一個對象集合構(gòu)造一個劃分,形成k個簇,使得評價函數(shù)最優(yōu)。不同的評價函數(shù)將產(chǎn)生不同的聚類結(jié)果,k-means算法通常使用的評價函數(shù)為:

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

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

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

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

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

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