崔藝嬋

（四川大學(xué)計算機學(xué)院，成都 610065）

0 引言

位置預(yù)測在城市規(guī)劃、交通預(yù)警、基于位置的推薦服務(wù)等方面具有巨大的經(jīng)濟和社會效益。用戶歷史軌跡具有隨機性、多樣性和時序性，而很多已有方法不能將時間對用戶移動行為的影響量化反映[1-4]，從而無法實現(xiàn)有效預(yù)測?；谖恢棉D(zhuǎn)移時空規(guī)律的用戶簽到位置預(yù)測[5]，提出基于向量自回歸的位置轉(zhuǎn)移演化算法（LTE），通過用戶歷史簽到記錄，學(xué)習(xí)用戶位置轉(zhuǎn)移隨時間、空間變化的規(guī)律。本文針對上述算法未考慮相似用戶的移動規(guī)律對目標用戶位置轉(zhuǎn)移的影響這一問題，提出移動性相似用戶的概念，以挖掘目標用戶的相似用戶群體，進一步提高位置預(yù)測的準確度。

1 基于移動性相似用戶的位置預(yù)測

在實際生活中，人們的移動行為往往會受到朋友的影響，為了進一步提高位置預(yù)測的準確度，本文旨在挖掘目標用戶的相似用戶群體，根據(jù)移動性相似用戶的歷史軌跡數(shù)據(jù)，預(yù)測目標用戶未來特定時刻的位置。

1.1 停留點軌跡建模

由于GPS 軌跡數(shù)據(jù)采集位置點的頻率較高，且位置點分布具有隨機性，使得用戶移動軌跡中包含大量位置點。本文從每一條軌跡中，識別停留區(qū)，提取停留點，生成停留點軌跡。

停留點軌跡建模的方法是首先識別停留區(qū)，然后從中選取用戶訪問可能性最大的位置點作為停留點，根據(jù)各停留點的時間先后順序連接成停留點軌跡，以更加有效地表示用戶的移動性。結(jié)合實際情況，一個用戶在某個位置點的訪問頻率越高且停留時間越長，說明該位置點對用戶越重要，該用戶訪問該位置點的可能性越大。本文以位置點的重要性得分來描述該位置點對于用戶的重要性。

位置點l 對于用戶u 的重要性得分如公式（1）所示。

其中，F(xiàn)l表示用戶u 在停留區(qū)SR 中訪問位置點l的次數(shù)（一個用戶可能多次訪問同一個位置點）；FSR表示用戶u 在停留區(qū)SR 中的簽到次數(shù)；FGl表示用戶u 的所有軌跡中包含位置點l 的軌跡數(shù)量；FG表示用戶u 的所有軌跡數(shù)量；Tl表示用戶u 在停留區(qū)SR 中在位置點l 的停留時間；TSR表示用戶u 在停留區(qū)SR的停留總時間；TGl表示用戶u 在包含位置點l 的軌跡

花費的時間；TG表示用戶u 在所有軌跡花費的時間。

1.2 移動性相似用戶查找

現(xiàn)在將1.1 小節(jié)中生成的停留點軌跡數(shù)據(jù)進行K-means 聚類，為每個停留點添加簇ID，以每個用戶的每一條停留點軌跡作為一個序列，生成簇間轉(zhuǎn)移序列，通過PrefixScan 序列模式挖掘算法，挖掘每個用戶的移動模式。

定義1 移動頻繁序列MFS：用戶移動行為中頻繁出現(xiàn)的簇間轉(zhuǎn)移序列，如公式（2）所示。

其中xi表示用戶的第i 個簇ID，?ti表示從xi轉(zhuǎn)移到xi+1的轉(zhuǎn)移時間，?ti不超過轉(zhuǎn)移時間閾值tt，如公式（3）所示。

其中arvT( xi+1) 表示用戶在簇xi+1的到達時間，levT(xi)表示用戶在簇xi的離開時間。

定義2 移動模式MP：用戶u 的移動模式由該用戶的所有移動頻繁序列描述，如公式（4）所示。

定義3 移動相似序列MSS：針對用戶u1的移動頻繁序列MFS1（如公式（5）所示），與用戶u2的移動頻繁序列MFS2（如公式（6）所示），若每對簇的相對位置相同（xi=yi），且每對簇的轉(zhuǎn)移時間差|?ti-?t'i|不超過轉(zhuǎn)移時間差閾值td ，則認為MFS1和MFS2是移動相似序列。用戶u1與用戶u2的相似性度量如公式（7）所示。其中MPu1表示用戶u1的移動模式，MPu2表示用戶u2的移動模式，MSS 表示用戶u1與用戶u2的移動相似序列，len( MFS )表示移動頻繁序列MFS 的長度，supu1(MFS)表示移動頻繁序列MFS 在用戶u1所有軌跡的支持度，supu2(MFS)表示移動頻繁序列MFS 在用戶u2所有軌跡的支持度。

注意：兩個移動頻繁序列的相對位置，在滿足轉(zhuǎn)移時間閾值和轉(zhuǎn)移時間差閾值的情況下，允許向后兼容。如圖1 所示，針對三個用戶的移動頻繁序列，設(shè)轉(zhuǎn)移時間閾值tt=2.5h，轉(zhuǎn)移時間差閾值td=1h，用戶1 與用戶2 有移動相似序列C1 →C2 →C3。針對用戶3，C1 →C2 的轉(zhuǎn)移時間為2.5h，滿足tt，所以相對位置可以跳過C4。用戶1 與用戶3 有移動相似序列C1 →C2 →C3，而用戶2 的C2 →C3 轉(zhuǎn)移時間為2h，用戶3 的C2 →C3 轉(zhuǎn)移時間為0.5h，兩者的轉(zhuǎn)移時間差|2h-0.5h |＞td，所以用戶2 與用戶3 沒有移動相似序列。

圖1 移動相似序列的向后兼容

算法：查找移動相似序列

輸入：用戶u 的一個移動頻繁序列MFSu，用戶v的一個移動頻繁序列MFSv，轉(zhuǎn)移時間閾值tt，轉(zhuǎn)移時間差閾值td，兼容最大步長max S

輸出：兩個序列的移動相似序列

初始化：集合MSS，存儲兩個序列對應(yīng)移動相似序列中的簇ID,si=1，sj=1

1. 查找兩個移動序列中，第一對簇ID 相同出現(xiàn)的位置，分別記為i,j

2. MSS.insert(第一個相同的簇ID)

3. while i＜length(MFSu)and j＜length(MFSv)：

4. if si＞maxS or sj＞maxS then //兼容步長超過閾值，停止查找

5. break

6. //相對位置的簇ID 相同，且滿足轉(zhuǎn)移時間閾值、轉(zhuǎn)移時間差閾值

7. if Ci+si==Cj+sjand ?ti≤tt and ?tj≤tt and|?ti-?tj|≤td then

8. MSS.insert(Ci+si) //該簇ID 加入MSS 集合

9. i+=si //匹配下一個位置

10. j+=sj //匹配下一個位置

11. si=1 //重置兼容步長

12. sj=1

13. //第二個序列向后兼容一步，符合條件

14. else if Ci+si!=Cj+sjand Ci+si==Cj+sj+1and?ti≤tt and |tj-tj+sj+1|≤tt then

15. sj++//當前兼容步長加1

16. //第一個序列向后兼容一步，符合條件

17. else if Ci+si!=Cj+sjand Ci+si+1==Cj+sjand?ti≤tt and |ti-ti+si+1|≤tt then

18. si++

19. //兩個序列都向后兼容，符合條件

20. else if Ci+si!=Cj+sjand Ci+si+1==Cj+sj+1and|ti-ti+si+1|≤tt and |tj-tj+sj+1|≤tt then

21. si++

22. sj++

23. return MSS

定義4 移動性相似用戶：用戶u1與用戶u2具有多個移動相似序列，且兩者的相似度超過給定相似度閾值sT ，則稱用戶u1與用戶u2是移動性相似用戶。

根據(jù)目標用戶u 與其他用戶的相似度分數(shù)，選取得分超過閾值的所有用戶作為目標用戶的移動性相似用戶群體（包括目標用戶自身）。

1.3 基于簇間轉(zhuǎn)移概率矩陣的位置預(yù)測

現(xiàn)在根據(jù)1.2 小節(jié)中查找的目標用戶的移動性相似用戶，提取這些用戶所有的停留點軌跡，按照給定的時間粒度為每個停留點生成時間ID。

定義5 簇間轉(zhuǎn)移概率矩陣C：設(shè)k 為簇個數(shù)，存在矩陣Ck×k，對于任意1 ≤i,j ≤k，矩陣元素Ci,j表示從簇i 轉(zhuǎn)移到簇j 的概率，由簇i 轉(zhuǎn)移到簇j 的簽到頻次占從簇i 轉(zhuǎn)移出的所有簽到頻次的百分比表示。矩陣Ck×k稱為數(shù)據(jù)集G 上的簇間轉(zhuǎn)移概率矩陣。所有時刻的簇間轉(zhuǎn)移概率矩陣按照時間順序排列，形成簇間轉(zhuǎn)移概率矩陣序列S=＜Ct1,Ct2,…,CtT,＞，其中T 表示最大的時間ID。

向量自回歸模型（VAR）描述多變量時間序列之間的變動關(guān)系以及隨機擾動項對變量的動態(tài)影響。本文將每個時刻的簇間轉(zhuǎn)移概率矩陣按行展開，形成簇間轉(zhuǎn)移向量序列。滯后階數(shù)為p 的VAR 模型如公式（8）所示。

yt=c+?1yt-1+?2yt-2+…+?pyt-p+εt（8）

本文采用極大似然估計方法確定模型參數(shù)，在已知yt-1,yt-2,…,yt-p時，利用模型預(yù)測，同時可進行多步預(yù)測，預(yù)測未來多個時刻目標用戶的簇ID。

2 實驗

2.1 數(shù)據(jù)集

本文使用GeoLife GPS 軌跡數(shù)據(jù)集進行實驗，該數(shù)據(jù)集由微軟亞洲研究的GeoLife 項目收集，包含從2007 年4 月到2012 年8 月182 位用戶的軌跡數(shù)據(jù)。軌跡由一系列帶時間戳的位置點表示，每個位置點包含緯度、經(jīng)度、高度等信息。

2.2 評價指標

本文將每個用戶的軌跡數(shù)據(jù)按照時間順序以9：1的比例分為兩部分，分別作為訓(xùn)練集和測試集，預(yù)測目標用戶測試集中對應(yīng)時刻的位置。

本文借鑒混淆矩陣，選用準確率、平均召回率和F1 值評價算法性能。按照如下公式定義準確率、平均召回率和F1 值：

其中，T(ui)表示用戶ui的真實簇ID，P(ui)表示用戶ui的預(yù)測簇ID，N 表示預(yù)測N 個時刻的位置，T(uij) 表示用戶ui的真實簇ID 為簇j，P(uij) 表示用戶ui的預(yù)測簇ID 為簇j，k 表示簇個數(shù)。

2.3 實驗分析

本文算法與LTE 算法的對比實驗結(jié)果，如圖2所示。

圖2 對比實驗

通過以上對比實驗可以發(fā)現(xiàn)，基于移動性相似用戶的位置預(yù)測算法相較于LTE 算法[5]，準確率、平均召回率和F1 值更高。由此可見，基于移動性相似用戶的歷史軌跡挖掘目標用戶的位置轉(zhuǎn)移規(guī)律，可以排除非相似用戶的歷史軌跡數(shù)據(jù)對目標用戶的干擾，從而實現(xiàn)更加準確有效的預(yù)測。

3 結(jié)語

位置預(yù)測具有重大的理論價值和應(yīng)用價值。本文介紹了一種基于移動性相似用戶的位置預(yù)測算法，通過停留點軌跡建模、移動頻繁序列挖掘，查找目標用戶的移動性相似用戶，根據(jù)這些用戶的歷史軌跡數(shù)據(jù)，挖掘目標用戶的位置轉(zhuǎn)移規(guī)律，可以在一定程度上排除非相似用戶的干擾，從而提高預(yù)測性能。