一种卡口车辆轨迹相似度算法的研究和实现

樊志英

摘 要： 依据车辆轨迹相似度在时间和空间维度上的约束，引入LCSS算法，遵循最长公共子序列的原理，抽象出轨迹中的卡口号序列，提出一种两条车辆轨迹相似度的计算方法，并结合Spark并行计算、Hive数据仓库存储等相关技术，搭建数据分析平台，实现该算法。实验表明，该算法满足实际车辆轨迹在时间和空间上的相似性，数据分析计算在性能上可以满足前台业务的检索。该算法和轨迹相似度分析业务，可作为治安卡口应用系统中关联车辆分析、团伙作案车辆分析等功能的后台支撑业务。

关键词： 轨迹相似度； LCSS算法； Spark； Hive

中图分类号： TN911?34； TP311.5 文献标识码： A 文章编号： 1004?373X（2016）23?0133?03

Research and implementation of a vehicle trajectory similarity algorithm

used for security access monitoring

FAN Zhiying

（First Research Institute of the Ministry of Public Security of PRC， Beijing 100048， China）

Abstract： According to the constraints of time and space dimensions of the vehicle trajectory similarity， the LCSS （longest common subsequence） algorithm is proposed. According to the principle of longest common subsequence， the access monitoring sequences in the trajectory are abstracted. A calculation method of two vehicle trajectories similarity is proposed. The Spark pa?rallel calculation， Hive data warehouse storage and other correlation technologies are combined to establish the data analysis platform， and implement the algorithm. The experimental results show that the algorithm can satisfy the time and space similarity of the practical vehicle trajectory， and the data analysis and calculation can meet the search performance of foreground business. The algorithm and trajectory similarity analysis business can be used as the background support service of the vehicle relevance analysis and gang crime vehicle analysis in the security access monitoring application system.

Keywords： trajectory similarity； LCSS algorithm； Spark； Hive

0 引 言

随着城市经济的快速发展，各地机动车保有量迅速增加，与车辆相关的刑事和治安案件也在逐年上升，除了传统的违法涉案车辆的缉查管控外，基于重点车辆的行驶轨迹和出行规律分析等业务也将为侦查破案提供有力的依据。

随着治安卡口、电子警察等应用系统的建设和使用，各地已积累了大量的车辆通行记录和违法记录，这些记录中涵盖了车牌号码、经过时间、车辆颜色、车辆类型、行驶方向、行驶状态等车辆信息，为开展车辆出行规律分析等业务提供了强大的数据支撑。

本文使用某地区已有的大量车辆通行记录，结合大数据相关技术，对车辆轨迹和轨迹相似度进行分析和实现，该方案可作为治安卡口应用系统的车辆数据分析的实现思路，为其提供业务支撑。

1 车辆轨迹相似度计算

车辆轨迹相似度分析业务指的是计算指定车辆和其他车辆的行驶轨迹，分析出与指定车辆具有相似轨迹的多个车辆的通行记录，进而为治安卡口应用系统的关联车辆、团伙作案车辆等功能提供后台业务支撑。

车辆轨迹相似度分析分别在时间和空间维度上进行了限制，首先，其他车辆与指定车辆经过同一个卡口的时间要在一定范围内，如2 min以内；其次，其他车辆与指定车辆经过多个卡口的顺序要一致，一致性越高，相似度越高。

3 结 语

本文依据卡口车辆轨迹相似度在时间和空间维度上的约束，提出了一种轨迹相似度的计算方法，并结合大数据相关技术对该算法进行验证。实验表明，该计算公式和实现方法满足后台业务分析的需求，可作为治安卡口应用系统相关功能的业务支撑。

参考文献

[1] VLACHOS M， KOLLIOS G， GUNOPULOS D. Discovering si?milar multidimensional trajectories [C]// Proceedings of 2002 18th International Conference on Data Engineering. Riverside： IEEE， 2002： 673?684.

[2] KOLLIOS G， GUNOPULOS D， VLACHOS M. Robust similarity measures for mobile object trajectories [C]// Proceedings of 2002 International Workshop on Database & Expert Systems Applications. France： IEEE， 2002： 721?726.

[3] WHITE T.Hadoop权威指南[M].周敏奇，王晓玲，金澈清，等译，2版.北京：清华大学出版社，2011.

[4] DEAN J， GHEMAWAT S. MapReduce： simplified data processing on large clusters [C]// Proceedings of the 6th Confe?rence on Symposium on Operation Systems Design Implementation. Berkeley： ACM， 2004： 107?113.

[5] ZAHARIA M， CHOWDHURY M， DAS T， et al. Resilient distributed datasets： a fault?tolerant abstraction for in?memory cluster computing [C]// Proceedings of the 9th USENIX Confe?rence on Networked Systems Design and Implementation. Berkeley： ACM， 2012： 141?146.

[6] HWANG J R， KANG H Y， LI K J. Spatio?temporal similarity analysis between trajectories on road networks [C]// Procee?dings of ER 2005 Workshops on AOIS. BP?UML， CoMoGIS， eCOMO， and Qols. Klagenfurt： Springer Berlin Heidelberg， 2005： 280?289.

[7] 夏俊鸾，刘旭晖，邵赛赛，等.Spark大数据处理技术[M].北京：电子工业出版社，2015.

[8] 高彦杰.Spark大数据处理：技术、应用与性能优化[M].北京：机械工业出版社，2014.