基于轨迹大数据离线挖掘与在线实时监测的出租车异常轨迹检测算法

王伟 谭松荣

摘要：本文探讨了异常轨迹检测算法的理论概述，对此类检测算法进行了研究，通过分析出租车异常轨迹的框架，在一定程度上验证了检测算法的有效性和高效性。

关键词：轨迹大数据;离线挖掘;异常轨迹;检测算法

中图分类号：TP311.13 文献标识码：A 文章编号：1007-9416（2018）12-0118-02

1 异常轨迹检测算法的理论概述

所谓轨迹其实就是一种时空数据的类型，它是通过记录移动对象的历史位置所形成的，而异常轨迹就是指一些没有按照预期的模式出现的表现形式，轨迹的异常检测的方法主要有分类检测法、历史相似性检测法、距离检测法以及网格划分检测法四种。

（1）运用分类检测法可以将其分成两个阶段进行检测，根据收集到的大量的轨迹数据，在移动的路径当中提取出与位置相关的motif等移动的特征，再对其轨迹进行检测，构建出一个数据的分辨率的视图，可以有效对不同维度和不同粒度的轨迹特征进行分析，最终达到检测的目的。但是由于数据是一直在更新产生的，所以分类检测法并不能对轨迹流进行在线的异常检测。（2）历史轨迹相似性的检测法是通过对历史的轨迹进行收集，建立一个全局的特征模型，然后利用全局特征模型中的数据对异常的轨迹进行检测，如果不考虑轨迹数据的变化速度，基于历史轨迹相似性的异常检测方法往往能够提供比较精确的检测数据，所以这类检测方法经常运用与航海和路网交通中。（3）距离检测方法就是将轨迹的数据进行集中，其中与大多数的轨迹不同且距离比较远的轨迹就是异常轨迹，它的目的主要在于及时发现在某一个时间段内的异常移动的对象，比较强调轨迹本身的异常行为。（4）网格划分检测方法是指在划分的大小相同的网格的城市路網当中有效识别出异常的网格单元。网格划分检测方法中的iBat检测算法能够对出租车异常轨迹进行识别，可以及时对出租车司机进行绕路或者欺骗的行为进行揭示，但是目前此类检测方法的检索效率和方式还有待完善，才能充分发挥出网格划分检测方法的作用。

2 出租车异常轨迹的检测框架

2.1 准备数据和预处理

（1）对数据进行准备。文本通过对西安市的历史的出租车轨迹数据进行收集，将8867辆出租车的GPS的数据作为检测的样本，并对数据进行处理，对一些频率间隔不稳定以及定位不再西安市本地的数据进行剔除，再将剩余的数据进行编号，保证数据的可靠性。（2）对数据进行预处理。轨迹数据往往会因为环境和仪器产生故障的因素，会出现缺失、重复GPS的记录数据的现象，并且如果传送的频率发生的异常，其定位的范围就会超出所要研究的城市，所以就会产生一些异常的数据，这些异常数据严重影响了运算的结果，因此要提前对数据进行预处理，有效去除有问题的数据。对数据进行预处理可以通过对异常的数据进行分析，过滤掉状态为熄火和防劫、频率过高或者过低、经纬度范围不在西安市、缺少或者重复等的数据，并对一些数据进行识别，然后再用oracle作为数据库，将text格式的数据导入建立的表空间内，然后再使用sql的语句对数据进行处理。

2.2 提取出有效的载客轨迹

通过提取出有效的载客轨迹可以提供出有效的轨迹数据，帮助异常检测工作能够顺利进行，载客轨迹的提取是将预处理后的数据进行排序，将车牌号和时间作为排序的基础，并把一辆车在一个时间段之内变化的状况作为检测的线索，然后生成一个有效的OD表，才能有效提取出载客的轨迹数据。

2.3 将轨迹数据与地图相匹配

对出租车进行异常轨迹检测时，可以先将出租车的轨迹数据绘制在相对应的电子数据上，如果一辆出租车没有异常的轨迹运动，那么尽管它没有完全在道路上，但是它的总体的行驶趋势还是会跟道路相似。并且如果想要数据发挥出它的有效性，就要在进行异常轨迹的检测之前对数据进行校正，让轨迹数据能够真正的与地图相匹配。通过在车辆指挥中心接收到车辆在行驶过程中的GPS位置信息，设计科学、合理的模型和算法，有效将车辆目前正在行驶的位置与电子地图上的位置相连接，最终让车辆的具体位置出现在电子地图的道路上，这就是地图匹配，目前已经有很多种方法能够实现车辆的GPS位置信息能有效与路网的信息相关联起来，比如多权值的地图匹配方法等。

3 基于轨迹大数据挖掘的出租车异常轨迹检测

由于GPS数据具有随机性、特殊性、数据大量等特点，所以现在还没有很好能够应用在实际生活中的异常轨迹的检测，并且轨迹的不同的表达方式在很大程度上影响了轨迹异常检测算法的准确率和效率，所以对轨迹的表达方式进行研究，表达唯一的路口序列形式，在一定程度上降低轨迹数据的复杂性，并能对异常轨迹进行有效的实时监测[1]。

3.1 收集西安市的相关数据

根据西安市的经纬度的范围，对西安市的电子地图的数据进行下载，其中主要的信息有路段的信息和路口的信息，然后在提取相关的路口序列，有效利用几何相交的原理将提取的路段信息和路口信息进行处理，所以可以得到23064个路口的信息和31114的路段信息。

3.2 对异常轨迹检测的简单的算法

所谓简单的算法其实就是指将一些即将检测的轨迹上的每一个轨迹的点与历史中的轨迹进行对应检查，从中找出比较异常的轨迹点，然后再充分根据相关的数据确定轨迹发生异常的片段和程度，其主要的算法是：通过输入相关的轨迹数据集Ts，待测的轨迹Ttest以及阈值δ，然后依照公式for i=1：n do，来计算出每一个轨迹点会发生的轨迹的概率P（i），再将P（i）与阈值相比较，输出发生异常的轨迹点，再将发生异常的轨迹点连接，使其组成异常的轨迹片段，计算出其长度，最后再与阈值进行比较，就可以得出异常的轨迹数值。

简单的异常轨迹检测算法的复杂程度和轨迹的数目都成正比，并且每一条轨迹都必须要与全部的轨迹数据库进行匹配，所以此类方法的算法空间和时间的复杂度都是比较高的。并且简单的异常轨迹检测算法是对部分的轨迹进行检测，避免了对全局的轨迹空间进行检测，所以在很大程度上提高了异常轨迹检测方法的精度和速率。

4 结语

随着科学技术的不断发展，带动了智能终端的发展，并且由于我国许多城市的出租车都出现了绕路的欺骗行为，所以检测出租车异常轨迹的检测方法的出现是必然的趋势，此类检测方法通过对历史的出租车行驶的轨迹进行收集，并对其数据进行预处理，可以有效分析出出租车在行驶过程中出现的异常轨迹行为，并且能够根据分析出的结果，有效对乘客进行反馈以及向有关的管理部门发送通知，规范出租车司机的行为，保证出租车行业能呈现良好发展的态势。

参考文献

[1]韩博洋，汪兆洋，金蓓弘.一种基于轨迹大数据离线挖掘与在线实时监测的出租车异常轨迹检测算法[J].中国科学技术大学学报，2016，46（3）：247-252.

Taxi Abnormal Trajectory Detection Algorithm Based on Off-line Mining of Large Trajectory Data and On-line Real-time Monitoring

WANG Wei， TAN Song-rong

（Tianyi Ai Music Cultural Technology Co.， Ltd. ， Guangzhou Guangdong 510180）

Abstract：In this paper the theory of abnormal trajectory detection algorithm is discussed， and this kind of detection algorithm is studied， By analyzing the framework of abnormal taxi trajectory， the effectiveness and efficiency of the detection algorithm are verified to a certain extent.

Key words：large trajectory data; off-line mining; abnormal trajectory; detection algorithm