考慮用戶時空行為的眾包任務推薦方法

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

遼寧工程技術大學 電子與信息工程學院，遼寧 葫蘆島125105

1 引言

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

目前如何將時空眾包任務合理分配給合適的眾包工人仍然是時空眾包領域的研究重點。Cheng 等人[4]將時空眾包系統分為兩類：工人的動機和分配模式。關于工人的動機有兩種類型：獎勵型和興趣型，獎勵型是通過報酬激勵工人完成任務（如滴滴打車、美團外賣），興趣型是靠工人的意愿和興趣主動完成任務。分配模型也有兩種模式：時空眾包工人主動選擇任務，時空眾包平臺分配任務給工人。

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

2 相關工作

手機等移動定位設備的快速普及推動了時空眾包技術的發展，各種基于空間位置的服務與人們的生活聯系越來越密切。時空眾包任務分配問題成為時空眾包領域研究的重點問題之一。

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

相比之下，本文針對興趣型時空眾包工人，提出了區分兩種不同工人數據的方法以及提高興趣型時空眾包工人任務完成率的方法，使時空眾包任務分配領域的研究更為完善。

3 解決方案

圖1 總體框架

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

4 興趣型數據與激勵型數據的區分

LBSN（基于位置的社會網絡）數據大多采用如表1的格式。

表1 LBSN數據格式

本文采用的數據集為Brightkite 和Gowalla 的用戶簽到記錄，在本文中，把用戶ID作為時空眾包工人id，簽到的地點即時空眾包任務的地點，簽到地點的經緯度值即時空眾包任務的經緯度值。一條簽到數據是指某一時間點某個時空眾包工人在某地完成某個時空眾包任務。

本文通過引入基尼系數（GC）[14]的網絡指標來區分興趣型時空眾包工人和激勵型時空眾包工人的數據。GC被用來衡量程度分布的不平等，在分析用戶行為時，可以用它來表示用戶隨機選擇的地點之間的期望度差，計算方法如下：

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

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

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

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

5 興趣點聚類

興趣點之間具有位置關系和社會關系，位置是興趣點的天然屬性，興趣點本身不具備社會屬性，但訪問興趣點的人具有社會聯系，因此使得興趣點也具有了社會屬性。

本文通過構建地理-社會關系模型，計算得到各個地點之間的地理-社會關系相關度，進而可以得到興趣點的相關度矩陣，在此基礎上采用DBSCAN 聚類算法進行興趣點聚類。

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

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

兩點間的社會距離計算公式如下：

這里：

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

ω∈[0，1]為可調系數，用來調整兩地點之間地理距離與社會距離所占的比例。

使用地理-社會關系的興趣點聚類方法，在考慮地點間地理距離遠近的同時，也考慮到了訪問地點的工人之間的社會聯系，用來預測興趣型時空眾包工人的時空行為。

6 基于馬爾可夫模型的眾包任務預測

本文針對興趣型時空眾包工人進行合理的時空眾包任務分配，意在通過發現興趣型時空眾包工人的時空行為規律，預測興趣型時空眾包工人在不同時間點可能偏好去的地點，從而分配與其偏好去的地點一致或鄰近的時空眾包任務，以此來提高興趣型時空眾包任務的完成率。

本文利用馬爾可夫模型，挖掘興趣型時空眾包工人的時空行為規律，預測其下一步要去的地點。

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

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

圖3 是利用高斯混合模型通過對名為Tom 的時空眾包工人的數據擬合出的其在一天之內的狀態轉移時間點的分布。

圖3 高斯混合分布

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

用戶在t 時刻轉移到地點pj的概率為用戶從所有可能的地點pi轉移至地點pj的概率之和：

接下來，選擇概率最大的地點作為用戶在時間tend時轉移到的位置：

算法描述如下：

輸入：

tnow：當前時間

tend：結束時間

pnow：當前位置

t=(t(0),t(1),… ,t(m))：m 個位置的狀態轉移時間點集合

Pnow：當前概率值，初值為1

過程：

For 0 ≤j ≤m

在t(j)中求取對于當前時間tnow的下一個狀態轉移時間點

P(X(t)=pj)=

Continue

Else：

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

(pj,tend,M,Pnow)

End

算法結束運行后，把時空眾包工人在下一個狀態轉移時間點可能到達的位置對應到各個位置的時空眾包任務，將不同地點的時空眾包任務按眾包工人最可能移動到的地點概率的降序排列，選擇其中的前五個時空眾包任務推薦給時空眾包工人，從而提高興趣型時空眾包任務的完成率。

7 效果與性能實驗分析

7.1 實驗數據

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

圖4 訓練集大小對眾包任務完成情況的影響

7.2 實驗設置

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

效果評價標準：

首先改變訓練集的大小，通過以連續的一個月、兩個月、三個月的連續數據作為訓練集，研究不同大小的訓練集對實驗結果的影響。

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

然后以每組的連續三個月的數據作為訓練集進行以下對比。

圖5顯示了三組興趣型眾包工人在一周7天的眾包任務完成率。可以發現周一到周五眾包工人的眾包任務完成率較高，而周末的眾包任務完成率較低，這可能是由于在休息日興趣型時空眾包工人的時空行為具有較高的多樣性，難以準確預測導致。

圖5 一周七天的任務完成率

還對這三組工人的任務完成率進行對比，研究本算法的穩定性。

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

圖6 三組工人的任務完成率

最后，對比其他推薦方法。這里選擇傳統協同過濾方法（Traditional Collaborative Filtering，TCF）、考慮用戶興趣與能力的眾包任務推薦方法[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）進行眾包任務完成率對比，由表2所示。可見本文所提出的TRSBA 方法的眾包任務完成率更高。

表2 不同方法的任務完成率對比

8 總結

本文針對興趣型時空眾包工人，提出了興趣型時空眾包工人與激勵型時空眾包工人數據的區分方法，同時通過預測興趣型時空眾包工人下一狀態轉移時間點的位置，并把預測得出的概率最大的前五條工人可能移動到的位置的時空眾包任務按順序推薦給時空眾包工人，提出了對興趣型時空眾包工人的任務分配方法，且完成率在53%左右。在今后的工作中，將嘗試加入一些約束條件，如在一定時間內的時空眾包任務完成率等來使方法更加完善。