基于改進的Jaccard系數文檔相似度計算方法①

俞婷婷,徐彭娜,江育娥,林 劼

(福建師范大學 軟件學院,福州 350108)

基于改進的Jaccard系數文檔相似度計算方法①

俞婷婷,徐彭娜,江育娥,林 劼

(福建師范大學 軟件學院,福州 350108)

文本相似度主要應用于學術論文查重檢測、搜索引擎去重等領域,而傳統的文本相似度計算方法中的特征項提取與分詞環節過于冗雜,而且元素的隨機挑選也會產生權重的不確定性. 為了解決傳統方法的不足,提出一種基于改進的Jaccard系數確定文檔相似度的方法,該算法綜合考慮了各元素、樣本在文檔中的權重及其對多個文檔相似度的貢獻程度. 實驗結果表明,基于改進的Jaccard系數的文檔相似度算法具有實效性并且能夠得到較高的準確率,適用于各種長度的中英文文檔,有效地解決現有技術中存在的文檔間相似度計算不精的問題.

文本相似度; Jaccard 系數; 文本分析; 文本查重; 文本檢索

隨著現代計算機技術的快速發展與網絡的飛速普及,網上數據資源也在急速增加,豐富的數據資源為人們的生活提供了便利,也提高了人們的工作效率. 在這些數據資源給人們提供便利的同時,也出現了不少問題,如學術論文抄襲、新聞轉載等. 在這樣的背景下,文檔查重檢測應運而生. 相似度計算具有廣泛的應用前景,目前主要應用于學術論文查重檢測、電子檔版權、文本聚類、文本分類、問卷調查整理、搜索引擎去重等.

相似性數據的檢測數據量十分龐大. 在百度百科上,以中國學位論文全文數據庫收錄的學位論文為例[1],截止2011年10月,論文總量達200萬篇以上,每年以30萬篇以上的速度在增長. 再如,2016年4月份中國50所高校在線發表論文數量高達62 000篇以上[2],其中大部分的科研論文都需要進行相似性檢測. 如此龐大的數據,借助一種基于改進的Jaccard系數確定多個文檔相似度的方法進行檢測,實現多個文檔之間的相似性比對是很有必要的. 一個好的計算文檔相似度的方法在學術論文相似性檢測、文本聚類、文本分類、輿情調查等領域中具有重要意義.

本文第1節介紹文本相似度計算方法的現狀; 第2節介紹本文提出的相似度計算方法; 第3節通過實驗驗證并分析本文方法的有效性; 第4節對實驗結果進行總結并給出下一步研究工作.

1 相關研究工作

文本相似度是文本挖掘的一個重要內容,近年來不少研究人員對文本挖掘的研究也集中在文本相似度的計算上.

傳統的文本相似度計算方法一般采用向量空間模型[3],實際上就是將語義相似度用空間上的相似度來表達,對文本進行特征項選取后再對其做加權處理,用向量來表示特征項權重,使這些特征項權重從離散的數字轉化為一個個帶向量的分量,于是文本的相似度計算就轉化成特征項權重在高維空間內的相似度計算[4].這種計算方法直觀易懂,有效地將文本處理的問題轉化為數學問題. 但是在對特征項進行加權時向量空間模型沒有考慮到特征項在文本中的位置信息,并且忽略了各個特征項的語義在文本之間的關聯性. 許鑫[5]在實驗中對傳統的向量空間模型做了優化,提出了四種實驗方案,認為不僅要考慮到主題間內容上的語義相似度,還要兼顧到語義相似度低的鏈接中可能存在的相關關系. 基于編輯距離的基礎,G Sidorov[6]提出使用一種樹編輯距離的算法來計算文本相似度,實驗結果的準確率高于編輯距離. 賈惠娟[7]在有特征詞知識庫支持的前提條件下,提出將編輯距離與向量空間模型相結合構建一種新的文本相似度計算模型,雖然在數據預處理的過程中可能會丟失一些文本特征項,但是用于領域文檔查詢也取得不錯的效果.

為了解決傳統方法的不足,王小林[8]考慮到特征項在文本中的位置對權重的影響,對特征項添加了位置權重,進行信息增益和熵值計算,雖然該算法在一定程度上提高了查全率和查準率,但該算法的時間復雜度較高,還需進一步改進才能運用在實際環境中. 考慮到不同文本中特征項的頻率波動也會影響到特征項權值,周麗杰[9]將得到的特征項權值經過馬爾科夫模型與向量空間模型的結合,得到一個總體相似度,提高了準確率,忽略了關鍵詞在不同文檔中的權重問題. 與傳統的文本相似度算法不同,何維[10]從文本分析的粒度出發,將文本相似度用句子相似度來表示,結合KNN算法,得到的準確率和回歸率較為可觀.

為了得到更加精確的文本相似度結果,除了上述計算方法外,還有其他比較具有代表性的算法,Yang Liu[11]結合五種不同特征使用支持向量機對句子間語義相似度的得分進行預測,實驗結果表明該方案具有良好的泛化能力. Jiyi Li[12]通過給定的一個文檔集合充分利用不同的模型來評估文檔的語義相似度,觀察模型與線性或非線性因素的融合關系來選出一個最合適的模型表示. 李圣文[13]提出的一種基于熵的文本相似性算法,該方法基于字符的角度,考慮到文本間共同的字符串對相似度的影響,在提取文本間的字符信息后,對共同的字符串進行了維度上的度量,再用熵的方法進行相似度計算. 這種相似度方法在一定程度上避免了對長文本的特征提取,而是直接進行相似度計算,并且考慮到了字符串在不同長度文本中所占的比重. 更有一種基于圖形編輯距離的算法被Schuhm- acher[14]提出,用于計算兩個文本的語義距離,為文本相似度的計算提供了新思路.

N Kowsalya[15]提出的K-nearest模型有效解決了在文檔分類中會遇到的特征的高維性、數據的高容量等問題. 涂建軍[16]在特征提取算法中,通過對嵌套詞串的處理,有效地避免了在降維過程中存在丟失重要信息的問題. 在對短文本的處理上,X Yan[17]構建的 biterm主題模型可以發現較為突出和連貫的主題,該實驗結果優于R ?eh??ek[18]用傳統的LDA算法得到的結果.Zhifei Zhang[19]先是利用LDA對主題建模后對短文本中同義詞與多義詞的權重進行調整,得到較好的實驗結果. 王賢明[20]提出一種基于n-Gram的相似度算法操作簡單,避免了傳統文本相似度計算方法中提取特征項這一繁雜的環節,有效地提高了計算效率,但在計算權重的評價函數過程中,采用隨機挑選元素的方法,造成了元素權重的不確定性.

也有學者利用Jaccard相似度來實現文本相似度的計算,孫宇[21]利用Jaccard相似度實現了社團發現,并完成了聚類研究. Jaccard系數是兩元素交集與并集的個數之比,不考慮個體間具體差異值的大小,僅關注個體間是否存在共同的特征. 基于Jaccard系數可以成對評估數據的相似性和多樣性,Niwattanakul[22]將其用于比較關鍵詞之間的相似性,并在關鍵詞聚類上取得了較好的結果. Huang[23]對7個數據集采用5種最為廣泛使用的相似性措施,并表明Jaccard系數能達到最好的效果. 與現有的相似度計算方法不同,鄧琨[24]提出的JS和JSJ相似度計算方法,不僅可以反映出數據的局部相似性,還可以高效地從整體上來評估其相似關系.

針對傳統方法的不足,本文運用一種基于改進的Jaccard模型的計算方法,提出一種兼顧特征項權重與計算效率的文本相似度計算方法,用以獲得更準確的文本信息描述,提高文本分類性能.

2 方法及原理

文本相似度是指在兩篇或者多篇文檔中出現的詞語、句子、段落或者篇章的吻合程度. 兩篇文檔在詞語、句子、段落或者篇章上越相同或相似部分越多,代表著這兩篇文檔的相似度越高. 文檔相同是特殊的相似,即相似度為100%.

2.1 主要步驟

以下介紹本文方法的主要步驟:

(1) 給定參數K,K為文檔中移動窗口大小. 給定兩個文檔長度分別為n1、n2的文檔X和文檔Y. 確定文檔中長度為K的元素個數,并計算每個元素在文檔中所占的比重;

(2) 計算每個元素的Jaccard相似度;

(3) 計算每個元素在所有長度為K的元素中所占的比重;

(4) 確定每個K字元素的權重;

(5) 匯總所有K字元素相似度,計算文檔相似度.

2.2 步驟的詳細描述

以下是上述步驟的詳細解析.

(1) 確定文檔中長度為K的元素個數,并計算每個元素在文檔中所占的比重.

假設文檔X和Y的文檔長度分別為n1和n2,則文檔X中含有n1個長度為1的元素Xw1,含有(n1-1)個長度為2的元素Xw2,依此類推,文檔X中含有1個長度為n1的元素,這些元素的滑動窗口的大小為1,該滑動窗口從文本起始位置滑向終止位置進而形成了n-Gram.所以在文檔X中含有(n1-K+1)個長度為K的K字元素(1≤K≤n1),文檔Y中含有(n2-K+1)個長度為K的K字元素(1≤K≤n2).

而每個K字元素在文檔X、Y中所占的權重分別為:

(2) 計算元素的Jaccard相似度.

根據Jaccard相似度原理,文檔X和文檔Y的Jaccard相似度等于文檔X和文檔Y的交集大小與并集大小的比值. 若有元素wi同時存在于文檔X、Y中,那么該元素對應的兩文檔改進的Jaccard相似度為:

(3) 計算每個元素在所有長度為K的元素中所占的比重.

(4) 確定元素對文檔相似度是否有貢獻.

若元素同時出現在兩個文檔中,則該元素對文檔X和Y的文檔相似度有貢獻,F(wi)的值為1; 否則,F(wi)的值為0.

(5)計算文檔相似度.

文檔X和文檔Y的相似度評價函數如下:

2.3 示例

以下以具體文檔為實例來介紹本文的文本相似度方法.

例如在文檔X=“abcabc123”與文檔Y=“123abc”中,他們的文檔長度分別為n1=9和n2=6.

假設n-Gram長度K=3,那么在文檔X中含有7 個 n-Gram 長度為 3 的L字元素: {abc,bca,cab,abc,bc1,c12,123},在文檔Y中含有 4 個n-Gram 長度為3 的L字元素: {123,23a,3ab,abc}.

在文檔X中n-Gram長度為3的元素為{abc,bca,cab,bc1,c12,123},對應的數量分別為{2,1,1,1,1,1};在文檔Y中n-Gram長度為3的元素為{123,23a,3ab,abc},對應的數量分別為{1,1,1,1}.

由于元素wabc和w123同時出現在文檔X和文檔Y中,所以X、Y兩文檔改進的Jaccard相似度為:

文檔X、Y中所有元素為: wabc,wbca,wcab,wbc1,wc12,w123,w23a,w3ab,那么這些元素在文檔X和文檔Y所有n-Gram長度為3的元素中的所占的比重是:

由于元素wabc和w123同時出現在文檔X和文檔Y中,所以:

而元素 wbca,wcab,wbc1,wc12,w23a,w3ab不是同時出現在文檔X和文檔Y中,所以:

所以,文檔X和文檔Y的相似度為:

3 實驗設計及結果分析

3.1 實驗目的

本實驗的目的是驗證上述技術方案的有效性與準確度,且探討該技術方案下,元素的L字長度與相似度的關系.

3.2 實驗方案

本文的實驗數據來源于搜狗實驗室提供的文本分類語料庫[25],一共有 43 565 篇文本,從其中隨機選出8 000 篇長短不一的文檔. 為了減小實驗誤差,對 8 000篇文本進行字符處理,去掉文本中的空格與標點符號及一些特殊符號,如“●”,即不將上述符號計入文本長度中. 經過上述處理后,再篩選出文本長度超過10k的100篇文檔. 在接下來的實驗中,用與這些文檔的內容不相關的字符來對這100篇文檔進行字符替換,每篇文檔每次替換的字符數占其總字符數的5%、10%、…、95%這19個比例,即替換字符后的文檔與原文檔的字符重復比例為95%、90%、…、5%. 替換的位置是從每篇文本中任意篩選出來的,即經過字符替換后得到的文檔與原文檔的字符相異之處是隨機的. 本實驗的文檔內容涉及領域較為廣泛,如汽車、財經、健康、旅游等.

本實驗著重從兩個方面來驗證上述提出的計算文本相似度的有效性: (1) 驗證本方法計算得到的相似度與實際重復率之間的關系. (2) 分析L參數的選擇與計算精度的關系. 其中實驗一是通過改變L字計算不同字符重復比例下的文本相似度值; 實驗二則是利用實驗一得出的重復比例與相似度的相關性(精度),計算在不同L字長度的元素下相關性(精度)發生的變化.

實驗一. 驗證本方法計算得到的相似度與實際重復率之間的關系.

經過數據預處理,對得到的文本長度超過10 k的100個文檔,分別對其進行如下操作(為簡化問題,本實驗主要針對一篇文檔對不同L字時字符重復比例與相似度的關系進行探討與說明,而其余文檔的處理方式可以對照參考).

對于文檔A,分別按照不同重復比例對其進行字符替換,依次得到 19 個文檔: A1,A2,…,A19. 即文檔A1,A2,…,A19與文檔 A 的字符重復比例分別為 5%,10%,…,95%. 分別選擇不同長度的L字 (L=2,3,…,7)元素,計算在該元素長度下,文檔 A1,A2,…,A19與文檔A的文本相似度. 并計算100篇文檔19種重復比例的平均相似度.

實驗二. 分析L參數的選擇與計算精度的關系.

分別選擇不同長度的L字 (L=2,3,…,7),計算實驗得到的字符重復比例與文本相似度的關系,即相關性(精度),分析在不同L字長度的元素下相關性(精度)發生的變化.

3.3 實驗結果與分析

(1) 不同L字時重復比例與相似度的關系

對實驗數據的100個文檔與其在不同L字時重復比例與平均文本相似度的關系進行計算,得到的結果如圖1所示,橫坐標表示重復比例,縱坐標表示該重復比例下對應的平均文本相似度.

圖1 不同L字時重復比例與相似度的關系

對圖1進行以下分析:

1) 觀察圖中6種L字長度下重復比例與平均相似度的關系可以發現,在所有L字的實驗中,相似度總是隨著重復率的增加而增加,并且重復比例與平均相似度基本成線性關系. 隨著L字的增加,重復比例與相似度的線性回歸關系越明顯.

2) 相似度與重復比例不一定總呈現相等關系. 在實際應用過程中,可對訓練文本進行訓練得到相似度與重復率的對應關系,進而對測試文本進行計算,可根據計算所得的相似度結果推斷出實際重復率的值.

3) 從整體趨勢來看,圖中6種L字長度所對應的曲線沒有太大的差別. 這說明影響兩文本相似度的因素不只是所選L字長度. 并且隨著長度L字的不斷增加,相似度曲線趨于平穩,如L字為6、7的散點圖所對應的曲線明顯比2對應的曲線起伏更小,甚至接近一條直線. 這主要是因為,隨著L字不斷增加,相似度計算越精確,從而使最終結果趨于平穩.

(2) 計算相關性(精度)與L字長度的關系

如圖2所示,在L=2至7時,隨著L字長度的不斷增大,字符重復比例與相似度的相關性也呈現出增長的趨勢,即L字長度與相關性呈線性關系,L字的值取的越大,相似度計算得越精確,相關性遞增得比較明顯.但是L字大于7以后,相關性的遞增幅度為負數,L越大,相關性越低. 因此,在實際應用過程中,推薦L字的取值在7左右.

圖2 計算相關性 (精度)與L字長度的關系

4 結語

本文提出的一種基于改進的Jaccard系數確定文檔相似度的方法,綜合考慮了各元素、樣本在文檔中的權重及其對多個文檔相似度的貢獻程度,可以有效地解決現有技術中存在的文檔間相似度計算不精的問題. 另外,將本文提出的方法運用到多文檔相似度的確定,可以有效地避免元素因隨機挑選所帶來的權重的不確定性,還可以避免傳統文本相似度計算方法中不可避免的特征項提取與分詞環節中出現的高維問題.此外,本文的方法適用于各種長度的中、英文文檔. 實驗結果表明,一種基于改進的Jaccard系數確定文檔相似度的方法在一定程度上可以提高文檔間相似度計算的精度. 該方法計算簡單,速度快,精度高,可以應用在文本聚類、文本分類等文本挖掘技術中.

1百度百科. 中國學位論文全文數據庫. http://baike.baidu.com/view/7134347.htm,2011.

2中國科技論文在線. 2016年4月份各高校在線發表論文數量統計排序. 2016. http://www.edu.cn/rd/gao_xiao_cheng_guo/shu_ju_pai_hang/201605/t20160503_1393357.sh tml. [2016-10-11]

3Sidorov G,Velasquez F,Stamatatos E,et al. Syntactic N-grams as machine learning features for natural language processing. Expert Systems with Applications,2014,41(3):853–860. [doi: 10.1016/j.eswa.2013.08.015]

4薛蘇琴,牛永潔. 基于向量空間模型的中文文本相似度的研究. 電子設計工程,2016,24(10): 28–31. [doi: 10.3969/j.issn.1674-6236.2016.10.008]

5許鑫,蘇曉蘭. 基于文本計算和鏈接分析的主題導航優化-以 ERS 網站為例. 情報學報,2015,34(9): 938–948.

6Sidorov G,Gómez-Adorno H,Markov I,et al. Computing text similarity using tree edit distance. 2015 Annual Conference of the North American Fuzzy Information Processing Society (NAFIPS) Held Jointly with 2015 5th World Conference on Soft Computing (WConSC). Redmond,WA,USA.2015. 1–4.

7賈惠娟. 一種改進的文本相似度算法在政務系統中的應用. 信息技術與信息化,2016,(7): 49–52.

8王小林,肖慧,邰偉鵬. 基于 Hadoop 平臺的文本相似度檢測系統的研究. 計算機技術與發展,2015,25(8): 90–93.

9周麗杰,于偉海,郭成. 基于改進的 TF-IDF 方法的文本相似度算法研究. 泰山學院學報,2015,37(3): 18–22.

10何維. 基于多示例學習的中文文本表示及分類研究. 大連理工大學[碩士學位論文]. 大連: 大連理工大學,2009.

11Liu Y,Sun CJ,Lin L,et al. Computing semantic text similarity using rich features. 29th Pacific Asia Conference on Language,Information and Computation. Shanghai,China. 2015. 44–52.

12Li JY,Shimizu T,Yoshikawa M. Document similarity computation by combining multiple representation models.2015 16th IEEE/ACIS International Conference on Software Engineering,Artificial Intelligence,Networking and Parallel/Distributed Computing (SNPD). Takamatsu,Japan. 2015.1–6.

13李圣文,凌微,龔君芳,等. 一種基于熵的文本相似性計算方法. 計算機應用研究,2016,33(3): 665–668.

14Schuhmacher M,Ponzetto SP. Knowledge-based graph document modeling. Proc. of the 7th ACM International Conference on Web Search and Data Mining. New York,USA.2014. 543–552.

15Lin YS,Jiang JY,Lee SJ. A similarity measure for text classification and clustering. IEEE Trans. on Knowledge and Data Engineering,2014,26(7): 1575–1590. [doi: 10.1109/TKDE.2013.19]

16涂建軍,何漢林. 基于語義分析的降維特征提取. 情報學報,2014,33(9): 952–958.

17Yan XH,Guo JF,Lan YY,et al. A biterm topic model for short texts. Proc. of the 22nd International Conference on World Wide Web. Rio de Janeiro,Brazil. 2013. 1445–1456.

18?eh??ek R,Sojka P. Software framework for topic modelling with large corpora. Proc. of LREC 2010 Workshop New Challenges for NLP Frameworks. Valletta,Malta. 2010. 45–50.

19Zhang ZF,Miao DQ,Yue XD. Similarity measure for short texts using topic models and rough sets. Journal of Computational Information Systems,2013,9(16): 6603–6611.

20王賢明,胡智文,谷瓊. 一種基于隨機n-Grams的文本相似度計算方法. 情報學報,2013,32(7): 716–723.

21孫宇. 一種基于Jaccard相似度的社團發現方法. 電子技術與軟件工程,2016,(3): 20.

22Niwattanakul S,Singthongchai J,Naenudorn E,et al. Using of Jaccard coefficient for keywords similarity. Proc. of the International MultiConference of Engineers and Computer Scientists. Hong Kong,China. 2013. 380–384.

23Huang A. Similarity measures for text document clustering.New Zealand: The University of Waikato,Hamilton,2008.

24鄧琨,張堯學,周悅芝. 一種整體性的相似度計算方法. 情報學報,2014,33(11): 1133–1145.

25搜狗實驗室. 數據資源. http://www.sougou.com/labs/resources.html. [2012-04-21].

Text Similarity Method Based on the Improved Jaccard Coefficient

YU Ting-Ting,XU Peng-Na,JIANG Yu-E,LIN Jie

(Faculty of Software,Fujian Normal University,Fuzhou 350108,China)

Text similarity check is mainly used in Re-check detection of Papers,the deduplication of search engines and other fields. However,it’s extremely fussy to extract feature items with the traditional methods for computing the text similarity. In addition,it will bring uncertainty to select elements randomly. To solve these problems,a text similarity method based on improved Jaccard coefficient is proposed. This method takes into account the weights of elements and samples in the document,even the contribution degree to multiple text similarity. The results suggest that the text similarity method based on the improved Jaccard coefficient has been proved to be effective with a satisfactory accuracy,which can be applicable to various lengths of Chinese,English documents. It effectively solves the problem of inexact computing with existing technologies.

text similarity; Jaccard coefficient; text analysis; text checking; text retrieval

林 劼,E-mail: linjie891@163.com

俞婷婷,徐彭娜,江育娥,林劼.基于改進的Jaccard系數文檔相似度計算方法.計算機系統應用,2017,26(12):137–142. http://www.c-sa.org.cn/1003-3254/6123.html

國家自然科學基金(61472082); 福建省自然科學基金(2014J01220)

2017-03-21; 修改時間: 2017-04-13; 采用時間: 2017-04-17