- 相關推薦
基于車牌識別大數據的伴隨車輛組發現方法
摘要：基于對車牌識別大數據的處理與分析，可以完成伴隨車輛組的發現，在涉案車輛追蹤等方面具有廣泛的應用。然而當前單一機器模式下伴隨車輛組發現算法存在時間和空間上處理性能低下等問題。針對此問題，提出了一種伴隨車輛組發現方法――FPDTC方法。該方法將傳統的FPGrowth算法利用分布式處理框架Spark進行了并行化，并作了相應的改進和優化來更加高效地發現伴隨車輛組。實驗結果的分析表明，提出的方法能夠很好地解決車牌識別大數據上的伴隨車輛組發現問題，性能相比采用同樣方法的Hadoop實現提升了近4倍。
關鍵詞：智能交通系統;伴隨車輛組;FPGrowth算法;Spark并行框架;車牌識別
引言
隨著科技的發展，通過使用傳感器、位置捕獲和跟蹤設備等技術產生了大量的位置相關方面的數據，智能交通系統(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所示。
1) 使用textFile方法讀取ANPR數據集并將其轉換為相同格式的彈性分布式數據集(Resilient Distributed Dataset，RDD)形式，具體為HadoopRDD，其包含〈v，s，time〉 3個字段的信息;2) 通過mapToPair方法以車牌號作為鍵，監測點和時間作為值將RDD從DRDD轉換為PairRDD的形式，其格式為〈v，s+time〉;3) 然后通過groupByKey方法將PairRDD按照鍵v進行分組，將具有相同鍵值v的數據放在一起，形成另一種形式的PairRDD，格式為〈v， Iterable〈s+time〉〉，其中鍵v不變，值為具有相同鍵v的一組數據;4) 再通過mapValues方法實現對PairRDD中的數據排序的功能，該方法將對同一車牌號下的數據按照時間先后排序。5) 最后使用collect方法得出車輛軌跡數據，其格式為List〈v， Iterable〈s+time〉〉。
本文算法都是基于Spark實現的，而彈性分布式數據集(RDD)是Spark最基本的數據抽象。它是一個容錯的、并行的數據結構，可以讓用戶顯式地將數據存儲到磁盤和內存中，并能控制數據的分區[5]。同時，RDD還提供了一組豐富的操作可以像在MapReduce中處理數據一樣并行地操作數據，如flatMap、filter、mapToPair、groupByKey等操作。
得出車輛軌跡數據后，基于這些軌跡數據對每一個監測點和相同監測點下的每一輛車進行迭代，當滿足時間閾值時，將該車輛加入點伴隨組G，其數據格式為〈s， v1：v2：v3：…〉。
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)
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
20)
LocalFPTree(Gj，δcom， item)
21)
Qi.add(Iterable(freqSubset));
22)
end LocalFPTree
23)
end FPGStepTwo
24)
Q=CollectFromEachNode(Qi)
25)
return Q;
程序后
三、實驗與分析
為了有效驗證本文提出的利用分布式并行處理框架Spark實現的FPGrowth算法來發現伴隨車輛組方法的有效性，搭建了基于Spark集群的實驗環境并進行了多組實驗。
3.1實驗環境與數據
本文的Spark集群采用基于Yarn的資源調度模式，由5臺裝載CentOS release 6.4系統，Spark1.1.0以及 Hadoop2.3.0軟件的服務器搭建而成，內存主節點配置6GB，從節點機器配置為3GB，其他硬件配置均相同。實驗中采用的數據為北京市2012年11月13日到11月19日7天全天采集到的真實車牌識別數據，每天的數據記錄約970萬余條，涉及約230萬輛車，1794個道路監測點，實驗中的所有數據均存儲在同一個HDFS集群中。
3.2實驗結果與分析
1)性能測試與分析。
本文方法通過在相同規模數據與硬件配置環境下，測試單機算法與并行算法在Spark集群中單個計算節點下的執行時間來說明采用分布式計算的必要性，通過測試FPDTC方法在不同的并行計算框架下的執行時間來評估該算法的性能。如測試10min、20min、…、60min時間之內的交通數據分別在單機算法和并行算法框架下，以及分別在Hadoop和Spark框架下執行5次的平均時間。
表1展示了單機FPGrowth算法和并行FPDTC算法Spark集群單節點下的實驗結果對比。
從表1中可以看到，當輸入數據規模很小時，并行算法處理效率低于單機FPGrowth算法，這是因為Spark集群啟動和分配任務時需要消耗一定的時間和資源，且在總運行時間中占據很大的比例。隨著數據規模的增長，單機算法內存消耗增大，剩余內存不足以支撐計算任務;而并行算法由于具有良好的并行框架Spark的支持，進行適當的內部資源調度，最終能夠完成計算任務。這充分說明了在單一機器模式下不足以處理和分析車牌識別大數據，利用集群并行處理數據是很有必要的。
圖4展示了在兩種不同的并行計算框架下實現的FPDTC算法的性能比較。從圖中可以看出，Spark實現的算法執行時間明顯短于用Hadoop實現的算法，性能相比提升了近4倍。這是由于Spark框架的每一次迭代都是基于內存計算的，而Hadoop則需要頻繁地讀寫磁盤，耗費了大量的時間。還可以看到隨著數據規模的增大，前者增長幅度明顯小于后者。因此通過使用Spark框架實現該FPDTC方法能夠很好地解決車牌識別大數據上的伴隨車輛組發現問題。
2)關鍵參數影響測試與分析。
在計算伴隨車輛組的過程中，有兩個參數閾值的調整對結果具有很大的影響，分別是時間閾值δt和監測點閾值δcom。
時間閾值δt是產生點伴隨組的基礎。首先設定數據集的時間范圍為30min，監測點閾值為4，然后依次將δt設置為1min，2min，3min，…，10min，計算算法執行5次的平均時間。
圖5展示了不同時間閾值下算法的執行性能。隨著時間閾值的增大，算法的執行時間成本相應的增加，這是因為點伴隨組的數量規模也在不斷增加，此時可以通過擴展集群節點的方法降低程序執行時間。
監測點閾值δcom是計算伴隨車輛組的基礎。為了測試其對結果的影響，設定數據集的時間范圍為30min，時間閾值為5min，監測點閾值δcom為3，4，5，6，7，8。從圖6可以看出算法的執行時間隨著監測點閾值的增大而減小，這是因為每一次迭代計算的數據規模都變小了。
四、相關工作
雖然伴隨車輛組發現一直是智能交通領域的一個研究熱點，然而，基于交通大數據的集成與分析研究尚處于起始階段，本文總結了當前的相關工作如下：
1)伴隨車輛組發現。近年來，移動對象的伴隨組發現與查詢成為移動對象數據管理領域的研究熱點[8]。很多研究者也提出了許多的計算方法，如Gridbased、Euclidean distance、動態時間歸整(Dynamic Time Warping， DTW)等方法[9-11]，但在最初的研究中它們很多都缺乏對移動對象軌跡時間屬性的考慮以及偏側重于對全球定位系統(GPS)數據的分析處理，并不適合位置可測但車輛對象不定的車牌識別數據，而文獻[4]中的伴隨車輛查詢(AVD)方法雖然適用于車牌識別數據，但是同以上方法一樣并沒有從并行化的角度來考慮算法的性能問題。
2)大數據的處理框架。隨著數據量的不斷增加，越來越多的并行編程框架被用在加速大數據的處理之中，如Hadoop框架、Dryad框架、Storm框架等，但是這些框架并不適合用來進行迭代式計算和交互式計算。Spark是開源的類Hadoop MapReduce的通用的并行計算框架，擁有Hadoop MapReduce所具有的優點，不同于MapReduce的是， job的中間輸出和結果可以保存在內存中，從而不再需要讀寫HDFS，因此Spark能更好地適用于數據挖掘與機器學習中需要迭代的算法。
3)關聯分析領域的工作。當前數據挖掘領域的很多算法都已經實現了并行化，對于并行的關聯規則挖掘，Agrawal等在文獻[12] 中提出了計數分布(Count Distribution，CD)、候選分布 (Candidate Distribution，CaD) 和數據分布(Data Distribution，DD) 算法，但是這些算法對于節點數量的擴展不具有很好的支持，算法在實際生產環境中還需要考慮多節點所帶來的節點故障、網絡通信故障等復雜問題。
五、結語
本文論述了在面對海量交通數據時如何利用分布式并行數據處理框架Spark來分析處理數據，并利用并行FPDTC方法來求解伴隨車輛組。本文提出了一種基于多過程并行模式的處理方法，分別從車輛軌跡生成、計算點伴隨組以及產生伴隨車輛組3個過程展開敘述，最后通過實驗證明，該方法適用于大規模交通數據的分析與應用。本文還有許多需要改進的地方，比如求解伴隨車輛組時采用更加高效的求解頻繁子集的算法等。
參考文獻：
[1]NOREIKIS M， BUTKUS P， NURMINEN J K. Invehicle application for multimodal route planning and analysis[C]// Proceedings of the 2014 IEEE 3rd International Conference on Cloud Networking. Piscataway： IEEE， 2014：350-355.
[2]LU S， ZHAO Z， HAN Y. A query method of the similarity of the vehicle trajectory[J].Computer and Digital Engineering， 2014， 42(9)：1565-1569. (盧帥， 趙卓峰， 韓燕波. 一種車輛移動對象相似軌跡查詢算法[J].計算機與數字工程，2014， 42(9)： 1565-1569.)
[3]TANG L A， ZHENG Y， YUAN J， et al.On discovery of traveling companions from streaming trajectories[C]// Proceedings of the 2012 IEEE 28th International Conference on Data Engineering. Piscataway： IEEE， 2012： 186-197.
[4]FANG A， LI X， MAN S， et al. A discovery algorithm of travelling companions based on association rule mining[J]. Computer Applications and Software， 2012， 29(2)： 94-96. (方艾芬， 李先通， 蔄世明， 等. 基于關聯規則挖掘的伴隨車輛發現算法[J]. 計算機應用與軟件， 2012， 29(2)： 94-96.)
[5]ZAHARIA M. An architecture for fast and general data processing on large clusters， UCB/EECS201412 [R/OL].[20150122]. http：//www.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS201412.html.
[6]AGRAWAL R， IMIELINSKI T， SWAMI A. Database mining： a performance perspective[J]. IEEE Transactions on Knowledge and Data Engineering， 1993，5(6)：914-925.
[7]AGRAWAL R， IMIELINSKI T， SWAMI A. Mining assocaition rules between sets of items in large databases[C]// Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. New York： ACM， 1993：207-216.
[8]DING R，MENG X，YANG N. An efficient query method of similar trajectories of moving objects[J]. Computer Science， 2003， 30(10)： 386-403.(丁銳， 孟小峰， 楊楠. 一種高效的移動對象相似軌跡查詢方法[J]. 計算機科學， 2003， 30(10)： 386-403.)
[9]UEHARA K， SEKI K， JINNO R. Parallel distributed trajectory pattern mining using MapReduce[C]// Proceedings of the 2012 IEEE 4th International Conference on Cloud Computing Technology and Science. Piscataway： IEEE， 2012： 269-273.
[10]CHAN K P， FU A C. Efficient time series matching by wavelets[C]// Proceedings of the 15th International Conference on Data Engineering. Piscataway： IEEE， 1999：126-133.
[11]KEOGH E J， PAZZANI H J. Scaling up dynamic time warping for datamining applications[C]// Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2000：285-289.
[12]AGRAWAL R，SHAFER J C. Parallel mining of association rules[J].IEEE Transactions on Knowledge and Data Engineering，1996，8(6)：962-969.
【基于車牌識別大數據的伴隨車輛組發現方法】相關文章：
基于聚類分析的數據挖掘方法03-08
基于單目視覺的夜間車輛檢測方法研究03-07
一種基于路測數據的基站定位方法03-07
字符結構知識在車牌識別中的應用03-19
實現基于網頁的數據庫數據導入03-18
基于XMLSchema的元數據方案實現03-21
基于SVM的ISAR像中的目標識別03-19
一種基于灰值形態學的汽車牌照提取方法03-18