李佳澤 高全力 郭 帥 胡發(fā)麗 李慶敏

（西安工程大學(xué)計算機科學(xué)學(xué)院 西安 710048）

1 引言

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

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

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

2 數(shù)據(jù)模型定義及說明

2.1 軌跡數(shù)據(jù)預(yù)處理

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

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

2.2 Markov模型

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

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

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

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

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

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

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

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

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

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

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

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

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

式中：Pnext為條件概率集合對應(yīng)的區(qū)域；Pn為當前所在區(qū)域位置。

4 實驗及分析

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

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

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

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

圖1 三種方法的預(yù)測準確率比較

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

圖2 不同階數(shù)下兩種方法的預(yù)測準確率的比較

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

圖3 不同規(guī)模軌跡數(shù)據(jù)集下的預(yù)測準確率對比

5 結(jié)語

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