喬少杰 韓楠 丁治明 金澈清 孫未未 舒紅平

隨著無線通信和定位技術(shù)的高速發(fā)展,人們對(duì)持續(xù)移動(dòng)物體所處的空間位置的跟蹤能力不斷加強(qiáng),推動(dòng)相關(guān)應(yīng)用領(lǐng)域的研究不斷深入,如智能交通控制、智能導(dǎo)航和軍事指揮等.此類應(yīng)用系統(tǒng)往往基于移動(dòng)對(duì)象數(shù)據(jù)庫(kù)構(gòu)建,其中存儲(chǔ)了大量關(guān)于移動(dòng)對(duì)象時(shí)空位置及運(yùn)動(dòng)狀態(tài)的信息.這些數(shù)據(jù)通常以軌跡的形式存儲(chǔ),隱藏著關(guān)于移動(dòng)對(duì)象大量的行為特征及運(yùn)動(dòng)規(guī)律.然而,移動(dòng)對(duì)象所處的運(yùn)動(dòng)環(huán)境往往是動(dòng)態(tài)變化的,不能單純依賴靜態(tài)交通網(wǎng)絡(luò)環(huán)境預(yù)測(cè)其運(yùn)動(dòng)行為,需要綜合考慮移動(dòng)速度和方向的動(dòng)態(tài)變化對(duì)對(duì)象運(yùn)動(dòng)行為的影響.如何綜合考慮主客觀因素,高效準(zhǔn)確地查詢和預(yù)測(cè)移動(dòng)對(duì)象不確定性位置成為當(dāng)前移動(dòng)數(shù)據(jù)管理領(lǐng)域的研究熱點(diǎn)[1].尤其值得注意的是,在包含較為復(fù)雜的軌跡模式場(chǎng)景下，典型運(yùn)動(dòng)模式不止一個(gè),一條軌跡可能隸屬于多個(gè)軌跡模式,稱之為多模式.不同類型移動(dòng)對(duì)象運(yùn)動(dòng)行為各有差異,相同類型的移動(dòng)對(duì)象由于主客觀因素影響,運(yùn)動(dòng)模式也不盡相同,因此挖掘多模式移動(dòng)對(duì)象運(yùn)動(dòng)行為特征更具實(shí)際意義.

多模式移動(dòng)對(duì)象位置預(yù)測(cè)是一項(xiàng)非常困難和富有挑戰(zhàn)意義的課題.1)由于移動(dòng)對(duì)象運(yùn)動(dòng)模式復(fù)雜多變,且通過定位系統(tǒng)獲得的數(shù)據(jù)流信息量大,具有不確定性,需要更加穩(wěn)定和具有可伸縮性的挖掘方法進(jìn)行處理;2)位置預(yù)測(cè)需要盡可能快地對(duì)可能運(yùn)動(dòng)軌跡進(jìn)行評(píng)價(jià),延時(shí)或滯后將產(chǎn)生無意義的預(yù)測(cè)結(jié)果;3)基于模擬技術(shù)的預(yù)測(cè)方法依賴于大量輸入?yún)?shù),這些參數(shù)的設(shè)置極大地影響模型的準(zhǔn)確性,對(duì)于不確定性的軌跡數(shù)據(jù)進(jìn)行預(yù)測(cè),需要考慮諸多客觀因素和領(lǐng)域?qū)＜抑R(shí);4)如果算法設(shè)計(jì)不合理,隨著移動(dòng)對(duì)象數(shù)目的增加,模型的計(jì)算代價(jià)可能呈指數(shù)級(jí)增長(zhǎng).下面以移動(dòng)對(duì)象軌跡預(yù)測(cè)為主要背景,以智能交通系統(tǒng)為例說明問題意義和概貌.

智能交通旨在建立一種在較大范圍內(nèi),全方位發(fā)揮作用的實(shí)時(shí)、準(zhǔn)確和高效的綜合運(yùn)輸和管理系統(tǒng).系統(tǒng)將采集到的各種道路交通及服務(wù)信息處理后,傳輸?shù)竭\(yùn)輸系統(tǒng)的各種用戶(例如駕駛員、居民、警察),出行者可實(shí)時(shí)選擇交通方式和交通路線,交通管理部門可進(jìn)行自動(dòng)和合理的交通疏導(dǎo)、控制及事故處理.決策者可知每天哪一時(shí)段,具體在哪一區(qū)域是機(jī)動(dòng)車出行的高峰期,應(yīng)該采用何種手段可以使路網(wǎng)上的交通流量處于最佳狀態(tài),改善交通擁擠和阻塞狀況,最大限度地提高交通的通行能力,提高整個(gè)公路運(yùn)輸系統(tǒng)的機(jī)動(dòng)性、安全性和運(yùn)輸效率.可以形式化描述為在一組約束下,確定一組閾值ε和σ,使得

上式(?)意義為求取當(dāng)各種車輛總和∑Ti＜ε,且保證不同時(shí)段j內(nèi)交通事故發(fā)生率Pj＜σ時(shí),各種車輛的數(shù)量Num(Ti),并且在測(cè)試數(shù)據(jù)集上支持度超過Supp,置信度超過Conf.其中,ε表示交通運(yùn)輸能力,σ表示事故發(fā)生率門限值.

本文結(jié)構(gòu)如下:第1節(jié)對(duì)國(guó)內(nèi)外在移動(dòng)對(duì)象不確定性軌跡預(yù)測(cè)領(lǐng)域的成果進(jìn)行綜述;第2節(jié)針對(duì)單一運(yùn)動(dòng)模式軌跡,挖掘軌跡熱點(diǎn)區(qū)域并利用頻繁模式樹準(zhǔn)確高效預(yù)測(cè)移動(dòng)對(duì)象連續(xù)位置信息;第3節(jié)介紹一個(gè)面向復(fù)雜運(yùn)動(dòng)場(chǎng)景的基于高斯混合回歸的多模式軌跡預(yù)測(cè)模型;第4節(jié)驗(yàn)證本文提出的兩種針對(duì)不同運(yùn)動(dòng)模式的軌跡預(yù)測(cè)算法的性能;第5章總結(jié)全文工作并對(duì)未來工作進(jìn)行展望.

1 國(guó)內(nèi)外研究現(xiàn)狀

針對(duì)移動(dòng)對(duì)象的連續(xù)位置預(yù)測(cè)主要包括過去軌跡的重現(xiàn)及當(dāng)前和未來軌跡的預(yù)測(cè),主要研究集中于軌跡頻繁模式挖掘,通過挖掘頻繁模式找出典型運(yùn)動(dòng)路徑.Hu等[2]將連續(xù)軌跡視為離散狀態(tài)點(diǎn)之間轉(zhuǎn)變的過渡,對(duì)軌跡離散狀態(tài)分析的不足之處在于對(duì)大量時(shí)空數(shù)據(jù)進(jìn)行離散化處理代價(jià)極高,而且需要計(jì)算離散數(shù)據(jù)點(diǎn)之間的相關(guān)性.Parker等[3]設(shè)計(jì)了移動(dòng)對(duì)象運(yùn)動(dòng)目標(biāo)概率函數(shù)可以滿足的若干axiom,這些axiom用于精確度量預(yù)測(cè)軌跡與真實(shí)軌跡之間的差異.Song等[4]在Science上發(fā)表了預(yù)測(cè)人類移動(dòng)性的研究成果,通過測(cè)量個(gè)體軌跡的信息熵,定量地給出了人類動(dòng)態(tài)運(yùn)動(dòng)軌跡具有93%的可預(yù)測(cè)性,并證明了人類有規(guī)律的運(yùn)動(dòng)路線與距離無關(guān).Centola[5]在Science上的工作是在原始GPS數(shù)據(jù)中使用層次型馬爾科夫模型抽取重要地點(diǎn),進(jìn)而檢測(cè)用戶的行為模式.針對(duì)已有軌跡預(yù)測(cè)算法僅能預(yù)測(cè)短期內(nèi)運(yùn)動(dòng)路徑的不足,Jeung等[6]提出了一種基于路網(wǎng)的移動(dòng)預(yù)測(cè)模型,用于準(zhǔn)確計(jì)算移動(dòng)對(duì)象在交叉路口運(yùn)動(dòng)變換模式和在不同路段上的速度信息,但該方法局限于路網(wǎng)中應(yīng)用.Zhou等[7]利用動(dòng)態(tài)選取的參考軌跡構(gòu)建預(yù)測(cè)模型,模型建立之前目標(biāo)軌跡是已知的,具備先驗(yàn)知識(shí),可以基于少量的歷史軌跡構(gòu)建精準(zhǔn)的預(yù)測(cè)模型.

隨著越來越多不同種類移動(dòng)對(duì)象軌跡數(shù)據(jù)被收集,近期多模式軌跡預(yù)測(cè)的工作得到學(xué)者的廣泛關(guān)注,Pan等[8]提出了基于多變?cè)龖B(tài)分布的線性預(yù)測(cè)器,應(yīng)用這一方法預(yù)測(cè)會(huì)產(chǎn)生延遲,不能應(yīng)用于交通流的實(shí)時(shí)監(jiān)控環(huán)境中.Qiao等[9]借助隱馬爾科夫模型(Hidden Markov model,HMM),設(shè)計(jì)實(shí)現(xiàn)了一種可以自適應(yīng)調(diào)整軌跡預(yù)測(cè)參數(shù)的動(dòng)態(tài)預(yù)測(cè)算法,根據(jù)不同類型軌跡數(shù)據(jù)預(yù)測(cè)最佳路線,但是這一模型沒有考慮大數(shù)據(jù)環(huán)境下算法的運(yùn)行時(shí)間性能問題.此外,喬少杰等[10]提出了基于隱馬爾科夫模型的自適應(yīng)軌跡預(yù)測(cè)模型,該算法通過對(duì)大數(shù)據(jù)環(huán)境下移動(dòng)對(duì)象海量軌跡利用基于密度的聚類方法進(jìn)行位置密度分區(qū)和高效分段處理,根據(jù)輸入軌跡自動(dòng)選取參數(shù)組合,避免隱馬爾科夫模型中隱狀態(tài)不連續(xù)、狀態(tài)停留等問題.Ding等[11]近期提出了一種路網(wǎng)匹配的基于軌跡數(shù)據(jù)庫(kù)的交通流分析方法,用于預(yù)測(cè)移動(dòng)對(duì)象位置信息.Xu等[12]提出了用于避免大圖上過度二次計(jì)算的有效策略,更好地支持動(dòng)態(tài)路網(wǎng)中路徑動(dòng)態(tài)規(guī)劃.為了支持軌跡大數(shù)據(jù)中個(gè)性化多模式運(yùn)動(dòng)路徑預(yù)測(cè),Dai等[13]利用高斯混合模型,描述行駛偏好矢量中隨機(jī)變量的概率分布，構(gòu)建帶權(quán)重的軌跡圖，權(quán)重反映對(duì)象候選路徑的可能性，并結(jié)合最短路徑算法推薦個(gè)性化運(yùn)動(dòng)軌跡.Tripathy等[14]根據(jù)不同對(duì)象的歷史軌跡特征,構(gòu)建線性函數(shù),預(yù)測(cè)移動(dòng)對(duì)象將來可能運(yùn)動(dòng)位置,所提方法可以保證較小的預(yù)測(cè)偏差.Xu等[15]提出一種通用位置表達(dá)模型,定義不同對(duì)象可能的位置,實(shí)現(xiàn)復(fù)雜場(chǎng)景不同運(yùn)動(dòng)模式下軌跡預(yù)測(cè).黃玉龍等[16]提出了一種改進(jìn)的高斯近似濾波方法,用于再入飛行器的目標(biāo)跟蹤.陳成等[17]提出了一種基于四階貝塞爾曲線的無人車可行軌跡規(guī)劃算法,用于在實(shí)際道路中行駛的車輛.考慮到高緯度和不確定性對(duì)軌跡預(yù)測(cè)準(zhǔn)確性的影響,Monfort等[18]提出了一種逆最優(yōu)控制方法,用于計(jì)算人類活動(dòng)軌跡出現(xiàn)的概率.

通過對(duì)上述移動(dòng)對(duì)象軌跡預(yù)測(cè)工作進(jìn)行分析,可以得到如下結(jié)論:1)如果針對(duì)海量軌跡數(shù)據(jù)挖掘移動(dòng)對(duì)象頻繁軌跡模式,已有算法需要多次掃描數(shù)據(jù)庫(kù),代價(jià)很高,需要設(shè)計(jì)新型頻繁模式挖掘算法,提高挖掘的效率和準(zhǔn)確性.2)現(xiàn)有軌跡預(yù)測(cè)算法對(duì)具有單一簡(jiǎn)單模式的移動(dòng)對(duì)象的位置跟蹤預(yù)測(cè)效果較好,對(duì)于復(fù)雜場(chǎng)景下多模式軌跡預(yù)測(cè)的研究?jī)?nèi)容相對(duì)較少.

2 基于頻繁軌跡模式樹的軌跡預(yù)測(cè)算法

移動(dòng)對(duì)象的運(yùn)動(dòng)模式通常比較單一,例如在城市交通道路上勻速運(yùn)動(dòng).針對(duì)單一運(yùn)動(dòng)模式,本節(jié)提出一種基于頻繁模式挖掘的軌跡預(yù)測(cè)算法[19].

2.1 軌跡熱點(diǎn)區(qū)域挖掘算法

在預(yù)測(cè)前改進(jìn)DBSCAN算法對(duì)海量GPS軌跡點(diǎn)進(jìn)行聚類挖掘軌跡熱點(diǎn)區(qū)域,可以將軌跡點(diǎn)與由信號(hào)不穩(wěn)定等原因產(chǎn)生的噪點(diǎn)區(qū)分.軌跡熱點(diǎn)區(qū)域挖掘算法RoIDiscovery采用密度聚類思想,通過遍歷每個(gè)軌跡點(diǎn)的鄰域生成簇.如果軌跡點(diǎn)p的鄰域內(nèi)包含多于θ個(gè)軌跡點(diǎn),則創(chuàng)建一個(gè)新的簇,將p作為該簇的核心對(duì)象.然后,遞歸地遍歷核心對(duì)象直接密度可達(dá)的對(duì)象,這個(gè)過程中包含簇的合并操作.當(dāng)沒有新的點(diǎn)可以被添加到任何簇時(shí),過程結(jié)束.基于密度的軌跡熱點(diǎn)區(qū)域挖掘算法如算法1所示[19].

算法1.基于密度的軌跡聚類算法

輸入.軌跡數(shù)據(jù)集Tr,聚簇半徑ε,最少軌跡點(diǎn)數(shù)θ.

輸出.聚類后簇集合R={R1,R2,···,Rn}.

1.n=0;

2.foreachp∈Trdo

3.markpas visited;

4.N=getNeighbours(p,ε);

5.ifsize(N)＜ θthen

6.markpas noise;

7.else

8.create a new clusterRk;

9.ExpandCluster(p,N,Rk,ε,θ).

算法1的基本思想為:遍歷Tr中所有軌跡點(diǎn),初始化簇個(gè)數(shù)(第1行);將軌跡點(diǎn)p標(biāo)記為已訪問(第3行);第4～9行利用getNeighbours(·)函數(shù)計(jì)算軌跡點(diǎn)p與其他軌跡點(diǎn)的距離,將距離小于ε的軌跡點(diǎn)存入集合N中,如果size(N)＜θ,則標(biāo)記p為噪聲點(diǎn),否則以p為核心建立新簇,并調(diào)用ExpandCluster(·)函數(shù)遞歸訪問N中軌跡點(diǎn).ExpandCluster(·)基本思想是對(duì)N鄰域內(nèi)的所有點(diǎn)進(jìn)行半徑檢查,如果大于θ,擴(kuò)展N的數(shù)目,將新節(jié)點(diǎn)加入擴(kuò)展后的簇.當(dāng)沒有新節(jié)點(diǎn)可以被添加到任何簇,該過程結(jié)束.

2.2 頻繁軌跡模式挖掘算法

本節(jié)介紹基于頻繁軌跡模式樹的軌跡預(yù)測(cè)算法FTP-mining[19],首先給出頻繁軌跡模式樹定義.

定義 1(頻繁軌跡模式樹—FTP-tree)[19].FTP-tree由一個(gè)標(biāo)記為空的根節(jié)點(diǎn)及一系列由原子路段組成的前綴子樹構(gòu)成,且包含一個(gè)頭節(jié)點(diǎn)表Header table.FTP-tree的數(shù)據(jù)結(jié)構(gòu)與FP-tree類似,前綴子樹上的每一個(gè)節(jié)點(diǎn)具有三個(gè)屬性:id,count和pointer,其中id表示原子路段的標(biāo)識(shí),count表示從根節(jié)點(diǎn)到達(dá)某一節(jié)點(diǎn)的路徑被訪問次數(shù),pointer表示指向FTP-tree中具有相同id的下一個(gè)節(jié)點(diǎn)指針.Header table中每一行記錄包含兩個(gè)屬性:節(jié)點(diǎn)id和頭指針(指向FTP-tree中具有某id的第一個(gè)節(jié)點(diǎn)).基于頻繁軌跡模式樹的軌跡預(yù)測(cè)算法FTP-mining如算法2所示[19].

算法2.FTP-mining( FFF, α)

輸入.具有根節(jié)點(diǎn)t的FTP-treeF,與t對(duì)應(yīng)的軌跡熱點(diǎn)路段L,空集合α.

輸出.頻繁軌跡模式集合R={f1,f2,···,fn}.

1.構(gòu)建一個(gè)空的頻繁軌跡模式集合R;

2.if有一條從t出發(fā)的路徑Qthen

3.構(gòu)建一條模式q=Q∪α;

4.support_count=min{counti};//counti表示Q中第i個(gè)節(jié)點(diǎn)被訪問的次數(shù);

5.Q.add(q);

6.else

7.for each候選項(xiàng)li∈Ldo

8.構(gòu)建模式p=li∪α;

9.suppor_tcount=min{counti};

10.構(gòu)建與p對(duì)應(yīng)的conditional pattern base和conditional FTP-treeF0;

11.ifF0nullthen

12.FTP-mining(F0,p);

13.ifR不變化then

14.R.add(p);

15.輸出R中頻繁軌跡模式.

算法2的基本思想為:首先生成長(zhǎng)度為1的頻繁序列集;然后根據(jù)長(zhǎng)度為1的頻繁序列集生成長(zhǎng)度為2的頻繁序列集;依此類推,產(chǎn)生所有頻繁序列模式,與FP-tree[20]類似.FTP-mining與FTP-tree的不同之處在于:1)FTP-tree中的項(xiàng)集表示被移動(dòng)對(duì)象訪問的路段,從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的一條完整的路徑表示一條頻繁軌跡模式;2)每一條前綴樹帶有時(shí)間戳信息,時(shí)間戳表示訪問一條路段的時(shí)間間隔.基于FTP-tree的軌跡預(yù)測(cè)算法包含F(xiàn)TP-tree構(gòu)建和FTP-mining兩個(gè)步驟,FTP-tree的構(gòu)建過程與FP-tree的構(gòu)建相同,不再贅述.FTP-mining算法挖掘頻繁軌跡模式的過程不同于FP-tree,其主要目標(biāo)是找到大于給定門限值的最長(zhǎng)的頻繁路徑,算法2第4～12行計(jì)算生成的最長(zhǎng)頻繁序列模式?jīng)]有考慮路段模式組合的情況,第10行中conditional pattern base是具有相同前綴模式的頻繁路段項(xiàng)子集合.

在上述兩項(xiàng)技術(shù)基礎(chǔ)上,給出基于FTP-tree的移動(dòng)對(duì)象軌跡預(yù)測(cè)算法PathPrediction,如算法3所示[19].

算法3.基于FTP-tree的移動(dòng)對(duì)象軌跡預(yù)測(cè)算法PathPrediction

輸入.移動(dòng)對(duì)象數(shù)據(jù)庫(kù)D,路網(wǎng)中路段集合S.

輸出.預(yù)測(cè)軌跡集合Tr.

1.R=RoIDiscovery(D,S);

2.foreach RoIrinRdo

3.Tr=FTPTreeGeneration(r);

4.FTP-mining(Tr,α);

5.輸出最可能運(yùn)動(dòng)軌跡集合Tr.

算法3首先利用RoIDiscovery算法從移動(dòng)對(duì)象數(shù)據(jù)庫(kù)D找出熱點(diǎn)區(qū)域集合R(第1行).然后,對(duì)R中的每個(gè)軌跡熱點(diǎn)區(qū)域構(gòu)建FTP-tree(第2行和第3行),并利用FTP-mining計(jì)算出頻繁軌跡模式(第4行).最后,輸出所有頻繁軌跡模式(第5行).

3 基于GPR的復(fù)雜多模式軌跡預(yù)測(cè)模型

本節(jié)主要解決復(fù)雜場(chǎng)景中包含多種運(yùn)動(dòng)模式且很難用單一一種運(yùn)動(dòng)模式刻畫的復(fù)雜運(yùn)動(dòng)模式預(yù)測(cè)問題,首先介紹利用高斯過程回歸模型實(shí)現(xiàn)單一運(yùn)動(dòng)模式預(yù)測(cè),進(jìn)而引出基于高斯混合回歸的復(fù)雜運(yùn)動(dòng)模式預(yù)測(cè)模型.

3.1 高斯過程回歸

一種典型運(yùn)動(dòng)模式路徑可以由一個(gè)高斯過程表示,利用高斯過程回歸(Gaussian process regression,GPR)[21]進(jìn)行預(yù)測(cè).下面介紹針對(duì)簡(jiǎn)單運(yùn)動(dòng)模式的高斯過程回歸模型的理論基礎(chǔ).

對(duì)于輸入訓(xùn)練數(shù)據(jù)集其中xi∈Rd為d維輸入矢量,yi∈R 為相應(yīng)輸出.對(duì)于給定輸入數(shù)據(jù)集合X,可構(gòu)成一個(gè)隨機(jī)變量集合{f(x1),f(x2),···,f(xN)},且具有聯(lián)合高斯分布,則該高斯過程(Gaussian process,GP)的全部統(tǒng)計(jì)數(shù)字特征可由均值函數(shù)m(x)和協(xié)方差函數(shù)k(x,x′) 確定,即

其中,m(x)=E[f(x)],k(x,x′)=E[(f(x)?m(x))×(f(x′)?m(x′))],本文所用核函數(shù)為標(biāo)準(zhǔn)指數(shù)協(xié)方差函數(shù),表示為

其中,θ0為指數(shù)權(quán)重參數(shù),θ1表示長(zhǎng)度規(guī)模參數(shù),δij是狄拉克函數(shù),當(dāng)i=j時(shí),函數(shù)δij=1,否則為0.

應(yīng)用高斯過程回歸的目的是在訓(xùn)練集輸入數(shù)據(jù)X和輸出數(shù)據(jù)Y之間建立映射關(guān)系f(·):Rd→R,繼而預(yù)測(cè)出與新測(cè)試輸入數(shù)據(jù)x?對(duì)應(yīng)最可能的觀測(cè)輸出值f(x?),求取回歸估計(jì)函數(shù)過程如下.

求解過程:由于輸入輸出的觀測(cè)和測(cè)量數(shù)據(jù)經(jīng)常伴隨噪聲數(shù)據(jù)干擾,因此將噪聲數(shù)據(jù)考慮進(jìn)觀測(cè)目標(biāo)值y,建立高斯過程回歸一般模型:y=f(x)+ε.其中,ε為獨(dú)立的高斯白噪聲,符合高斯分布,均值為0,方差為σ2,可記為ε～N(0,σ2).由于噪聲ε獨(dú)立于f(x),所以當(dāng)f(x)服從高斯分布時(shí),有限觀測(cè)值聯(lián)合分布的集合y同樣可形成一個(gè)高斯過程,即

其中,協(xié)方差函數(shù)以矩陣方式表達(dá),即

式中,I表示N×N的單位矩陣,C(X,X)表示N×N協(xié)方差矩陣,K(X,X)表示N×N的核函數(shù)矩陣,元素Kij=k(xi,xj),K(X,X)表示如下:

K(X?,X)=[k(x?,x1),k(x?,x2),...,k(x?,xn)]表示K(X,X)中某一行,且K(X?,X?)=k(x?,x?).

由于整個(gè)高斯過程模型利用多元高斯分布表達(dá)數(shù)據(jù),根據(jù)貝葉斯原理可知,GP在給定訓(xùn)練集數(shù)據(jù)Dtrain集合上建立先驗(yàn)函數(shù),然后在測(cè)試數(shù)據(jù)集下轉(zhuǎn)變?yōu)楹篁?yàn)分布,則訓(xùn)練數(shù)據(jù)輸入數(shù)據(jù)X的輸出向量y和測(cè)試數(shù)據(jù)X?的輸出向量y?之間的聯(lián)合高斯密度分布為

為了求取輸出向量y?,需要借助聯(lián)合高斯密度回歸定理.

由此可知,當(dāng)(y,y?)T服從聯(lián)合高斯分布時(shí),條件概率p(y?|y)是高斯分布,所以得到y(tǒng)?關(guān)于y回歸方程及相應(yīng)方差如下:根據(jù)定理1,可以得到關(guān)于預(yù)測(cè)輸出數(shù)據(jù)的條件概率P(y?|y)和GP回歸方程,即

其中,K?=K(X?,X),K??=K(X?,X?),于是y?關(guān)于y的最佳回歸估計(jì)方程,即y?的預(yù)測(cè)值為

而關(guān)于y?的預(yù)測(cè)不確定性區(qū)間用方差表示為

3.2 基于高斯混合回歸的軌跡預(yù)測(cè)模型

在軌跡包含較為復(fù)雜運(yùn)動(dòng)模式場(chǎng)景下,需要采用多個(gè)高斯過程,利用高斯混合回歸模型(Gaussian mixture regression,GMR)[22]進(jìn)行軌跡預(yù)測(cè)分析.

3.2.1 訓(xùn)練模型

在具有多種軌跡模式的場(chǎng)景中,一條軌跡可能隸屬于多個(gè)軌跡模式,準(zhǔn)確地刻畫一條軌跡需要采用混合模型.例如,對(duì)于軌跡S=〈(x1,y1),(x2,y2),···,(xn,yn)〉,本文將其轉(zhuǎn)化為X和Y方向上的n維矢量X=(x1,x2,···,xn)T和Y=(y1,y2,···,yn)T,n表示軌跡的觀測(cè)點(diǎn)個(gè)數(shù),X和Y方向上矢量在所有M個(gè)軌跡模式中出現(xiàn)的總概率是由不同運(yùn)動(dòng)模式的高斯概率混合而成,表示為

其中,M表示混合軌跡模式的狀態(tài)數(shù)量,wi表示第i個(gè)軌跡模式的權(quán)重,且和Σx,i分別表示第i個(gè)軌跡模式狀在X方向上的均值和協(xié)方差,參數(shù)λ={wi,μi,Σi},i=1,2,···,M.GP(Xn|μx,i,Σx,i)表示軌跡矢量Xn相對(duì)第i個(gè)運(yùn)動(dòng)模式狀態(tài)的高斯概率函數(shù),定義如下:

其中,μ和Σ表示軌跡高斯過程的典型運(yùn)動(dòng)模式在X方向上的均值和協(xié)方差矩陣,μ=[E(x1),E(x2),···,E(xd)]T,Σ =(Cij)d×d,Cij=Cov(xi,xj).

于是,對(duì)于軌跡訓(xùn)練集S={X,Y},整個(gè)軌跡訓(xùn)練集高斯混合模型似然函數(shù)為

模型中如何計(jì)算復(fù)雜運(yùn)動(dòng)模式中的參數(shù)λ是一個(gè)關(guān)鍵步驟,本文通過使軌跡訓(xùn)練模型(即式(14)和式(15))概率達(dá)到最大,從已知的訓(xùn)練軌跡矢量集S={X,Y}中學(xué)習(xí)訓(xùn)練出最佳參數(shù)λ,利用概率最大的方式,使用最大似然法估計(jì)(Expectationmaximization,EM),選出構(gòu)成運(yùn)動(dòng)模型的概率密度最大的那一組參數(shù),為軌跡回歸分析預(yù)測(cè)時(shí)所用.

EM 算法在迭代中改善模型參數(shù)估計(jì),在每次迭代中不斷地增加模型估計(jì)參數(shù)λ與觀測(cè)訓(xùn)練軌跡X方向矢量xi(由若干軌跡點(diǎn)構(gòu)成)的匹配概率,這里討論X軸方向,Y軸方向情況類似,即每次迭代使式(14)滿足p(X|λk+1)＞p(X|λk),其中k表示迭代的次數(shù).通過不斷地學(xué)習(xí),獲得最佳匹配訓(xùn)練軌跡矢量集X={x1,x2,···,xn}.迭代訓(xùn)練的目的即為找到一組λ,使得p(X|λ)最大,即

由于篇幅限制,求解使p(X|λ)達(dá)到最大的參數(shù)λ值的過程參見文獻(xiàn)[23].

3.2.2 預(yù)測(cè)模型

在上一節(jié)的基礎(chǔ)上,本節(jié)給出基于GMR的軌跡預(yù)測(cè)模型.已知訓(xùn)練數(shù)據(jù)集為S=(x,y),其中輸入數(shù)據(jù)為x,輸出數(shù)據(jù)為y.測(cè)試數(shù)據(jù)集S?=(x?,y?), 輸入測(cè)試數(shù)據(jù)為x?, 預(yù)測(cè)輸出y?, 那么[y,y?]T的聯(lián)合概率密度函數(shù)遵從如下的GMR模型.

其中并且滿足每個(gè)高斯成分GP(·|μi,Σi) 可由式(9)計(jì)算出,聯(lián)合概率密度函數(shù)表示為

其中,除此之外,邊緣密度py和條件密度py?|y可由式(17)和式(18)求得,y的邊緣密度函數(shù)為

條件密度函數(shù)為

其中混合權(quán)重

因此,y?關(guān)于y的回歸函數(shù)(y?預(yù)測(cè)值)為

對(duì)應(yīng)的方差為

式(22)稱作高斯混合回歸模型,基于GMR的軌跡預(yù)測(cè)算法思路即利用式(20)對(duì)預(yù)測(cè)數(shù)據(jù)概率密度函數(shù)建模,應(yīng)用EM算法估計(jì)相應(yīng)參數(shù),依據(jù)正態(tài)分布數(shù)據(jù)的條件分布(參見定理1)得到m個(gè)高斯分量回歸函數(shù),利用式(22)將總體回歸函數(shù)加權(quán)混合實(shí)現(xiàn)對(duì)整體數(shù)據(jù)的回歸預(yù)測(cè)分析.

4 實(shí)驗(yàn)及算法性能分析

4.1 基于FTP-tree的軌跡預(yù)測(cè)算法性能分析

為了驗(yàn)證基于FTP-tree的軌跡預(yù)測(cè)算法預(yù)測(cè)準(zhǔn)確性和時(shí)間性能,對(duì)Naive算法(沒有采用軌跡熱點(diǎn)區(qū)域挖掘RoIDiscovery算法,僅應(yīng)用FTP-mining算法),PutMode算法[24](基于時(shí)間連續(xù)貝葉斯網(wǎng)絡(luò)的軌跡預(yù)測(cè)算法)和PathPrediction算法(集成軌跡熱點(diǎn)區(qū)域挖掘和FTP-mining算法)進(jìn)行對(duì)比實(shí)驗(yàn).實(shí)驗(yàn)數(shù)據(jù)集使用New York,Kansas和Chengdu真實(shí)矢量地圖.New York,Kansas和Chengdu地圖分別由435186×563287,348693×437998和23514×25672個(gè)像素構(gòu)成,合成的軌跡數(shù)據(jù)通過修改Brinkhoff軌跡生成器[25]生成.為了進(jìn)一步證明算法的真實(shí)有效性,實(shí)驗(yàn)使用微軟亞洲研究院GeoLife數(shù)據(jù)集[26],由182個(gè)用戶5年間1129天GPS軌跡數(shù)據(jù)組成,包含17621條軌跡.

4.1.1 軌跡預(yù)測(cè)準(zhǔn)確性對(duì)比

實(shí)驗(yàn)利用預(yù)測(cè)命中率評(píng)價(jià)算法的有效性[19].

定義2(預(yù)測(cè)命中).已知一條軌跡序列S={s1,s2,···,sk},根據(jù)S得到的預(yù)測(cè)軌跡序列為Tp={p1,p2,···,pk},dist(p,q) 表示時(shí)空點(diǎn)p和q之間的歐氏距離,θ是一個(gè)給定的距離門限值,dist(si,pi)≤θ表明一次軌跡預(yù)測(cè)命中,預(yù)測(cè)命中定義為

定義3(預(yù)測(cè)命中率).已知一條軌跡序列S和預(yù)測(cè)得到的軌跡序列Tp,預(yù)測(cè)命中率定義為

其中,|Tp|表示組成Tp軌跡點(diǎn)的數(shù)量.

圖1和圖2給出了不同算法隨軌跡數(shù)量增加的軌跡預(yù)測(cè)準(zhǔn)確率.其中,橫軸表示軌跡數(shù)量,縱軸表示預(yù)測(cè)準(zhǔn)確率.實(shí)驗(yàn)結(jié)果表明,融合軌跡熱點(diǎn)區(qū)域挖掘和基于FTP-tree的頻繁軌跡模式挖掘方法PathPrediction的預(yù)測(cè)精度在Chengdu數(shù)據(jù)集上平均高出PutMode算法8.0個(gè)百分點(diǎn),高出Naive預(yù)測(cè)算法29.2個(gè)百分點(diǎn),在GeoLife真實(shí)數(shù)據(jù)集上平均高出PutMode算法5.5個(gè)百分點(diǎn),高出Naive預(yù)測(cè)算法28.9個(gè)百分點(diǎn).原因在于PathPrediction算法對(duì)經(jīng)過聚類后的軌跡熱點(diǎn)區(qū)域進(jìn)行頻繁軌跡模式的挖掘,軌跡熱點(diǎn)區(qū)域是由經(jīng)過噪聲處理后的軌跡點(diǎn)組成的,因此預(yù)測(cè)的準(zhǔn)確性更高.此外,構(gòu)建的頻繁軌跡模式樹FTP-tree綜合考慮了真實(shí)路網(wǎng)中的軌跡運(yùn)動(dòng)規(guī)則,因此預(yù)測(cè)的結(jié)果與移動(dòng)對(duì)象真實(shí)運(yùn)動(dòng)情況更加吻合,而PutMode算法融合了軌跡聚類和時(shí)間連續(xù)貝葉斯網(wǎng)絡(luò),相比于沒有進(jìn)行軌跡熱點(diǎn)挖掘的Naive算法準(zhǔn)確性要高.

圖1 Chengdu數(shù)據(jù)集下不同算法預(yù)測(cè)準(zhǔn)確率比較Fig.1 Prediction accuracy comparison of different algorithms under Chengdu datasets

圖2 GeoLife數(shù)據(jù)集下不同算法預(yù)測(cè)準(zhǔn)確率比較Fig.2 Prediction accuracy comparison of different algorithms under GeoLife datasets

4.1.2 軌跡預(yù)測(cè)時(shí)間性能對(duì)比

為了驗(yàn)證本文提出的基于FTP-tree的軌跡預(yù)測(cè)算法的時(shí)間性能,本節(jié)實(shí)驗(yàn)在不同的電子地圖(New York,Kansas和Chengdu)上生成軌跡數(shù)據(jù)集,觀察PathPrediction算法的預(yù)測(cè)時(shí)間,結(jié)果如圖3所示.可以發(fā)現(xiàn),不同電子地圖上,隨著生成軌跡數(shù)量的增加,PathPrediction算法的運(yùn)行時(shí)間均近似呈線性增長(zhǎng),證明了算法的可伸縮性.

圖3 PathPrediction算法在不同數(shù)據(jù)集下預(yù)測(cè)時(shí)間比較Fig.3 Prediction time of PathPrediction algorithm under different datasets

為了進(jìn)一步驗(yàn)證PathPrediction的時(shí)間性能,隨著移動(dòng)對(duì)象數(shù)量增加,觀察算法1～3的運(yùn)行時(shí)間,實(shí)驗(yàn)數(shù)據(jù)集為Chengdu地圖生成的軌跡數(shù)據(jù)集和GeoLife真實(shí)軌跡數(shù)據(jù)集,結(jié)果如圖4和圖5所示.

圖4 Chengdu數(shù)據(jù)集下不同算法預(yù)測(cè)時(shí)間比較Fig.4 Prediction time comparison of different algorithms under Chengdu datasets

通過圖4和圖5可以發(fā)現(xiàn),PathPrediction算法在所有情況下預(yù)測(cè)時(shí)間均小于PutMode算法,略高于Naive算法.原因在于Naive算法沒有應(yīng)用軌跡熱點(diǎn)區(qū)域挖掘算法,因此預(yù)測(cè)時(shí)間要小于PathPrediction算法.而PutMode算法需要訓(xùn)練時(shí)間連續(xù)貝葉斯網(wǎng)絡(luò)并構(gòu)建轉(zhuǎn)換強(qiáng)度矩陣,該過程非常耗時(shí),時(shí)間遠(yuǎn)遠(yuǎn)高于本文提出的頻繁軌跡模式挖掘算法FTP-mining.此外,可以發(fā)現(xiàn)Naive和PathPrediction算法運(yùn)行時(shí)間接近,說明本文提出的軌跡熱點(diǎn)區(qū)域挖掘算法時(shí)間隨著軌跡數(shù)量的增加不會(huì)發(fā)生巨大變化.

圖5 GeoLife數(shù)據(jù)集下不同算法預(yù)測(cè)時(shí)間比較Fig.5 Prediction time comparison of different algorithms under GeoLife datasets

4.2 基于高斯混合回歸的軌跡預(yù)測(cè)算法性能分析

為了驗(yàn)證本文提出的面向多模式移動(dòng)對(duì)象軌跡預(yù)測(cè)算法的性能,設(shè)計(jì)實(shí)現(xiàn)了基于高斯混合回歸的軌跡預(yù)測(cè)算法GMRTP,基于卡爾曼濾波的預(yù)測(cè)算法Kalman,基于隱馬爾科夫模型(Hidden Markov model,HMM)的軌跡預(yù)測(cè)算法HMTP[9].其中,Kalman filter[27]是一種應(yīng)用普遍的回歸預(yù)測(cè)方法,與本文提出的預(yù)測(cè)算法的可比性較高.HMTP算法基于HMM模型提取隱狀態(tài)和觀察狀態(tài),預(yù)測(cè)效果較好,通過與其比較,可以充分證明本文算法的性能優(yōu)勢(shì).

本節(jié)比較上述三種算法的準(zhǔn)確性和時(shí)間性能.實(shí)驗(yàn)數(shù)據(jù)來源于MIT停車場(chǎng)行駛車輛數(shù)據(jù)1http://www.ee.cuhk.edu.hk/xgwang/MITtrajsingle.html,收集了40453條真實(shí)軌跡.

4.2.1 高斯過程分量的選取

GMRTP算法中高斯過程分量個(gè)數(shù)M的選取很重要,如果選擇的過程分量過少,算法不能充分地對(duì)數(shù)據(jù)建模,進(jìn)而對(duì)測(cè)試軌跡進(jìn)行準(zhǔn)確的預(yù)測(cè);選擇的過程分量太多,則會(huì)增加軌跡預(yù)測(cè)時(shí)間代價(jià).本節(jié)實(shí)驗(yàn)觀察在不同高斯過程分量個(gè)數(shù)下,不同軌跡輸入長(zhǎng)度(即已知軌跡點(diǎn)個(gè)數(shù))對(duì)預(yù)測(cè)誤差的影響.

定義4(預(yù)測(cè)誤差).軌跡預(yù)測(cè)是將測(cè)試軌跡數(shù)據(jù)集輸入預(yù)測(cè)模型得到預(yù)測(cè)輸出軌跡,其中輸入測(cè)試軌跡為部分軌跡點(diǎn)的集合,采用均方根誤差(Root mean squared error,RMSE)計(jì)算預(yù)測(cè)軌跡點(diǎn)與實(shí)際軌跡點(diǎn)的誤差.

其中,(xi,yi)表示真實(shí)位置,表示預(yù)測(cè)位置,k為預(yù)測(cè)軌跡點(diǎn)的數(shù)量.

實(shí)驗(yàn)中每條觀測(cè)軌跡由60個(gè)軌跡點(diǎn)構(gòu)成,已知輸入軌跡點(diǎn)長(zhǎng)度分別取10,30,50,對(duì)應(yīng)預(yù)測(cè)的未來軌跡點(diǎn)數(shù)目分別是50,30,10,實(shí)驗(yàn)結(jié)果如圖6所示.

圖6 不同高斯過程分量下軌跡預(yù)測(cè)誤差比較Fig.6 Prediction error comparison with distinct Gaussian regression components

從圖6可以看出:1)在不同高斯過程分量下,當(dāng)觀測(cè)的歷史軌跡輸入點(diǎn)個(gè)數(shù)越多時(shí)(例如observable length=50),算法預(yù)測(cè)誤差越低.因?yàn)轭A(yù)測(cè)模型有了更多的歷史軌跡數(shù)據(jù)點(diǎn)信息,包含更多的運(yùn)動(dòng)模式,預(yù)測(cè)誤差降低.2)GP混合分量個(gè)數(shù)從1增加到5時(shí),其預(yù)測(cè)誤差變化較大.當(dāng)高斯過程分量達(dá)到5時(shí),預(yù)測(cè)誤差收斂.值得注意的是,不同軌跡數(shù)據(jù)集其運(yùn)動(dòng)模式個(gè)數(shù)不同,因此需要通過實(shí)驗(yàn)探尋最佳的高斯過程分量個(gè)數(shù).本節(jié)后面實(shí)驗(yàn)內(nèi)容中GMRTP中高斯過程分量個(gè)數(shù)均設(shè)置為5.

4.2.2 預(yù)測(cè)準(zhǔn)確性分析

本節(jié)觀察三種預(yù)測(cè)算法在訓(xùn)練軌跡數(shù)量為39000條、不同測(cè)試集數(shù)據(jù)規(guī)模為100～1000條軌跡下的預(yù)測(cè)準(zhǔn)確性.用預(yù)測(cè)命中率評(píng)價(jià)算法的準(zhǔn)確性,用預(yù)測(cè)誤差(RMSE)評(píng)價(jià)算法的預(yù)測(cè)精度,實(shí)驗(yàn)結(jié)果取每種測(cè)試集下所有軌跡預(yù)測(cè)結(jié)果的平均值,如圖7和圖8所示.

從圖7可以看出,相比于其他兩種算法,隨著測(cè)試軌跡數(shù)量的增加,GMRTP預(yù)測(cè)誤差最小,一直保持在40m上下波動(dòng),相對(duì)較長(zhǎng)的真實(shí)軌跡,預(yù)測(cè)精度較高且比較穩(wěn)定.分析實(shí)驗(yàn)結(jié)果發(fā)現(xiàn),HMTP預(yù)測(cè)的平均誤差比GMRTP平均高出5.5m,GMRTP相比Kalman算法,預(yù)測(cè)誤差平均減少18.6m.原因在于HMTP和Kalman軌跡預(yù)測(cè)算法對(duì)于處理較為簡(jiǎn)單運(yùn)動(dòng)模式的軌跡預(yù)測(cè)精度較好,而實(shí)驗(yàn)中采用的數(shù)據(jù)集中軌跡模式較為復(fù)雜且種類繁多,因此預(yù)測(cè)誤差最大.而基于GMR的模型通用性較好,可以針對(duì)不同的多模式軌跡利用高斯過程回歸預(yù)測(cè).

圖7 不同算法預(yù)測(cè)誤差比較Fig.7 Prediction bias comparison of different algorithms

圖8 不同算法預(yù)測(cè)準(zhǔn)確率比較Fig.8 Prediction accuracy comparison of different algorithms

從圖8可以看出,相比HMTP和Kalman算法,GMRTP算法的預(yù)測(cè)準(zhǔn)確率平均提高9.9%和21.2%,且GMRTP比較穩(wěn)定,準(zhǔn)確率維持在90%上下波動(dòng).

4.2.3 預(yù)測(cè)時(shí)間性能分析

本節(jié)實(shí)驗(yàn)觀察上述三種算法隨著移動(dòng)對(duì)象數(shù)量增加的預(yù)測(cè)時(shí)間代價(jià),結(jié)果如圖9所示.

從圖9可以看出,GMRTP的預(yù)測(cè)時(shí)間最少,相比HMTP和Kalman算法,平均減少49.3%和11.3%.原因在于Kalman算法對(duì)每條軌跡中下一個(gè)位置預(yù)測(cè)都要將前一個(gè)位置信息代入回歸分析,當(dāng)預(yù)測(cè)的軌跡數(shù)量增加時(shí),預(yù)測(cè)時(shí)間近似呈線性增長(zhǎng).而GMRTP預(yù)測(cè)時(shí)利用高斯過程刻畫的軌跡僅需一次性預(yù)測(cè)即可,因此當(dāng)預(yù)測(cè)軌跡數(shù)量增加時(shí),只要沒有增加較多的軌跡運(yùn)動(dòng)模式,預(yù)測(cè)時(shí)間并不會(huì)產(chǎn)生較大的增加和波動(dòng).而HMTP算法預(yù)測(cè)最為耗時(shí),因?yàn)槠湓谟?xùn)練模型時(shí)需對(duì)軌跡進(jìn)行分段處理,并利用HMM模型提取隱狀態(tài)和觀察狀態(tài),代價(jià)較高.

圖9 不同算法預(yù)測(cè)時(shí)間性能比較Fig.9 Prediction time comparison among different algorithms

4.2.4 單一運(yùn)動(dòng)模式軌跡預(yù)測(cè)準(zhǔn)確性對(duì)比

為了進(jìn)一步證明基于高斯過程回歸的軌跡預(yù)測(cè)算法GMRTP的通用性,本節(jié)比較在單一運(yùn)動(dòng)模式下,GMRTP和PathPrediction的預(yù)測(cè)準(zhǔn)確性,實(shí)驗(yàn)采用GeoLife數(shù)據(jù)集,結(jié)果如圖10所示.其中,橫軸表示軌跡的數(shù)量,縱軸表示預(yù)測(cè)準(zhǔn)確性.

圖10 單一運(yùn)動(dòng)模式軌跡預(yù)測(cè)準(zhǔn)確率比較Fig.10 Prediction accuracy comparison beyond single-motion-pattern trajectories

從圖10可以看出,GMRTP算法對(duì)具有單一運(yùn)動(dòng)模式的軌跡進(jìn)行預(yù)測(cè)時(shí)仍然具有很高的準(zhǔn)確性,當(dāng)移動(dòng)對(duì)象數(shù)量大于2000時(shí),預(yù)測(cè)準(zhǔn)確率在90%以上;且隨著移動(dòng)對(duì)象數(shù)量增加,GMRTP均優(yōu)于本文提出的基于頻繁模式樹的單一模式軌跡預(yù)測(cè)算法PathPrediction.原因在于GMRTP對(duì)軌跡數(shù)據(jù)利用概率密度函數(shù)建模,依據(jù)符合正態(tài)分布數(shù)據(jù)的條件分布得到回歸函數(shù)完成回歸預(yù)測(cè),能夠準(zhǔn)確地反應(yīng)移動(dòng)對(duì)象真實(shí)運(yùn)動(dòng)行為.

5 總結(jié)與展望

多模式移動(dòng)對(duì)象不確定性軌跡預(yù)測(cè)是移動(dòng)對(duì)象數(shù)據(jù)庫(kù)領(lǐng)域新提出的充滿挑戰(zhàn)性的研究課題,針對(duì)當(dāng)前部分軌跡預(yù)測(cè)算法精度不高,復(fù)雜多模式軌跡預(yù)測(cè)準(zhǔn)確性不高、預(yù)測(cè)實(shí)時(shí)性不能保證、預(yù)測(cè)軌跡長(zhǎng)度較短的不足,本文提出一種基于軌跡頻繁模式樹的軌跡預(yù)測(cè)方法,充分考慮真實(shí)路網(wǎng)中的軌跡運(yùn)動(dòng)規(guī)則,預(yù)測(cè)結(jié)果準(zhǔn)確性較高.為了對(duì)復(fù)雜多模式移動(dòng)對(duì)象位置進(jìn)行預(yù)測(cè),提出了基于高斯過程回歸的多模式軌跡預(yù)測(cè)模型,算法運(yùn)行過程中無需設(shè)置大量參數(shù),可以通過數(shù)據(jù)自身利用概率統(tǒng)計(jì)分布獲得各種運(yùn)動(dòng)模式下的位置信息.

未來工作包括:1)對(duì)頻繁模式樹FTP-tree挖掘頻繁項(xiàng)集進(jìn)一步優(yōu)化,提高算法的挖掘效率;2)與國(guó)內(nèi)交通部門合作將所提模型應(yīng)用于卡口攝像頭采集到的交通數(shù)據(jù),輔助跟蹤和定位機(jī)動(dòng)車輛和行人(主要針對(duì)未裝備GPS定位系統(tǒng)的交通工具);3)為了保證預(yù)測(cè)的準(zhǔn)確性,充分考慮影響對(duì)象運(yùn)動(dòng)行為的主客觀因素.

References

1 Meng X F,Ding Z M,Xu J J.Moving Objects Management:Models,Techniques and Applications.Berlin:Springer-Verlag,2014.117?131

2 Hu W M,Xiao X J,Fu Z Y,Xie D,Tan T N,Maybank S.A system for learning statistical motion patterns.IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(9):1450?1464

3 Parker A,Subrahmanian V S,Grant J.Fast and accurate prediction of the destination of moving objects.In:Proceedings of the 3rd International Conference on Scalable Uncertainty Management.Berlin,Germany:Springer,2009.180?192

4 Song C M,Qu Z H,Blumm N,Barabási A L.Limits of predictability in human mobility.Science,2010,327(5968):1018?1021

5 Centola D.The spread of behavior in an online social network experiment.Science,2010,329(5996):1194?1197

6 Jeung H,Yiu M L,Zhou X F,Jensen C S.Path prediction and predictive range querying in road network databases.The VLDB Journal,2010,19(4):585?602

7 Zhou J B,Tung A K H,Wu W,Ng W S.A “semi-lazy”approach to probabilistic path prediction in dynamic environments.In:Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM,2013.748?756

8 Pan T L,Sumalee A,Zhong R X,Indra-payoong N.Shortterm traffic state prediction based on temporal-spatial correlation.IEEE Transactions on Intelligent Transportation Systems,2013,14(3):1242?1254

9 Qiao S J,Shen D Y,Wang X T,Han N,Zhu W.A selfadaptive parameter selection trajectory prediction approach via hidden Markov models.IEEE Transactions on Intelligent Transportation Systems,2015,16(1):284?296

10 Qiao Shao-Jie,Li Tian-Rui,Han Nan,Gao Yun-Jun,Yuan Chang-An,Wang Xiao-Teng,Tang Chang-Jie.Self-adaptive trajectory prediction model for moving objects in big data environment.Journal of Software,2015,26(11):2869?2883(喬少杰,李天瑞,韓楠,高云君,元昌安,王曉騰,唐常杰.大數(shù)據(jù)環(huán)境下移動(dòng)對(duì)象自適應(yīng)軌跡預(yù)測(cè)模型.軟件學(xué)報(bào),2015,26(11):2869?2883)

11 Ding Z M,Yang B,Güting R H,Li Y G.Network-matched trajectory-based moving-object database:models and applications.IEEE Transactions on Intelligent Transportation Systems,2015,16(4):1918?1928

12 Xu J J,Gao Y J,Liu C F,Zhao L,Ding Z M.Efficient route search on hierarchical dynamic road networks.Distributed and Parallel Databases,2015,33(2):227?252

13 Dai J,Yang B,Guo C J,Ding Z M.Personalized route recommendation using big trajectory data.In:Proceedings of the 31st IEEE International Conference on Data Engineering.Seoul,South Korea:IEEE Computer Society,2015.543?554

14 Tripathy S,Howard C J.Multiple trajectory tracking.Scholarpedia,2012,7(4):Article No.11287

15 Xu J Q,Güting R H.A generic data model for moving objects.Geoinformatica,2013,17(1):125?172

16 Huang Yu-Long,Zhang Yong-Gang,Li Ning,Zhao Lin.An improved Gaussian approximate filtering method.Acta Automatica Sinica,2016,42(3):385?401(黃玉龍,張勇剛,李寧,趙琳.一種改進(jìn)的高斯近似濾波方法.自動(dòng)化學(xué)報(bào),2016,42(3):385?401)

17 Chen Cheng,He Yu-Qing,Bu Chun-Guang,Han Jian-Da.Feasible trajectory generation for autonomous vehicles based on quartic Bézier curve.Acta Automatica Sinica,2015,41(3):486?496(陳成,何玉慶,卜春光,韓建達(dá).基于四階貝塞爾曲線的無人車可行軌跡規(guī)劃.自動(dòng)化學(xué)報(bào),2015,41(3):486?496)

18 Monfort M,Liu A Q,Ziebart B D.Intent prediction and trajectory forecasting via predictive inverse linear-quadratic regulation.In:Proceedings of the 29th AAAI Conference on Arti ficial Intelligence.Austin,Texas,USA:AAAI,2015.3672?3678

19 Qiao S J,Han N,Zhu W,Gutierrez L A.TraPlan:an effective three-in-one trajectory-prediction model in transportation networks.IEEE Transactions on Intelligent Transportation Systems,2015,16(3):1188?1198

20 Han J W,Pei J,Yin Y W,Mao R Y.Mining frequent patterns without candidate generation:a frequent-pattern tree approach.Data Mining and Knowledge Discovery,2004,8(1):53?87

21 Rasmussen C E,Williams C K I.Gaussian Processes for Machine Learning(Adaptive Computation and Machine Learning).Cambridge,USA:The MIT Press,2005.12?22

22 Yu Jian-Bo,Lu Xiao-Lei,Zong Wei-Zhou.Wafer defect detection and recognition based on local and nonlocal linear discriminant analysis and dynamic ensemble of Gaussian mixture models.Acta Automatica Sinica,2016,42(1):47?59(余建波,盧笑蕾,宗衛(wèi)周.基于局部與非局部線性判別分析和高斯混合模型動(dòng)態(tài)集成的晶圓表面缺陷探測(cè)與識(shí)別.自動(dòng)化學(xué)報(bào),2016,42(1):47?59)

23 Dellaert F.The Expectation Maximization Algorithm,Technical Report GIT-GVU-02-20,Colleage of Computing,Georgia Institute of Technology,USA,2002.

24 Qiao S J,Tang C J,Jin H D,Long T,Dai S C,Ku Y C,Chau M.PutMode:prediction of uncertain trajectories in moving objects databases.Applied Intelligence,2010,33(3):370?386

25 BrinkhoffT.A framework for generating network-based moving objects.GeoInformatica,2002,6(2):153?180

26 Zheng Y,Xie X,Ma W Y.Geolife:a collaborative social networking service among user,location and trajectory.IEEE Data(base)Engineering Bulletin,2010,33(2):32?40

27 Deng Hu-Bin,Zhang Lei,Wu Ying,Zhou Jie,Liu Feng.Research on track estimation based on Kalman filtering algorithm.Transducer and Microsystem Technologies,2012,31(5):4?7(鄧胡濱,張磊,吳穎,周潔,劉楓.基于卡爾曼濾波算法的軌跡估計(jì)研究.傳感器與微系統(tǒng),2012,31(5):4?7)