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

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

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

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

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

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

文本相似度; Jaccard 系數(shù); 文本分析; 文本查重; 文本檢索

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

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

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

1 相關(guān)研究工作

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

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

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

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

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

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

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

2 方法及原理

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

2.1 主要步驟

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

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

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

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

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

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

2.2 步驟的詳細描述

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

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

假設文檔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中所占的權(quán)重分別為:

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

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

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

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

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

(5)計算文檔相似度.

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

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},對應的數(shù)量分別為{2,1,1,1,1,1};在文檔Y中n-Gram長度為3的元素為{123,23a,3ab,abc},對應的數(shù)量分別為{1,1,1,1}.

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

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

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

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

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

3 實驗設計及結(jié)果分析

3.1 實驗目的

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

3.2 實驗方案

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

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

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

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

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

實驗二. 分析L參數(shù)的選擇與計算精度的關(guān)系.

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

3.3 實驗結(jié)果與分析

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

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

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

對圖1進行以下分析:

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

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

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

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

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

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

4 結(jié)語

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

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

2中國科技論文在線. 2016年4月份各高校在線發(fā)表論文數(shù)量統(tǒng)計排序. 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許鑫,蘇曉蘭. 基于文本計算和鏈接分析的主題導航優(yōu)化-以 ERS 網(wǎng)站為例. 情報學報,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賈惠娟. 一種改進的文本相似度算法在政務系統(tǒng)中的應用. 信息技術(shù)與信息化,2016,(7): 49–52.

8王小林,肖慧,邰偉鵬. 基于 Hadoop 平臺的文本相似度檢測系統(tǒng)的研究. 計算機技術(shù)與發(fā)展,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相似度的社團發(fā)現(xiàn)方法. 電子技術(shù)與軟件工程,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鄧琨,張堯?qū)W,周悅芝. 一種整體性的相似度計算方法. 情報學報,2014,33(11): 1133–1145.

25搜狗實驗室. 數(shù)據(jù)資源. 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系數(shù)文檔相似度計算方法.計算機系統(tǒng)應用,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