時(shí)空眾包環(huán)境下基于統(tǒng)計(jì)預(yù)測(cè)的自適應(yīng)閾值算法

劉　輝，李盛恩

(山東建筑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，濟(jì)南 250101)(*通信作者電子郵箱megatron101@163.com)

0　引言

“眾包”這一概念是由Jeff Howe提出的，旨在幫助機(jī)構(gòu)把一些工作交給互聯(lián)網(wǎng)用戶。早期的眾包平臺(tái)包括Amazon’s Mechanical Turk、CrowdFlower，需要互聯(lián)網(wǎng)用戶利用個(gè)人計(jì)算機(jī)完成相應(yīng)的任務(wù)。近幾年，移動(dòng)智能設(shè)備的快速普及極大地促進(jìn)了移動(dòng)互聯(lián)網(wǎng)的發(fā)展，眾包平臺(tái)也逐漸得到了業(yè)界和大眾的關(guān)注，例如滴滴打車、餓了么等應(yīng)用。因此，眾包平臺(tái)正式從傳統(tǒng)眾包發(fā)展成為時(shí)空眾包。與傳統(tǒng)眾包的研究類似，時(shí)空眾包同樣專注于任務(wù)分配。移動(dòng)智能設(shè)備攜帶了用戶的個(gè)人信息如位置、手機(jī)號(hào)碼等，任務(wù)請(qǐng)求者將個(gè)人信息及具體任務(wù)提交到平臺(tái)，平臺(tái)在掌握任務(wù)及工人信息的情況下，選出合適工人去完成任務(wù)請(qǐng)求者的任務(wù)，并得到報(bào)酬。因此如何將隨機(jī)出現(xiàn)并帶有時(shí)間、位置信息的任務(wù)分配給最合適的工人并使報(bào)酬最大化成為時(shí)空眾包環(huán)境下要解決的問題。本文以一類新型時(shí)空眾包平臺(tái)應(yīng)用南瓜車為例，在分析貪心算法和隨機(jī)閾值算法的基礎(chǔ)上，設(shè)計(jì)一種基于統(tǒng)計(jì)預(yù)測(cè)的自適應(yīng)閾值算法。

1　相關(guān)研究

1.1　問題定義

本章介紹任務(wù)分配算法中涉及到的實(shí)體對(duì)象及評(píng)價(jià)標(biāo)準(zhǔn)，并舉例闡述實(shí)現(xiàn)任務(wù)分配的具體過程。

1)眾包任務(wù)t。t為任務(wù)請(qǐng)求者通過移動(dòng)智能設(shè)備向平臺(tái)發(fā)出的任務(wù)請(qǐng)求，可定義為t={Pt,Rt,St,Et,Mt}。其中：Pt、Rt代表t出現(xiàn)的位置和活動(dòng)范圍；St、Et代表t的上線時(shí)間和下線時(shí)間，若在此時(shí)間段內(nèi)t得不到分配，則用戶下線；Mt是任務(wù)t的回報(bào)。

2)眾包工作地點(diǎn)p。p為任務(wù)執(zhí)行的地點(diǎn)，可定義為p={Pp,Sp,Ep,Cp}。其中：Pp代表p出現(xiàn)的位置；Sp、Ep分別代表p的上線時(shí)間和下線時(shí)間；Cp是地點(diǎn)p的容量，即能夠容納Cp個(gè)任務(wù)在p執(zhí)行。

3)眾包工人w。w可定義為w={Pw,Rw,Sw,Ew,Qw}。其中：Pw、Rw是w出現(xiàn)的位置和活動(dòng)范圍；Sw、Ew代表w的上線時(shí)間和下線時(shí)間；Qw是w的工作質(zhì)量。

4)效用。效用定義為U(t,w,p)=Mt*Qw，即若任務(wù)t和工人w得以分配，則效用為任務(wù)回報(bào)和工人工作質(zhì)量的乘積。

在線任務(wù)分配包括三類對(duì)象：任務(wù)t、工作地點(diǎn)p、工人w依時(shí)間次序出現(xiàn)，眾包平臺(tái)在任意時(shí)刻根據(jù)任務(wù)分配算法對(duì)此時(shí)刻已出現(xiàn)的t∈T，p∈P，w∈W進(jìn)行匹配(T、P、W為已出現(xiàn)且未進(jìn)行匹配的任務(wù)、地點(diǎn)和工人的集合)，最終使效用總和最大化。

圖1　任務(wù)、地點(diǎn)和工人分布示意圖Fig. 1　Task, position and worker distribution diagram

1.2　系統(tǒng)分配任務(wù)模式下的任務(wù)分配

無(wú)論是有兩類對(duì)象的眾包平臺(tái)，還是有三類對(duì)象在線分配的新型眾包平臺(tái)，都涉及到了任務(wù)分配問題。根據(jù)時(shí)空眾包任務(wù)分配科技報(bào)告[1],時(shí)空眾包平臺(tái)的任務(wù)分配有兩種不同的模式：工人選擇任務(wù)(Worker Selected Tasks, WST)和系統(tǒng)分配任務(wù)(Server Assigned Tasks, SAT)。WST模式是在線工人不通過眾包平臺(tái)分配而自主選擇任務(wù)請(qǐng)求者發(fā)出的任務(wù)的工作模式，因此眾包平臺(tái)不能控制任務(wù)分配使總效用達(dá)到最優(yōu)，故WST模式不屬于本文研究的重點(diǎn)。以下將介紹SAT模式下兩種對(duì)實(shí)時(shí)性要求不同的任務(wù)分配問題：離線任務(wù)分配與在線任務(wù)分配。

1.2.1離線分配

離線任務(wù)分配問題是傳統(tǒng)眾包中的經(jīng)典問題，其中最具有代表性的微任務(wù)平臺(tái)如Amazon’s Mechanical Turk[2]，文獻(xiàn)[2]中闡述了傳統(tǒng)眾包平臺(tái)可以解決的圖像識(shí)別、信息檢索、自然語(yǔ)言處理及專家系統(tǒng)等，該平臺(tái)為最早的離線分配模型。

隨著傳統(tǒng)眾包的發(fā)展，離線分配問題可以根據(jù)待分配對(duì)象的數(shù)量分為兩類：離線二分匹配和離線三分匹配。長(zhǎng)期以來(lái)，離線二分匹配一直都是組合優(yōu)化領(lǐng)域的經(jīng)典問題，可以看作對(duì)一個(gè)無(wú)向圖G=(U∪V,E)求E的子集M的過程。離線二分匹配可以根據(jù)邊是否有權(quán)重分為最大二分匹配和最大二分加權(quán)匹配[3]，分別對(duì)應(yīng)眾包領(lǐng)域中的兩個(gè)優(yōu)化目標(biāo)：最大化任務(wù)分配數(shù)和最大化效用值。針對(duì)這兩個(gè)不同的優(yōu)化目標(biāo)，文獻(xiàn)[3]分別介紹了Ford-Fulkerson算法和Hungarian算法。文獻(xiàn)[4-5]為了將二分圖匹配問題擴(kuò)展到空間數(shù)據(jù)中，把離線分配問題看作等價(jià)于空間匹配問題的一個(gè)變種問題。針對(duì)空間數(shù)據(jù)的任務(wù)分配，文獻(xiàn)[4，6]針對(duì)移動(dòng)距離進(jìn)行了研究，文獻(xiàn)[4]的優(yōu)化目標(biāo)是基于有容量限制的條件下，最小化匹配的距離之和，而文獻(xiàn)[6]的優(yōu)化目標(biāo)為最小化最大匹配距離。文獻(xiàn)[7]均提出了兩段式分配策略，不同之處在于文獻(xiàn)[7]將整個(gè)分配過程平均為兩個(gè)部分，前后兩個(gè)部分分別采用貪心思想和Hungarian算法解決圖匹配問題，而文獻(xiàn)[8]則在得到初始分配后，在保持分配穩(wěn)定的基礎(chǔ)上維護(hù)分配的最優(yōu)性。與離線二分匹配問題不同，最大三分匹配為NP-hard問題[9]，可利用局部搜索的思想去嘗試獲得更好的結(jié)果。

1.2.2在線分配

在SAT模式中，在線分配問題不僅存在優(yōu)化目標(biāo)的不同，也存在待分配對(duì)象類別和數(shù)量的區(qū)別。文獻(xiàn)[8]認(rèn)為對(duì)象的出現(xiàn)順序能夠影響分配算法的性能，已存在的研究中都在討論最壞情況下的算法性能，但研究發(fā)現(xiàn)最壞情況的出現(xiàn)概率非常低，如果參與對(duì)象的數(shù)量是n的話，則最壞情況出現(xiàn)的概率為1/n!，故研究在最壞情況下的算法性能意義并不大，應(yīng)討論算法在大多數(shù)情況下的平均性能，并提出了競(jìng)爭(zhēng)比的概念。根據(jù)文獻(xiàn)[10]，在線任務(wù)分配可以規(guī)約為有權(quán)雙向圖匹配問題，文獻(xiàn)[11-12]分別利用貪心算法解決此問題，使競(jìng)爭(zhēng)比達(dá)到了1/2。文獻(xiàn)[5]中先把任務(wù)分配問題規(guī)約為穩(wěn)定婚姻問題和最近點(diǎn)問題，然后提出了一種針對(duì)無(wú)權(quán)雙向圖匹配的Chain算法，并在有權(quán)圖上進(jìn)行了改進(jìn)。該算法首先隨機(jī)選取一個(gè)待分配的對(duì)象O作為初始點(diǎn)尋找可與之匹配且最近鄰的其他類對(duì)象Y，再尋找Y的其他最近鄰的對(duì)象，以此類推。文獻(xiàn)[6]提出了關(guān)于距離的閾值算法，只有移動(dòng)距離小于d的對(duì)象才會(huì)得到匹配。文獻(xiàn)[13]針對(duì)兩類對(duì)象的在線分配，以最大化任務(wù)分配數(shù)為優(yōu)化目標(biāo)，但只允許一類對(duì)象動(dòng)態(tài)出現(xiàn)，對(duì)解決在線的最大二分匹配問題提出了新的思路。文獻(xiàn)[8]改進(jìn)了貪心算法加入閾值限制條件，并提出了兩段式全局在線分配算法，根據(jù)對(duì)問題規(guī)模的估計(jì)，在任務(wù)分配過程中，前半段采用貪心的策略為每個(gè)新出現(xiàn)的任務(wù)(工人)分配可能得到最高效用的工人(任務(wù))，后半段使用Hungarian算法對(duì)有權(quán)雙向圖進(jìn)行匹配。文獻(xiàn)[14]改進(jìn)了閾值算法，提出了自適應(yīng)閾值算法，該算法能夠根據(jù)任務(wù)分配情況自動(dòng)調(diào)整閾值的大小。

1.3　其他相關(guān)工作

為保持眾包平臺(tái)參與人員的數(shù)量,文獻(xiàn)[15]提出一套積分管理策略，在對(duì)眾包參與者的吸引及眾包工人的工作質(zhì)量上有一定的幫助。文獻(xiàn)[16]通過反轉(zhuǎn)競(jìng)拍、游戲化、經(jīng)驗(yàn)值更新等策略激勵(lì)眾包參與者和吸引更多的眾包參與者。文獻(xiàn)[17]提出一種基于多種任務(wù)的主題感知任務(wù)分配策略，根據(jù)任務(wù)的類型分配擅長(zhǎng)該類型任務(wù)的眾包工人。

基于以上研究可以發(fā)現(xiàn)，在各類閾值算法中，雖然通過設(shè)置閾值可以過濾掉效用較小的分配對(duì)，但僅僅設(shè)置閾值往往還不能使結(jié)果接近最優(yōu)，必須有相應(yīng)的匹配策略來(lái)調(diào)度?；诖耍疚奶岢鲆环N基于統(tǒng)計(jì)預(yù)測(cè)的自適應(yīng)閾值算法和匹配策略。實(shí)驗(yàn)表明，該算法能夠在真實(shí)情況下使總效用接近最優(yōu)，算法整體表現(xiàn)優(yōu)于貪心算法和隨機(jī)閾值算法。

2　閾值算法與匹配策略

2.1　貪心算法

文獻(xiàn)[14]中稱貪心算法為樸素隨機(jī)算法，意為對(duì)每一個(gè)新出現(xiàn)的對(duì)象，如果通過這個(gè)對(duì)象可以作出若干任務(wù)分配，則從任務(wù)分配集中隨機(jī)選擇一種分配。算法的輸入為新出現(xiàn)的對(duì)象，包括任務(wù)、工人、工作地點(diǎn)以及效用函數(shù)；算法的輸出為分配結(jié)果。當(dāng)新對(duì)象出現(xiàn)時(shí)，算法會(huì)在候選隊(duì)列中隨機(jī)選擇滿足約束條件的匹配對(duì)象。如果得到的匹配結(jié)果不為空，則把新出現(xiàn)的對(duì)象和匹配到的對(duì)象加入到分配結(jié)果，并把匹配對(duì)象從候選隊(duì)列中移除，停止查找；如果匹配對(duì)象為空，則把新出現(xiàn)的對(duì)象加入到候選隊(duì)列中。

算法1貪心算法。

輸入隨機(jī)出現(xiàn)的任務(wù)、工人、工作地點(diǎn)及效用函數(shù)。

對(duì)每一個(gè)新出現(xiàn)的任務(wù)、工人及工作地點(diǎn)v：

1)根據(jù)出現(xiàn)對(duì)象的類型，在候選隊(duì)列中選擇滿足約束的其他兩類對(duì)象:o1,o2←Cand。

2)若o1,o2不為空，則將v與o1,o2進(jìn)行匹配，得到匹配結(jié)果:M←{v,o1,o2}。

3)若o1,o2為空，則將v加入候選隊(duì)列:Cand←v。輸出匹配結(jié)果M。

貪心算法雖時(shí)間消耗比較小，但是由于任務(wù)、地點(diǎn)、工人完全是按照出現(xiàn)順序進(jìn)行分配，沒有考慮效用的大小，所以在不同回報(bào)的任務(wù)出現(xiàn)沖突時(shí)，貪心算法會(huì)按照出現(xiàn)順序選擇待分配對(duì)象。若回報(bào)較低的任務(wù)先出現(xiàn)并且滿足分配條件時(shí)，后出現(xiàn)的較高回報(bào)的任務(wù)將無(wú)法得到分配。

2.2　隨機(jī)閾值算法

隨機(jī)閾值算法是改進(jìn)的貪心算法，對(duì)新出現(xiàn)的對(duì)象,除需要對(duì)象滿足基本的活動(dòng)范圍條件外，還需滿足閾值條件即該分配產(chǎn)生的效用應(yīng)大于隨機(jī)閾值。如算法2所示，在算法第1)步，首先閾值設(shè)置為ek，k為隨機(jī)選擇0～θ的值，θ的取值為：

θ=「ln(Umax+1)?

(1)

其中Umax是從任務(wù)分配過程中單個(gè)分配可能獲得的最大效用，可以從歷史分配數(shù)據(jù)中獲得。在候選隊(duì)列中隨機(jī)選擇一個(gè)滿足約束條件且滿足產(chǎn)生的效用大于閾值的匹配對(duì)象。如果匹配對(duì)象不為空，則加入分配結(jié)果，然后從候選隊(duì)列中移除匹配對(duì)象，停止查找；否則把新對(duì)象加入到候選隊(duì)列中。最后返回分配結(jié)果。

算法2隨機(jī)閾值算法。

輸入隨機(jī)出現(xiàn)的任務(wù)、工人、工作地點(diǎn)及效用函數(shù)。

對(duì)每一個(gè)新出現(xiàn)的任務(wù)、工人及工作地點(diǎn)v：

1)隨機(jī)設(shè)置閾值ek:k∈[0,θ]，θ=「ln(Umax+1)?。

2)根據(jù)出現(xiàn)對(duì)象的類型,在候選隊(duì)列中選擇滿足約束且產(chǎn)生效用大于閾值的其他兩類對(duì)象:o1,o2←Cand。

3)若o1,o2不為空，則將v與o1,o2進(jìn)行匹配，得到匹配結(jié)果:M←{v,o1,o2}。

4)若o1,o2為空，則將v加入候選隊(duì)列:Cand←v。輸出匹配結(jié)果M。

盡管隨機(jī)閾值算法能夠在一定程度上過濾掉效用較低的任務(wù)分配，但是由于k值的選擇是隨機(jī)的，所以算法總效用差異較大，表現(xiàn)不穩(wěn)定。

2.3　基于統(tǒng)計(jì)預(yù)測(cè)的自適應(yīng)閾值算法

在閾值算法中，三類對(duì)象可以分配的前提是滿足一定的閾值條件。閾值的設(shè)置關(guān)鍵之處在于：若閾值設(shè)置過低，無(wú)法起到過濾作用，使整個(gè)分配過程與貪心算法類似且計(jì)算量增多；若閾值設(shè)置過高，大部分對(duì)象無(wú)法正常參與分配，浪費(fèi)平臺(tái)總效用。為解決閾值的設(shè)置問題，本文提出一種基于統(tǒng)計(jì)預(yù)測(cè)的自適應(yīng)閾值算法，算法思想如下。

2.3.1閾值作用對(duì)象

在貪心算法和隨機(jī)閾值算法中，閾值通常是針對(duì)效用設(shè)置的，有如下缺點(diǎn)：1)閾值產(chǎn)生作用的前提是對(duì)任務(wù)進(jìn)行預(yù)分配得到效用值，根據(jù)該效用值是否滿足閾值條件決定該分配是否有效，若未滿足閾值條件則考慮其他分配，這種局部搜索方法造成的時(shí)間消耗會(huì)使任務(wù)分配的等待時(shí)間變長(zhǎng)；2)有一定的概率造成效用的浪費(fèi)，例如高回報(bào)任務(wù)與低工作質(zhì)量工人結(jié)合或低回報(bào)任務(wù)與高工作質(zhì)量工人結(jié)合的分配方式，雖然效用值滿足閾值條件，但是以上兩種分配方式并不能得到理想的效用值。

為解決以上問題，本文將任務(wù)的回報(bào)值作為閾值的作用對(duì)象。當(dāng)任務(wù)出現(xiàn)時(shí)，考察該任務(wù)的回報(bào)值，若任務(wù)回報(bào)值滿足閾值條件則進(jìn)入任務(wù)隊(duì)列，否則丟棄掉。為任務(wù)的回報(bào)設(shè)置閾值有以下優(yōu)勢(shì)：1)如圖2所示，在任務(wù)出現(xiàn)時(shí)，按照閾值大小可直接決定此任務(wù)是否可加入任務(wù)隊(duì)列，省去了局部搜索的過程，減少時(shí)間消耗并提高了分配效率；2)過濾掉回報(bào)較小的任務(wù)，能降低低回報(bào)任務(wù)與高工作質(zhì)量工人分配的概率，提高眾包平臺(tái)整體的效用值。

圖2　閾值算法示意圖Fig. 2　Threshold algorithm diagram

2.3.2閾值設(shè)置

基于統(tǒng)計(jì)預(yù)測(cè)的自適應(yīng)閾值算法采用一種在線調(diào)整的策略，該算法的運(yùn)行過程根據(jù)實(shí)時(shí)出現(xiàn)的任務(wù)、工人、工作地點(diǎn)和得到分配的對(duì)象以及超時(shí)的對(duì)象，實(shí)時(shí)統(tǒng)計(jì)當(dāng)前平臺(tái)中空閑任務(wù)(Free Task, FT)、空閑工人(Free Worker, FW)、空閑工作地點(diǎn)(Free Position, FP)的數(shù)量，以及最大回報(bào)值Rmax和最小回報(bào)值Rmin。根據(jù)前一時(shí)刻的閾值θ′，在調(diào)整基數(shù)?的基礎(chǔ)上計(jì)算出當(dāng)前時(shí)刻的閾值θ。

(2)

為防止閾值的波動(dòng)過大導(dǎo)致的平臺(tái)運(yùn)行狀態(tài)不穩(wěn)定，閾值的設(shè)置應(yīng)當(dāng)控制在一定的范圍內(nèi)，本文將閾值的調(diào)整范圍設(shè)置為當(dāng)前時(shí)刻出現(xiàn)任務(wù)回報(bào)的差值，每次調(diào)整的范圍為[-?,?]。當(dāng)某時(shí)刻未出現(xiàn)任務(wù)或出現(xiàn)單個(gè)任務(wù)時(shí)，調(diào)整范圍設(shè)置為1，只進(jìn)行較小幅度的調(diào)整。CRmax與CRmin分別是當(dāng)前時(shí)刻出現(xiàn)的最大回報(bào)值和最小回報(bào)值。

(3)

算法3基于統(tǒng)計(jì)預(yù)測(cè)的自適應(yīng)閾值算法。

輸入隨機(jī)出現(xiàn)的任務(wù)、工人、工作地點(diǎn)及效用函數(shù)。

1)對(duì)每一個(gè)新出現(xiàn)的任務(wù)、工人及工作地點(diǎn)v，根據(jù)式(2)計(jì)算當(dāng)前時(shí)刻的閾值。

2)根據(jù)出現(xiàn)對(duì)象的類型，在候選隊(duì)列中選擇滿足約束且產(chǎn)生效用大于閾值的其他兩類對(duì)象:o1,o2←Cand。

3)若o1,o2不為空，則將v與o1,o2進(jìn)行匹配，得到匹配結(jié)果:M←{v,o1,o2}。

4)若o1,o2為空，則將v加入候選隊(duì)列:Cand←v。

輸出匹配結(jié)果M。

2.4　匹配策略

任務(wù)分配算法的性能及效果在很大程度上依賴數(shù)據(jù)的分布或?qū)ο蟪霈F(xiàn)的順序[8]，若數(shù)據(jù)分布不均勻則算法的效果無(wú)法保證。為消除這種不確定性，本文采用“一對(duì)一”的匹配策略，在滿足約束條件即待分配的對(duì)象在互相的活動(dòng)范圍內(nèi)時(shí)，當(dāng)任務(wù)回報(bào)確定時(shí)，與之匹配的工人也將確定。通過匹配策略，使平臺(tái)的總效用值達(dá)到最優(yōu)或接近最優(yōu)。

“一對(duì)一”的匹配策略采用Min-max normalization方法為每個(gè)任務(wù)匹配工人。假設(shè)任務(wù)回報(bào)值的范圍為Mt∈[0,100]，工人的工作質(zhì)量Qw∈[0,1],若出現(xiàn)一個(gè)任務(wù)回報(bào)值為80的任務(wù)，則根據(jù)匹配策略將為其匹配一個(gè)工作質(zhì)量為0.8的眾包工人。匹配策略可以避免低回報(bào)任務(wù)與高工作質(zhì)量工人結(jié)合或高回報(bào)值任務(wù)與低工作質(zhì)量工人結(jié)合造成平臺(tái)效用的浪費(fèi)。

在數(shù)據(jù)分布不均勻時(shí)，采用匹配策略能夠出現(xiàn)任務(wù)或工人的閑置問題。如圖3所示，對(duì)gMission[18]數(shù)據(jù)集進(jìn)行統(tǒng)計(jì)發(fā)現(xiàn)，工人的工作質(zhì)量集中在0.5左右，而任務(wù)的回報(bào)值集中在80～90，回報(bào)值為90的任務(wù)與工作質(zhì)量為0.5的工人都不能完全匹配到合適的對(duì)象。為解決此問題，本文把任務(wù)與工人根據(jù)其數(shù)據(jù)分布分為兩個(gè)部分。通過對(duì)歷史數(shù)據(jù)的分析和估計(jì)得到任務(wù)回報(bào)值的中位數(shù)α和眾包工人工作質(zhì)量的中位數(shù)β。當(dāng)出現(xiàn)一個(gè)任務(wù)時(shí)，若任務(wù)的回報(bào)Mt∈[0,α]，則匹配的工人工作質(zhì)量也應(yīng)滿足Qw∈[0,β]；若任務(wù)的回報(bào)Mt∈[α,100]，則匹配的工人工作質(zhì)量也應(yīng)滿足Qw∈[β,1]。根據(jù)此規(guī)則，使用Min-max normalization方法尋找一個(gè)滿足匹配策略的其他對(duì)象。

圖3　gMission數(shù)據(jù)集任務(wù)回報(bào)及工人工作質(zhì)量分布Fig. 3　Task return and worker quality distribution of gMission data set

而真實(shí)情況中，在匹配確定工作質(zhì)量或回報(bào)的對(duì)象中，往往沒有完全吻合條件的確定對(duì)象，此時(shí)可匹配近似滿足條件的對(duì)象，近似對(duì)象與確定對(duì)象之間的差異不超過5%，此差異值的設(shè)置可參考眾包對(duì)象的密度。

2.5　基于統(tǒng)計(jì)的概率預(yù)測(cè)

在2.4節(jié)中介紹了當(dāng)出現(xiàn)一個(gè)任務(wù)t時(shí)，如何匹配滿足約束條件且使效用最大化的工人w。本節(jié)主要講述計(jì)算工人w會(huì)在任務(wù)t的活動(dòng)時(shí)間內(nèi)出現(xiàn)的概率，按照概率決定任務(wù)t是否等待工人w。

在歷史數(shù)據(jù)中可以得到在整個(gè)眾包活動(dòng)周期中可與任務(wù)t匹配的工人w的數(shù)量，通過對(duì)多組數(shù)據(jù)的學(xué)習(xí)可以得到一個(gè)估值。任務(wù)t的生命周期有時(shí)長(zhǎng)限制，可計(jì)算出在任務(wù)t的生命周期內(nèi)可以出現(xiàn)的工人w的數(shù)量。由于眾包平臺(tái)任務(wù)及工人的出現(xiàn)受客觀因素影響較大，故在任務(wù)t的生命周期內(nèi)可以通過匹配策略匹配到工人w的概率是：

(4)

其中β是在不同環(huán)境下客觀因素對(duì)眾包平臺(tái)的影響指數(shù)，如天氣、節(jié)假日等。當(dāng)p(t,w)≥θ，即在任務(wù)t的生命周期內(nèi)匹配到工人w的概率大于θ時(shí)，任務(wù)t選擇等待工人w；反之，則不等待。

在估計(jì)任務(wù)t匹配到工人w的概率的同時(shí)，為該類工人W建立等待隊(duì)列Queue，工作質(zhì)量相同的工人可看作一類工人，該隊(duì)列中存儲(chǔ)正在等待該類工人W的任務(wù)。Queue的長(zhǎng)度為σ-Eσ，即估計(jì)的將要出現(xiàn)的該類工人的數(shù)量σ與已經(jīng)出現(xiàn)的該類工人數(shù)量Eσ之差。查看W的等待隊(duì)列是否超過該類工人出現(xiàn)的個(gè)數(shù)，若超過，則t的匹配對(duì)象自動(dòng)等待w的近似對(duì)象。根據(jù)以上規(guī)則，可定義損失函數(shù)：

(5)

2.6　運(yùn)行實(shí)例

假設(shè)目前可以通過閾值算法加入到隊(duì)列的眾包對(duì)象有：任務(wù)t1、t2和t3、工作地點(diǎn)p1，工人w1和w2,且對(duì)所有對(duì)象都滿足p(t,w)≥θ。其中眾包任務(wù)的回報(bào)值為t1:40，t2:58和t3:100，眾包工人的工作質(zhì)量為w1:0.4和w2:0.96，眾包工作地點(diǎn)的容量為3，加入隊(duì)列的順序?yàn)閠3、p1、w1、t1、w2、t2，眾包任務(wù)回報(bào)值的中位數(shù)為60，眾包工人工作質(zhì)量的中位數(shù)為0.4，且所有的對(duì)象都處在其他對(duì)象的活動(dòng)范圍內(nèi),其分配過程如圖4所示。

圖4　匹配策略運(yùn)行示意圖Fig. 4　Running diagram of matching strategy

如圖4所示，當(dāng)t3、p1、w1出現(xiàn)時(shí)，按照匹配策略的規(guī)則未進(jìn)行匹配操作。t2出現(xiàn)后，根據(jù)Min-max normalization方法可求得應(yīng)為t2作出匹配的眾包工人的工作質(zhì)量為0.39，但此時(shí)隊(duì)列中不存在工作質(zhì)量為0.39的眾包工人，由于差異值設(shè)為5%,則其近似對(duì)象的工作質(zhì)量取值范圍為[0.34,0.44]，故t2與p1、w1進(jìn)行匹配，得到的效用值為23.2。同理w2出現(xiàn)后與t3匹配，得到效用值為96，總效用為118.2。在不使用匹配策略的情況下，能夠進(jìn)入待分配隊(duì)列的對(duì)象則會(huì)按照出現(xiàn)順序進(jìn)行分配，得到的效用值為78.4。

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

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

本文實(shí)驗(yàn)均使用了處理器為Intel Core i7- 7500U CPU @ 2.70 GHz 2.90 GHz、內(nèi)存為8 GB(內(nèi)存頻率1 867 MHz)，操作系統(tǒng)為Windows 10的計(jì)算機(jī)完成。實(shí)驗(yàn)使用的編程語(yǔ)言為Python2.7，使用的集成開發(fā)環(huán)境為PyCharm 2016。實(shí)驗(yàn)數(shù)據(jù)保存在文本文件中，按行讀取以表示眾包參與者出現(xiàn)的時(shí)間和順序，同時(shí)借助了MongoDB存儲(chǔ)在文本文件中讀取到的實(shí)驗(yàn)數(shù)據(jù)。

3.2　數(shù)據(jù)集

實(shí)驗(yàn)使用gMission的數(shù)據(jù)集。為了保護(hù)隱私，gMission數(shù)據(jù)集在真實(shí)數(shù)據(jù)集的基礎(chǔ)上進(jìn)行了部分模糊處理。gMission數(shù)據(jù)集共分為5個(gè)數(shù)據(jù)文件，分別對(duì)應(yīng)將眾包活動(dòng)范圍設(shè)置為不同數(shù)值時(shí)所產(chǎn)生的數(shù)據(jù)，眾包活動(dòng)范圍有：10、15、20、25、30。每份數(shù)據(jù)文件中包含的屬性包括眾包參與者的類型、出現(xiàn)時(shí)間、坐標(biāo)X、坐標(biāo)Y、活動(dòng)范圍，這五個(gè)屬性是共有的。眾包任務(wù)還有回報(bào)值、截止時(shí)間兩個(gè)屬性，眾包工作地點(diǎn)有容量屬性，眾包工人有工作質(zhì)量屬性。每個(gè)部分的數(shù)據(jù)集共有6 300條數(shù)據(jù)，其中包括3 000個(gè)任務(wù)、3 000個(gè)工人、300個(gè)工作地點(diǎn)(每個(gè)工作地點(diǎn)容量為10)，圖5為活動(dòng)范圍為10時(shí)的三類對(duì)象隨時(shí)間出現(xiàn)的累計(jì)數(shù)量。

圖5　三類對(duì)象依時(shí)間出現(xiàn)的個(gè)數(shù)Fig. 5　Numbers of three types of objects which appear in time

3.3　實(shí)驗(yàn)設(shè)置

本文提出的基于統(tǒng)計(jì)預(yù)測(cè)的自適應(yīng)閾值算法與貪心算法、隨機(jī)閾值算法進(jìn)行對(duì)比，評(píng)價(jià)指標(biāo)為獲得的總效用值，即各個(gè)分配得到的效用和。同時(shí)本文使用的數(shù)據(jù)為五種眾包活動(dòng)范圍的數(shù)據(jù)集，觀察改變活動(dòng)范圍時(shí)效用的變化。在隨機(jī)閾值算法中，Umax設(shè)置為100。在基于統(tǒng)計(jì)預(yù)測(cè)的自適應(yīng)閾值算法中，初始閾值θ設(shè)置為歷史數(shù)據(jù)中任務(wù)回報(bào)的均值，影響指數(shù)β設(shè)置為1。

3.4　實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)結(jié)果如圖6所示，可以觀察到隨著活動(dòng)范圍的擴(kuò)大，總效用也在增長(zhǎng)，原因可以歸結(jié)為隨著活動(dòng)范圍的擴(kuò)大，任務(wù)能夠在更大的范圍內(nèi)匹配合理的工人。同時(shí)，在不同活動(dòng)范圍的數(shù)據(jù)集上，基于統(tǒng)計(jì)預(yù)測(cè)的自適應(yīng)閾值算法的總效用始終優(yōu)于貪心算法和隨機(jī)閾值算法，并且隨著活動(dòng)范圍的不斷擴(kuò)大，貪心算法和隨機(jī)閾值算法的總效用值趨于不變，而基于統(tǒng)計(jì)預(yù)測(cè)的自適應(yīng)閾值算法依然可以獲得較高的總效用值。

圖6　gMission數(shù)據(jù)集實(shí)驗(yàn)結(jié)果Fig. 6　Experimental results for gMission data set

3.5　實(shí)驗(yàn)分析

通過在真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，發(fā)現(xiàn)在不同活動(dòng)范圍的條件下，基于統(tǒng)計(jì)預(yù)測(cè)的自適應(yīng)閾值算法產(chǎn)生的總效用優(yōu)于貪心算法和隨機(jī)閾值算法，并且隨著活動(dòng)范圍的擴(kuò)大，總效用的增長(zhǎng)不會(huì)出現(xiàn)衰減。這說(shuō)明本文中提出的基于統(tǒng)計(jì)預(yù)測(cè)的自適應(yīng)閾值算法具有較好的實(shí)際應(yīng)用價(jià)值。

4　結(jié)語(yǔ)

本文研究了時(shí)空眾包環(huán)境下三類對(duì)象的在線分配算法，并分析了貪心算法和隨機(jī)閾值算法無(wú)法獲得較高效用的原因，提出了一種基于統(tǒng)計(jì)預(yù)測(cè)的自適應(yīng)閾值算法。本文在充分理解閾值算法作用機(jī)制的前提下，改變了閾值算法的作用對(duì)象，提出了旨在最大限度利用可用資源的算法，通過對(duì)眾包參與者人數(shù)的分析，制定閾值的設(shè)置及調(diào)整策略。通過匹配策略，眾包平臺(tái)的任務(wù)分配不再是隨機(jī)分配，而是一種更具有確定性的分配方式。實(shí)驗(yàn)表明，本文提出的任務(wù)分配方法能夠使眾包平臺(tái)獲得更高的總效用值。

參考文獻(xiàn):

[1]CHENG P, JIAN X, CHEN L. Task assignment on spatial crowdsourcing [R/OL]. [2017- 05- 02]. http://arxiv.org/pdf/1605.09675.

[2]KITTUR A, CHI E H, SUH B. Crowdsourcing user studies with Mechanical Turk [C]// CHI ’08: Proceedings of the 2008 SIGCHI Conference on Human Factors in Computing Systems. New York: ACM, 2008: 453-456.

[3]CORMEN T H, LEISERSON C E, RIVEST R, et al. Introduction to Algorithms [M]. Cambridge, MA: MIT Press, 2009: 118.

[4]LEONG HOU U, MAN LUNG YIU, MOURATIDIS K, et al. Capacity constrained assignment in spatial databases [C]// SIGMOD ’08: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2008: 15-28.

[5]WONG R C-W, TAO Y, FU A W-C, et al. On efficient spatial matching [C]// VLDB ’07: Proceedings of the 33rd International Conference on Very large Data Bases. New York: ACM, 2007: 579-590.

[6]LONG C, WONG R C-W, YU P S, et al. On optimal worst-case matching [C]// SIGMOD ’13: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2013: 845-856.

[7]TONG Y, SHE J, DING B, et al. Online mobile micro-task allocation in spatial crowdsourcing [C]// ICDE 2016: Proceedings of the 2016 IEEE 32nd International Conference on Data Engineering. Piscataway, NJ: IEEE, 2016: 49-60.

[8]LEONG HOU U, MOURATIDIS K, MAMOULIS N. Continuous spatial assignment of moving users [J]. The VLDB Journal — The International Journal on Very Large Data Bases, 2010, 19(2): 141-160.

[9]GAREY M R, JOHNSON D S. Computers and Intractability: A Guide to the Theory of NP-completeness [M]. New York: W. H. Freeman, 1979: 90-91.

[10]MEHTA A. Online matching and ad allocation [J]. Foundations & Trends in Theoretical Computer Science, 2013, 8(4): 265-368.

[11]WANG Y, WONG S C-W. Two-sided online bipartite matching and vertex cover: beating the greedy algorithm [C]// ICALP 2015: Proceedings of the 2015 International Colloquium on Automata, Languages, and Programming, LNCS 9134. Berlin: Springer, 2015: 1070-1081.

[12]TING H F, XIANG X. Near optimal algorithms for online maximum edge-weighted b-matching and two-sided vertex-weighted b-matching [J]. Theoretical Computer Science, 2015, 607(P2): 247-256.

[13]HASSAN U U, CURRY E. A multi-armed bandit approach to online spatial task assignment [C]// UIC-ATC-ScalCom ’14: Proceedings of the 2014 IEEE 11th International Conference on Ubiquitous Intelligence and Computing, and 2014 IEEE 11th International Conference on Autonomic and Trusted Computing, and 2014

IEEE 14th International Conference on Scalable Computing and Communications and Its Associated Workshops. Washington, DC: IEEE Computer Society, 2014: 212-219.

[14]宋天舒，童詠昕.空間眾包環(huán)境下的三類對(duì)象在線任務(wù)分配[J].軟件學(xué)報(bào)，2017,28(3):611-630. (SONG T S, TONG Y X. Three types of objects online task allocation space crowdsourcing environment.[J] Journal of Software, 2017, 28(3): 611-630.)

[15]REN J, ZHANG Y, ZHANG K, et al. SACRM: Social Aware Crowdsourcing with Reputation Management in mobile sensing [J]. Computer Communications, 2014, 65: 55-65.

[16]DAI W, WANG Y, JIN Q, et al. An integrated incentive framework for mobile crowdsourced sensing [J]. Tsinghua Science and Technology, 2016, 21(2): 146-156.

[17]張曉航,李國(guó)良,馮建華.大數(shù)據(jù)群體計(jì)算中用戶主題感知的任務(wù)分配[J].計(jì)算機(jī)研究與發(fā)展,2015,52(2):309-317. (ZHANG X H, LI G L, FENG J H. User topic aware task assignment in large data group computing [J]. Journal of Computer Research and Development, 2015, 52 (2): 309-317).

[18]CHEN Z, FU R, ZHAO Z, et al. gMission: a general spatial crowdsourcing platform [J]. Proceedings of the Very Large Data Base Endowment, 2014, 7(13): 1629-1632.