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

（1.中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116；2.中國(guó)煤炭工業(yè)協(xié)會(huì)，北京 100713）

1 引言

移動(dòng)對(duì)象空間定位技術(shù)的快速發(fā)展極大地推動(dòng)了基于位置服務(wù)的廣泛應(yīng)用，為了使服務(wù)具有前瞻性，不僅要對(duì)移動(dòng)對(duì)象當(dāng)前活動(dòng)的位置進(jìn)行分析，更要能夠?qū)ζ湮恢眠M(jìn)行預(yù)測(cè)。移動(dòng)對(duì)象位置預(yù)測(cè)是一項(xiàng)具有挑戰(zhàn)性的工作，主要原因如下：由于GPS等定位設(shè)備具有采樣盲點(diǎn)，移動(dòng)對(duì)象在封閉空間內(nèi)的位置信息無(wú)法被捕獲，造成移動(dòng)對(duì)象軌跡數(shù)據(jù)的部分缺失，這些缺失的部分往往可能是移動(dòng)對(duì)象活動(dòng)較為重要的區(qū)域，因此，軌跡數(shù)據(jù)的缺失和不完整，大大增加了移動(dòng)對(duì)象活動(dòng)的預(yù)測(cè)難度；移動(dòng)對(duì)象的運(yùn)動(dòng)具有不確定性，不同周期內(nèi)移動(dòng)對(duì)象的活動(dòng)模式不完全相同；移動(dòng)對(duì)象軌跡的時(shí)空信息具有離散性和瑣碎性，無(wú)法將原始軌跡直接用于移動(dòng)對(duì)象未來(lái)位置的預(yù)測(cè)。

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

以上文獻(xiàn)大多從宏觀角度分析移動(dòng)對(duì)象興趣區(qū)域間的轉(zhuǎn)換關(guān)系，考慮移動(dòng)對(duì)象興趣區(qū)域間運(yùn)動(dòng)的研究不多，這樣存在2個(gè)問題：1）對(duì)象活動(dòng)模式強(qiáng)調(diào)移動(dòng)對(duì)象若干活動(dòng)間的順序性，由于運(yùn)動(dòng)的不確定性，距離較近的區(qū)域間的訪問順序可能不固定；2）在移動(dòng)對(duì)象歷史活動(dòng)記錄中，一個(gè)興趣區(qū)域之后的候選訪問區(qū)域可能包含多個(gè)，僅依靠興趣區(qū)域間的歷史訪問習(xí)慣很難準(zhǔn)確地篩選最佳興趣區(qū)域。

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

2 基于運(yùn)動(dòng)趨勢(shì)的移動(dòng)對(duì)象位置預(yù)測(cè)模型

基于運(yùn)動(dòng)趨勢(shì)的移動(dòng)對(duì)象位置預(yù)測(cè)算法（LP-MT）包括移動(dòng)對(duì)象歷史活動(dòng)模型的訓(xùn)練以及未來(lái)位置的預(yù)測(cè)2個(gè)階段。

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

圖1 LP-MT算法訓(xùn)練階段示意

圖2 LP-MT算法預(yù)測(cè)階段示意

未來(lái)位置預(yù)測(cè)過程（如圖2所示）中，首先將移動(dòng)對(duì)象最近停留區(qū)域結(jié)合基于馬爾可夫的移動(dòng)對(duì)象活動(dòng)模型進(jìn)行初步預(yù)測(cè)。其次，將最近停留區(qū)域至當(dāng)前位置間的軌跡段對(duì)應(yīng)至停留區(qū)域提取時(shí)劃分的網(wǎng)格中，將軌跡點(diǎn)序列轉(zhuǎn)換為網(wǎng)格序列（如圖 2中g(shù)16,4-＞g15,4-＞g15,5），使用網(wǎng)格序列中提取的移動(dòng)對(duì)象運(yùn)動(dòng)特征描述移動(dòng)對(duì)象的近期運(yùn)動(dòng)趨勢(shì)，根據(jù)運(yùn)動(dòng)趨勢(shì)對(duì)移動(dòng)對(duì)象未來(lái)位置進(jìn)行進(jìn)一步的預(yù)測(cè)。最后，根據(jù)未來(lái)位置的分類規(guī)則，給出綜合預(yù)測(cè)結(jié)果。

2.1 基于移動(dòng)對(duì)象活動(dòng)模型的預(yù)測(cè)

目前，移動(dòng)對(duì)象未來(lái)位置預(yù)測(cè)算法大多通過挖掘移動(dòng)對(duì)象軌跡的頻繁模式來(lái)發(fā)現(xiàn)其歷史停留區(qū)域間的關(guān)聯(lián)關(guān)系。在現(xiàn)實(shí)世界中，部分停留區(qū)域可能較為集中，移動(dòng)對(duì)象對(duì)這些區(qū)域的訪問順序有很大的隨機(jī)性。假設(shè)3個(gè)停留區(qū)域A、B、C間的距離較小，D、E為距離A、B、C較遠(yuǎn)的2個(gè)區(qū)域，移動(dòng)對(duì)象歷史活動(dòng)模式中包含以下序列：A-＞B-＞C-＞D，A-＞B-＞C-＞E，B-＞A-C-＞E，B-＞C-＞A-＞D。若移動(dòng)對(duì)象的近期停留區(qū)域序列為B-＞A-＞C，完全匹配歷史活動(dòng)模式時(shí)，預(yù)測(cè)結(jié)果為E。然而，A、B、C間的距離較近，區(qū)域訪問具有不確定性，因此D作為未來(lái)停留區(qū)域的概率也較大。另外，對(duì)象近期停留區(qū)域序列的長(zhǎng)度很難選取。本文借鑒馬爾可夫模型的思想，提出基于馬爾可夫的移動(dòng)對(duì)象活動(dòng)模型，考慮相鄰?fù)Ａ魠^(qū)域間的轉(zhuǎn)換，對(duì)移動(dòng)對(duì)象歷史活動(dòng)建模。

馬爾可夫模型[15]由一系列狀態(tài)以及狀態(tài)轉(zhuǎn)移矩陣組成，第n次轉(zhuǎn)換獲得的狀態(tài)只和第n-1次的狀態(tài)有關(guān)。移動(dòng)對(duì)象的歷史停留區(qū)域序列SRL={SR1,SR2,…,SRN}可以被表示為狀態(tài)變量序列XL={X1,X2,…,XN}。若移動(dòng)對(duì)象潛在停留區(qū)域的數(shù)量為m，則狀態(tài)空間集合EL=＜E1,E2,…,Em＞，每個(gè)停留區(qū)域?qū)?yīng)一個(gè)狀態(tài)，移動(dòng)對(duì)象在某一時(shí)刻只能處于一種狀態(tài)。根據(jù)移動(dòng)對(duì)象的當(dāng)前狀態(tài)以及狀態(tài)間轉(zhuǎn)移關(guān)系，可以粗略估計(jì)移動(dòng)對(duì)象的后續(xù)狀態(tài)。

若移動(dòng)對(duì)象最近停留區(qū)域?yàn)镾Rr，歷史記錄中區(qū)域 SRr后已訪問的停留區(qū)域集合為SRLN={SRl1,SRl2,…,S Rls}，SRr和SRli是移動(dòng)對(duì)象連續(xù)訪問區(qū)域，SRli稱為SRr的后續(xù)停留區(qū)域，本文將移動(dòng)對(duì)象最近停留區(qū)域的后續(xù)停留區(qū)域集合 SRLN稱為預(yù)測(cè)停留區(qū)域集合。最近停留區(qū)域SRr在狀態(tài)空間集合中的對(duì)應(yīng)狀態(tài)為Er，Er的后續(xù)狀態(tài)集合為ELN={El1,El2,…,Els}。狀態(tài) Er至后續(xù)狀態(tài) Eli的一步轉(zhuǎn)移概率 PMarr,li=P(Er→Eli)=P(Xn+1=Eli|Xn=Er)體現(xiàn)了停留區(qū)域 SRli作為停留區(qū)域SRr的未來(lái)位置的可能性。預(yù)測(cè)停留區(qū)域集合 SRLN中的區(qū)域作為最近停留區(qū)域SRr的未來(lái)位置的概率集合PMarL={PMarr,l1,P Marr,l2,… PMarr,ls}。

2.2 基于移動(dòng)對(duì)象運(yùn)動(dòng)趨勢(shì)的預(yù)測(cè)

移動(dòng)對(duì)象活動(dòng)模型從停留區(qū)域的角度對(duì)移動(dòng)對(duì)象活動(dòng)習(xí)慣進(jìn)行描述，而對(duì)象近期運(yùn)動(dòng)趨勢(shì)也能夠指導(dǎo)移動(dòng)對(duì)象未來(lái)位置的預(yù)測(cè)。例如，對(duì)象從停留區(qū)域A出發(fā)可能到達(dá)B和C，但B、C分別在區(qū)域A的左側(cè)和右側(cè)。若對(duì)象從A出發(fā)向左走，距離B越來(lái)越近，則盡管歷史記錄中到達(dá)C的概率較大，根據(jù)移動(dòng)對(duì)象的近期運(yùn)動(dòng)趨勢(shì)可以發(fā)現(xiàn)，B更可能為移動(dòng)對(duì)象的未來(lái)停留位置。因此本文在考慮停留區(qū)域間關(guān)系的同時(shí)，也考慮移動(dòng)對(duì)象的近期運(yùn)動(dòng)趨勢(shì)，使用移動(dòng)對(duì)象運(yùn)動(dòng)方向以及與各潛在停留區(qū)域的距離對(duì)移動(dòng)對(duì)象運(yùn)動(dòng)趨勢(shì)進(jìn)行描述。

移動(dòng)對(duì)象軌跡中距離當(dāng)前時(shí)間越近的信息越能反映移動(dòng)對(duì)象的近期運(yùn)動(dòng)趨勢(shì)，對(duì)預(yù)測(cè)結(jié)果的影響越大。本文將移動(dòng)對(duì)象最近停留區(qū)域至當(dāng)前位置間的軌跡段轉(zhuǎn)換為網(wǎng)格序列，首先計(jì)算網(wǎng)格序列至各潛在停留區(qū)域的距離概率和方向概率，然后根據(jù)距離權(quán)重和方向權(quán)重得到綜合概率，用來(lái)描述運(yùn)動(dòng)趨勢(shì)對(duì)各潛在停留區(qū)域作為未來(lái)位置的影響。

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

從宏觀角度，移動(dòng)對(duì)象至目標(biāo)位置的距離應(yīng)越來(lái)越短。本文認(rèn)為移動(dòng)對(duì)象趨向于向距離當(dāng)前位置較近的停留區(qū)域運(yùn)動(dòng)，若一段時(shí)間內(nèi)，移動(dòng)對(duì)象距離區(qū)域X越來(lái)越近，則移動(dòng)對(duì)象下一個(gè)停留區(qū)域?yàn)閄的概率較大。為了將距離標(biāo)準(zhǔn)轉(zhuǎn)換為概率，假設(shè)當(dāng)前網(wǎng)格到各潛在停留區(qū)域的最遠(yuǎn)、最近距離分別為Dmax、Dmin，到達(dá)X的距離為DX，則從當(dāng)前網(wǎng)格到達(dá) X 的概率為Pd(X)=1?(DX?Dmin)/(Dmax?Dmin)。網(wǎng)格序列GL={G1,G2,…,Gs}至潛在停留區(qū)域X的距離概率集合為PLd={Pd1(X),Pd2(X),…,Pds(X)},則網(wǎng)格序列至X的綜合距離概率為

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

移動(dòng)對(duì)象向目標(biāo)位置移動(dòng)過程中，整體行進(jìn)方向會(huì)趨向于目標(biāo)位置的方向。當(dāng)前網(wǎng)格與前一網(wǎng)格以及停留區(qū)域代表網(wǎng)格間都存在方向向量。若隨對(duì)象運(yùn)動(dòng)、方向向量間夾角越來(lái)越小，則停留區(qū)域?yàn)槟繕?biāo)位置的概率較大。假設(shè)當(dāng)前網(wǎng)格的第一個(gè)樣本點(diǎn)為pi+1，前一網(wǎng)格中最后一個(gè)樣本點(diǎn)為pi，則方向向量，區(qū)域 X代表網(wǎng)格的中心點(diǎn)為r'=(x,y)，則當(dāng)前網(wǎng)格至X的方向向量為，當(dāng)前網(wǎng)格至區(qū)域X的方向概率為Pa(X)=cos。網(wǎng)格序列 GL=＜G1,G2,…,Gs＞至區(qū)域 X的方向概率集合為PLa=＜Pa1(X),Pa2(X),…,Pas(X))＞，則網(wǎng)格序列至X的綜合方向概率為

若綜合距離概率和綜合方向概率的權(quán)重分別為WD和WA，則網(wǎng)格序列至X的綜合概率

假設(shè)移動(dòng)對(duì)象潛在停留區(qū)域集合為SRL={SR1,SR2,…,SRm}，反映移動(dòng)對(duì)象近期運(yùn)動(dòng)趨勢(shì)的網(wǎng)格序列GL=＜G1,G2,…,Gs＞，則根據(jù)網(wǎng)格序列計(jì)算至潛在停留區(qū)域集合 SRL中的各個(gè)區(qū)域的綜合概率集合PMovL={PMov1,PMov2,…,PMovm}。

2.3 移動(dòng)對(duì)象未來(lái)位置的分類

移動(dòng)對(duì)象未來(lái)位置可以分為三類：一是預(yù)測(cè)停留區(qū)域集合中的位置，即歷史數(shù)據(jù)中記錄的最近停留區(qū)域的后繼停留區(qū)域；二是潛在停留區(qū)域集合中預(yù)測(cè)停留區(qū)域外的其余停留區(qū)域，這類區(qū)域單純依靠軌跡模式是無(wú)法得到的；最后一類是移動(dòng)對(duì)象未出現(xiàn)過的區(qū)域，這類區(qū)域無(wú)法通過單個(gè)對(duì)象的歷史數(shù)據(jù)得到，需要分析和當(dāng)前對(duì)象相似的多個(gè)對(duì)象才能給出合適的結(jié)果。本文只考慮前兩類位置，即預(yù)測(cè)位置和推薦位置。

移動(dòng)對(duì)象可能在其歷史停留區(qū)域集合中的任意位置停留，因此潛在停留區(qū)域集合中的區(qū)域?qū)⒆鳛槲磥?lái)位置的候選。潛在停留區(qū)域 X作為移動(dòng)對(duì)象未來(lái)位置的可能性大小被定義為區(qū)域 X的可達(dá)性，表示為PRX。若一段時(shí)間內(nèi)，移動(dòng)對(duì)象到達(dá)停留區(qū)域 X的可達(dá)性都較高，則移動(dòng)對(duì)象運(yùn)動(dòng)到區(qū)域X的可能性最大。

針對(duì)預(yù)測(cè)位置和推薦位置，LP-MT算法得到預(yù)測(cè)區(qū)域可達(dá)性列表和推薦區(qū)域可達(dá)性列表。預(yù)測(cè)區(qū)域可達(dá)性列表對(duì)應(yīng)上述第一類，包含預(yù)測(cè)區(qū)域列表以及各個(gè)區(qū)域的可達(dá)性，其中預(yù)測(cè)區(qū)域列表按照區(qū)域可達(dá)性遞減的順序排列。通過基于馬爾可夫的移動(dòng)對(duì)象活動(dòng)模型和運(yùn)動(dòng)趨勢(shì)的綜合計(jì)算可得到預(yù)測(cè)區(qū)域的可達(dá)性。推薦區(qū)域可達(dá)性列表為上述第二類位置，包含推薦區(qū)域列表以及各個(gè)區(qū)域的可達(dá)性，其中推薦區(qū)域列表按照區(qū)域可達(dá)性遞減的順序排列。推薦區(qū)域的可達(dá)性可通過對(duì)移動(dòng)對(duì)象近期運(yùn)動(dòng)趨勢(shì)的分析得到。

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

3 基于運(yùn)動(dòng)趨勢(shì)的移動(dòng)對(duì)象位置預(yù)測(cè)算法

3.1 算法描述

LP-MT包含2個(gè)階段：1）訓(xùn)練階段，移動(dòng)對(duì)象歷史數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)集，提取歷史停留區(qū)域及歷史活動(dòng)序列，并以此建立基于馬爾可夫的移動(dòng)對(duì)象活動(dòng)模型；2）預(yù)測(cè)階段，根據(jù)移動(dòng)對(duì)象最近停留區(qū)域以及運(yùn)動(dòng)趨勢(shì)進(jìn)行分步預(yù)測(cè)。

LP-MT 算法 輸入：TTrain(訓(xùn)練軌跡)，TTest(測(cè)試軌跡)，Dth(最小距離閾值)，Tth(最小時(shí)間閾值)，GHorGVer(網(wǎng)格數(shù)量)，WD(距離權(quán)重)，WA(方向權(quán)重)

輸出：SRLPre(預(yù)測(cè)可達(dá)性列表)，SRLCom(推薦可達(dá)性列表）

/*訓(xùn)練階段*/

1)SR=FindStayRegions(TTrain,Dth,Tth,GHor×GVer); /*發(fā)現(xiàn)停留區(qū)域集合*/

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

3)MarkovM=BuildMarkovModel(SRL); /*建立基于馬爾可夫的移動(dòng)對(duì)象活動(dòng)模型*//*預(yù)測(cè)階段*/

4)SRr=FindRecentSR(TTest,Dth,Tth,GHor×GVer);/*發(fā)現(xiàn)移動(dòng)對(duì)象最近停留區(qū)域*/

5)GL=AbstractGridsList(TTest,SRr,GHor×GVer);/*提取反映運(yùn)動(dòng)趨勢(shì)的網(wǎng)格序列*/

6)PMarL=CalPredReachList(SRr,MarkovM);/*計(jì)算至預(yù)測(cè)停留區(qū)域的概率集合*/

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

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

9)SRLPre=SynPreReachList(PMarL,PMovL);/*預(yù)測(cè)可達(dá)性列表*/

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

3.2 算法性能分析

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

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

為了驗(yàn)證本文提出的基于運(yùn)動(dòng)趨勢(shì)的移動(dòng)對(duì)象位置預(yù)測(cè)算法，采用Visual C# 2005開發(fā)了移動(dòng)對(duì)象未來(lái)位置預(yù)測(cè)系統(tǒng) LP-MT，軌跡數(shù)據(jù)存儲(chǔ)在SQLServer 2000中。實(shí)驗(yàn)進(jìn)行的軟硬件環(huán)境包括：Windows XP，Lenovo ThinkCentre (Duro 2，2.8G的CPU，3G內(nèi)存)。實(shí)驗(yàn)數(shù)據(jù)集使用2007年希臘雅典市區(qū)卡車(Trucks)的運(yùn)動(dòng)軌跡[16]。

4.1 參數(shù)影響

本實(shí)驗(yàn)測(cè)試網(wǎng)格數(shù)量對(duì)于基于馬爾可夫的移動(dòng)對(duì)象活動(dòng)模型的健壯性的影響，選取Trucks數(shù)據(jù)集中ID=900的軌跡進(jìn)行實(shí)驗(yàn)，設(shè)定最小距離閾值Dth=400 m，最小時(shí)間閾值Tth=5 min，由于對(duì)象運(yùn)動(dòng)時(shí)對(duì)方向和距離的無(wú)意識(shí)性，設(shè)定 WD=WA=0.5。圖3顯示不同網(wǎng)格數(shù)量和訓(xùn)練集規(guī)模時(shí)，馬爾可夫模型狀態(tài)數(shù)、網(wǎng)格序列數(shù)以及運(yùn)行時(shí)間的變化情況。

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

圖3 不同網(wǎng)格數(shù)量和數(shù)據(jù)規(guī)模對(duì)LP-MT算法的影響

4.2 預(yù)測(cè)精度

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

1)不同訓(xùn)練樣本比例

該實(shí)驗(yàn)主要用于測(cè)試在歷史數(shù)據(jù)充分學(xué)習(xí)的情況下，算法的預(yù)測(cè)精度。選取整條軌跡30%～85%的數(shù)據(jù)量作為訓(xùn)練樣本，訓(xùn)練樣本的結(jié)束點(diǎn)作為移動(dòng)對(duì)象的當(dāng)前位置開始預(yù)測(cè)。

從表1可以看出，訓(xùn)練樣本比例與馬爾可夫模型狀態(tài)數(shù)成正比。實(shí)驗(yàn)表明馬爾可夫模型中10%～20%的狀態(tài)有3個(gè)及3個(gè)以上的轉(zhuǎn)換狀態(tài)，20%～30%的狀態(tài)有2個(gè)轉(zhuǎn)換狀態(tài)，其余包含一個(gè)轉(zhuǎn)換狀態(tài)，極少數(shù)情況下，不包含轉(zhuǎn)換狀態(tài)，此時(shí)，移動(dòng)對(duì)象首次到達(dá)該停留區(qū)域且沒有移動(dòng)至下一區(qū)域。使用不同數(shù)據(jù)集建立的馬爾可夫模型的狀態(tài)轉(zhuǎn)換情況有所不同。

表1 Truck數(shù)據(jù)不同訓(xùn)練樣本比例對(duì)馬爾可夫模型狀態(tài)數(shù)量的影響

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

圖4 不同訓(xùn)練樣本比例下的誤差率

以3%的數(shù)據(jù)集為一個(gè)梯度，25次實(shí)驗(yàn)中共產(chǎn)生5次推薦和20次預(yù)測(cè)。推薦準(zhǔn)確率達(dá)到40%。20次預(yù)測(cè)結(jié)果中，僅根據(jù)基于馬爾可夫的移動(dòng)對(duì)象活動(dòng)模型預(yù)測(cè)的準(zhǔn)確率達(dá)到50%。增加考慮移動(dòng)對(duì)象運(yùn)動(dòng)趨勢(shì)可提高 24%的預(yù)測(cè)成功率，其余情況下，結(jié)合運(yùn)動(dòng)趨勢(shì)也可以使準(zhǔn)確率在簡(jiǎn)單的一步預(yù)測(cè)的基礎(chǔ)上有顯著提高。實(shí)驗(yàn)表明算法在不同訓(xùn)練樣本比例下都具有較高準(zhǔn)確性。

2)訓(xùn)練集規(guī)模

該實(shí)驗(yàn)主要測(cè)試當(dāng)歷史數(shù)據(jù)量較少時(shí)，預(yù)測(cè)結(jié)果的準(zhǔn)確性。選取整條軌跡 30%～90%間不同梯度的數(shù)據(jù)量作為訓(xùn)練樣本，以90%處的樣本點(diǎn)作為移動(dòng)對(duì)象當(dāng)前位置。

從圖5中的曲線可以看出，訓(xùn)練集規(guī)模較小時(shí)，推薦結(jié)果的準(zhǔn)確率較高，這是由于此時(shí)移動(dòng)對(duì)象歷史數(shù)據(jù)較少，僅依靠歷史停留區(qū)域間的轉(zhuǎn)換關(guān)系無(wú)法準(zhǔn)確預(yù)測(cè)，但是移動(dòng)對(duì)象近期運(yùn)動(dòng)趨勢(shì)能夠反映對(duì)象活動(dòng)意圖，從而提高推薦準(zhǔn)確性。圖5顯示推薦誤差率趨近于 0，表明本文選取距離和方向作為反映運(yùn)動(dòng)趨勢(shì)的標(biāo)準(zhǔn)較為合理。隨著訓(xùn)練集規(guī)模的增加，預(yù)測(cè)結(jié)果更加準(zhǔn)確，綜合誤差率基本小于0.3。因此，歷史數(shù)據(jù)量較少時(shí)，運(yùn)動(dòng)趨勢(shì)能夠很好地對(duì)未來(lái)位置進(jìn)行推薦，隨著歷史數(shù)據(jù)集規(guī)模的增大，預(yù)測(cè)精度則越來(lái)越高。

3)學(xué)習(xí)充分性

該實(shí)驗(yàn)用于檢驗(yàn)基于馬爾可夫的移動(dòng)對(duì)象活動(dòng)模型能否充分學(xué)習(xí)對(duì)象的歷史活動(dòng)模式。選取整條軌跡50%～100%之間的數(shù)據(jù)進(jìn)行訓(xùn)練，從軌跡的45%處開始預(yù)測(cè)。以5%的數(shù)據(jù)集為一個(gè)梯度，20次實(shí)驗(yàn)的預(yù)測(cè)誤差率全部為0，實(shí)驗(yàn)表明對(duì)象活動(dòng)模型能夠準(zhǔn)確、全面地反映移動(dòng)對(duì)象的歷史活動(dòng)模式。

圖5 訓(xùn)練集規(guī)模與誤差率間關(guān)系

4)算法穩(wěn)定性

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

圖6 測(cè)試位置與平均誤差率的關(guān)系

4.3 移動(dòng)對(duì)象活動(dòng)模型的更新有效性

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

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

4.4 同類算法性能比較

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

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

圖9 PPM-C與LP-MT算法運(yùn)行時(shí)間比較

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

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

5 結(jié)束語(yǔ)

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

[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]彭曲,丁治明,郭黎敏. 基于馬爾可夫鏈的軌跡預(yù)測(cè)[J]. 計(jì)算機(jī)科學(xué),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.