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

崔藝嬋

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

0 引言

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

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

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

1.1 停留點(diǎn)軌跡建模

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

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

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

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

花費(fèi)的時(shí)間；TG表示用戶u 在所有軌跡花費(fèi)的時(shí)間。

1.2 移動(dòng)性相似用戶查找

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

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

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

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

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

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

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

圖1 移動(dòng)相似序列的向后兼容

算法：查找移動(dòng)相似序列

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

輸出：兩個(gè)序列的移動(dòng)相似序列

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

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

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

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

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

5. break

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

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 //匹配下一個(gè)位置

10. j+=sj //匹配下一個(gè)位置

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

12. sj=1

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

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

15. sj++//當(dāng)前兼容步長加1

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

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

18. si++

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

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 移動(dòng)性相似用戶：用戶u1與用戶u2具有多個(gè)移動(dòng)相似序列，且兩者的相似度超過給定相似度閾值sT ，則稱用戶u1與用戶u2是移動(dòng)性相似用戶。

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

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

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

定義5 簇間轉(zhuǎn)移概率矩陣C：設(shè)k 為簇個(gè)數(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)移概率矩陣。所有時(shí)刻的簇間轉(zhuǎn)移概率矩陣按照時(shí)間順序排列，形成簇間轉(zhuǎn)移概率矩陣序列S=＜Ct1,Ct2,…,CtT,＞，其中T 表示最大的時(shí)間ID。

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

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

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

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

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

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

2.2 評價(jià)指標(biāo)

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

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

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

2.3 實(shí)驗(yàn)分析

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

圖2 對比實(shí)驗(yàn)

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

3 結(jié)語

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