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

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

0 引 言

文本聚類是將大規(guī)模文本按照某種表示模型劃分為多個(gè)簇，使得同一個(gè)簇中的文本之間相似度盡可能大，不同簇中的文本之間相似度盡可能小[1]。文本聚類中最重要的兩個(gè)步驟是：特征選取和利用特征進(jìn)行相似度判斷[2]。常見(jiàn)的文本聚類有基于向量空間模型的文本聚類和基于潛在語(yǔ)義索引的文本聚類[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作為文本表示模型會(huì)產(chǎn)生兩個(gè)問(wèn)題：一是表示文本的向量維度過(guò)高，導(dǎo)致算法復(fù)雜度過(guò)高；二是VSM模型缺乏詞語(yǔ)的語(yǔ)義信息。VSM向量維度過(guò)高的問(wèn)題通常采用降維策略，對(duì)文本進(jìn)行特征抽取[6-8]或者挖掘頻繁項(xiàng)集作為特征信息[9-10]的方法降低數(shù)據(jù)的維度。

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

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

1.1 義原相似度算法

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

圖1 義原層次樹(shù)示意圖

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

(1)

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

(2)

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

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

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

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

(3)

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

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

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

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

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

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

(4)

(5)

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

(6)

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

2.2 文本預(yù)處理

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

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

2.2.2 基于語(yǔ)義相似度的詞語(yǔ)消歧算法

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

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

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

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

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

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

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

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

2.3 文本語(yǔ)義特征抽取

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

2.3.1 語(yǔ)義特征壓縮

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

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

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

2.3.2 文本特征抽取

在獲取到文本的主題詞集合d之后，需要根據(jù)主題詞的權(quán)重抽取出文本的特征集。由于進(jìn)行了語(yǔ)義壓縮，筆者認(rèn)為語(yǔ)義因素比詞語(yǔ)的頻數(shù)因素更加重要，所以對(duì)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ì)算。通過(guò)特征詞集建立文本表示模型Di={Wi1,Wi2,…,Win}，其中Di為文本集中的第i個(gè)文本，Wik為Di的第k個(gè)特征項(xiàng)。由于特征詞都是經(jīng)過(guò)語(yǔ)義壓縮以及主題詞權(quán)重排序抽取得到的，所以文中所有特征詞具有相同的語(yǔ)義權(quán)重。

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

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

(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中元素與空對(duì)應(yīng)，賦予一較小常數(shù)。

2.5 簇的語(yǔ)義特征抽取

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(9)

(10)

(11)

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

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

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

圖3 不同閾值對(duì)聚類的影響

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

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

表2 特征集維度比較

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

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

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

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

4 結(jié)束語(yǔ)

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