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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2  k-means算法的分析及其改進(jìn)

2.1 權(quán)重評(píng)價(jià)函數(shù)的改進(jìn)

　　k-means算法采用向量空間模型(VSM)將Web文檔分解為由詞條特征構(gòu)成的向量,利用特征詞條及其權(quán)重表示文檔信息。向量d=(ω₁,ω₂,ω₃,∧,ωm)表示文檔d的特征詞條及相應(yīng)權(quán)重。其中:m為文檔集中詞條的數(shù)目,ω_i(i=1,∧,m)表示詞條t_i在文檔d中的權(quán)重。特征權(quán)重ωi的計(jì)算通常采用經(jīng)典的TF*IDF算法,并進(jìn)行規(guī)格化處理:

　　其中:TF表示該詞條t_i在文檔d中的頻數(shù),DF_i表示文檔集中包含詞條t_i的文檔數(shù),N表示文檔集中的文檔數(shù)。從公式(2)可以看出,這種特征權(quán)重的計(jì)算方法是把文檔當(dāng)做一組無(wú)序詞條,詞條特征權(quán)重只是體現(xiàn)了該詞條是否出現(xiàn)以及出現(xiàn)次數(shù)多少的信息,而對(duì)于詞條在文檔中的不同位置對(duì)文檔內(nèi)容的決定程度不同這一問(wèn)題卻未加考慮。

　　對(duì)于Web文檔而言,由于XML(可擴(kuò)展標(biāo)識(shí)語(yǔ)言)已經(jīng)成為Web上新一代數(shù)據(jù)內(nèi)容描述標(biāo)準(zhǔn),因此Web上的文檔聚類(lèi)應(yīng)體現(xiàn)XML文檔的特性。XML文檔中的基本單位是元素(element)。元素由起始標(biāo)簽、元素的文本內(nèi)容和結(jié)束標(biāo)簽組成。它的語(yǔ)法格式為:

　　<標(biāo)簽> 文本內(nèi)容

　　基于XML的Web文檔中,用戶(hù)把要描述的數(shù)據(jù)對(duì)象放在起始標(biāo)簽和結(jié)束標(biāo)簽之間,無(wú)論文本的內(nèi)容多長(zhǎng)或者多么復(fù)雜,XML都可以通過(guò)元素的嵌套進(jìn)行處理。不同標(biāo)簽下,同一個(gè)詞條也可能有不同含義。由此可見(jiàn),XML文檔中不同位置的詞條對(duì)文檔內(nèi)容的決定程度會(huì)有很大的不同。

　　通常,一個(gè)文檔的標(biāo)題、摘要、關(guān)鍵詞以及段首和段尾出現(xiàn)的詞條對(duì)整個(gè)文檔內(nèi)容有很大的決定作用。在XML文檔中,通過(guò)標(biāo)簽可以得出詞條對(duì)文檔內(nèi)容的決定程度,但很難對(duì)這種決定程度進(jìn)行準(zhǔn)確的定義。因此,本文利用模糊集理論,根據(jù)XML文檔特性計(jì)算詞條從屬關(guān)系系數(shù),并且將其量化為介于0和1之間的隸屬度,加入到原有權(quán)重評(píng)價(jià)函數(shù),從而表明XML文檔具有該詞條特征的程度。

　　為了簡(jiǎn)化計(jì)算,詞條在文檔中出現(xiàn)的位置主要分為標(biāo)題、摘要、關(guān)鍵詞、段首尾、特殊標(biāo)識(shí)處和正文幾個(gè)部分。其相應(yīng)權(quán)重為σ_t,在[0,1]之間取值,用lt表示詞條在相應(yīng)位置出現(xiàn)的次數(shù)。加入了詞條隸屬度的權(quán)重評(píng)價(jià)函數(shù)為:

2.2 相似性度量的改進(jìn)

　　利用向量空間模型處理Web文檔時(shí),由于文檔的繁雜性,表示文檔的特征向量可以達(dá)到數(shù)萬(wàn)維,甚至更多。通過(guò)預(yù)處理階段停用詞和無(wú)用高頻詞的過(guò)濾后,特征向量的維數(shù)雖然顯著減少,但剩余的維數(shù)仍然很多。本文實(shí)驗(yàn)中選用的娛樂(lè)類(lèi)1500篇Web文檔在預(yù)處理后特征向量的維數(shù)仍然達(dá)到了8291維。

　　如此高維的特征向量使得聚類(lèi)算法的處理時(shí)間大大增加,同時(shí)對(duì)算法的準(zhǔn)確性產(chǎn)生不利影響,并且這些特征對(duì)于聚類(lèi)來(lái)說(shuō)大多是無(wú)用的,例如聚類(lèi)算法STC(Suffix Tree Clustering)將特征向量的維數(shù)減少到幾十維仍然能夠準(zhǔn)確聚類(lèi)。這主要是因?yàn)?對(duì)于非結(jié)構(gòu)化的文檔,體現(xiàn)其類(lèi)別特點(diǎn)的特征詞有很多,當(dāng)進(jìn)行某一方面的聚類(lèi)時(shí),與此無(wú)關(guān)的特征詞就成了噪音。從這一點(diǎn)來(lái)說(shuō),文中前面改進(jìn)的權(quán)重評(píng)價(jià)函數(shù)體現(xiàn)了特征詞對(duì)文檔內(nèi)容的貢獻(xiàn)程度,從而突出了與聚類(lèi)相關(guān)的特征詞,降低了無(wú)關(guān)特征詞的干擾。另一方面,過(guò)多的特征詞使得特定的特征詞出現(xiàn)的頻率較低,容易被噪音所淹沒(méi)。

　　k-means算法使用基于距離的相似性度量,通過(guò)計(jì)算文檔向量之間的距離表明文檔之間相似性的大小。通常采用的是余弦函數(shù),計(jì)算公式為:

[!--empirenews.page--]

　　利用向量空間模型對(duì)文檔進(jìn)行聚類(lèi)只能根據(jù)文檔的二種信息:(1)文檔中每個(gè)特征詞出現(xiàn)的頻率;(2)文檔的長(zhǎng)度。由于文檔長(zhǎng)度與文檔所屬的類(lèi)別之間的關(guān)系不大,因此可以把所有的文檔長(zhǎng)度進(jìn)行歸一化處理,從而使文檔向量具有統(tǒng)一的特征維數(shù)m。

　　其中:m為特征向量維數(shù),α_k為二個(gè)文檔對(duì)應(yīng)特征詞條的四位碼字的十進(jìn)制數(shù)值差的絕對(duì)值。由于這種相似性的計(jì)算使用的是整數(shù),所以計(jì)算速度和精度得到一定的提高。

　　可以利用簡(jiǎn)單的示例驗(yàn)證公式(5)的合理性。當(dāng)二個(gè)文檔完全相似時(shí),sim(d_i,d_j)的值等于1,而二個(gè)文檔完全不同時(shí)它的值為0。這種方法不僅反應(yīng)了文檔之間的差異,而且定量地描述了這種差異性,從而為文檔的聚類(lèi)提供了依據(jù)。下面通過(guò)對(duì)具體的Web文檔進(jìn)行實(shí)驗(yàn)并進(jìn)一步地驗(yàn)證。

3  實(shí)  驗(yàn)

　　實(shí)驗(yàn)用的文檔是從搜狐的中文網(wǎng)站上獲取的娛樂(lè)類(lèi)文檔,選用其中的1500篇。對(duì)這1500篇文檔進(jìn)行手工分類(lèi),如表1所示共分為10類(lèi)。

　　衡量信息檢索性能的召回率和精度也是衡量分類(lèi)算法效果的常用指標(biāo)。然而聚類(lèi)過(guò)程中并不存在自動(dòng)分類(lèi)類(lèi)別與手工分類(lèi)類(lèi)別確定的一一對(duì)應(yīng)關(guān)系,因此無(wú)法像分類(lèi)一樣直接以精度和召回率作為評(píng)價(jià)標(biāo)準(zhǔn)。為此本文選擇了平均準(zhǔn)確率作為評(píng)價(jià)的標(biāo)準(zhǔn)。平均準(zhǔn)確率通過(guò)考察任意二篇文章之間類(lèi)屬關(guān)系是否一致來(lái)評(píng)價(jià)聚類(lèi)的效果。

　　試驗(yàn)中對(duì)使用公式(3)和(5)的改進(jìn)k-means算法和原k-means算法的平均準(zhǔn)確度進(jìn)行了比較,實(shí)驗(yàn)結(jié)果如表2所示。

　　實(shí)驗(yàn)結(jié)果表明,改進(jìn)后的k-means算法與原k-means算法在運(yùn)行速度上基本相同甚至略快,平均準(zhǔn)確度則比原算法有了普遍提高,尤其在正確指定聚類(lèi)數(shù)k時(shí),平均準(zhǔn)確度提高了近7%,說(shuō)明此算法具有較高的準(zhǔn)確性。由于實(shí)驗(yàn)中使用的文檔集很小,所以改進(jìn)的算法優(yōu)勢(shì)不很明顯。

4 結(jié)束語(yǔ)

　　本文對(duì)k-means算法進(jìn)行了改進(jìn)。根據(jù)不同位置的特征詞條對(duì)文檔內(nèi)容的不同決定程度,提出一種新的文檔特征詞條的權(quán)重評(píng)價(jià)函數(shù),并在此基礎(chǔ)上提出一種文檔相似性的度量方法。實(shí)驗(yàn)表明改進(jìn)后的算法不僅保留了原k-means算法效率高的優(yōu)點(diǎn),而且在平均準(zhǔn)確度方面比原算法有了較大提高。實(shí)驗(yàn)還表明,k-means算法要依賴(lài)原始聚類(lèi)數(shù)k的選擇。如何為初始文檔集選擇合適的聚類(lèi)數(shù)k以及進(jìn)一步提高平均準(zhǔn)確度是今后改進(jìn)k-means算法的主要研究方向。