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

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

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

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

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

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

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

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

1k-means算法簡(jiǎn)介

　　k-means算法是一種基于分割的聚類(lèi)算法?；诜指畹木垲?lèi)算法可以簡(jiǎn)單描述為:對一個(gè)對象集合構造一個(gè)劃分,形成k個(gè)簇,使得評價(jià)函數最優(yōu)。不同的評價(jià)函數將產(chǎn)生不同的聚類(lèi)結果,k-means算法通常使用的評價(jià)函數為:

　　k-means算法的具體過(guò)程如下:

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

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

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

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

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