趙澤祺，孟祥福，毛 月，趙路路

遼寧工程技術(shù)大學(xué) 電子與信息工程學(xué)院，遼寧 葫蘆島125105

1 引言

隨著智能移動(dòng)設(shè)備的普及，人們能夠很輕松地參與一些基于位置的任務(wù)，例如監(jiān)控交通狀況、收集地點(diǎn)信息（百度地圖），檢查附近商家的商品貨架（Gigwalk）等。伴隨著這些現(xiàn)象的出現(xiàn)，時(shí)空眾包技術(shù)[1-2]應(yīng)運(yùn)而生。不像傳統(tǒng)的眾包方式，人們可以在線[3]完成眾包任務(wù)。時(shí)空眾包要求用戶（即眾包工人）在線下完成基于位置的時(shí)空眾包任務(wù)（如美團(tuán)送餐、在微信朋友圈發(fā)布某一時(shí)刻所見所聞等）。

目前如何將時(shí)空眾包任務(wù)合理分配給合適的眾包工人仍然是時(shí)空眾包領(lǐng)域的研究重點(diǎn)。Cheng 等人[4]將時(shí)空眾包系統(tǒng)分為兩類：工人的動(dòng)機(jī)和分配模式。關(guān)于工人的動(dòng)機(jī)有兩種類型：獎(jiǎng)勵(lì)型和興趣型，獎(jiǎng)勵(lì)型是通過報(bào)酬激勵(lì)工人完成任務(wù)（如滴滴打車、美團(tuán)外賣），興趣型是靠工人的意愿和興趣主動(dòng)完成任務(wù)。分配模型也有兩種模式：時(shí)空眾包工人主動(dòng)選擇任務(wù)，時(shí)空眾包平臺(tái)分配任務(wù)給工人。

在很多情況下，時(shí)空眾包工人不僅僅指那些依靠完成時(shí)空眾包任務(wù)獲取報(bào)酬的專職人員（如滴滴打車的司機(jī)，美團(tuán)外賣的送餐員等），根據(jù)人們的日?；顒?dòng)，人們無形中就成為了時(shí)空眾包工人。例如，在用戶使用高德地圖進(jìn)行導(dǎo)航的同時(shí)，高德地圖通過用戶的位置和移動(dòng)速度來獲取實(shí)時(shí)的路況信息，進(jìn)而更新某個(gè)時(shí)段的交通狀況。人們在出行的同時(shí)，完成了高德地圖的時(shí)空眾包任務(wù)，無形中成為了時(shí)空眾包工人。對(duì)于此類時(shí)空眾包模式，由于興趣型時(shí)空眾包工人不受實(shí)質(zhì)性獎(jiǎng)勵(lì)等條件的約束，如何提高興趣型時(shí)空眾包工人的眾包任務(wù)完成率成為當(dāng)前亟待解決的問題。本文針對(duì)此類興趣型時(shí)空眾包工人，考慮到時(shí)空眾包任務(wù)能否順利被興趣型工人完成主要取決于工人的時(shí)空行為和興趣偏好，本文提出了一種基于用戶時(shí)空行為分析的時(shí)空眾包任務(wù)推薦方法，在時(shí)間t1之前就預(yù)測到某眾包工人A1在時(shí)間t1時(shí)會(huì)到達(dá)地點(diǎn)P1，在t1之前給該眾包工人推薦需要在t1時(shí)刻完成的位于地點(diǎn)P1的時(shí)空眾包任務(wù)，從而有效提高興趣型時(shí)空眾包工人的眾包任務(wù)完成率。

2 相關(guān)工作

手機(jī)等移動(dòng)定位設(shè)備的快速普及推動(dòng)了時(shí)空眾包技術(shù)的發(fā)展，各種基于空間位置的服務(wù)與人們的生活聯(lián)系越來越密切。時(shí)空眾包任務(wù)分配問題成為時(shí)空眾包領(lǐng)域研究的重點(diǎn)問題之一。

在以往的時(shí)空眾包任務(wù)分配問題的研究中：Tong等人[5]針對(duì)出租車平臺(tái)，提出了LinUOTD模型用來預(yù)測單位時(shí)間和單位區(qū)域的出租車呼叫需求數(shù)量；Cheng 等人[6]考慮到了時(shí)空眾包任務(wù)的多樣性，提出了三種有效的近似方法，分別是貪婪算法、抽樣算法和分治算法；Deng 等人[7]提出了兩種基于動(dòng)態(tài)規(guī)劃和分枝定界策略的精確算法，來最大化時(shí)空眾包工人自主選擇任務(wù)的數(shù)量；Deng 等人[8]針對(duì)多個(gè)時(shí)空眾包工人任務(wù)分配問題，提出了一個(gè)基于二分法框架的算法；Tong 等人[9]對(duì)所有針對(duì)時(shí)空眾包任務(wù)最優(yōu)分配的算法進(jìn)行了統(tǒng)一實(shí)現(xiàn)并明確了各個(gè)算法的優(yōu)缺點(diǎn)；李洋等[10]提出了運(yùn)用樹分解算法解決帶有最晚時(shí)間約束的眾包工人的時(shí)空眾包任務(wù)分配問題；Song等[11]研究了動(dòng)態(tài)實(shí)時(shí)的時(shí)空眾包分配問題。然而，這些時(shí)空眾包分配算法的研究都是針對(duì)獎(jiǎng)勵(lì)型的時(shí)空眾包工人，都是在時(shí)空眾包工人有報(bào)酬獎(jiǎng)勵(lì)的約束情況下，一定接受時(shí)空眾包任務(wù)的基礎(chǔ)上尋找更加高效的時(shí)空眾包任務(wù)分配方法。忽視了那些沒有獎(jiǎng)勵(lì)約束，有選擇完成眾包任務(wù)的興趣型時(shí)空眾包工人的眾包任務(wù)分配。

相比之下，本文針對(duì)興趣型時(shí)空眾包工人，提出了區(qū)分兩種不同工人數(shù)據(jù)的方法以及提高興趣型時(shí)空眾包工人任務(wù)完成率的方法，使時(shí)空眾包任務(wù)分配領(lǐng)域的研究更為完善。

3 解決方案

圖1 總體框架

圖1 為總體解決方案。首先，在數(shù)據(jù)集的處理方面，本文提出了一種有效區(qū)分興趣型時(shí)空眾包工人與激勵(lì)型時(shí)空眾包工人數(shù)據(jù)的方法，能夠較為準(zhǔn)確地篩選出興趣型時(shí)空眾包工人的數(shù)據(jù)，為接下來針對(duì)興趣型時(shí)空眾包工人的推薦方法提供可靠數(shù)據(jù)集。然后，構(gòu)建地理-社會(huì)關(guān)系模型[12]，在考慮各個(gè)地點(diǎn)間地理距離遠(yuǎn)近的同時(shí)，考慮各地點(diǎn)間的社會(huì)距離，計(jì)算地點(diǎn)間的地理-社會(huì)相關(guān)度，采用DBSCAN 聚類算法把相關(guān)度較高的地點(diǎn)聚為一類，使聚類結(jié)果更加符合實(shí)際。接下來利用高斯混合模型[13]找到時(shí)空眾包工人可能移動(dòng)的時(shí)間點(diǎn)，以這些時(shí)間點(diǎn)作為狀態(tài)轉(zhuǎn)移點(diǎn)，建立馬爾可夫模型，預(yù)測眾包工人在這一時(shí)間點(diǎn)可能移動(dòng)的各個(gè)地點(diǎn)，用概率表示。在預(yù)測興趣型工人的時(shí)空行為這一步中，本推薦方法既考慮了工人最可能發(fā)生狀態(tài)轉(zhuǎn)移的時(shí)間，又考慮到了工人在不同轉(zhuǎn)移時(shí)間點(diǎn)所要到達(dá)的位置，有效地提高了預(yù)測興趣型眾包工人的時(shí)空行為的準(zhǔn)確率。最后，把位于臨近工人狀態(tài)轉(zhuǎn)移時(shí)間點(diǎn)的這些位置的時(shí)空眾包任務(wù)，按概率由大到小的順序發(fā)送給用戶，由用戶選擇執(zhí)行的眾包任務(wù)。

4 興趣型數(shù)據(jù)與激勵(lì)型數(shù)據(jù)的區(qū)分

LBSN（基于位置的社會(huì)網(wǎng)絡(luò)）數(shù)據(jù)大多采用如表1的格式。

表1 LBSN數(shù)據(jù)格式

本文采用的數(shù)據(jù)集為Brightkite 和Gowalla 的用戶簽到記錄，在本文中，把用戶ID作為時(shí)空眾包工人id，簽到的地點(diǎn)即時(shí)空眾包任務(wù)的地點(diǎn)，簽到地點(diǎn)的經(jīng)緯度值即時(shí)空眾包任務(wù)的經(jīng)緯度值。一條簽到數(shù)據(jù)是指某一時(shí)間點(diǎn)某個(gè)時(shí)空眾包工人在某地完成某個(gè)時(shí)空眾包任務(wù)。

本文通過引入基尼系數(shù)（GC）[14]的網(wǎng)絡(luò)指標(biāo)來區(qū)分興趣型時(shí)空眾包工人和激勵(lì)型時(shí)空眾包工人的數(shù)據(jù)。GC被用來衡量程度分布的不平等，在分析用戶行為時(shí)，可以用它來表示用戶隨機(jī)選擇的地點(diǎn)之間的期望度差，計(jì)算方法如下：

這里n 為總的地點(diǎn)數(shù)，xi為時(shí)空眾包工人完成在地點(diǎn)i的時(shí)空眾包任務(wù)的次數(shù)，xˉ為時(shí)空眾包工人完成各個(gè)地點(diǎn)的時(shí)空眾包任務(wù)的次數(shù)的均值，有興趣偏好的興趣型時(shí)空眾包工人的GC很高。

來看一個(gè)例子。圖2 顯示了兩個(gè)具有不同GC 的時(shí)空眾包工人，分析A 和B 的時(shí)空行為可知，A 工人所完成的時(shí)空眾包任務(wù)無明顯的興趣偏好，屬于激勵(lì)型時(shí)空眾包工人。B 工人完成的時(shí)空眾包任務(wù)有明顯的興趣偏好，也就是說某些地點(diǎn)的訪問次數(shù)比較頻繁，屬于興趣型時(shí)空眾包工人。

圖2 兩種不同類型工人的GC

根據(jù)公式（1），GC 越趨近于1 的時(shí)空眾包工人的時(shí)空行為越具有明顯的興趣偏好，是屬于興趣型的時(shí)空眾包工人；GC 越趨近于0，說明該時(shí)空眾包工人的行為沒有明顯的偏好，屬于激勵(lì)型時(shí)空眾包工人。

5 興趣點(diǎn)聚類

興趣點(diǎn)之間具有位置關(guān)系和社會(huì)關(guān)系，位置是興趣點(diǎn)的天然屬性，興趣點(diǎn)本身不具備社會(huì)屬性，但訪問興趣點(diǎn)的人具有社會(huì)聯(lián)系，因此使得興趣點(diǎn)也具有了社會(huì)屬性。

本文通過構(gòu)建地理-社會(huì)關(guān)系模型，計(jì)算得到各個(gè)地點(diǎn)之間的地理-社會(huì)關(guān)系相關(guān)度，進(jìn)而可以得到興趣點(diǎn)的相關(guān)度矩陣，在此基礎(chǔ)上采用DBSCAN 聚類算法進(jìn)行興趣點(diǎn)聚類。

設(shè)P 為所有地點(diǎn)的集合，U 為所有用戶的集合，E為所有用戶之間關(guān)系的集合，ua，ub具有朋友關(guān)系，即表示為(ua,ub)∈E，pi與pj為需要計(jì)算地理-社會(huì)關(guān)系距離的兩個(gè)地點(diǎn)，這兩點(diǎn)的地理距離的計(jì)算公式如下：

其中，E(pi,pj)為pi和pj兩點(diǎn)的歐氏距離，maxD 是P 集合中任意兩地點(diǎn)間的最大歐式距離。

兩點(diǎn)間的社會(huì)距離計(jì)算公式如下：

這里：

pi與pj的地理-社會(huì)距離可由下式得出：

ω∈[0，1]為可調(diào)系數(shù)，用來調(diào)整兩地點(diǎn)之間地理距離與社會(huì)距離所占的比例。

使用地理-社會(huì)關(guān)系的興趣點(diǎn)聚類方法，在考慮地點(diǎn)間地理距離遠(yuǎn)近的同時(shí)，也考慮到了訪問地點(diǎn)的工人之間的社會(huì)聯(lián)系，用來預(yù)測興趣型時(shí)空眾包工人的時(shí)空行為。

6 基于馬爾可夫模型的眾包任務(wù)預(yù)測

本文針對(duì)興趣型時(shí)空眾包工人進(jìn)行合理的時(shí)空眾包任務(wù)分配，意在通過發(fā)現(xiàn)興趣型時(shí)空眾包工人的時(shí)空行為規(guī)律，預(yù)測興趣型時(shí)空眾包工人在不同時(shí)間點(diǎn)可能偏好去的地點(diǎn)，從而分配與其偏好去的地點(diǎn)一致或鄰近的時(shí)空眾包任務(wù)，以此來提高興趣型時(shí)空眾包任務(wù)的完成率。

本文利用馬爾可夫模型，挖掘興趣型時(shí)空眾包工人的時(shí)空行為規(guī)律，預(yù)測其下一步要去的地點(diǎn)。

用馬爾可夫模型來進(jìn)行位置的預(yù)測時(shí)，需要有用戶的狀態(tài)轉(zhuǎn)移時(shí)間點(diǎn)，現(xiàn)有的馬爾可夫模型都是以固定的時(shí)間間隔來選取用戶的轉(zhuǎn)移時(shí)間點(diǎn)；而實(shí)際上，用戶在不同地點(diǎn)的停留時(shí)間往往不同，比如生活有規(guī)律的上班族在工作日時(shí)，在公司停留的時(shí)間比在商場和超市停留的時(shí)間久，狀態(tài)轉(zhuǎn)移時(shí)間點(diǎn)的時(shí)間間隔有所不同。因此在選取狀態(tài)轉(zhuǎn)移時(shí)間點(diǎn)時(shí)引入高斯混合模型，計(jì)算出用戶在各個(gè)時(shí)間點(diǎn)t 可能從位置pi轉(zhuǎn)移到pj的概率：

這里，μn為第n個(gè)高斯分布的期望，Lij(t|μn,σn)為高斯混合模型中第n 個(gè)分量，πn為第n 個(gè)分量的權(quán)重，取轉(zhuǎn)移概率最大的時(shí)間點(diǎn)作為用戶的一個(gè)狀態(tài)轉(zhuǎn)移時(shí)間點(diǎn)t。

圖3 是利用高斯混合模型通過對(duì)名為Tom 的時(shí)空眾包工人的數(shù)據(jù)擬合出的其在一天之內(nèi)的狀態(tài)轉(zhuǎn)移時(shí)間點(diǎn)的分布。

圖3 高斯混合分布

假定用戶移動(dòng)到一個(gè)地點(diǎn)pj的概率只受其上一個(gè)位置pi和在t 時(shí)間點(diǎn)的轉(zhuǎn)移概率P(t|pi→pj)影響，X(t)為t 時(shí)刻用戶所在的地點(diǎn)，則用戶在t 時(shí)刻離開pi轉(zhuǎn)移到pj的概率為：

用戶在t 時(shí)刻轉(zhuǎn)移到地點(diǎn)pj的概率為用戶從所有可能的地點(diǎn)pi轉(zhuǎn)移至地點(diǎn)pj的概率之和：

接下來，選擇概率最大的地點(diǎn)作為用戶在時(shí)間tend時(shí)轉(zhuǎn)移到的位置：

算法描述如下：

輸入：

tnow：當(dāng)前時(shí)間

tend：結(jié)束時(shí)間

pnow：當(dāng)前位置

t=(t(0),t(1),… ,t(m))：m 個(gè)位置的狀態(tài)轉(zhuǎn)移時(shí)間點(diǎn)集合

Pnow：當(dāng)前概率值，初值為1

過程：

For 0 ≤j ≤m

在t(j)中求取對(duì)于當(dāng)前時(shí)間tnow的下一個(gè)狀態(tài)轉(zhuǎn)移時(shí)間點(diǎn)

P(X(t)=pj)=

Continue

Else：

Pnow=P(X(tnow)=pnow)×P(→pj)

(pj,tend,M,Pnow)

End

算法結(jié)束運(yùn)行后，把時(shí)空眾包工人在下一個(gè)狀態(tài)轉(zhuǎn)移時(shí)間點(diǎn)可能到達(dá)的位置對(duì)應(yīng)到各個(gè)位置的時(shí)空眾包任務(wù)，將不同地點(diǎn)的時(shí)空眾包任務(wù)按眾包工人最可能移動(dòng)到的地點(diǎn)概率的降序排列，選擇其中的前五個(gè)時(shí)空眾包任務(wù)推薦給時(shí)空眾包工人，從而提高興趣型時(shí)空眾包任務(wù)的完成率。

7 效果與性能實(shí)驗(yàn)分析

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

本文采用的數(shù)據(jù)集為Brightkite 和Gowalla 2009 年5月到2010年12月用戶的簽到數(shù)據(jù)，由于數(shù)據(jù)中用戶簽到的地點(diǎn)太過廣泛，本實(shí)驗(yàn)選擇紐約市的時(shí)空眾包工人作為實(shí)驗(yàn)對(duì)象，并且刪除簽到數(shù)據(jù)不足10 次的用戶信息和被訪問次數(shù)少于10 次的地點(diǎn)信息，經(jīng)過GC 篩選后得到的興趣型時(shí)空眾包工人的數(shù)據(jù)有37 925條，經(jīng)過地理-社會(huì)關(guān)系的聚類方法聚類后得到的時(shí)空眾包任務(wù)的位置有946個(gè)，興趣型時(shí)空眾包工人有597名。

圖4 訓(xùn)練集大小對(duì)眾包任務(wù)完成情況的影響

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

本文的實(shí)驗(yàn)把597 名用戶分成三組，每組199 名用戶，每一組分別以他們連續(xù)的數(shù)據(jù)作為訓(xùn)練集，以之后相鄰的7 天的數(shù)據(jù)作為測試集。對(duì)不同工人的時(shí)空眾包任務(wù)完成情況進(jìn)行驗(yàn)證。

效果評(píng)價(jià)標(biāo)準(zhǔn)：

首先改變訓(xùn)練集的大小，通過以連續(xù)的一個(gè)月、兩個(gè)月、三個(gè)月的連續(xù)數(shù)據(jù)作為訓(xùn)練集，研究不同大小的訓(xùn)練集對(duì)實(shí)驗(yàn)結(jié)果的影響。

由圖4 可知訓(xùn)練集里的數(shù)據(jù)越詳細(xì)，越能更加準(zhǔn)確地了解時(shí)空眾包工人的興趣偏好，進(jìn)而較為準(zhǔn)確地預(yù)測時(shí)空眾包工人在下一時(shí)間轉(zhuǎn)移點(diǎn)的地理位置。但是隨著訓(xùn)練集的增大，在數(shù)據(jù)處理階段的時(shí)間也會(huì)同步增長，因此訓(xùn)練集的選擇也不宜過大，對(duì)于本實(shí)驗(yàn)所選取的數(shù)據(jù)集，以三個(gè)月的連續(xù)數(shù)據(jù)作為訓(xùn)練集最為合適。

然后以每組的連續(xù)三個(gè)月的數(shù)據(jù)作為訓(xùn)練集進(jìn)行以下對(duì)比。

圖5顯示了三組興趣型眾包工人在一周7天的眾包任務(wù)完成率?？梢园l(fā)現(xiàn)周一到周五眾包工人的眾包任務(wù)完成率較高，而周末的眾包任務(wù)完成率較低，這可能是由于在休息日興趣型時(shí)空眾包工人的時(shí)空行為具有較高的多樣性，難以準(zhǔn)確預(yù)測導(dǎo)致。

圖5 一周七天的任務(wù)完成率

還對(duì)這三組工人的任務(wù)完成率進(jìn)行對(duì)比，研究本算法的穩(wěn)定性。

由圖6 可以看出，三組興趣型時(shí)空眾包工人的平均任務(wù)完成率在53%左右，具有較高的完成率。

圖6 三組工人的任務(wù)完成率

最后，對(duì)比其他推薦方法。這里選擇傳統(tǒng)協(xié)同過濾方法（Traditional Collaborative Filtering，TCF）、考慮用戶興趣與能力的眾包任務(wù)推薦方法[15]（Task Recom‐mendation based on Interest and Competency of workers，TRIC）與本方法（crowdsourcing Task Recom‐mendation method based on user Spatiotemporal Behav‐ior Analysis，TRSBA）進(jìn)行眾包任務(wù)完成率對(duì)比，由表2所示。可見本文所提出的TRSBA 方法的眾包任務(wù)完成率更高。

表2 不同方法的任務(wù)完成率對(duì)比

8 總結(jié)

本文針對(duì)興趣型時(shí)空眾包工人，提出了興趣型時(shí)空眾包工人與激勵(lì)型時(shí)空眾包工人數(shù)據(jù)的區(qū)分方法，同時(shí)通過預(yù)測興趣型時(shí)空眾包工人下一狀態(tài)轉(zhuǎn)移時(shí)間點(diǎn)的位置，并把預(yù)測得出的概率最大的前五條工人可能移動(dòng)到的位置的時(shí)空眾包任務(wù)按順序推薦給時(shí)空眾包工人，提出了對(duì)興趣型時(shí)空眾包工人的任務(wù)分配方法，且完成率在53%左右。在今后的工作中，將嘗試加入一些約束條件，如在一定時(shí)間內(nèi)的時(shí)空眾包任務(wù)完成率等來使方法更加完善。