基于頻繁項集挖掘算法的伴隨車應(yīng)用與實現(xiàn)

陳 瑤 桂 峰 盧 超 王 華

1(上海市計算技術(shù)研究所 上海 200040)2(同濟大學電子與信息工程學院 上海 201800)

基于頻繁項集挖掘算法的伴隨車應(yīng)用與實現(xiàn)

陳 瑤1桂 峰2盧 超1王 華1

1(上海市計算技術(shù)研究所 上海 200040)2(同濟大學電子與信息工程學院 上海 201800)

隨著大數(shù)據(jù)技術(shù)的發(fā)展和交通數(shù)據(jù)量迅速膨脹的挑戰(zhàn)，對海量交通數(shù)據(jù)進行伴隨車挖掘已然成為研究熱點。提出一種基于Spark計算框架的頻繁項集挖掘算法應(yīng)用于伴隨車挖掘模塊當中，對海量的卡口交通數(shù)據(jù)進行Hadoop分布式文件存儲(HDFS)，并將伴隨車挖掘結(jié)果可視化地展示在集成系統(tǒng)當中。以實際項目為依托，從而驗證該伴隨車模塊的實現(xiàn)具有實際意義，并可為交通管理者提供科學的輔助決策。

HDFS Spark計算框架 頻繁項集挖掘 伴隨車

0 引 言

隨著交通系統(tǒng)中硬件設(shè)施的逐年更新和完善以及道路卡口識別系統(tǒng)的廣泛應(yīng)用，使得前端卡口設(shè)備采集的數(shù)據(jù)量越來越龐大。據(jù)統(tǒng)計，在北京、上海、廣州等這些交通繁忙的一線城市中，一些交通要道卡口位置的平均車流量為3 000輛/小時，一個交通卡口一天的數(shù)據(jù)采集量可達到6萬條。以上海某區(qū)為例，該區(qū)有42個卡口位置，每天該區(qū)卡口過車數(shù)據(jù)采集量可達100萬條。由此可見，卡口設(shè)備采集數(shù)據(jù)已經(jīng)進入大數(shù)據(jù)時代。

由于車輛相關(guān)的刑事案件和治安案件的發(fā)現(xiàn)呈現(xiàn)逐年上升的趨勢，如何從多源動態(tài)的海量交通數(shù)據(jù)中挖掘有價值的信息，為治安管理者提供決策支持的方案，已成為當前交通領(lǐng)域研究的熱點和重點，其中對伴隨車挖掘已然成為一個重要的應(yīng)用方向。方艾芬等提出一種基于FP-Tree關(guān)聯(lián)規(guī)則的伴隨車挖掘算法，該方法在內(nèi)存中構(gòu)造FP-Tree，當數(shù)據(jù)規(guī)模龐大時，會對內(nèi)存造成較大壓力[1]。曹波等提到基于Spark框架的FP-Growth算法進行伴隨車挖掘，相較于方艾芬提出的方法，盡管緩解了內(nèi)存壓力，然而其產(chǎn)生頻繁子集的效率不高[2]。張笑達等提到一種矩陣剪枝的頻繁項集挖掘算法，該算法根據(jù)預(yù)判條件，有效地避免產(chǎn)生冗余候選頻繁項集[3]。然而對于數(shù)據(jù)集龐大的事務(wù)數(shù)據(jù)庫，無法進行分布式算法的運算，從而降低了算法的效率。

綜上所述，本文旨在探討伴隨車功能的應(yīng)用與實現(xiàn)，將一種改進的關(guān)聯(lián)規(guī)則算法——基于Spark的頻繁項集挖掘算法應(yīng)用于伴隨車的挖掘，并結(jié)合Hadoop大數(shù)據(jù)平臺對海量交通卡口數(shù)據(jù)采用分布式文件系統(tǒng)的方式存儲，最后將伴隨車挖掘結(jié)果以直觀、簡潔的可視化方式呈現(xiàn)。本文針對數(shù)據(jù)、算法、視圖這幾個層次，分別從伴隨車分析、設(shè)計、實現(xiàn)、以及成果展示幾個部分，闡述了伴隨車功能的應(yīng)用實現(xiàn)，并最終以實際項目為依托，驗證了該設(shè)計方法的可行性與實際意義。

1 伴隨車分析

伴隨車是一個交通術(shù)語，是指在規(guī)定的時間段內(nèi)，與追查車輛存在伴隨關(guān)系的車輛以一定概率存在時，且該概率大于設(shè)定的概率閾值，則該具有伴隨關(guān)系的車輛即為追查車輛的伴隨車[2]。由伴隨車的定義可知，要判斷兩輛車之間是否有伴隨關(guān)系，首先要根據(jù)卡口設(shè)備識別出來的車牌信息，規(guī)定在一定的時間范圍內(nèi)(既定義中的時間閾值)，經(jīng)過相同監(jiān)測地點的車輛集合，均視為存在伴隨關(guān)系。例如車輛A，規(guī)定的時間閾值為5分鐘，如果A經(jīng)過某一個方向的路口的時間是18:00，那么在17:55到18:05之間經(jīng)過相同方向、相同路口的車B視為一次伴隨關(guān)系。當車輛A和車輛B存在伴隨關(guān)系次數(shù)的頻次達到一定高度時，可確定A和B是嫌疑伴隨車輛。

所以，伴隨車的查找實際上可以轉(zhuǎn)化為數(shù)據(jù)挖掘中頻繁項集挖掘的問題[4]。從海量的原始過車數(shù)據(jù)中查找出頻繁出現(xiàn)的車輛集合，通過設(shè)定的最小支持數(shù)(即是最少伴隨次數(shù))，從而篩查出嫌疑伴隨的車輛集合。

2 伴隨車應(yīng)用的設(shè)計

伴隨車的挖掘模塊是基于Hadoop平臺實現(xiàn)的，因此將原始卡口交通數(shù)據(jù)的文本文件以Hadoop分布式文件系統(tǒng)HDFS的方式保存，做為底層的數(shù)據(jù)服務(wù)層支持分布式運算。基于對引言中前人對頻繁項集算法的研究，并以實際課題項目的海量卡口數(shù)據(jù)為基礎(chǔ)，本方案中算法層采用基于Spark的矩陣剪枝頻繁項集挖掘算法。因為Spark計算框架的并行化機制，可以使算法結(jié)果緩存于集群的內(nèi)存當中，有效地避免大量磁盤I/O操作。矩陣剪枝的頻繁子集挖掘可以減少冗余候選頻繁項集產(chǎn)生，緩解內(nèi)存壓力，提高算法效率[5]。最后通過異構(gòu)平臺的結(jié)果解析，反饋伴隨車挖掘結(jié)果。因此伴隨車應(yīng)用的設(shè)計方案如圖1所示。

圖1 伴隨車模塊設(shè)計

3 伴隨車應(yīng)用的實現(xiàn)

3.1 數(shù)據(jù)預(yù)處理

本文基于實際課題項目，以上海某區(qū)的卡口數(shù)據(jù)為基礎(chǔ)示范數(shù)據(jù)。該原始卡口交通數(shù)據(jù)存儲在Oracle數(shù)據(jù)庫當中，包括過車信息表、卡口位置表、卡口設(shè)備信息表等27張表，其中最主要的過車信息表是一張動態(tài)表，包括車牌信息、車輛顏色、過車時間、過車速度、卡口編號、卡口方向、等20多個字段。該表實時接受并存儲前端卡口設(shè)備采集的過車信息[6]。

1) 數(shù)據(jù)清洗

車牌識別技術(shù)是伴隨車挖掘的基礎(chǔ)，由于前端設(shè)備受天氣等各方面因素的影響，無法保證百分之百正確識別車牌，因此將對過車信息表中一些無用車輛信息從數(shù)據(jù)庫中清洗掉。在原始數(shù)據(jù)庫中，車牌號為“000000”以及“無車牌”的過車數(shù)據(jù)均視為無效數(shù)據(jù)，如圖2所示，方框內(nèi)的數(shù)據(jù)均是無效的過車數(shù)據(jù)。

圖2 過車信息表中的無效數(shù)據(jù)

2) 數(shù)據(jù)規(guī)約

伴隨車挖掘過程中，只需要過車信息表中車牌號碼、卡口編號和過車時間這三個字段，因此需將這三個字段從過車信息表中提取出來，以空格分隔，并將數(shù)據(jù)保存在文件中。

3) 數(shù)據(jù)轉(zhuǎn)換

基于Spark的伴隨車挖掘算法要求將原始的一條條過車數(shù)據(jù)轉(zhuǎn)換成原始事務(wù)數(shù)據(jù)庫中的事務(wù)。轉(zhuǎn)換規(guī)則是：對于任意某輛車，將與其經(jīng)過同一個卡口和相同方向的前后1 min內(nèi)的車輛集合做為一條事務(wù)。在Spark平臺下生成的原始事務(wù)數(shù)據(jù)庫流程如圖3所示。

圖3 基于Spark的事務(wù)數(shù)據(jù)庫生成流程

首先通過調(diào)用textFile()函數(shù)讀取HDFS上的原始過車數(shù)據(jù)，得到一個彈性分布式數(shù)據(jù)RDD(Resilient Distributed Datasets)，該RDD中的每個元素是由車牌號碼、卡口編號和過車時間組成的三元組(id,n,t)；其次通過調(diào)用map()函數(shù)，將上述三元組轉(zhuǎn)換成一個key-value鍵值對，其中key對應(yīng)三元組中的卡口編號n，value值是由車牌號碼和過車時間組成的二元組(id,t)，從而獲得一個包含鍵值對的RDD；然后通過groupByKey()函數(shù)的調(diào)用，將上一步中得到的鍵值對RDD按照key值(即卡口編號)進行分組，得到另一個包含鍵值對的RDD，該鍵值對中的key值即為卡口編號，value值為該卡口編號方向的所有車牌號碼n及其過車時間t所組成的二元組；最后調(diào)用mapPratitions()函數(shù)，按照轉(zhuǎn)換規(guī)則，最終得到一個事務(wù)RDD，該事務(wù)RDD中的每個元素即為一個伴隨關(guān)系的車輛集合。至此便完成了原始過車數(shù)據(jù)到事務(wù)數(shù)據(jù)的轉(zhuǎn)換。

3.2 算法應(yīng)用

伴隨車的挖掘算法采用基于Spark的矩陣剪枝頻繁項集挖掘算法，該算法依據(jù)傳統(tǒng)關(guān)聯(lián)規(guī)則Apriori算法進行改進[7]。為降低內(nèi)存占用，本方案使用BitSet數(shù)據(jù)結(jié)構(gòu)表示事務(wù)數(shù)據(jù)庫中每個項目的支持數(shù)，同時結(jié)合矩陣剪枝的挖掘特點，在產(chǎn)生候選頻繁k-項集矩陣M時(k>1)，采用HashMap數(shù)據(jù)結(jié)構(gòu)代替矩陣M右上角的元素。算法的挖掘過程分為兩步：

(1) 計算頻繁1-項集和2-項集矩陣。如圖4所示為伴隨車挖掘算法的步驟一。

a.首先讀取HDFS中的原始事務(wù)數(shù)據(jù)庫，該原始事務(wù)數(shù)據(jù)庫就是3.1節(jié)中由原始數(shù)據(jù)轉(zhuǎn)換得到。通過調(diào)用cache()函數(shù)將事務(wù)數(shù)據(jù)庫緩存在Spark集群內(nèi)存。

b.調(diào)用flatmap()函數(shù)，可以得到一個存儲項目的RDD，這個RDD邏輯上包含事務(wù)數(shù)據(jù)庫的全部事務(wù)。

c.通過調(diào)用reduceByKey()函數(shù)可以計算每個項目在原始事務(wù)數(shù)據(jù)庫中的支持數(shù)，得到一個存儲的RDD，其中value值為項目在事務(wù)數(shù)據(jù)庫中實際的支持數(shù)，得到了鍵值對的RDD。

d.對上一步中的RDD執(zhí)行filter()函數(shù)，該函數(shù)通過value值與最小支持數(shù)s對比，找出符合要求的鍵值對，并按照value值升序排列獲得一個有序的RDD。

e.提取上一步RDD中的key值即為頻繁1-項集，通過調(diào)用cache()函數(shù)，將其保存在集群內(nèi)存中，同時將計算所得頻繁1-項集對應(yīng)的Bitset數(shù)據(jù)廣播到集群的節(jié)點上。

f.根據(jù)上一步中廣播的Bitset數(shù)據(jù)，計算2-項集矩陣M，如前文中討論的，此處的矩陣M采用HashMap數(shù)據(jù)結(jié)構(gòu)形式存儲其上三角的數(shù)據(jù)。該HashMap鍵值對是一個嵌套的HashMap結(jié)構(gòu)，其中的key值為頻繁1-項集，value值仍是一個HashMap數(shù)據(jù)，內(nèi)部這個HashMap的鍵值對中，key為可能組合成為頻繁2-項集的候選頻繁1-項集，value為這個候選頻繁2-項集的支持度計數(shù)[8]。最后將該嵌套HashMap數(shù)據(jù)結(jié)構(gòu)的Bitset廣播到集群節(jié)點，以支持后續(xù)計算使用。

圖4 伴隨車挖掘算法步驟(一)

(2) 由頻繁k-項集集合迭代計算出頻繁(k+1)-項集集合(k≥1)，直到算法停止。如圖5為伴隨車挖掘算法的步驟二。

a.首先判斷頻繁k-項集集合Lk中的個數(shù)是否大于等于k+1，此為計算頻繁(k+1)-項集的前提條件。若判斷成立，則算法繼續(xù)執(zhí)行，否則算法過程終止，算法結(jié)束。

b.根據(jù)(1)中廣播出去的數(shù)據(jù)結(jié)構(gòu)，此時在Spark集群內(nèi)存節(jié)點中存在頻繁k-項集的HashMap和相應(yīng)的Bitset的只讀數(shù)據(jù)變量，對頻繁k-項集的RDD調(diào)用map()函數(shù)，計算得到候選頻繁(k+1)-項集和其相應(yīng)的Bitset數(shù)據(jù)，并返回一個鍵值對RDD，其中key為頻繁(k+1)-項集候選集，value是其對應(yīng)的Bitset。

c.對上一步中產(chǎn)生的候選(k+1)-項集RDD調(diào)用filter函數(shù)和map函數(shù)，篩選出支持數(shù)不小于最小支持數(shù)s的頻繁項，這里通過計算Bitset中“1”的個數(shù)大于等于s即可，最終得到邏輯上存儲頻繁(k+1)-項集的RDD。

圖5 伴隨車挖掘算法步驟(二)

4 成果展示

4.1 運行環(huán)境

伴隨車的挖掘所需要的Spark集群環(huán)境由3臺高配置的PC機組成。部署模式為Standalone，即ClusterManager為Standalone模式。部署過程中我們將Master節(jié)點的PC機同時賦予其Worker節(jié)點角色，可以使得集群中增加一個Worker工作節(jié)點。每套機器的配置如表1所示。

表1 Spark集群的PC機配置

伴隨車的挖掘算法需要Hadoop組件中的HDFS提供數(shù)據(jù)存儲，因此還需搭建Hadoop集群，算法挖掘集群的軟件配置如表2所示。

表2 集群軟件配置

伴隨車數(shù)據(jù)文件存放在本地電腦根目錄下的文件夾“AccompanyCar”中，該文件夾中一共有82個數(shù)據(jù)文本，對應(yīng)某區(qū)的82個交通卡口數(shù)據(jù)采集設(shè)備。在客戶端通過Hadoop命令“hadoop fs -mkdir /accompanycar_input”在HDFS文件系統(tǒng)下建立一個伴隨車輸入文件夾，然后利用“hadoop fs-copyFromLocal/AccompanyCar/* /accompanycar_input”將本地伴隨車輸入數(shù)據(jù)上傳到HDFS文件系統(tǒng)中[9]。

4.2 運行效果

伴隨車挖掘的結(jié)果集是保存在本地的一個文件當中，其挖掘結(jié)果如圖6所示。

圖6 伴隨車挖掘結(jié)果

該伴隨車結(jié)果集中的每條數(shù)據(jù)格式如下：

車牌號car1：([與car1形成伴隨關(guān)系的車輛集合]+伴隨次數(shù))

即以車牌“京GS3006”為例，伴隨車的結(jié)果為([滬FU6527，滬B52710，…滬DK5578，京GS3006]，7)時，則表示車牌為滬FU6527和滬DK5578等車輛集與“京GS3006”的車輛有7次伴隨關(guān)系，故被檢索為具有伴隨嫌疑的車輛。

在對伴隨車結(jié)果進行可視化時，我們采用B/S結(jié)構(gòu)，使用Java語言在Eclipse平臺進行開發(fā)，對伴隨車挖掘結(jié)果文件進行解析，解析的關(guān)鍵代碼如下：

BufferedReader br=null;

try{

br = new BufferedReader(new InputStreamReader(new

FileInputStream(request.getSession().getServletContext().

getRealPath(″″)+″/upload/car.txt″), ″UTF-8″));

while(br.ready()){

line=br.readLine();

_carName=_line.substring(0,_line.indexOf(″([″));

followcar=_line.substring(_line.indexOf(″([″)).split

(″),([″);

for(i=0;i

followcars=followcar[i].replace(″([″, ″″).split(″],″);

_c+=″″+

followcars[0]+″″+followcars[1].replace(″)″,

″″)+″″;

}

}

br.close();

}finally{

if(br!=null){

br.close();

br=null;

}

}

解析后的結(jié)果以表格的形式顯示在伴隨車的系統(tǒng)模塊當中，伴隨車功能實現(xiàn)的效果如圖7所示。

圖7 伴隨車功能展示

5 結(jié) 語

本文中提出的伴隨車功能的實現(xiàn)，以海量的卡口交通數(shù)據(jù)為基礎(chǔ)，對海量數(shù)據(jù)采用HDFS的方式進行分布式存儲，并采用基于Spark計算框架的頻繁項集挖掘算法，高效地從海量數(shù)據(jù)中進行伴隨車功能的挖掘。最終以直觀友好的界面展示在系統(tǒng)的伴隨車模塊當中，為交通運輸?shù)墓芾碚咛峁┹o助決策的功能。由于伴隨車的挖掘結(jié)果與伴隨車功能實現(xiàn)實行異構(gòu)平臺的交互，因此文中的方案具有良好的可擴展性。下一步將對伴隨結(jié)果的可視化工作做進一步研究，或采用processing等可視化工具進行結(jié)果展示，以豐富大數(shù)據(jù)挖掘的成果呈現(xiàn)。

[1] 方艾芬,李先通,蔄世明,等.基于關(guān)聯(lián)規(guī)則挖掘的伴隨車輛發(fā)現(xiàn)算法[J].計算機應(yīng)用與軟件,2012,29(2):94-96,144.

[2] 曹波,韓燕波,王桂玲.基于車牌識別大數(shù)據(jù)的伴隨車輛組發(fā)現(xiàn)方法[J].計算機應(yīng)用,2015,35(11):3203-3207.

[3] 張笑達,徐立臻.一種改進的基于矩陣的頻繁項集挖掘算法[J].計算機技術(shù)與發(fā)展,2010,20(4):93-96.

[4] 陳慧萍,王建東,王煜.一種高效的最大頻繁項集挖掘算法DFMFI-Miner[J].計算機仿真,2006,23(7):79-83.

[5] 吳湘華,張祖平.Apriori算法中頻繁項集求法的改進[J].科技創(chuàng)新與應(yīng)用,2013(15):58.

[6] 蔡昌理.郫縣公安局機動車緝查布控系統(tǒng)設(shè)計與實現(xiàn)[D].成都:電子科技大學,2014.

[7] 張忠平,李巖,楊靜.基于矩陣的頻繁項集挖掘算法[J].計算機工程,2009,35(1):84-86.

[8] 鄭志嫻.基于云計算的Apriori算法設(shè)計[J].莆田學院學報,2014,21(5):61-64.

[9] 劉亞光.實時同步云存儲客戶端的設(shè)計與實現(xiàn)[D].大連:大連理工大學,2014.

APPLICATION AND REALIZATION OF ESCORT VEHICLE BASED ON FIM ALGORITHM

Chen Yao1Gui Feng2Lu Chao1Wang Hua1

1(ShanghaiInstituteofComputingTechnology,Shanghai200040,China)2(SchoolofElectronicsandInformationEngineering,TongjiUniversity,Shanghai201800,China)

With the development of big data technology and the challenge of the rapid expansion of traffic data, escort vehicle data mining to the massive traffic data has become a hot research area. In this paper, a frequent itemset mining (FIM) algorithm based on Spark computing framework is proposed, which is applied to the escort vehicle mining module, using HDFS to store the massive traffic bayonet data and visualization display the result of escort vehicle mining in the integrated system. Based on the actual project, this paper proves that the verification of the escort vehicle mining module has practical significance, and can provide scientific auxiliary decision for the traffic management.

HDFS Spark computing framework FIM Escort vehicle

2016-03-31。上海市科學技術(shù)委員會應(yīng)用技術(shù)開發(fā)專項(2014-104)。陳瑤，碩士，主研領(lǐng)域：應(yīng)用軟件開發(fā)。桂峰，碩士。盧超，工程師。王華，教授級高工。

TP3

A

10.3969/j.issn.1000-386x.2017.04.011