基于位置相似性與Markov 模型的移動(dòng)軌跡預(yù)測(cè)算法?

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

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

1 引言

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

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

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

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

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

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

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

2.2 Markov模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)及分析

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

為了測(cè)試LSMM 算法的性能和對(duì)預(yù)測(cè)準(zhǔn)確率的提升情況，本文將選取1 階Markov 模型和2 階Markov 模型與之進(jìn)行對(duì)比分析。實(shí)驗(yàn)評(píng)價(jià)指標(biāo)為預(yù)測(cè)準(zhǔn)確率PredictionA，其定義為

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

1）圖1 給出了本文提出的LSMM 模型與1 階、2階Markov 模型在不同軌跡長(zhǎng)度下的預(yù)測(cè)準(zhǔn)確率的比較?？梢钥闯觯? 階模型和2 階Markov 模型的預(yù)測(cè)準(zhǔn)確率并沒(méi)有隨著軌跡序列長(zhǎng)度的增加而大幅度提高，在序列長(zhǎng)度較小的時(shí)候，LSMM 模型由于歷史信息利用不足而與Markov 模型的準(zhǔn)確率差距不大。而隨軌跡長(zhǎng)度增加，LSMM 模型預(yù)測(cè)的準(zhǔn)確率不斷提高，超過(guò)了1階模型和2階Markov模型。

圖1 三種方法的預(yù)測(cè)準(zhǔn)確率比較

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

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

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

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

5 結(jié)語(yǔ)

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