張安冉，廖祎瑋，趙國生，王 健

(1.哈爾濱師范大學計算機科學與信息工程學院,黑龍江 哈爾濱 150025;2.哈爾濱理工大學計算機科學與技術學院,黑龍江 哈爾濱 150080)

1 引言

移動群智感知MCS(Mobile Crowd Sensing)是在參與感知和眾包等概念的基礎上發(fā)展而來的，劉云浩教授在2012年率先提出群智感知計算的概念[1]。MCS作為一種大規(guī)模獲取數(shù)據(jù)的全新感知模式，已經(jīng)應用于解決包括街邊停車管理[2]、交通狀況檢測[3]和環(huán)境污染監(jiān)測[4]等多種問題。但是，在用戶分布稀疏的情況下進行任務分配時，可能會出現(xiàn)任務所在區(qū)域的用戶數(shù)量覆蓋不足的問題，導致不能有效進行感知任務的分配。因此，用戶未來時刻位置的預測對于群智感知應用極其重要。若能對用戶位置進行精準的預測，則可以幫助平臺快速判斷在任務地點最有可能出現(xiàn)的用戶，以此來避免因用戶分布稀疏所造成的任務分配失敗問題。

隨著群智感知應用的深入，群智感知系統(tǒng)中關于用戶位置預測的問題也得到了進一步重視[5]。目前在基于位置預測的群智感知任務中，應用最普遍的是馬爾可夫模型。景瑤等人[6]提出一種針對移動性目標追蹤的預測方法MPRE(Movement PREdiction)，根據(jù)用戶的歷史軌跡，利用馬爾可夫模型對目標下一位置進行評估，并在此基礎上分別提出了以人為中心和以任務為中心的2種智能算法對任務進行最佳分配，實現(xiàn)了對感知數(shù)據(jù)的實時獲取。Yang等人[7]將馬爾可夫模型作為核心技術，根據(jù)用戶的歷史行為軌跡，提出了一種基于興趣點的移動性預測模型，用來獲取用戶可以完成任務的可能性。Wang等人[8]提出了一種基于預測的逆向拍賣激勵機制，使用Semi-Markov模型預測下一刻的用戶位置，根據(jù)預測位置選擇具有最小移動距離和競標價格的獲勝者。

用戶的位置序列是一個時間序列，用戶每一時刻的位置都與他過去時刻和未來時刻的位置存在密切聯(lián)系。在位置序列數(shù)據(jù)緊密連續(xù)的情況下，馬爾可夫模型通常更適合用來處理時空數(shù)據(jù)，但是當數(shù)據(jù)中所包含的位置點稀疏時，馬爾可夫模型在預測精度方面的表現(xiàn)則不佳。另外，馬爾可夫過程只考慮當前的位置狀態(tài)，并不受其歷史位置狀態(tài)的影響。近年來，許多學者和研究人員為解決位置預測等問題對人類的移動模式展開了研究，發(fā)現(xiàn)人類的行動位置可以被有效預測[9]?；诖私Y論，學者們針對位置的預測問題又提出了一些不同的解決方案。其中有學者充分利用卡爾曼濾波[10]和高斯模型[11,12]進行位置預測；Luan等人[13]提出一種名為XGBoost的基于樹的位置預測模型來預測目標將要訪問的下一位置；張震等人[14]提出了一種新型任務分配算法，并根據(jù)初始任務通過貝葉斯推理對用戶活動的下一位置進行評估，消除了由于用戶位置的可變性對數(shù)據(jù)實時性造成的負面影響；Xiao等人[15]利用支持向量機SVM(Support Vector Machine)回歸來實現(xiàn)位置和軌跡預測，降低了計算復雜度，克服了維數(shù)災難的問題。Jeong等人[16]采用深度神經(jīng)網(wǎng)絡DNN(Deep Neural Networks)進行位置預測，并用仿真實驗證明了其有效性。但是，DNN無法對具有時序性的數(shù)據(jù)進行建模，使得預測結果達不到較高的精度。Choi等人[17]將循環(huán)神經(jīng)網(wǎng)絡RNN(Recurrent Neural Network)應用于預測位置中的下一地點。RNN可看作在時間維度進行傳遞的深度神經(jīng)網(wǎng)絡，對于序列數(shù)據(jù)建模非常有效。但是，在學習過程中因為考慮失效的歷史信息會導致梯度消失或梯度爆炸問題，使模型預測精度下降。

用戶的位置序列具有時序性，每個時刻的位置與其前后位置密切相關，因此針對群智感知中現(xiàn)有方法存在的問題，本文提出了一種基于門控循環(huán)單元GRU(Gated Recurrent Unit)的用戶位置預測模型。首先分析對比了各種神經(jīng)網(wǎng)絡算法應用于用戶位置預測的可行性，根據(jù)對用戶位置時間序列的分析，搭建了基于GRU網(wǎng)絡的用戶位置預測模型。利用均方誤差MSE(Mean Squared Error)等作為評價標準，對網(wǎng)絡模型參數(shù)中的迭代次數(shù)和批次大小進行調(diào)優(yōu)；并根據(jù)交叉熵代價函數(shù)選取了Adam優(yōu)化器。最后對所提模型進行了仿真對比分析。

2 基于位置預測的群智感知系統(tǒng)模型

對于群智感知系統(tǒng)，位置預測可以極大提高任務的分配效率。在基于位置的群智感知應用中，時常會出現(xiàn)某些時刻用戶數(shù)目無法充分覆蓋感知區(qū)域的現(xiàn)象(當下時刻位于任務地點的用戶數(shù)目稀少或幾乎沒有，達不到任務完成所需數(shù)量)，對任務完成產(chǎn)生負面影響。因此，可通過位置預測為群智感知系統(tǒng)提供用戶現(xiàn)在及將來時刻位置，并配合相關激勵機制，增加參與者數(shù)量，保證感知任務順利完成。圖1為本文提出的系統(tǒng)模型，感知服務平臺根據(jù)預測的用戶未來時刻位置進行任務分配，其中請求服務的一方稱為任務請求者，被感知服務平臺鎖定為執(zhí)行任務的備選者稱為用戶。

Figure 1 Model of the crowd sensing system圖1 群智感知系統(tǒng)模型

如圖1系統(tǒng)模型所示，平臺對任務備選者的未來時刻位置進行預測，然后將其與發(fā)布的任務信息進行匹配，最后通知被選定的用戶并給出任務執(zhí)行的下一步指示,確保有效執(zhí)行任務。用戶向平臺提供包括GPS位置坐標和時間戳等自身信息，用一個6元組表示：ID是用戶的標識符，x、y、v和e分別代表用戶在t時刻的經(jīng)度、緯度、速度和所在路段。突發(fā)緊急任務的情況下，感知平臺利用用戶的歷史位置數(shù)據(jù)立即對用戶未來位置進行預判，并根據(jù)接收到的任務的時間和位置等信息分配任務。分配完成后，平臺會通知所選用戶。用戶根據(jù)任務指令在一定時間內(nèi)到達指定的任務位置，并利用現(xiàn)有設備采集信息，經(jīng)過簡單的處理和計算，將數(shù)據(jù)上傳至服務平臺，完成此次任務。

3 基于GRU網(wǎng)絡的用戶位置預測算法

通過對人類運動軌跡的研究發(fā)現(xiàn)，人類的出行活動存在著較高的重復性，會在固定的時間段內(nèi)，在相對固定的地點進行一些日常活動[9]。因此，本文提出了一種基于GRU網(wǎng)絡的用戶位置預測算法，利用對用戶的歷史出行位置時間序列模型的研究，預測用戶將來某個時刻可能到達的地點；同時，利用Adam算法對GRU網(wǎng)絡進行優(yōu)化，使得預測結果更加準確。

3.1 GRU網(wǎng)絡結構

對于用戶歷史出行位置的時間序列的分析要求算法具備記憶功能，能夠記錄用戶歷史位置數(shù)據(jù)特征。作為神經(jīng)網(wǎng)絡的RNN、長短期記憶LSTM(Long Short-Term Memory)網(wǎng)絡和GRU都具有記憶功能，適用于處理時間序列。相較于普通的神經(jīng)網(wǎng)絡RNN增加了一個循環(huán)機制，將上一個隱含層的輸出結果作為條件加入當前隱含層的結果判斷。如圖2所示，對于一個標準的RNN模型，其輸入序列為x={x1,x2,x3,…,xn}，通過模型計算可得到隱含層的序列h={h1,h2,h3,…,hn}和輸出序列y={y1,y2,y3,…,yn},其中x、h、y均為向量，分別代表輸入層、隱含層及輸出層的值，U、V、W分別是輸入層到隱含層、隱含層到輸出層和隱含層內(nèi)的權重矩陣。

Figure 2 RNN time line expansion圖2 RNN時間線展開圖

具體公式如式(1)和式(2)所示：

ht=tanh(Wx*xt+Wh*ht-1+b)

(1)

yt=Softmax(Wsht)

(2)

其中，tanh、Softmax是激活函數(shù)，Wx、Wh、Ws分別為輸入層、隱含層和輸出層的權重，b為偏置。ht、ht-1分別是t和t-1時刻隱含層的值，yt是t時刻的輸出值，都為向量。

用戶未來時刻位置的預測依賴于對用戶歷史位置時間序列的分析，時間序列越長，記錄的用戶歷史運動軌跡數(shù)據(jù)越多，預測精度相應也會越高。但是，RNN的記憶能力相對有限，信息積累到一定時間長度時，初始的信息便會消失，無法解決長期依賴的問題。相較于RNN，LSTM引入了門(Gate)的概念，通過輸入門、輸出門、遺忘門來選擇或遺忘數(shù)據(jù)特征，實現(xiàn)了序列數(shù)據(jù)的長距離依賴，解決了RNN的梯度消失問題。GRU在LSTM網(wǎng)絡的基礎上進行了改進，其網(wǎng)絡結構如圖3所示，它只包含更新門和重置門，去掉了單獨的存儲單元，使用隱藏狀態(tài)傳遞數(shù)據(jù)特征。

Figure 3 GRU unit structure圖3 GRU單元結構

GRU單元的更新可分為如下幾個步驟(其中xt和ht分別代表t時刻的輸入和輸出數(shù)據(jù))：

zt=σ(Wxzxt+Whzht-1)

(3)

rt=σ(Wxrxt+Whrht-1)

(4)

(5)

其中，⊙表示Hadamard乘積。

(6)

3.2 基于GRU網(wǎng)絡的用戶位置預測模型

用戶在現(xiàn)實生活中的運動都會受到路網(wǎng)條件的限制，因此在構建用戶運動模型時考慮路網(wǎng)因素具有重要意義。將路網(wǎng)結構定義為一個有向圖Q=〈S,E〉，S與E分別表示節(jié)點與邊的集合。其中每個節(jié)點si(si∈S)對應路網(wǎng)中的交叉路口，每條邊e=(si,sj)(si,sj∈S,e∈E)表示2個路口si與sj之間的路段，且表示方向為由節(jié)點si朝向節(jié)點sj。每個節(jié)點si(si∈S)都分別對應著一個經(jīng)緯度坐標點p={x,y}，如圖4所示。

Figure 4 Road network structure圖4 路網(wǎng)結構

用戶位置預測問題實際上是一種利用GRU網(wǎng)絡的回歸性問題。此模型中的網(wǎng)絡輸入為用戶的歷史位置特征和當前位置特征，網(wǎng)絡輸出為用戶在未來某一時刻的位置特征數(shù)據(jù)。通過預測值與真實值的誤差對比來訓練網(wǎng)絡，以此建立用戶位置的歷史特征數(shù)據(jù)與未來特征數(shù)據(jù)之間的函數(shù)關系，實現(xiàn)對用戶未來位置特征的評估。針對單個用戶在GRU模型的數(shù)據(jù)輸入軌跡特征可表示為：

(7)

根據(jù)用戶歷史軌跡坐標p映射到圖Q中邊上的位置li，那么用戶的軌跡實際上是一系列位置li按時間緯度進行排列的時間序列，位置點集合可表示為Loca=〈l1,l2,…,li〉。li表示用戶位置中的第i個位置點，其可表示為li=〈xi,yi,vi,ti,ei〉，其中，xi，yi，vi，ti，ei分別代表用戶在第i個位置點時的經(jīng)度、緯度、速度、時間以及對應圖Q中的所在路段。對GRU模型的輸入而言，位置的時間序列表示為Xt=[lix,liy,lit,liv,lie]，用戶位置表示為X=[X1,X2,X3,…,Xt]。為了實現(xiàn)用戶位置的預測，本文將連續(xù)前k個時刻的用戶位置數(shù)據(jù)X(t-k+1),…,X(t-1)和X(t)作為GRU模型的輸入，t+1時刻的用戶位置X(t+1)作為模型輸出，用戶位置預測模型的表達式如式(8)所示：

X(t+1)=f({X(t-k+1),…,X(t-1),X(t)})

(8)

為加快梯度下降中求取最優(yōu)解的速率并減少預測誤差，將模型的輸入數(shù)據(jù)進行歸一操作，使數(shù)據(jù)的取值統(tǒng)一于[0,1]。采用離差標準化(Min-Max Normalization)進行歸一化，轉換公式如式 (9)所示：

(9)

其中，Xmax為樣本數(shù)據(jù)中的最大值，Xmin為樣本數(shù)據(jù)中的最小值，X代表初始訓練數(shù)據(jù)，X*代表歸一后的數(shù)據(jù)。歸一化處理可以有效地避免數(shù)據(jù)數(shù)量級和取值范圍不同的影響。利用GRU網(wǎng)絡對用戶位置進行預測后的結果所處量級依舊在[0,1]，無法直接判斷與真實值之間的誤差，因此需要對結果按式(10)進行反歸一化處理，即式(9)的逆運算，才能得到實際的預測結果y。

y=X*(Xmax-Xmin)+Xmin

(10)

算法1基于GRU網(wǎng)絡的用戶位置預測算法

輸入：用戶位置序列Xposition,待預測用戶位置序列Xtext。

輸出：用戶下一時刻的位置Xresult。

BEGIN

構建訓練數(shù)據(jù)集，輸入連續(xù)k個時刻X(t-k+1),…,X(t-1),X(t)的位置特征數(shù)據(jù);

通過式(9)對輸入數(shù)據(jù)進行歸一化處理；

訓練集合Xposition中的每條數(shù)據(jù)，并保存訓練結果{data}；

將訓練數(shù)據(jù){data}輸入GRU網(wǎng)絡;

計算誤差函數(shù)，并利用Adam算法更新GRU參數(shù)，得到最佳GRU網(wǎng)絡模型;

將待預測用戶位置序列Xtext輸入訓練完成的GRU網(wǎng)絡模型;

根據(jù)式(8)得到用戶下一時刻的位置Xresult;

END

由算法1可以看出，用戶位置預測算法包括訓練和預測2部分。在訓練階段，將子軌跡數(shù)據(jù)進行歸一化處理之后，對于每一條歷史軌跡序列,取前k個時刻的軌跡點作為子序列加入到訓練數(shù)據(jù)集中，將第t+1時刻軌跡點作為預測目的點，加入到目標數(shù)據(jù)集中，利用訓練集對GRU網(wǎng)絡模型進行訓練，并采用Adam算法對模型參數(shù)進行優(yōu)化。最終利用GRU網(wǎng)絡模型得到所需要的下一時刻位置點，并對所得結果進行反歸一化處理，得到預測結果。

3.3 Adam優(yōu)化算法

為了加快權值矩陣的訓練，本文采用Adam算法作為預測用戶位置的GRU網(wǎng)絡的梯度訓練算法。該算法把AdaGrad (Adaptive Gradient Algorithm)算法[18]和RMSProp (Root Mean Square Prop)算法[19]的優(yōu)點結合起來，提高了參數(shù)更新和梯度更新計算的效率，減少了內(nèi)存使用，而且能夠解決梯度稀疏或梯度噪聲大的問題。如算法2所示：

算法2Adam優(yōu)化算法

輸入：全局學習率η(默認值為0.9);矩估計的指數(shù)衰減速率：β1，β2∈[0,1)(一般分別取0.9和0.999);用于數(shù)值穩(wěn)定的小常數(shù)δ(默認值為10-8);初始參數(shù)W0。

初始化一階和二階矩變量m0=0，v0=0;

初始化時間步t=0;

whileWt沒有收斂do

計算梯度：gt←▽J(Wt-1)(J為代價函數(shù)，得到隨機目標在時間步長t處的梯度);

更新時間步t;

更新有偏一階矩估計：mt←β1mt-1+(1-β1)gt;

更新參數(shù)：Wt+1←Wt+Δw;

endwhile

4 仿真實驗

為了驗證GRU網(wǎng)絡在群智感知中對于用戶位置預測的有效性，本文實驗基于深度學習框TensorFlow 2.0版本的上層框架Keras，構建了基于GRU網(wǎng)絡的用戶位置預測模型。為了優(yōu)化模型，提高模型的預測精度，通過模型自身對比實驗尋找最優(yōu)參數(shù)。在相同實驗環(huán)境下，通過與RNN和LSTM模型的對比，來驗證基于GRU網(wǎng)絡的用戶位置預測模型的有效性。

4.1 實驗數(shù)據(jù)集

車輛的出行數(shù)據(jù)不僅記錄了車輛的行車位置，還蘊藏著居民的出行規(guī)律[9]。因此，本文實驗采用來自于實際路網(wǎng)數(shù)據(jù)收集的城市區(qū)域車輛行駛的GPS位置信息[20]。實驗采用市內(nèi)車輛在2014年7月31日至8月12日的部分有效出行數(shù)據(jù)，并將路段信息進行標號，使路段e1,e2,…,em分別對應為序號1,2,…,m。這些數(shù)據(jù)很好地反映了當前城市區(qū)域內(nèi)車輛行駛的位置、時間等信息，可以作為本文的實驗數(shù)據(jù)使用。表1所示為車輛位置的部分GPS數(shù)據(jù)。

Table 1 Segment of vehicle trajectory data set

在實驗部分為了使GRU預測模型更具有說服力，將數(shù)據(jù)集劃分為65%訓練集和35%測試集，同時為了驗證本文模型的精度設置了5%驗證集。

4.2 實驗內(nèi)容

為了更好地評價、分析和預測結果，本文采用MSE、平均絕對誤差MAE(Mean Absolute Error)和平均絕對百分誤差MAPE(Mean Absolute Percentage Error)作為評價標準。MSE的數(shù)學表達如式(11)所示，這里用作網(wǎng)絡預測模型的loss值，loss值的大小代表著位置預測模型的預測精度。MAE和MAPE的數(shù)學表達分別如式(12)和式(13)所示，2種誤差指標為0%時表示模型完美，大于100%則表示模型劣質(zhì)。

(11)

(12)

(13)

4.2.1 模型參數(shù)分析

適合的參數(shù)可以優(yōu)化網(wǎng)絡模型的性能，因此實驗針對迭代次數(shù)epoch、批次大小batchsize2個參數(shù)進行對比分析。將均方誤差作為評價指標，對上述樣本進行不同參數(shù)值的訓練學習，部分結果如表2所示。

Table 2 MSE for different parameters

如表2所示，實驗中總計數(shù)據(jù)量為6 428條，通過比較最終確定epoch=500，batch_size=128時均方誤差最小，結果為2.49E-05。說明在當前參數(shù)配置下的GRU網(wǎng)絡模型表現(xiàn)出最好的預測能力與精度。

為了實現(xiàn)模型的最優(yōu)化，使得用戶位置預測結果的誤差盡可能小，要選擇合適的優(yōu)化器來尋找網(wǎng)絡合適的參數(shù)。Adam算法與RMSProp算法都可以對GRU網(wǎng)絡的參數(shù)更新和梯度更新進行優(yōu)化，在相同的實驗環(huán)境下進行對比，圖5為分別采用2種優(yōu)化算法的訓練效果。

Figure 5 Optimizer training results圖5 優(yōu)化器訓練結果

如圖5所示，2條線分別代表基于GRU的用戶預測模型中訓練損失loss的變化。RMSProp和Adam優(yōu)化器在第1次訓練時達到的loss值分別為0.018和0.012，此時模型所表現(xiàn)的精度不夠。繼續(xù)訓練可以看到使用Adam算法的loss值在第13次訓練時迅速下降到了1.95E-04，并且很快收斂，在相同的時間段內(nèi)RMSProp的表現(xiàn)稍遜色一些。從整體效果來看，在2種優(yōu)化算法作用下，訓練損失loss值都處于下降收斂的趨勢，但是Adam算法的優(yōu)化效果明顯比RMSProp好，更適用于本文實驗規(guī)模數(shù)據(jù)和參數(shù)訓練場景，所以最終選取Adam優(yōu)化器完成基于GRU的用戶位置預測模型的訓練。

4.2.2 模型質(zhì)量分析

通過上述對用戶位置預測模型的參數(shù)尋優(yōu)調(diào)整后，其訓練后的MAPE結果如圖6所示，實線代表基于GRU用戶預測模型中MAPE值的變化。MAPE是作為當前訓練得到的模型好壞的一個“可視化”指標。開始訓練時MAPE值達到了255%，說明此時所訓練的模型不夠成熟。但是，伴隨迭代次數(shù)的不斷增加，MAPE值也隨之減小，并最終降至6.11%,趨于穩(wěn)定，經(jīng)驗證與之對應的測試集誤差也在減小，說明經(jīng)過參數(shù)優(yōu)化后的基于GRU的用戶預測模型效果良好。

Figure 6 MAPE value of the model圖6 模型的MAPE值

4.2.3 用戶位置預測效果

為了更清晰地表達預測位置的精度，在此分析了預測位置與實際位置的誤差。根據(jù)確定的GRU最佳迭代次數(shù)、批次大小以及優(yōu)化器選型，將3個時刻的用戶位置數(shù)據(jù)作為初始輸入，預測接下來的4個點的用戶位置，得到的預測位置與實際位置的誤差結果如圖7所示。

Figure 7 User location prediction圖7 用戶位置預測

從圖7中可看出，預測位置(黑色折線4個點)與實際位置(灰色折線)近乎重疊。同時輸出的路段信息根據(jù)本文所定義的路網(wǎng)結構可判斷用戶的移動方向，按照式(14)，利用前一時刻t的位置以及預測得到的速度和方向推測下一時刻t+1位置，所得結果與圖7的一致，說明模型的預測精度較高，可以滿足群智感知系統(tǒng)要求。

pt+1=pt±vt

(14)

4.3 實驗結果

分別使用GRU模型、LSTM模型和RNN模型對樣本進行訓練，在輸入的測試數(shù)據(jù)及歷史時刻的用戶位置特征(數(shù)據(jù)格式如式(7)所示)完全相同的情況下，以遞歸方式進行連續(xù)預測，得到預測模型對于訓練集和測試集的擬合精度，如表3和表4所示。

Table 3 Training results of different models

Table 4 Test results of different models

由表3可知，GRU與LSTM較RNN而言，訓練時間長，約為RNN的2倍，但預測誤差小，其內(nèi)部原因在于這2種模型作為深度遞歸網(wǎng)絡，具有聯(lián)想記憶功能和遺忘機制，網(wǎng)絡進化時間較長。同時，GRU由于參數(shù)少，結構較LSTM更加簡化，所以擁有更快的訓練速度，訓練時間比LSTM節(jié)省8.3%，并且GRU的MSE和MAPE分別比LSTM的低18.0%和1.1%。同時，在表4所示的測試集結果中，GRU的MSE和MAE分別比LSTM的低33.3%和58.2%。

5 結束語

本文針對在群智感知環(huán)境中用戶位置預測的精度問題，并根據(jù)位置數(shù)據(jù)可變性大、非線性強的特點，將門控循環(huán)單元引入到用戶位置預測中。模型引入了Adam優(yōu)化算法迭代更新GRU網(wǎng)絡權重，有效地提高了GRU網(wǎng)絡預測的精度及優(yōu)化效率。同時，使用均方誤差作為選擇參數(shù)的評價指標，平均絕對誤差和平均絕對百分誤差分別作為測試結果和判斷調(diào)試后模型優(yōu)劣的評價標準。將RNN、LSTM和所提的GRU網(wǎng)絡模型進行對比實驗，對3個模型的訓練時間及預測精度進行了定量研究。仿真實驗表明，本文提出的基于GRU網(wǎng)絡的用戶位置預測算法的預測精度高于經(jīng)典的RNN和LSTM算法，可以為群智感知系統(tǒng)提供用戶未來時刻的準確位置，進而有效地進行任務分配工作，提高群智感知系統(tǒng)效率。本文研究的最終目的是通過對用戶位置的準確預測來實現(xiàn)任務及時有效的分配，所以下一步研究的重點是在已知用戶未來位置的基礎上提高感知任務的完成效率。