基于加权极限学习机的异常轨迹检测算法

李威龙，范新南，2，李 敏，郑併斌

（1.河海大学物联网工程学院，常州213022；2.江苏省输配电重点实验室，常州213022）

基于加权极限学习机的异常轨迹检测算法

李威龙1，范新南1，2，李 敏1，郑併斌1

（1.河海大学物联网工程学院，常州213022；2.江苏省输配电重点实验室，常州213022）

针对现有异常轨迹检测中分类不平衡造成难以确定最优分类面的问题，提出一种基于加权极限学习机（ELM，Extreme Learning Machine）的异常轨迹检测算法。该算法采用加权ELM克服轨迹数据不平衡造成的分类面偏移，通过对正、负两类样本合理分配权重，并构造最优分类面获得较好的异常检测效果。仿真实验表明，加权ELM算法在训练速度，准确率，整体性能等方面均优于传统SVM和BP网络分类方法。

异常检测；迹轨分析；极限学习机

1 引 言

目前，基于轨迹的异常事件分析已成为一个令人关注的研究课题，针对异常轨迹检测，传统分类器和相似性度量的方法被许多学者应用。较早的有Johnson等［1］采用矢量量化（VQ）表示轨迹和多层神经网络识别分类的方法；Stauffer等［2］将量化后的轨迹矢量依据同现矩阵分析进行分类。近年来，Lee等［3］提出TRAOD（TRAjectory Outlier Detection）算法，轨迹分段表示作为局部特征，并使用Hausdorff距离的不匹配性分离异常轨迹。Claudio Piciarelli等［4］提出采用（单）一类支持向量机的无监督学习方法实现异常轨迹的检测，获得较好的检验准确度。还有Li等［5］使用分类器的思想，提出基于motifs模块化的异常检测算法，获得了较好的泛化能力。

通常异常轨迹检测研究中所需解决的基本问题是，如何在大量复杂轨迹数据中找出少量具有异常特征的轨迹。然而异常轨迹特征具有时空稀疏性以及复杂性（通常表现为高维特征）的特点，容易导致算法复杂度增加、检测结果准确性和鲁棒性降低等问题［6］。

传统分类器对所有样本均赋予固定的正则化参数C，这表示对正负样本的决策分配相同的权重。然而对于非平衡数据的处理，如包含极少异常的大量轨迹数据，则是一个典型的不平衡分类问题，极易导致分类曲面的偏移或者过拟合现象，因而无法取得较好的分类（识别）效果。

极限学习机（the extreme learning machine，ELM）是一种较新的机器学习方法，相比较传统的分类器，如支持向量机（SVM），BP神经网络等，具有更快的学习及更好的分类性能［7］。从轨迹（样本）数据的不平衡性出发，提出了一种基于加权极限学习机的异常轨迹检测算法，并能自适应分配权重。最后通过与其它方法的比较和分析，表明了该算法的准确性和优越性。

2 ELM算法原理

极限学习采用单隐层前馈神经网络（SLFN）框架，给定N个训练样本（xi，ti），含有L个节点的标准SLFN模型可以表示为

式中G（x）为隐层节点的激活函数，βi为第i个节点与所连接输出神经元的输出权值，（ai，bi）为第i个输入神经元的输入权值和偏置，Oj为第j个输出神经元的实际输出值。

存在一个（ai，bi）和βi，有，使得该SLFN模型可以零误差逼近样本集｛（xi，ti），i＝1，...，N｝，即

公式（2）可以合并成为下面矩阵式

其中隐层输出矩阵为

不同于BP神经网络，在训练过程中极限学习机的初始权值随机设置不需要调整，只需解出输出权值最小二乘范数解即可。而根据Bartlett的理论［8］，前馈神经网络的输出权值范数越小，网络的泛化性越好。因此需要在最小化输出权值和最小化误差之间做出折中，则构造如下公式

类似最小二乘支持向量机，该最优化问题可用公式表示成

其中ζi＝［ζi，1，...，ζi，m］T是训练样本xi在第m个输出节点的输出值与真实值之间的误差向量。而C为正则化参数，它是用来权衡经验风险和结构风险的惩罚因子，可以通过设置来防止过拟合，达到更好的分类效果。

由隐层输出矩阵H的Moore-Penrose广义逆矩阵Hτ，可得解，其中T＝［ti，...，tN］。

综上可知，ELM算法的训练步骤为：

Step1：随机设置输入权值和偏置（ai，bi）i＝1，...，N

Step2：计算隐层输出矩阵H

3 加权ELM的异常检测

这里提出一种基于加权（极限学习）的改进方法，对于不平衡的两类样本给予不同的权值W，于是极限学习机算法的求解公式（6）就变成了如下形式

其中W是定义的一个N×N对角矩阵，每一个主对角元素wii都对应着一个样本xi，不同类别的样本将会自动分配不同的权值。

根据KKT条件，可以定义lagrange函数求解该二次规划问题，则等效为求解下面的公式：

其中αi为lagrange乘数，且都是非负数。相应的KKT优化限制条件为

对于异常检测，属于二分类问题，ELM只需要一个输出节点，则决策函数为f（x）＝sign（h（x）β），即：

此外，权值矩阵W＝diag｛wii｝，i＝1，...，N的计算在该加权ELM中十分重要，它直接影响了最后的分类效果。这里在考虑计算复杂度和分类效果的同时，对轨迹异常检测选择了一种简单有效的方法，就是根据两类样本的数量比来分配不同的权值。

T为总样本个数，posx为正样本个数，权值矩阵W计算的伪代码如下

4 实验与分析

4.1 数据集描述

为了验证该算法的有效性，以仿真轨迹数据与真实视频数据进行仿真实验。首先，选用AVIRES Lab的轨迹生成器［9］来创建仿真轨迹数据集。轨迹数据分为训练集和测试集，每个数据集包含正常轨迹和异常轨迹：如260条轨迹中，250条正常轨迹可分为5类，另10条为异常轨迹。每条轨迹由空间特征点组成，坐标作为特征向量值，以形式αi＝［x（1），...，x（trlen），y（1），...，y（trlen）］存储，trlen表示轨迹长度，这里选取16个采样点。

真实视频来自Central Florida大学的KNIGHT目标跟踪监控系统［10］。训练集的数据从183mins的实时监控视频中获取，共997条轨迹。测试集截取了其中15mins的视频信息，共287条轨迹。视频中记录了所有移动目标的轨迹，包含如行人横穿马路，踩踏草坪，测试人员曲线行走等异常轨迹信息。每条轨迹都是等时隙采样，以空间坐标向量的形式存储。

4.2 仿真轨迹实验

图1显示了在一次人工轨迹数据上的实验结果。首先分别产生260个训练样本和260个测试样本，训练集和测试集包含250条正常轨迹和10条异常轨迹，正常轨迹分为5个类别。采用带有权值的极限学习机，普通的无权极限学习机，SVDD算法和BP网络算法分别进行识别，识别结果如图1所示。

图1中灰色表示正常轨迹，大致可看出分成5簇，代表5类正常轨迹集合，黑实线表示正确识别的异常轨迹，黑虚线表示被错误识别为正常的异常轨迹（漏检轨迹）。从中可以看出，采用了加权极限学习机（ELM）算法进行检测，异常轨迹全部被正确的检测出来，而采用其他算法进行检测分别都有误判，与正常轨迹较为接近的异常轨迹被错误识别为正常轨迹，表明了分类面偏移造成不理想的结果。

表1给出了该算法在不同轨迹数据集上的测试结果，并与其他算法的检验结果进行了对比。从表中可以看出，对于异常轨迹检测这种不平衡数据的检测识别，采用了加权算法的效果要明显好于其他传统分类算法。

表1 加权ELM和SVDD、BP网络在几种异常轨迹的检测中准确率对比

4.3 真实视频数据实验

以上仿真轨迹数据实验表明了此算法的优越性，下面通过对真实视频数据的检测验证该算法的有效性。测试数据集如图2所示，分为训练集和测试集，在固定监控场景下，所有样本轨迹用青色表示。

对于真实轨迹的实验，为了后续异常检测的效果，一般需要对原始轨迹数据进行预处理。首先采用等距映射（Isomap）算法提取轨迹中的有用信息，将轨迹的尺寸进行规范化处理，给与分类器一个合适的输入空间。然后将提炼后的数据集进行训练，分别采用带有权值的极限学习机和普通的无权极限学习机进行识别比较。

如图3所示，灰色表示正常轨迹，黑实线表示识别出的异常轨迹，黑虚线表示被误判为异常的正常轨迹。结果表明该算法不仅可以识别出明显偏离正常运动规律的异常轨迹，而且还可以挖掘出具有一定隐蔽性、局部偏离正常的异常轨迹。因此，加权ELM对于异常检测具有一定的现实意义。

图1 各种算法效果比较

图2 轨迹数据

图3 加权ELM与普通ELM的效果比较

5 结论

异常轨迹检测对智能化事件分析具有重要的意义。该算法将加权极限学习机算法引入了轨迹分类中，通过对权值的合理分配，克服传统分类器中构造分类面偏移的缺点。最后通过人工数据和真实数据的对比测试，验证了该算法的有效性和优越性，具有一定的潜在应用价值。

［1］N Johnson，D Hogg.Learning the distribution of object trajectories for event recognition［J］.Image Vis.Comput.，1996，14（8）：609-615.

［2］C Stauffer，W Grimson.Learning patterns of activity using realtime tracking［J］.IEEE Trans on Pattern Anal.Mach.Intell.，2000，22（8）：852-872.

［3］JG Lee，J Han，X Li.Trajectory Outlier Detection：A Partition-and-Detect Framework［C］.Proc.of the 2008 IEEE 24th Intl.Conf.on Data Engineering（ICDE），2008：140-149.

［4］C Piciarelli，Christian Micheloni，Gian Luca Foresti. Trajectory-Based Anomalous Event Detection［J］.IEEE Trans on Circuits And Systems For Video Technology，Novernber，2008，18（11）：1544-1554.

［5］X Li，JHan，S Kim.Motion-Alert：Automatic Anomaly Detection in Massive Moving Objects［C］.Proc.of the 4th IEEE Intl.Conf.on Intelligence and Security Informatics（ISI），2006：166-177.

［6］M Gupta，Jing Gao，Charu C.Aggarwal and Jiawei Han.Outlier Detection for Temporal Data：A Survey［J］.IEEE Trans on Knowledge And Data Engeering，January，2013，25（1）：1-20.

［7］Huang G B，Zhou H，Ding X，et al.Extreme learning machine for regression and multiclass classification［J］.Systems，Man and Cybernetics，Part B：Cybernetics，IEEE Transactions on，2012，42（2）：513-529.

［8］P L Bartlett.The Sample Complexity of Pattern Classification with Neural Networks：The Size of the Weights is More Important than the Size of the Network［J］.IEEE Trans on Information Theory，1998，42（2）：525-536.

［9］Claudio Piciarelli.Matlab Trajectory Generator［DB／OL］.Available：http：／／avires.dimi.uniud.it／papers／trclust.

［10］Arslan Basharat.Tracking Dataset［DB／OL］.Available：http：／／eecs.ucf.edu／～arslan／surveillance.

Trajectory Outliers Detection Algorithm Based on Weighted ELM

LIWei-long1，FAN Xin-nan1，2，LIMin1，ZHENG Bing-bin1
（1.College of Internet of Things Engineering，Hohai University，Changzhou 213022，China；2.Jiangsu Key Laboratory for Power Transmission and Distribution，Changzhou 213022，China）

It is difficult to find the optimal separating hyperplane caused by imbalance classification of the existing trajectory outlier detection algorithm，this paper proposes an algorithm to detect trajectory outliers bymeans ofweighted extreme learningmachine（ELM）.This algorithm adopts theweighted ELM to overcome the offset of separating hyperplane.Firstly，proper weight is set for positive and negative samples adaptively，and then the optimal separating hyperplane is constructed to get better effect for abnormal detection.The results of simulation experiments show that，in training speed，accuracy and overall performance，the weighted ELM algorithm is better than the traditional SVM and BP network classification method.

Outliers detection；Trajectory analysis；Extreme Learning Machine

10.3969／j.issn.1002-2279.2014.01.021

TP391

：A

：1002-2279（2014）01-0076-04

李威龙（1987-），男，江苏高淳人，硕士研究生，主研方向：信息获取与处理。

2013-11-05