基于Adaboost-Markov模型的移動用戶位置預(yù)測方法

楊震 王紅軍

摘 要：針對Markov模型在位置預(yù)測中存在預(yù)測精度不高及匹配稀疏等問題，提出了一種基于Adaboost-Markov模型的移動用戶位置預(yù)測方法。首先，通過基于轉(zhuǎn)角偏移度與距離偏移量的軌跡劃分方法對原始軌跡數(shù)據(jù)進(jìn)行預(yù)處理，提取出特征點(diǎn)，并采用密度聚類算法將特征點(diǎn)聚類為用戶的各個興趣區(qū)域，把原始軌跡數(shù)據(jù)離散化為由興趣區(qū)域組成的軌跡序列;然后，根據(jù)前綴軌跡序列與歷史軌跡序列模式樹的匹配程度來自適應(yīng)地確定模型階數(shù)k;最后，采用Adaboost算法根據(jù)1～k階Markov模型的重要程度為其賦予相應(yīng)的權(quán)重系數(shù)，組成多階融合Markov模型，從而實(shí)現(xiàn)對移動用戶未來興趣區(qū)域的預(yù)測。在大規(guī)模真實(shí)用戶軌跡數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，與1階Markov模型、2階Markov模型、權(quán)重系數(shù)平均的多階融合Markov模型相比， Adaboost-Markov模型的平均預(yù)測準(zhǔn)確率分別提高了20.83%、11.3%以及5.38%，且具有良好的普適性與多步預(yù)測性能。

關(guān)鍵詞：位置預(yù)測;興趣區(qū)域;Adaboost算法;多階融合Markov模型;權(quán)重系數(shù);自適應(yīng)

中圖分類號： TP311

文獻(xiàn)標(biāo)志碼：A

文章編號：1001-9081（2019）03-0675-06

Abstract： To solve the problem that Markov model has poor prediction accuracy and sparse matching in location prediction， a mobile user location prediction method based on Adaboost-Markov model was proposed. Firstly， the original trajectory data was preprocessed by a trajectory division method based on angle offset and distance offset to extract feature points， and density clustering algorithm was used to cluster the feature points into interest regions of the user， then the original trajectory data was discretized into a trajectory sequence composed of interest regions. Secondly， according to the matching degree of prefix trajectory sequence and historical trajectory pattern tree， the model order k was adaptively determined. Finally， Adaboost algorithm was used to assign the corresponding weight coefficients according to the importance degree of 1 to k order Markov models to form a multi-order fusion Markov model， realizing the prediction of future interest regions of the mobile user. The experimental results on a large-scale real user trajectory dataset show that the average prediction accuracy of Adaboost-Markov model is improved by 20.83%， 11.3%， and 5.38% respectively compared with the first-order Markov model， the second-order Markov model， and the multi-order fusion Markov model with average weight coefficient， and the proposed model has good universality and multi-step prediction performance.

Key words： location prediction; region of interest; Adaboost algorithm; multi-order fusion Markov model; weight coefficient; adaptivelyadaptation

0 引言

隨著智能移動終端普及率的提高以及移動空間定位技術(shù)的迅猛發(fā)展，基于位置的服務(wù)（Location Based Service， LBS）得到了廣泛應(yīng)用[1]。目前基于位置的服務(wù)主要包含定位查詢、路徑規(guī)劃和位置共享等功能，這些功能多集中于為用戶提供當(dāng)前位置的相關(guān)服務(wù)。為了使服務(wù)更具前瞻性，近年來大量國內(nèi)外學(xué)者把目光投向了移動用戶的位置預(yù)測上[2-3]。移動用戶位置預(yù)測具有很高的研究價值與廣闊的應(yīng)用前景，其中最直觀的應(yīng)用包括：1）個性化推薦與提醒。根據(jù)預(yù)測出的用戶下一步地點(diǎn)，可以針對用戶進(jìn)行個性化的推薦與提醒，例如系統(tǒng)預(yù)測出某個用戶的下一步地點(diǎn)為某個酒吧，可以向這位用戶推薦這個酒吧的促銷活動，以及推薦常去此酒吧的新朋友。2）可疑目標(biāo)追蹤。移動用戶位置預(yù)測可用于對可疑用戶進(jìn)行追蹤定位，例如在網(wǎng)上發(fā)表極端言論的用戶，通過預(yù)測目標(biāo)用戶的未來目的地，可以有效防范危害公共安全的惡性事件發(fā)生[4-5]。3）智能化交通。通過車載GPS（Global Positioning System）設(shè)備采集的大量軌跡數(shù)據(jù)可用于預(yù)測交通擁堵情況，從而便于司機(jī)規(guī)劃行駛路線以及提高出租車的調(diào)度效率[6]。

但是，移動用戶位置預(yù)測也是一項(xiàng)非常困難且富有挑戰(zhàn)性的工作。首先，由于城市內(nèi)高樓建筑的遮擋以及用戶隨意開關(guān)設(shè)備定位功能，容易造成部分重要數(shù)據(jù)的缺失以及訓(xùn)練數(shù)據(jù)的不足;其次，移動用戶的活動具有不確定性，在不同的時間周期內(nèi)，同一個用戶表現(xiàn)出的移動模式可能大相徑庭;再者，用戶的軌跡數(shù)據(jù)同時具有離散型和海量性，研究人員無法直接將原始數(shù)據(jù)用于位置預(yù)測，需要通過軌跡處理算法提取出重要數(shù)據(jù)，并過濾掉冗余數(shù)據(jù)以提高預(yù)測效率。

現(xiàn)有的研究方法主要通過建立用戶的歷史移動模式以及軌跡匹配進(jìn)行位置預(yù)測，常用的方法有馬爾可夫（Markov）模型[7-12]、隱馬爾可夫（Hidden Markov）模型[13]、高斯混合模型[14]以及卡爾曼濾波[15]等。

Markov模型以其良好的時序軌跡數(shù)據(jù)表示能力而成為應(yīng)用最為廣泛的位置預(yù)測模型之一。文獻(xiàn)[7]中余雪崗等[7]結(jié)合最大期望算法提出了1階1步與2步相結(jié)合的Markov模型，在一定程度上解決了低階Markov 預(yù)測精度差的問題。文獻(xiàn)[8]中呂明琪等[8]針對高階Markov模型中難以確定最優(yōu)階數(shù)的問題，提出了自適應(yīng)變階Markov模型，但其實(shí)質(zhì)與歷史模式匹配相同，根據(jù)最長匹配序列來確定階數(shù)，仍然存在匹配稀疏率高等問題。文獻(xiàn)[9]中Chen等[9]考慮了軌跡中的時間因素，提出了一種時間箱與Markov模型結(jié)合的位置預(yù)測算法。文獻(xiàn)[10]中宋路杰等[10]通過引入軌跡相似度對Markov模型的預(yù)測結(jié)果進(jìn)行修正，提高了預(yù)測的準(zhǔn)確率與穩(wěn)定性。文獻(xiàn)[11]中喬少杰等[11]提出了基于前綴投影數(shù)據(jù)庫的Markov模型，通過設(shè)置支持度閾值，將符合條件的前綴軌跡序列放入投影數(shù)據(jù)庫。該方法一定程度上解決了高階Markov模型中匹配稀疏率高的問題，但是建立投影數(shù)據(jù)庫的時間代價較大。文獻(xiàn)[12]中Killijian[12]提出了n-MMC（n-Mobility Markov Chain）模型來預(yù)測用戶位置，并驗(yàn)證了在n=2時預(yù)測效果最好。文獻(xiàn)[16]中Trasarti等[16]提出了MyWay方法對移動用戶進(jìn)行位置預(yù)測，該方法采用插值修正軌跡，接著通過設(shè)定啟發(fā)式閾值來尋找與待預(yù)測軌跡相似的歷史軌跡;但是該方法沒有對原始軌跡進(jìn)行預(yù)處理，預(yù)測出的結(jié)果粒度過細(xì)，導(dǎo)致計(jì)算量太大。文獻(xiàn)[17]中Monreale等[17]提出了WhereNext方法進(jìn)行位置預(yù)測，該方法首先通過網(wǎng)格劃分將原始軌跡數(shù)據(jù)離散化，隨后采用T模式樹挖掘用戶的頻繁移動模式，從而完成位置預(yù)測;但是，采用網(wǎng)格劃分方法進(jìn)行數(shù)據(jù)預(yù)處理必須以用戶的各個興趣區(qū)域規(guī)模相當(dāng)為前提，該方法可伸縮性較差，難以適用于大規(guī)模軌跡數(shù)據(jù)中。文獻(xiàn)[18]中Yuan等[18]提出了一種移動用戶多粒度周期性模型，用于發(fā)現(xiàn)個體行為規(guī)律，預(yù)測用戶未來位置;但是，該模型采用有監(jiān)督的學(xué)習(xí)方法識別個體行為，計(jì)算開銷較大。

針對現(xiàn)有方法存在的問題，本文首先采用軌跡劃分與密度聚類相結(jié)合的方法，將原始軌跡數(shù)據(jù)離散化為移動用戶的各個興趣區(qū)域，接著利用Adaboost算法為多階融合Markov模型合理確定權(quán)重系數(shù)，在充分利用歷史軌跡序列的基礎(chǔ)上，提高了預(yù)測準(zhǔn)確率，保證了模型的普適性。

1.1 軌跡劃分與興趣點(diǎn)提取

為了實(shí)現(xiàn)上述目的，本文提出了一種新的軌跡劃分方法，用于提取出軌跡中用戶行為變化較大的采樣點(diǎn)，并將它們作為特征點(diǎn)，每個特征點(diǎn)作為前一段子軌跡的終點(diǎn)與下一段子軌跡的起點(diǎn)，從而將一條完整軌跡劃分為若干條連續(xù)子軌跡。

低階Markov模型具有時間代價小、計(jì)算速度快的優(yōu)點(diǎn)，但是其預(yù)測精度不高，如1階Markov模型，它僅僅利用用戶當(dāng)前所在的興趣區(qū)域來預(yù)測下一個興趣區(qū)域，沒有充分利用前綴軌跡序列中所包含的信息。而高階Markov模型通常擁有更高的預(yù)測精度，但是隨之而來的是空間狀態(tài)膨脹與匹配稀疏問題，并且有研究[8]指出，隨著階數(shù)提高帶來的預(yù)測性能增長有一個極限。若Markov模型階數(shù)設(shè)定過高，如3階及以上Markov模型，它同時利用用戶當(dāng)前所在的興趣區(qū)域與前綴軌跡序列中的多個興趣區(qū)域來預(yù)測下一個興趣區(qū)域，在與用戶的歷史軌跡序列進(jìn)行匹配時，可能會導(dǎo)致匹配失敗或是僅僅匹配出極少數(shù)的歷史軌跡序列，即匹配稀疏，這樣反而會導(dǎo)致模型的預(yù)測性能降低。如圖2所示，以某位用戶的歷史軌跡序列模式樹為例，假設(shè)采用三階Markov模型，前綴軌跡序列為C2 → C4 → C5，并基于此移動模式樹預(yù)測用戶的下一興趣區(qū)域。但是，在此模式樹中并沒有以C2 → C4 → C5為前綴序列的歷史軌跡，三階Markov模型無法作出預(yù)測。針對此問題，文獻(xiàn)[8]提出了的自適應(yīng)多階Markov模型能夠在前綴序列與移動歷史模式樹匹配失敗時自動降階，直到匹配成功。然而，當(dāng)Markov模型的階數(shù)較高時，即使在用戶的歷史軌跡序列模式樹中找到以C2 → C4 → C5為前綴的序列，也極有可能存在匹配數(shù)量過少、稀疏率高等問題，從而導(dǎo)致預(yù)測效果不佳。

2 Adaboost-Markov建模

1階Markov模型僅僅利用了用戶當(dāng)前所在的興趣區(qū)域，對歷史軌跡序列的利用率不高;而高階Markov模型由于存在匹配困難、稀疏率高的問題，同樣存在無法充分利用歷史軌跡序列的問題。因此，將低階模型與高階模型相結(jié)合是一種可行的方法。那么，合理地確定各階模型對最終預(yù)測結(jié)果的影響系數(shù)，則是保證預(yù)測性能良好的重要前提。從宏觀上看，高階Markov模型通常具有更高的預(yù)測精度，在組合模型中應(yīng)該具有更大的“話語權(quán)”。為了確定各階模型的具體影響系數(shù)，本文提出了基于Adaboost-Markov模型的移動用戶位置預(yù)測方法。Adaboost算法作為一種代表性的提升方法，可以通過改變訓(xùn)練數(shù)據(jù)的概率分布以及弱分類器的權(quán)重系數(shù)，組合多個弱分類器，生成一個強(qiáng)分類器[17]。本文自適應(yīng)確定模型階數(shù)k，將1階至k階Markov模型作為k個弱預(yù)測器，通過Adaboost算法改變用戶軌跡數(shù)據(jù)的概率分布與各階Markov模型的權(quán)重系數(shù)，最終生成一個多階融合Markov模型用于預(yù)測用戶位置。

階數(shù)k由用戶前綴軌跡序列與歷史軌跡序列的最大匹配階長所決定。以圖3為例，用戶原始軌跡數(shù)據(jù)經(jīng)過預(yù)處理后建立了歷史軌跡序列庫，參與匹配的前綴軌跡序列長度通常有兩種方法確定：一是前綴軌跡序列與歷史軌跡序列的最大匹配長度，但是當(dāng)前綴軌跡序列過長時，采用這種方法會導(dǎo)致時間代價過高。二是人為指定參與匹配的前綴軌跡序列長度，由用戶確定參與匹配的前綴軌跡序列元素個數(shù)并輸入相應(yīng)長度的待預(yù)測前綴軌跡序列，若能在歷史軌跡序列庫中找到與前綴軌跡序列相同的序列，則匹配成功，并將此時前綴軌跡序列的元素個數(shù)設(shè)為模型階數(shù)k;否則，此次匹配失敗，則自動降階，去掉前綴軌跡序列中距離當(dāng)前最遠(yuǎn)的一個元素，并繼續(xù)在歷史軌跡序列庫中尋求匹配，重復(fù)以上步驟，直至匹配成功。

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

本文仿真實(shí)驗(yàn)環(huán)境為Windows10 64 位操作系統(tǒng)，Intel Core i7-6700HQ 2.60GHz CPU，8GB內(nèi)存，硬盤1TB。本實(shí)驗(yàn)中所采用的軌跡數(shù)據(jù)集來自于微軟亞洲研究院的Geolife項(xiàng)目[18]，該數(shù)據(jù)集包含182名用戶從2007年4月至2012年8月的軌跡采樣點(diǎn)，共有17621條軌跡，總距離為1292951km，總持續(xù)時間為50176h;并且，91.5%的軌跡以每1～5s或每5～10m記錄一次，能夠真實(shí)反映出用戶的生活習(xí)慣及行為模式。

為驗(yàn)證模型的有效性，本文對4種模型進(jìn)行對比實(shí)驗(yàn)：1階Markov模型、2階Markov模型、權(quán)重系數(shù)平均的多階融合Markov模型以及本文提出的Adaboost-Markov模型。其中，權(quán)重系數(shù)平均的多階融合Markov模型與Adaboost-Markov模型的區(qū)別在于，前者為1～k階Markov模型賦予相同的權(quán)重系數(shù)，而后者采用Adaboost算法根據(jù)各階模型的預(yù)測誤差調(diào)整對應(yīng)的權(quán)重系數(shù)。從Geolife軌跡數(shù)據(jù)集中隨機(jī)抽取90%用于訓(xùn)練上述模型，剩下10%的軌跡數(shù)據(jù)用于檢測預(yù)測性能。

為了方便量化表示算法的性能優(yōu)勢，本文采用如下性能評價指標(biāo)。

定義9 預(yù)測準(zhǔn)確率（Prediction Accuracy）。已知待預(yù)測軌跡序列T與由某個模型預(yù)測出的軌跡序列P，預(yù)測準(zhǔn)確率定義為：

首先，為驗(yàn)證使用Adaboost算法進(jìn)行權(quán)重系數(shù)分配的合理性，比較了不同前綴軌跡序列元素個數(shù)下Adaboost-Markov模型、權(quán)重系數(shù)均等的多階融合Markov模型與普通Markov模型的預(yù)測準(zhǔn)確率。

如圖4所示，橫軸表示前綴軌跡序列元素的個數(shù)，縱軸表示預(yù)測準(zhǔn)確率。對于普通Markov模型來說，前綴元素個數(shù)即等同于模型階數(shù)，而Adaboost-Markov模型與權(quán)重系數(shù)平均的多階融合Markov模型采用了自適應(yīng)確定模型階數(shù)k的匹配方法。因此，隨著前綴元素個數(shù)的增多，普通Markov模型的預(yù)測準(zhǔn)確率首先呈現(xiàn)出提升的趨勢，在2階時達(dá)到最大值，隨后由于階數(shù)的增多，匹配稀疏率逐漸增高，從而導(dǎo)致預(yù)測準(zhǔn)確率逐漸降低。Adaboost-Markov模型則有效克服了這一不足，其預(yù)測準(zhǔn)確率首先隨著前綴元素?cái)?shù)量的增加而提高，在前綴元素?cái)?shù)量為3時基本趨近于最大值，隨后預(yù)測準(zhǔn)確率一直穩(wěn)定在最大值附近。因此，在接下來的仿真實(shí)驗(yàn)中，Adaboost-Markov模型與權(quán)重系數(shù)平均的多階融合Markov模型均將前綴軌跡序列長度設(shè)為3。并且，從圖4中可以看出，通過Adaboost算法確定的模型權(quán)重系數(shù)是合理有效的，無論給定的待預(yù)測序列中前綴元素的數(shù)量怎樣變化，Adaboost-Markov模型的預(yù)測準(zhǔn)確率均高于權(quán)重系數(shù)平均的多階融合Markov模型。

接著，利用上述4種模型進(jìn)行單步預(yù)測，即預(yù)測用戶的下一個興趣區(qū)域，圖5和圖6分別展示了4種模型在小規(guī)模軌跡數(shù)據(jù)集及大規(guī)模軌跡數(shù)據(jù)集上的預(yù)測效果，橫軸代表軌跡序列長度，即用于預(yù)測的歷史軌跡序列庫中的元素個數(shù)，縱軸表示預(yù)測準(zhǔn)確率。

從圖5、6中觀察可以發(fā)現(xiàn)，本文提出的Adaboost-Markov模型對用戶下一步興趣區(qū)域預(yù)測的準(zhǔn)確率明顯高于1階Markov模型、2階Markov模型以及權(quán)重系數(shù)平均的多階融合Markov模型：在小規(guī)模軌跡數(shù)據(jù)集的實(shí)驗(yàn)中，與1階Markov模型、2階Markov模型以及權(quán)重系數(shù)平均的多階融合Markov模型相比，Adaboost-Markov模型的平均預(yù)測準(zhǔn)確率分別提高了39.73%、18.3%以及9.12%;在大規(guī)模軌跡數(shù)據(jù)集的實(shí)驗(yàn)中，與1階Markov模型、2階Markov模型以及權(quán)重系數(shù)平均的多階融合Markov模型相比，Adaboost-Markov模型的平均預(yù)測準(zhǔn)確率分別提高了20.83%、11.3%以及5.38%。隨著軌跡長度的增加，各模型預(yù)測準(zhǔn)確率的增長也趨于穩(wěn)定，因此在大規(guī)模軌跡數(shù)據(jù)集的實(shí)驗(yàn)中，各模型的準(zhǔn)確率曲線相對平緩。1階Markov模型和2階Markov模型由于對前綴軌跡序列的利用不夠充分，所以其預(yù)測準(zhǔn)確率的上升空間不大;而權(quán)重系數(shù)平均的多階融合Markov模型與Adaboost-Markov模型的預(yù)測準(zhǔn)確率均明顯高于1、2階Markov模型，這是因?yàn)闄?quán)重系數(shù)平均的多階融合Markov模型與Adaboost-Markov模型的前綴軌跡序列長度被設(shè)為3，當(dāng)歷史軌跡序列庫滿足匹配條件時，上述模型同時利用了1～3階Markov模型的前綴軌跡序列，充分利用了軌跡序列中所包含的移動模式信息，在歷史軌跡序列庫不符合匹配條件時，亦可自適應(yīng)降低前綴軌跡序列長度，相比于定階Markov模型具有更好的靈活性。權(quán)重系數(shù)平均的多階融合Markov模型雖然融合了各階Markov模型且較為充分利用了前綴軌跡序列，但是其沒有考慮到各階Markov模型的重要性差異問題，因此結(jié)合了Adaboost算法為各階模型合理分配權(quán)重系數(shù)的Adaboost-Markov模型具有更高的預(yù)測準(zhǔn)確率。

為了更為全面地比較4種模型的預(yù)測性能，隨機(jī)選用了Geolife項(xiàng)目中8名用戶的軌跡數(shù)據(jù)集。從圖7中可以看出，雖然四種模型在不同數(shù)據(jù)集上的預(yù)測準(zhǔn)確率存在一定范圍的波動，但是整體上的預(yù)測性能排名與之前的實(shí)驗(yàn)結(jié)果并無二致，與1階Markov模型、2階Markov模型以及權(quán)重系數(shù)平均的多階融合Markov模型相比，Adaboost-Markov模型的平均預(yù)測準(zhǔn)確率分別提高了23.14%、15.44%以及7.06%?？梢姳疚奶岢龅腁daboost-Markov模型具有良好的普適性，在不同數(shù)據(jù)集上的預(yù)測準(zhǔn)確率均好于另外3種模型。

在位置預(yù)測中，多步預(yù)測能力也是反映模型好壞的關(guān)鍵之一。多步預(yù)測即預(yù)測出用戶在n步之后所處的興趣區(qū)域。實(shí)驗(yàn)結(jié)果如圖8所示，從圖8中可以看出，隨著預(yù)測步長的增加，各模型預(yù)測準(zhǔn)確率的下降幅度均較為明顯，但是Adaboost-Markov模型在各步長的預(yù)測準(zhǔn)確率均優(yōu)于另外三種模型。原因在于，在進(jìn)行n步預(yù)測對比實(shí)驗(yàn)時，1、2階Markov模型采用n步轉(zhuǎn)移概率預(yù)測之后的興趣區(qū)域，相比于Adaboost-Markov模型的自適應(yīng)可變長序列的預(yù)測方式，1、2階Markov模型僅僅考慮了固定長度的軌跡序列，對于數(shù)據(jù)的適應(yīng)性不佳。

4 結(jié)語

本文針對Markov模型進(jìn)行位置預(yù)測時存在預(yù)測準(zhǔn)確率低與匹配稀疏等不足，采用軌跡劃分與密度聚類相結(jié)合的方法作為軌跡數(shù)據(jù)預(yù)處理手段，提出了Adaboost算法與多階融合Markov模型相結(jié)合的預(yù)測方法，充分利用了歷史軌跡序列，提高了預(yù)測準(zhǔn)確率。真實(shí)用戶軌跡數(shù)據(jù)集上的實(shí)驗(yàn)證明了本文方法在一定程度上解決了低階Markov模型預(yù)測準(zhǔn)確率低以及高階Markov模型匹配稀疏率高等問題，具有較高的預(yù)測準(zhǔn)確率以及良好的普適性。未來工作中，還將對上述模型進(jìn)一步優(yōu)化，更深入地研究軌跡數(shù)據(jù)的時空特性與群體特性，將天氣、時間（工作日與休息日）以及用戶相關(guān)的社交數(shù)據(jù)等因素考慮在內(nèi)，以期進(jìn)一步提高模型的預(yù)測準(zhǔn)確率。

參考文獻(xiàn) （References）

[1] 郭遲，劉經(jīng)南，方媛，等.位置大數(shù)據(jù)的價值提取與協(xié)同挖掘方法[J].軟件學(xué)報(bào)，2014，25（4）：713-730.（GUO C， LIU J N， FANG Y， et al. Value extraction and collaborative mining methods for location big data [J]. Journal of Software， 2014， 25（4）：713-730.）

[2] WIDHALM P， NITSCHE P， BRANDIE N. Transport mode detection with realistic smartphone sensor data [C]// Proceedings of the 21st International Conference on Pattern Recognition. Piscataway， NJ： IEEE， 2012： 573-576.

[3] SHIH D H， SHIH M H， YEN D C， et al. Personal mobility pattern mining and anomaly detection in the GPS era [J]. American Cartographer， 2016， 43（1）： 55-67.

[4] GUNDUZ S， YAVANOGLU U， SAGIROGLU S. Predicting next location of twitter users for surveillance [C]// Proceedings of the 12th International Conference on Machine Learning and Applications. Washington， DC： IEEE Computer Society， 2013： 267-273.

[5] BOGOMOLOV A， LEPRI B， STAIANO J， et al. Once upon a crime： towards crime prediction from demographics and mobile data [C]// ICMI '14： Proceedings of the 16th International Conference on Multimodal Interaction. New York： ACM， 2014： 427-434.

[6] QIAO S， HAN N， ZHU W， et al. TraPlan： an effective three-in-one trajectory-prediction model in transportation networks [J]. IEEE Transactions on Intelligent Transportation Systems， 2015， 16（3）： 1188-1198.

[7] 余雪崗，劉衍珩，魏達(dá)，等.用于移動路徑預(yù)測的混合Markov模型[J].通信學(xué)報(bào)，2006，27（12）：61-69. （YU X G， LIU Y H， WEI D， et al. Hybrid Markov model for mobile path prediction [J]. Journal on Communications， 2006， 27（12）： 61-69.）

[8] 呂明琪，陳嶺，陳根才.基于自適應(yīng)多階Markov模型的位置預(yù)測[J].計(jì)算機(jī)研究與發(fā)展，2010，47（10）：1764-1770.（LYU M Q， CHEN L， CHEN G C. Position prediction based on adaptive multi-order Markov model [J]. Journal of Computer Research and Development， 2010， 47（10）： 1764-1770.）

[9] CHEN M， YU X， LIU Y. Mining moving patterns for predicting next location [J]. Information Systems， 2015， 54： 156-168.

[10] 宋路杰，孟凡榮，袁冠.基于Markov模型與軌跡相似度的移動對象位置預(yù)測算法[J].計(jì)算機(jī)應(yīng)用，2016，36（1）：39-43.（SONG L J， MENG F R， YUAN G. Moving object location prediction algorithm based on Markov model and trajectory similarity [J]. Journal of Computer Applications， 2016， 36（1）： 39-43.）

[11] 喬少杰，韓楠，李天瑞，等.基于前綴投影技術(shù)的大規(guī)模軌跡預(yù)測模型[J].軟件學(xué)報(bào)，2017，28（11）：3043-3057.（QIAO S J， HAN N， LI T R， et al. Large-scale trajectory prediction model based on prefix projection technique [J]. Journal of Software， 2017， 28（11）： 3043-3057.）

[12] KILLIJIAN M O. Next place prediction using mobility Markov chains [C]// MPM '12： Proceedings of the 1st Workshop on Measurement， Privacy， and Mobility. New York： ACM， 2012： Article No. 3.

[13] QIAO S J， SHEN D， WANG X， et al. A self-adaptive parameter selection trajectory prediction approach via hidden Markov models [J]. IEEE Transactions on Intelligent Transportation Systems， 2015， 16（1）： 284-296.

[14] 喬少杰，金琨，韓楠，等.一種基于高斯混合模型的軌跡預(yù)測算法[J].軟件學(xué)報(bào)，2015，26（5）：1048-1063.（QIAO S J， JIN K， HAN N， et al. Trajectory prediction algorithm based on Gaussian mixture model [J]. Journal of Software， 2015，26（5）：1048-1063.）

[15] PATHIRANA P N， SAVKIN A V， JHA S. Robust extended Kalman filter applied to location tracking and trajectory prediction for PCS networks [C]// Proceedings of the 2004 IEEE International Conference on Control Applications. Piscataway， NJ： IEEE， 2004， 1： 63-68.

[16] TRASARTI R， GUIDOTTI R， MONREALE A， et al. MyWay： location prediction via mobility profiling [J]. Information Systems， 2017， 64： 350-367.

[17] MONREALE A， PINELLI F， TRASARTI R， et al. WhereNext： a location predictor on trajectory pattern mining [C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009： 637-646.

[18] YUAN G， ZHAO J， XIA S， et al. Multi-granularity periodic activity discovery for moving objects [J]. International Journal of Geographical Information Systems， 2016， 31（3）： 435-462.

[19] 楊震，王紅軍，周宇.一種截?cái)嗑嚯x和聚類中心自適應(yīng)的聚類算法[J].數(shù)據(jù)分析與知識發(fā)現(xiàn)，2018，2（3）：39-48.（YANG Z， WANG H J， ZHOU Y. A clustering algorithm by adaptive cut-off distances and cluster centers [J]. Data Analysis and Knowledge Discovery， 2018， 2（3）： 39-48.）

[20] 李航.統(tǒng)計(jì)學(xué)習(xí)方法[M].北京：清華大學(xué)出版社， 2012：137-139.（LI H. Statistical Learning Method [M]. Beijing： Tsinghua University Press， 2012： 137-139.）

[21] ZHENG Y， CHEN Y， XIE X， et al. GeoLife2.0： alocation-based social networking service [C]// Proceedings of the 2009 10th International Conference on Mobile Data Management： Systems， Services and Middleware. Washington， DC： IEEE Computer Society， 2009： 357-358.