常 鵬,馮 楠

(1.天津大學 管理學院,天津 300072; 2.天津大學 網(wǎng)絡與信息中心,天津 300072)

1 引言

隨著信息技術(shù)的發(fā)展，特別是互聯(lián)網(wǎng)的普及，電子化的信息資源呈爆炸式增長，已經(jīng)遠遠超出了人類的認知與理解能力，只有借助計算機的高效處理才有可能從中獲取人們感興趣的知識與信息。在這些信息資源中，文本信息占絕大部分，而文本信息是一種半結(jié)構(gòu)或無結(jié)構(gòu)的數(shù)據(jù)，傳統(tǒng)數(shù)據(jù)挖掘算法無法直接適用于文本挖掘，因此，將無結(jié)構(gòu)的文本信息轉(zhuǎn)化為結(jié)構(gòu)化信息是文本挖掘的關鍵性、基礎性的問題。傳統(tǒng)的文檔表示模型以向量空間模型(Vector Space Model,VSM[1])為主，然而，由于VSM只考慮了詞頻信息，而忽略了很多重要的信息，它無法達到更高的準確率。近年來很多學者利用自然語言處理的技術(shù)，來提高信息檢索的性能，其中詞的共現(xiàn)(Co-Occurrence)現(xiàn)象是研究的熱點之一。本文從詞的共現(xiàn)現(xiàn)象著手，分析了詞的共現(xiàn)現(xiàn)象與文檔主題之間的關系，進而提出了基于詞共現(xiàn)的文檔表示模型，定義了基于CTVSM的文檔相似性度量方法。實驗表明CTVSM可以有效地表達文檔的主要特征，具有更好的文檔區(qū)分能力。

2 相關工作

文檔建模可以分為基于概率模型的方法與基于空間向量的方法，其中基于空間向量的VSM[1]可以算得上是應用最為廣泛的文檔表示模型，目前文本挖掘的算法大部分都是建立在VSM之上的。盡管VSM在信息檢索與文本挖掘等領域的應用獲得了極大的成功，它還是存在一些缺點：1)隨著文本規(guī)模增大，向量空間的維數(shù)也迅速增大，造成了“維數(shù)災難”，現(xiàn)有文本挖掘算法的性能急劇下降；2)由于忽略了詞與詞之間的語義相關性，同義詞與多義詞等語言現(xiàn)象導致了算法準確性的下降。

針對于VSM忽略的詞間的關聯(lián)關系，一些學者試著從更高的層次來建立文檔表示模型，典型的代表是Feldman提出的從“Term”的層面來建立文本的特征[2]，從而提高文本挖掘的質(zhì)量，其中，“Term”被定義為有意義的詞串。詞串的引入可以消除詞的歧義現(xiàn)象，然而詞串的抽取需要滿足特定的語法結(jié)構(gòu)，例如，“名詞—介詞—名詞”、“形容詞—名詞”等，這為詞串的抽取帶來一定的難度。Hammouda提出一種基于短語的文檔標引圖(Document Index Graph，DIG)[3]文本表示模型，短語被定義為排序的詞的組合，通常運用統(tǒng)計的方法抽取詞匯的二元組和三元組。高茂庭等人則提出了基于DIG的相似度計算改進算法[4]，將抽取出的短語作為VSM中詞向量的補充，提高了DIG的文檔區(qū)分能力。

文檔間相似度計算算法對文檔的區(qū)分能力直接影響著文本挖掘與信息檢索的效果，因此國內(nèi)的學者們則普遍關注文檔間相似度計算的問題，并取得了一定的成果。潘謙紅、史忠植等以屬性論為理論依據(jù)，建立文本屬性重心剖分模型[5]，并在屬性坐標系中表示文本向量與查詢向量，確立了向量間的匹配基準，從而建立了文本與查詢式之間的相似度計算公式。晉耀紅提出了基于語境框架下的文本相似度計算方法[6]，將文本內(nèi)容抽象成領域、情景與背景三個側(cè)面，從而使文本之間的語義相似度得以量化。曹恬等人則提出利用詞共現(xiàn)信息來改進文本相似度計算算法[7]，用相關詞序列的相似度貢獻值來修正基于VSM的相似度計算公式。張燕平等人提出基于詞共現(xiàn)的垃圾郵件過濾方法[8]，利用詞共現(xiàn)模型有效提高了郵件的特征提取準確度。賈西平等人提出基于主題的文檔檢索模型[9]，利用LDA學習文檔中的主題分布，從而建立主題向量空間，在主題空間內(nèi)用文本主題向量的余弦夾角來計算文本相似度。

綜合上述國內(nèi)外學者的研究成果，可以看出文檔表示模型及建立在其上的文檔相似度計算方法受到了學者們的持續(xù)關注。其中大部分學者的工作是建立在VSM基礎之上，對其進行了改進研究。從學者們的研究思路來看，主要有兩條思路：1)從更高的語言層次描述文檔，例如：短語、概念、主題；2)降維處理，選擇最能代表文檔主要特征的詞匯，構(gòu)造文檔特征向量，其中前者是目前學者們最為關注的領域。然而，目前對文本表示模型的研究尚存在一定的局限性，大部分研究并未擺脫VSM的影響。本文從詞共現(xiàn)現(xiàn)象開始，分析詞共現(xiàn)與文本主題之間的內(nèi)在聯(lián)系，在文檔建模中引入詞共現(xiàn)組合的概念，建立了基于詞共現(xiàn)的文檔表示模型，從而更加精確地描述了文本的主題特征。

3 基于詞共現(xiàn)的文檔模型

3.1 詞的共現(xiàn)現(xiàn)象

通常，文本中出現(xiàn)的詞匯都是為了幫助作者表達其主題思想，因此都可以作為主題相關詞匯，只不過與主題的相關程度有所不同。文檔建模的目的就是找出與主題密切相關的詞匯，進而利用這些詞匯代表文檔的主要特征。就像客觀存在的事物一樣，詞匯也有其領域標簽。因此，相同領域或主題內(nèi)的詞匯共同出現(xiàn)在同一篇文檔中的概率相對較高，利用詞的共現(xiàn)現(xiàn)象可以判斷詞匯與主題之間的相關程度。

假設文檔空間D上有主題集合T和詞匯集合W，其中，di∈D代表第i篇文檔，tk∈T代表文檔空間中的第k個主題，S(tk)為主題tk的主題相關詞集合，wm∈W為文檔中出現(xiàn)的詞匯。在主題tk出現(xiàn)的情況下，詞匯wm出現(xiàn)的條件概率可表示為P(wm|tk)。則有如下定義。

定義1：顯著性事件是指發(fā)生概率較高的事件，即滿足P(?)>θ的事件為被稱為顯著性事件，其中θ為顯著性判別標準。通常顯著性事件的判別標準與文檔集的規(guī)模以及主題在文檔空間中的分布有關。

根據(jù)Hoffman提出的概率潛在語義分析模型(Probabilistic Latent Semantic Analysis，PLSA)[10]。對應潛在的主題變量，定義在W×W上的聯(lián)合概率模型如定義2所示。

定義2：共現(xiàn)率詞匯wi與wj的共現(xiàn)率是指這兩個詞在同一語言單位中共同出現(xiàn)的概率，即它們在文本空間中的聯(lián)合概率，如公式(1)所示：

(1)

?wi,wj∈W

公式(1)的圖模型描述如圖1所示。

圖1 PLSA(相位模型)的圖模型

定義3：主題相關當P(wm|tk)為顯著性事件時，即P(wm|tk)≥θ，wm是tk的主題相關詞匯，稱wm與tk主題相關。

定義4：主題無關當P(wm|tk)為非顯著性事件時，即P(wm|tk)<θ，wm不是tk的主題相關詞匯，稱wm與tk主題無關。

推論1：兩個詞匯的共現(xiàn)為顯著性事件，則這兩個詞匯與某個共同的主題相關。即：當P(wi,wj)≥θ時，?tk使得P(wi|tk)≥θ且P(wj|tk)≥θ。

證明：

根據(jù)定義2可知

已知P(wi,wj)≥θ，不妨設

P(wi,wj)>P(tk)P(wi|tk)P(wj|tk)≥θ

因為P(?)∈[0,1]，且在實際數(shù)據(jù)中詞匯在文本集上的后驗概率以及主題分布要遠小于1，所以：

推論1得證。

在文檔空間中，兩個詞匯的共現(xiàn)率是比較容易通過統(tǒng)計的方式獲取的，根據(jù)推論1可知，如果兩個詞匯的共現(xiàn)率超過一定的閾值，就預示著這兩個詞是主題相關的。

3.2 詞的共現(xiàn)率計算

根據(jù)定義2可知，詞的共現(xiàn)率是兩個詞在同一主題內(nèi)同時出現(xiàn)的概率之和，然而在實際文檔建模過程中，主題是文本的隱含變量，無法準確獲得。因此，通過統(tǒng)計兩個詞在文本中共現(xiàn)的次數(shù)計算它們的共現(xiàn)率。假設一個窗口單元(例如，一句話、一個段落)代表一個主題，文檔空間中有n個窗口單元，則主題的先驗概率為P(t)=1/n。當詞w在窗口單元出現(xiàn)，則其后驗概率為P(w|t)=1。則根據(jù)公式(1)，如果詞wi和wj共同出現(xiàn)在x個不同的窗口單元中，它們的聯(lián)合概率為P(wi,wj)=x/n。因此詞的共現(xiàn)率可以由公式(2)計算得出。

式中，Segment(wi,wj)表示文檔空間中同時包含wi和wj的窗口單元集合，Segment表示文檔空間中的窗口單元集合，‖?‖表示集合中的元素個數(shù)。例如，將窗口單元設為一個自然段，則自然段內(nèi)出現(xiàn)的詞匯對視為它們的一次共現(xiàn)。

3.3 共現(xiàn)詞組合的抽取

共現(xiàn)詞組合的抽取過程類似于利用關聯(lián)規(guī)則的數(shù)據(jù)挖掘方法發(fā)現(xiàn)事務中頻繁項集的過程。文檔中的自然段被視為一個事務，自然段中出現(xiàn)的詞匯視為事務包含的項。通過關聯(lián)規(guī)則挖掘算法，挖掘項之間的關系。其中項的支持度由公式(3)表示，置信度由公式(4)表示。

由于共現(xiàn)詞組合為二元組，所以只考慮二元組的規(guī)則抽取。給定關聯(lián)規(guī)則挖掘空間S=(T,I,R,θ)，其中含義如下：

(1)T={t1,t2,...,tn}為S上的事務集合(Transaction Set)，其中tn∈T為S上的事務，即文檔中的自然段；

(2)I={i1,i2,...,im}為S上的項集(Item Set)，im∈I為d上的項，即文檔中的候選詞匯；

(3)R={r1,r2,...,tk}為T中蘊含的規(guī)則，其中rk=(ix,iy),ix,iy∈I，即抽取出的共現(xiàn)詞組合；

(4)θ={α,β}為S上的約束，α和β分別為給定的支持度與置信度的閾值。

則在空間S上的“事務—項”矩陣可以表示為m×n的矩陣。其中行向量代表一個事務t，列向量代表項i，矩陣為0-1矩陣。如果事務tn包含項im，則矩陣中對應的第n行m列的值為1，否則為0。則S上的支持度與置信度可以轉(zhuǎn)化為以下的代數(shù)形式：

在上述定義的關聯(lián)規(guī)則挖掘空間S上，本文設計了一個簡單高效的挖掘算法，算法如下：

算法1：關聯(lián)規(guī)則挖掘算法

輸入：事務數(shù)據(jù)庫

輸出：規(guī)則集

過程：

(1)掃描事務數(shù)據(jù)庫，構(gòu)造m×n的“事務—項”矩陣；

(2)生成I上的所有二階的項組合(ix,iy),?ix,iy∈I

(3)在項組合集上循環(huán)，利用公式(5)和(6)計算項組合(ix,iy)的支持度與置信度。如果支持度和置信度大于設定閾值，則將該項組合加入R。

(4)返回規(guī)則集R，算法結(jié)束

此算法只在算法開始時讀取一次數(shù)據(jù)庫，即將所有數(shù)據(jù)讀到內(nèi)存中，之后利用矩陣運算得到項集上的支持度與置信度。同時算法的復雜度也大大降低，復雜度為O(m2)。

3.4 CTVSM

與VSM的建模思想類似，CTVSM也將文檔表示為一個共現(xiàn)詞組合的向量。設文檔空間D={d1,d2,...,dn}中包含n篇文檔，在D上抽取出的共現(xiàn)詞組合的集合為C={c1,c2,...,cm}，其中cm為抽取出的第m個共現(xiàn)詞組合。則文檔空間D可表示為一個m×n的矩陣。其中行向量di=(ci1,ci2,...,cim)代表一篇文檔，列向量cj=(c1j,c2j,...,cnj)T代表一個共現(xiàn)詞匯組合在各文檔中的分布情況。矩陣中的元素cij表示文檔di中共現(xiàn)詞匯組合cj的分布情況，如果共現(xiàn)詞匯組合出現(xiàn)則相應的權(quán)值為1，如果不出現(xiàn)，則相應權(quán)值為0，如公式(7-9)所示。

4 基于CTVSM的文本相似性度量

4.1 文檔距離

在CTVSM中，將文檔看作高維空間中的一個向量，每個共現(xiàn)詞組合作為空間中的一個維度，則文檔間的距離定義如下。

定義5：文檔距離文檔的距離是兩篇文檔在CTVSM中相異的共現(xiàn)詞組合的度量，給定兩篇文檔di和dj，共現(xiàn)詞組合矩陣C，它們之間的距離為(式10)：

距離在一定程度上可以反映出兩篇文檔的相似性，即反映出了兩篇文檔之間不同的共現(xiàn)詞對個數(shù)。

4.2 文檔的相似性

定義6：文檔相似性文檔的相似性是兩篇文檔在CTVSM中相同的共現(xiàn)詞組合的度量，給定兩篇文檔di和dj，共現(xiàn)詞組合矩陣C，它們的相似性定義如下：

根據(jù)定義可知在兩篇文檔中共同包含的共現(xiàn)詞組合個數(shù)越多，它們的相似性越大。

4.3 文檔的相關度

在文本處理中，文檔之間的相關度比較是個常見的問題，文檔之間的相關程度與它們之間的相似度以及距離有關，文檔之間的距離越大表明文檔的差異越大，而文檔之間的相似度越大表明文檔的主題重合度越大。然而，僅僅用距離或者相似度是無法準確反映文檔之間的相關程度的，例如，在CTVSM中，文檔A、B與文檔C具有相同的相似度(相同的共現(xiàn)詞組合個數(shù))，但是由于A、B與C的不同的共現(xiàn)詞組合個數(shù)不一定相同(距離不相等)，實際上應當距離越小的相關度越大。因此，文檔之間的相關度定義如下。

定義7：文檔相關度文檔的相關度是文檔之間主題相關的度量，它綜合了文檔距離及相似度指標。給定兩篇文檔di和dj，共現(xiàn)詞組合矩陣C，它們的相關度定義如下：

5 實驗與討論

5.1 實驗數(shù)據(jù)

本文選用互聯(lián)網(wǎng)上的新聞文檔作為實驗數(shù)據(jù)，從百度新聞搜索中，搜索“天然氣”的相關新聞，得到關于“北方降溫，天然氣短缺”的新聞15篇，關于“天然氣爆炸”的新聞5篇，關于“韓國總統(tǒng)盧武鉉跳崖自殺”的新聞5篇。其中，大部分文本為報道性的短篇新聞。經(jīng)過分詞和去除停用詞(對文檔分類作用不大的助詞、副詞以及常用詞)處理后，得到1 480個詞匯，其中僅出現(xiàn)一次的詞匯數(shù)量為862個，出現(xiàn)一次以上的詞匯為618個。本章在此文本集上進行了共現(xiàn)詞組合抽取、文檔相似度計算及分類的操作，以驗證CTVSM是否有效。

5.2 實驗過程與討論

(1)共現(xiàn)詞抽取

本文首先在文本集上抽取了共現(xiàn)詞組合。為了對比不同詞語上下文范圍對抽取結(jié)果產(chǎn)生的影響，本文采用了兩種不同的上下文范圍。分別以段落和句子為單位進行共現(xiàn)詞組合的抽取，即以段落為上下文有效范圍的共現(xiàn)詞組合抽取中，在一個段落范圍內(nèi)，如果兩個詞同時出現(xiàn)，則認為它們共現(xiàn)一次；以句子為單位的抽取中，則需要統(tǒng)計它們共同出現(xiàn)在哪些句子中。在進行中文分詞的時候，記錄每個詞出現(xiàn)的段落及句子，以便于統(tǒng)計。

共現(xiàn)詞抽取算法采用本文提出的關聯(lián)規(guī)則挖掘算法，詳見算法1。支持度閾值設為0.01，置信度閾值設為0.5。經(jīng)計算，以段落為單位的共現(xiàn)詞組合抽取算法抽取出了273條規(guī)則，而基于句子的共現(xiàn)詞組合抽取算法只抽取出25條規(guī)則，抽取出的部分規(guī)則如表1所示。

從兩個不同語境單元中，抽取出的具有較高支持度與置信度的共現(xiàn)詞組合基本一致，從字面上可以看出，這些共現(xiàn)詞組合中的詞匯都是主題相關的詞匯。從詞語的搭配角度來看，以語句為語境單位的共現(xiàn)詞抽取結(jié)果更為合理， 因為在同一句子中的詞匯是具有主題高度相關性和詞語搭配可能性更高一些。然而，由于文本集上的句子數(shù)量遠大于段落數(shù)量，因此共現(xiàn)詞匯的支持度有所下降，然而置信度卻保持了較高的水平。將支持度閾值降低到0.005時，抽取出的規(guī)則有所增多，增加到124條。

表1 抽取出的部分共現(xiàn)詞組合

文檔集抽取出的共現(xiàn)詞組合數(shù)量對文檔主題的表達有著直接的影響，降低支持度與置信度閾值相當于降低共現(xiàn)詞組合抽取門檻，共現(xiàn)詞組合數(shù)量增多但是質(zhì)量降低，而增加相關的閾值參數(shù)則提高了質(zhì)量降低了數(shù)量。為了驗證此論斷，本文選擇了一系列不同的閾值進行文檔聚類的實驗，對比不同閾值下，抽取出的共現(xiàn)詞組合對文檔主題表達的準確性。實驗分別采取固定置信度閾值變動支持度閾值和固定支持度閾值變動置信度閾值的方法，考察不同支持度閾值、置信度閾值組合下對聚類結(jié)果的影響。實驗結(jié)果如圖2所示。在不同支持度閾值下的F-measure值變化如圖2(a)所示?？梢钥闯鲈谥С侄乳撝等^(qū)間[0.003，0.005]，置信度閾值取0.5時，聚類結(jié)果準確率最高，達到0.976。即在此參數(shù)設置下抽取出的共現(xiàn)詞集合的規(guī)模是合適的，共現(xiàn)詞集合已經(jīng)可以表現(xiàn)出文檔的主要特征。隨著支持度閾值的減小，共現(xiàn)詞集合規(guī)模增大，一些噪音被抽取出，導致了聚類結(jié)果的下降。

(a)置信度閾值固定，支持度閾值變化; (b)支持度閾值固定，置信度閾值變化

(2)相似度對比實驗

在文檔的相似度對比實驗中，比較了不同文檔分布在VSM與CTVSM空間中的相似度。經(jīng)過分詞與去除停用詞，得到詞匯1 480個。為了減低計算復雜度，將只出現(xiàn)一次的低頻詞匯去除，得到618個詞匯。而在文檔集上抽取出的共現(xiàn)詞組合數(shù)為273條(基于段落)與124條(基于語句)。采用余弦夾角公式計算VSM中的文本相似度；采用公式(12)計算CTVSM中的文檔的相關度。實驗結(jié)果如表2所示。

表2 文檔相似度對比(部分結(jié)果)

以編號為1的文檔與其他文檔的相似度為例，分別對比了三種計算方法得到它與其他文本的相似度，如圖3所示。

圖3 三種相似度的比較

從實驗結(jié)果可以看到三種相似度的趨勢基本保持了一致，即對于相似的文檔三種算法得到的相似度較高，而對于不相關的文檔相似度都比較低。這說明基于詞共現(xiàn)組合的文檔表示模型是能夠反映出文檔之間的差異性的。此外，基于段落語境構(gòu)建的共現(xiàn)詞空間與基于語句語境構(gòu)建的共現(xiàn)詞空間，在空間維數(shù)相當?shù)那闆r下，計算得到的相似度基本一致。這說明語境范圍的大小對文檔建模精確度影響是不大的，抽取出的共現(xiàn)詞組合的個數(shù)才是影響建模有效性的關鍵因素，即文檔空間的維數(shù)是影響文檔表示模型的關鍵因素。

此外，VSM與CTVSM有一個明顯的區(qū)別，即VSM的文檔相似度的方差較小，即使兩篇文檔的主題不一致，但是因為它們都包含了相同的詞語，從而導致了相似度不會變的很低，然而，CTVSM中，不同主題之間的文檔相似度降到很低(低于VSM)，而相同主題的文檔相似度又變的很高(高于VSM)。例如，在本實驗中，關于天然氣的兩個不同主題，由于它們都是包含天然氣這一關鍵詞，因此，在VSM中，這兩個主題之間的文檔相似度也比較高，而CTVSM中，由于兩個主題之間的文檔抽取出的共同的詞匯組合較少，因此，它們之間的相似度很低。由此，可以看到CTVSM中得到的文檔相似度是主題敏感的，他能有效過濾多義詞帶來的負面影響。特別是在文檔分類及聚類研究中，此特性將有助于顯著區(qū)分不同主題下文檔的相似度。

(3)文檔聚類實驗

對實驗數(shù)據(jù)分別在VSM與CTVSM空間中進行聚類實驗，聚類算法采用層次聚類算法，最優(yōu)層次劃分的判斷標準采用聚類增益[11]。聚類過程中的聚類增益如圖4所示。

在進行到61步附近時VSM與CTVSM中的聚類增益均達到最大值，比較聚類增益取得最大值的層次劃分的F-measure值，在VSM中達到最優(yōu)層次劃分時的F-measure值為0.76，而在CTVSM中達到最優(yōu)層次劃分時的F-measure值為0.97。實驗結(jié)果表明，在CTVSM下聚類結(jié)果得到了顯著的提高。

6 結(jié)論

本文通過對詞共現(xiàn)的分析，挖掘出詞匯共現(xiàn)現(xiàn)象背后的主題關系，提出詞匯的共現(xiàn)在一定程度上可以反映出主題的發(fā)生模式。進而設計了一個在文檔集上抽取共現(xiàn)詞組合的抽取算法，并利用文檔空間上的共現(xiàn)詞組合構(gòu)建了文檔表示模型。實驗證明，該文檔表示模型是有效的，在文檔相關度的度量中比VSM下具有更好的區(qū)分度，而且在CTVSM下文檔聚類的效果得到了顯著提高。

(a)VSM; (b)CTVSM(0.004，0.5)

[1]Salton G,Wong A,Yang C S.A vector space model for automatic indexing[C]//Communications of the ACM,1975,Vol.18 (11)：613-620.

[2]Feldman R,Aumann Y,et al.Text Mining at the Term Level[C]//Proceedings of the 2nd European Symposium on Principles of Data Mining and Knowledge Discovery.Nantes,France,1998,23-26.

[3]Hammouda K,Kamel M.Efficient Phrase-based Document Indexing for Web Document Clustering [J].IEEE Transactions on Knowledge and Data Engineering,2004,16(10)：1279-1296.

[4]高茂庭,王正歐.基于文檔標引圖模型的文本相似度策略[J].計算機工程，2008,34(7)：19-22.

[5]潘謙紅,王炬,史忠植.基于屬性論的文本相似度計算[J].計算機學報，1999,22(6)：651-655.

[6]晉耀紅.基于語境框架的文本相似度計算[J].計算機工程與應用，2004,16：36-39.

[7]曹恬,周麗,張國煊.一種基于詞共現(xiàn)的文本相似度計算[J].計算機工程與科學，2007,29(13)：52-53.

[8]張燕平,史科,徐慶鵬,等.基于詞共現(xiàn)模型的垃圾郵件過濾方法研究[J].中文信息學報，2009,23(6),61-66,71.

[9]賈西平,彭宏,鄭啟倫,等.基于主題的文檔檢索模型[J].華南理工大學學報(自然科學版)，2008,36(9),37-42.

[10]Thomas Hofmann.Unsupervised Learning by Probabilistic Latent Semantic Analysis[J].Machine Learning，2001,42：177-196.

[11]Yunjae Jung,Haesun Park,Ding-Zhu Du,et al.A Decision Criterion for the Optimal Number of Clusters in Hierarchical Clustering[J].Journal of Global Optimization，2003,25：91-111.