车辆大數(shù)据研判之同行(xíng)车辆（伴随车辆）

• 2016/10/24

车辆大數(shù)据研判之同行(xíng)车辆（伴随车辆）

  随着科技的发展，通(tōng)过使用传感器、位置捕获和(hé)跟踪设备等技術(shù)产生了(le)大量的位置相关方面的數(shù)据，智能(néng)交通(tōng)系统(Intelligence Transportation Systems， ITS)领域的应用程序開(kāi)始利用這(zhè)些交通(tōng)數(shù)据，来记录车辆移动和(hé)交通(tōng)轨迹的动态生成情况[1]。车牌自(zì)动识别(Automatic Number Plate Recognition， ANPR)數(shù)据是对交通(tōng)摄像头捕捉到的道(dào)路交通(tōng)數(shù)据进行(xíng)处理生成的數(shù)据。ANPR 數(shù)据每時(shí)每刻都(dōu)在不停地(dì)产生，形成了(le)庞大的數(shù)据规模。  

  现代社会道(dào)路监控技術(shù)发展的同時(shí)，违法犯罪行(xíng)為(wèi)与车辆、交通(tōng)系统的联系也越来越密切。伴随车辆是一(yī)个交通(tōng)術(shù)语，是指在一(yī)定時(shí)間(jiān)內(nèi)与追踪车辆以一(yī)定概率存在伴随关系的车辆。如(rú)果事先知道(dào)涉案车辆的车牌号，可(kě)以直接通(tōng)过查询ANPR數(shù)据找出其伴随车辆，然而实际情况中往往并不知道(dào)涉案车辆的车牌号，在這(zhè)种情况下(xià)就需要(yào)通(tōng)过伴随车辆组发现方法從(cóng)海(hǎi)量的ANPR數(shù)据中寻找出经常一(yī)起出现的伴随车辆，提供给公安机关进行(xíng)排查。  

  在涉案车辆追踪服务应用中，可(kě)以对海(hǎi)量ANPR數(shù)据进行(xíng)分析处理，為(wèi)公安部门办案中的犯罪嫌疑车辆排查分析提供参考。本文的主要(yào)贡献是：1)提出了(le)一(yī)种基于并行(xíng)FPGrowth算法的伴随车辆组发现方法――FPDTC方法。该方法对关联分析中的FPGrowth算法作(zuò)了(le)并行(xíng)化的改进和(hé)优化，解决了(le)车牌识别大數(shù)据处理中涉及到的頻(pín)繁子集挖掘問(wèn)题;2)利用云计算环境下(xià)的分布式并行(xíng)处理框架Spark，实现了(le)该算法。经过实验验证该方法能(néng)够很(hěn)好地(dì)处理海(hǎi)量ANPR數(shù)据，解决了(le)单机模式下(xià)的內(nèi)存不足等問(wèn)题，在伴随车辆组分析发现上(shàng)的性能(néng)得到了(le)提升。   

一(yī)、問(wèn)题的提出  

  伴随车辆组的发现是從(cóng)ANPR數(shù)据集中的不同车辆之間(jiān)的联系来分析车辆的行(xíng)驶习惯，通(tōng)过了(le)解哪些车辆頻(pín)繁地(dì)在多个监测点共同出现来分析它们之間(jiān)的相互关系，本质上(shàng)就是寻找不同车辆之間(jiān)的关联性或相关性，因此可(kě)以使用关联分析方法来解决。点伴随是指在一(yī)定的時(shí)間(jiān)范围內(nèi)共同经过同一(yī)监测点的车辆所具有的一(yī)种伴随关系，具有点伴随关系的车辆共同组成点伴随组。前面提到伴随车辆是在一(yī)定時(shí)間(jiān)內(nèi)与追踪车辆以一(yī)定概率存在伴随关系的车辆，实际场景中這(zhè)个概率通(tōng)常指设定的监测点阈值与点伴随车辆共同经过的监测点數(shù)目的比值。因此可(kě)以通(tōng)过对点伴随组进行(xíng)关联分析，找出满足這(zhè)一(yī)概率的頻(pín)繁子集车辆，即可(kě)求解出伴随车辆组，作(zuò)為(wèi)涉案车辆重点追踪和(hé)排查的对象。  

  当前的车辆數(shù)据越来越多，据统计，中國(guó)一(yī)个大型城市部署的带车牌识别功能(néng)的摄像头可(kě)达到5000个，高峰期每个摄像头车牌识别數(shù)据的采集頻(pín)率可(kě)达每秒1条，每天的交通(tōng)高峰折算率按0.33统计，则一(yī)天的车辆识别數(shù)据记录數(shù)将达到1.44亿条，數(shù)据量约12GB[2]。面对如(rú)此大量的ANPR數(shù)据，利用关联分析方法在单台机器上(shàng)分析求解伴随车辆组存在大量的计算和(hé)存储负担，效率偏低(dī)。  

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

  基于以上(shàng)两个原因，需要(yào)考虑一(yī)种新的高效的方法来解决伴随车辆组的发现問(wèn)题。本文提出的FPDTC方法，通(tōng)过使用分布式处理框架Spark实现的并行(xíng)FPGrowth算法来從(cóng)车牌识别大數(shù)据中更加高效地(dì)发现伴随车辆组。 

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

  计算伴随车辆组，需要(yào)综合數(shù)天的车牌识别數(shù)据进行(xíng)分析处理，本文采用一(yī)种基于多过程并行(xíng)模式的处理方法(简称為(wèi)FPDTC方法)。首先，需要(yào)对ANPR數(shù)据集进行(xíng)预处理，过滤掉不符合要(yào)求的數(shù)据，仅保留计算过程中需要(yào)的字段值;然后，将过滤后的數(shù)据集按時(shí)間(jiān)先后排序，根据车牌号生成每辆车的车辆轨迹;再根据所得的车辆轨迹计算各监测点下(xià)的点伴随组;最后，根据点伴随组求得伴随车辆组。在這(zhè)一(yī)章(zhāng)中将具体介绍這(zhè)些过程的实现方法。  

  2.1交通(tōng)數(shù)据的预处理  

  ANPR數(shù)据集中的每一(yī)条记录均包含多个字段，由于所捕获的监测点數(shù)据有限导致某些字段的值缺失或者某些字段对于当前的數(shù)据分析处理没有任何意义，這(zhè)样的數(shù)据在车辆轨迹判定中很(hěn)难发挥作(zuò)用。因此本文方法通(tōng)过Spark中的过滤函數(shù)将數(shù)据集并行(xíng)的处理成只包含〈车牌号，监测点，時(shí)間(jiān)点〉(简写為(wèi)〈v， s， time〉)3个字段的數(shù)据集，從(cóng)而降低(dī)参与后续计算的數(shù)据规模，提高处理速度。  

  2.2车辆轨迹和(hé)点伴随组的生成  

  车辆轨迹是一(yī)段時(shí)間(jiān)內(nèi)车辆所经过的监测点位置序列。对过滤后的數(shù)据集先按照车牌号分组，然后根据监测時(shí)間(jiān)先后排序，最终得到在一(yī)定日期時(shí)間(jiān)范围內(nèi)的车辆轨迹。步骤如(rú)图1所示。    

  本文算法都(dōu)是基于Spark实现的，而弹性分布式數(shù)据集(RDD)是Spark最基本的數(shù)据抽象。它是一(yī)个容错的、并行(xíng)的數(shù)据结构，可(kě)以让用户显式地(dì)将數(shù)据存储到磁盘和(hé)內(nèi)存中，并能(néng)控制數(shù)据的分區(qū)[5]。同時(shí)，RDD还提供了(le)一(yī)组丰富的操作(zuò)可(kě)以像在MapReduce中处理數(shù)据一(yī)样并行(xíng)地(dì)操作(zuò)數(shù)据，如(rú)flatMap、filter、mapToPair、groupByKey等操作(zuò)。  

  得出车辆轨迹數(shù)据后，基于這(zhè)些轨迹數(shù)据对每一(yī)个监测点和(hé)相同监测点下(xià)的每一(yī)辆车进行(xíng)迭代，当满足時(shí)間(jiān)阈值時(shí)，将该车辆加入点伴随组G，其數(shù)据格式為(wèi)〈s， v1：v2：v3：…〉。 

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

  2.3伴随车辆组的发现  

  為(wèi)了(le)方便地(dì)分析求解問(wèn)题，本文為(wèi)伴随车辆组作(zuò)了(le)如(rú)下(xià)的形式化定义：  

  设q是点伴随组G的一(yī)个子集，δcom為(wèi)监测点阈值，ncom為(wèi)q中车辆共同经过的监测点數(shù)目，当且仅当ncom≥δcom時(shí)，称q中的车辆互為(wèi)伴随车辆，q称為(wèi)伴随车辆组。  

  下(xià)面以图2為(wèi)例简单介绍下(xià)发现伴随车辆组的过程。  

  图2中，共有{s1， s2，…，s6}6个监测点，{v1， v2， …， v10}10辆车，横坐(zuò)标是车辆经过某监测点的時(shí)間(jiān)，纵坐(zuò)标是监测点的位置。假定监测点阈值為(wèi)5，時(shí)間(jiān)阈值為(wèi)30min，车辆组{v1， v2， v7， v3， v4}和(hé){v8， v10， v5}在時(shí)間(jiān)阈值內(nèi)共同经过了(le)同一(yī)个监测点s1，则它们共同组成一(yī)个点伴随组。從(cóng)图中可(kě)以看(kàn)出，车辆组{v1， v2， v3， v4}、{v5， v10}都(dōu)是此点伴随组的子集，车辆组{v1， v2， v3， v4}共同经过了(le){s1， s2， s3， s5} 4个监测点，而车辆组{v5， v10}共同经过了(le){s1， s2， s3， s4， s6} 5个监测点，所以只有车辆组{v5，v10}满足大于等于监测点阈值的条件，在這(zhè)种情况下(xià)，车辆v5， v10共同组成伴随车辆组。  

  上(shàng)一(yī)节中求出点伴随组后，其子集均為(wèi)共同经过某一(yī)监测点的车辆或车辆组，根据前面给出的伴随车辆组的形式化定义，要(yào)想求得伴随车辆组，需要(yào)找出满足共同经过的监测点數(shù)目超过监测点阈值的所有点伴随组子集，因此可(kě)以使用关联分析算法对点伴随组进行(xíng)頻(pín)繁子集挖掘即可(kě)，求得的這(zhè)些点伴随组的子集就是伴随车辆组。目前传统的頻(pín)繁项集挖掘主要(yào)包括两大类算法，基于Apriori的挖掘算法和(hé)基于模式增長(cháng)(FPGrowth)类的算法。其中FPGrowth算法摆脱了(le)Apriori算法必须产生候选项集的方式，提高了(le)數(shù)据的挖掘效率[6]。  

  传统FPGrowth算法的基本思路是：不断地(dì)迭代FPTree的构造和(hé)投影过程，对FPTree进行(xíng)递归挖掘找出所有的頻(pín)繁项集。该算法需要(yào)扫描两次事务集：第1次扫描事务集求出頻(pín)繁1项集，并按照支持度降序排列;第2次扫描事务集，对于每个頻(pín)繁项，构造它的条件投影數(shù)据库和(hé)投影FPTree;对每个新构建的FPTree重复這(zhè)个过程，直到构造的新FPTree為(wèi)空，或者只包含1条路径。当构造的FPTree為(wèi)空時(shí)，其前缀即為(wèi)頻(pín)繁模式;当只包含1条路径時(shí)，通(tōng)过枚举所有可(kě)能(néng)组合并与此樹(shù)的前缀连接即可(kě)得到頻(pín)繁模式[7]。  

  由于传统的FPGrowth算法对于FPTree的构造是在內(nèi)存中进行(xíng)的，当數(shù)据规模很(hěn)大時(shí)，FP樹(shù)的內(nèi)存占用会相当可(kě)观，同時(shí)FPTree的构造过程也需要(yào)很(hěn)高的运算性能(néng)。本文基于Spark框架将FPGrowth算法进行(xíng)了(le)并行(xíng)化的改进和(hé)优化，使其可(kě)以根据事务集的规模进行(xíng)分组，将事务集均衡地(dì)分配到每个节点下(xià)进行(xíng)并行(xíng)计算来提高运算效率。基于Spark的并行(xíng)FPGrowth处理计算框架如(rú)图3所示。  

  图3所示框架展示了(le)算法的4个步骤：1)首先通(tōng)过一(yī)个并行(xíng)计算过程，如(rú)mapToPair、groupByKey等求出頻(pín)繁1项集，统计事务项頻(pín)繁度并按其降序排列。2)為(wèi)了(le)达到负载均衡的效果，并且保证每组相对独立，以便后续处理更方便，要(yào)对數(shù)据进行(xíng)平衡分组。通(tōng)过利用頻(pín)繁1项集的结果建立Hash表，按照Hash分组策略第2次扫描事务集将其分组。假设有m个节点，n个頻(pín)繁1项集，數(shù)据分解后的空間(jiān)复雜(zá)度就减小到O(n/m)。3)对分组后的事务集进行(xíng)一(yī)定的并行(xíng)处理后将其分配到各个节点单独计算各分组的子頻(pín)繁项集，各节点從(cóng)条件 FPTree分单分支和(hé)多分支两种情况进行(xíng)本地(dì)递归挖掘頻(pín)繁项集。4)最后对各个节点的頻(pín)繁子集进行(xíng)汇总。其伪代码如(rú)算法1所示。  

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

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

  输出伴随车辆组數(shù)据集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)  

  //在各个节点下(xià)运行(xíng)本地(dì)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