程媛 遲榮華 黃少濱 呂天陽,4

當前,類似手機等智能終端的廣泛普及,使人類傳感信息的獲取變得更加容易,而面向這種傳感信息的應用和服務則隨之快速增長且類型多種多樣.其中面向位置的服務在基于終端傳感信息的應用中最為熱門,這類服務可實時獲取用戶的坐標和區(qū)域等位置信息.所獲取的位置信息的歷史數(shù)據(jù)可用于對用戶的移動軌跡進行預測,而較準確的預測結果能夠為用戶提供所需的信息和幫助.

較為常見的軌跡預測研究是軌跡序列預測.Song等[1]在預測人類移動軌跡的研究工作中,通過個體的軌跡信息熵的測量,量化了人類移動行為的一般性規(guī)律,并得出人的移動行為是可預測的.其他移動軌跡預測方法還包括軌跡頻繁模式挖掘[2?4]、基于復雜信息的行為模式挖掘[5?6]和混合方法[7].

由于人的移動行為極其復雜,可能會受到信號采集、客觀環(huán)境、主觀意圖等多種不確定因素的影響,使得對軌跡序列難以進行較準確的預測.而移動行為復雜多變,但一般情況下,人的行為目的性較強,移動軌跡終點較為明確,因此移動軌跡預測的另一類研究問題就是移動軌跡的終點預測.

軌跡終點的預測方法一般是將待預測軌跡的數(shù)據(jù)流與歷史軌跡數(shù)據(jù)進行匹配,選擇并篩選出最為相近的軌跡,該軌跡的終點即為待預測軌跡的終點,匹配方法也多基于常見的分類預測模型.De Brbisson等[8]以軌跡的起始坐標和背景等信息作為特征向量訓練多層感知的神經(jīng)網(wǎng)絡,通過匹配訓練數(shù)據(jù)集中的軌跡實現(xiàn)對軌跡終點的預測.對于訓練過的相似軌跡,模型可以較好地預測;但對于新區(qū)域的軌跡,模型需要新的訓練數(shù)據(jù)集以及新的相關信息;另外,網(wǎng)絡模型本身難以解釋,使其難以通過調(diào)整和控制網(wǎng)絡模型適應新的數(shù)據(jù),限制了模型的適用性.Krumm等[9]和Ziebart等[10]利用除軌跡以外的信息進行貝葉斯信念網(wǎng)的訓練來預測軌跡的終點.Patterson等[11]也基于貝葉斯模型預測軌跡終點,但考慮了如行走、乘車之間狀態(tài)改變等形式的歷史軌跡的運動模式信息.Monreale等[12]利用T-pattern決策樹對移動軌跡建模,通過匹配決策樹中的路徑預測軌跡終點.

隨著軌跡預測研究的深入,軌跡中的不確定性問題也逐漸被發(fā)現(xiàn)是限制軌跡預測準確性的重要因素,現(xiàn)有研究大多從軌跡中位置間轉(zhuǎn)移概率的角度來考慮不確定因素.Ashbrook等[13]在GPS數(shù)據(jù)上,結合位置間的轉(zhuǎn)移概率訓練Markov模型,并預測軌跡的終點.Gambs等[14]利用Markov Chains對軌跡位置序列中的興趣點建模,通過計算興趣點間的轉(zhuǎn)移概率預測軌跡的終點.現(xiàn)有研究中利用的Markov和貝葉斯模型均可以描述位置之間的轉(zhuǎn)移概率,但其模型屬于離散類型,對于歷史信息中尚未出現(xiàn)過的軌跡預測結果準確性有限.因此,喬少杰等[15]以及Besse等[16]利用高斯密度分布對軌跡建模,并利用高斯回歸過程對軌跡進行預測.這種基于連續(xù)密度的模型不僅可以以概率的形式對軌跡的不確定建模,還能對軌跡的終點給出連續(xù)形式的解,相較于離散模型具有更高的預測準確性.

現(xiàn)有研究雖然采用了不同的預測方法,但幾乎均需要根據(jù)待檢測的移動軌跡與歷史軌跡數(shù)據(jù)的匹配程度進行軌跡終點的判斷.然而在真實的移動場景中,人的移動行為具有較強的不確定性,一是由于信息采集設備的能效問題可能導致錄入的信息存在不同程度的損失或干擾,使獲取的信息與真實信息存在偏差;再者由于人與社會的復雜性,人的移動具有較強的不確定性,使得在以同一目標為終點進行移動時可能出現(xiàn)任意不同的移動軌跡,例如為了躲避交通的擁堵可能選擇路程相對較遠的路線,或為了興趣或特殊目的而選擇比較隨意的移動路線等.可見,真實的移動場景中的軌跡充滿了各種各樣的不確定性,一個用戶當前的移動軌跡可能與任意一條歷史軌跡均不相同,但實際上又可能與某條歷史移動軌跡具有相同的起始點和終點.針對這樣的體現(xiàn)用戶不確定移動行為的軌跡,現(xiàn)有方法難以對終點進行較準確的預測.對于移動軌跡的研究面臨的問題來說,一方面是無法準確地確定移動對象的移動軌跡細節(jié)(例如移動對象下一個準確的移動位置),另一方面是難以通過單一或簡單的假設理論模型進行確定的建模,這種復雜性與不確定性的存在,使得理想條件下對移動軌跡的預測難以獲得較準確的結果.面對這種問題,本文將結合不確定性的研究思路根據(jù)用戶當前的移動行為其軌跡終點進行預測.

一個用戶的移動軌跡由其經(jīng)過的若干個位置信息構成.如果將一個用戶的移動軌跡視為不確定的,那么起始點和終點相同的若干移動軌跡則構成了表示兩點間所有經(jīng)過路線的不確定軌跡數(shù)據(jù)集,即包含了兩點間所有可能路線的樣本集.此時可以從該不確定樣本集內(nèi)的所有移動軌跡中獲得用戶在兩點間的移動行為分布特征,而這種行為的分布特征具體體現(xiàn)為軌跡中位置信息的分布特征.如果認為移動軌跡中的位置點服從某種密度分布,那么對于概率密度較高的位置,分析當前用戶的移動軌跡時會有較高的可能性選擇該位置.而非參數(shù)估計方法能夠在不假設分布類型的前提下構建更符合數(shù)據(jù)實際分布特征的概率密度函數(shù),因此本文基于這種不確定性的研究思路,提出一種基于非參數(shù)密度估計的面向不確定軌跡的終點預測方法.首先基于非參數(shù)估計方法,對已獲取的兩點間的所有移動軌跡數(shù)據(jù)構建符合其分布特征的概率密度函數(shù);然后在分析當前用戶的移動軌跡時,基于假設檢驗方法度量待檢測軌跡與已有的不確定軌跡關于軌跡中位置點分布特征的相似性,分析待檢測軌跡未來可能經(jīng)過的位置點以及可達的終點.所提方法主要利用不確定性的分析方法,結合所有歷史移動軌跡信息的特點,對移動軌跡進行建模,使得模型能夠基于概率分布函數(shù)體現(xiàn)歷史數(shù)據(jù)中所有用戶的移動行為特征,最終達到能夠?qū)v史數(shù)據(jù)中尚未出現(xiàn)的軌跡也具有極好的識別能力,即在更接近人類移動行為特征的條件下,對其軌跡的未來移動位置和終點進行較準確的預測.本文首先構建不確定移動軌跡模型;進而提出不確定移動軌跡相似性度量方法;然后據(jù)此對待檢測的移動軌跡的終點進行預測;接著通過實驗驗證所提方法的有效性;最后得出結論.

1 非參數(shù)密度估計

非參數(shù)密度估計是一種對先驗知識要求最少,完全依靠訓練數(shù)據(jù)進行估計,而且可用于任何形狀密度函數(shù)的方法.非參數(shù)密度估計方法能夠在不假設數(shù)據(jù)分布形式的前提下獲取符合分布特征的概率密度函數(shù),常用的非參數(shù)密度估計方法有直方圖估計方法、核函數(shù)估計方法以及K–近鄰估計方法.其中基于高斯核函數(shù)的非參數(shù)密度估計方法由于其較好的數(shù)學性質(zhì)以及廣泛的適用性,在本文中予以采用.基于如下核密度估計方法求得的概率密度函數(shù)能夠在樣本點與目標數(shù)據(jù)量足夠大時,收斂到任意一種密度函數(shù)[17].

其中,qi為權重系數(shù),h為核函數(shù)的平滑參數(shù)—帶寬(bandwidth),{si}i=1,···,N為服從某種未知分布的樣本點.

假設數(shù)據(jù)X1, x2,···, Xn是d維向量,并取自一個連續(xù)分布f(X),在任意點x處的一種核密度估計定義為,其中f(X)是一個d維隨機變量的密度函數(shù),K(·)是定義在d維空間上R的核函數(shù),K:Rd→R,并滿足條件K(X)≥0,K(X)du=1.其中,帶寬hd對模型的光滑程度有較大的影響,合適的取值可使模型具有更好的擬合效果.在維度較高時,帶寬的取值需要參考每個維度上的取值分布,可以通過核密度估計的邊緣概率計算,屬于比較復雜的情況.而在本文所提方法中假設表示軌跡點的經(jīng)度和緯度的變量是相對獨立的,因此分別計算各個維度的h即可,利用最小化均方誤差方法,當核函數(shù)為高斯核時,可取最優(yōu)帶寬hopt=1.06σn1/5.

2 不確定移動軌跡模型

理想的移動軌跡信息記錄了移動對象的起點、終點、必要的路徑信息以及較少的噪音或冗余,這種移動模式簡單且軌跡間的相似程度較高.考慮到移動軌跡中的不確定性,本文結合非參數(shù)密度估計方法對人的移動軌跡進行建模與預測.將人的移動軌跡中的所有路線作為樣本數(shù)據(jù),用于構建面向不確定性的移動軌跡模型,其中的不確定性用能夠體現(xiàn)軌跡樣本分布的概率密度函數(shù)進行表示;然后以該模型為基礎,結合個人當前的移動路線,分析預測可能的移動方向與路徑.

首先,令數(shù)據(jù)集D表示已有的對象移動軌跡集合,該集合中的每條數(shù)據(jù)記錄了一個對象在一次移動行為中不同時間點采集的位置信息,即每條記錄由對象的位置信息序列構成.那么一個移動對象的移動軌跡有序集可表示為D={T1,T2,···,Tn},其中第i條移動軌跡序列,表示為在d個時間點采集到的位置的有序集合,且為在第j個時間點采集的位置信息,并可表示為一個三元組:,1≤j≤d,其中表示采樣時間,表示在時間點采集的二維位置信息.

此時原始軌跡數(shù)據(jù)集D中的軌跡序列Ti,1≤i≤n可表示為,而且不同的軌跡序列間可能存在若干相同的軌跡點,那么重構后的軌跡數(shù)據(jù)集可表示為D'={T1',T2',···,Tn0}.從D'中的軌跡序列即可提取若干具有相同起始點與終點的軌跡路線,在這些路線中還極可能包含不同的軌跡點,體現(xiàn)了不同用戶在移動中的不同行為.本文將這種具有相同起始點s終點e且經(jīng)過不同軌跡點集的路線稱為起始點s終點e的不確定軌跡,具體描述如定義1所述.

定義1(不確定軌跡).移動對象的不確定軌跡UT由起始點s、終點e以及其間經(jīng)過的軌跡點集ns和軌跡集ts構成,表示為一個四元組:UT=(s,e,ns,ts),其中s, e∈V,ns?V,ts是D'中所有經(jīng)過s與ee的軌跡的集合,可表示為.

一條不確定軌跡UT即是從移動軌跡數(shù)據(jù)集D'中提取的,在起始點s和終點e之間的所有軌跡的集合;并且起始點s、終點e以及軌跡中的軌跡點均屬于軌跡點集V.即軌跡數(shù)據(jù)集D'中每條數(shù)據(jù)表示一條用戶的移動軌跡序列Ti0,但在這些序列中包含的任意兩點間都可能存在至少一條軌跡,例如表示在T1'中包含的vi和vj間的可達軌跡路線.因此若將?vi, vj∈V作為不確定軌跡的起始點與終點,并假設D'中每條軌跡序列中都包含這兩個軌跡點間的路線,可得vi,vj間的不確定軌跡,其中,表示在歷史數(shù)據(jù)中用戶經(jīng)過這兩點時可能選擇的所有軌跡路線.

基于軌跡數(shù)據(jù)集雖然難于分析每個用戶選擇移動路線的目的,但從tsi,j包含的移動軌跡中能夠分析用戶在兩點間的移動行為分布特征.如前所述由于多種原因,tsi,j中的軌跡所經(jīng)過的軌跡點是極其復雜和不確定的,因此軌跡的密度分布一般不服從某種簡單的假設分布,例如正態(tài)分布、冪律分布等.而非參數(shù)估計方法能夠在不假設數(shù)據(jù)分布形式的前提下獲取符合分布特征的概率密度函數(shù),本文即利用非參數(shù)估計中的核密度估計方法獲取不確定軌跡中可體現(xiàn)用戶行為分布特征的概率密度函數(shù).另外,不同軌跡中的軌跡點及其數(shù)量均可能不同,難以直接分析每條軌跡的分布密度;而ts中的所有軌跡均由軌跡點組成,因此分析兩點間的用戶移動行為特征時,可將分析對象細化至軌跡點,那么構建的概率密度函數(shù)實際描述的是在歷史路徑中軌跡點的分布情況.

定義2(密度式不確定軌跡).定義1中的UT=(s, e,ns,ts)表示起始點vs和終點ve間的不確定軌跡,且vs,ve∈V.令ts中所有軌跡包含的軌跡點集合為V,1≤l≤m,其中m為軌跡點的個數(shù).根據(jù)核密度估計方法可得nss,e的概率密度函數(shù)為,由于構建的是關于軌跡點的概率密度函數(shù),其中X為表示軌跡位置中經(jīng)緯度的2維自變量,h2則表示2維的最優(yōu)帶寬.那么起始點vs和終點ve間的密度式不確定軌跡為UTf=(s, e,f).

圖1是以起始點(39.138,117.213)和終點(39.220,117.161)構成的軌跡及其密度分布.該軌跡由多條經(jīng)過起始點和終點的軌跡構成,在該軌跡的前半部出現(xiàn)了不同的軌跡路徑,但后半程軌跡路徑基本相同,因此在密度分布中會出現(xiàn)位置點密度不均勻的情況.

可見為了提取移動軌跡數(shù)據(jù)集中利于預測分析用戶移動軌跡行為的信息,需要從中提取任意兩點間的不確定軌跡并為其建模.對于一條不確定軌跡而言,其模型的構建不僅包括軌跡的起始點、終點和兩點間用戶選擇的多種軌跡路線,還包括這些路線中覆蓋的軌跡點的分布特征,即軌跡的不確定性體現(xiàn)在其中包含的多條可選軌跡路線,而不確定性的描述則由能夠體現(xiàn)軌跡點分布特征的概率密度函數(shù)來完成.實際所構建的模型本身不再關注難于確定的無窮軌跡細節(jié),而是更多關注軌跡目標的終點以及可能出現(xiàn)的軌跡模式.

3 基于假設檢驗的不確定軌跡相似性度量

對不確定軌跡建模主要是試圖根據(jù)當前用戶的移動行為,基于數(shù)據(jù)集中其他用戶的歷史移動行為特征,判斷其將來可能的移動路線與目的.這個過程中的關鍵是不確定軌跡間的相似性,即通過度量當前用戶的移動軌跡與歷史不確定軌跡間的相似性,判斷其未來可能的移動軌跡路線.

不確定軌跡的本質(zhì)在于由作為樣本軌跡的不同用戶選擇的多種軌跡路線所體現(xiàn)的不確定性,而其不確定性可由軌跡點的概率密度函數(shù)描述,表示移動對象在不同位置經(jīng)過的可能性.此外在軌跡預測的問題中,預測方法的輸入是動態(tài)采樣的軌跡點,是以流的形式輸入的數(shù)據(jù),即軌跡數(shù)據(jù)流.軌跡數(shù)據(jù)流是連續(xù)的且隨時間不斷動態(tài)增長的軌跡序列,假設數(shù)據(jù)流T={u1, u2,···, ut,···},ut是t時刻采集到的位置信息,ut+1是相對于ut在t+1時刻的新增的位置信息.每采集到一個新的數(shù)據(jù)就會相應補充到原有序列的尾部,并作為軌跡序列整體的一部分保存.可見待預測的目標對象以數(shù)據(jù)流的形式表示,并且無法一次性獲取大量的數(shù)據(jù)樣本以分析其分布特征.所以在完成預測任務時難以直接比較兩個概率密度函數(shù)間的相似性.此時預測任務實為判斷表示用戶當前不完整移動行為的軌跡點的有限樣本與已有不確定軌跡的密度分布間的匹配程度,然后將匹配程度較高的不確定軌跡中的移動軌跡與目的地作為當前用戶未來可能移動軌跡路線的預測結果.能夠?qū)崿F(xiàn)這一目的的有效方法是假設檢驗方法.

圖1 不確定軌跡示意圖Fig.1 Uncertain trajectory

假設檢驗是用來判斷樣本與樣本、樣本與總體的差異是由抽樣誤差引起還是本質(zhì)差別造成的統(tǒng)計推斷方法.其基本原理是先對總體的特征做出某種假設,然后通過抽樣研究的統(tǒng)計推理,對此假設應該被拒絕還是接受做出推斷.常用的假設檢驗方法有u-檢驗法、t檢驗法、?2檢驗法(卡方檢驗)、F-檢驗法以及秩和檢驗等.這些假設檢驗方法需要對數(shù)據(jù)分布進行某種假設,而不確定軌跡的密度分布一是其分布情況預先未知,二是其一般并不符合理想密度分布(例如正態(tài)分布、指數(shù)分布等),因此一般的假設檢驗方法并不足以分析本文面對的問題.非參數(shù)估計方法能夠在不對數(shù)據(jù)分布進行預先假設的基礎上,根據(jù)數(shù)據(jù)自身特點分析其分布特征,有助于解決本文面對不確定軌跡的預測問題.而KS(Kolmogorov-Smirnov)檢驗作為一種非參數(shù)的假設檢驗方法,不僅具有很好的穩(wěn)健性,而且分析過程中不依賴均值的位置,對尺度化不敏感,即使樣本不服從正態(tài)分布,也依然具有良好的敏感性,有助于完成表示當前用戶行為的有限軌跡點樣本與表示已有軌跡不確定性的密度分布間的匹配問題.因此本文將基于KS檢驗進行不確定軌跡間的相似性度量.

選擇該院收治的婦科行宮腔鏡手術治療的患者200例為觀察對象，其中子宮黏膜下肌瘤切除85例，子宮內(nèi)膜息肉切除98例，宮腔粘連松解術17例。所有患者及其家屬均知情同意，并通過醫(yī)院倫理委員會的批準簽屬知情同意書。納入標準：選擇擬行婦科宮腔鏡手術治療的患者，年齡 25～58歲，體重 45～75 kg，美國麻醉醫(yī)師學會（ASA）I～II級，術前血離子檢查正常，近期未使用糖皮質(zhì)激素和鎮(zhèn)痛藥物。排除標準：孕婦及哺乳期婦女，合并嚴重心、腦、肺疾病者，肝、腎功能不全者，近日出現(xiàn)藥物過敏者，糖尿病患者，凝血功能異常者，多次行宮腔內(nèi)檢查者及術中出現(xiàn)子宮穿孔者。

KS檢驗基于累積頻數(shù)分布,檢驗數(shù)據(jù)分布是否與某種理論分布相似,或比較兩個數(shù)據(jù)分布是否有顯著性差異.KS檢驗的核心依然是檢驗兩個樣本的密度分布是否一致,但無需對數(shù)據(jù)的分布類型進行預先假設,而且隨著用戶移動行為的持續(xù)進行,獲取的表示移動軌跡的數(shù)據(jù)逐步積累,使得KS檢驗這樣基于累積頻數(shù)分布的方法能夠在此過程中逐步獲得接近數(shù)據(jù)真實分布的結論.

由于本文分析對象為二維的軌跡點,因此根據(jù)二維正態(tài)分布的假設檢驗方法,基于KS檢驗分析二維隨機變量的分布情況.通過軌跡點不同維度的密度分布以及累積分布的差異,能夠體現(xiàn)由軌跡點描述的軌跡間的差異.那么基于KS檢驗方法判斷軌跡關于軌跡點密度分布的一致性,就能夠說明軌跡間的相似性.KS檢驗方法的應用需要考慮的重要問題是變量是否獨立,位置信息中的分量間是否獨立決定了方法的合理性和復雜程度.對于位置分量的獨立性問題,難以通過理論證明獨立性是軌跡位置信息中的固有性質(zhì),那么就需要通過實驗驗證變量獨立性的存在,因此本文通過卡方檢驗對樣本進行隨機抽取檢驗,檢驗結果說明位置樣本中表示經(jīng)緯度的分量間相互獨立.另外,在準確性損失較小的前提下,假設位置信息分量間相互獨立可大幅度降低模型和計算的復雜性,在實現(xiàn)較高預測準確度的前提下進行快速軌跡預測.出于上述考慮,本文假設位置信息中的分量間是獨立的,對于二維隨機變量的KS檢驗,只需要分別對各分量的分布進行檢驗即可,因此本文只給出一維隨機變量的KS檢驗,然后再推廣到二維隨機變量的情況.

根據(jù)KS檢驗的定義,假設隨機變量x取自于樣本,目標密度函數(shù)為f,則有假設H0:總體X服從分布f,檢驗統(tǒng)計量為

若H0為真,則Z依分布收斂于Kolmogonov分布,即,可得

對于軌跡對象,假設軌跡數(shù)據(jù)流T={ X1,···,xn},其中X1是軌跡的起點,xn是移動對象在時刻n的位置,另有某密度式不確定軌跡UTf=(sss,e,f).若X1=s,根據(jù)KS檢驗判斷T是否可能來自于不確定軌跡UTf的密度分布,即判斷T來自的總體是否服從概率密度函數(shù)為f的分布,具體步驟如下:

1)檢驗的假設定義如下:H0來自的總體服從概率密度函數(shù)為f的分布,說明當前用戶軌跡可能來自于數(shù)據(jù)集中的不確定軌跡UTf的密度分布;H1來自的總體不服從概率密度函數(shù)為f的密度分布.

2)構造f的累積概率密度分布;根據(jù)核密度函數(shù)公式,F(X)可表示為

其中,K(·)表示核函數(shù).

3)計算累計分布F'.

4)計算統(tǒng)計量

5)根據(jù)KS檢驗臨界值表[18],若Z>Z(n,α),則拒絕H0假設,反之則接受.

若H0假設成立,說明T可能來自于具有相同起點的不確定軌跡UTf的密度分布,預測T的軌跡終點時,可參考UTf軌跡的終點.

4 軌跡預測算法

現(xiàn)有的軌跡預測研究中的一般預測目標是根據(jù)軌跡數(shù)據(jù)集中的歷史軌跡信息,預測移動對象起始點至終點的詳細確切的軌跡,試圖為用戶構建其未來可能經(jīng)過的完全軌跡模式.但在實際情況中,影響人的移動行為的因素較多,導致移動軌跡極其復雜而且容易出現(xiàn)與歷史軌跡不同情況的移動模式.因此本文主要對用戶移動軌跡的最終目的地進行預測,而非對軌跡中的每一個軌跡點進行精準預測.

軌跡終點的預測需要根據(jù)當前用戶已經(jīng)形成的移動軌跡數(shù)據(jù)流,在不確定軌跡集中檢索所有具有相同起始點且密度分布特征相同的不確定軌跡.首先根據(jù)當前已形成的部分軌跡數(shù)據(jù)流T={ X1,···, xn},確定軌跡的起點s=X1;在不確定軌跡數(shù)據(jù)集UD中檢索所有滿足起點為s的條件的k個不確定軌跡UTfi=(s,ei,fi),1≤i≤k;然后利用KS檢驗方法對軌跡數(shù)據(jù)流T與fi,1≤i≤k依次進行假設檢驗,檢驗結果為真的密度分布函數(shù)所對應的不確定軌跡可作為分析當前用戶移動軌跡的依據(jù),即將不確定軌跡的終點作為待分析移動軌跡的終點的可能預測結果.

在實際的分析過程中,用戶移動行為中每一次被采集到的軌跡點都作為輸入軌跡數(shù)據(jù)流的新增數(shù)據(jù),由于利用了KS檢驗基于累積分布的特點,隨著移動軌跡中采集到的軌跡點的增長以及輸入軌跡數(shù)據(jù)流樣本數(shù)量的增多,分析軌跡分布的KS檢驗精度能夠不斷提高,得到的結果不斷貼近數(shù)據(jù)實際分布,使得預測結果的準確性不斷提高.另外如果檢測結果為沒有在軌跡數(shù)據(jù)集中找到與以s為起始點的軌跡數(shù)據(jù)流T={s, x2,···, Xt}相匹配的不確定軌跡,可以考慮是否在數(shù)據(jù)集中存在不確定軌跡與當前數(shù)據(jù)流中的部分軌跡相匹配,即將軌跡數(shù)據(jù)流進行截取得到{ X2,···, Xt},并作為輸入軌跡數(shù)據(jù)流再次進行預測,直到發(fā)現(xiàn)匹配結果或無歷史數(shù)據(jù)可匹配為止.該預測算法的具體步驟下:

算法1.UDTM(D,T?)

輸入.歷史移動軌跡數(shù)據(jù)集D={T1,T2,···,Tn},T?:移動軌跡.

輸出.匹配的不確定軌跡集{UDf?}.

步驟1.令U為D中軌跡內(nèi)包含的所有位置信息的集合.

步驟2.構建不確定軌跡集UD.

算法首先構建不確定軌跡集,該過程中先基于聚類方法對原始軌跡的位置點進行約簡,得到約簡后的軌跡點集,時間復雜度為O(Nkt),其中N為數(shù)據(jù)集D的大小,且k,t?N;而后構建不確定軌跡集,該步驟需要遍歷軌跡數(shù)據(jù)集,時間復雜度為O(nk2),其中n為軌跡個數(shù),k為聚簇個數(shù);再進一步計算表示每條不確定軌跡中軌跡點分布特征的概率密度函數(shù),從而得到密度式不確定軌跡集,所需時間復雜度為O(nk2).可見構建不確定軌跡集的時間復雜度基本為線性時間.在軌跡預測階段,主要進行當前移動軌跡與數(shù)據(jù)集中所有具有相同起始點的密度式不確定軌跡關于分布是否一致的檢驗;已知軌跡點總數(shù)為N,不確定軌跡總數(shù)為k2,得不確定軌跡平均長度為N/k2,則核密度估計函數(shù)的計算時間復雜度為O(N/k2),若基于KS檢驗得到的具有相同起點的不確定軌跡個數(shù)為m以及待預測軌跡的長度為t,則預測算法的時間復雜度為O(tm(N/k2)).

圖2是軌跡預測示意圖.下面通過圖2解釋基于所提預測算法對當前用戶的軌跡終點進行預測的過程.

假設軌跡起點為A(x0, y0),而且已經(jīng)獲得軌跡數(shù)據(jù)集中的所有不確定軌跡及其概率密度函數(shù).若不確定軌跡集中包含不確定軌跡(A,B,fAB),(A,C,fAC)和(A,D,fAD),首先可得由A可能到達的終點包括軌跡點{B,C,D};隨著用戶移動行為的持續(xù)進行,采集到移動軌跡數(shù)據(jù)流{(X0, y0),(x1, y1),(X2, y2)},根據(jù)當前的數(shù)據(jù)流,經(jīng)KS檢驗得到當前移動軌跡與不確定軌跡(A,B,fAB)的密度分布并不一致的結論,此時的候選終點集縮減為{C,D};在采集到更豐富的軌跡數(shù)據(jù)集{(X0, y0),(x1, y1),(X2,y2),(x3, y3),(x4, y4)}后,經(jīng)KS檢驗可得軌跡(A,C,fAC)的密度分布與當前軌跡并不一致.最終可判斷A的可能終點為D.

圖2 軌跡預測示意圖Fig.2 Trajectory prediction

5 算法實施與性能分析

本文將從算法實施過程以及與幾種軌跡預測方法間的結果對比兩個角度,驗證所提算法的有效性與實用性.

5.1 算法實施

所提方法是一種軌跡終點預測方法,通過構建模型、訓練模型,再經(jīng)軌跡識別算法,實現(xiàn)對軌跡終點的預測.其中有兩個關鍵問題需要解決:一是并非任意兩點間的軌跡均適合軌跡預測,因此如何提取合理的軌跡,使得軌跡能夠真正描述一個移動行為,作為軌跡模式識別的基礎;二是如何確定待預測軌跡數(shù)據(jù)流的長度,如上所述隨著待預測軌跡采集樣本的增加可以提高軌跡識別的準確度,但同時也會增加預測復雜性和預測周期,所以確定合理的待預測軌跡數(shù)據(jù)流長度可以使預測方法更加高效.

實驗數(shù)據(jù)選用了軌跡研究領域普遍使用的公開數(shù)據(jù)集,由微軟亞洲研究院采集的GPS軌跡數(shù)據(jù)Geolife[19].該數(shù)據(jù)由Geolife記載了5年內(nèi)182名用戶的GPS坐標信息,包括經(jīng)緯度、海拔和時間點.該數(shù)據(jù)集包含17621個軌跡,24874410條位置信息,總距離1292951千米,總持續(xù)時間50176小時.這些軌跡由不同的GPS記錄器記錄.

為了提取合理的軌跡數(shù)據(jù),需要合理地確定軌跡的起始點與終點,起始點與終點之間的連續(xù)位置點則是一條合理的軌跡.Geolife軌跡數(shù)據(jù)是有明確的開始記錄時間和結束記錄時間的,所以可以根據(jù)此信息確定軌跡.另外,在數(shù)據(jù)集中任意一條軌跡內(nèi)還可能包含多條子軌跡,這些子軌跡雖然不屬于原始數(shù)據(jù)中實際意義上的完整軌跡,卻極可能成為分析其他用戶移動行為的依據(jù),因此有必要提取這些子軌跡的信息.例如對于用戶中途的休息、吃飯等行為,可能將原始軌跡拆分成幾個部分.因此為了獲取更豐富的軌跡數(shù)據(jù),首先對移動軌跡中的停留時間的頻次進行統(tǒng)計,得到如圖3所示的全部數(shù)據(jù)中所有用戶軌跡的停留時間頻次分布圖.

圖3中數(shù)據(jù)顯示停留時間與其對應的頻數(shù)在雙對數(shù)坐標系中趨于線性,屬于典型的冪律分布;在該數(shù)據(jù)集中一般的統(tǒng)計軌跡周期為1s或5s,超過5s的可視為移動的停頓,而當停留時間大于10s時,停留的頻數(shù)明顯下降.因此本文將移動行為中停留時間超過10s的停留點視為駐點,若駐點屬于某軌跡內(nèi)的軌跡點,則將其用于獲取原有軌跡的子軌跡;即根據(jù)駐點來定義軌跡預測中不確定軌跡的起點或終點;從軌跡數(shù)據(jù)集中獲取經(jīng)過任意兩個駐點的軌跡集合,計算這些軌跡內(nèi)包含的軌跡點的概率密度函數(shù),從而分析包含的軌跡點的分布特征,并構建以選取駐點為起始點和終點的不確定軌跡模型.

圖3 停留時間的頻次分布圖Fig.3 Frequency distribution of marking time

另一個關鍵是如何選取合理的軌跡數(shù)據(jù)流長度,以提高預測的準確度和效率.在理想情況下(不確定軌跡接近典型理論分布),根據(jù)預測算法的思想,設原假設為待預測軌跡數(shù)據(jù)流來自于某不確定軌跡的分布.若經(jīng)過KS檢驗,原假設被拒絕,可排除該不確定軌跡的候選.對于KS檢驗而言,當樣本數(shù)量較多時,能夠得到較為準確的檢驗結果,并易于區(qū)分密度分布相近的不確定軌跡,卻同時影響預測的效率.但當樣本數(shù)量較少時,假設檢驗的靈敏度則較差.因此待預測對象的軌跡數(shù)據(jù)流的規(guī)模直接影響了預測結果.所以本文嘗試分析不確定軌跡密度分布在不同的顯著水平下,可供拒絕原假設的最大樣本數(shù)量比.顯著性水平選取0.01～0.9,在不同的顯著性水平下,原假設被拒絕的平均軌跡數(shù)據(jù)流長度統(tǒng)計如圖4所示.可見在顯著性水平為0.01、樣本占總體平均4%時即可拒絕不符合的不確定軌跡,所需最大的數(shù)據(jù)流長度為7%;而當顯著性水平為0.05時,最大所需長度為4%,因此為了提高算法的準確性,本文選擇顯著性水平為0.05以及樣本規(guī)模為7%的參數(shù)作為軌跡識別條件.

圖4 不同顯著性水平下的有效樣本規(guī)模Fig.4 Significance level of different data scale

然而在實際的軌跡數(shù)據(jù)分析中,經(jīng)?？梢园l(fā)現(xiàn)軌跡一般情況下并不接近任何典型理論分布.如圖5所示,圖中的不確定軌跡u-t(Uncertain trajectory)以及待預測子軌跡s-t(Sub trajectory)的經(jīng)度和緯度的累積密度并不接近任何典型密度分布,其最大累積誤差也大于KS檢驗的指標值.在這種情況下,KS檢驗方法常常會較早的拒絕假設,使得任何軌跡都無法獲得匹配結果,因此本文根據(jù)KS檢驗的方法,以最大累積誤差為指標值,選擇待預測軌跡與不確定軌跡進行匹配,選取指標值最小的為最佳匹配對象,進而預測軌跡終點.

根據(jù)上述分析,本文將軌跡預測分為兩種情況:一是在KS檢驗過程中接受原假設的結果(例如密度分布接近典型理論分布的情況)進行直接預測;二是在KS檢驗失效時,將最小累積密度誤差作為指標值,選取誤差最小的作為最佳的匹配對象進行間接預測.通過兩種方法的結合,預測方法能夠針對不同情況進行軌跡終點預測.圖6描述了Geolife軌跡數(shù)據(jù)集上預測的準確度分析結果,可見在樣本規(guī)模40%時,預測準確度即可達到70%,并且隨著待預測軌跡數(shù)據(jù)流規(guī)模的不斷增加,所提方法的預測準確度不斷提高.而且預測結果的方差較小,說明所提預測方法不僅具有較高的預測精度,而且具有較好的穩(wěn)定性.

5.2 算法性能分析

為了說明本文所提方法的有效性,本文在Geo-life和 T-Drive數(shù)據(jù)集[19]上,與馬爾科夫方法(Markov-based methods,MBM)[14]、貝葉斯網(wǎng)絡方法(Bayesian network-based methods,BNM)[20]、回歸方法(Regression-based methods,RBM)[21]和神經(jīng)網(wǎng)絡方法(Neural network-based methods,NNM)[21]從預測準確性與方法運行效率兩方面進行對比.為了保證對比結果的公平性,對比算法的參數(shù)選擇參照對應文獻中效果最優(yōu)的參數(shù).基于Markov的方法根據(jù)文獻[14]中算法的執(zhí)行分析采用3階Markov模型.基于回歸的方法根據(jù)文獻[2]采用基于高斯核的回歸模型.基于神經(jīng)網(wǎng)絡的方法采用文獻[21]中基于多層感知機的網(wǎng)絡模型MLP,網(wǎng)絡模型中的隱層數(shù)量為5,訓練模型時的學習率、沖量因子以及學習次數(shù)分別為0.3、0.2和500次.

圖5 不確定軌跡預測的累計密度及其誤差變化Fig.5 Accumulation density and error of uncertain trajectory prediction

圖6 預測算法準確度分析Fig.6 Prediction method accuracy

為了驗證算法在不同數(shù)據(jù)條件下的準確性,在Geolife和T-Drive數(shù)據(jù)集上進行算法性能的對比分析.驗證采用十折交叉驗證法,將數(shù)據(jù)按70:30的比例劃分,其中70%作為訓練數(shù)據(jù)集,30%作為測試數(shù)據(jù)集,并以準確度為指標評價預測的準確性.但這4種預測方法一般都是短期預測,而本文方法是直接預測軌跡終點的長期預測;為了能夠統(tǒng)一尺度,對于測試數(shù)據(jù),分別獲取待預測軌跡的30%、60%和90%作為輸入數(shù)據(jù),進而對于3種不同長度的待預測軌跡數(shù)據(jù),對比各算法的預測準確性.

表1和表2分別記錄了兩個實驗數(shù)據(jù)集上進行交叉驗證的幾種算法的預測結果準確性,進行十折交叉驗證的實驗次數(shù)為120次,由于篇幅限制僅列出部分結果.從表中數(shù)據(jù)可以看出,所提算法在測試數(shù)據(jù)集上均能獲得較高的準確性,而且隨著待預測軌跡數(shù)據(jù)的豐富,即待預測軌跡的60%和90%作為輸入數(shù)據(jù)時,所得準確性相對更高,說明隨待預測軌跡數(shù)據(jù)規(guī)模的增加,UDTM的預測準確性也能逐漸提高.

為了更客觀地比較幾種算法的預測效果,將表1和表2中的數(shù)據(jù)進行統(tǒng)計分析,獲取每種情況下所得準確性的均值與方差,對比結果如圖7和圖8所示.在預測過程中,輸入軌跡數(shù)量為30%時,對比算法的準確性只有50%左右,而UDTM可以達到70%左右,當輸入軌跡數(shù)量為60%時,UDTM的預測準確度則可達到0.8～0.9,并且UDTM 預測準確性的方差為±0.0173,說明UDTM 方法在十折交叉驗證中具有較好的穩(wěn)定性.相比其他算法,UDTM算法在T-Drive和Geolife數(shù)據(jù)集中都具有較好的準確度,并且在T-Drive數(shù)據(jù)集上的準確度更高,其原因是Geolife的樣本都是個人的移動軌跡,相比T-Drive中的汽車軌跡具有更強的隨機性,因此預測準確性略低.

表1 Geolife數(shù)據(jù)集上各算法的預測準確性對比Table 1 Prediction accuracy comparison of several methods on Geolife

圖7 T-Drive數(shù)據(jù)集的準確性驗證Fig.7 Accuracy verification on T-Drive

時間復雜性是軌跡預測算法執(zhí)行的關鍵指標,好的預測算法應在具有較高預測準確度的同時兼具較快的響應速度.根據(jù)UDTM方法的模型定義,UDTM方法不是完全根據(jù)樣本的個數(shù),而是根據(jù)樣本的聚集情況估計核函數(shù)的數(shù)量和權重確定模型的核函數(shù)的個數(shù),由于模型的這種設計,使得算法在執(zhí)行時具有較高的效率.圖9描述了幾種對比算法的預測時間,UDTM雖然并未具有最快的預測時間,如圖9所示隨著輸入軌跡數(shù)據(jù)流的增多,UDTM的時間也并未顯著增長.其中RBM與NNM由于需要訓練模型優(yōu)化參數(shù),使其在建模時時間耗費較多;而UDTM只需要確定非參數(shù)模型中不同核的權重,但為了保證預測精度,需要首先對不確定軌跡進行建模,仍具有一定時間復雜度,因此相對于BNM和MBM而言需要的預測時間較長.另外在預測階段,由于RBM 需要將軌跡中的位置點進行回歸計算,所以當軌跡數(shù)量增加時,預測所需時間會呈指數(shù)型增長,而MBM、BNM、NNM以及UDTM由于在預測階段都是一次性計算,且模型本身不會更改,所以預測時間并不會隨軌跡數(shù)量的增長而顯著增加.

表2 T-Drive數(shù)據(jù)集上各算法的預測準確性對比Table 2 Prediction accuracy comparison of several methods on T-Drive

圖8 Geolife數(shù)據(jù)集的準確性驗證Fig.8 Accuracy verification on Geolife

圖9 算法執(zhí)行效率比較Fig.9 Algorithms execution efficiency comparison

雖然所提軌跡預測算法UDTM并非具有最快的預測效率,但并未較其他算法相差過多,并且也并不會隨著輸入數(shù)據(jù)的增多使得預測時間顯著增長,因此UDTM仍然具有較高的效率.另外即使在用戶軌跡數(shù)據(jù)流并不多的情況下,UDTM相較于其他算法還能夠較準確地預測待分析軌跡的終點,即在準確性方面具有較強的優(yōu)勢.

6 結論

針對移動對象軌跡的隨機性與不確定性問題,本文提出了一種基于非參數(shù)統(tǒng)計方法的不確定軌跡預測算法.首先利用核密度估計方法對軌跡數(shù)據(jù)集中的不確定軌跡進行建模,通過概率密度函數(shù)表示其不確定性的分布特征,基于非參估計的方法能夠獲得較客觀的符合數(shù)據(jù)實際分布的不確定軌跡分布情況;然后利用KS檢驗的方法分析輸入軌跡與已知的不確定軌跡分布間的匹配關系,從而根據(jù)相匹配的不確定軌跡預測輸入軌跡的目標終點.所提方法充分考慮軌跡中體現(xiàn)的移動用戶行為的不確定性,對歷史軌跡中任意可能的位置進行計算,因此在實際預測問題中,能夠獲得較好的建模和預測能力,在真實數(shù)據(jù)集上的實驗也驗證了所提方法的有效性和可靠性.