基于區(qū)域分布概率密度估計(jì)的軌跡分類方法

, ,

(盲信號(hào)處理重點(diǎn)實(shí)驗(yàn)室,成都 610041)

0 概述

隨著科技的進(jìn)步,定位手段越來越多樣,人們可以通過多種不同的途徑獲取軌跡數(shù)據(jù),基于軌跡數(shù)據(jù)的目標(biāo)屬性識(shí)別也逐漸成為目標(biāo)分析的重要手段。例如,可以基于運(yùn)動(dòng)軌跡識(shí)別出行交通方式[1]、基于視頻監(jiān)控中提取的運(yùn)動(dòng)軌跡識(shí)別被監(jiān)控對(duì)象的行為模式[2]等。利用軌跡數(shù)據(jù)進(jìn)行目標(biāo)分類具有潛在信息量豐富、無需額外添加傳感器、不易偽裝篡改等優(yōu)點(diǎn)。

在實(shí)際應(yīng)用中,需根據(jù)軌跡數(shù)據(jù)的特點(diǎn)選擇相應(yīng)的分類算法。對(duì)于通過GPS等手段獲取的位置數(shù)據(jù),其定位誤差小、采樣率高,一般通過提取軌跡的局部差分顯著特征來對(duì)其進(jìn)行分類。例如,文獻(xiàn)[1]針對(duì)手持設(shè)備采集的市區(qū)移動(dòng)軌跡,計(jì)算其速度、加速度、轉(zhuǎn)向率、停止率等顯著特征,實(shí)現(xiàn)出行交通模式的識(shí)別;文獻(xiàn)[3- 4]針對(duì)Auslan手語數(shù)據(jù)提取軌跡的曲率、撓率等旋轉(zhuǎn)不變量,實(shí)現(xiàn)手語詞匯的識(shí)別;文獻(xiàn)[5]考慮軌跡數(shù)據(jù)的尺度差異,提出利用曲率樹結(jié)構(gòu)來對(duì)手語軌跡數(shù)據(jù)進(jìn)行識(shí)別。

盡管上述方法具有極強(qiáng)的實(shí)用價(jià)值,但并不適用于一些具體的應(yīng)用場(chǎng)景。如在Starkey項(xiàng)目中,研究者通過采集北美有蹄動(dòng)物的遷徙數(shù)據(jù)來探索動(dòng)物習(xí)性的變化[6],該數(shù)據(jù)由無線電遙測(cè)手段獲取,定位誤差和采樣間隔較大,提取速度、曲率等元數(shù)據(jù)特征時(shí)會(huì)引入較大誤差,導(dǎo)致分類結(jié)果極不可靠。此外,通過雷達(dá)掃描、Wifi室內(nèi)定位[7]、蜂窩定位、Flicker照片位置數(shù)據(jù)[8]等手段獲取的軌跡數(shù)據(jù)都具有類似的統(tǒng)計(jì)特點(diǎn)。對(duì)于這類數(shù)據(jù),若不同類別的軌跡數(shù)據(jù)在空間上嚴(yán)重重疊,則一般認(rèn)為其可分性不強(qiáng);反之,若軌跡在空間中存在一定程度的分離現(xiàn)象,則可充分挖掘其位置相關(guān)特征。

文獻(xiàn)[9-10]對(duì)二維軌跡段所在的二維空間進(jìn)行劃分,以最小描述長(zhǎng)度(Minimum Description Length,MDL)為劃分粒度的選取準(zhǔn)則,提取僅包含一類軌跡的矩形“同質(zhì)區(qū)域”作為特征。相較于軌跡模式特征[1]方法,該方法不僅提高了軌跡的分類準(zhǔn)確率,還提升了分類器的訓(xùn)練效率。但是,該方法假設(shè)顯著區(qū)域呈近似矩形狀分布,這一假設(shè)在實(shí)際中并不一定適用。此外,為減小最佳劃分的搜索復(fù)雜度,該方法采用向x、y軸分別投影的方式交替選取各坐標(biāo)軸的劃分點(diǎn),這一策略在軌跡簇分布區(qū)域的劃分時(shí)具有局限性。為解決該局限性,文獻(xiàn)[11]提出采用空間區(qū)域合并的策略提取同質(zhì)區(qū)域,然而該方法并未消除矩形區(qū)域形狀的限制,仍有較強(qiáng)的局限性。此外,文獻(xiàn)[12-13]提出利用高斯混合模型(Gaussian Mixture Model,GMM)來擬合軌跡段在空間中的分布,該方法消除了區(qū)域劃分法的缺陷,且將應(yīng)用范圍擴(kuò)展至三維甚至更高維度的軌跡數(shù)據(jù)分類問題。但是,GMM方法的缺陷在于其引入了高斯分量個(gè)數(shù)K,不同的K值會(huì)影響分類結(jié)果:較小的K值不足以描述復(fù)雜的軌跡區(qū)域分布,較大的K值時(shí)可能因?yàn)槟Ｐ瓦^于復(fù)雜而導(dǎo)致訓(xùn)練失敗。

針對(duì)上述問題,本文提出基于核函數(shù)密度估計(jì)[14-17]的方法獲取軌跡片段在空間中的概率分布,并結(jié)合最大似然準(zhǔn)則,實(shí)現(xiàn)軌跡數(shù)據(jù)的可靠分類。該方法不對(duì)軌跡的分布區(qū)域形狀做任何假設(shè),且無需引入額外的參變量。

1 基于核密度估計(jì)的軌跡分類方法

1.1 算法流程

基于核密度估計(jì)的軌跡分類方法流程如圖1所示。

圖1 基于核密度估計(jì)的軌跡分類方法流程

該算法的具體流程如下:

1)基于DOTS算法[18]將每條軌跡劃分為軌跡段。

2)基于每條軌跡段的中心點(diǎn)估計(jì)軌跡片段在二維空間中的概率密度分布。

3)借助已知的概率密度計(jì)算軌跡屬于任一類別的似然概率,最后依據(jù)最大似然準(zhǔn)則進(jìn)行分類。

1.2 基于最小誤差準(zhǔn)則的軌跡分段

軌跡數(shù)據(jù)是典型的時(shí)間序列數(shù)據(jù),具有不定長(zhǎng)的數(shù)據(jù)特點(diǎn),各軌跡點(diǎn)的位置分別包含經(jīng)緯度和時(shí)間信息,如式(1)所示。

T={pi=(loni,lati,ti)|i=1,2,…,N}

(1)

其中,lon表示經(jīng)度,lat表示緯度,t表示時(shí)間。

通過核密度估計(jì)的方式得出各類軌跡在空間中的分布情況時(shí),直接以軌跡T為元素進(jìn)行密度估計(jì)顯然不合理,本文借鑒文獻(xiàn)[10]的思路,將每條軌跡切分成小片段,以這些片段為基礎(chǔ)粒度,估計(jì)軌跡的區(qū)域分布情況。

文獻(xiàn)[18]提出一種基于最優(yōu)準(zhǔn)則的軌跡數(shù)據(jù)分段方法,以增量的方式構(gòu)建無回路有向圖數(shù)據(jù)結(jié)構(gòu),通過在該圖中動(dòng)態(tài)搜索最短路徑來獲得原始軌跡的最優(yōu)分段結(jié)果,如圖2所示。該分段方法具有同等分段粒度下誤差最小的優(yōu)點(diǎn)。

圖2 軌跡分段示意圖

分段后,每條軌跡可用一系列軌跡段構(gòu)成的有序集合表示,即:

T={segi|i=1,2,…,M}

(2)

在下文中,用xi表示軌跡段segi的中點(diǎn)坐標(biāo)。

1.3 自適應(yīng)核密度估計(jì)

如前文所述,區(qū)域劃分法[10]額外引入了軌跡片段呈矩形狀聚類成簇的約束,與許多實(shí)際應(yīng)用場(chǎng)景不符,限制了其分類準(zhǔn)確率的提升。本文提出利用自適應(yīng)核密度估計(jì)的方法來擬合各類別軌跡片段在二維空間中的分布情況,其描述能力比矩形框更強(qiáng)。

核密度估計(jì)的計(jì)算方法如式(3)所示。

(3)

根據(jù)需求的不同,核函數(shù)的類型有均值核、三角核、雙權(quán)重核、Epanechnikov核、Gaussian核等。由于Gaussian函數(shù)具有諸多良好的數(shù)學(xué)性質(zhì),因此其應(yīng)用較廣[14-15]。

式(3)中存在被稱為帶寬的可調(diào)參數(shù)h,給定任意一種核函數(shù),結(jié)合h可以構(gòu)成一系列核函數(shù)族,即:

(4)

不難證明,對(duì)任意h>0,Kh均滿足式(4)所示的約束條件,其為合法的核函數(shù)。與直方圖統(tǒng)計(jì)類似,核密度估計(jì)的結(jié)果也受帶寬取值影響,如圖3所示。

圖3 帶寬h對(duì)一維核密度估計(jì)結(jié)果的影響

對(duì)于給定的參考概率分布(圖中“Ref”曲線)隨機(jī)生成數(shù)據(jù)樣本,然后分別以帶寬h取值0.20、0.57、5.00來估計(jì)樣本的概率密度,由圖3可以看出,得出的結(jié)果存在明顯差異。一般來說,h取值越小,密度估計(jì)的偏差就更接近0。若數(shù)據(jù)樣本無限充足,一般認(rèn)為h取值越小越好,但實(shí)際應(yīng)用中數(shù)據(jù)樣本有限,需要在概率密度的偏差和分布的復(fù)雜程度之間作出平衡。h取值過小會(huì)導(dǎo)致估計(jì)結(jié)果包含太多峰谷,推廣性不佳,統(tǒng)計(jì)上稱之為欠平滑;反之,h取值過大,則不足以發(fā)掘數(shù)據(jù)樣本中的局部分布差異,稱之為過平滑。

一般采用式(5)所示的指標(biāo)來衡量帶寬取值的優(yōu)劣。

(5)

MISE與p(x)和h間的函數(shù)關(guān)系復(fù)雜,不便求極值。在概率分布p(x)二階可導(dǎo)的假設(shè)下,可用式(6)所示的漸進(jìn)式誤差度量替代MISE,兩者僅相差無窮小項(xiàng)o(1/Nh+h4)[14]。

(6)

對(duì)AMISE求導(dǎo)得式(7)所示的極值點(diǎn),即為最佳帶寬。

(7)

(8)

盡管采用插入帶寬選擇器[15]、交叉驗(yàn)證帶寬選擇器等求解得到的最優(yōu)帶寬更準(zhǔn)確,但本文第3節(jié)的實(shí)驗(yàn)表明,雖然密度估計(jì)的準(zhǔn)確性與帶寬密切相關(guān),但基于密度估計(jì)軌跡分類方法的正確率卻對(duì)帶寬不敏感,只要選擇相對(duì)較合理的h值即可,不必過于精確?；谏鲜鲇懻?算法1給出了核密度估計(jì)部分參考實(shí)現(xiàn),其中P為查表形式的概率密度函數(shù),IDX(P)表示函數(shù)表的下標(biāo)集。

算法1自適應(yīng)核密度估計(jì)

輸入屬于同一類別c的軌跡段集合X={x1,x2,…,xn}

輸出概率密度函數(shù)P

3.P=0

4.FOR xi∈X DO

5. FOR x0IN IDX(P) DO

6. P(x0)=P(x0)+Kh(x0-xi)/n

7. END FOR

8.END FOR

9.RETURN P

以Starkey動(dòng)物遷徙軌跡數(shù)據(jù)[6]為例,軌跡段在二維空間的概率密度估計(jì)如圖4所示,其中圖4(a)、圖4(b)、圖4(c)分別表示牛、鹿、麋鹿3類動(dòng)物的密度分布,色階越暖表示概率密度越大,反之,則概率密度越小。

圖4 Starkey數(shù)據(jù)集的區(qū)域分布密度估計(jì)結(jié)果

根據(jù)概率密度的比值,可以將3類軌跡數(shù)據(jù)的顯著分布區(qū)域按式(9)進(jìn)行劃分,如圖4(d)所示。式(9)僅以類別“?！睘槔f明,其他類別的數(shù)據(jù)可以類比定義。

lx=cattle, i.f.f.

pcattle(x)>αpdeer(x),pcattle(x)>αpelk(x)

α>1

(9)

從圖4(d)可以看出,基于密度估計(jì)的類別劃分方法未對(duì)數(shù)據(jù)的分布形狀做任何強(qiáng)假設(shè),分界面更加靈活,分類效果較好。

1.4 基于最大似然度的軌跡分類

盡管可以利用式(9)所示的顯著區(qū)域進(jìn)行軌跡分類,但這一方法引入了參數(shù)α,增加了使用過程中的算法調(diào)參步驟。針對(duì)這一問題,本文在軌跡段獨(dú)立同分布的假設(shè)下,計(jì)算軌跡T屬于類別c的似然概率,以似然概率作為分類依據(jù)。

(10)

獨(dú)立同分布假設(shè)相較于Markov等鏈?zhǔn)侥Ｐ蚚19]的優(yōu)點(diǎn)在于,其概率模型更簡(jiǎn)單,對(duì)數(shù)據(jù)樣本量的要求更低,應(yīng)用場(chǎng)景更廣泛。

考慮到式(10)連乘過程可能引起浮點(diǎn)數(shù)數(shù)值溢出問題,可采用式(11)所示的對(duì)數(shù)累加形式計(jì)算軌跡的對(duì)數(shù)似然概率,其與式(10)等效。

(11)

(12)

其中,ε>0為一較小的正實(shí)數(shù),對(duì)概率密度提供零值保護(hù)。

仍考慮上述軌跡段segi,參照式(12),則似然概率偏差為ΔlogaP′(lT=c|T)≈logaP′(ε),segi定位偏差對(duì)似然概率的影響大大減小。另一方面,若segi為定位準(zhǔn)確的片段,則參數(shù)ε引入的誤差如式(13)所示。

(13)

通過第3節(jié)的真實(shí)數(shù)據(jù)實(shí)驗(yàn),發(fā)現(xiàn)這一微小改進(jìn)能夠令學(xué)習(xí)器的分類正確率提升5%左右,效果顯著。

最后,以最大似然概率為判別準(zhǔn)則,計(jì)算軌跡的類別標(biāo)簽,如式(14)所示。

(14)

上述工作流程可歸納為如算法2所示的偽代碼。其中,seg(T)表示對(duì)軌跡T按照DOTS算法進(jìn)行劃分得到的軌跡段集合,函數(shù)NN(A,b)用于在集合A中尋找點(diǎn)b的最近鄰。

算法2最大似然判別

輸入類別集合C={c1,c2,…,cm},各類別軌跡段空間分布概率估計(jì)Pc,待分類軌跡T

1.X=seg(T)

2.FOR c∈C DO

3. FOR xi∈X DO

4. x=NN(IDX(Pc),xi)

5. Prc(T)=Prc(T)+loga[Pc(x)+ε]

6. END FOR

7.END FOR

8.RETURN argmaxcPrc(T)

2 算法分析

2.1 時(shí)間復(fù)雜度

2.2 適用范圍

綜合前文的原理分析,將本文軌跡分類方法的適用范圍匯總?cè)缦?

1)軌跡數(shù)據(jù)的類別標(biāo)簽與區(qū)域分布有一定相關(guān)性。

2)軌跡數(shù)據(jù)受采集手段限制,采樣率較低、定位精度較差,不利于采用速度、加速度、運(yùn)動(dòng)模式等特征進(jìn)行分類。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文以Starkey動(dòng)物遷徙數(shù)據(jù)[6]和海洋船舶AIS數(shù)據(jù)[20]為例,測(cè)試各分類方法在軌跡數(shù)據(jù)分類方面的性能。2個(gè)數(shù)據(jù)集的統(tǒng)計(jì)特征如表1所示,其中Starkey軌跡按照動(dòng)物物種分為牛、鹿和麋鹿,船舶軌跡數(shù)據(jù)按照目標(biāo)所屬國(guó)家分為挪威、英國(guó)、法國(guó)。

表1 實(shí)驗(yàn)數(shù)據(jù)

3.2 分類準(zhǔn)確率分析

為對(duì)比各算法的分類準(zhǔn)確率,采用5折交叉驗(yàn)證的方式,每次從各數(shù)據(jù)集中隨機(jī)抽取80%的軌跡進(jìn)行訓(xùn)練,剩余20%的軌跡用于測(cè)試。為保證實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)可信,每項(xiàng)實(shí)驗(yàn)均重復(fù)進(jìn)行50次。各算法的分類錯(cuò)誤率如表2所示。

表2 各軌跡分類算法錯(cuò)誤率比較 %

由表2可以看出,本文方法在2類數(shù)據(jù)集下的準(zhǔn)確率均高于對(duì)比方法[10-11,13]。值得注意的是,式(12)引入的零值保護(hù)措施顯著提升了分類性能,在Starkey數(shù)據(jù)集下準(zhǔn)確性提升4.7%,在AIS數(shù)據(jù)集下準(zhǔn)確性提升高達(dá)9.34%,其原理已在1.4節(jié)討論。另外,將本文的零值保護(hù)方法應(yīng)用于GMM模型,分類準(zhǔn)確率相比于區(qū)域劃分法[10]、合并法[11]也有明顯改進(jìn),但仍比本文方法低約5%。

圖5 分類錯(cuò)誤率與帶寬的關(guān)系

圖6 分類錯(cuò)誤率與網(wǎng)格規(guī)模的關(guān)系

3.3 分類效率分析

本文算法的另一個(gè)突出優(yōu)勢(shì)在于其訓(xùn)練時(shí)間較短。本文借助積分圖等數(shù)據(jù)結(jié)構(gòu)高效地實(shí)現(xiàn)了MDL區(qū)域劃分算法[10],在2項(xiàng)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),結(jié)果如表3所示。

表3 各軌跡分類算法訓(xùn)練效率比較 s

從表5可知,本文方法訓(xùn)練時(shí)間僅約為對(duì)比算法的10%。

實(shí)驗(yàn)還分析了訓(xùn)練時(shí)間與帶寬h和網(wǎng)格規(guī)模G的關(guān)系,結(jié)果如圖7、圖8所示。

圖7 訓(xùn)練時(shí)間與帶寬的關(guān)系

圖8 訓(xùn)練時(shí)間與網(wǎng)格規(guī)模的關(guān)系

從圖7、圖8可以看出,訓(xùn)練時(shí)間與h不相關(guān),而與G呈線性關(guān)系,這也證實(shí)了前文對(duì)復(fù)雜度的理論分析結(jié)果。

4 結(jié)束語

區(qū)域分布特征是軌跡數(shù)據(jù)分類的重要支撐,針對(duì)MDL區(qū)域劃分法、混合高斯模型等對(duì)數(shù)據(jù)分布先驗(yàn)假設(shè)過強(qiáng)的問題,本文提出一種不依賴數(shù)據(jù)模型的軌跡分類方法。首先利用核密度估計(jì)獲取各類別數(shù)據(jù)在空間中的概率密度分布,然后采用最大似然判決實(shí)現(xiàn)目標(biāo)分類。該方法對(duì)帶寬、網(wǎng)格規(guī)模等參數(shù)不敏感,訓(xùn)練時(shí)間較短,且分類準(zhǔn)確率較高。下一步將在區(qū)域特征與運(yùn)動(dòng)模式、加速度等其他特征的融合利用方面開展研究。

[1] ZHENG Y,LIU L,WANG L,et al.Learning trans-portation mode from raw GPS data for geographic applications on the Web[C]//Proceedings of the 17th International Conference on World Wide Web.New York,USA:ACM Press,2008:247-256.

[2] PUSIOL G,BREMOND F,THONNAT M.Trajectory based activity discovery[C]//Proceedings of the 7th IEEE International Conference on Advanced Video and Signal Based Surveillance.Washington D.C.,USA:IEEE Press,2010:270-277.

[3] KADOUS M W.Temporal classification:extending the classification paradigm to multivariate time series[D].New South Wales,Australia:University of New South Wales,2002.

[4] YANG Jianyu,LI Y F,WANG Keyi,et al.Mixed signature:an invariant descriptor for 3D motion trajectory perception and recognition[J].Mathematical Problems in Engineering,2012(3):488-516.

[5] NIERHOFF T,HIRCHE S.Trajectory classification in n dimensions using subspace projection[C]//Proceedings of 2012 IEEE International Conference on Intelligent Robots and Systems.Washington D.C.,USA:IEEE Press,2012:1318-1323.

[6] ROWLAND M M,COE P K,STUSSY R J,et al.The starkey habitat database for ungulate research:construction,documentation,and use[J].Forest Service General Technical Report,1998(5):103-112.

[7] WANG Yan,LIU Jian,CHEN Yingying,et al.E-eyes:device-free location-oriented activity identification using fine-grained WiFi signatures[C]//Proceedings of the 20th Annual International Conference on Mobile Computing and Networking.New York,USA:ACM Press,2014:617-628.

[8] SPYROU E,SOFIANOS I,MYLONAS P.Mining tourist routes from flickr photos[C]//Proceedings of the 10th International Workshop on Semantic and Social Media Adaptation and Personalization.Washington D.C.,USA:IEEE Press,2015:1-5.

[9] 李 然,林 和,李永禮.基于最小描述長(zhǎng)度的不完備數(shù)據(jù)處理[J].蘭州大學(xué)學(xué)報(bào)(自然科學(xué)版),2006,42(6):78-80.

[10] LEE J G,HAN J,LI X,et al.TraClass:trajectory classification using hierarchical region-based and trajectory-based clustering[J].Proceedings of the VLDB Endowment,2008,1(1):1081-1094.

[11] 李智翔,褚衍杰.基于地理區(qū)域聚類的航跡分類方法[J].電信技術(shù)研究,2014(1):12-18.

[12] 吳 奎,宋 彥,戴禮榮.基于CUDA的GMM模型快速訓(xùn)練方法[J].數(shù)據(jù)采集與處理,2012,27(1):85-90.

[13] BASHIR F,KHOKHAR A,SCHONFELD D.Automatic object trajectory-based motion recognition using Gaussian mixture models[C]//Proceedings of 2015 IEEE International Conference on Multimedia and Expo.Washington D.C.,USA:IEEE Press,2005:1532-1535.

[14] SILVERMAN B W.Density estimation for statistics and data analysis[M].London,UK:Chapman and Hall,1986.

[15] BOTEV Z I,GROTOWSKI J F,KROESE D P.Kernel density estimation via diffusion[J].Annals of Statistics,2010,38(5):2916-2957.

[16] 周 寧,薛向陽.基于核密度估計(jì)的圖像自動(dòng)標(biāo)注方法[J].計(jì)算機(jī)工程,2010,36(6):198-200.

[17] 吳俊琦,倪 宏,李 俊.基于核密度估計(jì)的可變碼率視頻流量預(yù)測(cè)算法[J].計(jì)算機(jī)工程,2012,38(24):262-265.

[18] CAO W,LI Y.DOTS:an online and near-optimal trajectory simplification algorithm[J].Journal of Systems and Software,2017,126(1):34-44.

[19] NASCIMENTO J C,FIGUEIREDO M,MARQUES J S.Trajectory classification using switched dynamical hidden markov models[J].IEEE Transactions on Image Processing,2010,19(5):1338-1348.

[20] ETIENNE L,DEVOGELE T,BOUJU A.Spatio-temporal trajectory analysis of mobile objects following the same itinerary[J].Advances in Geo-Spatial Information Science,2012,38(2):86-91.