路网空间下基于马尔可夫决策过程的异常车辆轨迹检测算法

发布时间：2018-10-09 10:22

【摘要】：随着Internet、移动通信、空间定位和LBS技术的发展,越来越多的车辆轨迹被收集,如何从大量的车辆轨迹中高效检测出异常轨迹逐渐引起人们的关注.研究人员提出了许多针对车辆轨迹的异常检测方案,从采用的算法来划分,这些方案被分为三类:基于度量的算法、基于统计的算法和基于监督与半监督学习的算法.三类算法都各自存在不足:第一类的计算量随轨迹数据量的增长而增长,对异常特征的刻画不完整;第二类严重依赖历史数据,因此没有办法解决轨迹稀疏问题;第三类需要大量的人工标注.该文提出了一套路网空间下基于马尔可夫决策过程的异常车辆轨迹检测算法,该算法总共分为预处理、离线训练和在线检测三个阶段.预处理阶段采用了隐马尔可夫地图匹配算法作为核心,将原出租车轨迹转化为由路网空间中路段边序列表示的轨迹集合.离线训练阶段采用了马尔可夫决策过程模型对车辆驾驶行为进行建模,深入讨论了模型中路段奖励函数的设计规则,并提出采用无监督的贝叶斯反向增强学习算法配合蒙特卡洛采样算法训练历史车辆轨迹数据学习得到模型参数.在线检测阶段中,实时计算待检测的轨迹的异常度,通过用户指定的异常度阈值判断该轨迹是否为异常车辆轨迹.最后,在真实数据集上进行实验,同时实现了iBOAT算法和MEX算法,并作为对比算法.正确性实验中,该算法在NDCG评测指标中达到了99.3%的正确率;在算法的运行时间上,该算法的单条轨迹在线检测时间能够做到仅耗时0.012ms,较已有算法提升百倍到千倍的效率.在稀疏数据下进行结果正确性实验,在对比算法的效果严重受影响的情况下,该算法依然展现出很强的鲁棒性.在样例分析中可以看到通过该算法计算得到的路段奖励函数数值和对真实驾驶行为的评估高度一致.
[Abstract]:With the development of Internet, mobile communication, space location and LBS technology, more and more vehicle tracks are collected. How to detect abnormal tracks efficiently from a large number of vehicle trajectories has attracted more and more attention. Researchers have proposed a number of anomaly detection schemes for vehicle trajectories, which are divided into three categories: metric based algorithm, statistical based algorithm and supervised and semi-supervised learning algorithm. Each of the three algorithms has its own shortcomings: the first type of computation increases with the increase of the amount of track data, and the characterization of abnormal features is incomplete; the second type is heavily dependent on historical data, so there is no way to solve the problem of sparse trajectory. The third category requires a large number of manual annotations. In this paper, a set of abnormal vehicle trajectory detection algorithms based on Markov decision process in road network space is proposed. The algorithm is divided into three stages: preprocessing, off-line training and on-line detection. In the preprocessing stage, the hidden Markov map matching algorithm is used as the core, and the original taxi track is transformed into the track set represented by the edge sequence in the road network space. In the off-line training stage, the Markov decision process model is used to model the driving behavior of the vehicle, and the design rules of the road section reward function in the model are discussed in depth. An unsupervised Bayesian backstepping learning algorithm combined with Monte Carlo sampling algorithm is proposed to train track data of historical vehicles to obtain model parameters. In the on-line detection phase, the anomaly degree of the track to be detected is calculated in real time, and the abnormal degree threshold specified by the user is used to determine whether the track is an abnormal vehicle trajectory or not. Finally, the experiment is carried out on the real data set, and the iBOAT algorithm and the MEX algorithm are implemented simultaneously, and used as the contrast algorithm. In the correctness experiment, the accuracy rate of the algorithm is 99.3% in the NDCG evaluation index, and in the running time of the algorithm, the online detection time of the single track can only take 0.012 ms, which improves the efficiency by 100 times to 1000 times compared with the existing algorithm. Experiments on the correctness of the results are carried out under sparse data. When the effect of the comparison algorithm is seriously affected, the algorithm still shows strong robustness. In the sample analysis, it can be seen that the value of the road section reward function calculated by the algorithm is highly consistent with the evaluation of the real driving behavior.
【作者单位】：复旦大学计算机科学技术学院上海市数据科学重点实验室
【基金】：国家自然科学基金(61772138) 上海市自然科学基金(14ZR1403100)资助
【分类号】：TP181

【相似文献】