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

　　利用向量空間模型對(duì)文檔進(jìn)行聚類只能根據(jù)文檔的二種信息:(1)文檔中每個(gè)特征詞出現(xiàn)的頻率;(2)文檔的長(zhǎng)度。由于文檔長(zhǎng)度與文檔所屬的類別之間的關(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)了文檔之間的差異,而且定量地描述了這種差異性,從而為文檔的聚類提供了依據(jù)。下面通過(guò)對(duì)具體的Web文檔進(jìn)行實(shí)驗(yàn)并進(jìn)一步地驗(yàn)證。

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

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

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

　　試驗(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)確度則比原算法有了普遍提高,尤其在正確指定聚類數(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算法要依賴原始聚類數(shù)k的選擇。如何為初始文檔集選擇合適的聚類數(shù)k以及進(jìn)一步提高平均準(zhǔn)確度是今后改進(jìn)k-means算法的主要研究方向。