殷 碩，王衛(wèi)亞，柳有權(quán)

(長安大學 信息工程學院，陜西 西安 710064)

0 引 言

文本聚類是將大規(guī)模文本按照某種表示模型劃分為多個簇，使得同一個簇中的文本之間相似度盡可能大，不同簇中的文本之間相似度盡可能小[1]。文本聚類中最重要的兩個步驟是：特征選取和利用特征進行相似度判斷[2]。常見的文本聚類有基于向量空間模型的文本聚類和基于潛在語義索引的文本聚類[3]等。其中以向量空間模型[4](vector space model，VSM)作為文本表示模型，并使用TF-IDF(term frequency-inverse document frequency)作為模型中元素的權(quán)重的文本聚類方法應(yīng)用最為廣泛，比如文獻[5]提出了一種基于K-Means和VSM的聚類算法，利用VSM模型計算文本相似度，從而實現(xiàn)文本聚類算法。但是使用VSM作為文本表示模型會產(chǎn)生兩個問題：一是表示文本的向量維度過高，導致算法復雜度過高；二是VSM模型缺乏詞語的語義信息。VSM向量維度過高的問題通常采用降維策略，對文本進行特征抽取[6-8]或者挖掘頻繁項集作為特征信息[9-10]的方法降低數(shù)據(jù)的維度。

文中將《知網(wǎng)》[11]作為語義詞典引入到文本聚類中，提出一種既能降低向量維度，又能彌補VSM所缺少的語義信息的聚類方法。該方法首先改進詞語語義相似度算法，其次在詞語語義相似度的基礎(chǔ)上對文本進行語義特征抽取，降低文本表示模型的維度，以及完成對簇的語義特征抽取，最后通過計算抽取的特征集合之間的相似度，完成文本聚類。

1 詞語語義相似度算法改進

1.1 義原相似度算法

《知網(wǎng)》將義原分為了幾個大類，類與類之間不存在交集。通過義原之間的上下位關(guān)系，為每一個類構(gòu)建出一棵義原層次樹，不同義原層次樹之間不存在可達路徑。在知網(wǎng)中義原層次樹部分示意圖見圖1。

圖1 義原層次樹示意圖

朱新華[12]提出了綜合義原層次樹的深度以及密度因素計算義原相似度的公式，在一定程度上提高了詞語語義相似度的準確性，具體公式為：

(1)

其中，p1和p2為兩個義原，α為可調(diào)節(jié)參數(shù)，N為可達路徑長度，level(i)為可達路徑上的邊在義原層次樹中的層次，LCN為兩個義原在層次樹中的最小公共父節(jié)點，f(·)為當前節(jié)點的密度信息，其值為所有的兄弟節(jié)點的個數(shù)(含自身)除以義原層次樹的總節(jié)點個數(shù)，weight(·)函數(shù)為每一條邊的權(quán)重，定義為：

(2)

其中，depth為義原層次樹的高度，θ為調(diào)節(jié)參數(shù)，與樹高depth成反比，經(jīng)過實驗驗證取θ=4，i為當前所在的層次。

1.2 義項相似度計算

義項是使用知識表示語言進行描述的，通過對《知網(wǎng)》知識描述語言進行分析，劉群[13]按照描述形式的不同將描述義項的義原分為4個集合：

通過計算相同類型集合的相似度，再對其進行加權(quán)求和得到兩個義項之間的相似度。具體公式為：

(3)

其中，S1和S2為兩個義項，simj(S1,S2)為第j類集合的相似度，βi為對集合相似度的加權(quán)，且滿足β1+β2+β3+β4=1，β1>β2>β3>β4。

1.3 詞語相似度計算

假設(shè)現(xiàn)有兩個詞語W1和W2，詞語W1有n個義項，即s11,s12,…,s1n；詞語W2有m個義項，即s21,s22,…,s2m，在計算詞語之間的相似度時，首先需要進行消歧，具體消歧算法后面進行討論。在經(jīng)過消歧之后，得到兩個詞語唯一的義項S1和S2，W1和W2之間的相似度就是S1和S2之間的相似度。

2 基于語義特征抽取的文本聚類算法研究

2.1 詞語語義相似度改進

雖然文獻[12]在計算詞語相似度時使用了義原層次樹的密度信息，但是卻沒有考慮到可達路徑上所有節(jié)點的密度對相似度的影響。所有子節(jié)點是對父節(jié)點所表達的概念的進一步細分，比如“植物”的子節(jié)點有“水果”、“花草”、“樹”等，所以密度越大代表細分的程度越大?？蛇_路徑上的所有節(jié)點都比正在計算相似度的節(jié)點在樹中的層次高，即在可達路徑上的所有節(jié)點都是這兩個節(jié)點中某一個的父節(jié)點，父節(jié)點的密度越大，在一定程度上也影響著子節(jié)點的分類細致程度。所以，文中將結(jié)合可達路徑上的所以節(jié)點的密度，并對其進行加權(quán)再求和，得義原相似度計算時的密度部分：

(4)

(5)

通過上述處理，得到新的義原相似度計算函數(shù)：

(6)

其中，c1和c2是平衡深度和密度對相似度影響的權(quán)重因子，經(jīng)過實驗，文中取c1=0.7，c2=0.3。

2.2 文本預(yù)處理

2.2.1 文本內(nèi)容分詞

對于一篇文本，并不是所有的詞語都是有實際意義的。中文包含許多停用詞、虛詞等，所以需要對文本進行分詞、去停用詞、去虛詞等操作。文中使用NLPIR-ICTCLAS[14]分詞系統(tǒng)進行分詞，首先對NLPIR-ICTCLAS提供的二次開發(fā)接口進行編程對文本進行分詞，再利用停用詞表、虛詞表對分詞結(jié)果進行過濾，得到分詞過后的詞集。

2.2.2 基于語義相似度的詞語消歧算法

中文包含多義詞，多義詞在《知網(wǎng)》中具有多個義項，所以需要對多義詞進行消歧，確定詞語唯一的義項。筆者認為，多義詞在一個句子中的義項應(yīng)該是唯一的，在多義詞的所有義項中，需要確定的義項與其他已經(jīng)確定了義項的詞語之間的相似度是最大的。具體的消歧算法如下：

(1)獲得多義詞W的所有義項(s1,s2,…,sm)，以及句子中已經(jīng)確定了義項的詞語集合(W1,W2,…,Wn)；

(2)令W的所有義項的初始權(quán)重都為0；

(3)依次計算Wi的義項和(s1,s2,…,sm)之間的相似度，如果Wi和sj之間的相似度最大，則對sj的權(quán)重加1，其中1≤i≤n，1≤j≤m；

(4)比較(s1,s2,…,sm)的權(quán)重，選擇權(quán)重最大的義項為W的唯一義項。

通過上述算法，確定多義詞在一個句子中的唯一義項。但是在一篇正文中，多義詞可能會出現(xiàn)在多個句子中，而且所有句子中的義項不一定相同。針對這種情況，文中采取如下做法：

(1)計算每個義項在正文中所出現(xiàn)的次數(shù)；

(2)選取出現(xiàn)次數(shù)最多的義項作為多義詞在正文中的唯一義項。

2.3 文本語義特征抽取

如果直接使用2.2中得到的文本詞集作為文本表示模型會出現(xiàn)兩個問題：一是由于模型維度過高而導致算法復雜度過高，二是詞集中含有大量與文本主題無關(guān)的詞語，會降低聚類的精準度。所以需要對預(yù)處理后的文本詞集進行語義特征抽取，在獲得文本主題相關(guān)的特征項的同時，也可以降低模型維度。

2.3.1 語義特征壓縮

文本的主題是通過一系列主題詞進行描述的，而主題詞之間則具有較大相似度，通過詞語之間的語義相似度，可以獲取到文本的主題詞集合d，具體算法為：

(3)在S中，將相似度Sij≥μ的詞Wi和Wj所在的集合合并，其中μ表示語義相似度閾值，相似度大于μ的兩個詞語歸為同一集合；

(4)最后選取元素最多的一個集合作為文本主題詞集合d。

2.3.2 文本特征抽取

在獲取到文本的主題詞集合d之后，需要根據(jù)主題詞的權(quán)重抽取出文本的特征集。由于進行了語義壓縮，筆者認為語義因素比詞語的頻數(shù)因素更加重要，所以對TF-IDF進行調(diào)整之后提出如下公式計算主題詞的權(quán)重：

(7)

其中，Ni為包含詞Wi的文本個數(shù)，N為文本總數(shù)。

在計算出所有主題詞的權(quán)重之后，選取權(quán)重降序排序的前15個詞作為文本的特征詞集，主題詞的權(quán)重僅僅作為特征選擇的依據(jù)，并不參與文本相似度計算。通過特征詞集建立文本表示模型Di={Wi1,Wi2,…,Win}，其中Di為文本集中的第i個文本，Wik為Di的第k個特征項。由于特征詞都是經(jīng)過語義壓縮以及主題詞權(quán)重排序抽取得到的，所以文中所有特征詞具有相同的語義權(quán)重。

2.4 文本語義相似度計算

假設(shè)有兩個文本表示模型Di={Wi1,Wi2,…,Win}和Dj={Wj1,Wj1,…,Wjm}，且m≥n，語義相似度算法為：

(1)采用完備二部圖的構(gòu)造方法，將兩個模型的特征集的元素作為二部圖中的兩個頂點集合，建立連接，Di和Dj所構(gòu)成的二部圖如圖2所示。

(a)計算Di部每個頂點和Dj部每個頂點的相似度，把它作為兩個頂點的邊的權(quán)值，所有邊的權(quán)值集合記為S；

(b)從S中選取權(quán)值最大的邊{Wip,Wjq}加入集合L，并從頂點集合中刪除頂點Wip和Wjq以及從S中刪除所有與之相關(guān)的邊；

(c)重復(b)，直到Dj部中的頂點為空。

圖2 兩個文本模型構(gòu)成的二部圖

(2)由集合L中的邊的權(quán)值得出文本表示模型的相似度計算方法：

0.1*(m-n))

(8)

其中，0.1*(m-n)是當m>n的情況出現(xiàn)時，Wi中元素與空對應(yīng)，賦予一較小常數(shù)。

2.5 簇的語義特征抽取

(1)將C中所有文本的特征抽取出來，組成向量D'={(W1,F1),(W2,F2),…,(Wn,Fn)}，其中Fi為所有文本中Wi出現(xiàn)的頻數(shù)；

(2)類似于文本特征抽取算法，計算D'中所有詞語的兩兩相似度，找到相似度大于閾值μ的最大集合d'；

(3)選取d'中頻數(shù)降序排序的前30個詞作為簇的特征集。

與2.2類似，這里的頻數(shù)僅僅作為簇的特征抽取的依據(jù)，并不參與簇的相似度計算，簇中的特征項具有相同的語義權(quán)重。獲取到簇的特征集之后，將簇的表示模型定義為C={W1,W2,…,Wn}，與文本表示模型形式相同，所以簇之間的相似度計算類似于文本相似度計算，以下不再描述。

2.6 文本聚類算法設(shè)計

假設(shè)現(xiàn)有文本數(shù)量為N，需要將這N篇文本進行聚類，使之被分在不同的集合中，不同的集合代表不同的簇。首先利用文中提出的文本語義特征抽取算法抽取每個文本的特征集，初始情況下，將這N個文本視為N個集合，即N個簇，每個簇的特征集為對應(yīng)文本的特征集。計算所有簇兩兩之間的相似度sim(Ci,Cj)，如果相似度大于閾值，則將兩個簇進行合并，并重新抽取新簇的特征。如果兩次迭代之后簇的個數(shù)不變，則終止該算法。具體描述為：

(1)抽取每個文本的特征集；

(2)將N個文本初始化為N個簇，每個簇的特征集為對應(yīng)的文本的特征集；

(3)計算簇之間的兩兩相似度，如果兩個簇的相似度大于閾值α，則將兩個簇合并；

(4)根據(jù)簇的語義特征抽取算法更新所有簇的特征集；

(5)重復步驟(3)和步驟(4)，直到兩次迭代之后簇的個數(shù)不變。

3 實驗與分析

3.1 實驗數(shù)據(jù)獲取

使用爬蟲程序在新浪新聞網(wǎng)站中爬取財經(jīng)、旅游、教育、文化、軍事5個類別各400篇網(wǎng)頁，共2 000篇作為實驗數(shù)據(jù)。

3.2 聚類實驗

為了檢驗所提出的聚類算法的優(yōu)劣性，使用準確率(Precision,P)、召回率(Recall,R)和F1度量值作為評價指標，具體公式如下：

(9)

(10)

(11)

其中，a、b、c所表示的含義如表1所示。

表1 評價指標參數(shù)

實驗之前，首先需要確定文本特征抽取和簇特征抽取過程中所使用的閾值μ，以及聚類算法中不同簇之間的相似度閾值α。文中參考劉懷亮[15]所使用的詞語相似度閾值，令μ=0.8。然后需要確定閾值α的最佳值，圖3顯示了不同閾值α下對聚類結(jié)果的影響。

圖3 不同閾值對聚類的影響

當0.6≤α≤0.7時，F(xiàn)1度量值隨著α的增大而增大，表明聚類效果越來越好。主要原因是當閾值α變大時，不同簇之間的區(qū)分度也越來越大，所以聚類效果也在逐步提升。當0.7≤α≤0.85時，F(xiàn)1度量值隨著α的減小而減小，表明聚類效果反而降低了。主要原因是當閾值α變得過大時，原本應(yīng)當合并為一個新簇的兩個簇的相似度卻達不到閾值α，所以聚類效果逐步降低。

在設(shè)定簇相似度閾值α=0.7之后，添加文獻[5]基于K-Means和VSM的聚類算法作為對比，表2為兩種算法中每個類別文本的所有特征維度比較。

表2 特征集維度比較

由表2可以得出，文中提出的文本表示模型相較于傳統(tǒng)的VSM文本表示模型在維度方面有著極大的優(yōu)勢，主要因為文中使用語義對特征詞進行了抽取，每一個文本的特征詞數(shù)量都不會超過15，而VSM則將所有詞語所組成的向量作為文本表示模型，使向量維度極大。

表3為兩種算法的準確率、召回率和F1度量值的對比。

表3 實驗結(jié)果對比

由表3可以得出，文中提出的算法相較于文獻[5]的算法在準確率、召回率和F1度量值上都有所提高，其原因主要有兩點：一是加入了語義信息，彌補了VSM文本模型中語義缺失的問題，使詞語相似度更符合人類主觀判斷的結(jié)果，二是通過語義對文本特征進行了抽取，使特征項都是主題相關(guān)的，減少了主題無關(guān)詞語對文本相似度的影響，從而得到了更加準確的文本相似度。

4 結(jié)束語

文中提出一種基于語義特征抽取的文本聚類算法，使用詞語的語義信息和詞語權(quán)重對文本的特征項進行了抽取，不僅可以降低文本表示模型的維度，同時所抽取的特征都是主題相關(guān)的，彼此之間有著很大的關(guān)聯(lián)。通過計算文本表示模型之間的相似度使同一類的文本聚集到同一個簇中，并更新簇的特征，使簇的特征值可以更好地體現(xiàn)簇中文本主題。通過實驗分析，提出的聚類算法不僅能大幅降低文本表示模型的維度，而且聚類效果提升也比較明顯。