第  40 卷  计  算  机  学  报  Vol.40 2017 论文在线出版号  No.30  CHINESE JOURNAL OF COMPUTERS  Online Publishing No.30 ——————————————— 本课题得到自然科学基金(No.61073001）和上海市自然科学基金(No.14ZR1403100）资助.  毛江云，女，1990年生，硕士在读，学生，主要研究领域为移动数据管理和异常检测，手机：18801912037，E-mail: jymao14@fudan.edu.cn.  吴昊，男，1992年生，博士在读，学生，主要研究领域为轨迹计算，E-mail:  wuhao5688@fudan.edu.cn.  孙未未（通讯作者），男，1973年生，博士，副教授，计算机学会(CCF)高级会员（08792S）,  主要研究领域为时空数据处理和分析，E-mail: wwsun@fudan.edu.cn.  路网空间下基于马尔可夫决策过程的异常车辆轨迹检测算法 毛江云   吴昊   孙未未 (复旦大学计算机科学技术学院,  上海  201203)  (上海市数据科学重点实验室,  上海  201203) 摘  要  随着Internet、移动通信、空间定位和LBS技术的发展，越来越多的车辆轨迹被收集，如何从大量的车辆轨迹中高效检测出异常轨迹逐渐引起人们的关注。研究学者提出了许多针对车辆轨迹的异常检测工作，从采用的算法来划分，这些工作被分为三类，基于度量的算法、基于统计的算法和基于监督与半监督学习的算法。然而，三类算法都各自存在不足：第一类的计算量随轨迹数据量的增长而增长，且对于异常特征的刻画不完整；第二类方法严重依赖于历史数据，因此没有办法解决轨迹稀疏问题；第三类需要大量的人工标注。于是本文提出了一套路网空间下基于马尔可夫决策过程的异常车辆轨迹检测算法，总共分为预处理、离线训练和在线检测三个阶段。预处理阶段采用了隐马尔可夫地图匹配算法作为核心算法将原出租车轨迹转化为由路网空间中路段边序列表示的轨迹集合。离线训练阶段采用了马尔可夫决策过程模型对车辆驾驶行为进行建模，深入讨论了模型中路段奖励函数的设计规则，并提出采用无监督的贝叶斯反向增强学习算法配合蒙特卡洛采样算法训练历史车辆轨迹数据学习得到模型参数。在线检测阶段中，实时计算待检测的轨迹的异常度，通过用户指定的异常度阈值判断该轨迹是否为异常车辆轨迹。最后，通过在真实数据集上进行实验，同时实现了iBOAT算法和MEX算法作为对比算法。正确性实验中，本算法在NDCG评测指标中达到了99.3%的正确率；而在算法的运行时间上，本算法的单条轨迹在线检测时间能够做到仅耗时0.012ms，较已有算法提升百倍到千倍的效率。而在稀疏数据下进行结果正确性实验中，在对比算法的效果严重受影响的情况下，本算法依然展现出很强的鲁棒性。在样例分析中可以看到通过本算法计算得到的路段奖励函数数值和对真实驾驶行为的评估高度一致。 关键词  异常检测；轨迹计算；马尔可夫决策过程；增强学习；基于位置的服务 中图法分类号  TP311 论文引用格式：   毛江云,吴昊,孙未未,  路网空间下基于马尔可夫决策过程的异常车辆轨迹检测算法,2017,  Vol.40,在线出版号 No.30 MAO Jiang Yun,WU Hao,SUN  Wei  Wei, Vehicle Trajectory  Anomaly Detection in Road Network via Markov Decision Process, 2017, Vol.40,Online Publishing No. 30 Vehicle Trajectory Anomaly Detection in Road Network via Markov Decision Process MAO Jiang Yun    WU Hao    SUN Wei Wei (School of Computer Science, Fudan University, Shanghai 201203)  (Shanghai Key Laboratory of Data Science, Fudan University, Shanghai 201203) 网络出版时间：2017-03-24 22:42:34网络出版地址：http://kns.cnki.net/kcms/detail/11.1826.TP.20170324.2242.002.html2  计  算  机  学  报  2017年 Abstract  With the bloom of the Internet and the Location-based Services (LBSs) as well as the development of positioning  technologies,  more  and more  vehicles  are  equipped  with  positioning  devices  such  as  GPS  devices, which make it possible to collect and process such an increasing number of trajectory data. It also raises interest for many researchers to study how to effectively detect the anomalies in trajectory database as well as maintain the  efficiency  when  the  data  volume grows larger. This  paper  analyzes  abnormal  vehicle  trajectory  detection literatures at home and abroad and finds that in the current literature, the trajectory  anomaly detection research can be divided into three categories: metric-based approaches, statistics-based approaches as well as supervised and semi-supervised learning-based approaches. However, after making a comprehensive discussion and analysis on  the  correctness  of trajectory representation,  the  performance  on  sparse  data  and  the  feasibility  among  the existing  approaches,  we find  that  these  above  approaches  all  have  disadvantages.  For  the  metric-based approaches, the computation cost will be growing with the increase of data volume. Moreover, they cannot fully characterize  the  trajectory  since  only  distance  and  density  features  are  taken  into  consideration.  The statistics-based approaches highly rely on the historical data which means that the performance will suffer a large drop  when  the  data  sparsity  occurs.  While  the  problem  of  supervised  and semi-supervised  learning-based approaches  lay  on  the  troublesome  and  impractical  manual  annotation. Motivated  by  the  disadvantages  of existing  works,  this  paper  proposes  a  Markov  Decision  Process  (MDP)  based  trajectory  anomaly  detection approach in the road network space, and this architecture can be divided into three phases: preprocessing, offline training and online detection. In the preprocessing phase, a hidden Markov model based approach is adopted to convert the spatial trajectories into the sequence of road segments which are based on the origin and destination. In  the  offline  training  phase,  the  MDP  model  is  adopted  to  model  the  routing  behavior of  drivers. As  for the reward function of road segment, it is delicately designed to fit the anomaly detection in the road network space. And the Bayesian inverse reinforcement learning (BIRL) algorithm along with the Markov Chain Monte-Carlo (MCMC) sampling approach is leveraged to learn the reward function by the historical trajectory data. In online detection  phase,  it  computes  the  abnormal  score  from  the  output  of  the  MDP  model  and  judges  whether  the trajectory is an anomaly based on the threshold given by the user. At last, extensive experiments are conducted by using  real  world  dataset which is  generated from  a  city  called  Porto. In  addition,  two  approaches,  namely iBOAT and MEX are implemented as baselines. The proposed approach of this paper achieves 99.3% for NDCG metric  which  outperforms  the  baselines. What’s more,  the  approach  only  cost  0.012ms  for  online  anomaly detection  while  the  baselines  are  several  hundreds  to  thousands much slower. And  in  the  experiment  of  sparse data,  the  approach  shows  the  strong  robustness  against  data  sparsity  in  contrast  to  the  significant  performance drop of baselines. Finally, the case study further justifies the correctness of the reward function estimated by the model and the modeling for driving behavior. Key words  anomaly  detection;  trajectory  computing;  Markov  decision  process;  reinforcement  learning; location-based services   1  引言   随着移动通信、空间定位和位置服务等技术的不断发展，越来越多的移动对象，尤其是私家车、出租车等车辆，配备了诸如GPS等定位设备，使得人们可以收集和存储更多的车辆轨迹数据。如何快速处理和有效利用大量的车辆轨迹数据以服务于智能交通、智慧城市等领域引发了大量研究人员的兴趣[1,  2]。其中车辆的异常轨迹检测工作，即检测起终点（Origin-Destination，OD）相同的轨迹集合下  “少而不同”[3][4]的轨迹工作，具体而言，这里讨论的异常轨迹是指：①在轨迹集合中相同轨迹数量少，②不同于大部分的轨迹（频数较大的轨迹），也就是说，异常轨迹经过了不同的路段或者顺序不同，生活中的具体例子有如交通事故中肇事方追责问题、监督出租车司机绕路欺诈、城市电子地图更新、人群行为研论文在线出版号  No.30                  毛江云等：路网空间下基于马尔可夫决策过程的异常车辆轨迹检测算法  3 究等，近年来逐渐引起人们的关注。 异常检测工作在数据挖掘中被称为离群点检测问题。离群点是数据集当中少量、显著不同于其他数据点的对象。常见的离群点检测算法大体可以分为基于统计的算法、基于深度的算法、基于距离的算法、基于密度的算法和面向高维数据的算法等[5]。但是车辆轨迹异常检测工作不同于传统的异常检测工作，面临着更大的挑战：①车辆轨迹数据不同于常见的结构化数据，是多维非结构化数据，同时包含空间、时间及其他多维度信息（如速度、角度）；②随着车载定位设备的普及化，车辆轨迹数据与日俱增，呈现出爆发式增长速度，因而积累了海量的历史数据，并且同时还拥有着大量源源不断的实时数据；③车辆轨迹数据在宏观上呈现出海量性特点，但是在微观局部中仍体现出稀疏性问题，尤其是在长距离轨迹情况下。我们通过对葡萄牙出租车数据集进行统计发现轨迹总长度大于15km的轨迹总数只占总数据集的0.7%。这也就意味着，在长距离轨迹情况下，拥有相同行驶路径的车辆轨迹就变得稀少，这个被称为轨迹稀疏的问题是在处理车辆轨迹工作中不容忽视的，特别地，异常轨迹在数据稀疏情况下“少而不同”的特征表现弱，加大了误判的概率。因此针对该问题需要提出一种适用于车辆轨迹的快速、准确性高且能应对数据稀疏的异常检测算法。 目前已有许多针对车辆轨迹的异常检测工作[3-4,  6-15]，它们大致可以分为基于度量的方法，基于统计的方法和基于监督与半监督学习的算法。综合这些方法，都存在以下缺陷： (1)  对于基于度量的方法而言，首先其计算量随着轨迹数据量的增长而增长，其次上述工作只考虑了轨迹的距离、密度等特征，对于异常特征的刻画不完整。 (2)  基于统计的方法则严重依赖于历史数据的支持，当历史数据稀少时直接影响检测结果的正确性。也就是说，该方法没有办法解决轨迹稀疏尤其是数据缺失的情况。 (3)  对于基于监督与半监督学习的算法，不足之处是需要对训练集数据进行人工标注。第一，人工标注的结果因人而异；第二，真实道路网络日新月异，因此标注工作必须持续更新；第三，为了达到良好的效果，大量的人力标注工作是不可避免的。因此基于人工标注的方法不具有实用性。 于是本文提出一套基于路网空间的在线异常车辆轨迹检测算法。在我们的问题中，用概率模型对轨迹进行建模，所以异常轨迹的问题被形式化为轨迹的似然概率。具体地，看到真实生活中驾驶员驾驶的决策行为相似于马尔可夫决策过程，故采用马尔可夫决策过程对驾驶员的驾驶行为进行建模，接着使用无监督的贝叶斯强化学习对历史轨迹数据进行训练学习算法配合蒙特卡洛采样算法学习出路段的潜在开销，进而得到路段之间的转移概率，为异常轨迹检测提供支撑。我们的贡献在于： 1  不同于已有的工作，我们从驾驶行为建模的角度研究轨迹异常，使用无监督学习的方法在路网空间上解决在线车辆轨迹的异常检测工作。 2  利用马尔可夫决策过程以及反向增强学习的方法学习出路段的潜在开销，解决了数据稀疏的问题。 3  结合真实出租车轨迹数据，进行了大量的实验，验证了算法的高效性和鲁棒性。 本文第1节介绍了针对车辆轨迹的异常检测研究现状，第2节对相关工作进行概述，第3节将给出本算法框架的系统概览图，第4节对问题进行描述，并提出异常度的判断标准和马尔可夫决策过程的准确定义，第5节将详细展开技术细节的介绍，包括离线模型学习阶段和在线的异常检测过程，第6节将对所提到的方法进行实验分析，最后，总结全文并展望后续工作。 4  计  算  机  学  报  2017年 2  相关工作 近年来，针对车辆轨迹的异常检测工作取得了长足的发展[3-4,  6-15]，总结已有方法，大致可以分为以下三类：⑴基于距离、密度、误差等信息的基于度量的方法；⑵基于轨迹数量，车流量等信息的基于统计的方法；⑶通过提取和训练轨迹特征信息的基于监督与半监督学习的算法。 第一类基于度量的方法以Knorr和Ng[6]为代表，提出了“离群点”的概念，并提出了借助网格索引将O(kN2)的时间复杂度优化至线性的算法。Ge[7]  基于Dempster–Schafer理论，提出结合距离和密度的模型来识别欺诈出租车轨迹，首先采用独立成分分析方法计算一组轨迹的独立成分，其次计算每条轨迹的coding cost，于是得到了在起始点之间的“最常见路线”，最后只需要计算对应的每条轨迹和这个“最常见路线”的相异度即得到每条轨迹的异常度。而Lee[8]则提出一种基于轨迹划分的异常轨迹检测框架，他们首先将轨迹划分成等长的线段集合，接着采用基于距离和密度混合的Hausdorff距离标准进行检测。Yu[9]提出了一套多参数的分别基于“离群点”和“离群轨迹”的异常检测算法，计算实时流“窗口”（固定长度的子轨迹）中每个采样点的时空近邻点或者轨迹数量的支持度进而判断子轨迹异常与否。 第二类是基于统计的方法。Li等人[10]对比当前数据和历史在时间维度上的发展趋势，构造N的相似向量，N为道路网络路段数量，通过检测趋势的剧变来确定离群路段。Pan[11]等人提出结合车辆轨迹数据和社交网络数据来检测异常并进一步分析引起异常的原因，在检测异常车辆轨迹阶段，以路径模式（routing pattern）为单位计算其车流量的占比比率，通过对比比率的显著变化来检测异常，接着利用社交网络来挖掘分析引起该异常的原因。Zhang[3]则基于异常车辆轨迹“少（few）”和“不同（different）”两个显著特征，提出了基于隔离点的异常轨迹检测系统（iBAT）。该方法首先将空间划分成等尺度的网格，接着把轨迹转换成网格表示的网格序列，最后通过计算网格序列的频度来检测异常轨迹，不过该方法需要多次遍历在海量的历史轨迹数据集，耗时过大；在此基础之上，Chen[4]提出了一套基于隔离点的异常轨迹在线检测系统（iBOAT），解决了iBAT 在线检测和寻找局部异常轨迹的问题。该方法通过对起始点一致的轨迹集合建立倒排索引来索引历史轨迹，接着维护一个k长度的滑动窗口，实时计算窗口中的网格序列的异常值，从而检测出异常轨迹。Lei[12]综合考虑轨迹在空间、时间、行为三个维度的特征，建立异常轨迹检测系统，同样的，他首先将轨迹转化为网格序列，接着构建概率后缀树（PST-Tree）进而检测异常轨迹，不过该方法的处理对象是船舶的轨迹数据，该类轨迹和车辆轨迹的区别在于前者基于欧式空间，而后者则基于路网空间。 第三类是基于监督与半监督学习的算法。Li[13]提出了一套基于分类的异常轨迹检测算法。在该算法中，首先提取出共同模式（被称为motifs），接着这些共同模式组成一个特征空间，轨迹数据继而被转换到特征空间中，形成特征向量，之后可用分类器进行分类，检测出异常轨迹。Liao[14]设计了一套可视化分析系统来检测租车的异常轨迹。他们利用条件随机场建立模型，标注得到异常轨迹，再加上主动学习的场景，即利用用户交互逐步提高他们的模型。Sillito[15]开发出一套增量半监督学习方法来检测异常，他们对已标注的数据和未标注的数据糅合在一起，统一运用分类器分类，而未被标注的数据可以借助人为后期修正后再加入训练以提高模型的准确性。然而该方法处理的对象是视频流数据而非轨迹数据。 论文在线出版号  No.30                  毛江云等：路网空间下基于马尔可夫决策过程的异常车辆轨迹检测算法  5 3  系统概览 本节将介绍我们提出的基于路网空间的在线异常车辆轨迹检测算法，如图1 所示，系统分为三个阶段：预处理、离线训练和在线检测阶段。在预处理阶段，首先采用基于隐马尔可夫模型（Hidden  Markov Model，HMM）的地图匹配算法[16]，将由点序列表示的轨迹转化为由路段边序列表示的轨迹，接着根据相同的起始路段（OD）提取出OD轨迹集。在离线训练阶段，我们使用马尔可夫决策过程（Markov Decision Process，MDP）模型对驾驶行为建模，根据OD轨迹集数据，采用贝叶斯反向增强学习（Bayesian Inverse Reinforcement Learning，BIRL）算法不断训练道路网络中的路段潜在开销函数。而在在线检测阶段，输入一条待检测轨迹，通过离线训练得到的路段潜在开销函数构建的完整的MDP异常检测模型计算得到异常度，配以按需缓存策略的加速，高效地在线给出轨迹的异常度（或根据异常阈值判断异常与否）。 BIRL算法 异常检测异常度地图匹配MDP模型GPS轨迹数据 道路网络OD轨迹集C(e1)C(e2)C(e3)C(e4)C(e7)C(e5)C(e6)C(e8)路段潜在开销函数 待检测轨迹Cache按需缓存策略预处理阶段 离线训练阶段 在线检测阶段 图1 异常车辆轨迹检测系统流程图 4  基本概念 本章将给出详细介绍具体算法细节之前所需要了解的基本定义，概念以及涉及到的算法模型。 定义1.   道路网络（road network）：道路网络（简称路网）G(V,E)是一个有向图，其中V是结点集（即路口），E是边集（即路段）。对于路段eÎE，记e.sÎV为路段的起点，e.dÎV为路段的终点。 定义2.   轨迹（trajectory）：受限于路网空间运动的轨迹T=e1→e2→…→ek由有序的边序列组成，满足相邻边连续性质，即∀i 有ei.d =ei+1.s。 定义3.   问题定义：给定路网G(V, E)，以及轨迹集合T。对于待检测的轨迹T，设计异常检测算法鉴别T是否是异常。 定义4.   最优轨迹：对于给定的起始路段eS，eD，定义其最优轨迹T*为 *{ |  is from  to   } argmax ( | , )sDSDT T e eT P T e e = 即在所有从eS 出发到eD的可能路径中似然（likelihood）最高的轨迹。 定义5.   异常度：定义一条起始路段为eS，eD的轨迹的异常度为 *log ( | , )( ) 1log ( | , )SDSDP T e eTP T e ex =-              (1) 显然有() T x∈[0,1)，当轨迹为最优轨迹时（即T =T*）异常度取到最小值0。对概率加上对数是为了将概率的指数级变化映射到线性级变化。 6  计  算  机  学  报  2017年 定义6.   异常轨迹的判断标准：给定阈值λ，对于一条以eS，eD为起始路段的待测轨迹T : ( )               TTTlxl³ ìí<î则为异常轨迹如果有则为正常轨迹 对于一条轨迹T=e1→e2→…→ek，进行一阶马尔可夫假设的轨迹似然为 ( ) ( ) ( )11 1 1 1 11| | , | , , ,kk k i i kiP T e e P e e e P e e e e-+== Õ ( )1111 , |ki i kiP e e e-+==×Õ                    (2) 需要注意，在概率条件中省略了起点路段e1而保留了终点路段ek。原因是，转移概率P(ei+1|ei)为从路段ei 行驶到路段ei+1的概率，它受终点影响而并不受起点影响。以图2为例，驾驶员在路段ei，如果目的地为( ) 1De，则行驶到( ) 11 ie+的概率更大；若目的地为( ) 2De，那么行驶到( ) 21 ie+的概率更大。而显然，无论起点是在( ) 1Se还是在( ) 2Se ，并不会影响当前的决策。下面将介绍如何使用马尔可夫决策过程和反向增强学习算法对有目标条件限制的转移概率P(ei+1|ei, ek)进行建模。 eD(1)eD(2)eiei+1(1)ei+1(2)eS(1)eS(2) 图2  路段转移示意图 定义7.   马尔可夫决策过程（Markov  Decision Processes，MDP）：MDP1是一个四元组  (S, A, g, R)，其中 Ÿ  S是状态（state）集合。 Ÿ  A是动作（action）集合，定义a(s) Î S为状态s经过动作a后转移到的状态。 Ÿ  g Î[0, 1]是一个衰减系数（discount factor）。 Ÿ : RS R a是奖励（reward）函数，R(s)表示状                                                                 1  MDP可以分为确定性和非确定性，由于在驾驶行为决策中，司机做出了决策后状态的转移确定的，因此本文只讨论确定性的MDP。 态s对应的奖励。 一个MDP 的动态过程如下：某个代理者（agent）的初始状态为s0，最初选择动作a0执行，随后agent转移到了下一个状态s1，故有a0 (s0) = s1。接着再执行动作a1，就转移到了s2，有a1 (s1) = s2。以此类推。如图3 所示，我们得到了过程：0 120 1 2a aas s s ® ® ®L。 请注意，MDP过程中的动作决策满足一阶马尔可夫性，即只取决于当前状态，与前面状态无关。 s0s1s2s3s4a0a1a2 图3  马尔可夫决策过程示意图 定义8.   策略（policy）：记p为一个策略，p是一个SAa的函数，p(s)  = a表示当agent的状态为s时，策略p所给出的决策是执行动作a。 定义9.    值函数（value function）：给定一个策略p，奖励函数R，其对应的值函数为当前状态下的奖励以及未来根据策略决策后得到的奖励之和的期望，即： ( ) ( ) ( ) ( )20 0 1 2 |E V s R R s R s R sp g g p éù = + + +¼ëû ( ) ( ) ( )20 1 2R s R s R s gg = + + +¼ 其中未来的奖励会随时间乘以一个时间衰减项g。本文讨论的是确定性MDP，因此给定初始状态s0和策略p后，之后agent采取的动作以及状态的转移都是确定的，对应式子中的s0、s1、s2 等状态转移的序列是确定的，因此期望记号可以去掉。同时，根据贝尔曼方程可得： ( ) ( ) ( ) 0 0 1| V s R R s V sppg =+ 在所有的策略p中，使得系统中每个状态对应的值函数都能达到最大的策略则为最优策略（optimal policy），也就是说，最优策略p*满足： ( )*arg max    V s s Sppp = " Î 论文在线出版号  No.30                  毛江云等：路网空间下基于马尔可夫决策过程的异常车辆轨迹检测算法  7 定义10.    Q-函数：给定一个策略p和奖励函数R，Q函数是定义在S×A的函数，定义为 ( ) ( ) , | | Q s a R Q s s Rpp=®¢ ( ) ( ) =|R s V s Rpg ¢ +     (3) 为了方便描述，用(s→s')来表示(s, a)二元组，其中s'= a(s)。Q函数的值的意义为，当前状态s（不受限于策略p）通过采取某个动作a之后，依照策略p能够得到的奖励期望。 定义11.    增强学习（reinforcement  learning）：增强学习是智能系统从环境到行为的映射的学习，目的是为了使奖励信号函数值最大化。即给定一个MDP，增强学习的目标是得到最优策略p*，使得agent在任何状态下，根据p*的行动得到的奖励（值函数）是最多的。一般的做法是通过值迭代（value iteration）或策略迭代（policy iteration）来求得最优策略p* [17]。 定义12.    值迭代（value iteration）：值迭代是一种在MDP中求得最优策略的算法，具体算法步骤见算法1。 算法1.  值迭代 输入：MDP M(S, A, g, R) 输出：最优策略p* 1:   FOR s∈S DO 2:         V(s) ← 0; 3:   WHILE  未收敛  DO 4:           FOR s∈S DO 5:                   V(s) ← R(s) + maxa∈AV(a(s)); 6:   FOR s∈S DO 7:           pp (s) ← argmaxa∈AV(a(s)); 8:   RETURN p; 在给定MDP的情况下，值迭代算法不断更新值函数V（第5行），直至值函数V收敛后利用最优策略的定义（第7行）求得每个状态s下的最优策略。可以证明，V一定能收敛2。 定义13.    策略迭代（policy  iteration）：策略迭代                                                                 2 Convergence  of  Value  Iteration  Algorithm, http://www.math.tau.ac.il/~mansour/rl-course/scribe6/node4.html, 1999,12,18 是另外一种在MDP中求得最优策略的算法，具体算法步骤见算法2。 算法2.  策略迭代 输入：MDP M(S, A, g, R) 输出：最优策略p* 1:   FOR s∈S DO 2:         p p (s) ← Random(a∈A); 3:   WHILE 未收敛  DO 4:           V ← Vp; 5:           FOR s∈S DO 6:                   p (s) ← argmaxa∈A V(a(s)); 7:   RETURN p; 策略迭代首先对每个状态随机分配一个策略（第1、2行），之后每次迭代前，先通过求解贝尔曼方程组，根据当前求得的策略p来得到对应的值函数V（第4行），随后对于每个状态s，根据贪婪原则得到新一轮的策略p(s)，再进行下一轮的迭代直到策略p收敛为止。可以证明，p一定能收敛[18]。 需要注意的是，值迭代和策略迭代都是解决MDP的常用方法，并无特别优劣之分。一般而言，在小规模的MDP问题中，策略迭代收敛速度快；而在较大规模的MDP问题中，由于策略迭代需要解线性方程组，因此当状态空间非常大时，解方程组的开销将会变得很大，而此时值迭代方法更适合。 5  基于马尔可夫决策过程的转移概率建模 5.1    驾驶行为与转移概率 我们采用MDP对车辆驾驶行为进行建模。本节主要介绍两者之间的关联性。 具体地，路网中路段集合G.E对应状态空间，驾驶员则对应agent，驾驶员在路口进行的决策（如直行、左转、右转等）对应动作A。车辆在路网上的行驶过程可以认为是状态之间的转移过程，根据常识，在不相邻的路段之间转移是不合法的，因此限制该动作的发生。并且我们认为一个有经验的驾驶员的驾驶过程是经过增强学习后得到了最优的策略，进而采取最优策略的行为。表1总结了MDP中的元素与驾驶行为场景中的对应关系，其中关于8  计  算  机  学  报  2017年 奖励函数将在5.2节中介绍。 表1 驾驶行为与MDP对应关系 MDP元素  驾驶行为场景中对应的元素 状态集S  路段e∈G.E 动作集A  路口决策，决定转移至哪一个路段 奖励函数R  路段潜在开销的负数 使用MDP对驾驶行为建模是合理的，原因是基于MDP的增强学习得到的最优策略具有未来前瞻性（最大化当前与未来得到的奖励），这与驾驶行为是一致的。因为驾驶过程中，驾驶员的决定会结合未来的考量。如驾驶员某时刻的决策是“右转上高架”，做出决策的原因是考虑到这样做后，之后的驾驶体验会较优（如时间较短、道路通畅、红绿灯较少等），这也就是最大化当前与未来得到的奖励的过程。可见，MDP模型非常好地符合了该问题背景。 在最优决策的前提下，agent采取的行为是确定的，而现实生活中，人们的驾驶决策是不确定的，直观上地，人们的决策概率与做了该决策后的预期奖励正相关，即与Q函数正相关。更具体地，如果决策a1的Q函数的值与决策a2的Q函数值非常接近，那么人们选择a1或者a2的概率应该也是非常接近的，因为不论做哪一种决策，带来的预期奖励都是差不多的。因此，在给定奖励函数R的情况下，我们对驾驶员在路段ei 的情况下做出“转移到ej”的概率使用下式表示：      ( )( )*exp ||,( | )ijjiiQ e e RP e e RZ e Rp®=      (4) 为了满足概率定义，分母为归一化因子，即( )( )( )*adj| exp |nii i neeZ e R Q e e RpÎ=®å，  adj(ei)为与ei邻接的路段集合。从(4)式中可以看出，驾驶员做的决策概率与决策对应的Q函数的值成指数正比。需要注意的是，通常可以对目标状态的奖励函数值进行一些特殊的设置（将会在5.2节中进行阐述），诱导最优策略朝向目标状态进行转移。在驾车情形下，奖励函数由驾驶的最终目的地决定，这样驾驶员的决策将会诱导状态向目标状态进行转移。因此随机变量R与目的地路段eD在概率条件中是等同的，所以(4)式可以用于(2)式中的转移概率P(ei+1|ei, ek)的建模，下文将介绍如何计算奖励函数R。 5.2  奖励函数与路段潜在开销 由前文可知，如果MDP的所有元素都已给出，那么最优策略即可求出，对应的Q函数也可以求出，随后也可以根据(4)式求得(2)式中的转移概率而最终得到整条轨迹的异常度。而实际上，我们并不能直接获得MDP中的奖励函数R。本文采用的解决方法是利用机器学习的思想，根据历史数据的分布来自动地学习R，使得模型满足在当前奖励函数下，历史数据的似然最大。 从前文分析可以看出MDP中决定agent的策略的关键因素是奖励函数R和目标状态eD的设置。由第4节对图2中的例子分析可知，在车辆驾驶行为建模的场景下，不同的驾驶目的地在同一路段上对应着不同的路口决策，也即对应了不同的奖励函数。一种简单的方法是，可以直接将历史数据根据不同的目的地分成若干个集合，对每个集合内的数据训练一个独立的奖励函数RD。而这种方法有个严重的问题是，由于实际中状态空间（路段数量）很大，将历史数据根据目标状态进行划分后，每个状态对应的数据集则会变得非常稀疏，这样通过训练得到的奖励函数将会非常不准确。 但是同时，路段的等级、长度、车道数和限速等静态的外部特征往往是和目的地无关的，而驾驶员在进行决策时这些特征实际上起着重要的作用。考虑到这些因素，我们定义每条路段e存在着一定的潜在开销（latent cost）C(e)＞0，该潜在开销对于每条路段而言是一个固定的值，与目标路段无关。对于在同一个路网中的所有不同目标的MDP，除了目标路段以外都共享同样的路段潜在开销。所以，对于一个目标路段为eD的MDP，我们通过以下规则构造对应的奖励函数R ( )( )        DDC e e eReeeì-¹ =í=î如果  0 如果 由于驾驶员的目的是为了最小化开销，也就是说，最大化“负”开销，根据增强学习中的最优策略论文在线出版号  No.30                  毛江云等：路网空间下基于马尔可夫决策过程的异常车辆轨迹检测算法  9 的定义，我们将路段的潜在开销的负值作为路段状态在MDP中的奖励函数。除了目标路段以外的状态，其余对应的奖励都是小于0的，而将目标路段设置为0的原因是，将决策引向目标状态，这是因为如果不朝着目标状态做决策，那么不管如何进行转移，奖励的数值都是负的，只会越转越少。因为对于目标状态eD而言，最优策略p* (eD)应该为留在原地才能使得累计奖励最大化，这样实现了目的地的“吸引”特性，使得值函数不会无穷地计算下去。 C(e1)C(e2) C(e5)C(e4) C(e7)C(e3) C(e6)MDP(towards e1)MDP(towards e2)MDP(towards e7)R(e1)=0 R(e2)=0 R(e7)=0目的地为e1的轨迹目的地为e2的轨迹目的地为e7的轨迹 图4  共享路段潜在开销的驾驶行为建模示意图 如图4所示，虚线平行四边形框内的为路网，每条路段具有一个不变的潜在开销C(e)。对于不同目标的MDP，我们认为这些MDP共享除了各自对应的目标路段以外的奖励函数，即路段潜在开销的负值。将目标路段的奖励置为0则体现了MDP的不同目标的特性。最终，具有不同目标的驾驶员们根据对应的MDP产生了现实生活中的轨迹。 5.3  模型学习 本节将介绍如何学习找到路段的奖励分配方式（即MDP模型的参数R），根据这个路段的奖励分配方式，使得在该方式下生成的估计的概率最贴近真实生活中的轨迹，这样我们就能够利用MDP模型来求得以任何路段为终点的任意两个相邻路段之间的转移概率了。我们采用BIRL算法来完成这一任务[19]，该算法是一种无监督的学习算法，根据一系列由MDP产生的轨迹来学习出MDP中的奖励函数R。具体地，对于一个目标路段为ei 的MDP M = (S, A, g )，其奖励函数Ri 未知，给出根据该MDP产生的若干轨迹集iT，Ri 的后验分布记作( | )ii PRT。根据贝叶斯定律，并将(4)式代入有：     ( ) ( ) ( ) || i i i i i P R P R P R µ TT ( ) ( ) |iiiTP R P T RÎ= ÕT                  ( )( )*1exp | ( | )ijjiiT e T jjiQ e e RPRZ e RTp+Îή= ÕÕ  (5) 在无先验信息的情况下P(Ri)设置为均匀分布。 记真实的奖励函数为Ri，算法估计的奖励函数为 iR%，为了最小化平方误差22i iRR-%，等价于从Ri 的后验分布( | )ii PRT中返回均值  [20]。 由于总数据集是由不同的ei 为目标路段的MDP产生的，而每个Ri 都共享了除了目标路段以外相同的路段潜在开销，因此可以联立所有Ri 的后验分布得到C的后验分布      ( | ) ( | )ii iP C P R TT=Õ                (6) 所以实际上我们想要求得的是路段的潜在开销C，同样地，使用C的后验分布( | ) PCT的均值C%作为C的估计同样可以满足最小化平方误差22CC-%。 直接计算后验分布比较困难，[19]提出了一种基于马尔可夫链蒙特卡罗（Markov  Chain Monte-Carlo, MCMC）采样的方法。MCMC方法可以对一个分布进行采样，当马尔可夫链收敛时，采样出的数据的均值则是分布的均值。算法流程在算法3中有具体描述。首先使用路段的长度作为路段的开销C(e)的初始值且使用负开销作为奖励函数的初始值（第2行）。然后每次采样都从当前C的d-邻域中进行均匀地采样。即对于第t+1次的采样，采样器从[C(t) - d, C(t) + d ]中服从均匀分布地采一次样，得到C'（第5行）。然后根据公式(5)计算轨迹集T中的每条轨迹的似然，并根据公式(6)得到新采样到的路段潜在开销函数C' 的后验概率( ' | ) PCT（第6-10行），服从()( ' | )min 1,( | )tPCPCìü íý îþTT的概率接受C'成为C (t+1)  （第11行），并进行下一轮的采样。当马尔可夫链达到收敛后，采样器采得10  计  算  机  学  报  2017年 的样本（包含接受步骤）将服从目标分布( | ) PCT，此时对最后若干个采样的C样本求其均值（第12行）即可作为目标分布( | ) PCT的均值的一个估计。最后，将开销函数取负数即得到最终的奖励函数R。 采样过程中马尔可夫链的收敛是很难控制和检测的，因此我们将在实验过程中针对不同的步长d 进行实验，找出收敛最快的d 。 算法3. BIRL算法 输入：MDP M(S, A, g)，轨迹集合 输出：奖励函数R 1:   FOR e in G.E DO 2:           C(e) ← e.length,    R(e) ← –C(e); 3:   p ←value_iteration(M, R); 4:   WHILE 未收敛  DO 5:           C’ ~ Uniform[C - d, C + d ]; 6:           FOR T in T  DO   7:                   R' (eD) ← 0; 8:                   p ←value_iteration(M, R'); 9:                   根据(5)式计算P(T| R'); 10:           据(6)式计算计算( ' | ) PCT; 11:           服从概率( ' | )min 1,( | )PCPCìü íý îþTT接受C'成为C; 12:   C%←循环过程中最后得到的若干个C的均值; 13:   R%← –C%; 14:   RETURNR%; 稀疏性问题的解决：由于模型假定了在路网运动的车辆共享统一的路段潜在开销，因此，即使eS, eD距离很远导致历史轨迹稀疏的情况下，我们依然可以通过其他的密集轨迹学习到每条路段的潜在开销C(e)（或R(e)），对稀疏轨迹也能正确地计算出它的似然，从而进一步地判断其是否异常。 5.4  在线检测过程 求得每条路段的奖励R(e)后，对一条终点为eD的待检测轨迹T，算法4给出了检测异常的流程。 算法4.  异常检测在线算法 输入：轨迹T, MDP M(S, A, g),  开销函数C,  终点路段eD 输出：T是否为异常轨迹 1:   FOR ei ≠ eD DO 2:         R(ei) ← –C(ei); 3:   R(eD) ← 0; 4:   p ←value_iteration(M, R)或policy_iteration(M, R); 5:   计算P(T*|eS, eD); 6:   P(T|R) ← 1; 7:   FOR ei in T DO 8:           根据(3)式计算Qp (ei→ei-1|R); 9:           根据(4)式计算P(ei|ei-1, R); 10:         P(T|R) ← P(T|R)×P(ei|ei-1, R); 11:   根据(1)式计算x(T ); 12:   IF x(T ) > lpTHEN 13:           RETURN true; 14:   ELSE   15:            RETURN false; 算法的输入是待检测的轨迹T和终点路段eD，以及对应的MDP和通过历史数据训练得到的路段潜在开销函数C；输出是一个布尔值，标识检测轨迹T 是否为异常。首先将所有的路段的奖励函数R(ei)赋值成训练得到的路段负开销–C(ei)，而单独将目标路段设置为0，从而构建目标状态为目标路段的MDP(第1-3行)。注意到T的似然的计算需要计算Q函数，也就是计算R对应的值函数，因此第4行需要进行值迭代或策略迭代求得值函数。接着使用动态规划算法可求得最优轨迹的概率值（第5行）。6-10行计算待检测轨迹T对应的概率值。第11行通过异常度定义公式计算该轨迹的异常度。第12-15行，根据用户定义的异常度阈值l标识该轨迹异常与否。 注意到，由于每条轨迹需要将对应的终点奖励值设置成0后单独做一次值迭代或策略迭代，如果轨迹条数多的时候，需要每条做轨迹条数次值迭代或策略迭代，这显然会使得时间开销变得非常大。优化方法是首先离线地将每条路段作为终点做好值迭代或策略迭代，并计算每个状态下每个动作对应的值函数与Q函数，并求出状态之间的转移概率并保存下来，进而优化线上判断的过程。或者可以采取“按需计算并缓存”的思路。即每次需要对某个路段作为终点计算对应的MDP的值迭代或者策略迭代时，首先去事先缓存的区域查看是否之前已有缓存，如果有则直接使用之前计算过的结果（因论文在线出版号  No.30                  毛江云等：路网空间下基于马尔可夫决策过程的异常车辆轨迹检测算法  11 为只要两条轨迹的终点是一致的，那么他们对应的MDP的奖励函数也是一致的）；如果事先没有计算过且缓存下来。那么在进行一次值迭代或策略迭代算法计算后将结果缓存下来供之后的数据使用。类似的，第5行最优路径T*的计算也可以利用线下计算或按需计算并缓存的策略进行加速。 6  实验结果与分析 6.1    实验设置 我们使用了葡萄牙波尔多市的公开出租车轨迹数据集3，包含从2013年7月到2014年6月共442辆出租车约3GB的轨迹数据，经过数据清洗与切割后共选取了20 万条轨迹作为实验数据集。轨迹的平均采样率为15s。由于原始的数据是欧几里得空间上的点序列（即经纬度），我们首先采用地图匹配算法[16]，将其映射到路网上从而转化成了边序列。根据引言部分所述，目前iBOAT[4]与MEX[9]是现有的即支持在线地检测异常又是适合于车辆轨迹进行的研究工作。因此我们将iBOAT与MEX算法作为对比方法，由于MEX算法提出了两套不同的异常判别机制，分别是MEX-PN与MEX-TN，因此我们分别对这两种机制都进行了实现。 6.2  异常度实验分析 首先，我们针对该异常值的准确程度进行实验分析。本实验从轨迹数据中抽取若干对起始路段分别为eS，eD，且每对起始路段相同的轨迹集合满足：   1）不少于100条   2）至少有4种不同的轨迹模式 为了方便描述，本文将抽取的起始路段记作  (eS, eD)，并将给定起始路段(eS,  eD)之间的轨迹记为T1, T2, …, Tk（没有重复），每种轨迹在数据集中出现的频数记为F1, F2, …, Fk，不妨规定F1 ≤ F2 ≤ … ≤ Fk。这里假定在数据密集的情况下，一种轨迹经过的次                                                                 3 ECML/PKDD  15:  Taxi  Trajectory  Prediction  (I).     https://www.kaggle.com/c/pkdd-15-predict-taxi-service-trajectory-i, 2015,04,20 数与轨迹的异常程度是正相关的。一个好的轨迹异常检测算法对所有以(eS, eD)为起始路段的不同轨迹的异常度打分得到的降序排序应该与实际中按照轨迹的频数的升序排序是一致的（即异常度越高，轨迹频数应该越低）。因此，我们使用信息检索中常用的NDCG（Normalized DCG）标准对排序的性能进行评测[21]。NDCG是一种比较排序效果的度量标准。它的特点是，对待测算法得到的排序靠前的对象加上较大的权重，而减少靠后的对象权重。对于异常检测问题，NDCG指标对排序靠前的对象更敏感，例如，把实际中频繁的正常轨迹误判为异常，体现在把排序靠后的轨迹置前，这样会带来的惩罚将比把异常轨迹排序的位置置后更高。原因在于，轨迹异常检测的目的在大部分情况下是去除异常轨迹，将正常轨迹误判为异常通常会造成大量频繁正常的轨迹被删除的严重后果，必须要避免这样的情况发生。 具体地，令一个算法对给定(eS, eD)下的不同轨迹根据其计算得到的异常度进行降序排序后得到的轨迹顺序为 12ˆ ˆ ˆ, , ,kT T T L，记( )ˆiRankT为轨迹ˆiT在真实排序下的排名，ˆiT对应的实际的频数记作( )ˆˆiRaiT nkF F=。则有( )1 221log ( 1)rel ikiDCGi=-=+å，其中( )11ˆ ˆlog log(0,1]ˆlogkjjikjjF Frel iF==-=Îåå是相关度的计算函数，轨迹的真实排名越靠后（即频数越高），则对应的相关度越小，反之越接近1。DCG中的分母项2log ( 1) i+则是对排名进行了权重衰减，对靠后的排名，降低其权值，而增加排名靠前的重要程度。记iDCG为真实排序的DCG值，则 [ ] 0,1DCGNDCGiDCG=Î 其中当算法排序与真实排序一样时，NDCG值为1。算法与真实排序差异越大，NDCG值则越低。 在实验数据中，我们根据之前的选取规则，共选出了129对起始路段对，表2展示了四种算法在12  计  算  机  学  报  2017年 这些测试样本下的平均NDCG值和每条测试轨迹的平均的运行时间。运行时间已扣除算法的预处理时间，只计算在线执行的时间。 表2 算法平均性能结果   平均NDCG  平均时间（ms） iBOAT  0.951  474.931 MEX-PN  0.935  31.878 MEX-TN  0.943  7895.88 Ours  0.993  0.012 图5 中每个点的横坐标表示某一个起始路段(eS, eD)里的不重复的轨迹模式数量，纵坐标表示这些轨迹通过算法排序后得到的NDCG值。  图5 密集数据集下的NDCG结果 可以看出，我们的NDCG指数在大部分情况下非常接近1，即我们使用轨迹似然对轨迹的异常度进行打分得到的排序与真实的排序几乎一样，也就是说无论异常度的阈值设为多少，我们的算法都能很好地鉴别异常轨迹，而对比的三个算法它们的NDCG值则有较大的差距。主要原因是，iBOAT是基于网格的方法，有些异常轨迹在局部产生了异常，而这些轨迹却都落在一个或相邻的网格内。iBOAT 是无法发现这类异常的；而MEX-PN/TN两个算法由于涉及到过多参数（如近邻范围、窗口大小、异常点判定数量阈值等等），而这些参数与实际数据密度与分布密切相关，对不同的地方使用同样的参数必然会使得一些场景的效果变差。此外，从图中点的分布趋势可以看出，当(eS, eD)的轨迹模式变多的情况下，差距变小了。其主要原因是，当给定起始路段(eS, eD)的需要排序的轨迹模式很多的情况下，由于NDCG对靠后的排名进行权重衰减，因此即使出现对靠后的排名排序错误的情况，也不会对NDCG有很大的影响。而从数据分布来看，也可以看出，大部分数据的轨迹模式数量还是位于4~40内，因此我们的算法在实际中的优势还是很大的。 在算法性能方面，我们的方法由于不需要扫描数据集中的其他数据，因此效率非常高。而其他三种算法，由于都需要对原始数据集进行扫描，因此效率相比我们要差很多。图6展示了每个测试样本下对比的三个算法的时间开销与我们算法的时间开销的比值，为了便于展示，我们对统计结果根据我们的算法的绝对时间开销进行了升序排序。  图6 密集数据集下的时间开销与本文方法的比值 可以看出MEX-PN在近邻查询中有优化剪枝策略，一旦搜索到满足给定阈值的点的数量则停止搜索，在三个对比算法中最快，但仍比我们的算法慢了2~4个数量级；iBOAT 由于一开始的近邻查询必须需要完全查询，因此比MEX-PN还要慢了1个数量级；而MEX-TN也与iBOAT一样,需要进行完全查询，但是却不像iBOAT 会自动缩小检测窗口，因此更是比iBOAT 慢了1个数量级。三个对比算法在我们算法开销的时间增长的情况下，与我们的差距有所缩小，主要原因是，我们的时间开销是正比于轨迹长度的，也就是说横坐标越靠后轨迹长度越长，而当轨迹很长的情况下，三个对比算法都有对应的剪枝策略起到了作用，因此与我们的差距有所缩小。需要注意的是，我们的模型虽然有训练部分，但是该模块只需要针对历史数据离线训练一次即可，且在在线部分利用缓存优化或按需计算缓存思想加速可以保证在在线检测部分具有很快的论文在线出版号  No.30                  毛江云等：路网空间下基于马尔可夫决策过程的异常车辆轨迹检测算法  13 速度。 6.3  数据稀疏情况下的实验分析 为了观察在长距离历史数据稀疏的情况下异常检测算法是否依旧能具有鲁棒性，我们通过一定规则构造了一些稀疏情况下的测试集。需要注意的是，由于人工标注具有主观性（尤其实验区域在国外），此外能标注的数据量也很有限，因此人工标注不宜实施。相对地，我们设置了一定的规则构造了稀疏且有标记的测试样本。首先，从历史数据中抽取满足以下条件的(eS, eD)对以及对应的轨迹： 1）轨迹不少于100条 2）最短的路径至少经过8个路段 记(eS, eD)中所有轨迹的频数之和为F(eS, eD)。我们将轨迹中频数低于3%×F(eS, eD)的轨迹标记为异常轨迹，将频数高于3%×F(eS, eD)的轨迹标记为正常轨迹。同时，对这些正常轨迹稀疏化，每种只保留3%×F(eS, eD)条。   至此，我们得到了满足（1）长距离（2）有标记（3）稀疏的轨迹数据集了。将构造后的数据集作为异常轨迹检测算法的输入，进行实验。 首先，在稀疏化实验数据中，我们根据异常度实验分析实验的选取规则，同样分析了两个算法在这些测试样本下的NDCG值的分布情况，如图7所示。  图7 稀疏数据集下的NDCG结果 需要注意的是，本实验中NDCG的评测结果没有特别大的影响。原因是，NDCG对评测对象为给定起始路段后的所有不同的路线的排序情况，而在本实验中，给定起始路段，正常轨迹的路线种类是远小于异常轨迹的路线种类的，即使将正常轨迹错误地排在异常轨迹之间，因此对总NDCG的影响并不显著。此外，在稀疏的情况下，我们更需要知道的是正常轨迹是否会被错误地判断成了异常轨迹，因此综合考虑，我们认为用于评判分类标准的ROC曲线更适合用来描述稀疏情况下的评测标准。 我们根据表3统计对应的数量，然后以x轴为FPFPRTN FP=+，y轴为TPTPRTP FN=+，根据不同的预测的阈值l绘制ROC（Receiver Operating Characteristic）曲线[22]。ROC曲线能够体现在不同任务下的泛化性能的好坏，同时也能客观地应对正反例数量不均的情况。一个理想的分类器的ROC曲线应为左上角，一个随机分类器的ROC曲线为对角线。若一个分类器的ROC曲线被另一个分类器的曲线完全“包住”，则可断言后者的性能优于前者。 表3 分类结果混淆矩阵    预测为异常  预测为正常 标记为异常  TP  FN 标记为正常  FP  TN 根据规则，我们从数据中构造了6,165条轨迹用于测试，其中2,215条标记为正常轨迹，3,950条标记为异常轨迹。由于正常轨迹都被减少到了总数量的3%，因此正常轨迹的数量略少于异常轨迹。 图8为两个算法在稀疏情况下对应的ROC曲线。  图8  稀疏数据集下的ROC曲线 可以看出，我们的方法是大幅度优于对比的三种的。原因在于这三种算法都是基于统计的方法，根据轨迹数据集中与待测数据相近的轨迹或轨迹点数量进行判断。而一旦长距离下数据稀疏后，历史数据集中完全相同的轨迹数量非常少，根据这些算法的判断规则，这些轨迹都会被错判成异常轨迹，因而效果急剧变差，退化到了接近随机判断的结果。而我们的方法，虽然轨迹变少了，但是通过14  计  算  机  学  报  2017年 使得每条路段共享同一个潜在开销后，利用其它密集的数据进行训练后，依然能够学习出路段的潜在开销。即使历史数据中不存在与测试的正常轨迹一样的轨迹，依然可以正确地计算出它的似然。 更进一步地，图中长虚线对应的是我们使用未稀疏化的数据集训练得到的结果。通过对比使用稀疏化后的数据和稀疏化前的数据的结果，可以发现即使将部分长距离的频繁轨迹稀疏化后，我们的模型依然能够学习出稀疏化前的效果，这归功于我们模型中提出的开销（奖励）函数的共享机理。即使当长距离下历史轨迹较少，模型可以通过数据量较大的短距离下的轨迹分布情况，学习出路段的潜在开销，并将其共享到长距离的数据稀疏情况下，这也进一步证明了模型的鲁棒性。 6.4  步长选取实验分析 回想5.3节模型学习中，BIRL算法在MCMC采样过程中，每次会对当前的路段潜在开销函数C的d-邻域[C – d, C + d]内进行均匀采样。很明显，d将会直接影响模型学习的收敛速度与效果。 对于BIRL算法中的步长d，我们对该参数的选择进行了实验。我们通过在模型学习过程中记录根据式(6)计算路段潜在开销C相对于数据集中所有轨迹的后验分布，即MCMC采样算法所需要模拟的目标分布( | ) PCT，来观察不同的d下模型的收敛速度。由于概率数据过于小，我们将其对数化后对结果进行观察。我们分别将d设置为了0.1、0.2、0.4和0.8，结果展示在图9中，横坐标为MCMC采样的次数。  图9  训练步长δ与算法收敛关系实验结果图 从图9中可以看出，当d设置为0.1~0.4的时候，算法收敛效果较好，且d设置为0.2与0.4的马尔可夫链收敛速度要略快于0.1的情况，主要原因是最终的C离初始值较远，因此d大的情况下，每一步调整的步伐变大，也更容易达到最优解。同时地，随着d的增大，每次从C的d -邻域[C - d , C + d]中采样后的C’被接受的概率将会变低，且接近最优值的附近时，由于步长变长的原因，更加进一步地接近最优值的难度也加大了，因此d设置为0.2与0.4的时候不如d =  0.1的曲线那么平缓稳定。当d继续变大，设置成0.8时可以看出波动变大，因为每次采样得到的新的C可能接近最优值较远，算法收敛明显变困难。事实上我们也做了1.6~6.4的收敛实验，发现当d > 1.6时，算法已无法收敛。由于如果同时放上1.6~6.4 的结果会对的结果展示产生影响，故未在实验图中展示。 6.5  训练时间实验分析 本实验将分析异常车辆轨迹检测系统的离线训练的时间开销与数据规模的关系。本实验的运行环境为Intel i7-4790 3.6GHz的CPU, 32G DDR3内存，Windows 7系统；使用C++代码在Visual Studio 2015下编译。  图10 BIRL算法每轮采样时间开销与数据规模结果图 图10展示了BIRL算法每轮MCMC采样需要的时间开销与数据规模的关系，我们通过变化训练数据的数量（从5万条到35万条）来观察算法时间开销与数据规模的变化关系。可以看出，随着数据规模的增长，BIRL 算法每轮采样以及计算后验概率所需的时间近似线性增长，这与预想是一致的。因为BIRL算法每轮采样需要计算数据集中所有数据的后验概率，因此时间开销正比于数据的规模。以52 10 ´条轨迹（数据集中约3个月的跨度）为例，由图10可知，BIRL算法的MCMC采样在论文在线出版号  No.30                  毛江云等：路网空间下基于马尔可夫决策过程的异常车辆轨迹检测算法  15 约43 10 ´轮采样后开始收敛，因此约需要43 10 2 3600 16.67 ´ ´ ¸ =小时在一台桌面PC 上即可完成训练，这相对于3个月的跨度而言是可接受的。 6.6  样例分析 为了更好地展示我们的方法的有效性，我们选取了一个样例进行了分析。图11为给定起始路段下（起点路段标记为eS，终止路段标记为eD）数据集中的所有轨迹。 eSeD1 3435异常轨迹1异常轨迹2正常轨迹6异常轨迹1异常轨迹2 图11  异常检测样例 为了说明正常轨迹的频繁特征，我们并未对匹配后的轨迹进行可视化（匹配后的轨迹由于都是边序列，所以可视化后重叠在了一起不容易观察），而是对正常轨迹使用原始采样数据的可视化（即进行地图匹配前，欧几里得空间中的GPS采样点）；而为了研究异常轨迹的路段转移过程，我们对异常轨迹使用匹配到路网空间中的路段进行可视化。其中明显可以看出两条异常轨迹，图中分别标识为异常轨迹1和异常轨迹2。  图12  样例对应的两条异常轨迹的对数转移概率 图12显示了这两条异常轨迹在每个路口采取的行为对应的转移概率（已对数化）。可以看出，对于异常轨迹1，在第一个路口处，绝大部分的历史轨迹都选择了向下行驶，而这条轨迹则选择了右行，从图12中则体现为其第1个路口的转移概率很低。在第3个路口时，向下走能够再次返回正常的路线，而其依然向右直行，对应的转移概率也很低。同样地。对于第4个路口，向下转弯更为合理，而其依然向右直行，其对应的转移概率也很低。第5个路口也同理。在之后的状态下（第6个路口），异常轨迹1的后半部分应该和合理的行驶路线是一样的，对应的对数转移概率也都稳定在0附近。对于异常轨迹2，在第3个路口，其行为（向下）与大部分轨迹（向右）产生了偏差，对应的转移概率也立刻变低。 从此例可以看出，我们使用MDP对驾驶行为的概率建模是非常合理的，使用BIRL对路段潜在开销的学习也是很准确的。此外，我们的方法不仅能够检测出异常轨迹，还能准确定位到所有异常发生的位置。 7  结束语 本文从驾驶行为建模的角度出发，研究异常轨迹，提出一种在路网空间上基于无监督学习解决在线车辆轨迹的异常检测算法。算法利用马尔可夫决策过程以及反向增强学习的方法学习出路段的潜在开销，解决了数据稀疏的问题。并结合真实的出租车轨迹数据，与已有的方法iBOAT对比，我们的方法在一般情况下表现出更高的准确性以及在数据稀疏情况下表现出高效性和鲁棒性。同时通过样例研究更进一步地展示了本文提出的算法的有效性与优越性，为异常轨迹检测工作提供了新的思路。 在接下来的工作中，我们将考虑如何利用时间维度的信息使得模型能够适用于动态变化的道路网络状况，设计一套同时具有动态增量式的异常检测模型。 参 考 文 献 16  计  算  机  学  报  2017年 [1] Song Ying,  Li  Qing-Quan, Zhen  Nian-Bo.  Distributed  Vehicle  Monitor Information Service Platform Based on LBS. Computer Engineering, 2007, 33(06): 242-244 (in Chinese) (宋莺,  李清泉,  郑年波.  基于  LBS 的分布式车辆监控信息服务平台. 计算机工程, 2007, 33(06): 242-244) [2]  Zheng  Yu.  Methodologies  for  cross-domain  data  fusion:  an  overview. IEEE Transactions on Big Data, 2015, 1(1): 16-34 [3] Zhang Daqing, Li Nan, Zhou Zhi-Hua, et al. iBAT: detecting anomalous taxi  trajectories  from  GPS  traces//Proceedings  of  IEEE  13th  International Conference on Ubiquitous computing. Beijing, China, 2011: 99-108 [4]  Chen  Chao,  Zhang  Da-Qing,  Pablo  Samuel  Castro,  et  al.  iBOAT: isolation-based online anomalous trajectory detection. IEEE International on Intelligent Transportation Systems, 2013, 14(2): 806-818 [5] Li  Yan,  Li  Hao,  Qian  Xiao-Lu,  et  al.  A  review  and  analysis  of  outlier detection algorithms. Computer Engineering, 2002, 28(6): 5-6 (in Chinese) (李炎,  李皓,  钱肖鲁,  等.  异常检测算法分析.  计算机工程, 2002, 28(6): 5-6) [6] Edwin  M.  Knorr,  Raymond  T.  Ng,  Vladimir  Tucakov.  Distance-based outliers:  algorithms  and  applications. The  International  Journal  on  Very Large Data Bases, 2000, 8(3-4): 237-253 [7]  Ge Yong,  Xiong  Hui,  Liu  Chuan-Ren,  et  al.  A  taxi  driving  fraud detection  system//Proceedings of  IEEE  11th  International  Conference  on Data Mining. Vancouver, Canada, 2011: 181-190 [8] Lee  Jae-Gil,  Han Jia-Wei,  Li Xiao-Lei.  Trajectory  outlier  detection:  A partition-and-detect  framework//Proceedings of  IEEE  24th  International Conference on Data Engineering. Cancun, Mexico, 2008: 140-149 [9]  Yu  Yan-Wei,  Cao  Lei,  Qin  Wang.  Detecting  moving  object  outliers  in massive-scale  trajectory  streams//Proceedings  of  the  20th  ACM  SIGKDD international  conference  on  Knowledge  discovery  and  data  mining.  New York, USA, 2014: 422-431.   [10]  Li  Xiao-Lei,  Li  Zhen-Hui,  Han  Jia-Wei,  et  al.  Temporal  outlier detection  in  vehicle  traffic  data//Proceedings  of  IEEE  25th  International Conference Data Engineering. Shanghai, China, 2009:1319–1322. [11]  Pan  Bei,  Zheng  Yu,  David  Wilkie,  et  al.  Crowd  sensing  of  traffic anomalies  based  on  human  mobility  and  social  media//Proceedings  of  the 21st  ACM  SIGSPATIAL  International  Conference  on  Advances  in Geographic Information Systems. Orlando, USA, 2013: 344-353 [12]  Po-Ruey  Lei.  A  framework  for  anomaly  detection  in  maritime trajectory  behavior.  Knowledge  and  Information  Systems,  2016,  47(1): 189-214 [13] Li  Xiao-Lei,  Han  Jia-Wei,  Sangkyum  Kim,  et  al.  ROAM:  rule-and motif-based  anomaly  detection  in  massive  moving  object  data sets//Proceedings of  the  7th  SIAM International  Conference  on  Data Mining. Minnesota, USA, 2007: 273-284 [14] Liao  Zi-Cheng,  Yu  Yi-Zhou,  Chen  Bao-Quan.  Anomaly  detection  in GPS  data  based  on  visual  analytics//Proceedings of  IEEE Symposium  on Visual Analytics Science and Technology. Salt Lake City, USA, 2010: 51-58 [15]  Sillito  R  R,  Fisher  R  B.  Semi-supervised  learning  for  anomalous trajectory detection//Proceedings of the British Machine Vision Conference. Leeds, UK, 2008: 1-10 [16] Song Ren-Chu, Lu Wei, Sun Wei-Wei, et al. Quick map matching using multi-core  CPUs//Proceedings  of  the  20th  International  Conference  on Advances in Geographic Information Systems. Redondo Beach, USA, 2012: 605-608 [17]  Sutton  R  S,  Barto  A  G.  Reinforcement  learning:  an  introduction. London, UK: MIT Press, 1998   [18]  Manuel  S.  Santos,  John  Rust.  Convergence  properties  of  policy iteration.  SIAM  Journal  on  Control  and  Optimization,  2004,  42(6): 2094-2115. [19]  Ramachandran  D,  Amir  E.  Bayesian  inverse  reinforcement  learning// Proceedings  of  20th  International  Joint  Conference  on  Artificial Intelligence. Hyderabad, India, 2007: 2586-2591 [20]  Berger  J  O.  Statistical  decision  theory  and  Bayesian  analysis. New York, USA: Springer, 2013 [21]  Järvelin  K,  Kekäläinen  J.  Cumulated  gain-based  evaluation  of  IR techniques.  ACM  Transactions on  Information  Systems,  2002,  20(4): 422-446 [22] Tan P N, Steinbach M, Kumar V. Introduction to data mining. Boston, USA: Pearson Addison Wesley, 2006            MAO  Jiang  Yun,  born  in  1990,  M.S. candidate. Her research interests include mobile  data  management  and anomaly detection.   WU Hao, born in 1992, Ph.D. Candidate. His research interests focus on trajectory computing.  SUN  Wei  Wei, bron  in  1973,  Ph.D.,  associate  professor.  His research  interests  include spatial-temporal  data  processing  and analysis.  Background This  paper  is  mainly  focused  on  the  field  in  the  research on  detecting  the  anomaly  trajectory  given  its  origin  and destination  information  based  on  the  road  network.  This  field belongs  to  a  classical  problem  in  the  field  of data  mining, called outlier detection. Outlier is regarded as a data object that is grossly different  from or inconsistent with the remaining set  论文在线出版号  No.30                  毛江云等：路网空间下基于马尔可夫决策过程的异常车辆轨迹检测算法  17 of  data.  And  there  have  already  many  outlier  detection algorithms  reported  in  the  literature. Despite  its  importance,  it is  until  Knorr  tried  his  first  attempts  in  1998  that  anomaly trajectory  detection  attracted  attention  of  the  public. Previous studies  in  detecting  anomaly  trajectory can  be  classified  into three  methods: utilizing  distance  or  density  of  trajectories  to detect  anomaly,  directly  or  indirectly  doing  statistics  on  the number of trajectories, transforming trajectories into the feature space to compute their “distance” through model and then classifies  the  normal  ones  and  anomaly  ones.  However,  as already stated in the previous paper, they have some limitations such  as  suffering  low  efficiency,  lacking  in  specification  and failure to handle data sparsity problems. Motivated  by  this,  we  propose  an  abnormal  vehicle trajectory  detection  algorithm  in  road  network  space  via Markov  decision  process  model. Our  approach  supports returning  the  degree  of  abnormal  and  even  is  able  to  find  out exactly  where  the  abnormal  behavior  occurs.  We  conduct comprehensive  experiments  via  real  world  taxi  trajectory dataset. The results show that our approach outperforms current work not in both efficiency and effectiveness  when the dataset is dense. We also conduct  experiment  with respect  to long-trip data  sparsity,  the  result  again  justifies  the  robustness  of  our approach. This paper offers an extensive view on detecting anomaly trajectory,  and  we  also  provide  a  new  perspective  that  will  be helpful to the future researches on this field.