移動情景和用戶軌跡感知的眾包服務推薦*

姜 蕓，何 偉+，崔立真，楊 倩，劉 磊

1.山東大學 軟件學院，濟南 250101

2.山東省軟件工程重點實驗室，濟南 250101

1 引言

隨著無線通信技術和移動智能終端的快速發展，基于位置的服務（location-based service，LBS）[1]以其移動性、實用性、便攜性等獨有的特點，可以隨時隨地獲取移動網絡服務和信息內容，在諸多領域得到廣泛應用。所謂基于位置服務，指通過移動終端和無線或衛星通信網絡的配合,確定出移動用戶的實際地理位置,從而提供用戶需要的與位置相關的信息服務，例如地圖導航、物流跟蹤、交通監測、移動眾包任務推薦等。然而移動互聯網服務和信息傳遞頗受上下文信息、移動社會化網絡的影響，如何從浩瀚的移動信息海洋中發現用戶感興趣的服務，提升用戶個性化服務體驗，成為移動推薦系統亟待解決的難題。

與傳統互聯網用戶相比,移動通信網中,用戶的最大特征是用戶位置隨時間的隨機性變動,正是這種位置的變動性,才使得基于移動用戶不同位置的服務推薦成為可能。移動眾包服務中最核心的是眾包任務推薦，其旨在將時空任務推送給一個工人集合[2-4]，工人以各自獨立或相互協作的方式完成同一個任務（例如，拍照/拍視頻或者到指定地點簽到），同時滿足任務的時間、位置等約束[5-6]。在移動眾包應用場景中，眾包任務推薦面臨著兩個重要的挑戰：

第一個挑戰是移動用戶行程軌跡及其意圖的不確定性。眾包模式下任務的執行者是互聯網上的非特定人群，任務的接受和執行遵循自愿的原則，由用戶根據自身興趣或意圖自行決定而無法強制，進行任務推薦的時候需要充分考慮每個潛在用戶的軌跡變化、行為意圖以及各種移動情景對他們的影響，盡可能使移動任務與用戶的意愿相匹配，以提高任務推薦的成功率和他們對服務推薦的滿意程度。

第二個挑戰在于移動眾包服務場景的動態性。例如出租車、外賣等O2O 服務，無論是任務發布者，還是潛在的執行者都在不斷涌現，或者隨時退出，并且其位置、軌跡也處于動態變化之中，這些對時空任務推薦算法的實時有效性、動態場景適應能力都提出了更高的要求。

目前給用戶推薦任務的策略主要是基于移動用戶的當前（任務分配時刻）位置，為用戶推送時空任務或給他規劃一個任務執行路線，而較少關注用戶自身的軌跡及其位置變化趨勢，有可能由于推薦給他的任務偏離其軌跡方向、行為意圖等而拒絕接受這一任務，進而導致時空任務推薦的成功率低。

本文受工人歷史軌跡數據可以提供很多有意義信息的啟發，從中分析出某個用戶的移動軌跡模式、行為習慣、對于某些地點的偏好等；然后基于該分析，對用戶的移動位置區域進行預測；再將預測之后區域內的任務推送給他，這將會提高用戶接受任務的概率，同時降低額外的旅行費用、時間等成本。

本文的主要貢獻如下：

（1）首先將離散的位置點聚類成區域，然后對用戶的區域移動軌跡進行挖掘，利用移動模式集來描述特定用戶在不同移動情景下的軌跡變化。

（2）在用戶移動模式集的基礎上，構建移動規則，并提出預測工人位置區域的方法，將區域內的眾包任務推送給他。

（3）在真實數據集上進行實驗，驗證了本文提出的不同移動情景下用戶位置預測算法任務推薦策略的有效性和準確性。

本文的其余部分組織如下：第2章講述其他人的相關工作；第3 章介紹相關定義；第4 章提出本文的方法，講述具體的算法和例子；第5 章介紹任務推薦方法；第6章展示實驗結果；第7章給出本文的結論。

2 相關工作

隨著互聯網移動通信技術的發展以及智能終端的廣泛使用，很多研究人員把注意力集中到對歷史軌跡數據的分析和挖掘，也因此產生了很多與空間位置有關的研究成果[7-10]。但是，絕大多數是集中在如何具體分析移動對象的歷史軌跡，并從中發現有意義的信息，而對于位置預測技術的研究相對較少。Jeung和Liu等人[11]提出了一種新穎的方法，該方法結合預先定義好的運動公式來預測用戶的下一個位置。預定義的運動程式通過利用復雜的數學公式和Apriori算法從用戶軌跡中提取出頻繁移動模式來捕捉移動對象的移動行為。他們使用的運動程式可以是線性的模型，也可以是非線性的模型。該方法時間開銷巨大，計算量巨大。Morzy 利用改進版的Apriori算法來生成關聯規則[12]，在他后來的研究中又利用改進后的Prefix Span 算法來發現用戶頻繁的移動模式，然后利用找出的頻繁模式來生成預測規則[13]。盡管Morzy 的所有方法都有考慮時間信息和經緯度表示的地理位置信息，但是它們沒有考慮地理位置中隱含的語義信息。

本文對文獻[14]提出的位置預測方法進行改進，在預測移動模式生成中加入了上下文影響因素，例如考慮到周末/節假日和工作日的用戶移動行為的區別，并根據上下文相關的移動模式分別提取移動規則從而提高預測的準確性。

3 問題定義

本文方法的基本思路是通過挖掘移動用戶軌跡模式來預測用戶將要到達的位置區域，然后將區域內的任務推薦給工人，以提高工人成功接受任務的概率。為了方便理解，介紹本文方法的相關定義。

定義1（區域（region,r））區域r表示地理位置范圍，是對該移動用戶和時空任務物理坐標的聚合，在本文中使用編號來表示。例如，萬達廣場商圈可以作為一個區域r。

定義2（實際路線（worker actual path，WAP））工人實際路線WAP 定義為Wap(w)=<(r1,t1),(r2,t2),…,(rn,tn)>，其中(ri,ti)表示工人w在時間為ti的時候到達了區域ri，ri是區域編號。一條路線表示工人w在一天內按時間先后依次去過的區域位置。

定義3（移動模式（worker mobile pattern，WMP））移動模式WMP也是工人的移動軌跡，在工人軌跡中出現比較頻繁，即表示工人經常去的地方，能夠很好地描述出工人的日常移動軌跡，表示為Wmp(w)=(<(r1,t1),(r2,t2),…,(rn,tn)>,supp),其 中 <(r1,t1),(r2,t2),…,(rn,tn)>同上述2 的路線定義，supp表示該路線基于工人w歷史軌跡出現的頻繁程度，叫作支持度，supp≥0。支持度的計算方式參考Apriori算法。

定義4（移動規則（worker mobile rule，WMR））一個移動規則WMR 描述了工人在各個區域之間的轉移關系，表示為Wmr=→,其中為規則頭部，表示工人的當前軌跡路線，為規則尾部，表示工人有最大概率將要去的區域。移動規則是根據移動模式(<(r1,t1),(r2,t2),…,(rk-1,tk-1),(rk,tk)>,supp)得到的，在一個工人移動模式中，他按照時間先后去過k個區域，前1,2,…,k-1 個區域都可以作為規則的頭部(k>1),那么相對應的剩下的k-1,k-2,…，1 個區域則作為預測的區域，移動規則集示例如下所示。

→

→

…

→

4 基于移動模式挖掘的工人位置預測

移動工人的位置區域預測及任務推薦過程包括四個階段：首先對離散的位置點進行聚類，得到區域，對工人的歷史區域移動軌跡進行挖掘，形成工人移動模式；根據獲得的工人移動模式構建出工人移動規則；通過實時感知到的工人位置信息和移動規則預測工人下一步將要到達的位置區域；最后根據預測為工人推薦時空任務。位置預測及任務推薦過程如圖1所示。

4.1 生成區域

假設本文中所有任務所在的位置能夠包含在這些區域內，使用最流行的聚類算法K-means 算法將位置點聚合成區域，實現點到區域的變換。K-means算法的步驟如下：

Fig.1 Location prediction and task recommendation process for mobile workers圖1 移動工人的位置預測及任務推薦過程圖

（1）隨機選擇K個初始質心；

（2）如果沒有滿足聚類算法終止條件，則繼續執行步驟（3），否則轉步驟（5）；

（3）計算每個非質心點p到k個質心的歐幾里德距離，將p指派給距離最近的質心；

（4）根據上一步的k個質心及其對應的非質心點集，重新計算新的質心點，然后轉步驟（2）；

（5）輸出聚類結果，算法可以執行多次，比較不同的聚類結果，選擇較好的結果。

通過K-means 算法對位置點聚類后，得到區域，進一步將其形式化為有向圖G。圖2 是實際區域圖的例子，圖3 為區域網絡有向圖，雙向箭頭代表兩個區域之間可以直接到達。

4.2 挖掘工人移動模式

本節詳細介紹如何挖掘工人移動模式，下面是詳細步驟。

Fig.2 Actual area map圖2 實際區域圖

Fig.3 Digraph of regional network圖3 區域網絡有向圖

已知工人實際路線多條，首先可以得到長度為1的候選模式集C1，即長度為1的子路徑，計算它們的支持度，大于本文設定的閾值1.33就加入到長度為1的移動模式集中，用L1表示；在L1中的區域，通過區域網絡有向圖觀察從當前區域能夠直接到達哪個區域，就將其區域編號加入到集合中，形成長度為2 的候選模式集C2；接著計算支持度，大于閾值的加到長度為2 的移動模式集L2中。根據這個規則，一直到找不到候選模式集為止，則移動模式集生成完畢。工人移動模式WMPMining()挖掘算法描述如算法1所示。

在移動情景方面，劃分工作日、周末，將分別產生其移動模式Lw和Lp。

算法1工人移動模式WMP挖掘WMPMining()

輸入：數據庫中的工人實際路線（WAP）D，最小支持度suppmin，網絡區域圖G。

輸出：工人移動模式（WMP）Lw、Lp。

為了說明CandidateGeneration()是如何工作的，假設存在一個長度為k用戶軌跡，C=<(r1,t1),(r2,t2),…,(rk,tk)>作為算法的輸入，考慮在區域網絡有向圖中，首先將從頂點rk出發所能到達的所有區域頂點加入到集合N+(rk)中去，這個集合中的區域頂點表示了工人從rk出發能夠到達的地方。然后，從N+(rk)中選擇某個頂點v，加入到候選序列中C′=<(r1,t1),(r2,t2),…,(rk,tk),(v,t)>，將C′加入到長度為k+1的候選序列中。表1給出了基于圖3區域網絡有向圖的工人歷史軌跡的例子。

假設支持度預先設定的閾值suppmin=1.33，根據表1中工人實際路線，通過WMPMining()算法挖掘用戶的移動模式集L，如表2 所示。為了方便閱讀，在表格展示中將時間省略了，但實際是將時間考慮在內的。

4.3 生成移動規則

在挖掘工人移動模式的基礎上，進行移動規則提取，由第3 章移動規則定義可知，假設工人移動模式WMP，L=<(r1,t1),(r2,t2),…,(rk,tk)>,k>1,其移動規則見第3章。

Table 1 Workers'actual path表1 工人實際路線

Table 2 Worker mobile patterns set L表2 工人移動模式集合L

對于一個規則R:→，給它定義一個置信度，用來表示該規則的可信程度，即預測的準確程度。置信度使用如下公式定義：

利用工人移動模式挖掘算法得到的WMP，可以生成所有可能的移動規則并計算出它們的置信度。如果一個規則的置信度高于預先設定的置信度閾值(coffmin)，就將它們選擇出來用于下一個區域預測階段。

由于移動模式是基于不同情景提取的（本文只考慮了工作日/節假日相關性），每個移動規則也需要增加不同情景標簽，來表明特定情景下的移動規則。

例如，根據表2 所示的移動模式集，生成移動規則并計算每個規則的置信度，假設置信度閾值(coffmin)為50%，則移動規則集合如表3 所示（WD 代表工作日，PD代表非工作日）。

4.4 工人區域預測

位置區域預測是最后一個階段，算法的偽代碼描述如下：

算法2位置區域預測MobilityPrediction()

輸入：用戶當前的移動軌跡P=<(r1,t1),(r2,t2),…,(ri-1,ti-1)>,移動規則集合R,預測的最大位置個數m。

輸出：預測區域集合PRegions。

Table 3 Mobile rule set表3 移動規則集

上述算法的預測過程可以概括如下：假設工人當前移動軌跡為P=<(r1,t1),(r2,t2),…,(ri-1,ti-1)>,首先尋找適合當前路徑的所有規則，將其歸納到匹配規則集中，匹配規則有如下特點：規則的頭部包含在當前移動軌跡中，相當于是它的子路徑，在匹配的時候，按照先匹配頭部與軌跡一模一樣的，然后逐漸降低規則頭部長度的原則去尋找。把移動規則集全部掃描一遍找到所有符合匹配規則特點的規則后，將每個規則尾部的第一個區域編號以及此規則的置信度組成一個元祖（r,confidence），并按照置信度的大小降序排序。算法中還定義了另一個參數m，作為可以預測的區域的數量，從數組中選擇前m個排序后的元組，意味著使用前m個匹配規則去預測工人的下一個位置。

由于生成移動規則時添加了情景標簽（即是否為工作日），進行掃描時先判斷當前時間與當前標簽內容是否一致，如果與規則標簽不符，直接跳過去掃描下一個規則，這將大大提高匹配效率。

5 移動眾包任務推薦

在移動眾包應用場景中，由于空間任務和工人的位置、數量都動態變化并實時更新，任務推薦的目標考慮在一段時間內，實現任務分配數量最大化的局部最優，本文基于文獻[11]的貪心策略進行任務推薦。給定一組工人Wi={w1,w2,…}和區域D內的一組任務Ti={t1,t2,…},目標是在一段時間內，將Ti中的任務推薦給Wi中的工人。本文假設所有工人的質量一致。

基于文獻[11]提出的策略，使用圖的最大流問題解決任務推薦問題。給定一組工人Wi={w1,w2,…}和多個區域Ri的任務Ti={t1,t2,…},Gi=(V,E)表示網絡圖的頂點和邊，其中包含|Wi|+|Ri|+|Ti|+2個頂點。每個工人wj對應一個頂點vj，每個區域rj映射到頂點，每個任務tj映射到頂點同時創建一個源點src和一個終點dest,Gi包含|Wi|+|Ri|+|Ti|+m條邊，其中|Wi|條邊為連接源點src和每個頂點vj，用(src,vj)表示，邊的權重為每個工人可接受的最大任務數；有|Ti|條邊連接任務Ti和終點dest，權重設為1，表示這個任務推薦給一個工人。

如圖4 所示，是區域任務分布圖，轉化為圖5 所示的流程網絡圖。圖4 中工人與區域之間的箭頭表示預測工人將要到達那個區域。圖4 中的w1、w2、w3、w4對應于圖5 的v1、v2、v3、v4,區域r1、r2、r3對應于圖5的v5、v6、v7,區域內的任務對應于v8至v16，基于上一章中所述算法對工人到達位置區域的預測，可以判斷出每個空間任務所推薦給的候選工人集合，接著將區域內的任務推薦給候選工人集合里的工人。通過求解圖最大流問題，比如Ford-Fulkerson算法[15]，解決上述任務推薦問題。

Fig.4 Distribution map of workers,region and task圖4 工人、區域、任務分布圖

Fig.5 Process network diagram圖5 流程網絡圖

6 實驗

6.1 數據整理

為了在現實環境下測試所提出的方法，本文使用了基于位置的社交網絡Gowalla的數據集，包括用戶時間和其地點的經緯度，以及地點的ID。簽到集包括了從2009 年至2010 年10 月期間收集的644 多萬條數據，對其進行清洗和處理，最后提取了有100萬條數據的數據集，其包含4 000 多個用戶和45 000個不同地點。數據集的地點和用戶分別用來代表空間的眾包任務和工人的位置，只要工人到指定地點簽到就看作是接受眾包任務并完成。雖然數據集不是直接來自空間的眾包，但它提供了不同的、現實世界的工人和任務位置的分布，由于本文研究的算法依賴于位置，使用這個數據集，能夠對它們的相對性能得出一些合理的結論。

數據集本身是一些用戶的簽到數據，相對來說比較稀疏，本文首先對提取的數據集進行處理，將損壞的、空白的對實驗沒有任何幫助的數據全都清除。數據清洗完之后，使用K-means 算法對其進行聚類,將離散的數據聚成多個區域，看成眾包任務的分布地點。

圖6 是對數據集聚類的結果，其中類別數為2 000，每個類別分別用不同顏色標出，每種顏色代表一個類，即一個區域。

Fig.6 Clustering region graph圖6 聚類區域圖

按照時間先后將每一個工人的軌跡路徑劃分為訓練集和測試集，其中訓練集用來獲得4.3節介紹的工人移動規則，測試集是用來測試通過移動規則預測的區域和工人真實要去的區域是否一致。如果一致，表明預測的工人即將要去的區域和眾包任務的分布區域是一樣的，就可以將區域內的任務推送給工人，即代表任務推薦成功，否則推薦失敗。

6.2 實驗評估

用success代表任務推薦的成功率，計算公式如下：

其中，match表示任務推薦成功的數量，all表示所有的任務數。

下面給出本文方法與Yava?等研究者[14]提出的預測方法的比較，根據測試集預測區域編號的準確率進行對比，如圖7、圖8所示。

Fig.7 Comparison of accuracy of WMP and UMP on workdays圖7 WMP、UMP在工作日的準確率比較

Fig.8 Comparison of accuracy of WMP and UMP on weekends圖8 WMP、UMP在非工作日的準確率比較

圖7、圖8 表明，隨著聚類類別數的增加，兩個方法的準確率都是降低的。類別數少，實際區域的范圍就大，而工人的軌跡區域變化就少，工人基本待在固定的一到兩個區域內，準確率就會升高；類別數大，實際區域范圍就小，越來越接近位置點，工人的軌跡變化開始增多，準確率會稍微降低。類別數為100 時，區域范圍很大，工人一天基本待在一個區域內，預測的結果會很準確。由圖7、圖8 可知，本文方法不管在工作日還是非工作日都要比Yava?等提出的方法性能好。本文考慮了工人歷史軌跡的時序性，研究表明[16]，用戶去前100 個地點的概率比后面幾十萬地點的概率大0.5，這就說明，區域地點之間存在某種潛在的聯系，并不僅僅只考慮最后一個區域去預測。劃分工作日之后，不僅成功率提高，算法的時間復雜度也會較低，因為可以直接根據規則標簽來判斷是否為工作日，減少算法掃描規則的時間，進而高效地去預測區域，推送任務。

7 結論

針對移動眾包服務推薦，本文提出了一個移動情景和用戶軌跡感知的眾包服務推薦策略。本文方法在眾包平臺分配任務時，通過實時感知到的軌跡信息和移動規則，預測用戶即將到達的位置區域，從而將區域內的時空任務推送給該用戶。本文任務分配方法避免了額外增加的工人執行任務的時間、行程、費用等成本，工人更愿意接受任務，從而提高了任務完成的概率，也提高了用戶體驗推薦服務的滿意度。