移動(dòng)情景和用戶軌跡感知的眾包服務(wù)推薦*

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

1.山東大學(xué) 軟件學(xué)院，濟(jì)南 250101

2.山東省軟件工程重點(diǎn)實(shí)驗(yàn)室，濟(jì)南 250101

1 引言

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

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

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

第二個(gè)挑戰(zhàn)在于移動(dòng)眾包服務(wù)場(chǎng)景的動(dòng)態(tài)性。例如出租車、外賣等O2O 服務(wù)，無(wú)論是任務(wù)發(fā)布者，還是潛在的執(zhí)行者都在不斷涌現(xiàn)，或者隨時(shí)退出，并且其位置、軌跡也處于動(dòng)態(tài)變化之中，這些對(duì)時(shí)空任務(wù)推薦算法的實(shí)時(shí)有效性、動(dòng)態(tài)場(chǎng)景適應(yīng)能力都提出了更高的要求。

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

本文受工人歷史軌跡數(shù)據(jù)可以提供很多有意義信息的啟發(fā)，從中分析出某個(gè)用戶的移動(dòng)軌跡模式、行為習(xí)慣、對(duì)于某些地點(diǎn)的偏好等；然后基于該分析，對(duì)用戶的移動(dòng)位置區(qū)域進(jìn)行預(yù)測(cè)；再將預(yù)測(cè)之后區(qū)域內(nèi)的任務(wù)推送給他，這將會(huì)提高用戶接受任務(wù)的概率，同時(shí)降低額外的旅行費(fèi)用、時(shí)間等成本。

本文的主要貢獻(xiàn)如下：

（1）首先將離散的位置點(diǎn)聚類成區(qū)域，然后對(duì)用戶的區(qū)域移動(dòng)軌跡進(jìn)行挖掘，利用移動(dòng)模式集來(lái)描述特定用戶在不同移動(dòng)情景下的軌跡變化。

（2）在用戶移動(dòng)模式集的基礎(chǔ)上，構(gòu)建移動(dòng)規(guī)則，并提出預(yù)測(cè)工人位置區(qū)域的方法，將區(qū)域內(nèi)的眾包任務(wù)推送給他。

（3）在真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，驗(yàn)證了本文提出的不同移動(dòng)情景下用戶位置預(yù)測(cè)算法任務(wù)推薦策略的有效性和準(zhǔn)確性。

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

2 相關(guān)工作

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

本文對(duì)文獻(xiàn)[14]提出的位置預(yù)測(cè)方法進(jìn)行改進(jìn)，在預(yù)測(cè)移動(dòng)模式生成中加入了上下文影響因素，例如考慮到周末/節(jié)假日和工作日的用戶移動(dòng)行為的區(qū)別，并根據(jù)上下文相關(guān)的移動(dòng)模式分別提取移動(dòng)規(guī)則從而提高預(yù)測(cè)的準(zhǔn)確性。

3 問(wèn)題定義

本文方法的基本思路是通過(guò)挖掘移動(dòng)用戶軌跡模式來(lái)預(yù)測(cè)用戶將要到達(dá)的位置區(qū)域，然后將區(qū)域內(nèi)的任務(wù)推薦給工人，以提高工人成功接受任務(wù)的概率。為了方便理解，介紹本文方法的相關(guān)定義。

定義1（區(qū)域（region,r））區(qū)域r表示地理位置范圍，是對(duì)該移動(dòng)用戶和時(shí)空任務(wù)物理坐標(biāo)的聚合，在本文中使用編號(hào)來(lái)表示。例如，萬(wàn)達(dá)廣場(chǎng)商圈可以作為一個(gè)區(qū)域r。

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

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

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

→

→

…

→

4 基于移動(dòng)模式挖掘的工人位置預(yù)測(cè)

移動(dòng)工人的位置區(qū)域預(yù)測(cè)及任務(wù)推薦過(guò)程包括四個(gè)階段：首先對(duì)離散的位置點(diǎn)進(jìn)行聚類，得到區(qū)域，對(duì)工人的歷史區(qū)域移動(dòng)軌跡進(jìn)行挖掘，形成工人移動(dòng)模式；根據(jù)獲得的工人移動(dòng)模式構(gòu)建出工人移動(dòng)規(guī)則；通過(guò)實(shí)時(shí)感知到的工人位置信息和移動(dòng)規(guī)則預(yù)測(cè)工人下一步將要到達(dá)的位置區(qū)域；最后根據(jù)預(yù)測(cè)為工人推薦時(shí)空任務(wù)。位置預(yù)測(cè)及任務(wù)推薦過(guò)程如圖1所示。

4.1 生成區(qū)域

假設(shè)本文中所有任務(wù)所在的位置能夠包含在這些區(qū)域內(nèi)，使用最流行的聚類算法K-means 算法將位置點(diǎn)聚合成區(qū)域，實(shí)現(xiàn)點(diǎn)到區(qū)域的變換。K-means算法的步驟如下：

Fig.1 Location prediction and task recommendation process for mobile workers圖1 移動(dòng)工人的位置預(yù)測(cè)及任務(wù)推薦過(guò)程圖

（1）隨機(jī)選擇K個(gè)初始質(zhì)心；

（2）如果沒(méi)有滿足聚類算法終止條件，則繼續(xù)執(zhí)行步驟（3），否則轉(zhuǎn)步驟（5）；

（3）計(jì)算每個(gè)非質(zhì)心點(diǎn)p到k個(gè)質(zhì)心的歐幾里德距離，將p指派給距離最近的質(zhì)心；

（4）根據(jù)上一步的k個(gè)質(zhì)心及其對(duì)應(yīng)的非質(zhì)心點(diǎn)集，重新計(jì)算新的質(zhì)心點(diǎn)，然后轉(zhuǎn)步驟（2）；

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

通過(guò)K-means 算法對(duì)位置點(diǎn)聚類后，得到區(qū)域，進(jìn)一步將其形式化為有向圖G。圖2 是實(shí)際區(qū)域圖的例子，圖3 為區(qū)域網(wǎng)絡(luò)有向圖，雙向箭頭代表兩個(gè)區(qū)域之間可以直接到達(dá)。

4.2 挖掘工人移動(dòng)模式

本節(jié)詳細(xì)介紹如何挖掘工人移動(dòng)模式，下面是詳細(xì)步驟。

Fig.2 Actual area map圖2 實(shí)際區(qū)域圖

Fig.3 Digraph of regional network圖3 區(qū)域網(wǎng)絡(luò)有向圖

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

在移動(dòng)情景方面，劃分工作日、周末，將分別產(chǎn)生其移動(dòng)模式Lw和Lp。

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

輸入：數(shù)據(jù)庫(kù)中的工人實(shí)際路線（WAP）D，最小支持度suppmin，網(wǎng)絡(luò)區(qū)域圖G。

輸出：工人移動(dòng)模式（WMP）Lw、Lp。

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

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

4.3 生成移動(dòng)規(guī)則

在挖掘工人移動(dòng)模式的基礎(chǔ)上，進(jìn)行移動(dòng)規(guī)則提取，由第3 章移動(dòng)規(guī)則定義可知，假設(shè)工人移動(dòng)模式WMP，L=<(r1,t1),(r2,t2),…,(rk,tk)>,k>1,其移動(dòng)規(guī)則見(jiàn)第3章。

Table 1 Workers'actual path表1 工人實(shí)際路線

Table 2 Worker mobile patterns set L表2 工人移動(dòng)模式集合L

對(duì)于一個(gè)規(guī)則R:→，給它定義一個(gè)置信度，用來(lái)表示該規(guī)則的可信程度，即預(yù)測(cè)的準(zhǔn)確程度。置信度使用如下公式定義：

利用工人移動(dòng)模式挖掘算法得到的WMP，可以生成所有可能的移動(dòng)規(guī)則并計(jì)算出它們的置信度。如果一個(gè)規(guī)則的置信度高于預(yù)先設(shè)定的置信度閾值(coffmin)，就將它們選擇出來(lái)用于下一個(gè)區(qū)域預(yù)測(cè)階段。

由于移動(dòng)模式是基于不同情景提取的（本文只考慮了工作日/節(jié)假日相關(guān)性），每個(gè)移動(dòng)規(guī)則也需要增加不同情景標(biāo)簽，來(lái)表明特定情景下的移動(dòng)規(guī)則。

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

4.4 工人區(qū)域預(yù)測(cè)

位置區(qū)域預(yù)測(cè)是最后一個(gè)階段，算法的偽代碼描述如下：

算法2位置區(qū)域預(yù)測(cè)MobilityPrediction()

輸入：用戶當(dāng)前的移動(dòng)軌跡P=<(r1,t1),(r2,t2),…,(ri-1,ti-1)>,移動(dòng)規(guī)則集合R,預(yù)測(cè)的最大位置個(gè)數(shù)m。

輸出：預(yù)測(cè)區(qū)域集合PRegions。

Table 3 Mobile rule set表3 移動(dòng)規(guī)則集

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

由于生成移動(dòng)規(guī)則時(shí)添加了情景標(biāo)簽（即是否為工作日），進(jìn)行掃描時(shí)先判斷當(dāng)前時(shí)間與當(dāng)前標(biāo)簽內(nèi)容是否一致，如果與規(guī)則標(biāo)簽不符，直接跳過(guò)去掃描下一個(gè)規(guī)則，這將大大提高匹配效率。

5 移動(dòng)眾包任務(wù)推薦

在移動(dòng)眾包應(yīng)用場(chǎng)景中，由于空間任務(wù)和工人的位置、數(shù)量都動(dòng)態(tài)變化并實(shí)時(shí)更新，任務(wù)推薦的目標(biāo)考慮在一段時(shí)間內(nèi)，實(shí)現(xiàn)任務(wù)分配數(shù)量最大化的局部最優(yōu)，本文基于文獻(xiàn)[11]的貪心策略進(jìn)行任務(wù)推薦。給定一組工人Wi={w1,w2,…}和區(qū)域D內(nèi)的一組任務(wù)Ti={t1,t2,…},目標(biāo)是在一段時(shí)間內(nèi)，將Ti中的任務(wù)推薦給Wi中的工人。本文假設(shè)所有工人的質(zhì)量一致。

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

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

Fig.4 Distribution map of workers,region and task圖4 工人、區(qū)域、任務(wù)分布圖

Fig.5 Process network diagram圖5 流程網(wǎng)絡(luò)圖

6 實(shí)驗(yàn)

6.1 數(shù)據(jù)整理

為了在現(xiàn)實(shí)環(huán)境下測(cè)試所提出的方法，本文使用了基于位置的社交網(wǎng)絡(luò)Gowalla的數(shù)據(jù)集，包括用戶時(shí)間和其地點(diǎn)的經(jīng)緯度，以及地點(diǎn)的ID。簽到集包括了從2009 年至2010 年10 月期間收集的644 多萬(wàn)條數(shù)據(jù)，對(duì)其進(jìn)行清洗和處理，最后提取了有100萬(wàn)條數(shù)據(jù)的數(shù)據(jù)集，其包含4 000 多個(gè)用戶和45 000個(gè)不同地點(diǎn)。數(shù)據(jù)集的地點(diǎn)和用戶分別用來(lái)代表空間的眾包任務(wù)和工人的位置，只要工人到指定地點(diǎn)簽到就看作是接受眾包任務(wù)并完成。雖然數(shù)據(jù)集不是直接來(lái)自空間的眾包，但它提供了不同的、現(xiàn)實(shí)世界的工人和任務(wù)位置的分布，由于本文研究的算法依賴于位置，使用這個(gè)數(shù)據(jù)集，能夠?qū)λ鼈兊南鄬?duì)性能得出一些合理的結(jié)論。

數(shù)據(jù)集本身是一些用戶的簽到數(shù)據(jù)，相對(duì)來(lái)說(shuō)比較稀疏，本文首先對(duì)提取的數(shù)據(jù)集進(jìn)行處理，將損壞的、空白的對(duì)實(shí)驗(yàn)沒(méi)有任何幫助的數(shù)據(jù)全都清除。數(shù)據(jù)清洗完之后，使用K-means 算法對(duì)其進(jìn)行聚類,將離散的數(shù)據(jù)聚成多個(gè)區(qū)域，看成眾包任務(wù)的分布地點(diǎn)。

圖6 是對(duì)數(shù)據(jù)集聚類的結(jié)果，其中類別數(shù)為2 000，每個(gè)類別分別用不同顏色標(biāo)出，每種顏色代表一個(gè)類，即一個(gè)區(qū)域。

Fig.6 Clustering region graph圖6 聚類區(qū)域圖

按照時(shí)間先后將每一個(gè)工人的軌跡路徑劃分為訓(xùn)練集和測(cè)試集，其中訓(xùn)練集用來(lái)獲得4.3節(jié)介紹的工人移動(dòng)規(guī)則，測(cè)試集是用來(lái)測(cè)試通過(guò)移動(dòng)規(guī)則預(yù)測(cè)的區(qū)域和工人真實(shí)要去的區(qū)域是否一致。如果一致，表明預(yù)測(cè)的工人即將要去的區(qū)域和眾包任務(wù)的分布區(qū)域是一樣的，就可以將區(qū)域內(nèi)的任務(wù)推送給工人，即代表任務(wù)推薦成功，否則推薦失敗。

6.2 實(shí)驗(yàn)評(píng)估

用success代表任務(wù)推薦的成功率，計(jì)算公式如下：

其中，match表示任務(wù)推薦成功的數(shù)量，all表示所有的任務(wù)數(shù)。

下面給出本文方法與Yava?等研究者[14]提出的預(yù)測(cè)方法的比較，根據(jù)測(cè)試集預(yù)測(cè)區(qū)域編號(hào)的準(zhǔn)確率進(jìn)行對(duì)比，如圖7、圖8所示。

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

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

圖7、圖8 表明，隨著聚類類別數(shù)的增加，兩個(gè)方法的準(zhǔn)確率都是降低的。類別數(shù)少，實(shí)際區(qū)域的范圍就大，而工人的軌跡區(qū)域變化就少，工人基本待在固定的一到兩個(gè)區(qū)域內(nèi)，準(zhǔn)確率就會(huì)升高；類別數(shù)大，實(shí)際區(qū)域范圍就小，越來(lái)越接近位置點(diǎn)，工人的軌跡變化開(kāi)始增多，準(zhǔn)確率會(huì)稍微降低。類別數(shù)為100 時(shí)，區(qū)域范圍很大，工人一天基本待在一個(gè)區(qū)域內(nèi)，預(yù)測(cè)的結(jié)果會(huì)很準(zhǔn)確。由圖7、圖8 可知，本文方法不管在工作日還是非工作日都要比Yava?等提出的方法性能好。本文考慮了工人歷史軌跡的時(shí)序性，研究表明[16]，用戶去前100 個(gè)地點(diǎn)的概率比后面幾十萬(wàn)地點(diǎn)的概率大0.5，這就說(shuō)明，區(qū)域地點(diǎn)之間存在某種潛在的聯(lián)系，并不僅僅只考慮最后一個(gè)區(qū)域去預(yù)測(cè)。劃分工作日之后，不僅成功率提高，算法的時(shí)間復(fù)雜度也會(huì)較低，因?yàn)榭梢灾苯痈鶕?jù)規(guī)則標(biāo)簽來(lái)判斷是否為工作日，減少算法掃描規(guī)則的時(shí)間，進(jìn)而高效地去預(yù)測(cè)區(qū)域，推送任務(wù)。

7 結(jié)論

針對(duì)移動(dòng)眾包服務(wù)推薦，本文提出了一個(gè)移動(dòng)情景和用戶軌跡感知的眾包服務(wù)推薦策略。本文方法在眾包平臺(tái)分配任務(wù)時(shí)，通過(guò)實(shí)時(shí)感知到的軌跡信息和移動(dòng)規(guī)則，預(yù)測(cè)用戶即將到達(dá)的位置區(qū)域，從而將區(qū)域內(nèi)的時(shí)空任務(wù)推送給該用戶。本文任務(wù)分配方法避免了額外增加的工人執(zhí)行任務(wù)的時(shí)間、行程、費(fèi)用等成本，工人更愿意接受任務(wù)，從而提高了任務(wù)完成的概率，也提高了用戶體驗(yàn)推薦服務(wù)的滿意度。