鄭小波，鄭 誠(chéng)，尹莉莉

（安徽大學(xué) 計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230039）

基于GVSM的文本相似度算法研究

鄭小波，鄭 誠(chéng)，尹莉莉

（安徽大學(xué) 計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230039）

提出了一種基于WordNet和GVSM的文本相似度算法，通過(guò)語(yǔ)義的路徑長(zhǎng)度和路徑深度計(jì)算兩個(gè)詞的語(yǔ)義相似度，結(jié)合改進(jìn)的GVSM模型計(jì)算文本相似度，并對(duì)基于TFIDF-VSM模型和本文方法進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明，該算法取得了更好的準(zhǔn)確率和效率。

文本相似度；語(yǔ)義相似度；詞網(wǎng)；廣義向量空間模型

文本相似度計(jì)算在文本信息處理相關(guān)領(lǐng)域有著廣泛的應(yīng)用。目前，文本相似度的研究主要有三種方式：（1）篇章與篇章之間的相似度計(jì)算[1]；（2）短語(yǔ)與篇章之間的相似度計(jì)算；（3）短語(yǔ)與篇章中段落的相似度計(jì)算。文本相似度計(jì)算方法主要有隱性語(yǔ)義索引模型、向量空間模型、廣義向量空間模型、基于屬性論的方法、基于海明距離的計(jì)算方法、基于數(shù)字正文的重構(gòu)方法等。基于語(yǔ)義的相似度計(jì)算方法相關(guān)的研究主要有：使用WordNet進(jìn)行相似度計(jì)算的方法；使用同義詞詞林進(jìn)行相似度計(jì)算的方法[2]；使用知網(wǎng)《HowNet》知識(shí)結(jié)構(gòu)進(jìn)行相似度計(jì)算的方法[3]。廣義向量空間模型（GVSM）是 20世紀(jì) 80年代由 Wong提出[4]，在詞語(yǔ)消歧研究[1]、文本檢索研究[5]等方面得到了很好的應(yīng)用。

本文使用WordNet進(jìn)行相似度計(jì)算的方法，采用廣義向量空間模型，并對(duì)廣義向量空間模型進(jìn)行了擴(kuò)展，得到了新的廣義向量空間模型。通過(guò)WordNet計(jì)算兩個(gè)詞的語(yǔ)義相似度，把語(yǔ)義相似度應(yīng)用到GVSM模型中來(lái)計(jì)算文本相似度。實(shí)驗(yàn)結(jié)果表明，該算法取得了較好的準(zhǔn)確率和效率。

1 背景知識(shí)介紹

1.1 向量空間模型

向量空間模型（VSM）是20世紀(jì)70年代末由Salton等[6]提出的一種代數(shù)模型。在近30年內(nèi)，向量空間模型（VSM）被廣泛應(yīng)用到信息檢索、文本分類(lèi)、文本聚類(lèi)等領(lǐng)域，并取得了很好的效果。其基本思想是：假設(shè)詞與詞之間是不相關(guān)的，以向量表示文本，每個(gè)維度對(duì)應(yīng)于一個(gè)單獨(dú)的詞，則（w1，w2，w3，…，wn）文檔 dk可以看成相互獨(dú)立的詞條（t1，t2，t3，…，tn），為了表示詞條的重要程度，給每個(gè)詞條賦予相應(yīng)的權(quán)值 wi，其中文檔dk可用向量（w1，w2，w3，…，wn）表示。向量空間模型中的文檔相似度計(jì)算方法為：

其中 wki、wpi分別是詞 ti在 dk和 dp的權(quán)值，n是向量的維度。向量空間模型的前提是假設(shè)詞與詞之間是不相關(guān)的，但這種假設(shè)不現(xiàn)實(shí)，因?yàn)樵~與詞之間往往存在語(yǔ)義相關(guān)。

1.2 廣義向量空間模型

廣義向量空間模型GVSM擴(kuò)展的VSM模型，GVSM引入了詞與詞之間的相關(guān)度，并提出了一個(gè)新的向量空間，每個(gè)向量 ti被表示成 2n維向量 mr，其中 r=1，2，…，2n。文檔相似度計(jì)算方法為：

其 中 wki、wpi分 別 是 詞 ti在 dk和 dp的 權(quán) 值 ，R(ti，tj)是 詞 ti和tj的相關(guān)度。

1.3 WordNet介紹

WordNet由普林斯頓大學(xué)認(rèn)知科學(xué)實(shí)驗(yàn)室在1985年建立，是一部在線詞典數(shù)據(jù)庫(kù)系統(tǒng)，采用了與傳統(tǒng)詞典不同的方式，即按照詞義而不是詞形來(lái)組織詞匯信息。WordNet將英語(yǔ)的名詞、動(dòng)詞、形容詞、副詞組織為Synsets，每一個(gè)Synset表示一個(gè)基本的詞匯概念，并在這些概念之間建立了包括同義關(guān)系(synonymy)、反義關(guān)系(antonymy)、上下位關(guān)系(hypernymy&hyponymy)、部分關(guān)系(meronymy)等多種語(yǔ)義關(guān)系。不同的邊代表不同的語(yǔ)義關(guān)系。

2 文檔相似度計(jì)算

2.1 語(yǔ)義相似度計(jì)算

本文模型中使用WordNet衡量?jī)蓚€(gè)詞的語(yǔ)義關(guān)系。分別考慮了路徑長(zhǎng)度SPC(Semantic Path Compactness)和路徑深度SPE(Semantic Path Elaboration)，給定兩個(gè)詞的語(yǔ)義相關(guān)度SR(Semantic Relatedness)由SPC和SPE合并得出。下面給出相關(guān)定義。

定義 1：給定一個(gè)詞庫(kù) O、一組詞義 S=(s1，s2)和一條s1到s2路徑l，并對(duì)于每條邊進(jìn)行加權(quán)處理，其中權(quán)值e∈(0，1)，則 SPC 定義為：

其中 e1，e2，e3，…，el分別是每條邊的權(quán)值；當(dāng) s1=s2時(shí)，SPC(S，O)=1；如果s1與s2之間沒(méi)有路徑，則 SPC(S，O)=0。

定義 2：給定一個(gè)詞庫(kù) O、一組詞義 S=(s1，s2)和一條s1到 s2路徑 l，其中 s1，s2∈O 且 s1≠s2，則 SPE 可定義為：

定義 3：給定一個(gè)詞庫(kù) O、一組詞 T=(t1，t2)和它們所有的詞義 S=(s1i，s2j)，其中 s1i和 s2j分別是 t1和 t2的詞義，則 SR(T，S，O)可定義為：

其中 T=(ti，tj)，i=j=1，2，…，n。 當(dāng) t=ti=tj時(shí)，SR(T，S，O)=1；當(dāng) ti∈O 且 tj?O 或 ti?O 且 tj∈O 時(shí) ，SR(T，S，O)=0。

2.2 語(yǔ)義網(wǎng)絡(luò)構(gòu)建

為了計(jì)算兩個(gè)詞的語(yǔ)義關(guān)聯(lián)度，需要構(gòu)建語(yǔ)義網(wǎng)絡(luò)，采用了文獻(xiàn)[7]的方法。相比較其他方法，它嵌入所有可用的WordNet的語(yǔ)義信息并提供了豐富的語(yǔ)義表達(dá)。根據(jù)所采用語(yǔ)義網(wǎng)絡(luò)建設(shè)模式，每種類(lèi)型的邊將被賦予各自的權(quán)值，權(quán)重越高說(shuō)明它們的語(yǔ)義關(guān)聯(lián)度越高(如上位/下位邊的權(quán)值定義為0.57)。詞與詞義的關(guān)系在語(yǔ)義網(wǎng)中如圖1所示。

其中si·m、sj·n分別是詞ti和tj的詞義，m是詞ti的詞義數(shù)，n是詞 tj的詞義數(shù)。

遍歷ti和tj所有的詞義，將會(huì)出現(xiàn)以下幾種情況：

(1)如果 si·m和 sj·n之間沒(méi)有路徑，如圖 2(a)所示，則SR((ti，tj)，(si·m，sj·n)，O)=0 。

(2)如果 si·m和 sj·n之間只有一條路徑，如圖 2(b)所示，則 si·m和 sj·n的語(yǔ)義關(guān)聯(lián)度為 SPC((si·m，sj·n)，O)。

(3)如果 si·m和 sj·n之間有多條路徑，如圖 2(c)所示，則 si·m與 sj·n的 語(yǔ) 義 關(guān) 聯(lián) 度 為 max{SPC((si·m，sj·n)，O)×SPE((si·m，sj·n)，O)}。

2.3 文本相似度計(jì)算

式(2)中介紹了GVSM模型，現(xiàn)將式(5)應(yīng)用到 GSVM模型中，使得：

這里定義一個(gè)新的文本向量，新向量中增加了ti和tj在文本dk中的TF-IDF權(quán)值，如下定義：

由新的文本向量可以產(chǎn)生一個(gè)新的GVSM模型，則兩個(gè)文本之間的相似度公式定義為：

其中n為向量的維度，dk和dp分別是兩篇不同的文檔。

3 實(shí)驗(yàn)

利用上述方法，本文實(shí)現(xiàn)了基于WordNet的語(yǔ)義相似度計(jì)算程序模塊。為了對(duì)相似度計(jì)算結(jié)果更好地進(jìn)行分析，本文評(píng)價(jià)的方案放在文本分類(lèi)系統(tǒng)中，以觀察不同計(jì)算方法對(duì)文本分類(lèi)系統(tǒng)性能的影響。

3.1 實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)

評(píng)價(jià)標(biāo)準(zhǔn)是在測(cè)試過(guò)程中所使用的一些用來(lái)評(píng)價(jià)分類(lèi)器分類(lèi)準(zhǔn)確度的量化標(biāo)準(zhǔn)。本文采用常用的三種標(biāo)準(zhǔn)，它們?cè)诓煌姆矫鎭?lái)評(píng)價(jià)一個(gè)分類(lèi)器。

準(zhǔn)確率（precision）= （分類(lèi)正確的文本數(shù)）/（實(shí)際分類(lèi)的文本數(shù)）

召回率（recall）= （分類(lèi)正確的文本數(shù)）/（應(yīng)有分類(lèi)正確的文本數(shù)）

3.2 實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)是在Windows XP操作系統(tǒng)、Eclipse開(kāi)發(fā)環(huán)境下,通過(guò)Java語(yǔ)言實(shí)現(xiàn)。實(shí)驗(yàn)是在1GB內(nèi)存、P4 3.0GHz CPU的PC機(jī)下進(jìn)行的。實(shí)驗(yàn)數(shù)據(jù)集采用的是20-Newsgroups文本數(shù)據(jù)集。20-Newsgrops是在UseNet上下載的20個(gè)類(lèi)的新聞組討論英文文章。數(shù)據(jù)集共有20個(gè)類(lèi)，每個(gè)類(lèi)大約1 000篇。20-Newsgroups是一個(gè)比較常用的文本數(shù)據(jù)集。出于效率考慮，本實(shí)驗(yàn)選取其中的5個(gè)類(lèi)別，針對(duì)不同數(shù)量的訓(xùn)練文本進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)分別選取了200、400、600、1 000、2 000 篇文本平均分配到編號(hào)為 A、B、C、D、E的5個(gè)集合。分別對(duì)基于TFIDF-VSM[3]模型和本文提出的基于WordNet的GVSM模型進(jìn)行了比較實(shí)驗(yàn)。本文采用KNN[8]分類(lèi)器進(jìn)行評(píng)價(jià)，測(cè)試結(jié)果記錄了上述5種情況分類(lèi)器的準(zhǔn)確率、召回率、F1值。

實(shí)驗(yàn)結(jié)果表明，采用基于WordNet的GVSM模型比基于TFIDF-VSM模型具有更高的準(zhǔn)確率、召回率、F1值。分析發(fā)現(xiàn)當(dāng)文本數(shù)越多時(shí)，文本分類(lèi)的準(zhǔn)確率、召回率、F1值越高。

本文提出了一個(gè)新的文本相似度計(jì)算方法，將其成功地應(yīng)用在文本分類(lèi)當(dāng)中，實(shí)驗(yàn)證明得到了很好的效果。首先基于WordNet構(gòu)建了語(yǔ)義網(wǎng)，分別考慮路徑長(zhǎng)度SPC和路徑深度SPE來(lái)計(jì)算兩個(gè)詞的語(yǔ)義關(guān)聯(lián)度；然后將其應(yīng)用在GVSM模型中計(jì)算文本相似度；最后應(yīng)用在文本分類(lèi)中，得到了較高的分類(lèi)準(zhǔn)確率和召回率。下一步準(zhǔn)備將其應(yīng)用到信息檢索中，以提高信息檢索的準(zhǔn)確率與效率。

[1] WILLETT P.Recent trends in hierarchical document clustering： a criticalreview.InfProcess and Manage，1988：577-597.

[2]夏天.漢語(yǔ)詞語(yǔ)語(yǔ)義相似度計(jì)算研究 [J].計(jì)算機(jī)工程，2007，33（6）：191-194.

[3]李峰，李芳.中文詞語(yǔ)語(yǔ)義相似度計(jì)算——基于《知網(wǎng)》2000[J].中文信息學(xué)報(bào)，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年生，碩士研究生，主要研究方向：信息檢索與文本數(shù)據(jù)挖掘。

鄭誠(chéng)，男，1964年生，副教授，碩士生導(dǎo)師，主要研究方向：數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)研究。

尹莉莉，女，1985年生，碩士研究生，主要研究方向：數(shù)據(jù)挖掘。