基于區域分布概率密度估計的軌跡分類方法

, ,

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

0 概述

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

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

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

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

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

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

1.1 算法流程

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

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

該算法的具體流程如下:

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

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

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

1.2 基于最小誤差準則的軌跡分段

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

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

(1)

其中,lon表示經度,lat表示緯度,t表示時間。

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

文獻[18]提出一種基于最優準則的軌跡數據分段方法,以增量的方式構建無回路有向圖數據結構,通過在該圖中動態搜索最短路徑來獲得原始軌跡的最優分段結果,如圖2所示。該分段方法具有同等分段粒度下誤差最小的優點。

圖2 軌跡分段示意圖

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

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

(2)

在下文中,用xi表示軌跡段segi的中點坐標。

1.3 自適應核密度估計

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

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

(3)

根據需求的不同,核函數的類型有均值核、三角核、雙權重核、Epanechnikov核、Gaussian核等。由于Gaussian函數具有諸多良好的數學性質,因此其應用較廣[14-15]。

式(3)中存在被稱為帶寬的可調參數h,給定任意一種核函數,結合h可以構成一系列核函數族,即:

(4)

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

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

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

一般采用式(5)所示的指標來衡量帶寬取值的優劣。

(5)

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

(6)

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

(7)

(8)

盡管采用插入帶寬選擇器[15]、交叉驗證帶寬選擇器等求解得到的最優帶寬更準確,但本文第3節的實驗表明,雖然密度估計的準確性與帶寬密切相關,但基于密度估計軌跡分類方法的正確率卻對帶寬不敏感,只要選擇相對較合理的h值即可,不必過于精確。基于上述討論,算法1給出了核密度估計部分參考實現,其中P為查表形式的概率密度函數,IDX(P)表示函數表的下標集。

算法1自適應核密度估計

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

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

圖4 Starkey數據集的區域分布密度估計結果

根據概率密度的比值,可以將3類軌跡數據的顯著分布區域按式(9)進行劃分,如圖4(d)所示。式(9)僅以類別“牛”為例說明,其他類別的數據可以類比定義。

lx=cattle, i.f.f.

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

α>1

(9)

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

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

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

(10)

獨立同分布假設相較于Markov等鏈式模型[19]的優點在于,其概率模型更簡單,對數據樣本量的要求更低,應用場景更廣泛。

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

(11)

(12)

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

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

(13)

通過第3節的真實數據實驗,發現這一微小改進能夠令學習器的分類正確率提升5%左右,效果顯著。

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

(14)

上述工作流程可歸納為如算法2所示的偽代碼。其中,seg(T)表示對軌跡T按照DOTS算法進行劃分得到的軌跡段集合,函數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 時間復雜度

2.2 適用范圍

綜合前文的原理分析,將本文軌跡分類方法的適用范圍匯總如下:

1)軌跡數據的類別標簽與區域分布有一定相關性。

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

3 實驗結果與分析

3.1 實驗數據

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

表1 實驗數據

3.2 分類準確率分析

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

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

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

圖5 分類錯誤率與帶寬的關系

圖6 分類錯誤率與網格規模的關系

3.3 分類效率分析

本文算法的另一個突出優勢在于其訓練時間較短。本文借助積分圖等數據結構高效地實現了MDL區域劃分算法[10],在2項數據集上進行實驗,結果如表3所示。

表3 各軌跡分類算法訓練效率比較 s

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

實驗還分析了訓練時間與帶寬h和網格規模G的關系,結果如圖7、圖8所示。

圖7 訓練時間與帶寬的關系

圖8 訓練時間與網格規模的關系

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

4 結束語

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

[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] 李 然,林 和,李永禮.基于最小描述長度的不完備數據處理[J].蘭州大學學報(自然科學版),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] 李智翔,褚衍杰.基于地理區域聚類的航跡分類方法[J].電信技術研究,2014(1):12-18.

[12] 吳 奎,宋 彥,戴禮榮.基于CUDA的GMM模型快速訓練方法[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].計算機工程,2010,36(6):198-200.

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