一種圖文組合相似度算法的設(shè)計(jì)與優(yōu)化

鮮翠瓊 秦學(xué) 朱道恒 操淑敏

摘 ?要：包含文字和圖片的文檔作為信息的一種載體，能夠極大地豐富信息的表現(xiàn)形式。針對(duì)傳統(tǒng)計(jì)算圖文相似度的算法效率不高的問題，提出一種圖文組合相似度算法。將Jaccard相似系數(shù)引入余弦相似度，通過加權(quán)計(jì)算兩文本的相似度，然后用感知哈希算法計(jì)算文檔中圖片相似度并找出最大值，再計(jì)算單個(gè)文檔中所有圖片相似度均值，與文本相似度加權(quán)求得文檔的圖文相似度。最后通過一個(gè)文檔相似度查重系統(tǒng)驗(yàn)證了該算法能準(zhǔn)確高效地完成文檔之間相似度的量化，且優(yōu)化后的相似度算法能夠極大提高該系統(tǒng)的運(yùn)行效率。

關(guān)鍵詞：余弦相似度算法;Jaccard相似系數(shù);感知哈希算法;文本相似度

中圖分類號(hào)：TP391.1 ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract： As a carrier of information， documents containing both text and graphics can greatly enrich information. In view of the inconsistency of traditional algorithms for calculating similarity between graphics and text， this paper proposes a similarity algorithm for combining graphics and text. Jaccard similarity coefficient is introduced into cosine similarity， and the similarity of two kinds of text are calculated by weighting. Then， the graphic similarity in the document is calculated through PHash algorithm and the maximum value is derived. After that， the average similarity of all the graphics is calculated in a single document， and weighted with the text similarity， thus to obtain the similarity of both graphics and text of document. Finally， a document similarity check system is used to verify that the algorithm accurately and efficiently quantifies the similarity between documents， and the optimized similarity algorithm greatly improves the efficiency of the system.

Keywords： cosine similarity algorithm; Jaccard similarity coefficient; PHash similarity; text similarity

1 ? 引言（Introduction）

文本相似度分析是中文信息處理領(lǐng)域的一種基礎(chǔ)技術(shù)，凡是在處理中文信息處理的領(lǐng)域都有其身影。機(jī)器翻譯領(lǐng)域，文本相似度可作為翻譯準(zhǔn)確度的衡量原則[1];搜索引擎領(lǐng)域，文本相似度算法是其核心;自動(dòng)問答領(lǐng)域，文本相似度更是匹配回答與提問的重要技術(shù)[2];在論文查重領(lǐng)域，文本相似度研究更是系統(tǒng)檢測(cè)學(xué)術(shù)不端行為的唯一手段;在文本聚類領(lǐng)域，文本相似度也是聚類表中的重要參考[3];在新聞推薦、關(guān)聯(lián)詞推薦等智能精準(zhǔn)推薦領(lǐng)域，文本相似度研究更是其基礎(chǔ)工作[4]。而在計(jì)算機(jī)視覺領(lǐng)域，圖像相似度度量是一個(gè)基礎(chǔ)問題，它在圖像分類、圖像檢索、圖像匹配、模式識(shí)別和目標(biāo)檢測(cè)等多方面都有十分廣泛的應(yīng)用。因此，對(duì)圖像文本相似度度量的研究在諸多領(lǐng)域都有非常重要的意義。

2 ? 相關(guān)算法（Correlation algorithm）

2.1 ? 余弦相似度

余弦相似度又稱為余弦相似性，是通過測(cè)量?jī)蓚€(gè)向量的夾角的余弦值來度量它們之間的相似性。利用兩個(gè)向量之間的角度的余弦值確定兩個(gè)向量是否大致指向相同的方向。

將一個(gè)字符串通過分詞工具分成一個(gè)個(gè)詞語項(xiàng)，將這些詞語，映射到向量空間，形成字符串和向量數(shù)據(jù)的映射關(guān)系。利用詞語詞頻映射字符串向量。通過計(jì)算對(duì)應(yīng)向量的余弦值來表示兩個(gè)文本字符串在統(tǒng)計(jì)學(xué)方法中的相似度。

3.3 ? 算法優(yōu)化

上述算法是將所有圖片依次與其他圖片對(duì)比，對(duì)比完成后才處理結(jié)果，這樣在圖片重復(fù)度較高時(shí)會(huì)增加很多額外開銷。故在圖1所示的比較算法的10和11行間增加一個(gè)判斷語句，其余部分不變，如圖2所示。

改進(jìn)算法后系統(tǒng)運(yùn)行效率大幅提升，但仍受限于文檔中相似圖片的順序及數(shù)量。分析模塊調(diào)用算法，發(fā)現(xiàn)每組數(shù)據(jù)中只有幾十到幾百?gòu)垐D片，但圖片計(jì)算次數(shù)從幾百到幾十萬次。比較算法每計(jì)算一次就要對(duì)圖片進(jìn)行一次PHash處理，單次PHash處理很快，但幾十萬次PHash處理就會(huì)大大增加程序運(yùn)行時(shí)間。故考慮在圖片相似度計(jì)算發(fā)生前完成所有圖片的PHash處理，并將處理好的Hash指紋存儲(chǔ)起來。計(jì)算圖片相似度時(shí)不再調(diào)用Phash算法對(duì)圖片進(jìn)行DCT等計(jì)算，直接讀取已經(jīng)計(jì)算好的圖片Hash指紋。進(jìn)一步優(yōu)化比較算法如圖3所示。

4 ?實(shí)驗(yàn)驗(yàn)證與分析（Experimental verification and analysis）

4.1 ? 系統(tǒng)設(shè)計(jì)

設(shè)計(jì)一種文檔相似度查詢系統(tǒng)，應(yīng)用到判定作業(yè)是否抄襲的場(chǎng)景。系統(tǒng)主要包含六個(gè)模塊：文件導(dǎo)入模塊、文本相似度模塊、圖片相似度模塊、比較模塊、輸出模塊、可視化界面模塊，如圖4所示。系統(tǒng)可自動(dòng)識(shí)別txt文檔編碼格式，自動(dòng)分離Word中圖片和文字信息，然后按前面介紹的方法對(duì)圖片和文字分別計(jì)算相似度，加權(quán)求出文檔整體相似度，最后將全部比較數(shù)據(jù)輸入本地csv文檔中。此外可視化界面讓用戶使用時(shí)更加方便，只需把待比較文件放入同一文件夾下，將路徑傳入程序，便能自動(dòng)計(jì)算文件夾內(nèi)所有文檔的相似度，最后將結(jié)果導(dǎo)入到csv文件。

4.2 ? 測(cè)試結(jié)果分析

選四組數(shù)據(jù)（一組人工制造的有特殊相似度分布的數(shù)據(jù)加三組真實(shí)作業(yè)數(shù)據(jù)）進(jìn)行測(cè)試。第一組為兩份不同的文檔分別去除圖片和保留圖片放入待查重目錄進(jìn)行查重測(cè)試，產(chǎn)生特殊相似度分布的結(jié)果，方便檢查程序能否正常工作。另三組為實(shí)驗(yàn)報(bào)告合集，導(dǎo)入系統(tǒng)得到測(cè)試結(jié)果如表2—表5所示。

取第二組數(shù)據(jù)的測(cè)試結(jié)果作準(zhǔn)確性測(cè)試如圖5所示，得對(duì)比詳情如圖6所示。

從圖中看出，經(jīng)組合算法加權(quán)后的值更加光滑地表現(xiàn)了相似度分布，且處于各算法的中間值，趨于穩(wěn)定。從結(jié)果判斷具有極高相似度的數(shù)據(jù)量較小，隨數(shù)據(jù)量的增大，相似度在小范圍內(nèi)迅速下降，最后趨于平緩，符合實(shí)際情況。經(jīng)過人工比對(duì)加權(quán)相似度超過80%的99條比對(duì)結(jié)果，發(fā)現(xiàn)大部分內(nèi)容幾乎完全相同。在總加權(quán)相似度低于0.8但圖片相似度等其他三條相似度中兩條值偏高的文檔中，部分內(nèi)容也存在刪減性雷同。故實(shí)際使用時(shí)，判定抄襲的具體閾值還需實(shí)際作業(yè)類型來確定。一個(gè)字?jǐn)?shù)量龐大的作業(yè)，經(jīng)系統(tǒng)測(cè)試，當(dāng)加權(quán)相似度大于80%，或其他幾項(xiàng)文本相似度大于95%或圖片相似度大于90%才判定為抄襲的原則下，判定結(jié)果99.9%是準(zhǔn)確的。

4.3 ? 算法優(yōu)化后的測(cè)試結(jié)果

算法優(yōu)化后再次測(cè)試上述四組數(shù)據(jù)，優(yōu)化前后運(yùn)行時(shí)間對(duì)比如圖7—圖10所示。

從圖7至圖10可知，系統(tǒng)經(jīng)過優(yōu)化后，圖片處理次數(shù)從幾十萬次降至幾百次，極大地縮短了系統(tǒng)的運(yùn)算耗時(shí)。雖然會(huì)增加幾十萬次的讀取操作，但這個(gè)代價(jià)完全不值一提。測(cè)試數(shù)據(jù)整體運(yùn)行效率明顯提高，驗(yàn)證了改進(jìn)算法的有效性。

5 ? 結(jié)論（Conclusion）

針對(duì)傳統(tǒng)計(jì)算圖文相似度的算法效率低的問題，本文提出一種圖文組合相似度算法。通過將Jaccard相似系數(shù)引入余弦相似度通過加權(quán)計(jì)算文本間的相似度，再與PHash算法求得的圖片相似度均值加權(quán)后得到全文相似度，并對(duì)組合相似度算法作出優(yōu)化。最后在一個(gè)文檔相似度查重系統(tǒng)中驗(yàn)證了該算法的準(zhǔn)確性和可行性，并且運(yùn)行相似度優(yōu)化算法后，系統(tǒng)整體運(yùn)行效率得到極大提升。未來可以考慮引入詞頻權(quán)重

庫(kù)來提高計(jì)算準(zhǔn)確率，以及將系統(tǒng)部署在云服務(wù)器實(shí)現(xiàn)“云查重”來提升查詢效率。

參考文獻(xiàn)（References）

[1] 楊立波.基于CFN的相似度計(jì)算在實(shí)例機(jī)器翻譯中的應(yīng)用[J].電腦開發(fā)與應(yīng)用，2011，24（06）：58-60.

[2] 宋萬鵬.短文本相似度計(jì)算在用戶交互式問答系統(tǒng)中的應(yīng)用[D].中國(guó)科學(xué)技術(shù)大學(xué)，2010.

[3] 孫爽.基于語義相似度的文本聚類算法的研究[D].南京航空航天大學(xué)，2007.

[4] 田軍霞.基于短文本處理算法優(yōu)化的文本信息推薦系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].北京交通大學(xué)，2017.

[5] 金宇.基于常規(guī)水質(zhì)參數(shù)的供水管網(wǎng)特征污染物分類方法研究[D].浙江大學(xué)，2017.

[6] 張猛，李玲娟.基于改進(jìn)的Jaccard相似系數(shù)矩陣的社團(tuán)劃分算法[J].南京郵電大學(xué)學(xué)報(bào)（自然科學(xué)版），2018，38（06）：96-102.

[7] 金希茜.基于語義相似度的中文文本相似度算法研究[D].浙江工業(yè)大學(xué)，2009.

[8] 文心靈.方向離散余弦變換和方向離散小波變換及其在超聲圖像中的應(yīng)用[D].北京交通大學(xué)，2008.

[9] 唐菲駿.基于VC-1視頻標(biāo)準(zhǔn)的離散余弦變換實(shí)現(xiàn)及驗(yàn)證[D].西安科技大學(xué)，2012.

[10] Quyet Thang Dang， Trung Huy Phan. Determining Restricted Damerau-Levenshtein Edit-Distance of Two Languages by Extended Automata[P]. Computing and Communication Technologies， Research， Innovation， and Vision for the Future （RIVF）， 2010 IEEE RIVF International Conference on， 2010.

[11] F. Tichy， W. The string-to-string correction problem with block moves[J]. ACM Transactions on Computer Systems， 1984， 2（4）： 309-312.

[12] Anas M Al-Oraiqat， Natalya S. Kostyukova A Modified Image Comparison Algorithm Using Histogram Features[J]. ResearchGate， 2013， 4（1）： 152-156.

[13] 龔成清.基于Java的相似圖片搜索[J].電腦開發(fā)與應(yīng)用，2012，25（10）：13-15.

作者簡(jiǎn)介：

鮮翠瓊（1993-），女，碩士生.研究領(lǐng)域：數(shù)據(jù)挖掘與分析.

秦 ? 學(xué)（1980-），男，博士，副教授.研究領(lǐng)域：大數(shù)據(jù)環(huán)境下的電子政務(wù).

朱道恒（1992-），男，碩士生.研究領(lǐng)域：語義Web，數(shù)據(jù)挖掘.

操淑敏（1996-），女，碩士生.研究領(lǐng)域：數(shù)據(jù)挖掘與分析.