基于Hadoop的抄襲檢測的源檢索方法研究

王素紅，寧慧，王明星，徐麗

哈爾濱工程大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001

?

基于Hadoop的抄襲檢測的源檢索方法研究

王素紅，寧慧，王明星，徐麗

哈爾濱工程大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001

摘要：隨著科學(xué)技術(shù)的發(fā)展和互聯(lián)網(wǎng)的普及，網(wǎng)絡(luò)給人們帶來便利的同時，也給抄襲剽竊提供了機(jī)會，現(xiàn)在抄襲檢測已經(jīng)成為一個重要的研究課題。本文分析了傳統(tǒng)抄襲檢測系統(tǒng)源檢索模塊的優(yōu)缺點(diǎn)，結(jié)合分布式系統(tǒng)的特點(diǎn)，提出基于索引分片的源檢索體系結(jié)構(gòu)，在大規(guī)模數(shù)據(jù)集上進(jìn)行抄襲檢測研究，以便快速的檢測出可疑文檔的備選文集。通過實(shí)驗(yàn)證明，基于索引分片的源檢索結(jié)構(gòu)能夠應(yīng)對大規(guī)模數(shù)據(jù)集的處理要求，有效的提高了源檢索階段的時間性能，同時也保證了抄襲檢測系統(tǒng)的可靠性。

關(guān)鍵詞：抄襲；抄襲檢測；大規(guī)模數(shù)據(jù)集；源檢索；Hadoop 分布式源檢索模塊的主要功能是對大規(guī)模備選文檔數(shù)據(jù)集批量的構(gòu)建索引和接收查詢進(jìn)行分布式檢索，最后返回候選文檔集。從功能上能看出，分布式源檢索模塊包括2個子模塊：索引更新模塊和檢索模塊，如圖1所示。 檢索模塊接收查詢，將查詢請求發(fā)送到索引庫中進(jìn)行分布式查詢，檢索接口返回的是候選文檔集[11]。

寧慧(1964-)，女，副教授，碩士生導(dǎo)師.

隨著互聯(lián)網(wǎng)的發(fā)展，大量有價值的學(xué)術(shù)論文以及資料被發(fā)布在網(wǎng)絡(luò)上的同時，也為文本抄襲提供了便利。文本抄襲是指抄襲者將他人的作品沒有修改或者做出少量修改后使用而不做引用說明的行為。抄襲檢測是指人們利用計算機(jī)各方面的研究技術(shù)，檢測數(shù)字產(chǎn)品是否復(fù)制其他數(shù)字產(chǎn)品的過程。當(dāng)前的抄襲檢測系統(tǒng)存在很多問題。大規(guī)模備選文檔數(shù)據(jù)集上的抄襲檢測系統(tǒng)研究尚不成熟。隨著抄襲檢測的備選文檔數(shù)據(jù)集的迅速增長，基于單機(jī)的抄襲檢測系統(tǒng)已經(jīng)無法滿足大規(guī)模數(shù)據(jù)集的存儲需求和計算力需求，如何使抄襲檢測系統(tǒng)能夠適應(yīng)大規(guī)模數(shù)據(jù)集，從大規(guī)模數(shù)據(jù)集中獲取與可疑文本相似的抄襲片段，有待進(jìn)一步研究。

針對以上問題，文中提出了基于Hadoop[1]的抄襲檢測方法，使得抄襲檢測系統(tǒng)在數(shù)據(jù)存儲和計算資源上能夠應(yīng)對大規(guī)模的備選文檔數(shù)據(jù)集。

1相關(guān)技術(shù)介紹

1.1Hadoop簡介

Hadoop是Apache軟件基金會旗下的一個開源分布式計算平臺。以HDFS[2]和MapReduce[3]為核心的Hadoop為用戶提供了系統(tǒng)底層細(xì)節(jié)透明的分布式基礎(chǔ)架構(gòu)。HDFS的高容錯性、高伸縮性等優(yōu)點(diǎn)允許用戶將Hadoop部署在低廉的硬件上，形成分布式系統(tǒng)；MapReduce分布式編程模型允許用戶在不了解分布式系統(tǒng)底層細(xì)節(jié)的情況下開發(fā)并行應(yīng)用程序。所以用戶可以利用Hadoop輕松地組織計算機(jī)資源，從而搭建自己的分布式計算平臺，并且可以充分利用集群的計算和存儲能力，完成海量數(shù)據(jù)的處理。

Apache Hadoop的流行與大數(shù)據(jù)處理的興起關(guān)系密切。眾所周知，現(xiàn)代社會的信息量增長速度極快，這些信息里又積累著大量的數(shù)據(jù)，其中包括個人數(shù)據(jù)和工業(yè)數(shù)據(jù)。預(yù)計到2020年，每年產(chǎn)生的數(shù)字信息將會有超過1/3的內(nèi)容駐留在云平臺中或借助云平臺處理。人們需要對這些數(shù)據(jù)進(jìn)行分析和處理，以獲取更多有價值的信息。為了高效地存儲、管理和分析這些數(shù)據(jù)，可以選用Hadoop系統(tǒng)，它在處理這類問題時，采用了分布式存儲方式，提高了讀寫速度，并擴(kuò)大了存儲容量。采用MapReduce來整合分布式文件系統(tǒng)上的數(shù)據(jù)，可保證分析和處理數(shù)據(jù)的高效。與此同時，Hadoop還采用存儲冗余數(shù)據(jù)的方式保證了數(shù)據(jù)的安全性。

1.2 實(shí)驗(yàn)評測方法

該實(shí)驗(yàn)所使用的評價函數(shù)是信息檢索領(lǐng)域常用評價函數(shù)，分別為精確率(precision)，召回率(recall)和F1值[4]。在抄襲檢測的源檢索階段主要使用這3個評測指標(biāo)來進(jìn)行評測。精確率是用來衡量檢索出來的數(shù)據(jù)的準(zhǔn)確性，計算方法是正確的結(jié)果數(shù)與檢索返回的總數(shù)目的比值。召回率是用來衡量可以成功檢索到相關(guān)文本的可能性，計算方法是檢索到的正確的數(shù)據(jù)個數(shù)與標(biāo)準(zhǔn)答案所提供的總的相關(guān)個數(shù)的比值。F1值可以平衡地反映召回率與準(zhǔn)確率。F1值的公式如式(1)所示：

(1)

式中：R是召回率：

(2)

其中：P 是精確率：

(3)

其中：TP是指系統(tǒng)檢索到的相關(guān)文檔；FP是指系統(tǒng)未檢索到的相關(guān)文檔數(shù)；FN是系統(tǒng)檢索到的不相關(guān)的文檔數(shù)；F1值是調(diào)和函數(shù)，用于平衡召回率和精確率的值，是系統(tǒng)的最終評價指標(biāo)。

2源檢索模塊研究

2.1基于索引分片的源檢索研究

文中提出基于索引分片的源檢索模塊結(jié)構(gòu)。分布式檢索的基礎(chǔ)是分布式索引[5]，即邏輯索引被劃分成很多子索引，且這些子索引部署在不同的服務(wù)器上[6]，利用Hadoop可以實(shí)現(xiàn)分布式檢索模塊[7]。

該檢索模塊充分地利用了基于Hadoop的分布式集群所提供的存儲能力、計算能力，并且保證了源檢索模塊的高可靠性。

基于索引分片[8]的源檢索模塊結(jié)構(gòu)也把備選文檔數(shù)據(jù)集的邏輯索引劃分成多個子索引，每個子索引會有多個副本索引，所有的副本索引會被部署在Hadoop分布式集群的源檢索服務(wù)器上。在文中采用Apache Zookeeper集群協(xié)調(diào)和管理分布式集群。

圖1　基于索引分片的源檢索模塊

2.2索引更新模塊

索引更新模塊接收備選文檔數(shù)據(jù)集，批量構(gòu)建索引并部署到分布式集群中，將索引存儲在源檢索服務(wù)器上。集群中每個源檢索服務(wù)器可以包含多個處理單元，每個處理單元能獨(dú)立的提供索引更新或檢索功能[9]。索引更新模塊負(fù)責(zé)增量索引、文檔的刪除等。

源檢索模塊索引更新流程如下：

1)客戶端把需要索引更新的數(shù)據(jù)提交到服務(wù)器集群，集群中與邏輯索引相關(guān)的任一副本索引節(jié)點(diǎn)都有可能接收到更新請求。

2)如果該副本索引節(jié)點(diǎn)不是對應(yīng)的子索引的主節(jié)點(diǎn)，它就會把更新請求轉(zhuǎn)發(fā)給和自己是同一子索引上的主節(jié)點(diǎn)。

3)主節(jié)點(diǎn)把備選文檔數(shù)據(jù)的更新請求轉(zhuǎn)發(fā)給同一子索引的所有其他副本索引節(jié)點(diǎn)，所有節(jié)點(diǎn)都要執(zhí)行更新請求。

4)如果備選文檔數(shù)據(jù)的更新請求基于轉(zhuǎn)發(fā)規(guī)則并不屬于當(dāng)前子索引，主節(jié)點(diǎn)會把它轉(zhuǎn)交給相應(yīng)的子索引的主節(jié)點(diǎn)。

5)對應(yīng)的主節(jié)點(diǎn)會把備選文檔數(shù)據(jù)的更新請求轉(zhuǎn)發(fā)給該子索引的所有其他副本索引節(jié)點(diǎn)，所有的副本索引節(jié)點(diǎn)都需要執(zhí)行更新請求。

分布式源檢索模塊中的子索引主節(jié)點(diǎn)接收到備選文檔集數(shù)據(jù)的更新請求后，必須確定當(dāng)前更新請求屬于邏輯索引的哪個子索引。在基于索引分片的源檢索模塊中，負(fù)責(zé)分布式更新邏輯處理中的是一個Hash算法[10]，由此來決定更新記錄具體分配到哪個子索引。算法代碼如下所示。

private int hash(AddUpdateCommandcmd) {

String hashableId = cmd.getHashableId();

return Hash.murmurhash3_x86_32(hashableId, 0, hashableId.length(), 0);

}

private int hash(DeleteUpdateCommandcmd) {

return Hash.murmurhash3_x86_32(cmd.getId(), 0, cmd.getId().length(), 0);

}

其中cmd.getHashableId()方法返回的是備選文檔集數(shù)據(jù)的主鍵的值，通過其hash值定位更新到哪個子索引。

2.3檢索模塊

源檢索模塊會把邏輯索引劃分成多個子索引，客戶端向源檢索服務(wù)器集群中包含這個邏輯索引的任意源檢索服務(wù)器發(fā)出檢索請求此請求會被處理成多個子查詢分發(fā)到邏輯索引的各個子索引節(jié)點(diǎn)上。多個子索引源檢索服務(wù)器的檢索結(jié)果返回給最初的服務(wù)器匯總后，將檢索結(jié)果返回給客戶端。

源檢索模塊的分布式檢索流程如下：

1)客戶端向分布式源檢索服務(wù)器集群發(fā)送檢索請求，含有該邏輯索引的任意源檢索服務(wù)器都有可能接收到該請求，源檢索服務(wù)器的內(nèi)部處理邏輯會把查詢請求轉(zhuǎn)發(fā)到一個其他的副本索引節(jié)點(diǎn)。

2)這個副本索引節(jié)點(diǎn)啟動源檢索分布式查詢，根據(jù)子索引的個數(shù)，將查詢轉(zhuǎn)化為多個子查詢并把每個子查詢定位到對應(yīng)子索引的任意一個副本索引節(jié)點(diǎn)上。

3)接受檢索請求的副本索引節(jié)點(diǎn)返回各自的查詢結(jié)果。

4)最初的源檢索服務(wù)器節(jié)點(diǎn)合并這些子查詢，并把最終結(jié)果返回給客戶端。

在分布式源檢索模塊檢索時，多個查詢在分布式索引中并行地進(jìn)行檢索，減少了串行檢索的時間。

3實(shí)驗(yàn)設(shè)計與實(shí)驗(yàn)結(jié)果分析

3.1實(shí)驗(yàn)設(shè)計

PAN@CLEF2012國際評測訓(xùn)練數(shù)據(jù)集涵蓋了較為常見的多類抄襲案件：no obfuscation、artificial low、artificial high、simulated paraphrase和translation 5大類。本實(shí)驗(yàn)采用Pan2012的訓(xùn)練數(shù)據(jù)集，參考文檔是4 210篇，可疑文檔是1 804篇。實(shí)驗(yàn)的第一部分，針對每一種可疑文檔抄襲類型，隨機(jī)地選擇20篇可疑文檔，總共20×5篇可疑文檔，與4 210篇參考文檔一起，作為本章的實(shí)驗(yàn)數(shù)據(jù)的一部分，驗(yàn)證基于索引分片的源檢索模塊的性能。

實(shí)驗(yàn)分為備選文檔集索引的創(chuàng)建、可疑文檔文本預(yù)處理、檢索相關(guān)文檔和性能評測4個步驟：

1)備選文檔集索引的創(chuàng)建

對于訓(xùn)練數(shù)據(jù)集中的參考文檔集，按自然片段建立索引。當(dāng)文檔集很大時，可以利用MapReduce計算框架批量構(gòu)建索引方法創(chuàng)建索引。

2)可疑文檔文本預(yù)處理

對可疑文檔進(jìn)行預(yù)處理,包括停用詞的移除、大小寫字母轉(zhuǎn)化和詞干提取。

3)檢索相關(guān)文檔

在源檢索模塊的檢索階段，文中在不同結(jié)構(gòu)的源檢索模塊上進(jìn)行測試。首先將索引部署在基于單機(jī)索引的源檢索模塊上，調(diào)整檢索的各項(xiàng)閾值，如提交查詢個數(shù)的閾值，使源檢索模塊的性能達(dá)到最優(yōu)。其次，擴(kuò)展源檢索模塊的數(shù)據(jù)節(jié)點(diǎn)為4、5、6，將索引部署到基于索引分片的源檢索模塊上，調(diào)節(jié)數(shù)據(jù)參數(shù)使分布式源檢索模塊的性能達(dá)到基于單機(jī)的源檢索模塊的水平。返回各種情況下性能指標(biāo)、時間開銷等。

4)性能評測

根據(jù)1.2節(jié)中提出的評測方法，對獲得的相關(guān)文檔進(jìn)行評測。

本實(shí)驗(yàn)基于Pan@CLEF2012的評測標(biāo)準(zhǔn)和指標(biāo)，測試在Hadoop分布式平臺上，基于索引分片的源檢索模塊在訓(xùn)練數(shù)據(jù)集上的性能表現(xiàn)。實(shí)驗(yàn)還測試了基于索引分片的源檢索模塊結(jié)構(gòu)與基于單機(jī)的源檢索模塊結(jié)構(gòu)，在處理大規(guī)模備選文檔數(shù)據(jù)集上的時間效率對比。

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

實(shí)驗(yàn)的第1部分，不同的源檢索模塊體系結(jié)構(gòu)得到實(shí)驗(yàn)結(jié)果如表1所示，參加對比的源檢索模塊結(jié)構(gòu)分別是基于單機(jī)索引的源檢索模塊結(jié)構(gòu)和基于索引分片的源檢索模塊結(jié)構(gòu)，分布式環(huán)境下的數(shù)據(jù)節(jié)點(diǎn)分別擴(kuò)展為4、5、6臺源檢測服務(wù)器。表1中展示了6種數(shù)據(jù)集下的源檢索結(jié)果，分別是數(shù)據(jù)集1(no obfuscation)、數(shù)據(jù)集2(artificial low)、數(shù)據(jù)集3(artificial high)、數(shù)據(jù)集4(simulated paraphrase)和數(shù)據(jù)集5(translation)，以及將所有數(shù)據(jù)合并后的總的數(shù)據(jù)集數(shù)據(jù)6(All Data)。表1中的F1值是指最終的系統(tǒng)對比指標(biāo)，R指的是召回率，P指的是精確率。

表1　 不同源檢索模塊結(jié)構(gòu)檢索的實(shí)驗(yàn)結(jié)果

由于表1所示的檢索結(jié)果中R和P的值太小，將其放大100倍。在實(shí)驗(yàn)中，基于單機(jī)的源檢索模塊結(jié)構(gòu)的各個閾值經(jīng)過調(diào)節(jié)后，F(xiàn)1值在各個數(shù)據(jù)集可以達(dá)到最優(yōu)。由表1的實(shí)驗(yàn)結(jié)果可知，基于索引分片的源檢索模塊的各項(xiàng)閾值經(jīng)過調(diào)節(jié)后，在不同規(guī)模集群的F1值性能也可以達(dá)到基于單機(jī)索引的源檢索模塊的水平。

由表1中的檢索結(jié)果可以看出，對于相同的數(shù)據(jù)集，基于索引分片的源檢索模塊結(jié)構(gòu)的F1值可以達(dá)到基于單機(jī)索引的源檢索模塊結(jié)構(gòu)的最優(yōu)性能；同一種源檢索結(jié)構(gòu)在不同的數(shù)據(jù)集，性能效果也是不一樣的。因此，在Pan@CLEF2012的訓(xùn)練數(shù)據(jù)集上，基于索引分片的源檢索模塊可以達(dá)到基于單機(jī)索引的源檢索的最優(yōu)性能。該實(shí)驗(yàn)主要考察了4種不同的源檢索結(jié)構(gòu)的模塊的性能指標(biāo)，由實(shí)驗(yàn)結(jié)果可知，基于索引分片的源檢索模塊可以達(dá)到基于單機(jī)索引的源檢索結(jié)構(gòu)模塊的最優(yōu)性能。實(shí)驗(yàn)證明在基于Hadoop分布式平臺上，基于索引分片的源檢索體系結(jié)構(gòu)在性能上可以應(yīng)用于抄襲檢測系統(tǒng)上。

在實(shí)驗(yàn)的第2部分中，實(shí)驗(yàn)數(shù)據(jù)使用ClueWeb09[12]的英文文檔作為備選文檔集。實(shí)驗(yàn)中隨機(jī)選擇若干篇英文文檔組成5個不同規(guī)模的數(shù)據(jù)集，和實(shí)驗(yàn)第一部分的All Data一起組成本實(shí)驗(yàn)的6個數(shù)據(jù)集，測試在大規(guī)模備選文檔集上4個源檢索模塊的時間效率。實(shí)驗(yàn)數(shù)據(jù)集信息如表2所示。

表2　 較大規(guī)模的備選文檔集數(shù)據(jù)

表2中數(shù)據(jù)1為第一部分實(shí)驗(yàn)的All Data數(shù)據(jù)集。本實(shí)驗(yàn)用第一部分在數(shù)據(jù)6上獲得的源檢索模塊參數(shù)模型來測試時間效率。首先需要將這些數(shù)據(jù)在基于單機(jī)的源檢索模塊和基于索引分片的源檢索模塊(分別擴(kuò)展為4～6臺源檢索服務(wù)器)上創(chuàng)建備選文檔集數(shù)據(jù)的索引；其次在訓(xùn)練數(shù)據(jù)集可疑文檔中隨機(jī)選取100篇作為查詢。測試結(jié)果如表3。

表3　 源檢索模塊時間測試結(jié)果

實(shí)驗(yàn)證明了在Hadoop分布式平臺上，基于索引分片的源檢索模塊可以應(yīng)對抄襲檢測系統(tǒng)中大規(guī)模數(shù)據(jù)集的問題。

4結(jié)束語

針對當(dāng)前的抄襲檢測系統(tǒng)無法處理大規(guī)模備選文檔數(shù)據(jù)集的問題，本文提出了基于索引分片的源檢索結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明，基于索引分片的源檢索模塊在精確性、召回率、F1值等性能指標(biāo)上可以達(dá)到基于單機(jī)的源檢索模塊的性能水平，在性能上滿足抄襲檢索系統(tǒng)的要求。隨著備選文檔數(shù)據(jù)集規(guī)模的增大，基于索引分片的源檢索模塊的時間開銷增長速度相對比較平穩(wěn)，這說明了基于索引分片的源檢索模塊通過擴(kuò)展集群規(guī)模在處理大規(guī)模數(shù)據(jù)集時完全有效。

參考文獻(xiàn):

[1]Hadoop.Apache Hadoop[EB/OL]. [2011-12-27]. http://hadoop.apache.org.

[2]BORTHAKUR D. The hadoop distributed file system: Architecture and design[Z]. Hadoop Project Website, 2007: 1-10.

[3]DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters[J]. In Proceedings of Operating Systems Design and Implementation (OSDI), San Francisco,USA,2004, 51(1):107-113.

[4]POTTHAST M, GOLLUB T, HAGEN M, et al. Overview of the 4th International Competition on Plagiarism Detection[C]//CLEF 2012 Conference and Labs of the Evaluation Forum. Rome, Italy, 2012: 1-9.

[5]XU Jinxi, CALLAN J. Effective retrieval with distributed collections[C]//Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, USA, 1998: 112-120.

[6]ICHIKAWA Y, UEHARA M. Distributed search engine for an IaaS based cloud[C]// 2011 International Conference on Broadband and Wireless Computing, Communication and Applications (BWCCA). Washington D C, USA, 2011: 34-39.

[7]封俊. 基于Hadoop的分布式搜索引擎研究與實(shí)現(xiàn)[D]. 太原: 太原理工大學(xué), 2010: 35-53.

[8]蘇宇. 基于Hadoop的分布式全文檢索及相關(guān)技術(shù)研究[D]. 合肥: 中國科學(xué)技術(shù)大學(xué), 2014: 22-38.

[9]PARO A. ElasticSearch cookbook[M]. Bermingham: Packt Publishing Ltd, 2013: 5-25.

[10]吳煒, 蘇永紅, 李瑞軒, 等. 基于DHT的分布式索引技術(shù)研究與實(shí)現(xiàn)[J]. 計算機(jī)科學(xué), 2010, 37(2): 65-70.

[11]吳雪琴, 舒曉苓. 基于云計算的大數(shù)據(jù)信息檢索技術(shù)研究[J]. 電腦知識與技術(shù), 2014, 10(10): 2388-2390.

[12] Lemur. ClueWeb[EB/OL]. [2009-2-24]. http://lemurproject.org.

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1191.U.20151206.1018.016.html

Research on the source retrieval method of

plagiarism detection based on Hadoop

WANG Suhong, NING Hui, WANG Mingxing, XU Li

Department of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China

Abstract：With the development of science and technology and the popularity of Internet, the network has brought us convenience, as well as the opportunity for plagiarism. Plagiarism detection has become an important research subject. By analyzing the advantages and disadvantages of source retrieval of the traditional plagiarism detection system, in combination with characteristics of the distributed system, this paper proposes a source retrieval system structure based on the index slice, so as to retrieve candidate documents from massive data sets. Experimental results show that, the source retrieval structure based on the index slice can deal with massive data set. It can effectively improve time performance of source retrieval, and also guarantee the reliability of the plagiarism detection system.

Keywords：plagiarism; plagiarism detection; massive data sets; source retrieval; Hadoop

通信作者：寧慧，E-mail：ninghui@hrbeu.edu.cn.

作者簡介：王素紅(1986-)，女，碩士研究生；

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61201084).

收稿日期：2015-03-27.網(wǎng)絡(luò)出版日期：2015-12-06.

中圖分類號：TP311

文獻(xiàn)標(biāo)志碼：A

文章編號：1009-671X(2015)06-067-05

doi:10.11991/yykj.201503030