基于FVSM的核聚類算法在文本聚類中的應用

楊延錕,許少華 (大慶石油學院計算機與信息技術學院,黑龍江大慶1 6331 8)

文本分類是文本信息處理的一個重要研究領域,對提高文本檢索、文本存儲等應用的處理效率有著重要意義[1,2]。如何提高文本分類器的識別率和推廣能力是文本信息處理面臨的問題。在傳統的向量空間模型 (Vector Space Model,VSM)中,文本被簡單地表示成向量,作為向量空間的一個點,然后通過計算向量間的距離決定向量類別的歸屬[3]。該模型的不足之處在于它一般不考慮向量中各個特征項在文檔中的位置信息,而只是簡單地根據詞頻統計公式獲取特征向量,這使得距離的計算不夠準確,從而導致分類精度不夠高。針對傳統VSM模型在文本特征表示方面的不足,筆者構造了基于文本特征的模糊向量空間模型 (Fuzzy Vector Space Model,FVSM),并利用Mercer核將文本的特征向量映射到高維特征空間,并在特征空間中進行聚類[4]。核聚類算法在性能上比經典的聚類算法有較大的改進,它通過非線形映射能夠較好的分辨、提取并放大有用的特征,從而實現更為準確的聚類。同時,算法收斂速度較快,在經典聚類算法失效情況下也能得到正確的聚類。以中國期刊網全文數據庫部分文檔數據為例進行試驗,試驗結果表明了該文本自動聚類方法的有效性。

1 文本模糊核聚類算法

1.1 模糊特征向量的構造方法

構造特征向量首先要構造一個特征項集。一個有效的特征項集,必須具備以下2個特征:①完全性。特征項能夠體現全部文檔內容。②區分性。根據特征項集,能將目標同其他文檔相區分。假設已經獲得一個滿足上述2個條件的特征項集。在文本特征向量的構造方面,傳統VSM模型或者對特征項集采用二值 (0,1)編碼,即特征向量是特征項的精確集合;或者對特征項集采用加權處理,以各特征項的權值構成特征向量,這雖然比二值編碼前進了一步,但權值的計算一般只與各特征項在文檔中出現的頻數有關,這樣部分高頻特征項的權值很容易對某些頻數過低的特征項權值產生一定的抑制作用,進而會影響聚類的效果。考慮到各個特征項在文檔中的地位及重要性的不同,筆者在構造特征向量時采用了模糊集合方法,給予每個特征項一定的隸屬度,即按其對反映主題的重要程度取 [0,1]區間值,構造模糊特征向量,這是符合實際情況的[5]。

設特征項集為{T1,T2,…,TN},特征項在某一文檔中出現的頻數采用模糊集合方法計算,則模糊特征向量可按如下原則構造[6]:

1)若特征項在原文中已被作者選為關鍵詞 (如果有的話),應給予隸屬度1;

2)若特征項在標題和摘要 (如果有的話)中出現,應給予較高的隸屬度;

3)若特征項出現在正文中的一些 “關鍵句”,即那些包含諸如 “關鍵在于……”、“旨在……”、“主要目的 (標)是……”等的句子,應給予較大的隸屬度;

4)若特征項出現在引言和結論段中,應給予一定的隸屬度;

5)若特征項出現在段首或段尾,應給予一定的隸屬度;

6)若特征項在正文中有較高的出現頻度,應隨著頻度的增加逐次增加其隸屬度;

7)若一個特征項同時處于上述多種地位,則其隸屬度以求和方式迭加;

8)若一個特征項的同義詞、近義詞或轉義詞出現時,應根據其間的語義聯系大小作為該特征項的一次或部分出現統計在出現頻數中;

9)構造特征向量時還應考慮特征項的專指度。特征項的專指度可用文檔總數與含有該特征項的文檔數的比值表示。專指度過低的特征項會抑制聚類的精確性。因此對于專指度較高的特征項,應適當增加其文檔頻數;而對于專指度較低的特征項,則應適當減小其文檔頻數。

根據上述原則,模糊特征向量的構造步驟如下:

1)分別對P篇文檔,按原則1)～8)計算特征項集{T1,T2,…,TN}中每個特征項的文檔頻數;

2)依原則9)按式(1)構造P篇文檔的特征向量{fT(Tp1),fT(Tp2),…,fT(TpN)},(p=1,2,…,P)。

式中,VTFpk表示特征項Tk在文檔p中的出現頻數;N表示全部訓練文本中的文檔數;Nk表示含有特征項Tk的文檔數目。

3)對以上特征向量歸一化,可得P篇文檔的模糊特征向量~Tp={Tp1,Tp2,…,TpN};(p=1,2,…,P)。

1.2 模糊核聚類算法基本原理

所謂的聚類就是已知一個數據項目集,將該集合劃分成一個類集,使得類內相似性最大,類間相似性最小。聚類屬于非監督模式識別問題,其特點是輸入空間的樣本沒有期望輸出。聚類的過程完全依賴于樣本之間的特征差別。傳統的聚類方法都沒有對樣本特征進行優化,而是直接利用樣本特征進行聚類。這就使得聚類的有效性在很大程度上取決于樣本的分布情況。例如一類樣本散布較大,而另一類樣本散布較小,傳統的聚類方法效果就比較差。如果樣本分布更加混亂,則聚類的結果就會面目全非。因此,對于文本聚類問題,筆者融合模糊向量的特征描述能力和核聚類方法強大的特征提取能力,提出模糊核聚類算法。首先,對文本特征進行模糊提取,構造了能夠合理描述文本內容的模糊特征向量;其次,針對構造的模糊特征向量,采用具有強大分辨能力的核聚類算法[7]完成文本聚類。該方法利用Mercer核,將輸入空間樣本映射到特征空間,增加對樣本特征的優化,使映射后的樣本具有更好的聚類形式。

假設輸入空間樣本Xk∈RN(k=1,2,…,L)被某種非線性映射Φ映射到某一特征空間得到Φ(X1),Φ(X2),…,Φ(XL),則特征空間中,向量的點積形式可以用Mercer核表示為:

特征空間中Euclidean距離可表示為:

式(3)可作為聚類相似度的度量函數。聚類準則是使的下面的目標函數最小:

式中,C是聚類類別數;Ni是第Ci類樣本的個數。依式(3)計算各樣本的類屬情況,同時迭代修正各類中心。當各類中心穩定時聚類結束。

1.3 模糊核聚類算法實施步驟

模糊核聚類算法實施步驟如下:

1)確定聚類類別數C,聚類誤差Emax,初始化聚類中心Wi(k),i=1,2,…,C;

2)按式(3)計算各樣本到聚類中心的距離(i=1,2,…,C;j=1,2,…,L):

令:

3)修改核矩陣Kxjwi(k),Kwi(k)wi(k):

4)計算誤差:

5)如果e＜Emax,停機;否則轉步2)。

最后得到的聚類結果是,若dji=1,則xj∈Wi(i=1,2,…,C;j=1,2,…,L)。

2 實際應用

作為該方法的一個應用,筆者選擇中國期刊網全文數據庫 (CNKI)作為測試樣本源。根據CNKI已有的分類情況,作者下載了8個主題類共960篇文檔作為測試語料庫。每個主題的語料包括120篇文檔。綜合全部文檔的特征,共抽取了72個關鍵詞 (每類9個,其中第1個為該類的類屬詞)組成特征項的集合。按照前述方法構造全部語料樣本的模糊特征向量。評價與測試文檔聚類效果需要2個重要指標,即召回率recall(Ci)和正確率precision(Ci):

式中,Tn為通過聚類算法被正確聚類為Ci類的文檔數目;N為未聚類之前屬于Ci類的文檔數目;Cn為通過聚類算法被聚類為Ci類的文檔數目。采用如下的高斯核函數實現式(3)的計算:

根據采集的文本類屬情況,聚類數取為8類,限定誤差取為0.001,限定迭代次數為500次。初始聚類中心取為前8個樣本。該算法的聚類結果如表1所示。

表1 模糊核聚類算法的聚類結果

由表1可以看出,每個主題的聚類正確率都在87%～95%之間。觀察表1可發現,召回率高的類正確率不一定高 (如語言文字類);而召回率低的類不見得正確率也低 (如文學藝術類);召回率和正確率可能同時較高 (如聲學物理、原子物理類)。這說明對于自身特征不明顯的召回率較低的主題類,盡管該方法有較低的自識能力,但卻有著較高的排斥能力;對于自身特征較明顯而易于與其他類產生特征交叉的主題類,該方法的自識能力較強,排斥能力較弱;而對于自身特征很明顯的主題類,召回率和正確率都比較高,模型表現出了良好的聚類能力。

為進一步說明該方法的有效性,筆者對全部960個模糊向量采用K-均值聚類方法進行聚類,并采用相同的限定誤差和迭代次數,初始聚類中心也取為前8個樣本。聚類結果如表2所示。

表2 K-均值聚類算法的聚類結果

表2聚類結果表明,筆者提出的模糊核聚類算法明顯優于K-均值聚類算法。

3 結 語

文本的自動聚類是信息處理領域中的一項重要研究課題,筆者對文本自動聚類作了探討,針對實際聚類問題中文本特征、類屬特征的模糊性及特征信息對于反映文本類別的重要性,提出了基于模糊向量空間模型的核聚類算法。由于對特征空間的描述,采用了模糊數學方法,充分考慮了各個特征在反映文本主題上的重要性,增強了該方法對復雜聚類問題的適應性。試驗結果表明,該方法取得了很好的聚類效果。但在文本特征的抽取及賦值、聚類模型的完善、學習算法的改進、權重評價等許多方面還有待于進一步研究。

[1]何新貴.模糊知識處理的理論與技術 [M].第2版.北京:國防工業出版社,1998.

[2]何新貴,彭甫陽.中文文本的關鍵詞自動抽取和模糊分類[J].中文信息學報,1999,13(1):9～15.

[3]周濤,張艷寧,袁和金,等.粗糙核k-means聚類算法 [J].系統仿真學報,2008,20(4):921～925.

[4]周林峰,丁永生.基于遺傳算法的Mercer核聚類方法 [J].模式識別與人工智能,2006,19(3):307～311.

[5]索紅光,王玉偉.基于參考區域的k-means文本聚類算法 [J].計算機工程與設計,2009,(2):401～403,407.

[6]普運偉,朱明,金煒東,等.核聚類算法最佳聚類數的自適應確定方法 [J].計算機工程,2007,33(4):11～13.