基于ＶＳＭ的文本相似度計算的研究
2008-12-31 00:00:00郭慶琳李艷梅唐琦
計算機應用研究 2008年11期
(1. 華北電力大學 計算機科學與技術學院， 北京 102206； 2. 北京大學 計算機系， 北京 100871)
摘要：文本相似度的計算作為其他文本信息處理的基礎和關鍵，其計算準確率和效率直接影響其他文本信息處理的結果。提出改進的DF算法和TD-IDF算法，一方面利用了DF算法具有線性的時間復雜度，比較適合大規模文本處理的特點，并通過適當增加關鍵詞的方法，彌補了其對個別有用信息錯誤過濾的不足；另一方面，利用特征項在特征選擇階段的權重對TD-IDF方法進行加權處理，在不增加開銷的情況下擴大了文檔集的規模，還提高了相似度計算的精確度。
關鍵詞：文本相似度； 特征選擇； 詞頻—逆文檔頻率法； 向量空間模型
中圖分類號：TP391文獻標志碼：A
文章編號：1001-3695(2008)11-3256-03
Similarity computing of documents based on VSM
GUO Qing-lin1，2， LI Yan-mei1， TANG Qi1
(1.School of Computer Science Technology， North China Electric Power University， Beijing 102206， China; 2. Dept. of Computer Science Technology， Peking University， Beijing 100871， China)
Abstract:The precision and efficiency of the computing of documents similarity is the foundation and key of other documents process. This paper improved the DF and TF-IDF arithmetic. In this way， DF’s time complexity was linearity that suited the mass documents process， and could make up the fault that exceptional useful characters might be deleted. Also， it did a mend on the TF-IDF arithmetic to improve the precision of documents similarity.
Key words：documents similarity; feature selection; TF-IDF(term frequency-inverse document frequency); VSM(vector space model)
隨著計算機的普及和網絡的飛速發展，互聯網上以及各種電子文檔的數量以空前的速度增長，人們獲取知識的途徑也發生了深刻的變化。面對如此巨大的知識海洋，如何快速查找相關信息變得非常重要。如果沒有有效的組織和提取方式，普通用戶查找自己想要的信息所用的時間可能比了解信息本身所花費的時間還長，這是人們無法容忍的。文本相似度是表示兩個或多個文本之間匹配程度的一個度量參數，相似度大，說明文本相似程度高，反之文本相似度低。對于文本聚類、信息檢索、問答系統、網頁去重、文本分類等很多領域，文本相似度的有效計算問題是其進行信息處理的關鍵。
1向量空間模型
向量空間模型（VSM）是20世紀60年代末由Salton等人提出來的，它是代數模型的一種，也是目前信息檢索領域中廣泛采用且效果較好的一種模型。其基本思想是：假設詞與詞之間是不相關的，以向量來表示文本，從而簡化了文本中關鍵詞之間的復雜關系，使得模型具備了可計算性[1]。在VSM中，將文檔看成是相互獨立的詞條組(T1，T2，T3，…，Tn)構成，對于每一個詞條Ti，根據其在文檔中的重要程度賦予一定權值Wi，并將(T1，T2，T3，…，Tn)看成是一個n維坐標系中的坐標軸，(W1，W2，W3，…，Wn)為對應的坐標值。這樣由(T1，T2，T3，…，Tn)分解得到的正交詞條矢量組就構成了一個文檔向量空間[2]。
2特征選擇
特征選擇就是根據一些標準從原始特征集中選擇子集的過程。特征選擇的任務就是選擇對相似度計算真正有貢獻的特征項，被選中的特征項應能表征原始文本的主題。
21常用的特征選擇算法
依據需不需要類別信息，特征選擇分為有監督和無監督兩類。其中有監督的特征選擇方法有信息增益（information gain，IG）、χ2統計（CHI）和互信息（mutual information，MI）等；無監督的特征選擇算法有文檔頻率（document frequency，DF）、特征增強（term strength，TS）、特征貢獻（TC）等。
211信息增益
一個特征的信息增益是指如果該特征在一篇文檔中出現，進行類別預測所獲得的信息量[3]，也就是說一個特征項的信息增益就是在不考慮任何特征項的文檔集的熵和考慮該特征項后的文檔集的熵的差值，公式如下：
IG(t)=-∑mi=1P(ci) log P(ci)+
P(tk)∑mi=1P(ci｜tk) log P(ci｜tk)+
P(tk)∑mi=1P(ci｜tk) log P(ci｜tk)
(1)
其中：P(Ci)表示類別出現的概率；P(tk)為訓練集中出現詞條tk的概率；P(Ci｜tk)為文檔中出現tk時文檔屬于Ci的概率；P(Ci｜tk )為文檔中不出現tk時文檔屬于Ci的概率。詞條是否出現都將為分類提供重要的信息，根據每個特征的信息增益值進行排序，選擇排在前面的一定數量作為特征，具體數目需要根據實際情況進行調整。
212χ2統計
χ2統計表示了特征項和類別之間的關系[4]，定義如下：
χ2(t，c)=N×[P(t，c)×P(t，c)-P(t，c)×P(t，c)]2/
[P(t)×P(t)×P(c)×P(c)]≈
N×(AD-BC)2/[(A+B)×(C+D)×(A+C)×(B+D)](2)
其中：t表示特征項；A為t和c同時出現的次數；B為t出現而c沒有出現的次數；C為c出現而t沒有出現的次數；D為t和c同時沒有出現的次數；N為所有訓練文檔數。進而可以得出特征項t的平均CHI統計和最大CHI統計
χ2avg(t)=∑mi=1P(ci)χ2(t，ci)(3)
χ2max(t)=maxmi=1{χ2(t，ci)}(4)
其中：m表示類別數。CHI詞條統計值比較了一個類別的貢獻和對其余類別的貢獻，以及詞條和其他詞條對分類的影響。CHI值越大，特征項與類越相關，所以在特征選擇時就選擇CHI統計值大的特征項。
213互信息
令t表示特征，c表示類別，則t與c之間的互信息為
I(t，c)=log (P(t，c)/（P(t)×P(c)））(5)
在一個包含m個類別的集合中特征項t的互信息值可定義為如下兩種：
Iavg(t)=∑mi=1P(ci)I(t，ci)(6)
Imax(t)=max mi=1I(t，ci)(7)
其中：Iavg(t)表示t的平均互信息；Imax(t)表示t的最大互信息。互信息表征了特征與類之間的相關程度，當特征的出現只依賴于某一類時，互信息大；當特征與類相互獨立時，互信息為0；當特征很少在該類中出現時，互信息為負數。在特征選擇時，應該選擇互信息大的特征項。
214文檔頻率
文檔頻率是訓練集中含有詞條tk.的文本數和訓練集文檔總數的比。DF的理念假設是稀有單詞要么不含有有效信息，要么對分類產生的影響很小，或者是噪聲點。該方法是最簡單的特征選擇方法，具有線性的時間復雜度，因而容易擴展到大的數據集合。在實際應用中效果顯著[5]。
215特征增強
這種方法根據特征項出現在一對相關文檔的其中一個的條件下，也出現在另一個中的概率來計算TS。它用一個文檔訓練集來得到相似度超過閾值的文檔對。用di和dj代表任意一對不同但相關的文檔，t代表特征，一個特征TS定義如下：
TS(t)=P(t∈dj｜t∈di)；di，dj∈D∩sim(di，dj)＞β(8)
其中：β是決定相關文檔的閾值。
因為需要計算每一個文檔對的相似度，所以TS的時間復雜度是O(N2)，N表示所有的文檔數目。
216特征貢獻
該方法依據特征對文檔相似度的整體貢獻對特征進行排序。像DF這樣的簡單方法認為特征在不同文檔中具有相同的重要性，所以當特征項有高的文檔頻率但是在不同的類別中分布一致時，它是容易有偏差的。該方法考慮了特征項的權重。
22改進的DF算法
DF算法中，一般的做法是當特征項的DF小于某個閾值時去掉，特征項的DF大于某個閾值也去掉。可能會將某個在某篇文檔中出現率很高但在文檔集中含量不高的詞認為是無用特征過濾掉。為了彌補這個缺點，需要對該算法進行改進，對于在文檔關鍵位置出現的詞，適當增加其詞頻Ni，公式如下：
Wi=Ti/T×Ni/N(9)
其中：Wi表示特征項的權值；Ti表示出現特征項i的文檔數；T表示總文檔數；Ni表示特征項i出現的次數；N為總的特征項個數。這樣就可以在一定程度上減小出現在較少文本且有效的詞被過濾掉的概率。
3文檔相似度計算
計算對象相關度的常用模型主要有向量空間模型和集合運算模型等。由于后者的局限性比較大[6]，最常用的是向量空間模型。
31基于VSM的TF-IDF
基于向量空間模型的方法中，使用較多且效果較好的方法是基于空間向量模型的TF-IDF方法，它綜合考慮了不同的詞在所有文本中的出現頻率和這個詞對不同文本的分辨能力，被廣泛用于計算文本之間的相似度。一篇文檔在VSM中被表示成一個向量，每個向量由其特征項及其權值表示，這就構成了文檔向量空間。文檔的相似度可用向量之間的夾角或距離來表示，其距離或夾角越小，說明文檔相似度越高。
TF-IDF方法是空間向量模型的常用方法，其公式如下：
Wt，d=TFt，d×IDFt(10)
其中：Wt，d表示該特征項在文檔中的重要程度；TFt，d指特征項在文檔d中出現的次數。Salton將IDFt表示成
IDFt=long (N/nt)(11)
其中：N表示文檔集合中所有文檔的數目；nt表示所有文檔集合中t出現的次數，稱為特征項的文檔頻率。IDF反映特征項在整個文檔集合中的分布情況，在一定程度上體現了該特征項的區分能力；TF反映特征項在文檔內部的分布情況。TF-IDF算法可以排除那些高頻、低區分度的詞，因此TF-IDF是一種有效的權重定義方法。
32改進的TF-IDF算法
對于一般的文本相似度計算方法，首先是利用訓練集進行特征詞選擇，然后再根據已選擇的特征對文檔集進行統計，前后的工作是分離的，也就是說，前期的特征一旦被選中，在后期對文檔進行詞頻統計時，它們的地位相同。另外，無論是DF特征選擇，還是TF-IDF都是基于詞頻統計的，所以比較適用于大規模文本計算，即對于規模較大的文本集合，其效果更好。為了滿足基于統計算法的這個特性，又不增加系統開銷，本文提出將特征項在特征選擇階段的權重應用到要計算相似度的文檔集合中。改進的TF-IDF算法如下：
Wt，d=Wt×TFt，d×IDFt(12)
其中：Wt表示特征項t在訓練集中的權重，其大小應根據具體情況進行調整。
33相似度計算
余弦計算方法是常用的計算文本相似度的方法。其公式如下：
sim(Ti，Tj)=(∑nt=1Ti，t×Tj，t)/(∑nt=1Ti，t×∑nt=1Tj，t)(13)
其中：Ti表示文本特征向量；Ti，t表示文本Ti的第t個向量。
4實驗結果及分析
實驗選用的語料為英國Lancaster大學中文文本分類語料[7]（Lancaster corpus of mandarin Chinese，LCMC）。該語料共有500篇文本，839 006個詞，分為15個類別，已經用XML形式進行了切分和詞性標注。實驗對語料的新聞報道、新聞社論、新聞評論三個類別的88篇文章，147 771個詞進行了詞頻統計，選擇出350個特征詞。另外選出8篇文章，分別用TF-IDF和改進的TF-IDF計算其相似度，并與專家對其評估的結果比較。其結果如表1和圖1所示。
由圖1可以看出，改進的TF-IDF算法更接近專家評估，能較好地反映文檔之間的相似度。
5結束語
文本相似度的計算是其他文本信息挖掘的基礎和關鍵，越來越受到人們的重視，其效率和準確率直接影響后期的文本處理結果。本文提出，在特征選擇階段，利用DF算法的高效性，并對其可能造成的錯誤過濾進行改進；更主要的是，在相似度計算中，利用各個特征在特征提取時的權值，對TF-IDF進行了改進，提高了其精確度。
參考文獻：
［1］王秀娟. 文本檢索中若干問題的研究[D].北京：北京郵電大學，2006.
［2］沈斌. 基于分詞的中文文本相似度計算研究[D]. 天津：天津財經大學，2006.
［3］YANG Y， PEDERSEN J O. A comparative study on feature selection in text categorization[C]//Proc ofthe 14th International Conference on Machine Learning. San Francisco: Morgan Kaufmann， 1997:412-420.
［4］GALAVOTTI L，SEBASTIANI F，SIMI M. Feature selection and negative evidence in automated text categorization[C]//Proc of KDD-2000. Boston， MA:[s.n.]， 2000:16-22.
［5］嚴莉莉，張燕平. 基于類信息的文本聚類中特征選擇算法[J]. 計算機工程與應用，2007，43(12):144-146.
［6］宋玲，馬軍，連莉. 文檔相似度綜合計算[J]. 計算機工程與應用，2006，42(1):160-163.
［7］The Lancaster corpus of mandarin Chinese (LCMC)[EB/OL]. http://www.ling.lancs.ac.uk/corplang/lcmc/.
