, ,

(盲信號處理重點實驗室,成都 610041)

0 概述

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

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

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

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

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

1 基于核密度估計的軌跡分類方法

1.1 算法流程

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

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

該算法的具體流程如下:

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

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

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

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

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

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

(1)

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

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

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

圖2 軌跡分段示意圖

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

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

(2)

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

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

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

核密度估計的計算方法如式(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)

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

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

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

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

(5)

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

(6)

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

(7)

(8)

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

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

輸入屬于同一類別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動物遷徙軌跡數(shù)據(jù)[6]為例,軌跡段在二維空間的概率密度估計如圖4所示,其中圖4(a)、圖4(b)、圖4(c)分別表示牛、鹿、麋鹿3類動物的密度分布,色階越暖表示概率密度越大,反之,則概率密度越小。

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

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

lx=cattle, i.f.f.

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

α>1

(9)

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

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

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

(10)

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

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

(11)

(12)

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

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

(13)

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

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

(14)

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

算法2最大似然判別

輸入類別集合C={c1,c2,…,cm},各類別軌跡段空間分布概率估計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 時間復(fù)雜度

2.2 適用范圍

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

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

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

3 實驗結(jié)果與分析

3.1 實驗數(shù)據(jù)

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

表1 實驗數(shù)據(jù)

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

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

表2 各軌跡分類算法錯誤率比較 %

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

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

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

3.3 分類效率分析

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

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

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

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

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

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

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

4 結(jié)束語

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

[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] 李 然,林 和,李永禮.基于最小描述長度的不完備數(shù)據(jù)處理[J].蘭州大學(xué)學(xué)報(自然科學(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] 周 寧,薛向陽.基于核密度估計的圖像自動標(biāo)注方法[J].計算機工程,2010,36(6):198-200.

[17] 吳俊琦,倪 宏,李 俊.基于核密度估計的可變碼率視頻流量預(yù)測算法[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.