基于全文檢索的文本相似度算法應用研究*

王　格　吳　釗　李　向

(1.湖北文理學院數學與計算機科學學院　襄陽　441053)(2.中國地質大學(武漢)計算機學院　武漢　430074)

?

基于全文檢索的文本相似度算法應用研究*

王格1,2吳釗1李向2

(1.湖北文理學院數學與計算機科學學院襄陽441053)(2.中國地質大學(武漢)計算機學院武漢430074)

摘要在大量的文本數據中,針對不能快速有效地提取或查找有用信息及知識這個問題,以文本相似度計算為基礎的文本數據挖掘成為數據挖掘研究領域里的一個重要的課題。論文主要研究兩種不同的方法VSM余弦算法和Simhash來實現文本相似度的計算,首先采用傳統的VSM余弦算法和Simhash算法,按照余弦公式通過內積最終計算出文本間的相似度大小n(0

關鍵詞文本相似度; 余弦VSM; Simhash

Class NumberTP301.6

1　引言

文本相似度計算[1]是自然語言處理的一部分,可以計算一個文本中不同詞條的相似度,可以計算兩個文本間的相似度,也可以進行批處理,對多個文本之間進行兩兩計算,并輸出文本相似度的最后結果。在機器翻譯中,相似度可看作是用于衡量文本中詞語的可替換程度的參數;在信息檢索中,又可理解為文本內容與用戶想要搜索的資料的符合程度[2]等。

隨著科技的進步,計算機的普及以及Internet的飛速發展,文本信息的大量增長,文本相似度計算在信息檢索的效率提高方面,對于發表的文章中抄襲的檢測,對于文章相似信息進行壓縮存儲以便節省存儲空間的方面都起到了很大的作用。然而對于英文的文本相似度計算的時候,英文單詞本身是有空格分開的,這樣以單詞來處理一個英文文本進行比較就很簡單。

但是中文是沒有分隔的,需要加入很多詞義,中文是使用多個連續的字如雙字、四字成語來表達一個意思,并且在中文的前后語境的不同,一個詞語的意思也是不同的,并且有時候中文還會產生歧義,目前對文本的處理方式如圖1所示。

圖1　文本分詞處理方法

長久以來,國內外的很多學者一直在研究文本相似度的計算問題,對于文本相似度計算提出了一些解決的方案。著名的VSM向量空間模型(Vector Space Model)是由Gerard Salton等[3]在1969年首先提出的,文本映射成為N維空間向量,通過向量降維處理,詞頻統計和比較向量間的關系來計算相似度。在傳統的空間向量模型中,所使用的詞語向量之間是沒有任何語義聯系的,僅僅只是不同的詞語代表的向量就是不同。為此廣義向量空間模型(Generalized Vector Space Model,GVSM)[4]則使用了語義之間的聯系,使用文本代替詞語來表達文本之間的關系。Deerwester[5]等提出的隱性語義索引(Latent Semantic Indexing)也是文本相似度計算的有效方法,Oleshchuk等[6]在文本相似度計算中引入了本體論,提出了基于Ontology out的文本相似度比較方法,這個方法可以通過語義計算文本詞語的相似度。2002年由Google的Charikar[7]提出一種Simhash算法,將一篇文檔轉化為n位的簽名,通過比較簽名的相似度來計算原文檔的相似度。

國內學者中2001年,張煥炯、王國勝等提出了漢明碼的概念[8],利用漢明距離來計算文本相似度,較好地提高了相似度計算速度。2004年晉耀紅[9]提出了語境框架的新語義模型,實現了文本間語義相似度的量化,取得了較好的計算效果。2008年,曹恬、周麗、張國煊[10]等提出了基于詞共現的文本相似度計算方法。2013王振振[11]等提出了一種基于LDA主題模型的文本相似度計算方法,挖掘隱藏在文本內的不同主題與詞之間的關系,能夠明顯提高文本相似度計算的準確率。

本文對現有的兩種文本相似度計算方法VSM和Simhash進行研究,目的是為了對這兩種方法的優劣進行更深入的了解,以提高文本相似度計算的精度和有效性,用以對相關的應用起到引導以及參考作用。

2　VSM算法

文本在向量空間模型中代表的是各種電腦可以識別的數據,該數據使用Document表示,文本的關鍵字Key是指在該數據中出現而且可以代表該文章不同于其他文章或者代表文章中觀點的基本單位,關鍵字可以用文章之中特定的詞語表示,可以用關鍵字集表示文本為D(K1,K2,…,Kn),其中Ki是關鍵字,1≤i≤n。

文本之中有a,b,c,d這幾個關鍵字,那么這篇文本就可以用D(a,b,c,d)表示。對含有n個關鍵字的文本而言,通常會給每個關鍵字K的出現次數作為其代表的權重W來表示該關鍵字對文本的重要程度。D=D(K1,W1,K2,W2,…,Kn,Wn),簡記為D=D(W1,W2,…,Wn),這種方式叫做該文本D的向量代表方法。

其中Wi是Ki的權重,1≤i≤n。該文本之中,其關鍵字a,b,c,d的權重分別設置為30,20,20,10,就可以將該文本表示為D(30,20,20,10)。在VSM的向量空間之中,要計算的文本D1和D2的文本相似程度Sim(D1,D2)就可以使用文本之間的計算所得的文本向量余弦值大小表示:

(1)

式中,W1i,W2i表示文本D1和D2第i個關鍵字的權值,1≤i≤n。

在搜索文本的時候就可以計算待搜索文本和數據庫中文本的相似度進行余弦計算,其算法的流程圖如圖2所示。

例如待搜索文本Di的關鍵字為a,b,c,d,關鍵字權值分別為30,20,20,10,數據庫待核實文本C1的關鍵字為a,c,d,e,關鍵字權值分別為40,30,20,10,則D1的向量代表方法為D1(30,20,20,10,0),C1的向量代表方法為C1(40,0,30,20,10),根據式(1)計算待搜索文本D1與數據庫中待核實文本C1文本相似度是0.86。

圖2　VSM算法流程

文本相似度0.86的計算方法如下。

它的模:

(2)

兩個向量的點積:

(3)

(4)

(5)

物理意義就是兩個向量的空間夾角的余弦數值,下面是代入公式的過程:

=2000

(6)

(7)

(8)

(9)

3　Simhash算法

圖3　Simhash算法流程圖

Simhash算法是由Charikar[6]于2002年提出新的算法,這個算法也是目前被認同為最好、最有效的網頁相似內容去重算法,Simhash算法實質上是一種可傳統的Hash算法只負責將原始內容盡量均勻隨機地映射為一個簽名值,原理上相當于偽隨機數產生算法。而Simhash算法則是基于概率的文本相似度計算方法,對于一篇文章,提取出其中關鍵詞,然后將這些關鍵詞Hash一次,得到n位長度的Hash值,Hash值為1的,特征向量就為1,當Hash值為0,特征向量就為-1,如果要考慮權重,就在特征向量基礎上乘以權重,就是這個詞的向量值,一篇文檔的所有詞的向量累加,這個向量為全文主向量,大于或等于零的分量,映射為1,小于0的,映射為0,這相關得出全文的Simhash值,這個叫文本的簽名。通過比較不同文本之間簽名則可直接得到文本相似度,該算法的流程圖如圖3所示。

Simhash算法的步驟:

1) 先將文本定義為一個n維的向量D,將D的所有維度均置為0;再定義一個n位的二進制數x作為該文本的特征數并將其初始化為0;

2) 對文本之中每一個關鍵字:對該關鍵字使用傳統的Hash算法計算得到一個n位的二進制數y;

3) 對于i∈(0,n)進行循環操作:

如果二進制數y的第i位為1,則D的第i個維度的元素值加上該關鍵字的權重;

如果其為0,D的第i個維度的元素值減去該關鍵字的權重。

4) 再觀察D中的元素值,如果D的第i個元素值大于0,則二進制x的第i位設置為1,否則設置為0,并輸出文本的特征數x。

首先將所需要進行文本相似度計算的多個文章進行一個映射,不管這個映射是怎樣進行的,只需要得到該文本與其它文本完全不相似的映射,因為Hash算法就是對于不同的數據得到的Hash值是完全不相同的,于是對于每個關鍵字進行Hash處理,所得到的Hash值是均勻的隨機分布,且唯一的。如果一個關鍵字的Hash結果對應的二進制x的值為101010…0001,則其在算法中對應的向量大小為(k,-k,k,-k,k,-k,…,-k,-k,-k,k)T,其中k為當前關鍵字的權重,也就是說當其二進制數值為0是當前向量位置就為負值的權重,為1則為權重值大小。然后,將該文本所有的關鍵字的n維向量進行求和計算,此時會得到一個n位的1,0串,該串就表示該文檔的特征數。

為了得到這個n位的1,0串,進行求和計算的時候,如果第i位的數字大于等于1則將x該位的數據置為1,如果小于等于0,則將x該位的數據置為0。

3.1隨機超平面Hash算法

Simhash在數學運算中的方法具有可行性,但是,在2個文本相似較高的時候它們的特征數x是否會比較相似,在Google發布的Simhash的方法之中并沒有給出Google所使用的具體的Simhash算法和證明,本來在對其進行了試驗之后得到了下面的這些想法。

Simhash的算法思路是使用了Sandom hyperplane hash算法,其算法思路為對于一個n維的向量D:

1) 先定義k個n維的向量r1,r2,…,rk;

2) 對每一個向量ri(0

算法之中將每一維的向量都視做一個特定的hyperplane,在D在該hyperplane的投影值大于1則修改x在當前的元素值為1,否則就置其為0。對于2個不同的n維向量A,B來說,它們之間有一個夾角θ,對于任意一個hyperplane來說,能將2個向量分開的概率為θ/π,所以它們的特征數x在某一位的元素值不同的概率也是θ/π。所以可以使用hamming distance來計算2個n維向量之間的特征數所有元素值不同的數值總和來表示不同向量之間的差異程度。

3.2Simhash算法與隨機超平面Hash算法的比較

Simhash的算法之中使用Random Hyperplane Hash算法,Simhash并未使用Hyperplane的向量,而是使用關鍵字在某一位的數值如果為1則不變,為0則置其值為-1,這樣便有n位的特征值x得到了n維的空間隨機向量。對應了n維的Hyperplane。

下面是一個特殊的例子,首先使用5個關鍵字來代表某個特定的文本,并且得到一個4位的特征數,所以假設5個關鍵字的4位特征數分別為x1=1010,x2=1100,x3=1110,x4=1000,x5=0001;則對應的向量為(1,-1,1,-1),(1,1,-1,-1),(1,1,1,-1)(1,-1,-1,-1),(-1,-1,-1,1);再由算法中的第三步可以進行相同位數間的求和運算,得到的結果為(3,-1,-1,-3),由算法中的第四步可以得到文本的特征數x為1001。而對于Random Hyperplane Hash算法來說進行4個5維的向量(1,1,1,1,-1),(-1,1,1,-1,-1),(1,-1,1,-1,-1),(-1,-1,-1,-1,1)按照Random Hyperplane Hash算法可以得到向量D與4個5維向量的乘積結果為(3,-1,-1,3),所求得的文本的特征數也是1001。由兩種不同的算法所求得的文本特征數的結果都是1001,可以看出Simhash算法和Random Hyperplane Hash算法的思路是相同的,通過計算Simhash所得的特征數的Hamming distance,可以計算出兩個文本之間的相似程度。

由于本文使用的是C++的來進行Simhash的算法設計,由于C++中最大的數據只能使用long long類型來定義的2進制數只有最大2的63次方,在進行Simhash算法的時候還需進行乘法運算,經過測試使用50位的2進制串是比較合適的,但是由于2進制串的位數較少,算法精度不夠精準,本文又使用了Python進行編碼,再使用C++進行Python的調用,這樣就使2進制數的特征數達到了128位,對比2個Simhash的計算數值,也可以看出精度不同的區別。

4　實驗結果以及結果分析

4.1實驗數據

本文處理的文本是由網上找尋的一篇論文之中的幾段話,作為實驗中的原數據,來進行它們之間的文本相似度計算。

文本a.txt和文本b.txt中的文本數據是比較相似的如圖4和圖5中所示,用來做一組對照。而c.txt和d.txt中數據之間沒有任何的相似度,和a.txt與b.txt也沒有任何的相似程度如圖6和7中所示。

4.2實驗結果與對比分析

系統采用C++MFC界面并在Visual Studio 2010中實現,分別為瀏覽需要進行比較的文本并顯示其訪問路徑,然后對文本進行Simhash1(C++),Simhash2(Python),余弦算法的計算。

圖4　實驗數據a.txt

圖5　實驗數據b.txt

圖6　實驗數據c.txt

圖7　實驗數據d.txt

4.2.1實驗結果

將實驗數據a.txt,b.txt,c.txt,d.txt,進行比較,其中b.txt和a.txt的正反比較以及a.txt和a.txt的比較為對照比較。

表1　實驗結果

將實驗結果對照的結果用表1和圖8表示出來。

圖8　實驗結果折線圖

4.2.2實驗結果分析

Simhash算法,對于一篇文章,用分詞的方式將它分出詞來,然后將這些詞Hash一次,得到n位長度的Hash值,Hash值為1的,特征向量就為1,當Hash值為0,特征向量就為-1,如果要考慮權重,就在特征向量基礎上乘以權重,就是這個詞的向量值,一篇文檔的所有詞的向量累加,這個向量為全文主向量,大于或等于零的分量,映射為1,小于0的,映射為0,這相關得出全文的Hash值,這個叫全文的簽名。

對于文本a.txt和b.txt,它們本身只有幾個單詞的細微差別,對于整個文本而言是很少的Simhash1計算結果為0.971627,該結果準確度較低;Simhash2的計算結果為0.999939,該結果的準確度相當高;余弦算法VSM的計算結果為0.993358,該結果的精確度也是比較高的。對于文本a.txt和c.txt因為它們之間的聯系度非常之低,可以進行結果比較三種算法的準確度。Simhash1的計算結果為0.027991,雖然由于精度的原因該結果還是比較準確度;Simhash2的計算結果為0.000486,該結果是非常準確的;余弦算法VSM的結果為0.405043,該結果就非常不準確了。如數據所示,Simhash1與Simhash2相比較而言,由于C++中long long的數據限制使2進制10串的長度低于Python中128位的2進制10串,所以導致計算結果的不穩定,而余弦算

法,因為其算法本身的原因,其算法的準確度和Simhash1與Simhash2就相差很遠。

因此可以得出結論,余弦算法VSM由于其局限性已經不適合進行文本的相似度計算。而Simhash算法不管是因為C++的精度問題還是直接Python進行的128高精度計算都可以看出該基于概率的算法的高準確度具備可行性。

5　結語

本文對現有的兩種文本相似度計算方法VSM和Simhash進行研究,通過對文本進行Simhash1(C++),Simhash2(Python),余弦算法的計算,得出這兩種方法的優劣性,余弦算法VSM不適合進行文本的相似度計算,而Simhash算法基于概率的高準確度具有可行性,可以借此來給相關的應用提供參考,提高文本相似度計算的精度和有效性。

參 考 文 獻

[1] 宋玲,馬軍,連莉,等.文檔相似度綜合計算研究[J].計算機工程與應用,2006,30:160-163.

SONG Ling, MA Jun, LIAN Li, et al. The comprehensive computing research on document similarity[J]. Computer Engineering and Applications,2006,30:160-163.

[2] 劉麗珍,宋瀚濤.文本分類中的特征選取[J].計算機工程,2004,30(4):14-15.

LIU Lizhen, SONG Hantao. The feature selection oftext classification[J]. Computer Engineering,2004,30(4):14-15.

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

[4] Wong S K M, Ziarko W, Wong P C N. Generalized vector spaces model in information retrieval[C]//Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval. ACM,1985:18-25.

[5] Deerwester S C, Dumais S T, Landauer T K, et al. Indexing by latent semantic analysis[J]. JAsIs,1990,41(6):391-407.

[6] Oleshchuk V, Pedersen A. Ontology based semantic similarity comparison ofdocuments[C]//Proceedings of the 14th International Workshop on Database and Expert Systems Applications. IEEE,2003:735-738.

[7] Charikar M S. Similarity estimation techniques from rounding algorithms[C]//Proceedings of the thiry-fourth annual ACM symposium on Theory of Computing. ACM,2002:380-388.

[8] 張煥炯,王國勝,鐘義信.基于漢明距離的文本相度計算[J].計算機工程與應用,2001,21(2):21-22.

ZHANG Huanjiong, WANG Guosheng, ZHONG Yixin. The text similarity calculation based on hamming distance[J]. Computer Engineering and Applications,2001,21(2):21-22.

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

JIN Yaohong. The text similarity calculation based on thecontext framework[J]. Computer Engineering and Applications,2004,16:36-39.

[10] 曹恬,周麗,張國煊.一種基于詞共現的文本似度計算[J].計算機工程與科學,2008,29(3):52-53.

CAO Tian, ZHOU Li, ZHANG Guoxuan. A kind of textsimilarity computing based on wordco-occurrence[J]. Computer Engineering and Applications,2008,29(3):52-53.

[11] 王振振,何明,杜永萍.基于LDA主題模型的文本相似度計算[J].計算機科學,2013,12:229-232.

WANG Zhenzhen, HE Ming, DU Yongping. The text similarity calculation based on the LDA theme model[J]. Computer Science,2013,12:229-232.

收稿日期:2015年10月7日,修回日期:2015年11月23日

基金項目:國家自然科學基金項目“高可靠服務組合快速優化方法研究”(編號:61172084)資助。

作者簡介:王格,女,碩士研究生,研究方向:智能計算及應用。吳釗,男,博士研究生,教授,碩士生導師,研究方向:云計算、物聯網、大數據處理。李向,男,博士研究生,副教授,碩士生導師,研究方向:智能計算及應用。

中圖分類號TP301.6

DOI:10.3969/j.issn.1672-9722.2016.04.001

Application of Text Similar Algorithm Based on Full-text Retrieval

WANG Ge1,2WU Zhao1LI Xiang2

(1. School of Mathematics and Computer Science, Hubei University of Arts and Science, Xiangyang441053)(2. School of Computer Science and Technology, China University of Geosciences, Wuhan430074)

AbstractIn a large number of text data, due to the problem that it can’t quickly and efficiently find useful information and knowledge, text data mining on the basis of the text similarity calculation becomes an important research topic in the field of data mining. In this paper, Simhash and VSM cosine algorithm are used to realize the text similarity calculation. First, the traditional VSM cosine algorithm and Simhash algorithm are adopted to calculate the degree of similarity between the text size n(0

Key Wordstext similarity, cosine VSM, Simhash