鄭小波,鄭 誠,尹莉莉
(安徽大學 計算智能與信號處理教育部重點實驗室,安徽 合肥 230039)
基于GVSM的文本相似度算法研究
鄭小波,鄭 誠,尹莉莉
(安徽大學 計算智能與信號處理教育部重點實驗室,安徽 合肥 230039)
提出了一種基于WordNet和GVSM的文本相似度算法,通過語義的路徑長度和路徑深度計算兩個詞的語義相似度,結合改進的GVSM模型計算文本相似度,并對基于TFIDF-VSM模型和本文方法進行了比較。實驗結果表明,該算法取得了更好的準確率和效率。
文本相似度;語義相似度;詞網;廣義向量空間模型
文本相似度計算在文本信息處理相關領域有著廣泛的應用。目前,文本相似度的研究主要有三種方式:(1)篇章與篇章之間的相似度計算[1];(2)短語與篇章之間的相似度計算;(3)短語與篇章中段落的相似度計算。文本相似度計算方法主要有隱性語義索引模型、向量空間模型、廣義向量空間模型、基于屬性論的方法、基于海明距離的計算方法、基于數字正文的重構方法等?;谡Z義的相似度計算方法相關的研究主要有:使用WordNet進行相似度計算的方法;使用同義詞詞林進行相似度計算的方法[2];使用知網《HowNet》知識結構進行相似度計算的方法[3]。廣義向量空間模型(GVSM)是 20世紀 80年代由 Wong提出[4],在詞語消歧研究[1]、文本檢索研究[5]等方面得到了很好的應用。
本文使用WordNet進行相似度計算的方法,采用廣義向量空間模型,并對廣義向量空間模型進行了擴展,得到了新的廣義向量空間模型。通過WordNet計算兩個詞的語義相似度,把語義相似度應用到GVSM模型中來計算文本相似度。實驗結果表明,該算法取得了較好的準確率和效率。
向量空間模型(VSM)是20世紀70年代末由Salton等[6]提出的一種代數模型。在近30年內,向量空間模型(VSM)被廣泛應用到信息檢索、文本分類、文本聚類等領域,并取得了很好的效果。其基本思想是:假設詞與詞之間是不相關的,以向量表示文本,每個維度對應于一個單獨的詞,則(w1,w2,w3,…,wn)文檔 dk可以看成相互獨立的詞條(t1,t2,t3,…,tn),為了表示詞條的重要程度,給每個詞條賦予相應的權值 wi,其中文檔dk可用向量(w1,w2,w3,…,wn)表示。向量空間模型中的文檔相似度計算方法為:
其中 wki、wpi分別是詞 ti在 dk和 dp的權值,n是向量的維度。向量空間模型的前提是假設詞與詞之間是不相關的,但這種假設不現實,因為詞與詞之間往往存在語義相關。
廣義向量空間模型GVSM擴展的VSM模型,GVSM引入了詞與詞之間的相關度,并提出了一個新的向量空間,每個向量 ti被表示成 2n維向量 mr,其中 r=1,2,…,2n。文檔相似度計算方法為:
其 中 wki、wpi分 別 是 詞 ti在 dk和 dp的 權 值 ,R(ti,tj)是 詞 ti和tj的相關度。
WordNet由普林斯頓大學認知科學實驗室在1985年建立,是一部在線詞典數據庫系統,采用了與傳統詞典不同的方式,即按照詞義而不是詞形來組織詞匯信息。WordNet將英語的名詞、動詞、形容詞、副詞組織為Synsets,每一個Synset表示一個基本的詞匯概念,并在這些概念之間建立了包括同義關系(synonymy)、反義關系(antonymy)、上下位關系(hypernymy&hyponymy)、部分關系(meronymy)等多種語義關系。不同的邊代表不同的語義關系。
本文模型中使用WordNet衡量兩個詞的語義關系。分別考慮了路徑長度SPC(Semantic Path Compactness)和路徑深度SPE(Semantic Path Elaboration),給定兩個詞的語義相關度SR(Semantic Relatedness)由SPC和SPE合并得出。下面給出相關定義。
定義 1:給定一個詞庫 O、一組詞義 S=(s1,s2)和一條s1到s2路徑l,并對于每條邊進行加權處理,其中權值e∈(0,1),則 SPC 定義為:
其中 e1,e2,e3,…,el分別是每條邊的權值;當 s1=s2時,SPC(S,O)=1;如果s1與s2之間沒有路徑,則 SPC(S,O)=0。
定義 2:給定一個詞庫 O、一組詞義 S=(s1,s2)和一條s1到 s2路徑 l,其中 s1,s2∈O 且 s1≠s2,則 SPE 可定義為:
定義 3:給定一個詞庫 O、一組詞 T=(t1,t2)和它們所有的詞義 S=(s1i,s2j),其中 s1i和 s2j分別是 t1和 t2的詞義,則 SR(T,S,O)可定義為:
其中 T=(ti,tj),i=j=1,2,…,n。 當 t=ti=tj時,SR(T,S,O)=1;當 ti∈O 且 tj?O 或 ti?O 且 tj∈O 時 ,SR(T,S,O)=0。
為了計算兩個詞的語義關聯度,需要構建語義網絡,采用了文獻[7]的方法。相比較其他方法,它嵌入所有可用的WordNet的語義信息并提供了豐富的語義表達。根據所采用語義網絡建設模式,每種類型的邊將被賦予各自的權值,權重越高說明它們的語義關聯度越高(如上位/下位邊的權值定義為0.57)。詞與詞義的關系在語義網中如圖1所示。
其中si·m、sj·n分別是詞ti和tj的詞義,m是詞ti的詞義數,n是詞 tj的詞義數。
遍歷ti和tj所有的詞義,將會出現以下幾種情況:
(1)如果 si·m和 sj·n之間沒有路徑,如圖 2(a)所示,則SR((ti,tj),(si·m,sj·n),O)=0 。
(2)如果 si·m和 sj·n之間只有一條路徑,如圖 2(b)所示,則 si·m和 sj·n的語義關聯度為 SPC((si·m,sj·n),O)。
(3)如果 si·m和 sj·n之間有多條路徑,如圖 2(c)所示,則 si·m與 sj·n的 語 義 關 聯 度 為 max{SPC((si·m,sj·n),O)×SPE((si·m,sj·n),O)}。
式(2)中介紹了GVSM模型,現將式(5)應用到 GSVM模型中,使得:
這里定義一個新的文本向量,新向量中增加了ti和tj在文本dk中的TF-IDF權值,如下定義:
由新的文本向量可以產生一個新的GVSM模型,則兩個文本之間的相似度公式定義為:
其中n為向量的維度,dk和dp分別是兩篇不同的文檔。
利用上述方法,本文實現了基于WordNet的語義相似度計算程序模塊。為了對相似度計算結果更好地進行分析,本文評價的方案放在文本分類系統中,以觀察不同計算方法對文本分類系統性能的影響。
評價標準是在測試過程中所使用的一些用來評價分類器分類準確度的量化標準。本文采用常用的三種標準,它們在不同的方面來評價一個分類器。
準確率(precision)= (分類正確的文本數)/(實際分類的文本數)
召回率(recall)= (分類正確的文本數)/(應有分類正確的文本數)
本文實驗是在Windows XP操作系統、Eclipse開發環境下,通過Java語言實現。實驗是在1GB內存、P4 3.0GHz CPU的PC機下進行的。實驗數據集采用的是20-Newsgroups文本數據集。20-Newsgrops是在UseNet上下載的20個類的新聞組討論英文文章。數據集共有20個類,每個類大約1 000篇。20-Newsgroups是一個比較常用的文本數據集。出于效率考慮,本實驗選取其中的5個類別,針對不同數量的訓練文本進行了實驗,實驗分別選取了200、400、600、1 000、2 000 篇文本平均分配到編號為 A、B、C、D、E的5個集合。分別對基于TFIDF-VSM[3]模型和本文提出的基于WordNet的GVSM模型進行了比較實驗。本文采用KNN[8]分類器進行評價,測試結果記錄了上述5種情況分類器的準確率、召回率、F1值。
實驗結果表明,采用基于WordNet的GVSM模型比基于TFIDF-VSM模型具有更高的準確率、召回率、F1值。分析發現當文本數越多時,文本分類的準確率、召回率、F1值越高。
本文提出了一個新的文本相似度計算方法,將其成功地應用在文本分類當中,實驗證明得到了很好的效果。首先基于WordNet構建了語義網,分別考慮路徑長度SPC和路徑深度SPE來計算兩個詞的語義關聯度;然后將其應用在GVSM模型中計算文本相似度;最后應用在文本分類中,得到了較高的分類準確率和召回率。下一步準備將其應用到信息檢索中,以提高信息檢索的準確率與效率。
[1] WILLETT P.Recent trends in hierarchical document clustering: a criticalreview.InfProcess and Manage,1988:577-597.
[2]夏天.漢語詞語語義相似度計算研究 [J].計算機工程,2007,33(6):191-194.
[3]李峰,李芳.中文詞語語義相似度計算——基于《知網》2000[J].中文信息學報,2007,21(3):99-105.
[4]WONG,S.K.M.Wojciech Ziarko,Patrick C.N.Wong.Generalized vectorspacesmodelin information retrieval.SIGIR ACM,1985.
[5]TSATSARONIS G,PANAGIOTOPOULOU V.A generalized vector space modelfortextretrievalbased on semantic relatedness. Proceedings of the EACL 2009 Student Research Workshop,2009:70-78.
[6]SALTON,MCGILL M J.Introduction to modern information retrieval.McGraw-Hill,1983.
[7]VAZIRGIANNIS T M.Word sensedisambiguation with spreadingactivation networks generated from thesauri[C].In Proc.of the 20th IJCAI,2007:1725-1730.
[8]HALLP,PARK BU,SAMWORTH R J.Choiceof neighbor order in nearest-neighbor classification.Annals of Statistics:2008:2135-2152.
[9]Qinglin Guo.The similarity computing of documents based on VSM. IEEE International Computer Software and Applications Conference.2008:585-586.
Research on similarity algorithm of text based on GVSM
Zheng Xiaobo,Zheng Cheng,Yin Lili
(Key Lab.of Intelligent Computing& Signal Processing,Ministry of Education,Anhui University,Hefei 230039,China)
This paper presents a text similarity algorithm based on WordNet and GVSM,computing the similarity of two words by semantics of path length and depth,combined with the improved GVSM model.Then compare the TFIDF-VSM-based model with this method.The experimental results show that this algorithm can achieve a better precision and efficiency.
text similarity;semantic relatedness;WordNet;GVSM
TP391
A
1674-7720(2011)03-0009-03
2010-09-12)
鄭小波,男,1983年生,碩士研究生,主要研究方向:信息檢索與文本數據挖掘。
鄭誠,男,1964年生,副教授,碩士生導師,主要研究方向:數據挖掘、機器學習研究。
尹莉莉,女,1985年生,碩士研究生,主要研究方向:數據挖掘。