基于区域分布概率密度估计的轨迹分类方法

, ,

(盲信号处理重点实验室,成都 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.