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

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

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

0 引 言

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

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

1 詞語語義相似度算法改進(jìn)

1.1 義原相似度算法

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

圖1 義原層次樹示意圖

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

(1)

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

(2)

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

1.2 義項(xiàng)相似度計(jì)算

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

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

(3)

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

1.3 詞語相似度計(jì)算

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

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

2.1 詞語語義相似度改進(jìn)

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

(4)

(5)

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

(6)

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

2.2 文本預(yù)處理

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

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

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

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

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

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

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

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

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

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

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

2.3 文本語義特征抽取

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

2.3.1 語義特征壓縮

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

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

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

2.3.2 文本特征抽取

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

(7)

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

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

2.4 文本語義相似度計(jì)算

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

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

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

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

(c)重復(fù)(b)，直到Dj部中的頂點(diǎn)為空。

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

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

0.1*(m-n))

(8)

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

2.5 簇的語義特征抽取

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)獲取

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

3.2 聚類實(shí)驗(yàn)

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

(9)

(10)

(11)

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

表1 評價(jià)指標(biāo)參數(shù)

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

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

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

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

表2 特征集維度比較

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

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

表3 實(shí)驗(yàn)結(jié)果對比

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

4 結(jié)束語

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