一种基于长短记忆模型的交通轨迹异常挖掘模型

秦胜君　李婷

摘  要：针对现有异常轨迹检测方法没有捕捉轨迹数据时序特征，不能有效识别业务异常和新型异常等问题，提出基于长短记忆模型的异常轨迹挖掘模型.首先通过优化长短记忆模型进行轨迹预测，然后基于进化理论将预测轨迹转化为异常轨迹，从而构建了基于长短记忆模型的异常判别模型.该模型可以有效地识别业务异常和新型异常，提高了异常检测的精准度和可扩展性，同时适用于无标签数据，解决了传统神经网络必须应用于有监督学习的问题.最后通过与改进的密度聚类算法和马尔科夫过程的对比实验验证了该模型在交通轨迹异常检测的优越性.

关键词：长短记忆模型;异常轨迹;交通大数据;深度学习

中图分类号：TP273;U491  DOI：10.16375/j.cnki.cn45-1395/t.2021.02.010

0引言

随着传感器网络和无线通信等新兴技术的不断发展，越来越多的轨迹数据被收集和保存，轨迹数据挖掘有助于找出移动对象隐藏的模式信息或行为意图[1].异常轨迹数据挖掘是指识别隐藏在正常轨迹数据中的异常轨迹.异常轨迹不同于噪声点，噪声点会干扰挖掘工作，降低结果的有效性，而异常轨迹可能预示着有趣事件的发生，比如公共安全中的突发事件、交通事故、高速逃费行为等，从而具有更高的研究价值[2].

根据实现方法的不同，异常轨迹检测方法可以分为4类：基于聚类的检测方法、基于网格的检测方法、 基于分类的检测方法、基于统计學的检测方法.

基于聚类的检测方法是使用密度聚类、模糊聚类等方法，发现远离主体轨迹的少部分轨迹.例如，文献[3]先对轨迹进行切分分组，然后使用密度聚类方法找出异常轨迹.何明等[4]提出改进密度聚类与模式信息挖掘的异常轨迹识别方法，结合上海市与北京市出租车轨迹进行实验，验证了该算法的有效性.

基于网格的检测方法是将城市路网划分成均等大小的网格单元，从而识别出异常的网格单元序列.主要的实现方法有基于似然比统计量的检测方法[5]和基于隔离机制的异常检测方法[6].也有学者提出路网空间下基于马尔科夫决策过程的异常轨迹检测方法[7].

基于分类的检测方法是使用有监督的分类方法识别正常轨迹和异常轨迹.如俞庆英等[8]提出基于BP神经网络的异常轨迹检测方法.Li等[9]使用支持向量机进行特征学习，该方法可处理高维特征空间的异常检测.

基于统计学的检测方法是应用统计学相关理论进行异常检测.例如，安计勇等[10]提出一种多因素异常检测集成算法.首先通过统计数据分布给每种特征赋予一个异常分值，然后利用组合函数对分值集成，由此进行最终异常检测.汪霜霜等[11]研究了一种车辆轨迹学习自适应稀疏重构方法，以识别一场车辆运动模式.

综上所述，异常轨迹领域已有很多研究成果，为数据挖掘和智能交通提供了重要的理论基础和应用支撑.但是上述研究存在以下两个问题：1）基于聚类或分类的方法都没有考虑时序问题，交通轨迹是时序数据，分析轨迹时序有助于提高异常检测有效性;2）业务异常问题，现有的方法大多是根据历史数据中正常轨迹和异常轨迹的距离来判断是否异常，但是并没有考虑过业务异常问题，因此无法有效识别业务异常.为解决上述问题，本文提出基于长短记忆模型的异常轨迹检测方法.首先优化长短记忆模型预测下一阶段轨迹，在已预测出的轨迹数据中进行特征值的变异从而形成异常轨迹，再将正常轨迹和异常轨迹输入神经网络模型进行训练，最终形成基于长短记忆模型的异常轨迹检测方法.该模型解决了传统算法在识别业务异常时需要大量有标签数据的问题，并且在异常检测时加入变异因子，提高了模型在识别新型异常时的有效性.

1相关定义

车辆行驶轨迹本质是多属性的时间空间点序列，聚类等方法是使用距离来判别异常，该方法可以有效地判别数值异常，也就是在数值上偏离大部分轨迹的异常轨迹，而无法判断业务异常. 比如高速路上大货车的行驶轨迹，两段路程中车辆载重变化在核定载重范围内浮动都属正常，但是速度变化过大则有可能是超速，属于异常事件，因此不能仅仅以两条轨迹的距离来判断是否异常，以非线性的判别方式更符合需求.

1.1   轨迹基本定义

轨迹数据集中包含多辆车的多条轨迹.假设车辆轨迹数据集[CTD={CT1， CT2， …， CTi， …， CTn}]，[i=0， 1， …， n].每辆车的轨迹数据集合可以表示为：[CTi={Ti1， Ti2， …， Tij， …， Tim}]，[j=0， 1， …， m].单条轨迹[T]又包含相关特征，表示为：[Tj=（pj1， pj2， …， pjs， tj）]，[t0

轨迹[T]包含地理位置、速度、平均速度、时长、载重等相关特征.

1）地理位置：该特征表明车辆的行驶路线，可能是车辆所在的经纬度，也可以是车辆的出发地点.地理位置标志着车辆在运动空间内的位置移动情况.

2）速度：速度指的是在某个时刻车辆的行驶速度，一般是使用GPS等设备采集.

3）平均速度：该特征表示在某一段时间内车辆运行的平均速度.

4）时长：表明车辆从轨迹的出发点到某个位置的行驶时长.

5）载重：表示车辆所载重量.比如高速路上货车的载重量是判断异常的指标之一;出租车是否载人也有助于判断出租车轨迹是否异常.

除上述特征之外，还有加速度、转角等可用于识别轨迹异常，根据实际情况不同，可选择不同的特征.

1.2   异常相关定义

文中根据轨迹异常情况不同，将异常分为数值异常和业务异常.

1）数值异常

数值异常（data anomaly，DA）也可称为线性异常，指与正常轨迹的距离超过某个阈值的异常轨迹.可如下定义：

[Ti-Ta≥Av]  （1）

式（1）中：假设[Ti]为正常轨迹，[Av]为设定的阈值，[·]为距离度量，可以是欧式距离或者Hausdorff等距离度量方式.如果两条轨迹满足式（1），则[Ta]为数值异常轨迹.

在实际业务中，有可能出现距离度量无法判别异常轨迹.例如一辆货车在高速公路的正常行驶轨迹为120 km/h，载重20 t，该轨迹可表述为（120，20）.假如轨迹变换为（120，40），没有超出载重范围，因此该轨迹仍然为正常轨迹，但是如果轨迹变为（140，20），则被认为是超速，视为不安全驾驶行为，由此该轨迹检测为异常轨迹.虽然上述假设的两条轨迹与原始轨迹的距离一样，但是前者为正常，后者为异常.文中将此类异常定义为业务异常.

2）业务异常

业务异常（business anomaly，BA）也可称为非线性异常，指正常轨迹和异常轨迹经过某个非线性函数映射为指定值，例如1或者0.文中设置1为异常值，而0为正常值.于是，业务异常可定义如下：

[F（Ta）=1]，[F（Ti）=0]（2）

式（2）中：[F]为非线性函数;[Ti]为正常轨迹.如果满足式（2），则[Ta]为业务异常轨迹.

识别业务异常类似于分类算法，但是和分类不同之处在于，一方面异常数据大多是无标签数据，而且异常数据量较少.另一方面，业务异常是从数值上变换而来，通过业务分析也可以捕捉到业务异常，此方法比有监督的分类算法更灵活，更适合于快速变换的数据模式.由于业务异常分析比分类或数值异常更复杂，因此需要进行深入研究，建立有效的异常判别模型.

2异常挖掘模型

本文首先将轨迹点[（T1， T2， …， Ti-1）]输入到长短记忆模型预测出轨迹[Ty]，[Ty]是[Ti]的预测轨迹，然后在轨迹[Ty]基础上加入变异因子生成异常轨迹[Ta]，再将正常轨迹[Ti]和异常轨迹[Ta]输入到逻辑回归模型中进行异常检测训练，最终构建了基于长短记忆模型的异常判别检测框架.

2.1长短记忆模型

长短记忆模型（long short term memory，LSTM）是循环神经网络（recurrent neural network，RNN）的扩展.RNN不同于传统神经网络之处在于其输入和输出序列之间的映射过程中利用了上下文相关信息.RNN是由输入层、一个隐含层和一个输出层组成，展开之后的结构如图1所示.

由图1可知，[x]是输入向量;h是隐含层，该层其实是多个节点，节点数与h的维度相同;[U]和[V]分别表示输入层和隐含层的权重矩阵;[o]表示输出层的值.从RNN的结构可看出，隐含层h的值不仅取决于当前的输入[x]，还取决于上一次隐含层的h值.权重矩阵[W]为上一次隐含层的值作为这一次的输入权重.可以用以下公式来表示RNN的计算方法：

[st=f（Uxt+Wst-1）]   （3）

[ot=g（Vst）]   （4）

式（3）、式（4）中：[g]和[f]都是激活函数.从以上公式可以看出RNN的输出值受前面历次输入值的影响.但是RNN存在着梯度消失或梯度爆炸等问题[12]，为解决上述问题LSTM诞生了[13].

LSTM通过设计记忆单元保存历史信息，记忆单元包括输入门、遗忘门、输出门等主要部分[14].LSTM可以選择遗忘或更新记忆单元存储的信息，由于LSTM考虑输入对应输出之间的时间滞后性，使得该网络可以处理和预测时间序列中间隔和延迟相对较长的重要事件.LSTM关键的扩展是使自循环的权重视上下文而定，而不是固定的.

LSTM通过设计“门”的结构来遗忘或增加信息到细胞状态的能力.门是一种让信息选择式通过的方法，其包含一个sigmoid函数和一个pointwise乘法操作.Sigmoid层输出[0，1]之间的数值，描述每个部分的通过量.0表示不许任意量通过，1表示允许任意量通过.

由于车辆轨迹具有变换性，比如经过很长一段时间直线行驶之后转弯，因此轨迹数据带有一定的不平衡性.为避免轨迹预测时偏向大类数据，本文提出对LSTM模型优化，在原有的结构中加入变换门，从而提高预测精度.优化之后的结构如图2所示.

2.2   异常挖掘模型

LSTM可以保存历史信息，获取时间序列的特征，因此，使用LSTM进行轨迹预测有助于提高预测结果的精确度.假设[（T1， T2， …， Ti-1， Ti）]为某辆车的行驶轨迹，Lstm为长短记忆模型，[Ty]是[Ti]的预测轨迹，则预测模型可表示如下.

[Ty=Lstm（T1， T2， …， Ti-1）]   （13）

在预测轨迹的基础上对轨迹进行变异形成异常轨迹.轨迹变异的思想主要来源于进化算法，与进化算法不同之处在于，进化算法是为寻找最优解，而文中的变异相对较为简单，其目标是获得不同于正常轨迹的异常轨迹.

假设s为轨迹的特征数，则每次随机选择m个特征进行变异，其中[m≤s/3].假设[pi]为被选中的特征之一，[1≤i≤m]，[pmin]和[pmax]分别为该特征的最小值和最大值.则[pi]的变异过程如下：

首先设定一个超参数[λ∈[0， 1]]为变异因子，表示变异的幅度，[λ]越大则变异幅度越大，反之越小.随机生成一个数[θ∈{-1， 1}]，如果[θ=-1]，随机生成某个数[a]，使得[0

[pia=pi+θ·a]（14）

将所有被选择的特征进行变异之后，则生成了异常轨迹，然后再训练分类算法，文中选用神经网络作为异常判别算法.在训练时，如果正常轨迹和异常轨迹共同输入到判别算法中，结果应该为异常值1.如果是正常轨迹和正常轨迹，结果是0.如 式（15）所示.

[σ（Ta， Ti）=1]，[σ（Ty， Ti）=0]  （15）

式（15）中：[Ty]是预测轨迹;[Ta]是根据预测轨迹变异之后的轨迹;[Ti]是真实轨迹.如果满足式（15），则[Ta]为异常轨迹.整个异常检测训练模型的结构图如图3所示.

模型训练完成之后，在实际应用时，首先对轨迹进行预测，然后将预测的结果和真实轨迹输入到异常判别模型中，如果结果为1，则说明真实轨迹为异常轨迹，否则为正常轨迹.

3实验和结果分析

为了验证模型的适应性和有效性，本文对所提出的基于长短记忆模型的异常检测模型进行了实验分析.该模型的开发环境是Python 3.5，操作系统是Windows 10.实验的硬件环境为：CPU为Intel（R）i5-4590@ 3.30 GHz，内存是12 G.

3.1   实验数据集

经过相关部门的同意，本文将使用GPS采集到的货车轨迹数据集作为实验数据.总共采集到450台货车的运行数据，每台车大概有2万～5万条行驶记录不等，经过数据处理之后，可用的轨迹记录约为1 100万条.每条记录中包括车辆编号、经度、纬度、速度、时间、载货量、行驶公里数等特征.

3.2   性能评价指标

异常检测的最终目标是提高少数类（异常数据）的判别结果，因此，将正类作为异常样本，而负类作为正常样本.表1为二分类的混淆矩阵.

使用召回率（R）、假阳率（FPR）、精确率（P）和F1值作为算法性能的评价指标.前三者衡量的是算法判别正样本的性能，而F值是精确率和召回率的调和平均.其计算方式分别如下：

[R=TPTP+FN][FPR=FPFP+TN]

[P=TPFP+TP] [F1=2PRP+R]

3.3   结果分析

文中随机选择了350辆车的数据作为训练样本，100辆车作为测试样本.首先通过实验验证了模型的性能，然后对本异常检测方法和聚类进行了性能比较.实验的步骤如下：

1）数据进行归一化处理，然后将训练样本输入LSTM.本实验中将模型可记忆的长度设置为10，也就是每10条轨迹预测一次轨迹.

2）LSTM训练完成之后，使用LSTM进行轨迹预测，然后将预测轨迹进行变异产生异常轨迹，把预测轨迹和真实行驶轨迹合并成训练样本的负类，把预测轨迹和异常轨迹合并成训练样本的正类，并放置于异常检测模型的训练样本中.

3）建立神经网络作为异常判别模型.该网络的输入节点个数为12，输出节点的个数是1，训练该网络直到结果达到预期精度.

4）模型训练完成之后，将测试样本输入到LSTM模型，得到预测轨迹，再把真实轨迹和预测轨迹合并成一个测试样本输入到异常判别模型，得到测试结果，测试结果的值是0或1，1表示真实轨迹是异常轨迹，0则是正常轨迹.

图4表示随着变异因子的变化，异常轨迹识别的精确度和召回率的变化.

由图4可知，随着变异因子的变大，判别模型的召回率（R）和精确率（P）都在逐渐增大.精确率在变异因子λ=0.5时，便达到了0.820，之后缓慢增加，在λ=1.0时，精确率最大P=0.927.召回率整体略低于精确率，但是在λ=0.4之后，增长的速度高于精确率，召回率同样也是在λ=1.0时达到最大值0.890.假阳率（FPR）随着λ的变大而变小，主要是λ变大之后，FP值变小.FPR在λ=0.6之后，减小的速度变缓，最后FPR值可達到最小0.040.整体来看，模型在λ=0.8时便可以取得较好的性能，之后速度变缓.从实验结果可以看出，变异因子越大，模型的精确度越大，并逐渐稳定.主要是由于变异因子过小，和正常轨迹差距较小，不利于检测出异常轨迹;而变异因子变大，被构建的异常轨迹的范围变大，因此，更能有效地检测出异常轨迹.

本文分析LSTM判别算法的性能，还将该算法与改进的密度聚类算法（DBSCAN）[4]以及马尔科夫决策的异常检测算法（MDP）进行性能比较，图5和图6分别表示3种算法在数据异常（DA）和业务异常（BA）上的表现.

从实验结果可以看出，对于数据异常（DA），3种算法性能评价值结果相近，改进的DBSCAN稍好一些，精确度达到92.2%，然后是马尔科夫过程的异常检测算法，而LSTM算法稍微落后一下，但是整体差异并不明显.但是对于业务异常（BA），DBSCAN算法接近于崩溃，精确度只有68.7%，各种性能都无法达到要求;MDP算法比DBSCAN稍好一些，精确度达到78.2%;表现最优异的是LSTM模型，该模型的精确度并没有受到影响，仍然达到了90.6%.由此表明，在3种算法中，本文提出的LSTM异常判别模型对于业务异常具有较优的性能，主要是由于该模型并不是直接使用距离来判别异常轨迹，而是通过逻辑回归模型来判别异常.

除上述实验之外，本文在数据中加入3%的新型异常，即在已有数据中没有出现过，但是在未来有可能出现的异常，由此对比3种算法的可扩展性.实验结果如图7所示.

从图7可以看出，对于新型异常，LSTM仍具有较好的表现能力，性能上都要优于另外2种算法.其次是密度聚类算法，精度仍然可以达到80.3%.基于马尔科夫过程的异常检测算法表现最弱，精度只有69.5%.

文中提出的LSTM异常判别模型能有效识别业务异常的原因在于应用随机变异的方式，使模型可以识别出非线性异常，同时也跳出只能识别历史数据异常的范围，可以有效判别新型异常.聚类算法一般使用距离或其他测度去判别异常，适合查找数值异常，在查找业务异常时性能较低.马尔科夫过程在识别业务异常时比聚类算法稍好一些，但是马尔科夫过程也需要在历史数据基础上找到转移概率，使得马尔科夫过程识别新型异常时表现较弱.从整体上看，本文提出的LSTM异常判别模型在识别业务异常和新型异常时具有较好的优势.另外，该模型可应用于无监督数据，比传统的BP神经网络异常识别方法应用范围更广.

4结语

交通轨迹是具有时间序列特征的数据，而长短记忆模型能有效地捕捉数据的时序特征，提高预测的精确度.本文结合优化的长短记忆模型和进化算法，通过长短记忆模型预测移动对象的轨迹，然后将轨迹变异为异常轨迹，最后训练异常判别模型，解决异常模型训练时无标签问题，同时提高模型对识别业务异常的有效性.通过实验证明，本文提出的LSTM异常判别模型在识别业务异常时具有较高的精准率和召回率，而且可以有效识别新型异常，表明该模型具有较好的扩展性和适应性.该模型不足之处在于没有考虑轨迹数据的空间变换问题，有待于进一步深入研究.

参考文献

[1] 刘良旭，乐嘉锦，乔少杰，等.基于轨迹点局部异常度的异常点检测算法[J].计算机学报，2011，34（10）：1966-1975.

[2] 毛嘉莉，金澈清，章志刚，等. 轨迹大数据异常检测：研究进展及系统框架[J].软件学报，2017，28（1）：17-34.

[3] BIRANT D，KUT A. ST-DBSCAN：an algorithm for clustering spatial-temporal data[J].Data & Knowledge Engineering，2007，60（1）：208-221.

[4] 何明，仇功达，周波，等.基于改进密度聚类与模式信息挖掘的异常轨迹识别方法[J].通信学报，2017，38（12）：21-33.

[5] PANG X L，CHAWLA S，LIU W，et al. On mining anomalous patterns in road traffic streams[C]//International Conference on Advanced Data Mining and Applications，2011.DOI：10.1007/978-3-642-25856-5_18.

[6] ZHANG D Q，LI N，ZHOU Z H，et al. IBAT：detecting anomalous taxi trajectories from GPS traces[C]//13th International Conference on Ubiquitous Computing， Beijing，China，September 17-21，2011.DOI：10.1145/2030112.2030127.

[7] 毛江云，吴昊，孙未未.路网空间下基于马尔科夫决策过程的异常车辆轨迹检测算法[J].计算机学报，2018，41（8）：1928-1942.

[8] 俞庆英，李倩，陈传明，等.基于BP神经网络的异常轨迹检测方法[J].计算机工程，2019，45（7）：229-236.

[9] LI X L，HAN J W，KIM S. Motion-alert： automatic anomaly detection in massive moving objects[C]//Proceedings  of the International Conference on Intelligence and Security Informatics，San Diego，CA，USA，May 23-24， 2006.DOI：10.1007/11760146_15.

[10]   安计勇，朱猛，翟靖轩，等.轨迹多因素异常集成检测[J].计算机工程与设计，2015，36（10）：2700-2705.

[11]   汪霜霜，李春贵. 一种lp正则化改进的车辆轨迹学习算法[J].广西科技大学学报，2019，30（2）：53-60.

[12]   HOCHREITER S.The vanishing gradient problem during learning recurrent neural nets and problem solutions[J].International Journal of Uncertainty， Fuzziness and Knowledge-based Systems，1998，6（2）：107-116.

[13]   SCHUSTER M，PALIWAL K K.Bidrectional recurrent neural networks[C].IEEE Transaction on Signal Processing，1997，45（11）：2673-2681.DOI：10.1109/78.650093.

[14]   張洪刚，李焕.基于双向长短时记忆模型的中文分词方法[J].华南理工大学学报（自然科学版），2017，45（3）：61-67.

An anomaly detection algorithm for traffic trajectory data based on long short term memory model

QIN Shengjun， LI Ting

（School of Economics and Management， Guangxi University of Technology， Liuzhou 545006， China）

Abstact： An abnormal trajectory detection method based on Long Short Term Memory model is  proposed to solve the problem that the existing anomaly detection algorithm can't capture the timing characteristics of trajectory data， and can't effectively identify business anomalies and novel anomalies. In this paper， Long Short Term Memory model is used to predict trajectory which can improve the prediction accuracy， then the predicted trajectory is transformed into an abnormal trajectory based on the theory of evolution. Finally， an anomaly discrimination model based on Long Short Term Memory model has been constructed. The proposed model can effectively identify business anomalies and new types of anomalies， and improves the accuracy and scalability of anomaly detection. At the same time， the model is suitable for unlabeled data and solves the problem that traditional neural networks must be applied to supervised learning. In the end， comparative experiments with the improved densityclustering algorithm and Markov process verify the superiority of the model in detecting abnormal traffic trajectory.

Key words： long short term memory; abnormal trajectory; traffic big data; deep learning

（责任编辑：黎  娅）

收稿日期：2020-10-21

基金项目：广西高校中青年教师科研基础能力提升项目（2019KY0373）资助.

作者简介：秦胜君，博士，副教授，研究方向：交通大数据、数据挖掘、复杂网络，E-mail：shengjun_2012@foxmail.com.