基于運動趨勢的移動對象位置預測

李雯，夏士雄，劉峰，張磊，袁冠

（1.中國礦業大學 計算機科學與技術學院，江蘇 徐州 221116；2.中國煤炭工業協會，北京 100713）

1 引言

移動對象空間定位技術的快速發展極大地推動了基于位置服務的廣泛應用，為了使服務具有前瞻性，不僅要對移動對象當前活動的位置進行分析，更要能夠對其位置進行預測。移動對象位置預測是一項具有挑戰性的工作，主要原因如下：由于GPS等定位設備具有采樣盲點，移動對象在封閉空間內的位置信息無法被捕獲，造成移動對象軌跡數據的部分缺失，這些缺失的部分往往可能是移動對象活動較為重要的區域，因此，軌跡數據的缺失和不完整，大大增加了移動對象活動的預測難度；移動對象的運動具有不確定性，不同周期內移動對象的活動模式不完全相同；移動對象軌跡的時空信息具有離散性和瑣碎性，無法將原始軌跡直接用于移動對象未來位置的預測。

現有的位置預測方法大多在移動對象歷史行為模式[1,2]或關聯規則[3]的基礎上進行位置預測。文獻[1]提出基于軌跡模式的位置預測方法WhereNext，考慮移動對象的群體模式，卻忽略了對象間的相似性以及相似對象活動模式間的局部匹配性，預測準確性不高。文獻[3]使用匹配函數從提取的關聯規則中發現最佳規則，進而對位置進行預測。文獻[4]中提出HDTP算法考慮移動對象位置的時空信息，使用軌跡常見運動模式對位置進行預測。文獻[5]提出 PPM-C算法將移動對象近期活動區域序列與歷史活動模式進行完全匹配，發現最長匹配序列，并將匹配序列的后續區域作為未來位置的候選。此外，多種預測模型被應用至位置預測中，例如，貝葉斯網絡[6]、馬爾可夫[7,8]或隱馬爾可夫模型[9]、神經網絡方法[10]以及狀態預測[11]等方法。文獻[12]提出基于對象運動模式預測未來路徑和目的地的方法。文獻[13]將軌跡定義為移動對象運動時穿過的網格的邊的有序集合，在此基礎上提出Traj-PrefixSpan算法發現頻繁軌跡以及移動對象運動模式，進而進行預測。另外，文獻[5,8]中介紹了使用手機基站數據集進行預測的方法，應用熵計算從當前基站到達下一個基站的最大概率上限。

以上文獻大多從宏觀角度分析移動對象興趣區域間的轉換關系，考慮移動對象興趣區域間運動的研究不多，這樣存在2個問題：1）對象活動模式強調移動對象若干活動間的順序性，由于運動的不確定性，距離較近的區域間的訪問順序可能不固定；2）在移動對象歷史活動記錄中，一個興趣區域之后的候選訪問區域可能包含多個，僅依靠興趣區域間的歷史訪問習慣很難準確地篩選最佳興趣區域。

本文提出一種基于運動趨勢的移動對象位置預測算法(LP-MT,location prediction algorithm based on movement tendency)，使用基于馬爾可夫的移動對象活動模型記錄相鄰訪問區域間的轉換關系，在保證區域訪問有序性的同時，有效地擺脫對傳統模式匹配的依賴，降低運動不確定性帶來的影響。另外，由于對象從同一興趣區域出發，至不同區域間的運動路徑不可能完全相同，有各自的運動特征，因此移動對象的運動趨勢對位置預測具有指導意義。以往算法僅將歷史記錄中最近停留區域后的已訪問區域作為預測的候選，本文將移動對象的所有歷史停留區域作為未來位置的候選，并根據位置的特征，將算法結果分為預測位置和推薦位置。真實數據的實驗表明，算法可以對移動對象未來位置進行有效、高效的預測，較同類算法相比，預測精度提高10%左右。

2 基于運動趨勢的移動對象位置預測模型

基于運動趨勢的移動對象位置預測算法（LP-MT）包括移動對象歷史活動模型的訓練以及未來位置的預測2個階段。

在訓練階段（如圖 1所示），對移動對象歷史活動模式進行學習。首先，采用文獻[14]中介紹的基于時間距離約束的網格聚類算法，從原始軌跡中提取歷史停留區域集合，集合中的停留位置將作為未來位置的候選，該集合稱為潛在停留區域集合（圖1中潛在停留區域集合為{A,B,C,D}）。其次，移動對象歷史軌跡被表示為潛在停留區域的序列（如圖 1 中A-＞B-＞C-＞A-＞B-＞D-＞A），序列反映了移動對象的歷史活動模式，訪問順序以及訪問次數反映了移動對象運動的規律以及對各區域的喜好程度。最后，以潛在停留區域序列為輸入，建立基于馬爾可夫的移動對象活動模型。

圖1 LP-MT算法訓練階段示意

圖2 LP-MT算法預測階段示意

未來位置預測過程（如圖2所示）中，首先將移動對象最近停留區域結合基于馬爾可夫的移動對象活動模型進行初步預測。其次，將最近停留區域至當前位置間的軌跡段對應至停留區域提取時劃分的網格中，將軌跡點序列轉換為網格序列（如圖 2中g16,4-＞g15,4-＞g15,5），使用網格序列中提取的移動對象運動特征描述移動對象的近期運動趨勢，根據運動趨勢對移動對象未來位置進行進一步的預測。最后，根據未來位置的分類規則，給出綜合預測結果。

2.1 基于移動對象活動模型的預測

目前，移動對象未來位置預測算法大多通過挖掘移動對象軌跡的頻繁模式來發現其歷史停留區域間的關聯關系。在現實世界中，部分停留區域可能較為集中，移動對象對這些區域的訪問順序有很大的隨機性。假設3個停留區域A、B、C間的距離較小，D、E為距離A、B、C較遠的2個區域，移動對象歷史活動模式中包含以下序列：A-＞B-＞C-＞D，A-＞B-＞C-＞E，B-＞A-C-＞E，B-＞C-＞A-＞D。若移動對象的近期停留區域序列為B-＞A-＞C，完全匹配歷史活動模式時，預測結果為E。然而，A、B、C間的距離較近，區域訪問具有不確定性，因此D作為未來停留區域的概率也較大。另外，對象近期停留區域序列的長度很難選取。本文借鑒馬爾可夫模型的思想，提出基于馬爾可夫的移動對象活動模型，考慮相鄰停留區域間的轉換，對移動對象歷史活動建模。

馬爾可夫模型[15]由一系列狀態以及狀態轉移矩陣組成，第n次轉換獲得的狀態只和第n-1次的狀態有關。移動對象的歷史停留區域序列SRL={SR1,SR2,…,SRN}可以被表示為狀態變量序列XL={X1,X2,…,XN}。若移動對象潛在停留區域的數量為m，則狀態空間集合EL=＜E1,E2,…,Em＞，每個停留區域對應一個狀態，移動對象在某一時刻只能處于一種狀態。根據移動對象的當前狀態以及狀態間轉移關系，可以粗略估計移動對象的后續狀態。

若移動對象最近停留區域為SRr，歷史記錄中區域 SRr后已訪問的停留區域集合為SRLN={SRl1,SRl2,…,S Rls}，SRr和SRli是移動對象連續訪問區域，SRli稱為SRr的后續停留區域，本文將移動對象最近停留區域的后續停留區域集合 SRLN稱為預測停留區域集合。最近停留區域SRr在狀態空間集合中的對應狀態為Er，Er的后續狀態集合為ELN={El1,El2,…,Els}。狀態 Er至后續狀態 Eli的一步轉移概率 PMarr,li=P(Er→Eli)=P(Xn+1=Eli|Xn=Er)體現了停留區域 SRli作為停留區域SRr的未來位置的可能性。預測停留區域集合 SRLN中的區域作為最近停留區域SRr的未來位置的概率集合PMarL={PMarr,l1,P Marr,l2,… PMarr,ls}。

2.2 基于移動對象運動趨勢的預測

移動對象活動模型從停留區域的角度對移動對象活動習慣進行描述，而對象近期運動趨勢也能夠指導移動對象未來位置的預測。例如，對象從停留區域A出發可能到達B和C，但B、C分別在區域A的左側和右側。若對象從A出發向左走，距離B越來越近，則盡管歷史記錄中到達C的概率較大，根據移動對象的近期運動趨勢可以發現，B更可能為移動對象的未來停留位置。因此本文在考慮停留區域間關系的同時，也考慮移動對象的近期運動趨勢，使用移動對象運動方向以及與各潛在停留區域的距離對移動對象運動趨勢進行描述。

移動對象軌跡中距離當前時間越近的信息越能反映移動對象的近期運動趨勢，對預測結果的影響越大。本文將移動對象最近停留區域至當前位置間的軌跡段轉換為網格序列，首先計算網格序列至各潛在停留區域的距離概率和方向概率，然后根據距離權重和方向權重得到綜合概率，用來描述運動趨勢對各潛在停留區域作為未來位置的影響。

1)至潛在停留區域的距離概率

從宏觀角度，移動對象至目標位置的距離應越來越短。本文認為移動對象趨向于向距離當前位置較近的停留區域運動，若一段時間內，移動對象距離區域X越來越近，則移動對象下一個停留區域為X的概率較大。為了將距離標準轉換為概率，假設當前網格到各潛在停留區域的最遠、最近距離分別為Dmax、Dmin，到達X的距離為DX，則從當前網格到達 X 的概率為Pd(X)=1?(DX?Dmin)/(Dmax?Dmin)。網格序列GL={G1,G2,…,Gs}至潛在停留區域X的距離概率集合為PLd={Pd1(X),Pd2(X),…,Pds(X)},則網格序列至X的綜合距離概率為

2)至潛在停留區域的方向概率

移動對象向目標位置移動過程中，整體行進方向會趨向于目標位置的方向。當前網格與前一網格以及停留區域代表網格間都存在方向向量。若隨對象運動、方向向量間夾角越來越小，則停留區域為目標位置的概率較大。假設當前網格的第一個樣本點為pi+1，前一網格中最后一個樣本點為pi，則方向向量，區域 X代表網格的中心點為r'=(x,y)，則當前網格至X的方向向量為，當前網格至區域X的方向概率為Pa(X)=cos。網格序列 GL=＜G1,G2,…,Gs＞至區域 X的方向概率集合為PLa=＜Pa1(X),Pa2(X),…,Pas(X))＞，則網格序列至X的綜合方向概率為

若綜合距離概率和綜合方向概率的權重分別為WD和WA，則網格序列至X的綜合概率

假設移動對象潛在停留區域集合為SRL={SR1,SR2,…,SRm}，反映移動對象近期運動趨勢的網格序列GL=＜G1,G2,…,Gs＞，則根據網格序列計算至潛在停留區域集合 SRL中的各個區域的綜合概率集合PMovL={PMov1,PMov2,…,PMovm}。

2.3 移動對象未來位置的分類

移動對象未來位置可以分為三類：一是預測停留區域集合中的位置，即歷史數據中記錄的最近停留區域的后繼停留區域；二是潛在停留區域集合中預測停留區域外的其余停留區域，這類區域單純依靠軌跡模式是無法得到的；最后一類是移動對象未出現過的區域，這類區域無法通過單個對象的歷史數據得到，需要分析和當前對象相似的多個對象才能給出合適的結果。本文只考慮前兩類位置，即預測位置和推薦位置。

移動對象可能在其歷史停留區域集合中的任意位置停留，因此潛在停留區域集合中的區域將作為未來位置的候選。潛在停留區域 X作為移動對象未來位置的可能性大小被定義為區域 X的可達性，表示為PRX。若一段時間內，移動對象到達停留區域 X的可達性都較高，則移動對象運動到區域X的可能性最大。

針對預測位置和推薦位置，LP-MT算法得到預測區域可達性列表和推薦區域可達性列表。預測區域可達性列表對應上述第一類，包含預測區域列表以及各個區域的可達性，其中預測區域列表按照區域可達性遞減的順序排列。通過基于馬爾可夫的移動對象活動模型和運動趨勢的綜合計算可得到預測區域的可達性。推薦區域可達性列表為上述第二類位置，包含推薦區域列表以及各個區域的可達性，其中推薦區域列表按照區域可達性遞減的順序排列。推薦區域的可達性可通過對移動對象近期運動趨勢的分析得到。

若移動對象最近停留區域SRr與基于馬爾可夫的移動對象活動模型匹配得到的移動對象預測停留區域的概率集合為PMarL={PMarl1,PMarl2,…,PMarls}，根據移動對象近期運動趨勢得到的所有潛在停留區域的綜合概率集合 PMovL={PMov1,PMov2,…,PMovm}。預測區域列表由預測停留區域集合組成，預測區域可達性列表的概率集合為PRLPre={PRl1,P Rl2,…,P Rls}，其中 PRli=PMarli+PMovli,PRli＞PRli+1,i∈{1,s} 。推薦區域可達性列表集合為SRLCom={SRj| SRj∈SRL∧SRj?SRLN}，列表中的區域按照可達性遞減的順序排列，區域 SRj的可達性為PRj=PMovj，PRj＞PRj+1。

3 基于運動趨勢的移動對象位置預測算法

3.1 算法描述

LP-MT包含2個階段：1）訓練階段，移動對象歷史數據作為訓練數據集，提取歷史停留區域及歷史活動序列，并以此建立基于馬爾可夫的移動對象活動模型；2）預測階段，根據移動對象最近停留區域以及運動趨勢進行分步預測。

LP-MT 算法 輸入：TTrain(訓練軌跡)，TTest(測試軌跡)，Dth(最小距離閾值)，Tth(最小時間閾值)，GHorGVer(網格數量)，WD(距離權重)，WA(方向權重)

輸出：SRLPre(預測可達性列表)，SRLCom(推薦可達性列表）

/*訓練階段*/

1)SR=FindStayRegions(TTrain,Dth,Tth,GHor×GVer); /*發現停留區域集合*/

2)SRL=ExtractActivitiesList(SR); /*提取歷史活動序列*/

3)MarkovM=BuildMarkovModel(SRL); /*建立基于馬爾可夫的移動對象活動模型*//*預測階段*/

4)SRr=FindRecentSR(TTest,Dth,Tth,GHor×GVer);/*發現移動對象最近停留區域*/

5)GL=AbstractGridsList(TTest,SRr,GHor×GVer);/*提取反映運動趨勢的網格序列*/

6)PMarL=CalPredReachList(SRr,MarkovM);/*計算至預測停留區域的概率集合*/

7)PL=CalSynP(GL,SRL ,Wd,Wa); /*計算至潛在停留區域的概率集合*/

8)PMovL=CalPontitalReachList(PL,SRL); /*計算至潛在停留區域可達性*/

9)SRLPre=SynPreReachList(PMarL,PMovL);/*預測可達性列表*/

SRLCom=SynCommReachList(PMovL); /*推薦可達性列表*/

3.2 算法性能分析

LP-MT算法時間主要消耗在移動對象歷史活動的發現以及基于對象運動趨勢的預測上。歷史活動模式發現的時間復雜度為O(n)，n為移動對象訓練軌跡樣本點數量。利用運動趨勢進行預測的時間復雜度為O(ms)，其中m為移動對象歷史停留區域的數量，s為最近停留區域至當前位置的網格數量。為確保算法具有較高的時間效率，當真實停留區域確定后，可以對活動模型進行調整和更新。當預測次數小于對象活動模型最大更新上限時，歷史活動模式重建的時間被更新對象活動模型的時間代替，對象活動模型更新的時間復雜度為O(m)。

4 實驗及分析

為了驗證本文提出的基于運動趨勢的移動對象位置預測算法，采用Visual C# 2005開發了移動對象未來位置預測系統 LP-MT，軌跡數據存儲在SQLServer 2000中。實驗進行的軟硬件環境包括：Windows XP，Lenovo ThinkCentre (Duro 2，2.8G的CPU，3G內存)。實驗數據集使用2007年希臘雅典市區卡車(Trucks)的運動軌跡[16]。

4.1 參數影響

本實驗測試網格數量對于基于馬爾可夫的移動對象活動模型的健壯性的影響，選取Trucks數據集中ID=900的軌跡進行實驗，設定最小距離閾值Dth=400 m，最小時間閾值Tth=5 min，由于對象運動時對方向和距離的無意識性，設定 WD=WA=0.5。圖3顯示不同網格數量和訓練集規模時，馬爾可夫模型狀態數、網格序列數以及運行時間的變化情況。

通過圖3可以看出，基于馬爾可夫的對象活動模型的狀態數隨著網格數量增加而增加，相同網格大小，不同數據樣本規模時，對象活動模型的狀態數增勢平緩；另外，預測時間隨網格數量增加略微增加，但增速緩慢。以軌跡10%的數據量為梯度，選擇數據量的30%～80%作為預測模型的訓練樣本，進行6次未來位置的預測。當網格數量為10×10時，共計產生 3次推薦和 3次預測，預測準確率為100%。3次推薦中，真實停留區域分別位于推薦區域可達性列表的1、2、2位，此時狀態數較少，因此實驗結果較理想。網格數量為30×25時共產生4次預測和2次推薦。4次預測中實際停留區域分別位于預測區域可達性列表的 1、1、2、4位，推薦中實際位置分別位于推薦區域可達性列表的 3、4位。網格數量增加并沒有使預測準確率增加，主要原因是：雖然網格數量增加使得對象活動模型更加健壯，但是精細劃分的網格使得原本聯系緊密的狀態被分割，對象很小的動作被分離出來，增加預測誤差。而且反映對象運動趨勢的網格序列至潛在停留區域的距離以及偏轉趨勢受網格數量的影響，很小的距離或方向偏差可能對預測結果有很大影響。因此，網格大小的選擇應該適中。

圖3 不同網格數量和數據規模對LP-MT算法的影響

4.2 預測精度

為了檢驗預測精度，本文采用增量驗證方式，選取Trucks數據集中ID=870的軌跡進行分組實驗。為了衡量基于運動趨勢的移動對象位置預測算法的準確性，給出評價預測精度的預測準確率和推薦準確率、預測誤差率和推薦誤差率2組概念。假定預測次數為N，真實停留區域位于預測可達性列表首位的次數為PN，則預測準確率PAPre=PN/N。同理，假設真實停留區域位于推薦可達性列表首位的次數為RN，則推薦準確率 PACom=RN/N。假設移動對象當前位置至真實停留區域的距離為Dc-r，預測位置至真實停留區域的距離為Dp-r，則預測誤差率PFPre=Dp-r/Dc-r。同理，若推薦位置至真實停留區域的距離為Drec-r，則推薦誤差率PFCom=Drec-r/Dc-r。當前位置至真實停留區域的距離越大，預測產生誤差的概率越大，因此根據Dc-r與Dp-r的比值來衡量算法的誤差率比較合理。預測誤差率或推薦誤差率越小，則預測位置或推薦位置越接近真實位置，算法精度越高。

1)不同訓練樣本比例

該實驗主要用于測試在歷史數據充分學習的情況下，算法的預測精度。選取整條軌跡30%～85%的數據量作為訓練樣本，訓練樣本的結束點作為移動對象的當前位置開始預測。

從表1可以看出，訓練樣本比例與馬爾可夫模型狀態數成正比。實驗表明馬爾可夫模型中10%～20%的狀態有3個及3個以上的轉換狀態，20%～30%的狀態有2個轉換狀態，其余包含一個轉換狀態，極少數情況下，不包含轉換狀態，此時，移動對象首次到達該停留區域且沒有移動至下一區域。使用不同數據集建立的馬爾可夫模型的狀態轉換情況有所不同。

表1 Truck數據不同訓練樣本比例對馬爾可夫模型狀態數量的影響

算法結果由預測可達性列表以及推薦可達性列表共同決定。預測中無法判斷真實停留區域位于哪類結果中，因此預測誤差率和推薦誤差率的最小值決定了算法的綜合誤差率。圖4描述了不同訓練樣本比例下誤差率的變化情況，從圖中的曲線可以看出，算法綜合誤差率基本在0.1以下，預測精度較高。

圖4 不同訓練樣本比例下的誤差率

以3%的數據集為一個梯度，25次實驗中共產生5次推薦和20次預測。推薦準確率達到40%。20次預測結果中，僅根據基于馬爾可夫的移動對象活動模型預測的準確率達到50%。增加考慮移動對象運動趨勢可提高 24%的預測成功率，其余情況下，結合運動趨勢也可以使準確率在簡單的一步預測的基礎上有顯著提高。實驗表明算法在不同訓練樣本比例下都具有較高準確性。

2)訓練集規模

該實驗主要測試當歷史數據量較少時，預測結果的準確性。選取整條軌跡 30%～90%間不同梯度的數據量作為訓練樣本，以90%處的樣本點作為移動對象當前位置。

從圖5中的曲線可以看出，訓練集規模較小時，推薦結果的準確率較高，這是由于此時移動對象歷史數據較少，僅依靠歷史停留區域間的轉換關系無法準確預測，但是移動對象近期運動趨勢能夠反映對象活動意圖，從而提高推薦準確性。圖5顯示推薦誤差率趨近于 0，表明本文選取距離和方向作為反映運動趨勢的標準較為合理。隨著訓練集規模的增加，預測結果更加準確，綜合誤差率基本小于0.3。因此，歷史數據量較少時，運動趨勢能夠很好地對未來位置進行推薦，隨著歷史數據集規模的增大，預測精度則越來越高。

3)學習充分性

該實驗用于檢驗基于馬爾可夫的移動對象活動模型能否充分學習對象的歷史活動模式。選取整條軌跡50%～100%之間的數據進行訓練，從軌跡的45%處開始預測。以5%的數據集為一個梯度，20次實驗的預測誤差率全部為0，實驗表明對象活動模型能夠準確、全面地反映移動對象的歷史活動模式。

圖5 訓練集規模與誤差率間關系

4)算法穩定性

該實驗主要用于測試算法的穩定性。選取整條軌跡為訓練集，從軌跡的 30%～90%之間隨機選取若干位置作為移動對象的當前位置開始預測。若隨機選取一系列位置，誤差率集合PFL={PF1,PF2,…,PFn}，則?1≤i≤n，第 i次預測的平均誤差率為。平均誤差率反映了算法在多次預測中的持續預測能力，體現了算法的穩定性。圖6顯示算法的平均綜合誤差率維持在0.1以下，預測精度較高且較為穩定。另外，對于不同的數據集都有較好的效果，算法的適應性和可移植性較強。

圖6 測試位置與平均誤差率的關系

4.3 移動對象活動模型的更新有效性

該實驗主要測試算法更新的有效性以及最大的更新次數。以50%的數據量為訓練數據集對移動對象位置開始連續預測，根據真實停留區域對對象活動模型進行 55次更新。在實際情況中，移動對象的真實停留區域會與歷史停留區域有一定的偏差，但如果重疊面積較大，本文認為是同一個停留區域。從圖7中的曲線可以看出，前20次更新中，綜合誤差率基本在0.2以下波動，為可接受的誤差范圍。然而，在20次更新之后，算法的綜合誤差率開始增加，甚至達到 0.5。多次更新過程中，移動對象在同一區域出現的位置可能發生變化。因此，更新策略可保證算法在一定次數內的更新是有效的。本實驗環境下，20次更新后需要對對象活動進行重新建模。

圖7 馬爾可夫模型的更新對誤差率的影響

4.4 同類算法性能比較

PPM-C算法與LP-MT算法都是對移動對象位置進行預測的方法，在同類算法中，PPM-C算法的性能較好，具有一定代表性。為了比較 LP-MT算法與 PPM-C算法的性能，本文選取整條軌跡數據量的 30%～90%作為訓練樣本，以 90%處的樣本點作為預測起始位置。圖8和圖9顯示與PPM-C算法相比，LP-MT具有較好的預測效果和運行速度。

圖8 PPM-C與LP-MT算法誤差率比較

圖9 PPM-C與LP-MT算法運行時間比較

圖8比較了LP-MT與PPM-C使用相同訓練集，從同一位置開始預測的綜合誤差率。當訓練樣本規模占數據集總量的30%～60%時，PPM-C算法的綜合誤差率基本在0.7以上，同等情況下，LP-MT算法的綜合誤差率小于0.3。訓練樣本規模大于數據集總量的70%時，2種算法的綜合誤差率均小于0.3，LP-MT算法的綜合誤差率略低。主要由于：1）PPM-C主要依靠學習歷史數據來對移動對象未來位置進行預測，當訓練樣本較小時，PPM-C對歷史活動學習不夠充分，無法得到較為準確的預測結果，而LP-MT算法在學習不充分時，使用移動對象近期運動趨勢對結果進行補充，確保算法具有較好的預測效果；2）PPM-C僅考慮歷史數據中最近停留區域的后繼停留區域集合，忽略了移動對象運動的不確定性，LP-MT算法在考慮預測停留區域的同時，計算至所有潛在停留區域的可達性，提高預測精度。

圖9比較了LP-MT與PPM-C算法的運行時間，PPM-C算法的運行時間隨訓練樣本規模的增大迅速增加，而LP-MT算法的運行時間變化較為平緩。若移動對象潛在停留區域的數量為n，停留區域序列的長度為N(N＞＞n)，PPM-C算法中order表的規模與N成正比，隨著訓練樣本規模的增加，order表的規模迅速增加，而LP-MT只需根據 n個歷史停留區域集合進行建模。另外，每次預測時，PPM-C算法依次縮短近期停留區域序列與order表中各層進行完全匹配，使得預測時間較長。因此，訓練樣本規模較大時，PPM-C算法的運行時間遠遠大于LP-MT算法的運行時間。

5 結束語

針對目前移動對象位置預測大多只考慮移動對象歷史活動模式，導致預測精度不高且預測結果較為局限的問題，提出一種基于運動趨勢的移動對象位置預測算法，不僅使用移動對象最近停留區域和移動對象活動模型中存儲的移動對象歷史活動模式進行匹配給出初步預測，還綜合考慮移動對象最近運動趨勢，估計各潛在停留區域作為未來位置的概率。根據移動對象未來位置的特征，將潛在停留區域分為預測停留區域以及非預測停留區域，分別對應預測位置和推薦位置。應用真實數據的實驗表明，與其他同類算法相比，LP-MT算法預測精度提高近10%。在保證較高時間效率的同時，具有較好的準確性。下一步將在本文研究的基礎上，考慮移動對象的群體性以及多移動對象的局部相似性，使用多個對象的軌跡數據對未來位置進行預測。

[1]MONREALE A,PINELLI F,TRASARTI R. Where next: a location predictor on trajectory pattern mining[A]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C]. New York,2009. 637-646.

[2]YOON H,SHAHABI C. Robust time-referenced segmentation of moving object trajectories[A]. ICDM '08,Eighth IEEE International Conference on Data Mining[C]. 2008. 1121-1126.

[3]MORZY M. Mining frequent trajectories of moving objects for location prediction[A]. Machine Learning and Data Mining in Pattern Recognition[C]. 2007. 667-680.

[4]LI H Y,TANG C J,QIAO S J. Hotspot district trajectory prediction[A]. Web-Age Information Management[C]. 2010. 74-84.

[5]BURBEY I E. Predicting Future Locations and Arrival Times of Individuals[D]. Virginia: Virginia Polytechnic Institute and State University,2011.

[6]PETZOLD J,PIETZOWSKI A,BAGCI F,et al. Prediction of indoor movements using Bayesian networks[A]. Lecture Notes in Computer Science[C]. 2005. 173-184.

[7]彭曲,丁治明,郭黎敏. 基于馬爾可夫鏈的軌跡預測[J]. 計算機科學,2010,37(8): 189-193.PENG Q,DING Z M,GUO L M. Prediction of trajectory based on Markov chains[J]. Computer Science,2010,37(8):189-193.

[8]SONG C M,QU Z H,BLUMM N. Limits of predictability in human mobility[J]. Science,2010,327(5968): 1018-1021.

[9]JEUNG H,SHEN H T,ZHOU X F. Mining trajectory patterns using hidden Markov models[A]. Data Warehousing and Knowledge Discovery[C]. 2009. 470-480.

[10]KOSKELA T,LEHTOKANGAS M,SAARINEN J. Time series prediction with multilayer perceptron,FIR and Elman neural networks[A].Proceedings of the World Congress on Neural Networks[C]. 1996.491-496.

[11]BAGCI P J,TRUMLER F,et al. Global state context prediction techniques applied to a smart office building[A]. The Communication Networks and Distributed Systems Modeling and Simulation Conference[C]. San Diego,2004.

[12]CHEN L,LV M Q,CHEN G C. A system for destination and future route prediction based on trajectory mining [J]. Pervasive and Mobile Computing,2010,6(6): 657-676.

[13]ASHBROOK D,STARNER T. Using GPS to learn significant locations and predict movement across multiple users[J]. Personal and Ubiquitous Computing,2003,(7): 275-286.

[14]ZHENG V W C,ZHENG Y,XIE X. Collaborative location and activity recommendations With GPS history data[A]. Proceeding of International Conference on World Wide Web[C]. 2010. 1029-1038.

[15]http://en.wikipedia.org/wiki/Markov_model[EB/OL]. 2011.

[16]http://www.chorochronos.org/Default.aspx?tabid=75 [EB/OL]. 2012.