采用轨迹压缩和路网划分的车辆异常轨迹检测

苏建花，赵旭俊，蔡江辉

(太原科技大学 计算机科学与技术学院，太原 030024)

1 引 言

随着社会的进步，出租车和网约车逐渐成为人们出行的重要选择，随之出现的是层出不穷的网约平台.由于故意绕路使乘客支付不必要的费用等欺诈行为以及因轨迹存在异常隐含的刑事案件不断增多，保障乘客在乘车过程中的权益和人身安全已经成为亟待解决的问题.快速有效地从海量轨迹数据集中发现存在异常的车辆轨迹，挖掘背后有意义的隐藏信息，已成为众多学者研究的热点之一.

异常轨迹是指轨迹数据集中不符合给定条件或与大多数轨迹显著不同的轨迹[1].现有的检测算法根据轨迹之间的关系确定数据集中的异常轨迹.对于异常轨迹的检测非常有成效，并被广泛地应用于各个方面.

但仍存在一些不可避免的问题:1)TRAOD算法[2]和R-Tree算法[3]将轨迹划分为轨迹段集，通过与大多数轨迹之间的距离关系判断轨迹是否异常.但是其只突出位置信息对评估轨迹离群程度的影响，忽略了其他因素的作用.同时TRAOD需要人工设置许多参数，而参数越多，人为因素对检测结果的干扰就越大；2)参与检测的数据质量低.DBTOD算法[4]和SHNN-CAD算法[5]直接使用位置设备获取的数据，未考虑值丢失，数据失真等问题，忽略正常轨迹与异常轨迹的差异，导致检测结果准确率较低；3)文献[6]和文献[7]只适合出发地(S)和目的地(D)相同的轨迹，无法适应大范围的检测.而实际上车辆行驶是没有规律的，故存在一定的局限性.

针对上述问题，提出了一种采用轨迹压缩和路网划分的车辆异常轨迹检测算法(Vehicle anomalous detection based on trajectory compression and road network partition，PC-ATD)，将检测问题模型转化为道路的消耗，同时考虑位置变换和时间变化的影响，具体分为3个阶段:第1个阶段为数据预处理.首先，使用地图匹配概率将轨迹转化为遵循道路走向的点序列组合，解决了数据质量低的问题；其次，根据轨迹点序列，在道路交叉处填补缺失数据，确保轨迹划分后能够完整表示在每一路段上的轨迹段；然后，依据道路节点和车辆行驶方向是否改变对轨迹进行压缩，以减少内存消耗和后期参与计算的数据量；最后，以插点为节点将轨迹按照所在路段进行划分.第2个阶段为离线训练阶段.训练历史数据的时间和距离消耗构建道路消耗模型，并使用Dijkstra[8]算法获取路网中所有S-D对的最小消耗值.第3个阶段为检测阶段.计算支撑检测的消耗阈值矩阵，通过目标轨迹消耗与对应阈值的关系确定轨迹是否异常.由于异常轨迹在行驶过程中的消耗远远大于正常轨迹的消耗，因此行驶消耗高出阈值范围的轨迹就是要找的异常轨迹.

2 相关工作

近年来，关于异常轨迹检测的研究，众多学者已经提出许多优秀的算法[9，10].本节中主要研究了4种类型的异常轨迹检测算法：基于分类的算法、基于距离的算法、基于历史相似性的算法和基于网格的算法.

2.1 基于分类的检测方法

Wu等人[11]在双流体系结构中嵌入VAE/GAN，通过对先验数据进行离线训练构造一个分类器.该算法随着轨迹数据的不断收集，无法有效检测到进化的未知的异常.针对这一问题，Laxhammar等人[5]提出了SHNN-CAD算法，将旧的测试集不断的加入到训练集中，实现进化的未知的轨迹异常检测.当更新训练集时，需要动态的调整异常阈值，并将更新后的距离度量作为SHNN-CAD的输入，对下一个测试示例进行分类.当训练集增大到一定程度时，异常阈值的动态调整将会需要更高的计算成本.

基于分类的算法需要人工对数据进行准确标注，导致高昂的计算开销.且当缺失具有标签的训练集时，无法构建合适的分类器.

2.2 基于距离的检测方法

Liu等人[3]通过R-Tree以及轨迹基本比较单元之间的距离依次找到所有局部匹配的基本比较单元对，根据各轨迹比较单元之间的匹配情况确定它们是否全局匹配.该算法需要频繁计算各轨迹单元之间的距离，时间开销较大，执行效率较低.为避免以轨迹基本比较单元直接表示轨迹特征带来的问题，Bae等人[12]使用局部运动代替物体的运动，对物体的局部运动进行特征提取，依次连接具有时空连续性的特征点形成部分轨迹，并建立起相应的运动模式.但收集的轨迹数据无法涵盖所有异常现象，故构建的运动模式无法完全准确的检测到所有可能存在的异常.Lu等人[13]通过特征相似性度量将轨迹聚类到m簇，通过目标轨迹段与簇中心的距离确定轨迹属于已存在的簇还是一个新的簇.以上3种算法只适合在静态轨迹数据集下的检测.

针对轨迹流数据，Yu等人[14]在前期方法的基础上，对轨迹在时间轴上进行了纵向划分，设置恰当的阈值，从时间和空间的相关性上确定轨迹之间的关系.

基于距离的算法重点监测位置特征表现出来的异常，忽略了其他因素的作用，无法有效检测到与位置无关的特征所导致的异常现象.

2.3 基于历史相似性的检测方法

Fu等人[15]通过离线训练建立了一个关于行为特征的全局特征模型，使用时间感知和空域相关的协同算法对轨迹进行检测.此算法在不考虑轨迹时变进化特性时具有较高的检测精度，但随着轨迹数据飞速增加，新的异常现象随之产生，异常检测精度越来越低.针对这一现象，Mao等人[16]定义了局部异常轨迹碎片和进化异常运动目标的概念，从轨迹段集中获取所有特征点，搜索轨迹碎片领域，计算局部异常因子，通过局部异常因子生成演化异常因子.不仅能检测静态轨迹数据集中的异常现象，还能在模型的不断更新中捕捉轨迹流中时变的异常.Mao等人[7]通过无监督的贝叶斯反向增强算法对车辆的驾驶行为进行建模，并新增路段奖励函数和路段潜在开销函数.但是实际上道路状况是瞬息万变的，该算法无法适应动态变化的道路状况检测.

基于历史相似性的方法在采集到足够的轨迹数据时具有较高的检测精度，但是随着数据规模的不断增大，需对模型进行阶段性重建，需要较高的计算开销.

2.4 基于网格的检测方法

Chen等人[6]通过比较异常路由与正常路由在线监测轨迹中出现的异常，并确定异常发生的起因.但需要对检测范围进行网格划分，当轨迹超出一定数目，网格划分需要巨额的时间开销.Liu等人[4]通过确定目标轨迹与子轨迹的距离和在给定范围内邻域子轨迹的个数来判定目标轨迹是否异常.此算法只适合轨迹密度较大时的检测，当轨迹数目稀疏时，无法获取足够的领域子轨迹来判定轨迹是否异常.

基于网格划分的方法需要多次调整参数寻找合适的网格大小，在这个过程中将消耗大量的时间，导致检测效率低的问题.

3 基于地图匹配和轨迹插点压缩的路网划分

3.1 地图匹配

针对大部分算法直接使用位置设备获取的数据进行建模，未考虑数据实际质量导致检测精度偏低的问题，选择将轨迹数据映射到路网中，使最终得到的轨迹遵循真实路径的走向.相关定义如下：

定义1.道路网络.道路网络G是一个有向图网络，其中V表示道路节点集，E表示道路路段集.对路段e∈E，其起点为ei.s，终点为ei.d，有ei.d=ei+1.s，s，d∈V.

定义2.轨迹.轨迹是指运动物体的位置记录序列，由定位设备获得的一系列具有时空连续性的GPS轨迹点组成，即：

T={P1，P2，…，Pn}

(1)

考虑在地图匹配中空间坐标的变换，后期需计算轨迹在道路节点处的速度和时间戳，以及根据插点和行驶方向变换实现轨迹压缩，选择以七维矢量表示轨迹点，即pi=〈Idi，ti，loni，lati，vi，θi，si〉，其中Id是轨迹的唯一标识；t表示设备报告轨迹点的时间戳；lon和lat为轨迹点的空间坐标；v和θ分别是车辆在当前时间戳的瞬时速度和顺时针方向与北方的夹角；s是此刻车辆的状态.轨迹点按时间顺序到达，即满足：t1

路网中路段量大，将轨迹点在每一路段上进行投影计算成本过高，而实际上位置接收设备的误差是有限的，因此选取与轨迹点在一定路网距离内的路段作为候选路段，并选择路段上与轨迹点距离最近的点作为候选点来表示轨迹点在候选道路上的映射位置.定义如下：

定义3.候选路段.对于∀e∈E，若轨迹点p到路段e的距离d(p，e)满足：d(p，e)

定义4.候选点.轨迹点p在候选路段e上的候选点，记作mp，e，定义为e上与p距离最近的点，即满足：

d(p，mp，e)=min(d(me，p))

(2)

其中：me为e上的任意一点.

为了将轨迹数据更准确地映射到路网空间，使用匹配概率度量候选点与轨迹点的匹配度，以确定候选点在映射序列中被选中的可能性.匹配概率由候选点的观测概率和转移概率得出.所以在介绍匹配概率的形式化定义之前，将先给出观测概率和转移概率的定义.

给定一个轨迹点pi∈T，一条路段ej∈E且d(pi，ej)

(3)

其中：δ是标准偏差；d(pi，mpi，ej)为pi与mpi，ej之间的距离.

候选点的观测概率与候选点与轨迹点的距离相关，其随着候选点与轨迹点距离的减小而变大，即对于距离较近的候选点给予较大的观察概率.

假设映射序列中mpi，ej的上一映射点为mpi-1，et，mpi，ej的转移概率为映射序列中由mpi-1，et转移至mpi，ej的可能性，定义为：

(4)

其中：d(pi-1→pi)是相邻轨迹点pi-1和pi之间的空间距离；td(mpi-1，et→mpi，ej)是相邻候选点mpi-1，et和mpi，ej之间的最短路网转移距离.

映射序列的路网转移距离越小，映射转移的概率可能性越高.但要最终确定候选点与轨迹点的匹配程度，需要同时考虑候选点的观测概率和转移概率.根据公式(3)和公式(4)可以得到mpi，ej的匹配概率为：

MP(mpi，ej)=MP(mpi-1，et)+OP(mpi，ej|pi)×
DP(mpi-1，et→mpi，ej)

(5)

OP(mpi，ej|pi)和DP(mpi-1，et→mpi，ej)越大，mpi，ej的匹配概率越高，即在映射序列中被选中的可能性越大.在地图匹配过程中，考虑到路网的连通性，保存所有匹配步骤的最小总代价以及该代价情况下所有匹配步骤的选择，在所有轨迹点的候选点状态计算结束后，利用Viterbi算法通过回溯的方法找到轨迹点匹配序列中匹配概率最大的映射路径作为最终的匹配结果.

3.2 基于轨迹插点的轨迹压缩

由于轨迹收集率高，对内存和计算提出了新的挑战，因此选择通过轨迹压缩缓解内存压力，并减少后期参与计算的数据量.且在异常轨迹检测中，需将轨迹按照轨迹点所在路段进行划分，并加入到所在路段的轨迹段集合中.但实际情况下无法保证轨迹发生路段转移时，在相邻两路段的交叉口处存在轨迹点，导致划分后，在路段的起点和终点处可能存在信息丢失.

为保证划分后路段上轨迹段的完整性，且在离线训练和检测过程中仅考虑空间位置的变换和时间的消耗.在轨迹压缩和划分前，选择在轨迹发生路段转移的交叉口处进行插点.并根据前后轨迹点的时间戳和速度计算插点的相关信息.给定轨迹T′∈地图匹后的轨迹数据集TD′，且∃pi-1，pi∈T′.假设et，ej，为相邻两路段，存在以下4种情况：

1)pi为T′在ej上的第一个采样点且为T′的起始轨迹点，则在ej和et的交叉口处插入pet，ej.此时vi-1和ti-1均为0.

2)pi是et的最后一个采样点且是ej的第一个采样点，即pi为T′在et和ej交叉口处的轨迹点，则在交叉口插入pet，ej.此时pet，ej=.

3)pi-1为et上的最后一个采样点，pi为ej上的第一个采样点，且pi-1≠pi，则在et与ej交叉口插入pet，ej.pet，ej的空间坐标即为该交叉口的空间坐标，其行驶速度以及时间戳计算公式如下：

(6)

(7)

其中：d(pi-1，pet，ej)和d(pi，pet，ej)分别表示pet，ej与pi-1和pi的距离；S=d(pi-1，pet，ej)+d(pi，pet，ej).

4)pi-1为T′在et上的最后一个采样点且为T′的结束轨迹点，则在et和ej的交叉口处插入pet，ej.此时vi和ti均为0.

插点后得到的新数据集TD″.根据插点和车辆行驶方向是否发生变化对TD″中的轨迹依次进行压缩.轨迹压缩是输入一条轨迹数据后，输出一条新的轨迹，其含轨迹点更少但能最大限度的表示原始轨迹.压缩过程中，通过保留满足要求的轨迹点，删除不必要的数据样本以减小数据量的大小.即保留轨迹插点和行驶方向发生变化前后的轨迹点，删除不是插点且行驶方向未变化的点.

详细地，假设运动对象在路段e上行驶，e的两个端点分别是e.s和e.d.如果轨迹点pi满足：d(pi，e.s)=0或者d(pi，e.d)=0，即pi是道路节点处的插点，直接保留.当运动对象在e上由pi-1途经pi驶向pi+1，且pi-1和pi+1不是e的起点和终点时，若满足：d(pi+1，pi-1)>d(pi，pi-1)，即pi+1不是插点且行驶方向未发生变化，则删除点pi+1；否则保留pi+1.可得到压缩后的数据集TD‴.可以发现在不丢失重要信息的前提下，通过轨迹压缩可以最大限度的减少原始轨迹中的轨迹点量和检测过程中的计算量，且不会影响数据的后续使用.

3.3 轨迹划分

轨迹压缩后，以插点为节点对轨迹进行划分，给定一条轨迹T‴∈TD‴，划分步骤如下：

Step 1.假设pet，ej为T‴的第1个插入点，T‴在ej的初始轨迹段为Tsej，T‴={pet，ej}.若pi‴∈T‴(i≥1)不是插入点，则Tsej，T‴=Tsej，T‴∪pi；若pi为pet，ej的相邻插入点pej，es，则Tsej，T‴=Tsej，T‴∪pej，es.则得到T‴在ej上的轨迹段.

Step 2.以pej，es为新的起点，T‴在es的初始轨迹段为Tses，T‴={pej，es}，寻找T‴中与pej，es相邻的插入点pes，eu，并作为新的终点，将pej，es和pes，eu以及两点之间的轨迹点划分至路段es的轨迹段集合中，步骤同Step 1.

Step 3.重复Step 2，直至轨迹在当前路段的轨迹段终点为轨迹的最后一个轨迹点，即最后一个插入点.可得到轨迹T‴划分后的轨迹段集合为：{Tsej，T‴={pet，ej，…，pej，es}，Tses，T‴={pej，es，…，pes，eu}，…}.

根据插点对轨迹进行分割后，既可以正确表示轨迹在每一路段上的完整轨迹段，重新整合后又不会丢失原始轨迹的重要信息.

TD‴中所有轨迹划分结束后，将各轨迹中属于同一路段的轨迹段加入到该路段的轨迹段集中.即给定一个路段ej，ej的轨迹段集合记做Tssej，则Tssej={Tsej，Ti‴，j=1，2，3，…，m}，其中Tsej，T‴为T‴在ej上的轨迹段.

3.4 系统流程及算法描述

基于地图匹配和轨迹插点压缩的路网划分的流程图如图1所示，实现过程见算法1.首先，在地图匹配阶段，从路网空间中寻找轨迹点的候选路段集和候选点集.根据公式(3)-公式(5)计算候选点的匹配概率，并使用Viterbi算法进行回溯找到匹配概率和最大的映射序列(参见算法1中1-8行).当相邻两轨迹点匹配至相邻两路段时，根据公式(6)和公式(7)计算出运动对象在两路段交叉点处的行驶速度和时间戳，并插入轨迹中(参见算法1中9-14行).在划分前根据道路节点和车辆在单道路上的行驶方向是否发生变化对轨迹进行压缩，以减少离线训练时参与计算的数据量(参见算法1中15-19行).最后根据插点将轨迹划分至所在路段的轨迹段集合中(参见算法1中20-24行).

图1 路网划分流程图Fig.1 Flow chart of road network division

算法1.基于地图匹配和轨迹插点压缩的路网划分

输入：轨迹T={p1，p2，…，pn}∈TD，其中pi∈T，i∈{1，2，…，n}

输出：匹配后的轨迹T′={p1′，p2′，…，pn′}

划分后的轨迹段Tsej，T‴

1.For eachpi(i∈{1，2，…，n}) inT

2.根据定义3和定义4计算pi的候选路段集和候选点集M

3.For eachmpi，ejinM

4. 根据公式(3)-公式(5)计算mpi，ej的匹配概率MP(mpi，ej)

5. end for；

6.end for；

7.使用Viterbi算法找到匹配概率和最大的映射序列T′

8.end for；

9.For eachpi′ inT′

10.ifpi′满足插点的4种情况

11. 根据公式(6)和公式(7)计算插点pet，ej的速度和时间戳

12.T″←T″∪pet，ej

13.end if；

14.end for；

15. For eachpi″ inT″

16. ifpi″为T″为插点或pi″与pi+1″出现方向的转换

17.T‴←T‴∪pi″

18. end if；

19.end for；

20.For eachpi‴ inT‴for

21. ifpi‴和pk‴分别为T‴在et和ej，ej和es交叉处的插点

22.Tsej，T‴={pi‴，…，pk‴}

23. end if；

24.end for；

4 异常轨迹检测

4.1 离线训练

轨迹划分后，通过挖掘所有轨迹段的时间戳及空间坐标变换信息对路段消耗值进行建模，由Dijkstra算法[8]使用该模型生成路网中所有S-D对的最小消耗路径和最小消耗值.

首先，获取路网中的所有路段，及在每一路段上的轨迹段集合.其次，根据所有轨迹段的信息依次训练出各路段的消耗值.一般情况下，驾驶员在选择驾驶路线时会同时考虑路程的距离和时间需求，因此构建路段消耗函数时，将综合考虑时间和距离的消耗.在计算路段的消耗值前，首先给出轨迹段消耗值的定义.

定义5.轨迹段Ts的消耗值.给定一个轨迹段Ts={p0，p1，…，pk}，其消耗值Tse可定义为：

(8)

给定一个路段e∈E，假设经过划分后，得到e上的轨迹段集合为Tsse={Tse，T1‴，Tse，T2‴，…，Tse，Tl‴}，根据定义5可得e的消耗值为：

(9)

式中：l为e上轨迹段的数量.

依次获取所有路段的消耗值后，使用Dijkstra算法求解路网中所有S-D对间的最小消耗路径和最小消耗值.

给定某一S-D对间所有路段的集合Rss，假设从Rss中得到S-D对间的最小消耗路径为mlS-D=，每一路段的消耗值可由公式(8)计算得到，可得mlS-D的最小消耗值为：

(10)

重复上述步骤直至得到路网中所有S-D对间的最小消耗值.

4.2 异常轨迹检测

当收集到一条新的轨迹数据时，通过地图匹配、轨迹插点、轨迹压缩及路网划分得到当前轨迹分布在不同道路的轨迹段集合.确定该轨迹是否为异常轨迹的过程可以分为以下两个步骤：

1)通过挖掘轨迹的时间戳和空间坐标信息计算该轨迹的消耗值.轨迹划分后得到轨迹段序列，其中每一轨迹段的消耗值可直接由公式(8)得到.则轨迹消耗的定义如下：

对一条新的轨迹T，其从S点出发驶向D点，通过地图匹配、轨迹插点、轨迹压缩得到轨迹T‴，假设由T‴划分得到的轨迹段序列为T‴=，T的消耗值，记做Te，定义为轨迹段序列中所有轨迹段消耗值之和，即：

(11)

其中：Tsej为轨迹段Tsj的消耗值.

2)检测异常轨迹.检测异常轨迹需要一个统一的评估标准(消耗阈值)，最简单直接的方法就是将轨迹消耗值与消耗阈值比较以确定目标轨迹是否异常.

给定对应S-D对消耗阈值φS-D∈消耗阈值矩阵φ，对轨迹T，若其对应轨迹T‴的消耗值Te>φS-D，则T为异常轨迹，反之为正常轨迹.即：

然而，车辆行驶受道路状况的影响极大，在车流量较大时，道路出现堵塞，导致行驶距离较近，但实际行驶时间明显高于路况正常时期.而且，部分司机会主动避开堵塞路段选择行驶时间或距离相对较短的路线代替.因此，在检测异常轨迹时给消耗阈值一个可控的波动范围，以增强算法的容错率.根据公式(10)得到各S-D对的消耗阈值，定义如下：

φS-D=McS-D×γ

(12)

其中：γ为消耗阈值影响因子.

由所有S-D对的消耗阈值可得到消耗阈值矩阵φ.在实验中，动态调整γ的大小，从而找到最恰当的消耗阈值矩阵使异常轨迹的检测结果准确率最高.

4.3 系统流程及算法描述

异常轨迹检测流程如图2所示，挖掘算法1中得到的各路段轨迹段集，获取各路段的消耗值以及路网中各S-D对的最小消耗值，运算过程见算法2.首先，使用时间和距离消耗计算路段上每一轨迹段的消耗值，并通过所有轨迹段的消耗值计算该路段的消耗值(参见算法2中1-4行)；其次，利用Dijkstra算法获取S-D对的最小消耗路径，根据公式(10)计算最小道路消耗值，并根据公式(12)得到消耗阈值矩阵(参见算法2中5-7行)；最后，当一条新的轨迹被收集到时，通过算法1对T进行地图匹配、轨迹插点、压缩和划分，根据公式(8)和公式(11)计算轨迹的消耗值，将其与对应S-D对的消耗阈值进行比较，当消耗值高于相应S-D对的消耗阈值时，认为该轨迹对象为异常轨迹(参见算法2中8-14行).

图2 异常轨迹检测流程图Fig.2 Flow chart of abnormal trajectory detection

算法2.异常轨迹检测

输入：ej的轨迹段集Tssej={Tsej，T1‴，Tsej，T2‴，…，Tse，Tl‴}

S-D对间路段集Rss，测试轨迹T

输出：所有S-D对的最小消耗值MleS-D

消耗阈值矩阵φ；T是否为异常轨迹

1.forTsej，Ti‴inTssej

2. 根据公式(8)，计算Tsej，Ti‴的消耗值Tseej，Ti‴

3. 根据公式(9)，计算路段ej的消耗值

4.end for；

5.使用Dijkstra生成最小消耗路径mlS-D={e1，e2，…，eh}

6.根据公式(10)计算S-D对的最小路径消耗值MleS-D

7.根据公式(12)计算消耗阈值矩阵φ

8.使用算法1对T进行地图匹配、插点、压缩

9.根据公式(8)和公式(11)计算T的消耗值Te

10.ifTe>φS-D(φS-D∈φ) then

11. Return true

12.else

13. return false

14.end if；

5 实验结果及分析

本节使用2007年2月20日来自中国上海的出租车轨迹数据集验证了PC-ATD的有效性和效率.并与TADSS[1]、TRAOD[2]、iBOAT[6]和TPRO[17]进行比较，证实PC-ATD具有改进的性能.

该数据集受限于道路网络，包括大约4000辆出租车的4316条轨迹(约6060079条轨迹点记录)，每个GPS轨道的接收速度约为1次/分钟.考虑到范围跨度大，信息可能存在偏差导致结果精度较低的问题，从数据集中提取了徐汇区范围内的605条轨迹，经切分处理得到1772条时间连续且具有研究意义的轨迹作为最终实验数据进行效果测试，记作TD.

所有实验都是在具有Intel(R)Core(TM)i5-8250U CPU，8GB主内存和以64位Windows 10作为操作系统的工作站上使用真实数据集进行的，该算法在JDK8中实现.

5.1 实验的有效性

为验证PC-ATD的有效性，我们将TD划分为由1329条轨迹组成的训练集和由443条轨迹组成的测试集.对训练集进行离线训练构建道路消耗模型，在轨迹的动态进入中实现异常轨迹的实时检测.

首先，比较位置信息评估算法和PC-ATD算法，以注意结果的不同之处.使用位置信息评估算法时α=1，在测试集中检测到107条异常轨迹.使用PC-ATD算法时α=0.9，β=0.1，γ=1.4，在测试集中检测到65条异常轨迹.与位置信息评估算法相比，PC-ATD算法检测到的异常轨迹数量明显较少.原因在于，位置信息评估只考虑位置属性的变化，人为忽略了驾驶人对时间的考虑，导致将一些距离较远，行驶时间较短满足客户需求，且与正常轨迹差异微小的轨迹错误的归为异常，证明多属性异常评价方法是有意义的.

其次，在不同规模训练集下对PC-ATD进行测试，以注意训练集规模对检测结果的影响，参数设置为α=0.9，β=0.1，γ=1.4.可以观察到随着训练集规模的增大，一些被检测为异常的轨迹被评估为正常.原因是随着数据训练集的不断增大，得到的道路消耗值越接近普遍情况，消耗阈值矩阵中的元素越贴近多数情况，从而检测的准确度越高.

通过地图匹配解决了位置设备获取数据存在的设备误差问题，使轨迹数据的走向严格受限于路网；并通过轨迹压缩减少了后期参与计算的数据量，压缩率达到60%，有效的降低了内存占用率，提高了运算效率.

5.2 参数影响

实验分别以位置信息变化和时间戳变化作为距离消耗和时间消耗的量度，并以路段上所有轨道段的平均消耗值表示相应路段的消耗值，训练路网中所有S-D对间的最小消耗值及消耗阈值矩阵.此过程中涉及到3个影响因子：消耗函数影响因子α，β和消耗阈值影响因子γ.其三者的大小决定了检测结果的准确度.通过动态调整α，β和γ，分别评估了消耗影响因子和消耗阈值影响因子对异常轨迹挖掘准确度的影响，从而确定一组使检测结果更准确的影响因子值.

经过大量实验发现，当设置不同的影响因子时，得到的异常轨迹有所区别，且α和γ越大，检测到的异常轨迹数目越少.其原因在于：1)当α增大时，得到的各道路消耗值越高，得到的各S-D对最小消耗值越大;2)当γ增大时，支撑异常轨迹检测的消耗阈值矩阵中的各元素越大，意味着相同数据搜索范围内，得到的异常轨迹数目越少，当消耗阈值到达一定极限，一些明显异常的轨迹被错误认定为正常.

因地图匹配后轨迹遵循道路走向，绘制图像后出现轨迹间的覆盖，故采用局部数据来体现两者之间的区别(后同).图3显示了在不同组α和β作用下的局部数据检测结果，此时γ=1.4.图4显示了在不同γ值作用下的局部数据检测结果，此时α=0.9，β=0.1.可以发现，当α=0.9，β=0.1，γ=1.4时，整个算法的结果准确度最高且最接近真实情况.由此可知，寻找一组最佳的α，β和γ的值，能够极有效的提高算法检测结果的准确率.

(a) α=0.7,β=0.3 (b) α=0.8,β=0.2 (c) α=0.9,β=0.1图3 参数α和β对算法的影响Fig.3 Influence of parameters α and β

(a) γ=1.2 (b) γ=1.3 (c) γ=1.4图4 参数γ对算法的影响Fig.4 Influence of parameter γ

5.3 算法比较

为验证对道路消耗建模的性能优于从轨迹出发建模的性能，在不同规模的数据集上，使用不同的参数方案，比较了PC-ATD、TRAOD、iBOAT、TPRO和TADSS的性能，测试集规模分别为100、200、400，参数设置见表1.PC-ATD算法需要的初始道路模型由训练集训练得到.

表1 PC-ATD、TRAOD 、iBOAT、TADSS和TPRO的参数设置Table 1 Parameters setting of PC-ATD、TRAOD、iBOAT、TADSS and TPRO

首先，TRAOD只能实现对小规模轨迹数据的检测，需对数据进行过滤，效率较低，且需设置6个参数.在iBOAT和TPRO中，网格大小需多次调整，消耗大量的时间，TADSS直接从轨迹出发建模未考虑道路状况的影响.而PC-ATD可以对大规模的数据集进行检测，且只需要很少的参数调整.其次结果表明，对于同一轨迹数据集，各参数对TRAOD算法运行时间的影响是显著的.但各种参数对PC-ATD运行时间的影响很小.

观察图5可以发现，在初期与iBOAT和TRDSS相比，PC-ATD效率较高，但明显低于TRAOD和TPRO，随着轨迹的不断收集，PC-ATD的效率逐渐超过iBOAT 和TADSS，并存在明显优势.实验证明，PC-ATD的检测结果更准确，且在真实情况下更有效.更重要的是，提出了消耗阈值矩阵的概念，将检测的角度从轨迹本身转移到道路消耗，突破了只能检测同一S-D对之间轨迹的局限，可以实现更大范围的轨迹检测.

(a) 轨迹测试集规模=100 (b) 轨迹测试集规模=200 (c)轨迹测试集规模=400图5 PC-ATD、TRAOD、iBOAT、TADSS和TPRO的效率比较Fig.5 Comparison of experiment efficiency between PC-ATD、TRAOD、iBOAT、TADSS and TPRO

6 结束语

本文提出了一种基于轨迹压缩和路网划分的车辆异常轨迹检测算法，通过地图匹配将位置设备收集到的轨迹数据映射到路网空间，采用轨迹插点确保路网划分后各路段上轨迹段的完整性，并根据插点和车辆在单一路段行驶方向是否改变对轨迹进行压缩，最后对轨迹数据进行训练得到道路消耗模型，实现异常轨迹的实时检测.经过大量实验表明，该算法能够有效检测到数据集中的异常轨迹.将PC-ATD算法扩展到基于分布式计算平台上的分布是下一步工作重点.