車輛大數(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