- 相關(guān)推薦
基于車牌識(shí)別大數(shù)據(jù)的伴隨車輛組發(fā)現(xiàn)方法
摘要：基于對(duì)車牌識(shí)別大數(shù)據(jù)的處理與分析，可以完成伴隨車輛組的發(fā)現(xiàn)，在涉案車輛追蹤等方面具有廣泛的應(yīng)用。然而當(dāng)前單一機(jī)器模式下伴隨車輛組發(fā)現(xiàn)算法存在時(shí)間和空間上處理性能低下等問題。針對(duì)此問題，提出了一種伴隨車輛組發(fā)現(xiàn)方法――FPDTC方法。該方法將傳統(tǒng)的FPGrowth算法利用分布式處理框架Spark進(jìn)行了并行化，并作了相應(yīng)的改進(jìn)和優(yōu)化來更加高效地發(fā)現(xiàn)伴隨車輛組。實(shí)驗(yàn)結(jié)果的分析表明，提出的方法能夠很好地解決車牌識(shí)別大數(shù)據(jù)上的伴隨車輛組發(fā)現(xiàn)問題，性能相比采用同樣方法的Hadoop實(shí)現(xiàn)提升了近4倍。
關(guān)鍵詞：智能交通系統(tǒng);伴隨車輛組;FPGrowth算法;Spark并行框架;車牌識(shí)別
引言
隨著科技的發(fā)展，通過使用傳感器、位置捕獲和跟蹤設(shè)備等技術(shù)產(chǎn)生了大量的位置相關(guān)方面的數(shù)據(jù)，智能交通系統(tǒng)(Intelligence Transportation Systems， ITS)領(lǐng)域的應(yīng)用程序開始利用這些交通數(shù)據(jù)，來記錄車輛移動(dòng)和交通軌跡的動(dòng)態(tài)生成情況[1]。車牌自動(dòng)識(shí)別(Automatic Number Plate Recognition， ANPR)數(shù)據(jù)是對(duì)交通攝像頭捕捉到的道路交通數(shù)據(jù)進(jìn)行處理生成的數(shù)據(jù)。ANPR 數(shù)據(jù)每時(shí)每刻都在不停地產(chǎn)生，形成了龐大的數(shù)據(jù)規(guī)模。
現(xiàn)代社會(huì)道路監(jiān)控技術(shù)發(fā)展的同時(shí)，違法犯罪行為與車輛、交通系統(tǒng)的聯(lián)系也越來越密切。伴隨車輛是一個(gè)交通術(shù)語，是指在一定時(shí)間內(nèi)與追蹤車輛以一定概率存在伴隨關(guān)系的車輛。如果事先知道涉案車輛的車牌號(hào)，可以直接通過查詢ANPR數(shù)據(jù)找出其伴隨車輛，然而實(shí)際情況中往往并不知道涉案車輛的車牌號(hào)，在這種情況下就需要通過伴隨車輛組發(fā)現(xiàn)方法從海量的ANPR數(shù)據(jù)中尋找出經(jīng)常一起出現(xiàn)的伴隨車輛，提供給公安機(jī)關(guān)進(jìn)行排查。
在涉案車輛追蹤服務(wù)應(yīng)用中，可以對(duì)海量ANPR數(shù)據(jù)進(jìn)行分析處理，為公安部門辦案中的犯罪嫌疑車輛排查分析提供參考。本文的主要貢獻(xiàn)是：1)提出了一種基于并行FPGrowth算法的伴隨車輛組發(fā)現(xiàn)方法――FPDTC方法。該方法對(duì)關(guān)聯(lián)分析中的FPGrowth算法作了并行化的改進(jìn)和優(yōu)化，解決了車牌識(shí)別大數(shù)據(jù)處理中涉及到的頻繁子集挖掘問題;2)利用云計(jì)算環(huán)境下的分布式并行處理框架Spark，實(shí)現(xiàn)了該算法。經(jīng)過實(shí)驗(yàn)驗(yàn)證該方法能夠很好地處理海量ANPR數(shù)據(jù)，解決了單機(jī)模式下的內(nèi)存不足等問題，在伴隨車輛組分析發(fā)現(xiàn)上的性能得到了提升。
一、問題的提出
伴隨車輛組的發(fā)現(xiàn)是從ANPR數(shù)據(jù)集中的不同車輛之間的聯(lián)系來分析車輛的行駛習(xí)慣，通過了解哪些車輛頻繁地在多個(gè)監(jiān)測(cè)點(diǎn)共同出現(xiàn)來分析它們之間的相互關(guān)系，本質(zhì)上就是尋找不同車輛之間的關(guān)聯(lián)性或相關(guān)性，因此可以使用關(guān)聯(lián)分析方法來解決。點(diǎn)伴隨是指在一定的時(shí)間范圍內(nèi)共同經(jīng)過同一監(jiān)測(cè)點(diǎn)的車輛所具有的一種伴隨關(guān)系，具有點(diǎn)伴隨關(guān)系的車輛共同組成點(diǎn)伴隨組。前面提到伴隨車輛是在一定時(shí)間內(nèi)與追蹤車輛以一定概率存在伴隨關(guān)系的車輛，實(shí)際場(chǎng)景中這個(gè)概率通常指設(shè)定的監(jiān)測(cè)點(diǎn)閾值與點(diǎn)伴隨車輛共同經(jīng)過的監(jiān)測(cè)點(diǎn)數(shù)目的比值。因此可以通過對(duì)點(diǎn)伴隨組進(jìn)行關(guān)聯(lián)分析，找出滿足這一概率的頻繁子集車輛，即可求解出伴隨車輛組，作為涉案車輛重點(diǎn)追蹤和排查的對(duì)象。
當(dāng)前的車輛數(shù)據(jù)越來越多，據(jù)統(tǒng)計(jì)，中國一個(gè)大型城市部署的帶車牌識(shí)別功能的攝像頭可達(dá)到5000個(gè)，高峰期每個(gè)攝像頭車牌識(shí)別數(shù)據(jù)的采集頻率可達(dá)每秒1條，每天的交通高峰折算率按0.33統(tǒng)計(jì)，則一天的車輛識(shí)別數(shù)據(jù)記錄數(shù)將達(dá)到1.44億條，數(shù)據(jù)量約12GB[2]。面對(duì)如此大量的ANPR數(shù)據(jù)，利用關(guān)聯(lián)分析方法在單臺(tái)機(jī)器上分析求解伴隨車輛組存在大量的計(jì)算和存儲(chǔ)負(fù)擔(dān)，效率偏低。
目前一些先進(jìn)的伴隨車輛組發(fā)現(xiàn)方法及技術(shù)被用于全球定位系統(tǒng)(Global Positioning System， GPS)的數(shù)據(jù)分析[3]，而本文所研究的ANPR數(shù)據(jù)與GPS數(shù)據(jù)不同，其記錄的位置由于攝像頭固定等原因一般都是有限制的，其方法和技術(shù)并不完全適用于ANPR數(shù)據(jù)。文獻(xiàn)[4]提出的伴隨車輛查詢(Accompany Vehicle Discovery， AVD)方法雖然可以適用于ANPR數(shù)據(jù)的分析，但其采用的滑動(dòng)時(shí)間窗口技術(shù)僅在求解點(diǎn)伴隨組上提升了效率，最后利用關(guān)聯(lián)分析算法求解伴隨車輛時(shí)擺脫不了單臺(tái)機(jī)器的計(jì)算能力限制。
基于以上兩個(gè)原因，需要考慮一種新的高效的方法來解決伴隨車輛組的發(fā)現(xiàn)問題。本文提出的FPDTC方法，通過使用分布式處理框架Spark實(shí)現(xiàn)的并行FPGrowth算法來從車牌識(shí)別大數(shù)據(jù)中更加高效地發(fā)現(xiàn)伴隨車輛組。
二、伴隨車輛組發(fā)現(xiàn)方法――FPDTC方法
計(jì)算伴隨車輛組，需要綜合數(shù)天的車牌識(shí)別數(shù)據(jù)進(jìn)行分析處理，本文采用一種基于多過程并行模式的處理方法(簡稱為FPDTC方法)。首先，需要對(duì)ANPR數(shù)據(jù)集進(jìn)行預(yù)處理，過濾掉不符合要求的數(shù)據(jù)，僅保留計(jì)算過程中需要的字段值;然后，將過濾后的數(shù)據(jù)集按時(shí)間先后排序，根據(jù)車牌號(hào)生成每輛車的車輛軌跡;再根據(jù)所得的車輛軌跡計(jì)算各監(jiān)測(cè)點(diǎn)下的點(diǎn)伴隨組;最后，根據(jù)點(diǎn)伴隨組求得伴隨車輛組。在這一章中將具體介紹這些過程的實(shí)現(xiàn)方法。
2.1交通數(shù)據(jù)的預(yù)處理
ANPR數(shù)據(jù)集中的每一條記錄均包含多個(gè)字段，由于所捕獲的監(jiān)測(cè)點(diǎn)數(shù)據(jù)有限導(dǎo)致某些字段的值缺失或者某些字段對(duì)于當(dāng)前的數(shù)據(jù)分析處理沒有任何意義，這樣的數(shù)據(jù)在車輛軌跡判定中很難發(fā)揮作用。因此本文方法通過Spark中的過濾函數(shù)將數(shù)據(jù)集并行的處理成只包含〈車牌號(hào)，監(jiān)測(cè)點(diǎn)，時(shí)間點(diǎn)〉(簡寫為〈v， s， time〉)3個(gè)字段的數(shù)據(jù)集，從而降低參與后續(xù)計(jì)算的數(shù)據(jù)規(guī)模，提高處理速度。
2.2車輛軌跡和點(diǎn)伴隨組的生成
車輛軌跡是一段時(shí)間內(nèi)車輛所經(jīng)過的監(jiān)測(cè)點(diǎn)位置序列。對(duì)過濾后的數(shù)據(jù)集先按照車牌號(hào)分組，然后根據(jù)監(jiān)測(cè)時(shí)間先后排序，最終得到在一定日期時(shí)間范圍內(nèi)的車輛軌跡。步驟如圖1所示。
1) 使用textFile方法讀取ANPR數(shù)據(jù)集并將其轉(zhuǎn)換為相同格式的彈性分布式數(shù)據(jù)集(Resilient Distributed Dataset，RDD)形式，具體為HadoopRDD，其包含〈v，s，time〉 3個(gè)字段的信息;2) 通過mapToPair方法以車牌號(hào)作為鍵，監(jiān)測(cè)點(diǎn)和時(shí)間作為值將RDD從DRDD轉(zhuǎn)換為PairRDD的形式，其格式為〈v，s+time〉;3) 然后通過groupByKey方法將PairRDD按照鍵v進(jìn)行分組，將具有相同鍵值v的數(shù)據(jù)放在一起，形成另一種形式的PairRDD，格式為〈v， Iterable〈s+time〉〉，其中鍵v不變，值為具有相同鍵v的一組數(shù)據(jù);4) 再通過mapValues方法實(shí)現(xiàn)對(duì)PairRDD中的數(shù)據(jù)排序的功能，該方法將對(duì)同一車牌號(hào)下的數(shù)據(jù)按照時(shí)間先后排序。5) 最后使用collect方法得出車輛軌跡數(shù)據(jù)，其格式為List〈v， Iterable〈s+time〉〉。
本文算法都是基于Spark實(shí)現(xiàn)的，而彈性分布式數(shù)據(jù)集(RDD)是Spark最基本的數(shù)據(jù)抽象。它是一個(gè)容錯(cuò)的、并行的數(shù)據(jù)結(jié)構(gòu)，可以讓用戶顯式地將數(shù)據(jù)存儲(chǔ)到磁盤和內(nèi)存中，并能控制數(shù)據(jù)的分區(qū)[5]。同時(shí)，RDD還提供了一組豐富的操作可以像在MapReduce中處理數(shù)據(jù)一樣并行地操作數(shù)據(jù)，如flatMap、filter、mapToPair、groupByKey等操作。
得出車輛軌跡數(shù)據(jù)后，基于這些軌跡數(shù)據(jù)對(duì)每一個(gè)監(jiān)測(cè)點(diǎn)和相同監(jiān)測(cè)點(diǎn)下的每一輛車進(jìn)行迭代，當(dāng)滿足時(shí)間閾值時(shí)，將該車輛加入點(diǎn)伴隨組G，其數(shù)據(jù)格式為〈s， v1：v2：v3：…〉。
2.3伴隨車輛組的發(fā)現(xiàn)
為了方便地分析求解問題，本文為伴隨車輛組作了如下的形式化定義：
設(shè)q是點(diǎn)伴隨組G的一個(gè)子集，δcom為監(jiān)測(cè)點(diǎn)閾值，ncom為q中車輛共同經(jīng)過的監(jiān)測(cè)點(diǎn)數(shù)目，當(dāng)且僅當(dāng)ncom≥δcom時(shí)，稱q中的車輛互為伴隨車輛，q稱為伴隨車輛組。
下面以圖2為例簡單介紹下發(fā)現(xiàn)伴隨車輛組的過程。
圖2中，共有{s1， s2，…，s6}6個(gè)監(jiān)測(cè)點(diǎn)，{v1， v2， …， v10}10輛車，橫坐標(biāo)是車輛經(jīng)過某監(jiān)測(cè)點(diǎn)的時(shí)間，縱坐標(biāo)是監(jiān)測(cè)點(diǎn)的位置。假定監(jiān)測(cè)點(diǎn)閾值為5，時(shí)間閾值為30min，車輛組{v1， v2， v7， v3， v4}和{v8， v10， v5}在時(shí)間閾值內(nèi)共同經(jīng)過了同一個(gè)監(jiān)測(cè)點(diǎn)s1，則它們共同組成一個(gè)點(diǎn)伴隨組。從圖中可以看出，車輛組{v1， v2， v3， v4}、{v5， v10}都是此點(diǎn)伴隨組的子集，車輛組{v1， v2， v3， v4}共同經(jīng)過了{(lán)s1， s2， s3， s5} 4個(gè)監(jiān)測(cè)點(diǎn)，而車輛組{v5， v10}共同經(jīng)過了{(lán)s1， s2， s3， s4， s6} 5個(gè)監(jiān)測(cè)點(diǎn)，所以只有車輛組{v5，v10}滿足大于等于監(jiān)測(cè)點(diǎn)閾值的條件，在這種情況下，車輛v5， v10共同組成伴隨車輛組。
上一節(jié)中求出點(diǎn)伴隨組后，其子集均為共同經(jīng)過某一監(jiān)測(cè)點(diǎn)的車輛或車輛組，根據(jù)前面給出的伴隨車輛組的形式化定義，要想求得伴隨車輛組，需要找出滿足共同經(jīng)過的監(jiān)測(cè)點(diǎn)數(shù)目超過監(jiān)測(cè)點(diǎn)閾值的所有點(diǎn)伴隨組子集，因此可以使用關(guān)聯(lián)分析算法對(duì)點(diǎn)伴隨組進(jìn)行頻繁子集挖掘即可，求得的這些點(diǎn)伴隨組的子集就是伴隨車輛組。目前傳統(tǒng)的頻繁項(xiàng)集挖掘主要包括兩大類算法，基于Apriori的挖掘算法和基于模式增長(FPGrowth)類的算法。其中FPGrowth算法擺脫了Apriori算法必須產(chǎn)生候選項(xiàng)集的方式，提高了數(shù)據(jù)的挖掘效率[6]。
傳統(tǒng)FPGrowth算法的基本思路是：不斷地迭代FPTree的構(gòu)造和投影過程，對(duì)FPTree進(jìn)行遞歸挖掘找出所有的頻繁項(xiàng)集。該算法需要掃描兩次事務(wù)集：第1次掃描事務(wù)集求出頻繁1項(xiàng)集，并按照支持度降序排列;第2次掃描事務(wù)集，對(duì)于每個(gè)頻繁項(xiàng)，構(gòu)造它的條件投影數(shù)據(jù)庫和投影FPTree;對(duì)每個(gè)新構(gòu)建的FPTree重復(fù)這個(gè)過程，直到構(gòu)造的新FPTree為空，或者只包含1條路徑。當(dāng)構(gòu)造的FPTree為空時(shí)，其前綴即為頻繁模式;當(dāng)只包含1條路徑時(shí)，通過枚舉所有可能組合并與此樹的前綴連接即可得到頻繁模式[7]。
由于傳統(tǒng)的FPGrowth算法對(duì)于FPTree的構(gòu)造是在內(nèi)存中進(jìn)行的，當(dāng)數(shù)據(jù)規(guī)模很大時(shí)，F(xiàn)P樹的內(nèi)存占用會(huì)相當(dāng)可觀，同時(shí)FPTree的構(gòu)造過程也需要很高的運(yùn)算性能。本文基于Spark框架將FPGrowth算法進(jìn)行了并行化的改進(jìn)和優(yōu)化，使其可以根據(jù)事務(wù)集的規(guī)模進(jìn)行分組，將事務(wù)集均衡地分配到每個(gè)節(jié)點(diǎn)下進(jìn)行并行計(jì)算來提高運(yùn)算效率。基于Spark的并行FPGrowth處理計(jì)算框架如圖3所示。
圖3所示框架展示了算法的4個(gè)步驟：1)首先通過一個(gè)并行計(jì)算過程，如mapToPair、groupByKey等求出頻繁1項(xiàng)集，統(tǒng)計(jì)事務(wù)項(xiàng)頻繁度并按其降序排列。2)為了達(dá)到負(fù)載均衡的效果，并且保證每組相對(duì)獨(dú)立，以便后續(xù)處理更方便，要對(duì)數(shù)據(jù)進(jìn)行平衡分組。通過利用頻繁1項(xiàng)集的結(jié)果建立Hash表，按照Hash分組策略第2次掃描事務(wù)集將其分組。假設(shè)有m個(gè)節(jié)點(diǎn)，n個(gè)頻繁1項(xiàng)集，數(shù)據(jù)分解后的空間復(fù)雜度就減小到O(n/m)。3)對(duì)分組后的事務(wù)集進(jìn)行一定的并行處理后將其分配到各個(gè)節(jié)點(diǎn)單獨(dú)計(jì)算各分組的子頻繁項(xiàng)集，各節(jié)點(diǎn)從條件 FPTree分單分支和多分支兩種情況進(jìn)行本地遞歸挖掘頻繁項(xiàng)集。4)最后對(duì)各個(gè)節(jié)點(diǎn)的頻繁子集進(jìn)行匯總。其偽代碼如算法1所示。
算法1基于點(diǎn)伴隨組生成伴隨車輛組genFrequentSet。
輸入點(diǎn)伴隨組G，監(jiān)測(cè)點(diǎn)閾值δcom;
輸出伴隨車輛組數(shù)據(jù)集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)
//將事務(wù)分組到每個(gè)節(jié)點(diǎn)
7)
List(Gi)=Grouping(G， freqset_1)
8)
//在各個(gè)節(jié)點(diǎn)下運(yùn)行本地FP-Growth算法
9)
LocalFPTree(Gi，δcom，null)
10)
// 構(gòu)建項(xiàng)頭表
11)
headerTable=buildHeaderTable(Gi，δcom)
12)
//構(gòu)建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;
程序后
三、實(shí)驗(yàn)與分析
為了有效驗(yàn)證本文提出的利用分布式并行處理框架Spark實(shí)現(xiàn)的FPGrowth算法來發(fā)現(xiàn)伴隨車輛組方法的有效性，搭建了基于Spark集群的實(shí)驗(yàn)環(huán)境并進(jìn)行了多組實(shí)驗(yàn)。
3.1實(shí)驗(yàn)環(huán)境與數(shù)據(jù)
本文的Spark集群采用基于Yarn的資源調(diào)度模式，由5臺(tái)裝載CentOS release 6.4系統(tǒng)，Spark1.1.0以及 Hadoop2.3.0軟件的服務(wù)器搭建而成，內(nèi)存主節(jié)點(diǎn)配置6GB，從節(jié)點(diǎn)機(jī)器配置為3GB，其他硬件配置均相同。實(shí)驗(yàn)中采用的數(shù)據(jù)為北京市2012年11月13日到11月19日7天全天采集到的真實(shí)車牌識(shí)別數(shù)據(jù)，每天的數(shù)據(jù)記錄約970萬余條，涉及約230萬輛車，1794個(gè)道路監(jiān)測(cè)點(diǎn)，實(shí)驗(yàn)中的所有數(shù)據(jù)均存儲(chǔ)在同一個(gè)HDFS集群中。
3.2實(shí)驗(yàn)結(jié)果與分析
1)性能測(cè)試與分析。
本文方法通過在相同規(guī)模數(shù)據(jù)與硬件配置環(huán)境下，測(cè)試單機(jī)算法與并行算法在Spark集群中單個(gè)計(jì)算節(jié)點(diǎn)下的執(zhí)行時(shí)間來說明采用分布式計(jì)算的必要性，通過測(cè)試FPDTC方法在不同的并行計(jì)算框架下的執(zhí)行時(shí)間來評(píng)估該算法的性能。如測(cè)試10min、20min、…、60min時(shí)間之內(nèi)的交通數(shù)據(jù)分別在單機(jī)算法和并行算法框架下，以及分別在Hadoop和Spark框架下執(zhí)行5次的平均時(shí)間。
表1展示了單機(jī)FPGrowth算法和并行FPDTC算法Spark集群單節(jié)點(diǎn)下的實(shí)驗(yàn)結(jié)果對(duì)比。
從表1中可以看到，當(dāng)輸入數(shù)據(jù)規(guī)模很小時(shí)，并行算法處理效率低于單機(jī)FPGrowth算法，這是因?yàn)镾park集群啟動(dòng)和分配任務(wù)時(shí)需要消耗一定的時(shí)間和資源，且在總運(yùn)行時(shí)間中占據(jù)很大的比例。隨著數(shù)據(jù)規(guī)模的增長，單機(jī)算法內(nèi)存消耗增大，剩余內(nèi)存不足以支撐計(jì)算任務(wù);而并行算法由于具有良好的并行框架Spark的支持，進(jìn)行適當(dāng)?shù)膬?nèi)部資源調(diào)度，最終能夠完成計(jì)算任務(wù)。這充分說明了在單一機(jī)器模式下不足以處理和分析車牌識(shí)別大數(shù)據(jù)，利用集群并行處理數(shù)據(jù)是很有必要的。
圖4展示了在兩種不同的并行計(jì)算框架下實(shí)現(xiàn)的FPDTC算法的性能比較。從圖中可以看出，Spark實(shí)現(xiàn)的算法執(zhí)行時(shí)間明顯短于用Hadoop實(shí)現(xiàn)的算法，性能相比提升了近4倍。這是由于Spark框架的每一次迭代都是基于內(nèi)存計(jì)算的，而Hadoop則需要頻繁地讀寫磁盤，耗費(fèi)了大量的時(shí)間。還可以看到隨著數(shù)據(jù)規(guī)模的增大，前者增長幅度明顯小于后者。因此通過使用Spark框架實(shí)現(xiàn)該FPDTC方法能夠很好地解決車牌識(shí)別大數(shù)據(jù)上的伴隨車輛組發(fā)現(xiàn)問題。
2)關(guān)鍵參數(shù)影響測(cè)試與分析。
在計(jì)算伴隨車輛組的過程中，有兩個(gè)參數(shù)閾值的調(diào)整對(duì)結(jié)果具有很大的影響，分別是時(shí)間閾值δt和監(jiān)測(cè)點(diǎn)閾值δcom。
時(shí)間閾值δt是產(chǎn)生點(diǎn)伴隨組的基礎(chǔ)。首先設(shè)定數(shù)據(jù)集的時(shí)間范圍為30min，監(jiān)測(cè)點(diǎn)閾值為4，然后依次將δt設(shè)置為1min，2min，3min，…，10min，計(jì)算算法執(zhí)行5次的平均時(shí)間。
圖5展示了不同時(shí)間閾值下算法的執(zhí)行性能。隨著時(shí)間閾值的增大，算法的執(zhí)行時(shí)間成本相應(yīng)的增加，這是因?yàn)辄c(diǎn)伴隨組的數(shù)量規(guī)模也在不斷增加，此時(shí)可以通過擴(kuò)展集群節(jié)點(diǎn)的方法降低程序執(zhí)行時(shí)間。
監(jiān)測(cè)點(diǎn)閾值δcom是計(jì)算伴隨車輛組的基礎(chǔ)。為了測(cè)試其對(duì)結(jié)果的影響，設(shè)定數(shù)據(jù)集的時(shí)間范圍為30min，時(shí)間閾值為5min，監(jiān)測(cè)點(diǎn)閾值δcom為3，4，5，6，7，8。從圖6可以看出算法的執(zhí)行時(shí)間隨著監(jiān)測(cè)點(diǎn)閾值的增大而減小，這是因?yàn)槊恳淮蔚?jì)算的數(shù)據(jù)規(guī)模都變小了。
四、相關(guān)工作
雖然伴隨車輛組發(fā)現(xiàn)一直是智能交通領(lǐng)域的一個(gè)研究熱點(diǎn)，然而，基于交通大數(shù)據(jù)的集成與分析研究尚處于起始階段，本文總結(jié)了當(dāng)前的相關(guān)工作如下：
1)伴隨車輛組發(fā)現(xiàn)。近年來，移動(dòng)對(duì)象的伴隨組發(fā)現(xiàn)與查詢成為移動(dòng)對(duì)象數(shù)據(jù)管理領(lǐng)域的研究熱點(diǎn)[8]。很多研究者也提出了許多的計(jì)算方法，如Gridbased、Euclidean distance、動(dòng)態(tài)時(shí)間歸整(Dynamic Time Warping， DTW)等方法[9-11]，但在最初的研究中它們很多都缺乏對(duì)移動(dòng)對(duì)象軌跡時(shí)間屬性的考慮以及偏側(cè)重于對(duì)全球定位系統(tǒng)(GPS)數(shù)據(jù)的分析處理，并不適合位置可測(cè)但車輛對(duì)象不定的車牌識(shí)別數(shù)據(jù)，而文獻(xiàn)[4]中的伴隨車輛查詢(AVD)方法雖然適用于車牌識(shí)別數(shù)據(jù)，但是同以上方法一樣并沒有從并行化的角度來考慮算法的性能問題。
2)大數(shù)據(jù)的處理框架。隨著數(shù)據(jù)量的不斷增加，越來越多的并行編程框架被用在加速大數(shù)據(jù)的處理之中，如Hadoop框架、Dryad框架、Storm框架等，但是這些框架并不適合用來進(jìn)行迭代式計(jì)算和交互式計(jì)算。Spark是開源的類Hadoop MapReduce的通用的并行計(jì)算框架，擁有Hadoop MapReduce所具有的優(yōu)點(diǎn)，不同于MapReduce的是， job的中間輸出和結(jié)果可以保存在內(nèi)存中，從而不再需要讀寫HDFS，因此Spark能更好地適用于數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)中需要迭代的算法。
3)關(guān)聯(lián)分析領(lǐng)域的工作。當(dāng)前數(shù)據(jù)挖掘領(lǐng)域的很多算法都已經(jīng)實(shí)現(xiàn)了并行化，對(duì)于并行的關(guān)聯(lián)規(guī)則挖掘，Agrawal等在文獻(xiàn)[12] 中提出了計(jì)數(shù)分布(Count Distribution，CD)、候選分布 (Candidate Distribution，CaD) 和數(shù)據(jù)分布(Data Distribution，DD) 算法，但是這些算法對(duì)于節(jié)點(diǎn)數(shù)量的擴(kuò)展不具有很好的支持，算法在實(shí)際生產(chǎn)環(huán)境中還需要考慮多節(jié)點(diǎn)所帶來的節(jié)點(diǎn)故障、網(wǎng)絡(luò)通信故障等復(fù)雜問題。
五、結(jié)語
本文論述了在面對(duì)海量交通數(shù)據(jù)時(shí)如何利用分布式并行數(shù)據(jù)處理框架Spark來分析處理數(shù)據(jù)，并利用并行FPDTC方法來求解伴隨車輛組。本文提出了一種基于多過程并行模式的處理方法，分別從車輛軌跡生成、計(jì)算點(diǎn)伴隨組以及產(chǎn)生伴隨車輛組3個(gè)過程展開敘述，最后通過實(shí)驗(yàn)證明，該方法適用于大規(guī)模交通數(shù)據(jù)的分析與應(yīng)用。本文還有許多需要改進(jìn)的地方，比如求解伴隨車輛組時(shí)采用更加高效的求解頻繁子集的算法等。
參考文獻(xiàn)：
[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. (盧帥， 趙卓峰， 韓燕波. 一種車輛移動(dòng)對(duì)象相似軌跡查詢算法[J].計(jì)算機(jī)與數(shù)字工程，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. (方艾芬， 李先通， 蔄世明， 等. 基于關(guān)聯(lián)規(guī)則挖掘的伴隨車輛發(fā)現(xiàn)算法[J]. 計(jì)算機(jī)應(yīng)用與軟件， 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.(丁銳， 孟小峰， 楊楠. 一種高效的移動(dòng)對(duì)象相似軌跡查詢方法[J]. 計(jì)算機(jī)科學(xué)， 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.
【基于車牌識(shí)別大數(shù)據(jù)的伴隨車輛組發(fā)現(xiàn)方法】相關(guān)文章：
一種基于路測(cè)數(shù)據(jù)的基站定位方法03-07
字符結(jié)構(gòu)知識(shí)在車牌識(shí)別中的應(yīng)用03-19
實(shí)現(xiàn)基于網(wǎng)頁的數(shù)據(jù)庫數(shù)據(jù)導(dǎo)入03-18
基于修正的M距離輻射源識(shí)別方法及計(jì)算機(jī)仿真03-18
基于XMLSchema的元數(shù)據(jù)方案實(shí)現(xiàn)03-21