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

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

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

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

3實(shí) 驗

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

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

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

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

4結束語(yǔ)

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