CN108804539A - 一种时间与空间双视角下的轨迹异常检测方法 - Google Patents

Abstract

本发明公开了一种时间与空间双视角下的轨迹异常检测方法，通过将轨迹切割成多个轨迹片段，保留轨迹原有的局部特征；从时间与空间两个视角下综合考虑轨迹的异常性，为了提高方法的运行效率：引入时间段和空间网格的概念，获取其所在时间段和空间网格共同相似的轨迹片段；本发明是通过轨迹内异常轨迹片段数目占该轨迹中总轨迹片段数目的比例来判断某条轨迹的异常性；为了降低对测试轨迹误判的几率，将测试轨迹加入到原始轨迹运动模式中，对轨迹数据进行再次训练，获取新的轨迹运动模式并再次判断已被判定为异常的轨迹相对于新的轨迹运动模式是否仍为异常轨迹。

Description

一种时间与空间双视角下的轨迹异常检测方法

技术领域

本发明属于轨迹数据检测技术领域，具体涉及一种时间与空间双视角下的轨迹异常检测方法。

背景技术

随着通信技术、传感器网络技术和定位技术的迅速发展以及GPS定位设备、移动智能终端等设备的普及与应用，大量的个体轨迹信息被采集并保存于数据库中。轨迹信息往往隐藏了个体的运动规律，若能从已知的轨迹信息中挖掘出一定的运动规律并利用其检测异常轨迹，对于个体异常行为检测、城市规划、自然灾害预测等领域有着重大的意义。

目前关于轨迹异常检测方法主要有两大类。一类是通过检测轨迹点的异常程度来判断轨迹整体的异常性，比如Liu等人提出以k个连续轨迹点作为基本比较单元，通过对基本比较单元的对比确定轨迹的局部匹配，利用局部匹配的基本比较单元确定轨迹的全局匹配，从而判断轨迹的状态。之后Liu等人做了进一步的改进，通过判断每个轨迹点的异常度来确定轨迹整体的异常性。由于轨迹中往往包含大量的轨迹点，这类通过检测每个轨迹点的异常程度来判断轨迹整体异常性的方法，使得方法的时间复杂度较高。

另一类检测方法是，先对轨迹进行处理，获取轨迹中的特征点并利用特征点信息来检测轨迹的异常性。目前获取轨迹特征点的方法有两种，一是将每条轨迹划分为多个连续线段的组合，利用轨迹点的转角和速度先将轨迹划分为多个线段，通过判断任意两个线段之间的相似性，挖掘异常轨迹片段，之后通过异常轨迹片段确定轨迹整体的异常性。这些方法的不足之处是在划分轨迹片段时，未考虑个体轨迹运动方向的差异。另一种方法是将轨迹映射到相应的道路网格中，通过将原始轨迹数据映射到道路网格，从而获取其对应的映射轨迹，之后将具有相同的起点和终点的映射轨迹划分到同一组中，获取每个组中最受欢迎的路径并从空间和时间上检测某条轨迹的异常性。这种方法的不足之处是，对轨迹进行了映射，使得所获取的特征点不是轨迹中原有的轨迹点，忽略了轨迹原始的运动信息。这类通过轨迹中的特征点来检测轨迹异常性的方法，仅需检测特征点的异常度，而不需检测轨迹中每个轨迹点的异常度，因此该方法降低了方法的时间复杂度。然而，这类检测方法在检测过程中仅利用了特征点的运动信息，而部分轨迹点的运动信息被忽视，因此这类检测方法忽略了轨迹的局部特征。

通过对目前异常轨迹检测方法的分析后，发现其主要存在以下3大问题：(1)利用轨迹点的异常度来判断轨迹整体异常性的方法，方法的时间复杂度较高；(2)通过获取轨迹中的特征点来判断轨迹异常性的检测方法，虽然降低了方法的时间复杂度，但其往往根据位置和速度的差异来获取特征点，未考虑轨迹点运动方向的差异性且其忽略了轨迹的局部特征，如图1所示，A是某条轨迹的起点，B是轨迹的终点，C、D是轨迹中的两个相邻的轨迹点，从图中可以看到，C、D两点速度的方向相反，若其速率相等，在不考虑轨迹点运动方向时，可能无法判别出C、D两点运动的差异；(3)在大多数方法中，轨迹的运动模式一旦被建立就不会改变，然而轨迹数据具有时序性和变化性，其运动模式可能会随着时间的推移不断变化，如图2所示，对于一个轨迹时序数据，可能在某段时间内即从图2中的轨迹①到轨迹⑤这段时间内，轨迹拥有一个较为稳定的运动模式，而从某一时刻即图中的轨迹⑥开始，时序轨迹数据的运动模式发生了改变，现有的异常检测方法会将轨迹⑥、⑦、⑧、⑨均判断为异常轨迹，而实际上随着时间的推移，这些轨迹可能是正常的。

发明内容

本发明为解决上述不足而提出以下技术方案：

一种时间与空间双视角下的轨迹异常检测方法，包括：

对轨迹集合TR中任意一条轨迹Tr，识别轨迹的全部轨迹点中的切割点，并将相邻两个切割点间的轨迹点集作为所述轨迹的一个轨迹片段，生成轨迹的切割点集合和轨迹片段集合；

将不同轨迹的轨迹片段集合中的轨迹片段分别在时间和空间上进行映射，并利用映射后的时间段和空间网格来寻找轨迹片段的相似轨迹片段集合；

将轨迹集合中所有轨迹分为训练集和测试集，并完成相应的训练过程和测试过程，训练过程实现对训练集中每个轨迹片段状态的标记，测试过程实现对测试集中每条轨迹运动状态的标记；

给定轨迹片段距离阈值ω，若训练集中的第m条轨迹Tr_m的第e个轨迹片段Ts_me相对于训练集中第n条轨迹Tr_n(n≠m)的相似轨迹片段集合ts(Ts_me,Tr_n,ω)中，最长的轨迹片段maxts_n长度不小于轨迹片段Ts_me的长度，则确定轨迹Tr_n为轨迹片段Ts_me的近邻轨迹，从而确定轨迹片段Ts_me的近邻轨迹集合，且在轨迹片段Ts_me的近邻轨迹集合长度大于等于第一指定值时，标记轨迹片段Ts_me为正常轨迹片段，否则标记为异常轨迹片段；

若测试集中的第u条轨迹Tr_u的第f轨迹片段Ts_uf相对于训练集的相似轨迹片段集合中，异常轨迹片段的数量大于正常轨迹片段的数量，将轨迹Tr_u的轨迹片段Ts_uf加入轨迹Tr_u的异常轨迹片段集合，且在轨迹Tr_u的异常轨迹片段集合中异常轨迹片段的数量与轨迹Tr_u中轨迹片段的数量的比值大于第二指定值时，标记轨迹片段Ts_uf为异常轨迹片段，否则标记为正常轨迹片段。

其中，若轨迹Tr_i上的第j+1个轨迹点不满足如下条件，则认为第j+1个轨迹点为转折点即切割点；

式中，V_latj为轨迹Tr_i上第j(1≤j<len_i-1)个轨迹点在纬度方向上的速度，len_i为轨迹Tr_i的长度，V_lonj为该轨迹上第j个轨迹点在经度方向上的速度；V_lat(j+1)为该轨迹上第j+1个轨迹点在纬度方向上的速度，V_lon(j+1)为该轨迹上第j+1个轨迹点在经度方向上的速度；α为速度参数阈值。

其中，对于一条轨迹Tr_i，令dis(p_j-1,p_j)为该轨迹上第j-1和第j(2≤j<len_i)个轨迹点之间的距离，dis(p_j,p_j+1)为该轨迹上第j和第j+1个轨迹点之间的距离，令为第j-1和第j个轨迹点之间的距离以及第j和第j+1个轨迹点之间的距离的平均距离，若如下条件不成立，则认为第j个轨迹点为轨迹T_i的一个切割点；

式中，β为轨迹点距离阈值。

1.其中，在利用映射后的时间段来寻找轨迹片段的相似轨迹片段集合的步骤中，对于一天24小时，设置时间视角参数θ(0<θ≤24)，将一天24小时划分为个时间段，得到时间段序列CT＝(ct₁,ct₂,,ct_γ)，对于一个轨迹集合TR，Tr_m,Tr_n为该轨迹集合内的任意两条轨迹，Ts_me为Tr_m的一个轨迹片段，Ts_me的长度为k_me，设置t_ms为Ts_me起始轨迹点所对应的时间，为Ts_me终止轨迹点所对应的时间，获取轨迹片段Ts_me的映射时间段以及映射时间段的相邻时间段，取并集作为轨迹片段Ts_me在时间上的搜索范围，给定轨迹片段距离阈值ω，在所述搜索范围内以及轨迹Tr_n中，获取与Ts_me相似的轨迹片段集合，并将该集合记为Time(Ts_me,Tr_n,ω)。

其中，对任意一个时间段ctq(1≤q≤γ)，ct_w为其相邻时间段需满足以下两个条件：

(1)1≤w≤γ

(2)|w-q|≤1

其中，q、w和γ均为整数。

其中，在利用映射后的空间网格来寻找轨迹片段的相似轨迹片段集合的步骤中，对于拥有经度、纬度二维位置信息的轨迹，将对应的二维空间划分为Len_lon×Len_lat个网格，即将轨迹的经度空间划分为Len_lon个相等的单元，将轨迹的纬度空间划分为Len_lat个相等的单元；设G为空间网格集合，G＝{g(1,1),g(1,2),,g(id_lon,id_lat),,g(Len_lon,Len_lon)}，g(id_lon,id_lat)为经度空间中的第id_lon个划分与纬度空间中的第id_lat个划分组成的空间网格；对于一个轨迹集合TR，Tr_m,Tr_n为该轨迹集合内的任意两条轨迹，Ts_me为Tr_m的一个轨迹片段，得到轨迹片段Ts_me的映射网格以及映射网格的几何相邻网格后，取网格的并集作为轨迹片段Ts_me在空间上的搜索范围，给定轨迹片段距离阈值ω，在该搜索范围内以及轨迹Tr_n中，获取与Ts_me相似的轨迹片段集合，并将该集合记为Space(Ts_me,Tr_n,ω)。

其中，取Time(Ts_me,Tr_n,ω)与Space(Ts_me,Tr_n,ω)的交集作为轨迹片段Ts_me在轨迹Tr_n中的相似轨迹片段集合ts(Ts_me,Tr_n,ω)。

其中，将测试集中的轨迹Tr_u加入到训练集中构成新的训练轨迹集，再次判断测试集中已被判定为异常的轨迹相对于新的训练集轨迹是否仍为异常轨迹。

区别于现有技术，本发明的时间与空间双视角下的异常检测方法通过将轨迹切割成多个轨迹片段，保留轨迹原有的局部特征；从空间和时间上考虑轨迹的异常性，为了提高方法的运行效率：引入时间段和空间网格的概念，获取其所在时间段和空间网格共同相似的轨迹片段；本发明是通过轨迹内异常轨迹片段数目占该轨迹中总轨迹片段数目的比例来判断某条轨迹的异常性；为了降低对测试轨迹误判的几率，将测试轨迹加入到原始轨迹运动模式中，对轨迹数据进行再次训练，获取新的轨迹运动模式并再次判断已被判定为异常的轨迹相对于新的轨迹运动模式是否仍为异常轨迹。

附图说明

图1为轨迹点运动方向差异的示意图。

图2为轨迹运动模式发生变化示意图。

图3为轨迹片段的近邻轨迹示意图。

图4为本发明方法的方法流程示意图。

图5为本发明提供的一种时间与空间双视角下的轨迹异常检测方法的时间视角下的映射示意图。

图6为本发明提供的一种时间与空间双视角下的轨迹异常检测方法的空间视角下的映射示意图。

具体实施方式

在下面的描述中阐述了很多具体细节以便于充分理解本发明。但是本发明能够以很多不同于在此描述的其它方式来实施，本领域技术人员可以在不违背本发明内涵的情况下做类似推广，因此本发明不受下面公开的具体实施的限制。

其次，本发明利用示意图进行详细描述，在详述本发明实施例时，为便于说明，所述示意图只是实例，其在此不应限制本发明保护的范围。

设某移动对象在三维空间中运动，TR为该移动对象运动轨迹集合，TR中的第i条运动轨迹Tr_i可以表示为：Tr_i＝(p_i1,p_i2,...,p_ij,...,pilen_i)，p_ij＝(x_ij,y_ij,t_ij)其中，len_i为该轨迹中轨迹点的数目，p_ij为轨迹Tr_i中的第j个轨迹点，x_ij、y_ij分别为该轨迹点p_ij在时刻t_ij的经纬度位置信息。

轨迹片段即轨迹中的子轨迹，对于第i条轨迹Tr_i，其第z个轨迹片段可以表示为：其中s≥1∧(s+k_iz-1)≤len_i，k_iz为该轨迹片段的长度(所包含轨迹点的数目)。

对于一个轨迹集合TR，Tr_m、Tr_n(1≤m,n≤L)为该轨迹集合中的任意两条轨迹，L为轨迹集合TR中轨迹的数目。Ts_me是轨迹Tr_m的第e(1≤e≤tsl_m)个轨迹片段，tsl_m为轨迹Tr_m中轨迹片段的数目。Ts_nr是轨迹Tr_n的第r(1≤r≤tsl_n)个轨迹片段，tsl_n为轨迹Tr_n中轨迹片段的数目。给定轨迹片段的距离函数D(Ts_me,Ts_nr)和距离阈值ω，若轨迹片段Ts_me和Ts_nr的距离小于距离阈值ω，则认为Ts_me和Ts_nr相似。令ts(Ts_me,Tr_n,ω)表示为在ω邻域内，轨迹Tr_n中与轨迹Tr_m中第e个轨迹片段相似的轨迹片段集合，maxts_n为ts(Ts_me,Tr_n,ω)中最长的轨迹片段，maxts_n＝max(Ts_no|Ts_no∈ts(Ts_me,Tr_n,ω))，若maxts_n的长度不小于Ts_me的长度，则认为轨迹片段Ts_me与轨迹Tr_n近邻。如图3所示，假设轨迹Tr_n中的第2、5、7轨迹片段与Ts_me相似，maxts_n＝Ts_n7，由于k_n7＞k_me即maxts_n的长度大于Ts_me的长度，因此轨迹片段Ts_me与轨迹Tr_n近邻。令tr(Ts_me,ω)为在轨迹集合TR中与轨迹片段Ts_me近邻的轨迹集合，给定阈值ρ，若l_me<ρ*L，则认为Ts_me为异常轨迹片段，其中l_me为集合tr(Ts_me,ω)中轨迹的数目。

令NTs(Tr_i)为轨迹Tr_i中异常轨迹片段的集合，给定阈值λ，若(|NTs(Tr_i)|/tsl_i)＞λ，则认为Tr_i为异常轨迹，|NTs(Tr_i)|为集合NTs(Tr_i)中异常轨迹片段的数目。

图4是本发明提供的方法的流程示意图。本发明提供了一种时间与空间双视角下的轨迹异常检测方法。该方法的步骤包括：

S110：对轨迹集合中任意一条轨迹，识别轨迹的全部轨迹点中的切割点，并将相邻两个切割点间的轨迹点集作为所述轨迹的一个轨迹片段，生成轨迹的切割点集合和轨迹片段集合。

对于一条轨迹Tr_i，令V_latj为该轨迹上第j(1≤j<len_i-1)个轨迹点在纬度方向上的速度，V_lonj为该轨迹上第j个轨迹点在经度方向上的速度；V_lat(j+1)为该轨迹上第j+1个轨迹点在纬度方向上的速度，V_lon(j+1)为该轨迹上第j+1个轨迹点在经度方向上的速度。

在地球表面上，已知任意两点A、B的经纬度即可求得这两个点之间的距离，如公式(1)所示：

dis(A,B)＝R*arccos(sin(lat_B)sin(lat_A)+cos(lat_B)cos(lat_A)cos(lon_B-lon_A))*π/180 (1)

其中R为地球半径，lon_A、lat_A为A点的经纬度值，lon_B、lat_B为B点的经纬度值。

因此，可由公式(1)推导出轨迹T_i中第j和j+1个轨迹点之间的纬度距离d_lat(p_j,p_j+1)，经度距离d_lon(p_j,p_j+1)分别为：

d_lat(p_j,p_j+1)＝R*arccos(cos(y_j-y_j+1))*π/180 (2)

d_lon(p_j,p_j+1)＝R*arccos(sin²(y_j)+cos²(y_j)cos(x_j+1-x_j))*π/180 (3)

公式(2)、(3)的推导过程如下：设轨迹T_i中第j个轨迹点的经纬度值分别为x_j、y_j，第j+1个轨迹点的经纬度值分别为x_j+1、y_j+1。将第j个和第j+1个轨迹点的经纬度值代入(1)中，得到第j个和第j+1个轨迹点的距离为：

dis(p_j,p_j+1)＝R*arccos(sin(y_j+1)sin(y_j)+cos(y_j+1)cos(y_j)cos(x_j+1-x_j))*π/180 (4)

在计算第j个和第j+1个轨迹点的纬度距离时，其经度值被认为是相等的，因此(4)式可表示为：d_lat(p_j,p_j+1)＝Rarccos(sin(y_j+1)sin(y_j)+cos(y_j+1)cos(y_j)cos(0))*π/180

由cos0＝1以及正余弦和差角公式，对(4)进一步化解为

d_lat(p_j,p_j+1)＝R*arccos(sin(y_j+1)sin(y_j)+cos(y_j+1)cos(y_j))*π/180

＝R*arccos(cos(y_j-y_j+1))*π/180

在计算第j个和第j+1个轨迹点的经度距离时，其纬度值被认为是相等的，因此(4)式可表示为：d_lat(p_j,p_j+1)＝R*arccos(sin(y_j)sin(y_j)+cos(y_j)cos(y_j)cos(x_j+1-x_j))*π/180

进一步化解可得：d_lat(p_j,p_j+1)＝R*arccos(sin²(y_j)+cos²(y_j)cos(x_j+1-x_j))*π/180

由公式(2)、(3)可以求得轨迹Tr_i的第j+1个轨迹点在纬度和经度方向上的速率|v_lat(j+1)|、|v_lon(j+1)|分别为：

不妨规定由南到北、由西到东为正方向。在一般情况下，一条轨迹中轨迹点拥有相同的经纬度方向，因此可得出如下结论：对于处于北纬方向的轨迹，令Δlat(p_j+1,p_j)为该轨迹上第j+1和第j个轨迹点间的纬度差，若Δlat(p_j+1,p_j)＞0，则说明该轨迹从第j个轨迹点到第j+1个轨迹点的运动方向为从南向北即正方向，否则为反方向，因此可以得到，第j+1个轨迹点在纬度方向上的速度V_lat(j+1)为：

而对于处于南纬方向上的轨迹，若Δlat(p_j+1,p_j)<0，则说明该轨迹从第j个轨迹点到第j+1个轨迹点的运动方向为从南向北即正方向，否则为反方向，因此可以得到，第j+1个轨迹点在纬度方向上的速度V_lat(j+1)为：

同理可以得到处于东经方向上的轨迹，其第j+1个轨迹点在经度方向上的速度V_lon(j+1)为：

处于西经方向上的轨迹，其第j+1个轨迹点在经度方向上的速度V_lon(j+1)为：

令α为速度参数阈值，考虑到轨迹点的运动方向性，其速度大小有正负之分，因此在切割轨迹时，需要分别考虑每个轨迹点在纬度和经度方向上速度的正负情况。若轨迹Tr_i上的第j+1个轨迹点不满足条件(11)，则认为第j+1个轨迹点为转折点即切割点。

对于一条轨迹Tr_i，令dis(p_j-1,p_j)为该轨迹上第j-1和第j(2≤j<len_i)个轨迹点之间的距离，dis(p_j,p_j+1)为该轨迹上第j和第j+1个轨迹点之间的距离，令为第j-1和第j个轨迹点之间的距离以及第j和第j+1个轨迹点之间的距离的平均距离，β为轨迹点距离阈值，若条件(13)不成立，则认为第j个轨迹点为轨迹T_i的一个切割点。

对于一条轨迹Tr_i，从该轨迹中的第j(2≤j<len_i)个轨迹点开始，依次判断第j个轨迹点速度和位置的异常情况，若第j个轨迹点不满足条件(11)和(13)中的任意一个条件，则认为第j个轨迹点为轨迹Tr_i中的一个切割点。任意一条轨迹都存在两个特殊的轨迹点即轨迹的起点和终点，一条轨迹的起点没有前驱点，一条轨迹的终点没有后继点，因此在寻找轨迹的切割点时，直接将这两个特殊点判定为切割点。

通过轨迹中轨迹点的速度和位置得到该轨迹的切割点后，将相邻两个切割点间的轨迹点集合即子轨迹视为该轨迹的一个轨迹片段。

S120：将不同轨迹的轨迹片段集合中的轨迹片段分别在时间和空间上进行映射，并利用映射后的时间段和空间网格来寻找轨迹片段的相似轨迹片段集合。

对于一个轨迹集合TR，Tr_m,Tr_n为该轨迹集合内的任意两条轨迹，Ts_me为Tr_m的一个轨迹片段，若依次判断轨迹Tr_n中每一个轨迹片段与Ts_me的相似性，将会降低方法的运行效率。为此，本方法采用了双视角映射方法，将轨迹片段分别在时间和空间上进行映射，并利用映射后的时间段和空间网格来寻找轨迹片段的相似轨迹片段，大大缩小了搜索范围。

对于一天24小时，利用时间视角参数θ(0<θ≤24)可将其划分为个时间段，由此可得到一个时间段序列CT＝(ct₁,ct₂,,ct_γ)，t_ms为Ts_me起始轨迹点所对应的时间，为Ts_me终止轨迹点所对应的时间，获取轨迹片段Ts_me的映射时间段的方法为：

setp1：比较Ts_me轨迹片段起点和终点的时间，若则执行setp2，否则执行setp3；

setp2:令

for temp＝0:Δtme

令判断Ct_me是否包含时间段ct_ε，若不包含，则将ct_ε放入集合Ct_me；

end

setp3:令

for temp＝0:Δtme

令判断Ct_me是否包含时间段ct_ε，若不包含，则将ct_ε放入集合Ct_me；

end

for

令判断Ct_me是否包含时间段ct_ε，若不包含，则将ct_ε放入集合Ct_me。

对于任意一个时间段ctq(1≤q≤γ)，ct_w为其相邻时间段需满足以下两个条件：

(1)1≤w≤γ

(2)|w-q|≤1

得到轨迹片段Ts_me的映射时间段以及映射时间段的相邻时间段后，取这些时间段的并集作为轨迹片段Ts_me在时间上的搜索范围，给定轨迹片段距离阈值ω，在所述搜索范围内以及轨迹Tr_n中，获取与Ts_me相似的轨迹片段集合，并将该集合记为Time(Ts_me,Tr_n,ω)。

为了提高相似轨迹片段在空间范围内的查寻效率，本方法提出将空间划分为多个互不重叠的矩形即空间网格。轨迹片段通过映射到空间网格，在映射的空间网格以及该空间网格相邻的空间网格内搜索相似轨迹片段，将全局搜索转换为局部搜索，有效地提高了搜索效率。

对于拥有经度、纬度二维位置信息的轨迹，可将其对应的二维空间划分为Len_lon×Len_lat个网格，即将轨迹的经度空间划分为Len_lon个相等的单元，将轨迹的纬度空间划分为Len_lat个相等的单元。设G为空间网格集合，G＝{g(1,1),g(1,2),,g(id_lon,id_lat),,g(Len_lon,Len_lon)}，g(id_lon,id_lat)为经度空间中的第id_lon个划分与纬度空间中的第id_lat个划分组成的空间网格。

得到轨迹片段Ts_me的映射网格以及映射网格的几何相邻网格后，取这些网格的并集作为轨迹片段Ts_me在空间上的搜索范围，在该搜索范围内以及轨迹Tr_n中，获取与Ts_me相似的轨迹片段集合，并将该集合记为Space(Ts_me,Tr_n,ω)。

最后，取Time(Ts_me,Tr_n,ω)与Space(Ts_me,Tr_n,ω)的交集作为轨迹片段Ts_me在轨迹Tr_n中的相似轨迹片段集合ts(Ts_me,Tr_n,ω)。

设Tr_n拥有5个轨迹片段，时间间隔θ取值为1小时，将二维空间划分为7×6个网格，如图5、6所示。图5显示了轨迹Tr_n和轨迹片段Ts_me时间上的映射情况，从图中可以了解到，轨迹Tr_n的轨迹片段映射到了时间段ct₂～ct₁₃，获取这些映射时间段的相邻时间段与其的交集为ct₁～ct₁₄。轨迹片段Ts_me映射到了时间段ct₈～ct₁₀，获取这些时间段的相邻时间段与其的交集为ct₇～ct₁₁。假设Tr_n3、Tr_n4、Tr_n5与Ts_me的距离均小于ω，即Tr_n3、Tr_n4、Tr_n5与Ts_me相似，最终可得到集合Time(Ts_me,Tr_n,ω)，Time(Ts_me,Tr_n,ω)＝{Tr_n3,Tr_n4,Tr_n5}。

图6显示了轨迹Tr_n和轨迹片段Ts_me空间上的映射情况，从图中可以看到轨迹片段Ts_me映射到了网格g(4,4)、g(5,4)、g(5,5)，获取这些网格的相邻网格与其的交集为g(3,3)、g(3,4)、g(3,5)、g(4,3)、g(4,4)、g(4,5)、g(4,6)、g(5,3)、g(5,4)、g(5,5)、g(5,6)、g(6,3)、g(6,4)、g(6,5)、g(6,6)，如图中的阴影部分。假设Tr_n4、Tr_n5与Ts_me的距离均小于ω，即Tr_n4、Tr_n5与Ts_me相似，最终得到集合Space(Ts_me,Tr_n,ω)，Space(Ts_me,Tr_n,ω)＝{Ts_n4,Ts_n5}。由Time(Ts_me,Tr_n,ω)和Space(Ts_me,Tr_n,ω)，可以得到在轨迹Tr_n中，与轨迹片段Ts_me相似的轨迹集合ts(Ts_me,Tr_n,ω)，ts(Ts_me,Tr_n,ω)＝{Ts_n4,Ts_n5}。

S130：将轨迹集合中所有轨迹分为训练集trainTR和测试集testTR。

对于一个轨迹集合TR，将其前h条轨迹作为训练样本，构成训练轨迹集合trainTR，trainTR＝{Tr₁,Tr₂,,Tr_h}，将第h+1之后的轨迹作为测试样本，构成测试轨迹集合testTR，testTR＝{Tr_h+1,Tr_h+2,,Tr_L}。

S140：若训练集中的轨迹Tr_m的第e个轨迹片段Ts_me相对于训练集中轨迹Tr_n的相似轨迹片段集合ts(Ts_me,Tr_n,ω)中，最长的轨迹片段maxts_n长度不小于轨迹片段Ts_me的长度，则确定轨迹Tr_n为轨迹片段Ts_me的近邻轨迹，从而确定轨迹片段Ts_me的近邻轨迹集合，且在轨迹片段Ts_me的近邻轨迹集合长度大于等于第一指定值时，标记轨迹片段Ts_me为正常轨迹片段，否则标记为异常轨迹片段。

S150：若测试集中的轨迹Tr_u的第f轨迹片段Ts_uf相对于训练集trainTR的相似轨迹片段集合中，异常轨迹片段的数量大于正常轨迹片段的数量，将轨迹Tr_u的轨迹片段Ts_uf加入轨迹的异常轨迹片段集合，且在轨迹Tr_u的异常轨迹片段集合中异常轨迹片段的数量与轨迹Tr_u中轨迹片段的数量的比值大于第二指定值时，标记轨迹片段Ts_uf为正常轨迹片段，否则标记为异常轨迹片段。

由于轨迹数据具有时序性和变化性，其运动模式即运动状态可能会随着时间的推移不断变化，而目前异常检测方法往往忽视了这一点。为此本方法在测试阶段不仅检测测试轨迹的异常性，还要再次确定新轨迹集中每条轨迹所有轨迹片段的运动状态即重新获取轨迹集新的运动模式，并重新判断之前已被判定为异常的测试轨迹的运动状态，以降低测试轨迹的误判率。

对于一条测试轨迹，利用训练阶段得到的轨迹集中所有轨迹片段的运动状态来确定测试轨迹的异常性。

为了提高测试阶段方法的运行效率，将测试阶段的方法分为在线和离线两个过程，在线过程实时检测测试轨迹的异常性，离线过程获取轨迹集中所有轨迹片段的运动状态，在线过程与离线过程同步进行，有效地提高了方法的运行效率。在离线过程中，若用训练阶段的方法重新获取轨迹集中所有轨迹片段的运动状态，将会增大测试阶段方法的运行负担且带来一些不必要的操作。由于在训练阶段中，对于轨迹集TR中的任意一条轨迹Tr_i，轨迹Tr_i的每一个轨迹片段Ts_iz(1≤z≤L)的近邻轨迹集合tr(Ts_iz,ω)已被求得，因此在重新训练过程中，重新获取轨迹集TR中每个轨迹片段Ts_iz的近邻轨迹集合tr(Ts_iz,ω)时，仅需判断测试轨迹Tr_u是否与轨迹片段Ts_iz近邻，若近邻，则将轨迹Tr_u加入到轨迹片段Ts_iz的原始近邻轨迹集合tr(Ts_iz,ω)中并重新判断Ts_iz的运动状态，否则轨迹片段Ts_iz的运动状态不变。在重新训练过程中，标记测试轨迹Tr_u中每个轨迹片段运动状态方法与标记轨迹片段运动状态的方法相同。

其中，在线处理方法为在原始训练轨迹集trainTR中，利用寻找相似轨迹片段的方法求得测试轨迹Tr_u的第f个轨迹片段的相似轨迹片段集合ts(Ts_uf,trainTR,ω)，设abnumber为集合ts(Ts_uf,trainTR,ω)中异常轨迹片段的数目，number为集合ts(Ts_uf,trainTR,ω)中正常轨迹片段的数目，若abnumber＞number，则将Ts_uf加入到集合NTs(Tr_u)中，集合NTs(Tr_u)为轨迹Tr_u中异常轨迹片段的集合；如果满足(|NTs(Tr_u)|/tsl_u)＞λ，将轨迹Tr_u标记为异常轨迹；tsl_u为轨迹Tr_u中轨迹片段的数目。

离线处理方法为对于原始轨迹集trainTR中的每一条轨迹Tr_i，重新获取轨迹Tr_i中的每一个轨迹片段Ts_iz的近邻轨迹集合tr(Ts_iz,ω)并重新确定Ts_iz的状态，标记测试轨迹Tr_u中每个轨迹片段运动状态：获取Tr_u的轨迹片段集合，在原始轨迹集trainTR中获取轨迹Tr_u中每个轨迹片段的近邻轨迹集合并根据近邻轨迹集合标记轨迹片段的运动状态。对之前已被判定为异常的测试轨迹即轨迹集altestTR中的轨迹，再次判断轨迹的状态。

本文主要研究了轨迹的异常检测方法，提出了时间与空间双视角下的轨迹异常检测方法，本方法主要分为训练阶段和测试阶段，测试阶段又分为在线和离线两个过程。

在训练阶段，对轨迹训练集进行学习，通过切割轨迹，寻找相似轨迹片段并获取每条轨迹中每个轨迹片段的运动状态的方法，发现轨迹训练集的运动模式。利用了每个轨迹点的位置以及轨迹点速度的大小和方向信息，不仅考虑了轨迹位置的差异性，也考虑了轨迹运动方向的差异性。在获取相似性轨迹片段时，为了提高方法的运行效率，本文采用了双视角映射方法，引入时间段和空间网格的概念，通过将轨迹片段映射到相应的时间段和空间网格中，获取其所在时间段和空间网格共同相似的轨迹片段。

在测试阶段，区别于现有的异常检测方法，考虑到异常轨迹发生概率较低，属于非平衡数据范畴，因此本方法通过轨迹内异常轨迹片段数目占该轨迹中总轨迹片段数目的比例来判断某条轨迹的异常性而不是利用异常轨迹片段的轨迹点数占总轨迹点数的比例来确定轨迹的异常性。从而有效地减小了数据的非平衡程度，更能高效地发现异常轨迹。本方法将测试阶段分为在线和离线两个过程，在线过程和离线过程实现并行操作，从而提高了方法的运行效率。

在在线过程中，针对轨迹测试集，对每一条测试轨迹进行实时性检测，及时发现异常轨迹。

在离线过程中，考虑到移动对象轨迹的运动模式可能会随着时间的推移而发生变化，因此在该过程中，本方法会重新获取轨迹的运动模式，并重新判断已被判定为异常的测试轨迹相对于新的轨迹运动模式是否仍为异常轨迹，以降低对测试轨迹误判的几率。

区别于现有技术，本发明的时间与空间双视角下的异常检测方法通过将轨迹切割成多个轨迹片段，保留轨迹原有的局部特征；从空间和时间上考虑轨迹的异常性，为了提高方法的运行效率：引入时间段和空间网格的概念，获取其所在时间段和空间网格共同相似的轨迹片段；本发明是通过轨迹内异常轨迹片段数目占该轨迹中总轨迹片段数目的比例来判断某条轨迹的异常性；为了降低对测试轨迹误判的几率，将测试轨迹加入到原始轨迹运动模式中，对轨迹数据进行再次训练，获取新的轨迹运动模式并再次判断已被判定为异常的轨迹相对于新的轨迹运动模式是否仍为异常轨迹。

本发明虽然已以较佳实施例公开如上，但其并不是用来限定本发明，任何本领域技术人员在不脱离本发明的精神和范围内，都可以利用所述揭示的方法和技术内容对本发明技术方案做出可能的变动和修改，因此，凡是未脱离本发明技术方案的内容，依据本发明的技术实质对以上实施例所作的任何简单修改、等同变化及修饰，均属于本发明技术方案的保护范围。

Claims (9)

1.一种时间与空间双视角下的轨迹异常检测方法，其特征在于，包括：

对轨迹集合TR中任意一条轨迹Tr，识别轨迹的全部轨迹点中的切割点，并将相邻两个切割点间的轨迹点集作为所述轨迹的一个轨迹片段，生成轨迹的切割点集合和轨迹片段集合；

将不同轨迹的轨迹片段集合中的轨迹片段分别在时间和空间上进行映射，并利用映射后的时间段和空间网格来寻找轨迹片段的相似轨迹片段集合；

将轨迹集合中所有轨迹分为训练集和测试集，并完成相应的训练过程和测试过程，训练过程实现对训练集中每个轨迹片段状态的标记，测试过程实现对测试集中每条轨迹运动状态的标记；

给定轨迹片段距离阈值ω，若训练集中的第m条轨迹Tr_m的第e轨迹片段Ts_me相对于训练集中第n条轨迹Tr_n(n≠m)的相似轨迹片段集合ts(Ts_me,Tr_n,ω)中，最长的轨迹片段maxts_n长度不小于轨迹片段Ts_me的长度，则确定轨迹Tr_n为轨迹片段Ts_me的近邻轨迹，从而确定轨迹片段Ts_me的近邻轨迹集合，且在轨迹片段Ts_me的近邻轨迹集合长度大于等于第一指定值时，标记轨迹片段Ts_me为正常轨迹片段，否则标记为异常轨迹片段；

若测试集中的第u条轨迹Tr_u的第f轨迹片段Ts_uf相对于训练集的相似轨迹片段集合中，异常轨迹片段的数量大于正常轨迹片段的数量，将轨迹Tr_u的轨迹片段Ts_uf加入轨迹Tr_u的异常轨迹片段集合，且在轨迹Tr_u的异常轨迹片段集合中异常轨迹片段的数量与轨迹Tr_u中轨迹片段的数量的比值大于第二指定值时，标记轨迹片段Ts_uf为异常轨迹片段，否则标记为正常轨迹片段。

2.根据权利要求1所述的时间与空间双视角下的轨迹异常检测方法，其特征在于，若轨迹Tr_i上的第j+1个轨迹点不满足如下条件，则认为第j+1个轨迹点为转折点即切割点；

式中，V_latj为轨迹Tr_i上第j(1≤j<len_i-1)个轨迹点在纬度方向上的速度，len_i为轨迹Tr_i的长度，V_lonj为该轨迹上第j个轨迹点在经度方向上的速度；V_lat(j+1)为该轨迹上第j+1个轨迹点在纬度方向上的速度，V_lon(j+1)为该轨迹上第j+1个轨迹点在经度方向上的速度；α为速度参数阈值。

3.根据权利要求1所述的时间与空间双视角下的轨迹异常检测方法，其特征在于，对于一条轨迹Tr_i，令dis(p_j-1,p_j)为该轨迹上第j-1和第j(2≤j<len_i)个轨迹点之间的距离，dis(p_j,p_j+1)为该轨迹上第j和第j+1个轨迹点之间的距离，令为第j-1和第j个轨迹点之间的距离以及第j和第j+1个轨迹点之间的距离的平均距离，若如下条件不成立，则认为第j个轨迹点为轨迹T_i的一个切割点；

式中，β为轨迹点距离阈值。

4.根据权利要求1所述的时间与空间双视角下的轨迹异常检测方法，其特征在于，在利用映射后的时间段来寻找轨迹片段的相似轨迹片段集合的步骤中，对于一天24小时，设置时间视角参数θ(0<θ≤24)，将一天24小时划分为个时间段，得到时间段序列CT＝(ct₁,ct₂,,ct_γ)，对于一个轨迹集合TR，Tr_m,Tr_n为该轨迹集合内的任意两条轨迹，Ts_me为Tr_m的一个轨迹片段，Ts_me的长度为k_me，设置t_ms为Ts_me起始轨迹点所对应的时间，为Ts_me终止轨迹点所对应的时间，获取轨迹片段Ts_me的映射时间段以及映射时间段的相邻时间段，取并集作为轨迹片段Ts_me在时间上的搜索范围，给定轨迹片段距离阈值ω，在所述搜索范围内以及轨迹Tr_n中，获取与Ts_me相似的轨迹片段集合，并将该集合记为Time(Ts_me,Tr_n,ω)。

5.根据权利要求4所述的时间与空间双视角下的轨迹异常检测方法，其特征在于，对于任意一个时间段ctq(1≤q≤γ)，ct_w为其相邻时间段需满足以下两个条件：

(1)1≤w≤γ

(2)|w-q|≤1

其中，q、w和γ均为整数。

6.根据权利要求4所述的时间与空间双视角下的轨迹异常检测方法，其特征在于，根据时间视角参数和轨迹片段的起始时间获取轨迹片段相应的映射时间段。

7.根据权利要求1所述的时间与空间双视角下的轨迹异常检测方法，其特征在于，在利用映射后的空间网格来寻找轨迹片段的相似轨迹片段集合的步骤中，对于拥有经度、纬度二维位置信息的轨迹，将对应的二维空间划分为Len_lon×Len_lat个网格，即将轨迹的经度空间划分为Len_lon个相等的单元，将轨迹的纬度空间划分为Len_lat个相等的单元；设G为空间网格集合，G＝{g(1,1),g(1,2),,g(id_lon,id_lat),,g(Len_lon,Len_lon)}，g(id_lon,id_lat)为经度空间中的第id_lon个划分与纬度空间中的第id_lat个划分组成的空间网格；对于一个轨迹集合TR，Tr_m,Tr_n为该轨迹集合内的任意两条轨迹，Ts_me为Tr_m的一个轨迹片段，得到轨迹片段Ts_me的映射网格以及映射网格的几何相邻网格后，取网格的并集作为轨迹片段Ts_me在空间上的搜索范围，给定轨迹片段距离阈值ω，在该搜索范围内以及轨迹Tr_n中，获取与Ts_me相似的轨迹片段集合，并将该集合记为Space(Ts_me,Tr_n,ω)。

8.根据权利要求4-7任意一项所述的时间与空间双视角下的轨迹异常检测方法，其特征在于，取Time(Ts_me,Tr_n,ω)与Space(Ts_me,Tr_n,ω)的交集作为轨迹片段Ts_me在轨迹Tr_n中的相似轨迹片段集合ts(Ts_me,Tr_n,ω)。

9.根据权利要求1所述的时间与空间双视角下的轨迹异常检测方法，其特征在于，将测试集中的轨迹Tr_u加入到训练集中构成新的训练轨迹集，再次判断测试集中已被判定异常的轨迹相对于新的训练集轨迹是否仍为异常轨迹。