Web文檔聚類中k-means算法的改進

2 k-means算法的分析及其改進

2.1 權重評價函數的改進

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

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

　　對于Web文檔而言,由于XML(可擴展標識語言)已經成為Web上新一代數據內容描述標準,因此Web上的文檔聚類應體現XML文檔的特性。XML文檔中的基本單位是元素(element)。元素由起始標簽、元素的文本內容和結束標簽組成。它的語法格式為:

　　標簽> 文本內容

　　基于XML的Web文檔中,用戶把要描述的數據對象放在起始標簽和結束標簽之間,無論文本的內容多長或者多么復雜,XML都可以通過元素的嵌套進行處理。不同標簽下,同一個詞條也可能有不同含義。由此可見,XML文檔中不同位置的詞條對文檔內容的決定程度會有很大的不同。

　　通常,一個文檔的標題、摘要、關鍵詞以及段首和段尾出現的詞條對整個文檔內容有很大的決定作用。在XML文檔中,通過標簽可以得出詞條對文檔內容的決定程度,但很難對這種決定程度進行準確的定義。因此,本文利用模糊集理論,根據XML文檔特性計算詞條從屬關系系數,并且將其量化為介于0和1之間的隸屬度,加入到原有權重評價函數,從而表明XML文檔具有該詞條特征的程度。

　　為了簡化計算,詞條在文檔中出現的位置主要分為標題、摘要、關鍵詞、段首尾、特殊標識處和正文幾個部分。其相應權重為σ_t,在[0,1]之間取值,用lt表示詞條在相應位置出現的次數。加入了詞條隸屬度的權重評價函數為:

2.2 相似性度量的改進

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

　　如此高維的特征向量使得聚類算法的處理時間大大增加,同時對算法的準確性產生不利影響,并且這些特征對于聚類來說大多是無用的,例如聚類算法STC(Suffix Tree Clustering)將特征向量的維數減少到幾十維仍然能夠準確聚類。這主要是因為,對于非結構化的文檔,體現其類別特點的特征詞有很多,當進行某一方面的聚類時,與此無關的特征詞就成了噪音。從這一點來說,文中前面改進的權重評價函數體現了特征詞對文檔內容的貢獻程度,從而突出了與聚類相關的特征詞,降低了無關特征詞的干擾。另一方面,過多的特征詞使得特定的特征詞出現的頻率較低,容易被噪音所淹沒。

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