王亦敬，陳 榮，郭世凱，于 茜，張程偉

(大連海事大學(xué) 信息技術(shù)學(xué)院 遼寧 大連 116026)

0 引言

隨著先進(jìn)移動(dòng)設(shè)備以及無(wú)線網(wǎng)絡(luò)的普及，出現(xiàn)了一種新的眾包方式——空間眾包(spatial crowdsourcing，SC)[1-2]。SC系統(tǒng)由一群工人、一個(gè)云平臺(tái)和需求者組成，平臺(tái)負(fù)責(zé)發(fā)布各種與位置相關(guān)的空間任務(wù)，工人可以自身移動(dòng)到這些位置并完成相關(guān)的空間任務(wù)[3]。SC可以完成大量個(gè)人用戶無(wú)法應(yīng)對(duì)的空間任務(wù)，已廣泛應(yīng)用于諸多領(lǐng)域。如何將這些任務(wù)分配給工人成為當(dāng)前SC研究的主要問(wèn)題[4]?，F(xiàn)有的SC研究和技術(shù)工作一般聚焦在普通空間任務(wù)上，這些任務(wù)可以由非專業(yè)勞動(dòng)者完成，例如眾包災(zāi)難響應(yīng)和新聞報(bào)道。隨著任務(wù)的多樣化，尋找具有專業(yè)知識(shí)且質(zhì)量高的工人完成特定空間任務(wù)成為SC任務(wù)分配的目標(biāo)之一，例如某景點(diǎn)的法語(yǔ)解說(shuō)工作[5]。同時(shí)，人們開(kāi)始關(guān)注任務(wù)的完成質(zhì)量，這意味著平臺(tái)需要明確任務(wù)和工人屬性，以便精準(zhǔn)分配和高效完成任務(wù)。

當(dāng)前研究中一般單純考慮任務(wù)是否分配或工人的專業(yè)知識(shí)是否與任務(wù)相匹配[6]，導(dǎo)致平臺(tái)很可能將一個(gè)難度較大的任務(wù)分配給一個(gè)水平不夠或信譽(yù)度較低的工人。若沒(méi)有考慮工人是否能夠勝任，即無(wú)法得知該工人成功完成任務(wù)的概率，必然會(huì)影響任務(wù)完成率以及精確分配分?jǐn)?shù)等評(píng)價(jià)指標(biāo)。其中，最大化任務(wù)分配數(shù)量(maximum task assignment, MTA)是大部分工作的首要目標(biāo)[7]，其主要算法有兩種：一為二分圖匹配。當(dāng)不考慮工人任務(wù)時(shí)限問(wèn)題并假設(shè)所有工人皆能可靠完成任務(wù)時(shí)，便轉(zhuǎn)化為二分圖匹配問(wèn)題。二為定義位置熵。即將問(wèn)題轉(zhuǎn)化為最小成本最大流問(wèn)題[8]。由此可見(jiàn)，MTA局限于關(guān)注任務(wù)是否被分配，并不考慮工人是否具備能力。于是文獻(xiàn)[7]提出最大化匹配分?jǐn)?shù)(maximum score assignment, MSA)問(wèn)題。MSA方法為工人與任務(wù)隨機(jī)設(shè)定技能整數(shù)值，因此問(wèn)題目標(biāo)成為在考慮工人專業(yè)知識(shí)背景下探索任務(wù)分配問(wèn)題。但MSA僅加入了工人技能屬性，并未考慮工人效用值(代表工人可靠性)的不同會(huì)在很大程度上影響任務(wù)的完成率。若能夠在分配前得到工人完成某類任務(wù)的成功概率值(效用值)，則能夠有效避免由于工人質(zhì)量未知而導(dǎo)致匹配成功率降低的問(wèn)題。因此，本文提出一種用于SC任務(wù)匹配的未知工人效用估計(jì)方法，基于多臂老虎機(jī)(multi-armed bandit，MAB)模型進(jìn)行工人效用值計(jì)算，實(shí)現(xiàn)對(duì)任務(wù)和工人的高質(zhì)量匹配，采用兩階段算法解決帶有效用的最高分?jǐn)?shù)匹配(maximum score assignment with utility, MSAU)問(wèn)題。階段一在MAB模型的基礎(chǔ)上，利用具有臂特征的有界LinUCB算法[9]，解決傳統(tǒng)MAB算法在求解SC中工人與任務(wù)個(gè)體間存在很大差異時(shí)的異常收斂及相同屬性臂問(wèn)題；階段二采用改進(jìn)的分配加分方式,將效用值帶入精確分配分?jǐn)?shù)的計(jì)算中，定義新的加分方式與完成概念，清晰展現(xiàn)了在考慮工人效用值后帶給任務(wù)分配的積極影響。使用來(lái)自MovieLens和Gowalla數(shù)據(jù)集的真實(shí)歷史用戶數(shù)據(jù)，驗(yàn)證了帶有工人效用的任務(wù)匹配模型對(duì)任務(wù)分配評(píng)價(jià)指標(biāo)有很大程度的提高。

1 MAB模型介紹

MAB是一類處理不確定性決策問(wèn)題的模型，非常適合解決專家眾包問(wèn)題。在SC背景下，玩家類比于任務(wù)，老虎臂類比于工人，動(dòng)作類比于工人任務(wù)進(jìn)行一次匹配。在優(yōu)化過(guò)程中，工人最初具有未知獎(jiǎng)勵(lì)，必須通過(guò)嘈雜的試驗(yàn)來(lái)學(xué)習(xí)，其目標(biāo)是通過(guò)依次選擇不同的動(dòng)作來(lái)最大化獎(jiǎng)勵(lì)總量[10-12]。MAB模型中最著名的一個(gè)方法是上界置信區(qū)間(upper confidence bound，UCB)，UCB通過(guò)嚴(yán)格的理論論證可達(dá)到接近理論最優(yōu)的整體收益。但UCB需要嘗試一遍所有臂，因此當(dāng)臂數(shù)量很多時(shí)會(huì)出現(xiàn)過(guò)早收斂的問(wèn)題，而且UCB并未充分利用環(huán)境信息。

“Yahoo!”科學(xué)家們加入特征信息，提出了基于UCB的LinUCB算法[9]，不再僅僅是根據(jù)實(shí)驗(yàn)估算置信區(qū)間，而是結(jié)合了特征信息。然而LinUCB算法依舊存在一個(gè)問(wèn)題：由于需要計(jì)算每一個(gè)候選臂的期望收益和置信區(qū)間，因此同時(shí)處理的候選臂數(shù)量不能過(guò)大。在后續(xù)研究中，科學(xué)家們陸續(xù)提出了一些避免臂數(shù)量過(guò)多而導(dǎo)致收斂問(wèn)題的算法。例如與協(xié)同過(guò)濾算法結(jié)合[13-14]，采用協(xié)同聚類使玩家和老虎臂兩種協(xié)同方式同時(shí)進(jìn)行等。本文利用MAB模型估計(jì)工人的效用值，在解決了Genius Rocket站點(diǎn)需要?jiǎng)趧?dòng)密集型手動(dòng)選擇問(wèn)題的同時(shí)，也避免出現(xiàn)由于未知工人質(zhì)量而導(dǎo)致分配數(shù)量和質(zhì)量降低的情況。

2 兩階段模型

圖1為用于SC任務(wù)匹配的未知工人效用評(píng)估方法框架，主要分為兩個(gè)階段。

圖1 用于SC任務(wù)匹配的未知工人效用評(píng)估方法框架

2.1 階段一：基于MAB的工人效用評(píng)估

在評(píng)估工人效用時(shí)，采用時(shí)間復(fù)雜度為O(n3)的LinUCB算法，以老虎機(jī)一輪游戲模擬一次為任務(wù)選擇工人的過(guò)程，玩家作任務(wù)，老虎臂作工人，動(dòng)作作匹配過(guò)程，通過(guò)依次選擇不同老虎臂來(lái)最大化分配數(shù)量。

(1)

則對(duì)于所有的實(shí)驗(yàn)t，有

(2)

最后可以得出UCB類型的帶有工人效用值計(jì)算的MAB算法選擇策略，在每輪實(shí)驗(yàn)t，

(3)

效用值估計(jì)算法(算法1)的具體步驟如下。

算法1效用值估計(jì)

輸入：輸入矩陣A，參數(shù)a。

輸出：效用值ui,j。

fori=1,2,…,Tdo

計(jì)算所有臂的特征值j∈Ai:xi,j∈Rd

forj∈Aido

ifais new then

Aj←Id

bj←Od×1

end if

end for

bij←bij+rixi,j

end for

2.2 階段二：結(jié)合效用值的任務(wù)分配

2.2.1問(wèn)題定義 為了體現(xiàn)工人質(zhì)量作用以及明確表示分配方式的改變，進(jìn)行了如下定義。

定義1時(shí)空任務(wù)。時(shí)空任務(wù)t的形式為〈l,s,Entropy(l),Skill〉,其中l(wèi)表示任務(wù)t經(jīng)緯度；s表示時(shí)間片；Entropy(l)表示位置熵；Skill表示任務(wù)t所需技能。

定義2工人。工人w的形式為〈id,Tmax,R,l,Skill,uij〉,其中id表示唯一確定工人身份的編號(hào)；Tmax表示工人w最多可接受任務(wù)數(shù)量；R表示接受范圍；l表示工人w經(jīng)緯度；Skill表示工人w所具備技能；uij表示工人i對(duì)任務(wù)j的效用值。

定義3技能匹配。若工人完成任務(wù)的效用值大于閾值p且技能相符，即uij>p∧Skillw=Skillt時(shí)，方可認(rèn)為工人任務(wù)符合技能匹配。

定義4任務(wù)完成。當(dāng)工人對(duì)應(yīng)分配任務(wù)的效用值小于閾值時(shí)，即uij

定義5分?jǐn)?shù)。為了衡量分配情況，定義分?jǐn)?shù)概念，并將加分方式[7]

更改為

任務(wù)分配算法(算法2)的具體步驟如下。

算法2任務(wù)分配

輸入：輸入工人和任務(wù)矩陣Wsi、Tsi以及參數(shù)r，并輸入策略類型algorithm，開(kāi)始和截止時(shí)間startTime、endTime。

輸出：工人任務(wù)對(duì)WTfinal={〈w1,t1〉,…,〈wn,tn〉}。

1.forsi←startTimetoendTimedo

初始化工人矩陣W=Wsi、有效工人矩陣Wavailable=φ、有效任務(wù)矩陣Tavailable=φ

初始化w′i個(gè)候選時(shí)空任務(wù)集Twi=φ

2. forwj∈Wothersdo

3. ifwj.timeStamp=sithenW←wj

4. forwi∈Wdo

5. fortj∈Tsido

6. ifdistance(wi,tj)≤rthenTwi←tj,Tavailable←tj

7. ifTwi=φ,Wavailable←wi

8. 將Wavailable和Tavailable代入最大權(quán)重匈牙利算法，求出WT和最大得分Score

9. ifalgorithm=U-BasicthenWT=WTfinal

10. else ifalgorithm=U-CDPthen

11. else ifalgorithm=U-LLEPthen

使用CPLEX求解器找到當(dāng)前的最終解WTfinal，更新工人信息，Wothers←w。

圖2為 MSAU分配實(shí)例示意圖。在圖2的實(shí)例中，產(chǎn)生符合定義4與定義5的分配結(jié)果。當(dāng)滿足效用值閾值且技能屬性相同，即Skillw=Skillt∧p>0.4時(shí)，Score=3的分配對(duì)有〈w1,t1〉；當(dāng)滿足效用值閾值但技能屬性不同，即Skillw≠Skillt∧p>0.4時(shí)，Score=1的分配對(duì)有〈w3,t1〉、〈w4,t2〉；當(dāng)不滿足效用值閾值或工人任務(wù)不在范圍區(qū)域R內(nèi)，即xij=1∧p<0.4時(shí)，Score=0的分配對(duì)有〈w2,t1〉、〈w2,t2〉、〈w4,t1〉。

圖2 MSAU分配實(shí)例示意圖

2.2.2三種分配策略 本文提出帶有效用的、時(shí)間復(fù)雜度為O(n3)的基本方法(U-Basic)。U-Basic方法意在每個(gè)時(shí)間片上進(jìn)行任務(wù)最大分配，同時(shí)實(shí)現(xiàn)最大完成數(shù)量分配的目標(biāo)，并將此稱為MSAU實(shí)例問(wèn)題。解決MSAU實(shí)例問(wèn)題的思路是利用工人任務(wù)的約束，包括空間區(qū)域R、可接受任務(wù)的最大數(shù)量Tmax以及工人效用值uij來(lái)確保正確分配任務(wù)。若無(wú)約束，則可能會(huì)導(dǎo)致工人分配遠(yuǎn)距離任務(wù)以及無(wú)法高質(zhì)量完成任務(wù)等問(wèn)題。這意味著每個(gè)工人都愿意執(zhí)行R內(nèi)的最多Tmax任務(wù)，且只有滿足一定uij時(shí)方可算為分配成功。圖2(b)為圖2(a)當(dāng)Tmax=1時(shí)的對(duì)應(yīng)二分圖，工人w2在其范圍區(qū)域接受任務(wù)(t1,t2)，而w4可接受任務(wù)為t2。因此，有兩條邊連接w2，一條邊連接w4，虛線代表Score=0的情況。圖2(c)為圖2(b)的加權(quán)二分圖匹配，約束條件為T(mén)4max=2的w4被兩個(gè)具有T4max=1約束的w′4取代。由此可使用匈牙利算法進(jìn)行分配，Basic方法意在每個(gè)時(shí)間片上進(jìn)行任務(wù)最大分配，然而僅實(shí)現(xiàn)局部?jī)?yōu)化，如算法2中步驟9所示。因此，U-Basic方法僅能夠得到局部最優(yōu)解，MSAU在每個(gè)時(shí)間片不一定會(huì)得到全局最優(yōu)答案。

為了改進(jìn)基本策略，提出帶有效用的最小位置熵方法(U-LLEP)和帶有效用的近距離優(yōu)先方法(U-CDP)。位置熵考慮了該任務(wù)所在位置的工人總數(shù)，以及工人們未來(lái)訪問(wèn)該位置的相對(duì)比例。如果工人們以相同的速率訪問(wèn)某位置，則該位置的熵較高，反之則較低。因此，將位置熵較小區(qū)域中的任務(wù)給予更高的優(yōu)先級(jí)，那么這些任務(wù)被其他工人完成的可能性較低。在圖2(c)中，令Entropy(l2)為空間任務(wù)t2的位置熵。t2位于所有工人的空間區(qū)域中，因此將連接到t2的所有邊的成本設(shè)置為Entropy(l2)。U-LLEP問(wèn)題等價(jià)于解決每個(gè)時(shí)間片的最小成本問(wèn)題，首先使用匈牙利算法找到最大匹配項(xiàng)，然后使用CPLEX求解器解決此問(wèn)題，如算法2中步驟11所示。U-Basic和U-LLEP方法都試圖最大化任務(wù)分配數(shù)量，卻在分配過(guò)程中沒(méi)有考慮工人的差旅費(fèi)用(例如時(shí)間或距離)。

U-CDP的目標(biāo)是在每個(gè)時(shí)間片最大化任務(wù)分配數(shù)量的同時(shí)，盡可能地減少工人的差旅成本。實(shí)驗(yàn)中根據(jù)工人之間的歐氏距離，定義工人w和空間任務(wù)t之間的旅行成本d(w,t)，通過(guò)計(jì)算每個(gè)工人與其區(qū)域內(nèi)空間任務(wù)之間的距離，將較高的優(yōu)先級(jí)與較接近的任務(wù)相關(guān)聯(lián)。于是，該問(wèn)題演變?yōu)樽畹统杀镜腗SAU實(shí)例問(wèn)題，如算法2中步驟10所示。

3 實(shí)驗(yàn)部分

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

實(shí)驗(yàn)的兩個(gè)階段分別采用MovieLens和Gowalla數(shù)據(jù)集。MovieLens數(shù)據(jù)集(https:∥movielens.org)包括電影推薦服務(wù)的5星評(píng)級(jí)和自由文本標(biāo)記活動(dòng)，包含9 742部電影的100 836個(gè)評(píng)級(jí)和3 683個(gè)標(biāo)簽應(yīng)用程序，這些數(shù)據(jù)由610位用戶在1996年3月29日到2018年9月24日之間創(chuàng)建。該數(shù)據(jù)集于2018年9月26日生成，信息包括用戶與電影屬性以及影評(píng)記錄。本實(shí)驗(yàn)利用MovieLens數(shù)據(jù)集9 826個(gè)任務(wù)信息、1 297個(gè)工人信息和100 005個(gè)歷史信息進(jìn)行計(jì)算，并將α設(shè)定為0.1。Gowalla是一個(gè)基于位置的社交網(wǎng)絡(luò)，用戶可以在其中登錄附近的不同地點(diǎn)，簽入包括用戶地點(diǎn)的位置和時(shí)間，所用數(shù)據(jù)集包含了2009年2月至2010年10月之間的6 442 890條記錄數(shù)據(jù)，信息包括工人id以及打卡經(jīng)緯度與時(shí)間。實(shí)驗(yàn)假設(shè)用戶是SC系統(tǒng)的工人，簽到某個(gè)位置等效于在該位置接受空間任務(wù)。利用MovieLens數(shù)據(jù)集為用戶推薦電影映射SC背景下的任務(wù)尋找工人；利用Gowalla數(shù)據(jù)集為工人、任務(wù)隨機(jī)分配經(jīng)緯度，完成實(shí)驗(yàn)第一階段的工人效用值評(píng)估以及第二階段的任務(wù)分配。

3.2 實(shí)驗(yàn)內(nèi)容

工人聚類時(shí)，利用歐氏距離計(jì)算工人相似度。任務(wù)聚類時(shí)，利用輪廓系數(shù)si衡量聚類結(jié)果，K-means聚類結(jié)果示意圖如圖3所示。采用不同的特征提取進(jìn)行聚類，選擇c1特征提取結(jié)果，通過(guò)尋找較大的si，可以得到合適的k值如7、22、27、32等(每次運(yùn)行時(shí)稍微不同)。在本文實(shí)驗(yàn)中，選擇k=7。將聚類后的結(jié)果應(yīng)用于MAB算法，首先計(jì)算簇間效用值，然后選擇Top-1工人簇i進(jìn)行工人與任務(wù)的一對(duì)一計(jì)算，最后輸出工人效用值，并給予更新。

圖3 K-means聚類結(jié)果示意圖

特征矩陣X(xij∈X)用來(lái)表示工人對(duì)任務(wù)的偏好程度，用工人簇與任務(wù)簇?cái)?shù)據(jù)構(gòu)造，其中xij=nij，nij表示在歷史記錄數(shù)據(jù)中工人簇i(i∈kw)曾訪問(wèn)任務(wù)簇j(j∈kt)的數(shù)目，kw、kt分別表示工人簇和任務(wù)簇的數(shù)量。為了減少奇異數(shù)據(jù)對(duì)實(shí)驗(yàn)效果的影響，對(duì)矩陣X進(jìn)行了歸一化處理。

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

設(shè)置p=0.4，表1列出了6個(gè)評(píng)價(jià)指標(biāo)(總分配任務(wù)數(shù)、精確匹配任務(wù)數(shù)、精確匹配占比、任務(wù)總完成數(shù)、總完成占比和總距離)在使用效用值(表中用“使用uij”代替)和不使用效用值(表中用“未使用uij”代替)時(shí)的實(shí)驗(yàn)結(jié)果。

表1 不同評(píng)價(jià)指標(biāo)的實(shí)驗(yàn)結(jié)果

從表1可以看出，加入uij后，對(duì)于總分配任務(wù)數(shù)評(píng)價(jià)指標(biāo)，U-CDP和U-LLEP方法展現(xiàn)出明顯優(yōu)勢(shì)且彼此相差不大。而對(duì)于精確匹配任務(wù)數(shù)評(píng)價(jià)指標(biāo)，U-LLEP和U-CDP方法均優(yōu)于U-Basic方法。在總距離評(píng)價(jià)指標(biāo)方面，U-CDP方法最佳。對(duì)于沒(méi)有使用uij的原實(shí)驗(yàn)，在精確匹配數(shù)量方面LLEP方法最優(yōu)；在距離方面CDP方法最佳。這表明加入uij的實(shí)驗(yàn)并不會(huì)對(duì)分配策略的結(jié)果有太大影響。

加入uij后，U-CDP和U-LLEP方法的評(píng)價(jià)指標(biāo)如總分配任務(wù)數(shù)、精確匹配任務(wù)數(shù)和任務(wù)總完成數(shù)都較不考慮uij的情況有大幅度提升。對(duì)于U-CDP和U-LLEP方法，總分配任務(wù)數(shù)的增幅大于40%，精確匹配任務(wù)數(shù)的增幅大于60%。U-CDP方法的精確匹配占比增加11.70%，U-LLEP方法增加8.00%。U-Basic與U-CDP方法的任務(wù)總完成數(shù)約為原實(shí)驗(yàn)的5倍，U-LLEP方法約為原實(shí)驗(yàn)的4倍；同樣，U-Basic、U-CDP、U-LLEP方法的總完成占比分別增加約25%、13%、17%。說(shuō)明當(dāng)考慮了uij后，系統(tǒng)將任務(wù)分配給具有相對(duì)更高質(zhì)量的工人，既保證了分配的數(shù)量又保證了分配的質(zhì)量。

4 小結(jié)

本文提出一個(gè)用于SC任務(wù)匹配的未知工人效用評(píng)估方法，基于具有上下文的MAB模型，并為老虎臂和玩家加入特征元素，使其更符合SC的問(wèn)題背景。在原有單純考慮任務(wù)分配解決MTA、MSA問(wèn)題的基礎(chǔ)上，做到事先評(píng)估工人質(zhì)量，得到工人效用值后，在真實(shí)數(shù)據(jù)集上分別采用三種策略進(jìn)行分配，并利用多項(xiàng)評(píng)價(jià)指標(biāo)進(jìn)行對(duì)比分析，驗(yàn)證了當(dāng)考慮工人質(zhì)量的情況下不僅可以保證分配質(zhì)量，也可以提高分配數(shù)量。同時(shí)，加入工人與任務(wù)的多種屬性，使用聚類方法增強(qiáng)了傳統(tǒng)MAB算法的擴(kuò)展性。但本文犧牲了部分距離來(lái)?yè)Q取更多的分配數(shù)目，在接下來(lái)的研究中將尋找合適的方法解決總路程問(wèn)題。此外，將會(huì)增加實(shí)驗(yàn)原始對(duì)偶框架與本文方法的對(duì)比實(shí)驗(yàn)，考慮增加新的評(píng)價(jià)標(biāo)準(zhǔn)如花銷與預(yù)算，尋找在預(yù)算有限條件下的最優(yōu)方法等。