基于頻繁項集挖掘算法的伴隨車應用與實現

陳 瑤 桂 峰 盧 超 王 華

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

基于頻繁項集挖掘算法的伴隨車應用與實現

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

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

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

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

0 引 言

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

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

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

1 伴隨車分析

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

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

2 伴隨車應用的設計

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

圖1 伴隨車模塊設計

3 伴隨車應用的實現

3.1 數據預處理

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

1) 數據清洗

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

圖2 過車信息表中的無效數據

2) 數據規約

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

3) 數據轉換

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

圖3 基于Spark的事務數據庫生成流程

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

3.2 算法應用

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

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

a.首先讀取HDFS中的原始事務數據庫，該原始事務數據庫就是3.1節中由原始數據轉換得到。通過調用cache()函數將事務數據庫緩存在Spark集群內存。

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

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

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

e.提取上一步RDD中的key值即為頻繁1-項集，通過調用cache()函數，將其保存在集群內存中，同時將計算所得頻繁1-項集對應的Bitset數據廣播到集群的節點上。

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

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

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

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

b.根據(1)中廣播出去的數據結構，此時在Spark集群內存節點中存在頻繁k-項集的HashMap和相應的Bitset的只讀數據變量，對頻繁k-項集的RDD調用map()函數，計算得到候選頻繁(k+1)-項集和其相應的Bitset數據，并返回一個鍵值對RDD，其中key為頻繁(k+1)-項集候選集，value是其對應的Bitset。

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

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

4 成果展示

4.1 運行環境

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

表1 Spark集群的PC機配置

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

表2 集群軟件配置

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

4.2 運行效果

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

圖6 伴隨車挖掘結果

該伴隨車結果集中的每條數據格式如下：

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

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

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

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;

}

}

解析后的結果以表格的形式顯示在伴隨車的系統模塊當中，伴隨車功能實現的效果如圖7所示。

圖7 伴隨車功能展示

5 結 語

本文中提出的伴隨車功能的實現，以海量的卡口交通數據為基礎，對海量數據采用HDFS的方式進行分布式存儲，并采用基于Spark計算框架的頻繁項集挖掘算法，高效地從海量數據中進行伴隨車功能的挖掘。最終以直觀友好的界面展示在系統的伴隨車模塊當中，為交通運輸的管理者提供輔助決策的功能。由于伴隨車的挖掘結果與伴隨車功能實現實行異構平臺的交互，因此文中的方案具有良好的可擴展性。下一步將對伴隨結果的可視化工作做進一步研究，或采用processing等可視化工具進行結果展示，以豐富大數據挖掘的成果呈現。

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

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

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

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

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

[6] 蔡昌理.郫縣公安局機動車緝查布控系統設計與實現[D].成都:電子科技大學,2014.

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

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

[9] 劉亞光.實時同步云存儲客戶端的設計與實現[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。上海市科學技術委員會應用技術開發專項(2014-104)。陳瑤，碩士，主研領域：應用軟件開發。桂峰，碩士。盧超，工程師。王華，教授級高工。

TP3

A

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