許艷靜，朱建明，丁慶洋，莊雪揚(yáng)

(中央財(cái)經(jīng)大學(xué) 信息學(xué)院，北京 100081)

一、引言

眾包競(jìng)賽(Crowdsourcing Competition)由于能夠充分發(fā)掘社會(huì)大眾的智慧而被企業(yè)廣泛應(yīng)用。眾包競(jìng)賽指企業(yè)通過(guò)第三方網(wǎng)絡(luò)平臺(tái)舉辦一些創(chuàng)新競(jìng)賽，向來(lái)自世界各地參與競(jìng)賽的社會(huì)大眾征集任務(wù)解答方案，并給予一定現(xiàn)金獎(jiǎng)勵(lì)的新模式[1]。在眾包競(jìng)賽中，欺詐問(wèn)題時(shí)有發(fā)生，這種行為降低了創(chuàng)新效率，引起了眾多學(xué)者的廣泛關(guān)注。龐建剛通過(guò)博弈分析指出，由于交易雙方的信息不對(duì)稱，欺詐行為容易產(chǎn)生，且發(fā)起者是風(fēng)險(xiǎn)重要來(lái)源[2]。馮劍紅等發(fā)現(xiàn)，問(wèn)題解答者的欺詐行為已經(jīng)嚴(yán)重影響任務(wù)的完成質(zhì)量，如何識(shí)別出欺騙型解答者成為目前眾包研究中一個(gè)急需解決的問(wèn)題[3]。平臺(tái)運(yùn)營(yíng)商和發(fā)起者是眾包競(jìng)賽中篩除欺詐者的行為方。從網(wǎng)絡(luò)平臺(tái)角度看，常見(jiàn)的方式是利用黃金標(biāo)準(zhǔn)數(shù)據(jù)和測(cè)試題目。黃金標(biāo)準(zhǔn)數(shù)據(jù)方法是把解答者的數(shù)據(jù)和標(biāo)準(zhǔn)答案對(duì)比，篩選出欺騙類(lèi)的解答者，并舍棄他們的答案。這種方法如果沒(méi)有清晰標(biāo)準(zhǔn)的答案便失去了可行性。也可以通過(guò)添加一些測(cè)試題目篩選出一些欺詐者[4]，但是很多解答者并不想?yún)⒓訙y(cè)試，導(dǎo)致題目不能長(zhǎng)時(shí)間被完成。從任務(wù)的發(fā)起者視角看，篩除欺詐者可以依靠在題目中隨機(jī)添加一部分常識(shí)問(wèn)題，如若這些問(wèn)題回答錯(cuò)誤，便可剔除欺詐者，這樣既提高結(jié)果質(zhì)量又可以避免浪費(fèi)金錢(qián)。但是，這種方法有個(gè)很大的挑戰(zhàn)，就是如何做到隱蔽地插入常識(shí)。

離群數(shù)據(jù)是指數(shù)據(jù)集中那些遠(yuǎn)離常規(guī)對(duì)象的數(shù)據(jù)，表現(xiàn)為與多數(shù)常規(guī)對(duì)象有明顯差異，以至于被懷疑可能是由另外一種完全不同的機(jī)制產(chǎn)生[5]。眾包中欺詐用戶的個(gè)人信息和歷史記錄信息及參與眾包工作的答案和大眾信息相比是有很多的區(qū)別的，均可以利用一些新的方法從大眾中作為離群點(diǎn)分離出來(lái)。因此，離群點(diǎn)檢測(cè)是優(yōu)化欺詐者篩除機(jī)制的關(guān)鍵所在。

離群點(diǎn)檢測(cè)是識(shí)別數(shù)據(jù)中噪音，挖掘潛在的、有意義的知識(shí)的一種數(shù)據(jù)挖掘技術(shù)[6]，廣泛應(yīng)用于入侵檢測(cè)領(lǐng)域、信用卡詐騙檢測(cè)、電子商務(wù)犯罪活動(dòng)檢測(cè)、視頻監(jiān)控、天氣預(yù)測(cè)以及藥物研究等研究中。由于聚類(lèi)算法能夠根據(jù)樣本之間的相似度把觀測(cè)樣本分到不同分組，并使同一分組中的樣本盡可能相似而不同分組中的樣本盡可能不相似，因此聚類(lèi)算法被用于識(shí)別數(shù)據(jù)中的離群點(diǎn)。

離群點(diǎn)的檢測(cè)方法有很多，常見(jiàn)的有基于距離的和基于密度、基于分布的、基于深度的、基于方法的幾大類(lèi)。為了消除離群點(diǎn)對(duì)聚類(lèi)的影響，提出了能夠識(shí)別樣本聚類(lèi)和離群點(diǎn)的ORC(Outlier Removal Clustering)算法[7]，該算法先是用K-means-聚類(lèi)算法對(duì)樣本聚類(lèi)；然后根據(jù)樣本點(diǎn)與聚類(lèi)中心之間的距離來(lái)判斷哪些點(diǎn)是離群點(diǎn)并移除。在給定樣本間平均距離的情況下，ODC(Outlier Detection Clustering)算法將大于樣本間平均距離p倍的點(diǎn)視為離群點(diǎn)[8]。K-means-算法能夠同時(shí)識(shí)別聚類(lèi)和離群點(diǎn)，該算法需要給定聚類(lèi)個(gè)數(shù)k和離群點(diǎn)個(gè)數(shù)l。在給定參數(shù)的情況下，K-means-算法每次迭代會(huì)計(jì)算樣本點(diǎn)與最近的聚類(lèi)中心的相似度，并按大小進(jìn)行排序，將距離最大的前l(fā)個(gè)點(diǎn)視為離群點(diǎn)，用剩下的樣本點(diǎn)來(lái)重新計(jì)算聚類(lèi)中心，直到滿足終止條件[9]。

二、眾包競(jìng)賽的離群點(diǎn)欺詐用戶檢測(cè)算法的設(shè)計(jì)

(一)眾包的組織框架

我們將眾包工作概念化[10-12]。監(jiān)測(cè)和評(píng)估人群行為; 驗(yàn)證用戶的身份，然后才能在網(wǎng)站上發(fā)布信息或參加在線競(jìng)賽; 刪除虛假信息;篩選用戶有可能標(biāo)記可疑內(nèi)容或者虛假答案。

圖1 眾包工作概念框架

我們的眾包工作概念模型包括以下要素(圖1)：

(1)眾包任務(wù)：眾包任務(wù)也被稱為問(wèn)題或挑戰(zhàn)。

(2)人群：執(zhí)行任務(wù)的個(gè)人(人群工作人員)。在欺騙性眾包的背景下，與人群相關(guān)的問(wèn)題涉及惡意的人類(lèi)行為，以及可能引發(fā)此類(lèi)行為的機(jī)制的識(shí)別。

(3)眾包平臺(tái)：連接人群和問(wèn)題所有者。在捕捉眾包欺騙的例子時(shí)，我們將重點(diǎn)放在與平臺(tái)或其管理相關(guān)的風(fēng)險(xiǎn)和漏洞上。

(4)任務(wù)發(fā)布者：定義任務(wù)，在平臺(tái)上發(fā)布任務(wù)，并為任務(wù)完成提供數(shù)據(jù)和工具。對(duì)于我們的分析，我們集中于與問(wèn)題所有者的上下文相關(guān)的有關(guān)風(fēng)險(xiǎn)的信息，這些風(fēng)險(xiǎn)是由任務(wù)發(fā)布者發(fā)起的，或者是由他們的疏忽引起的。

(5)治理/管理：我們收集了關(guān)于事件中使用的治理機(jī)制和相關(guān)漏洞的信息，例如缺乏質(zhì)量控制，使用離群點(diǎn)檢測(cè)方法。

(6)群體貢獻(xiàn)：人群成員完成任務(wù)后的產(chǎn)出。

(二)離群點(diǎn)的定義

眾包框架中治理模塊的內(nèi)容涵蓋了眾包的用戶的管理，眾包的欺詐用戶檢測(cè)管理我們可以利用檢測(cè)離群點(diǎn)的方式操作。離群點(diǎn)是指數(shù)據(jù)中偏離大多數(shù)樣本的樣本集合，聚類(lèi)分析中的離群點(diǎn)則定義為遠(yuǎn)離聚類(lèi)中心的樣本集合[13]。應(yīng)用在眾包中我們可以給定n個(gè)觀測(cè)樣本的集合Xi=(X1，X2，…，Xn)T，假設(shè)Ck是聚類(lèi)中心集合，用d(Xi，Ck)來(lái)表示樣本Xi與聚類(lèi)中心Ck之間的相似度或距離。給定參數(shù)θ，用f(θ)來(lái)檢測(cè)樣本是否為離群點(diǎn)，若d(Xi，Ck)>f(θ)，則樣本Xi是遠(yuǎn)離聚類(lèi)Ck的離群點(diǎn)，反之若d(Xi，Ck)≤f(θ)，則樣本Xi不是聚類(lèi)Ck的離群點(diǎn)。

(三)離群點(diǎn)檢測(cè)算法

(四)基于樣本連通圖的離群點(diǎn)檢測(cè)算法

由于基于聚類(lèi)算法的離群點(diǎn)檢測(cè)算法K-means-算法[15]和DBSCAN算法[16]依賴于事先給定的參數(shù)，因此要提升算法的準(zhǔn)確性，必須準(zhǔn)確設(shè)置參數(shù)，在實(shí)踐中要準(zhǔn)確設(shè)置參數(shù)往往是困難的。為此，本文提出了基于樣本連通圖的離群點(diǎn)檢測(cè)算法(Outlier Detecting Algorithm Based on Sample Connection Graph，簡(jiǎn)稱為ODA-SCG)。

1.相關(guān)定義。給定參數(shù)θ，利用聚類(lèi)算法來(lái)識(shí)別數(shù)據(jù)中的離群點(diǎn)并對(duì)數(shù)據(jù)進(jìn)行聚類(lèi)，將會(huì)得到不同的聚類(lèi)結(jié)果和離群點(diǎn)集合：{Xs，Xo}，其中Xs={C1，C2，…，Ck}。對(duì)于任意兩個(gè)樣本點(diǎn)Xi和Xj，若它們都屬于第k個(gè)聚類(lèi)或都是離群點(diǎn)，即Xi，Xj∈Ck或Xi，Xj∈Xo那么認(rèn)為這兩個(gè)樣本之間存在連接關(guān)系Eij=1。若Xi和Xj不屬于同一聚類(lèi)或者不都是離群點(diǎn)，那么它們之間沒(méi)有連接Eij≠1。隨著參數(shù)θ取值的不斷變化，聚類(lèi)結(jié)果會(huì)發(fā)生變化，樣本Xi和Xj之間的連接情況也會(huì)發(fā)生變化。因此，在給定不同參數(shù)θ的情況下，Xi和Xj之間的連接情況是一個(gè)隨機(jī)變量。

定義1連接強(qiáng)度。用X表示包含n個(gè)觀測(cè)樣本的集合，假設(shè)Xi和Xj是來(lái)自數(shù)據(jù)集X的兩個(gè)樣本點(diǎn)，用Eij表示Xi與Xj之間是否連接，Eij=1表示有連接，Eij=0表示無(wú)連接。用Xi與Xj之間連接的概率p(Eij=1)∈[0，1]來(lái)表示連接強(qiáng)度，簡(jiǎn)記為pij。

接下來(lái)討論如何估計(jì)兩樣本之間的連接強(qiáng)度pij。由于K-means-算法和DBSCAN算法識(shí)別離群點(diǎn)時(shí)，依賴于設(shè)定的參數(shù)值，那么給定不同的參數(shù)值，得到的聚類(lèi)結(jié)果和離群點(diǎn)識(shí)別結(jié)果將會(huì)有所不同。為了解決這一問(wèn)題，我們給定參數(shù)范圍，然后利用K-means-算法和DBSCAN算法重復(fù)識(shí)別離群點(diǎn)，然后通過(guò)兩個(gè)點(diǎn)被劃分到同一個(gè)類(lèi)別的頻率，來(lái)估計(jì)Xi與Xj之間的連接強(qiáng)度。

定義 2連接強(qiáng)度計(jì)算。對(duì)于任意兩個(gè)樣本點(diǎn)Xi與Xj，若它們同屬于一個(gè)聚類(lèi)或都是離群點(diǎn)，則它們之間有連接Eij=1。給定參數(shù)范圍，重復(fù)調(diào)用離群點(diǎn)識(shí)別算法來(lái)識(shí)別離群點(diǎn)N次，計(jì)算任意兩個(gè)樣本Xi與Xj被分配到同一個(gè)聚類(lèi)或都是離群點(diǎn)的總次數(shù)為#(Eij=1)。那么定義連接強(qiáng)度pij為：

pij=#(Eij=1)/N

可見(jiàn)，當(dāng)且僅當(dāng)任意兩個(gè)樣本點(diǎn)Xi與Xj同屬一個(gè)聚類(lèi)或者都是離群點(diǎn)時(shí)，它們之間有強(qiáng)的連接強(qiáng)度，否則它們的連接強(qiáng)度較弱。

定義3樣本連通圖。定義樣本連接圖G(X，E，p)，其中X是樣本節(jié)點(diǎn)集合，E是樣本節(jié)點(diǎn)之間的連邊集合，p是樣本節(jié)點(diǎn)之間的連接強(qiáng)度集合。為了使樣本之間的連通圖變得稀疏，定義樣本之間的連接強(qiáng)度下界δ∈[0，1]，用來(lái)限制兩個(gè)樣本之間的連接情況。當(dāng)且僅當(dāng)pij>δ時(shí)，樣本節(jié)點(diǎn)i與樣本節(jié)點(diǎn)j之間有連接，否則無(wú)連接。

2.算法設(shè)計(jì)。根據(jù)上述定義，下面給出基于樣本連通圖的ODA-SCG，用來(lái)識(shí)別數(shù)據(jù)中的離群點(diǎn)。基于樣本連通圖的離群點(diǎn)檢測(cè)算法(ODA-SCG)的實(shí)現(xiàn)，主要完成以下方面的工作：

(1)觀測(cè)樣本集合X，連接強(qiáng)度下界δ，離群點(diǎn)識(shí)別算法參數(shù)范圍；

(2)給定聚類(lèi)個(gè)數(shù)和離群點(diǎn)個(gè)數(shù)，通過(guò)K-means-聚類(lèi)算法初始化聚類(lèi)中心C；

(3)循環(huán)迭代直至滿足收斂條件；

(4)計(jì)算各觀測(cè)樣本與其最近的聚類(lèi)中心的距離d(Xi；Ck)，并由大到小排序；

(5)將前l(fā)個(gè)距離聚類(lèi)中心最遠(yuǎn)的觀測(cè)樣本從聚類(lèi)中剔除，得到余下觀測(cè)樣本集合Z；

(6)利用余下觀測(cè)樣本集合Z重新計(jì)算聚類(lèi)中心；

(7)輸出聚類(lèi)分析結(jié)果和離群點(diǎn)集合；

(8)將觀測(cè)樣本集合X中的所有樣本點(diǎn)標(biāo)記為未處理狀態(tài)；

(9)循環(huán)迭代直至每個(gè)樣本被歸入某個(gè)聚類(lèi)或標(biāo)記為離群點(diǎn)；

(10)統(tǒng)計(jì)樣本點(diǎn)Xi的eps鄰域內(nèi)包含的樣本點(diǎn)數(shù)Neps(Xi)；

(11)如果Neps(Xi)包含的樣本數(shù)小于Minpts，則將Xi標(biāo)記為邊界點(diǎn)或離群點(diǎn)；

(12)否則標(biāo)記Xi為核心對(duì)象，并建立新聚類(lèi)C，將Xi的eps鄰域內(nèi)的樣本點(diǎn)劃分至聚類(lèi)C中；

(13)循環(huán)迭代直至Neps(Xi)中所有尚未被處理的對(duì)象Xj被歸入某個(gè)聚類(lèi)或標(biāo)記為離群點(diǎn)；

(14)統(tǒng)計(jì)樣本點(diǎn)Xj的eps鄰域內(nèi)包含的樣本點(diǎn)數(shù)Neps(Xj)；

(15)如果Neps(Xj)包含至少M(fèi)inpts個(gè)樣本點(diǎn)，則將Neps(Xj)中未歸入任何簇的對(duì)象加入C；

(16)輸出聚類(lèi)劃分和離群點(diǎn)集合；

(17)計(jì)算連接次數(shù)#(Eij=1)和連接強(qiáng)度pij；

(18)給定連接強(qiáng)度下界δ，構(gòu)造樣本之間的聯(lián)通圖；

(19)判別樣本在連通圖中的位置，標(biāo)記離群點(diǎn)；

(20)輸出離群點(diǎn)集合，算法實(shí)現(xiàn)流程見(jiàn)圖2。

圖2 基于樣本節(jié)點(diǎn)連通圖的離群點(diǎn)檢測(cè)算法流程

算法與K-means-離群點(diǎn)檢測(cè)算法和DBSCAN離群點(diǎn)檢測(cè)算法相比，它給定的參數(shù)是一個(gè)范圍，且通過(guò)重復(fù)調(diào)用離群點(diǎn)檢測(cè)算法并計(jì)算樣本節(jié)點(diǎn)之間的連接強(qiáng)度。這樣就避免了參數(shù)設(shè)置不準(zhǔn)確時(shí)，離群點(diǎn)檢測(cè)結(jié)果與實(shí)際結(jié)果偏差較大的問(wèn)題，解決了基于聚類(lèi)的離群點(diǎn)識(shí)別算法過(guò)度依賴于給定參數(shù)的問(wèn)題，離群點(diǎn)的識(shí)別結(jié)果較為穩(wěn)定。

以K-means-離群點(diǎn)檢測(cè)算法為例，它需要確定聚類(lèi)個(gè)數(shù)K。為了確定聚類(lèi)個(gè)數(shù)，本文通過(guò)最優(yōu)化聚類(lèi)內(nèi)部有效性指標(biāo)KL來(lái)確定最佳的聚類(lèi)個(gè)數(shù)[17]。

三、實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)采用R3.4.1軟件作為實(shí)驗(yàn)平臺(tái)，操作系統(tǒng)是Windows10專業(yè)版，Intel(R) Core(Lawrence et al.) i7-7560U CPU @2.40GHz(雙核)64位，16GB內(nèi)存，512GB固態(tài)硬盤(pán)。

(一)評(píng)價(jià)方法

為了評(píng)價(jià)ODA-SCG算法的有效性，本文采用離群點(diǎn)個(gè)數(shù)(Number of outliers，簡(jiǎn)寫(xiě)為No)、靈敏度(Sensitivity，簡(jiǎn)寫(xiě)為Sen)、特異度(Specificity，簡(jiǎn)寫(xiě)為Spc)、準(zhǔn)確率(Accuracy，簡(jiǎn)寫(xiě)為Accu)以及F-measure(簡(jiǎn)寫(xiě)為F)作為評(píng)價(jià)指標(biāo)。其中靈敏度、特異度、準(zhǔn)確率以及F的取值范圍在0和1之間，數(shù)值越接近1，說(shuō)明算法準(zhǔn)確度越高，反之算法準(zhǔn)確度越低。

將非離群點(diǎn)表示為正類(lèi)，離群點(diǎn)表示為負(fù)類(lèi)，用TP表示判別為正類(lèi)且實(shí)際為正類(lèi)的樣本點(diǎn)個(gè)數(shù)，F(xiàn)N表示判別為負(fù)類(lèi)但實(shí)際為正類(lèi)的樣本點(diǎn)個(gè)數(shù)，TN表示判別為負(fù)類(lèi)且實(shí)際為負(fù)類(lèi)的樣本點(diǎn)個(gè)數(shù)，F(xiàn)P表示判別為正類(lèi)但實(shí)際為負(fù)類(lèi)的樣本點(diǎn)個(gè)數(shù)。因此，Sen、Spe、Accu和F的定義如下：

Sensitivity =TP/(TP+FN )

Specificity=TN/(TN+FP )

Accuracy=(TP+TN )/(TP+TN+FP+FN )

F-measure=2(Precision·Recall)/(Precision+Recall)

其中，Precision為精度，其計(jì)算公式為T(mén)P/(TP+ FP )；Recall為召回率，其計(jì)算公式為T(mén)P/(TP+ FN )。

(二)實(shí)驗(yàn)數(shù)據(jù)

為了測(cè)試算法的準(zhǔn)確性，本文借助R軟件生成仿真數(shù)據(jù)集。仿真數(shù)據(jù)的產(chǎn)生有三種情形：聚類(lèi)之間完全分離，聚類(lèi)大小不同以及聚類(lèi)密度不相等。同時(shí)，設(shè)置兩種不同的離群點(diǎn)比例情形：離群點(diǎn)較少(5%的樣本點(diǎn)為離群點(diǎn))和離群點(diǎn)較多(20%的樣本點(diǎn)為離群點(diǎn))。因此，共有六種數(shù)據(jù)集將用來(lái)驗(yàn)證離群點(diǎn)檢測(cè)算法。具體設(shè)置見(jiàn)表1。

表1 仿真數(shù)據(jù)場(chǎng)景設(shè)置

1.ODA-SCG算法和已有的離群點(diǎn)經(jīng)典算法K-means-算法、DBSCAN算法的精確性和穩(wěn)定性比較

為了評(píng)價(jià)基于樣本節(jié)點(diǎn)連通圖的離群點(diǎn)檢測(cè)算法(ODA-SCG)在離群點(diǎn)個(gè)數(shù)確定、離群點(diǎn)辨識(shí)準(zhǔn)確度以及識(shí)別穩(wěn)定性方面的性能，應(yīng)用該算法分析每種實(shí)驗(yàn)場(chǎng)景產(chǎn)生的仿真數(shù)據(jù)(表1)，并與K-means-算法和DBSCAN算法對(duì)比。K-means-算法需要確定的參數(shù)包括聚類(lèi)個(gè)數(shù)k以及離群點(diǎn)個(gè)數(shù)l，本文采用KL指標(biāo)來(lái)輔助確定K-means-算法的最優(yōu)聚類(lèi)個(gè)數(shù)，在取最優(yōu)聚類(lèi)個(gè)數(shù)的情況下，設(shè)置K-means-算法中離群點(diǎn)個(gè)數(shù)l取值上限為樣本數(shù)的20%，即40個(gè)，在該區(qū)間內(nèi)分別取值為4、9、14、19、24。DBSCAN算法可以自動(dòng)地識(shí)別聚類(lèi)個(gè)數(shù)并將低密度區(qū)域的樣本點(diǎn)視為離群點(diǎn)，但需要確定鄰域半徑eps和給定鄰域內(nèi)的最小包含點(diǎn)數(shù)MinPts這兩個(gè)參數(shù)，設(shè)置掃描半徑eps的取值區(qū)間為[0.1，10]，在該區(qū)間內(nèi)分別取值為2、3、4、5、6，MinPts的取值為R中DBSCAN算法中的默認(rèn)值MinPts=5。在基于重復(fù)聚類(lèi)和節(jié)點(diǎn)連接圖的離群點(diǎn)挖掘算法中，最大離群點(diǎn)個(gè)數(shù)的取值等于K-means-算法中離群點(diǎn)個(gè)數(shù)l的取值上限，設(shè)置連接強(qiáng)度δ取值分別為0.2、0.3、0.4、0.5和0.6，這樣可以保證每個(gè)算法的參數(shù)變動(dòng)幅度相同，從而使得結(jié)果具有可對(duì)比性。對(duì)比結(jié)果如圖3～5和表2所示。其中，圖3～5每一組第一個(gè)柱形圖表示K-means-算法下的結(jié)果，第二個(gè)柱形圖表示DBSCAN算法下的結(jié)果，第三個(gè)柱形圖表示ODA-SCG+K-means-算法下的結(jié)果，第四個(gè)柱形圖表示ODA-SCG+DBSCAN算法下的結(jié)果。

圖3 聚類(lèi)之間完全分離

圖4 聚類(lèi)大小不同

圖5 聚類(lèi)密度不相等

在算法準(zhǔn)確度方面，ODA-SCG算法的靈敏度、特異度、準(zhǔn)確度和F-measure值均較高，這說(shuō)明ODA-SCG算法具有較高的準(zhǔn)確度。只有當(dāng)K-means-算法和DBSCAN算法的參數(shù)設(shè)置正確的時(shí)候，這兩個(gè)算法才具有較高的準(zhǔn)確度，而若參數(shù)偏離正確的取值，其離群點(diǎn)檢測(cè)結(jié)果也將差于ODA-SCG算法。

用三種算法對(duì)表1中的三種仿真數(shù)據(jù)進(jìn)行分析?？梢?jiàn)，ODA-SCG算法相比其他兩種算法而言離群點(diǎn)個(gè)數(shù)的變化幅度變化較小，更為穩(wěn)定。

表2 幾種算法的精確性和穩(wěn)定性比較

表3 離群點(diǎn)個(gè)數(shù)的變化幅度

綜上所述，若不能夠準(zhǔn)確給定K-means-算法和DBSCAN算法的參數(shù)，ODA-SCG算法將具有更好的優(yōu)勢(shì)，它的離群點(diǎn)個(gè)數(shù)波動(dòng)范圍相對(duì)較小，且具有較高的準(zhǔn)確度。

2.黃金標(biāo)準(zhǔn)數(shù)據(jù)方法和ODA-SCG算法的比較

我們的實(shí)驗(yàn)數(shù)據(jù)取自于“TREC-7Ad Hoc and TREC-8 Filtering Topics”中的四個(gè)主題。這四個(gè)主題分別是：

編號(hào):351 ?？颂m石油勘探；

編號(hào):357 領(lǐng)海爭(zhēng)端；

編號(hào):358 血液酒精中毒；

編號(hào):360 毒品合法化好處；

我們找到TREC會(huì)議的相關(guān)性文檔，從提供的中央情報(bào)局對(duì)外廣播情報(bào)處數(shù)據(jù)中選取了 690條作為我們的候選集合，其中含有560條不相關(guān)文檔，130條相關(guān)文檔.我們選取了50名工作者作為測(cè)試者。

為了更直觀地比較在標(biāo)準(zhǔn)數(shù)據(jù)答案下的準(zhǔn)確率和在離群點(diǎn)算法估計(jì)答案下的準(zhǔn)確率程度，我們把在兩種情況下的準(zhǔn)確率用折線圖呈現(xiàn)，如圖6所示，兩種方法的走勢(shì)非常相似，而且新的方法的結(jié)果更精確。這說(shuō)明利用離群點(diǎn)算法估計(jì)的答案來(lái)對(duì)工作者進(jìn)行評(píng)估是可行和有效的，這也使得本文提出的離群點(diǎn)算法策略在實(shí)際中具有良好的可行性。

表4 工作者在標(biāo)準(zhǔn)答案和ODA-SCG離群點(diǎn)算法下的準(zhǔn)確率比較

圖6 兩種策略比較

四、總結(jié)

本文通過(guò)給定參數(shù)范圍、重復(fù)調(diào)用離群點(diǎn)檢測(cè)算法來(lái)計(jì)算樣本之間的連接強(qiáng)度，并給定連接強(qiáng)度下界的情況下構(gòu)造樣本連通圖，再根據(jù)樣本之間的連接關(guān)系確定離群點(diǎn)，提出了基于樣本節(jié)點(diǎn)連通圖的離群點(diǎn)檢測(cè)算法(ODA-SCG)。該算法的創(chuàng)新之處在于，一是放寬了基于聚類(lèi)的離群點(diǎn)識(shí)別算法(如：K-means-算法和DBSCAN算法)的參數(shù)設(shè)置，把給定具體參數(shù)數(shù)值改為給定參數(shù)范圍；二是通過(guò)樣本的連接圖來(lái)判別離群點(diǎn)，這種方式更加直觀。仿真實(shí)驗(yàn)結(jié)果表明，該算法能夠放寬參數(shù)設(shè)置的范圍，減少離群點(diǎn)個(gè)數(shù)波動(dòng)范圍，提升離群點(diǎn)識(shí)別準(zhǔn)確率。當(dāng)連接強(qiáng)度下界δ取值發(fā)生變化時(shí)，離群點(diǎn)的個(gè)數(shù)變化范圍幅度不大，且離群點(diǎn)識(shí)別準(zhǔn)確度較高，優(yōu)于K-means-算法和DBSCAN算法。三是我們提出了一種新的眾包的欺詐檢測(cè)方法就是利用離群點(diǎn)檢測(cè)算法。把經(jīng)典的黃金標(biāo)準(zhǔn)答案和新的離群點(diǎn)檢測(cè)算法做比較，發(fā)現(xiàn)離群點(diǎn)檢測(cè)算法在準(zhǔn)確性上優(yōu)于黃金標(biāo)準(zhǔn)答案。

眾包競(jìng)賽由于能夠充分發(fā)掘社會(huì)大眾的智慧而被企業(yè)廣泛的應(yīng)用，然而來(lái)自解答者和發(fā)起者兩方面的欺詐行為導(dǎo)致眾包競(jìng)賽效率下降。該離群點(diǎn)檢測(cè)算法可以用來(lái)檢測(cè)不合理的眾包解答答案，從而篩除欺詐者，以期為眾包競(jìng)賽雙方營(yíng)造相互信任的交易環(huán)境為進(jìn)一步激勵(lì)用戶提供有價(jià)值的參考。因此優(yōu)化欺詐者篩除機(jī)制將有助于眾包競(jìng)賽健康發(fā)展。因此，在未來(lái)的研究中，將拓展算法的應(yīng)用，把其他離群點(diǎn)挖掘算法融入到本文的算法中，拓展該算法的適應(yīng)性和使用范圍。