车辆大数据研判之同行车辆（伴随车辆）

• 2016/10/24

车辆大数据研判之同行车辆（伴随车辆）

  随着科技的发展，通过使用传感器、位置捕获和跟踪设备等技术产生了大量的位置相关方面的数据，智能交通系统(Intelligence Transportation Systems， ITS)领域的应用程序开始利用这些交通数据，来记录车辆移动和交通轨迹的动态生成情况[1]。车牌自动识别(Automatic Number Plate Recognition， ANPR)数据是对交通摄像头捕捉到的道路交通数据进行处理生成的数据。ANPR 数据每时每刻都在不停地产生，形成了庞大的数据规模。  

  现代社会道路监控技术发展的同时，违法犯罪行为与车辆、交通系统的联系也越来越密切。伴随车辆是一个交通术语，是指在一定时间内与追踪车辆以一定概率存在伴随关系的车辆。如果事先知道涉案车辆的车牌号，可以直接通过查询ANPR数据找出其伴随车辆，然而实际情况中往往并不知道涉案车辆的车牌号，在这种情况下就需要通过伴随车辆组发现方法从海量的ANPR数据中寻找出经常一起出现的伴随车辆，提供给公安机关进行排查。  

  在涉案车辆追踪服务应用中，可以对海量ANPR数据进行分析处理，为公安部门办案中的犯罪嫌疑车辆排查分析提供参考。本文的主要贡献是：1)提出了一种基于并行FPGrowth算法的伴随车辆组发现方法――FPDTC方法。该方法对关联分析中的FPGrowth算法作了并行化的改进和优化，解决了车牌识别大数据处理中涉及到的频繁子集挖掘问题;2)利用云计算环境下的分布式并行处理框架Spark，实现了该算法。经过实验验证该方法能够很好地处理海量ANPR数据，解决了单机模式下的内存不足等问题，在伴随车辆组分析发现上的性能得到了提升。   

一、问题的提出  

  伴随车辆组的发现是从ANPR数据集中的不同车辆之间的联系来分析车辆的行驶习惯，通过了解哪些车辆频繁地在多个监测点共同出现来分析它们之间的相互关系，本质上就是寻找不同车辆之间的关联性或相关性，因此可以使用关联分析方法来解决。点伴随是指在一定的时间范围内共同经过同一监测点的车辆所具有的一种伴随关系，具有点伴随关系的车辆共同组成点伴随组。前面提到伴随车辆是在一定时间内与追踪车辆以一定概率存在伴随关系的车辆，实际场景中这个概率通常指设定的监测点阈值与点伴随车辆共同经过的监测点数目的比值。因此可以通过对点伴随组进行关联分析，找出满足这一概率的频繁子集车辆，即可求解出伴随车辆组，作为涉案车辆重点追踪和排查的对象。  

  当前的车辆数据越来越多，据统计，中国一个大型城市部署的带车牌识别功能的摄像头可达到5000个，高峰期每个摄像头车牌识别数据的采集频率可达每秒1条，每天的交通高峰折算率按0.33统计，则一天的车辆识别数据记录数将达到1.44亿条，数据量约12GB[2]。面对如此大量的ANPR数据，利用关联分析方法在单台机器上分析求解伴随车辆组存在大量的计算和存储负担，效率偏低。  

  目前一些先进的伴随车辆组发现方法及技术被用于全球定位系统(Global Positioning System， GPS)的数据分析[3]，而本文所研究的ANPR数据与GPS数据不同，其记录的位置由于摄像头固定等原因一般都是有限制的，其方法和技术并不完全适用于ANPR数据。文献[4]提出的伴随车辆查询(Accompany Vehicle Discovery， AVD)方法虽然可以适用于ANPR数据的分析，但其采用的滑动时间窗口技术仅在求解点伴随组上提升了效率，最后利用关联分析算法求解伴随车辆时摆脱不了单台机器的计算能力限制。  

  基于以上两个原因，需要考虑一种新的高效的方法来解决伴随车辆组的发现问题。本文提出的FPDTC方法，通过使用分布式处理框架Spark实现的并行FPGrowth算法来从车牌识别大数据中更加高效地发现伴随车辆组。 

  二、伴随车辆组发现方法――FPDTC方法  

  计算伴随车辆组，需要综合数天的车牌识别数据进行分析处理，本文采用一种基于多过程并行模式的处理方法(简称为FPDTC方法)。首先，需要对ANPR数据集进行预处理，过滤掉不符合要求的数据，仅保留计算过程中需要的字段值;然后，将过滤后的数据集按时间先后排序，根据车牌号生成每辆车的车辆轨迹;再根据所得的车辆轨迹计算各监测点下的点伴随组;最后，根据点伴随组求得伴随车辆组。在这一章中将具体介绍这些过程的实现方法。  

  2.1交通数据的预处理  

  ANPR数据集中的每一条记录均包含多个字段，由于所捕获的监测点数据有限导致某些字段的值缺失或者某些字段对于当前的数据分析处理没有任何意义，这样的数据在车辆轨迹判定中很难发挥作用。因此本文方法通过Spark中的过滤函数将数据集并行的处理成只包含〈车牌号，监测点，时间点〉(简写为〈v， s， time〉)3个字段的数据集，从而降低参与后续计算的数据规模，提高处理速度。  

  2.2车辆轨迹和点伴随组的生成  

  车辆轨迹是一段时间内车辆所经过的监测点位置序列。对过滤后的数据集先按照车牌号分组，然后根据监测时间先后排序，最终得到在一定日期时间范围内的车辆轨迹。步骤如图1所示。    

  本文算法都是基于Spark实现的，而弹性分布式数据集(RDD)是Spark最基本的数据抽象。它是一个容错的、并行的数据结构，可以让用户显式地将数据存储到磁盘和内存中，并能控制数据的分区[5]。同时，RDD还提供了一组丰富的操作可以像在MapReduce中处理数据一样并行地操作数据，如flatMap、filter、mapToPair、groupByKey等操作。  

  得出车辆轨迹数据后，基于这些轨迹数据对每一个监测点和相同监测点下的每一辆车进行迭代，当满足时间阈值时，将该车辆加入点伴随组G，其数据格式为〈s， v1：v2：v3：…〉。 

 var cpro_psid ="u2572954"; var cpro_pswidth =966; var cpro_psheight =120;

  2.3伴随车辆组的发现  

  为了方便地分析求解问题，本文为伴随车辆组作了如下的形式化定义：  

  设q是点伴随组G的一个子集，δcom为监测点阈值，ncom为q中车辆共同经过的监测点数目，当且仅当ncom≥δcom时，称q中的车辆互为伴随车辆，q称为伴随车辆组。  

  下面以图2为例简单介绍下发现伴随车辆组的过程。  

  图2中，共有{s1， s2，…，s6}6个监测点，{v1， v2， …， v10}10辆车，横坐标是车辆经过某监测点的时间，纵坐标是监测点的位置。假定监测点阈值为5，时间阈值为30min，车辆组{v1， v2， v7， v3， v4}和{v8， v10， v5}在时间阈值内共同经过了同一个监测点s1，则它们共同组成一个点伴随组。从图中可以看出，车辆组{v1， v2， v3， v4}、{v5， v10}都是此点伴随组的子集，车辆组{v1， v2， v3， v4}共同经过了{s1， s2， s3， s5} 4个监测点，而车辆组{v5， v10}共同经过了{s1， s2， s3， s4， s6} 5个监测点，所以只有车辆组{v5，v10}满足大于等于监测点阈值的条件，在这种情况下，车辆v5， v10共同组成伴随车辆组。  

  上一节中求出点伴随组后，其子集均为共同经过某一监测点的车辆或车辆组，根据前面给出的伴随车辆组的形式化定义，要想求得伴随车辆组，需要找出满足共同经过的监测点数目超过监测点阈值的所有点伴随组子集，因此可以使用关联分析算法对点伴随组进行频繁子集挖掘即可，求得的这些点伴随组的子集就是伴随车辆组。目前传统的频繁项集挖掘主要包括两大类算法，基于Apriori的挖掘算法和基于模式增长(FPGrowth)类的算法。其中FPGrowth算法摆脱了Apriori算法必须产生候选项集的方式，提高了数据的挖掘效率[6]。  

  传统FPGrowth算法的基本思路是：不断地迭代FPTree的构造和投影过程，对FPTree进行递归挖掘找出所有的频繁项集。该算法需要扫描两次事务集：第1次扫描事务集求出频繁1项集，并按照支持度降序排列;第2次扫描事务集，对于每个频繁项，构造它的条件投影数据库和投影FPTree;对每个新构建的FPTree重复这个过程，直到构造的新FPTree为空，或者只包含1条路径。当构造的FPTree为空时，其前缀即为频繁模式;当只包含1条路径时，通过枚举所有可能组合并与此树的前缀连接即可得到频繁模式[7]。  

  由于传统的FPGrowth算法对于FPTree的构造是在内存中进行的，当数据规模很大时，FP树的内存占用会相当可观，同时FPTree的构造过程也需要很高的运算性能。本文基于Spark框架将FPGrowth算法进行了并行化的改进和优化，使其可以根据事务集的规模进行分组，将事务集均衡地分配到每个节点下进行并行计算来提高运算效率。基于Spark的并行FPGrowth处理计算框架如图3所示。  

  图3所示框架展示了算法的4个步骤：1)首先通过一个并行计算过程，如mapToPair、groupByKey等求出频繁1项集，统计事务项频繁度并按其降序排列。2)为了达到负载均衡的效果，并且保证每组相对独立，以便后续处理更方便，要对数据进行平衡分组。通过利用频繁1项集的结果建立Hash表，按照Hash分组策略第2次扫描事务集将其分组。假设有m个节点，n个频繁1项集，数据分解后的空间复杂度就减小到O(n/m)。3)对分组后的事务集进行一定的并行处理后将其分配到各个节点单独计算各分组的子频繁项集，各节点从条件 FPTree分单分支和多分支两种情况进行本地递归挖掘频繁项集。4)最后对各个节点的频繁子集进行汇总。其伪代码如算法1所示。  

  算法1基于点伴随组生成伴随车辆组genFrequentSet。  

  输入点伴随组G，监测点阈值δcom;  

  输出伴随车辆组数据集Q。  

  程序前  

  1  

  freqset_1=FPGStepOne(G，δcom);  

  2)  

  FPGStepTwo(G， freqsubset_1，δcom)   3)  

  DRDD=SparkConf.textFile(G);  

  4)  

  mapToPair(DRDD)  

  5)  

  groupByKey(s， Gi)  

  6)  

  //将事务分组到每个节点  

  7)  

  List(Gi)=Grouping(G， freqset_1)  

  8)  

  //在各个节点下运行本地FP-Growth算法  

  9)

        var cpro_psid = "u2787156";

        var cpro_pswidth = "966";

        var cpro_psheight = "120";

   LocalFPTree(Gi，δcom，null)    10) 

   // 构建项头表    11) 

   headerTable=buildHeaderTable(Gi，δcom)    12) 

   //构建FP-Tree    13) 

   buildFPTree(Gi，headerTable)    14) 

   for each(gj) in Gi    15) 

   sortByHeaderTable(gj，headerTable)    16) 

   addNodes(TreeNode，gj，headerTable)    17)    end for    18) 

   end buildFPTree    19) 

   //递归以求子FP-Tree