楊震 王紅軍

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

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

中圖分類號(hào)： TP311

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

文章編號(hào)：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 引言

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

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

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

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

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

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

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

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

2 Adaboost-Markov建模

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

階數(shù)k由用戶前綴軌跡序列與歷史軌跡序列的最大匹配階長(zhǎng)所決定。以圖3為例，用戶原始軌跡數(shù)據(jù)經(jīng)過預(yù)處理后建立了歷史軌跡序列庫(kù)，參與匹配的前綴軌跡序列長(zhǎng)度通常有兩種方法確定：一是前綴軌跡序列與歷史軌跡序列的最大匹配長(zhǎng)度，但是當(dāng)前綴軌跡序列過長(zhǎng)時(shí)，采用這種方法會(huì)導(dǎo)致時(shí)間代價(jià)過高。二是人為指定參與匹配的前綴軌跡序列長(zhǎng)度，由用戶確定參與匹配的前綴軌跡序列元素個(gè)數(shù)并輸入相應(yīng)長(zhǎng)度的待預(yù)測(cè)前綴軌跡序列，若能在歷史軌跡序列庫(kù)中找到與前綴軌跡序列相同的序列，則匹配成功，并將此時(shí)前綴軌跡序列的元素個(gè)數(shù)設(shè)為模型階數(shù)k;否則，此次匹配失敗，則自動(dòng)降階，去掉前綴軌跡序列中距離當(dāng)前最遠(yuǎn)的一個(gè)元素，并繼續(xù)在歷史軌跡序列庫(kù)中尋求匹配，重復(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ù)時(shí)間為50176h;并且，91.5%的軌跡以每1～5s或每5～10m記錄一次，能夠真實(shí)反映出用戶的生活習(xí)慣及行為模式。

為驗(yàn)證模型的有效性，本文對(duì)4種模型進(jìn)行對(duì)比實(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ù)測(cè)誤差調(diào)整對(duì)應(yīng)的權(quán)重系數(shù)。從Geolife軌跡數(shù)據(jù)集中隨機(jī)抽取90%用于訓(xùn)練上述模型，剩下10%的軌跡數(shù)據(jù)用于檢測(cè)預(yù)測(cè)性能。

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

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

[1] 郭遲，劉經(jīng)南，方媛，等.位置大數(shù)據(jù)的價(jià)值提取與協(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á)，等.用于移動(dòng)路徑預(yù)測(cè)的混合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ù)測(cè)[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模型與軌跡相似度的移動(dòng)對(duì)象位置預(yù)測(cè)算法[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ù)測(cè)模型[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ù)測(cè)算法[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ù)分析與知識(shí)發(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.