基于位置相似性與Markov 模型的移動軌跡預測算法?

李佳澤 高全力 郭 帥 胡發麗 李慶敏

（西安工程大學計算機科學學院 西安 710048）

1 引言

隨著通信技術與互聯網基礎設施的快速發展，海量移動軌跡數據的獲取成為了現實［1］。與此同時，無人駕駛、智能車聯網等新應用的出現也催生了用戶對位置信息獲取與分析的需求［2］。移動用戶的軌跡數據不僅包含著移動用戶的行為軌跡模式，而且還記錄了用戶的實時動態［3］。通過分析潛在規律和相關有用信息，就能提供給用戶智能化、精確化的路線推薦［4］。因此，移動軌跡預測具有很高的研究價值［5］。

現有方法主要是Markov 模型和頻繁序列模式等。頻繁序列模式是利用關聯規則找出歷史軌跡中的頻繁軌跡序列［6］。該方法對歷史軌跡利用率很高，但耗費的時間較長［7］。Markov模型以其對時間序列數據處理的良好能力成為了應用廣泛的預測模型之一［8］。但是由于對歷史軌跡信息的利用不足，所以預測的精度不高［9］。馮然等［10］提出了基于二階馬爾可夫鏈的預測模型，時間復雜度較高。宋路杰等［11］引入相似度對Markov 模型候選結果集合進行修正。高建等［12］提出高斯混合-時間序列模型來預測用戶位置。李昇智等［13］提出了混合多步Markov 模型，將多階Markov 模型進行融合。程媛等［14］提出了基于非參數估計方法來構建概率密度函數，提高了軌跡的匹配程度。

上述的方法大多直接利用軌跡數據進行預測，對軌跡數據中的信息考慮不充分導致準確率不高。因此，本文提出了基于位置相似性與Markov模型（Location Similarity and Markov Model，LSMM）的軌跡預測算法，該方法是將位置相似性因素與Markov模型相結合，篩選出滿足位置相似的歷史軌跡序列集合；然后由軌跡相似的序列建立轉移概率矩陣，通過Markov 模型對用戶未來時間內的位置區域進行預測。

2 數據模型定義及說明

2.1 軌跡數據預處理

移動軌跡是一組時序序列，由一系列的軌跡采樣點構成，表示為{p1,p2,…,pn}(1 ≤i≤n)。由于軌跡采樣點的粒度過于細密，想要挖掘出其中的軌跡模式就需要進一步的處理，所以本文借鑒文獻［15］中的迭代網格劃分算法。對軌跡數據的樣本空間進行層次劃分，形成軌跡點的初始聚類，進而提取出具有一定規模的區域集合，實現軌跡的序列化。

定義1 軌跡序列：軌跡序列是由用戶的軌跡穿過的區域組成的序列。表示為

2.2 Markov模型

馬爾可夫過程假設未來的狀態只和當前的狀態有關，而和過去的狀態無關［16］。也就是說用戶的下一個位置僅和當前的地理位置相關。

定義2 馬爾可夫鏈：馬爾可夫鏈是一組狀態空間內具備馬爾可夫性質的隨機過程［17］。若隨機過程X={Xn:n>0} ，并且存在有限個狀態I={i0,i2,…,in}，若：

則X={Xn:n>0}被稱為馬爾可夫鏈。其中Xn=in表示X 處于n 時刻的狀態為in，Xn-1=in-1表示X 處于n-1時刻的狀態為in-1。

定義3 轉移概率：pij=P(Xn=j|Xn-1=i) 。轉移概率pi，j表示在當前n-1 時刻的狀態為i，下一時刻狀態轉化為j的概率［18］。若用戶經過的區域數量為n，那么轉移概率矩陣P 就是個n×n 的矩陣。其中pi，j表示從區域Si轉移到區域Sj的概率。其轉移概率表達式為

3 基于Markov 模型和位置相似性的預測算法

為了解決Markov 模型對歷史軌跡信息利用率低的問題，本文提出了基于歐式距離的位置相似性算法。該算法通過計算當前軌跡與歷史軌跡之間的歐式距離之和來判斷軌跡間的相似程度，并結合Markov模型完成軌跡預測。

考慮到歷史信息中距離當前軌跡較近的序列對結果影響比較大，所以在進行相似度判斷之前找出與用戶當前訪問區域相同的歷史軌跡序列，然后計算歷史軌跡序列與當前軌跡的歐式距離，找出符合滿足閾值的歷史軌跡序列。

若歷史軌跡集合為SH={H1,H2,…,Ha}(1 ≤k≤a)，則滿足與當前軌跡位置區域相同的歷史軌跡集合為H={H1,H2,…,Hβ}(1 ≤k≤β,β≤α) 。當前軌跡P={P1,P2,…,Pn}(1 ≤i≤n) ，歷史軌跡為Hk={Hk1,Hk2,…,Hkn}(k1 ≤ki≤kn)，kn 是歷史序列Hk中區域的個數，數量與當前軌跡P 中的個數n 相同，保證當前軌跡序列與歷史軌跡序列的長度相等。那么當前軌跡P 和歷史軌跡序列Hk中位置對應的第i 個區域的歐式距離D(P1,Hk1)的計算方法如下：

其中：Ploni和Plati表示Pi的經緯度坐標，Hionki和Hlatki表示Hki的經緯度坐標。

軌跡序列P 與歷史軌跡序列Hk的軌跡序列距離L(P,Hk)計算方法如下：

接著計算當前軌跡P 與歷史軌跡序列集合中軌跡序列距離L(P,Hk)的平均值μ。其表達式為

對于滿足L(P,Hk)≤μ的歷史軌跡序列，計算他們與當前軌跡P 的相似度。軌跡相似度是用來衡量當前軌跡P 與歷史軌跡序列Hk對應區域之間距離的離散程度，也就是計算軌跡之間距離的方差S(P,Hk)，其表達式為

對于S(P,Hk)小于相似度閾值δ的歷史軌跡序列，將該軌跡序列加入相似度集合M 中，根據相似度集合M 建立Markov 轉移概率矩陣，通過轉移概率矩陣的迭代計算可得出用戶下一步處于各區域的條件概率集合，其中條件概率最大的所對應的區域為預測結果。若預測區域為Pn+1，則

式中：Pnext為條件概率集合對應的區域；Pn為當前所在區域位置。

4 實驗及分析

本文的實驗環境是CPU 為Intel（R）Core（TM）i5-8300H的筆記本，內存為8GB，硬盤為500G的固態硬盤。實驗數據采用Geolife項目數據集［20］，該數據集不僅記錄了182 位用戶外出活動的真實行為和軌跡，還記錄了很多用戶日常生活中的信息，包括家庭住址或者工作單位等地理位置信息，能夠真實反映用戶軌跡模式。

為了測試LSMM 算法的性能和對預測準確率的提升情況，本文將選取1 階Markov 模型和2 階Markov 模型與之進行對比分析。實驗評價指標為預測準確率PredictionA，其定義為

其中：n為軌跡序列的長度；Ti和Hi分別為預測區域和真實區域。

1）圖1 給出了本文提出的LSMM 模型與1 階、2階Markov 模型在不同軌跡長度下的預測準確率的比較。可以看出，1 階模型和2 階Markov 模型的預測準確率并沒有隨著軌跡序列長度的增加而大幅度提高，在序列長度較小的時候，LSMM 模型由于歷史信息利用不足而與Markov 模型的準確率差距不大。而隨軌跡長度增加，LSMM 模型預測的準確率不斷提高，超過了1階模型和2階Markov模型。

圖1 三種方法的預測準確率比較

2）圖2 給出了兩種模型在不同階數下的預測準確率比較，對Markov 模型來說，模型階數的增加，預測準確率呈上升趨勢，但階數過高會出現數據稀疏問題，即在歷史軌跡集合中找不到與當前軌跡匹配的序列，導致預測精度不斷降低。而LSMM模型則很大程度上優化了Markov 模型，通過歷史信息的充分利用，降低了預測稀疏率的影響，提高了預測精度。

圖2 不同階數下兩種方法的預測準確率的比較

3）圖3 給出了不同規模的軌跡數據集下的三種模型的準確率的比較。隨著數據規模的不斷增加，三種模型的預測準確率都在增加，但是由于1階Markov 模型的對信息利用不夠充分，所以其準確率的上升空間小，而2階Markov模型雖然利用了歷史軌跡信息來提升模型的精度，但是對相似的軌跡利用率仍然不足。從圖上看，LSMM 模型無論是小規模數據集還是大規模數據集，表現都優于其他兩種算法。

圖3 不同規模軌跡數據集下的預測準確率對比

5 結語

本文提出了一種基于位置相似性與Markov 模型的移動軌跡預測算法。該算法首先對軌跡數據利用位置相似性因素進行篩選，作為Markov 模型的數據基礎，然后建立狀態轉移概率矩陣實現對未來區域的預測。實驗表明，該方法對比Markov 模型來說，充分利用了歷史軌跡信息，提高了預測的準確度和穩定性。未來工作中，還將在本文的基礎上，深入研究軌跡數據的時空特性實現軌跡的序列化，進一步提高模型的準確度。