基于頻繁集的伴隨車輛檢測算法研究

趙秋實　史燕中　方志　蔣遂平

摘要：為從海量機動車行駛數據中找出車輛的伴隨車輛信息，本文依據伴隨車輛的行為特點及關聯挖掘原理提出了一種基于頻繁項集的伴隨車輛檢測算法。通過分析伴隨車輛的行駛特點，設定頻繁項集的支持度和時間閾值，實現了從單項集到多項集的迭代過程。利用流數據處理方法，添加了針對伴隨車輛檢測的流數據處理方法，最終使算法可以快速的在海量數據中檢測到車輛的伴隨車輛信息。經實驗驗證，本算法可以快速正確的檢測出車輛的伴隨車輛信息。

關鍵詞：機動車；數據挖掘；頻繁集；伴隨車輛：大數據

中圖分類號：TP391.41 文獻標識碼：A DOI：10.3969/j.issn.1003-6970.2016.04.018

0 引言

隨著社會經濟發展，機動車普及程度迅速提高，極大地方便了人們的日常生活，但是同時也讓公安部門更難偵破以機動車為交通工具的違法犯罪活動。近年來，部分城市開始建立基于RFID汽車電子標識系統，通過在各卡點采集汽車電子標識信息，用以完成交通數據的采集與分析。相比于傳統利用攝像頭進行車牌識別的系統，其數據準確度及可信性更高。由于一個城市每天的數據量一般都超過百萬條，半年累計的數據量很容易超過了億條，通過傳統的統計學方法已經無法快速的進行處理。因此，借助大數據的數據挖掘方法對交通數據進行分析、挖掘，可以快速的尋找出交通數據中所包含的模式，對城市交通安全的保障具有重要作用。

單機動車行駛軌跡具有一定規律，多機動車行駛軌跡則會交叉重疊，所有軌跡在空間和時間上具有相似性，因此就導致伴隨車輛問題的出現。伴隨車輛發現是其中一項急待解決實際問題，針對此問題，方艾芬等人利用關聯規則進行伴隨車輛發現算法研究，通過求集合交集求出伴隨車輛，提出利用時間窗結構優化算法，但在挖掘開始前需要指定車輛才能進行計算。吳子珺等人通過生成車輛行駛軌跡，利用計算出車輛行駛過程中發現的可能伴隨的車輛頻次來計算軌跡相似度并以此判斷伴隨車輛。這兩種算法在計算伴隨車輛過程中都需要多次掃描數據庫，耗時較長，且算法從全局角度分析是采用排除法得到伴隨車輛，在此過程中有較大可能排除真實的伴隨車輛數據。因此本文綜合兩種算法特點，選擇使用頻繁項集發現算法處理不同卡點的采集數據，且在計算前不必指定車輛，可以挖掘出所有車輛的伴隨車輛信息。

頻繁項集發現是大數據處理中的一類主要技術。最早的頻繁項集發現算法Apriori于1993年由Agrawal等人提出，基于Apriori的大量改進算法和應用也隨之出現，本文算法采用了改進算法中部分的優化思想，利用頻繁項集的相關概念將伴隨檢測問題轉化為項集發現問題，并針對伴隨車輛檢測問題實現了改進的Apriori算法，通過實驗驗證了算法可以正確的完成伴隨車輛檢測，經分析算法效率更好，且也可對實時數據進行處理。

1 相關定義及算法原理

1.1 相關定義

定義1假設有集合S={s₁，s₂，…，s_n}是包含了所有項的集合，若有另一集合I是集合s的子集，即滿足I？S，則稱集合I為項集。

定義2如果I是一個項集，I的支持度（support）是指包含I向集合T（即I？T）數量。

定義3假定有支持度閾值s（support thresh-old），如果I的支持度不小于s，則稱I是頻繁項集（frequent itemset）。

定義4伴隨車輛指在某一特定時間段內，多個車輛一起通過多個卡點，且時間差小于預設時間閾值，當檢測次數超過假定檢測閾值時，稱這些通過多個卡點的車輛為伴隨車輛。

1.2 算法原理

在卡點采集車輛行駛數據時，每采集到一條數據就傳遞到后臺服務器進行處理和存儲，因此數據的存儲順序和時間相關，是典型的時間序列。分析伴隨車輛定義可知，若選定查找車輛A的伴隨車輛，則需要查找在一定時間內伴隨車輛A通過多個卡點的車輛，假設此時有車輛B是車輛A的伴隨車輛，則在數據庫中應有如圖1所示的數據關系：

從圖1中可以看出，特定車輛和其伴隨車輛在數據庫中具有較強的關聯性，大多數關聯規則的數據挖掘過程可以分解為兩步：

1.頻繁項集產生：發現滿足最小支持度閾值的所有項集，即頻繁項集；

2.規則產生：從頻繁項集中提取具有高置信度的規則。

在這兩步中，第一步花費了挖掘過程的大部分時間和計算量，也是算法的關鍵所在。頻繁項集產生算法基本過程為：

1.掃描數據庫，計算單項集支持度，生成頻繁1-項集L₁；

2.利用L₁查找頻繁2-項集L₂；并迭代查找，直到不能再擴展時，停止算法。在第k次迭代時，首先生成候選k-項集CL_k，然后掃描數據庫得到L_k。

3.在生成頻繁項集的基礎上，得到滿足最小置信度的關聯規則。

在迭代過程中每一次擴展都需要掃描一次數據庫，這極大的延長了挖掘時間，因此需要設計減少數據庫掃描次數。在頻繁項集生成過程中會產生大量候選集，在候選項集和頻繁項集加上頻次統計，則候選項集和頻繁集即可等同于數據庫數據，因此可利用第k步生成的所有項集內容及其頻次來計算生成（k+1）項集。即為本文中檢測伴隨車輛所使用的算法。

2 伴隨車輛頻繁項集挖掘算法

伴隨車輛挖掘算法利用頻繁項集挖掘算法。根據頻繁集挖掘方法，頻繁項挖掘的主要計算過程就是從k項集合（在機動車數據挖掘過程中即為有k個汽車電子標識的集合）到下（k+1）項集的轉移過程。對于元素數目為k的集合，存在兩個頻繁項集集合：

（1）候選的k項集集合C_k，這個集合中的k項集需要計算后才能確定是否為真正的頻繁項集；

（2）大小為k的真正頻繁k項集L_k。

整個轉移過程由一系列構建器和過濾器組成，如圖2所示，其中，構建器用于產生候選的k項集集合C_k，過濾器用于產生真正頻繁k項集L_k，整個過程可以進行到過濾器輸出的頻繁k項集L_k為空才結束。

在異常群組挖掘中，k項集表示為：

<{V₁，V₂，…，V_k}，T_b，T_e，S，C> （1）

其中，{V₁，V₂，…，V_k}是汽車電子標識的集合，T_b是k輛機動車中最早到達卡點的時間，T_e是k輛機動車中最后離開卡點的時間，S是卡點，C是k項集出現的次數。K=1時稱為汽車電子標識的單項集，此時T_b=T_e。

構建器k的算法和過濾器k的算法分別如算法1、算法2所示。構建器k產生候選k項集集合C_k，過濾器k生成頻繁k項集L_k。在構建器1中，初始輸入的單項集都是頻繁的。

算法1構建器k算法

輸入：頻繁的k項集：

<{V₁，V₂，…，V_k}，T_b，T_e，S，C>

輸出：候選的（k+1）項集：

<{V₁，V_k，…，V_k，V_k+1}，T_b，T_e，S，C>

偽代碼：

1）k項集的{V₁，V_k，…，V_k}，T_b，T_e，S，C>隊列Q₁初始化為空

2）（k+1）項集<{V₁，V_k，…，V_k，V_k+1}，T_b，T_e，S，C>的隊列Q₂初始化為空

3）For each輸入k項集<{V₁，V_k，…，V_k，V_k+1}，T_b'，T_e'，S>>do

4）For each Q₂中k項集{V₁，V_k，…，V'_k}，T'_b，T'_edo

5）If S=S'&&max（T_e，T'_e）-min（T_b，T'_b）≤TH_t&-&{{V₁，V₂，…，V_k}∪{V'₁，V'₂，…，V'_k}={V"₁，V"₂，…，V"_k，V”_k+1}

6）If Q₂中已經有{V"₁，V"₂，…，V"_k，V"_k+1}

7）Q<{₂中<{V"₁，V"₂，…，V"_k，V"_k+1}，T_b，T_e，S，C>的計數C增加l

8）Else

9）<{V"₁，V"₂，…，V"_k，V"_k+1}，min（T_b，T'_b），max（T_e，T'_e），S，1>加入Q₂

10）End if

11）End if

12）If<{V"₁，V"₂，…，V"_k，V"_k+1}，T_b，T_e，S，C>的計數c≥（k+2）×k/2

13）輸出<{V"₁，V"₂，…，V"_k，V"_k+1}，T_b，T_e，S，C>

14）End if

15）End for

16）End for

算法2過濾器k的算法

輸入：候選的（k+1）項集：

<{V₁，V₂，…，V_k，V_k+1}，T_b，T_e，S>

輸出：頻繁的（k+1）項集：

<{V₁，V₂，…，V_k，V_k+1}，T_b，T_e，S>

偽代碼：

1.（k+1）項集<{V₁，V₂，…，V_k，V_k+1}，T_b，T_e，S>的隊列Q₁初始化為空

2.（k+1）項集<{V₁，V₂，…，V_k，V_k+1}，T_b，T_e，S>的隊列Q₂初始化為空

3.For each輸入（k+1）項集<{V₁，V₂，…，V_k，V_k+1}，T_b，T_e，S>do

4.If Q₂中已經有<{V₁，V₂，…，V_k，V_k+1}，T_b，T_e，S>

5.Q₂中<{V₁，V₂，…，V_k，V_k+1}，T_b，T_e，C>的計數C增加1

6.Else

7.<{V₁，V₂，…，V_k，V_k+1}，T_b，T_e，C>加人Q₂

8.End if

9.<{V₁，V₂，…，V_k，V_k+1}，T_b，T_e，S>加入Q₁

10.End for

11.For each Q₁中<{V₁，V₂，…，V_k，V_k+1}，T_b，T_e，S>do

12.If Q₂中<<{V₁，V₂，…，V_k，V_k+1}，T_b，T_e，C>的計數C≥TH_s

13.輸出<{V₁，V₂，…，V_k，V_k+1}，T_b，T_e，S>

14.End if

15.End for

構建器算法中，{V₁，V₂，…，V_k}∪{V'₁，V'₂，…，V'_k}={V"₁，V"₂，…，V"_k，V"_k+1}表示將兩個分別包含k個機動車的集合并為一個包含（k+1）個機動車的集合。例如，{A，B，D}∪{A，C，D}={4，B，C，D}，但{A，B，D}和{C，D，E}則無法合并為一個包含4個機動車的集合。

構建器算法中，各個卡點S的輸入數據、處理和輸出是分離的，互不相關。因此，構建器算法完全可以并行化，為每個卡點分配一個構建器任務，并行處理，提高挖掘的速度。在實際挖掘中，各個采集點采集到的交通流數據是按時間排列，可以直接輸入到構建器1中，實現異常群組的實時挖掘。

在整個挖掘過程中，涉及2個閾值，TH_t和TH_s。其中，TH_t是時間閾值，當k輛機動車在時間間隔TH_t內出現在某個采集點時，就認為這k輛機動車時同時出現；TH_s是頻繁集的支持度，當某個k項集<{V₁，V₂，…，V_k}，T_b，T_e，S>的{V₁，V₂，…，V_k}出現次數不小于TH_s，才認為是頻繁的。

整個挖掘過程采用頻繁集遞增的轉移方式，在每個采集點，一旦有機動車被識別到，就與前面指定時間間隔內的其它機動車組合成候選的2項集，然后逐步向k項集轉移，并沒有采用直接枚舉出某個采集點在指定時間間隔內識別的機動車的全部組合的方式。因為采用明枚舉指定時間間隔內的機動車的組合，將產生大量的候選數據，另外，如果兩個時間間隔有重疊，還需要消除組合枚舉中的重復，效率極低。

在數據庫不發生變化時，每次進行計算的伴隨車輛結果都會相同。但在實際中，數據庫一直會加入新的采集數據，若每次都重新使用數據庫數據進行計算則會導致大量的重復計算。因此在實際應用時，卡口處采集的數據傳人后臺時先進行計算，之后再將數據存儲到數據庫中。計算過程是將當前的過車信息處理成為l項集<{V₁}，T_b，T_e，S>，并加入到原掃描數據庫生成的L₁中。若L₁中不存在則為<{V₁，V₂，…，V_k}，T_b，T_e，S，1>，若L₁中存在將原記錄頻次增加l。利用此方法可以實現實時數據的處理，完成實時伴隨車輛挖掘過程。

3 實驗及結果分析

我們利用實際的數據對實現的挖掘算法進行了驗證。實際數據來自于某一體育賽事中的基于RFID的汽車電子標識系統，安裝在道路上方的讀寫器在12天內采集了超過1萬輛機動車的約40萬個單項集數據。表1給出了部分原始單項集數據，其中，汽車電子標識ID是RFID標簽ID的后64比特，采集時間是1970年0時0分0秒開始的秒數。從單項集數據開始可以挖掘出頻繁同時出現的機動車。由于賽事中機動車中的行駛是成批活動的，因此理論上正確挖掘的結果會體現出這個特征。

固定頻繁集的最小支持度TH_s=5，對于單項集到2項集的挖掘，時間間隔閾值TH_t分別取30秒、25秒、20秒、15秒、10秒、5秒，表2給出了各種時間間隔下的輸入的頻繁單項集L₁數目、得到的候選2項集數目C₂，中包含的有2個機動車的集合CV₂的數目、滿足最小支持度TH_s的頻繁2項集數目L₂，L₂中包含的有2個機動車的集合LV₂的數目。從表可以看出，173271對機動車共出現了225513次，被認為是“頻繁”的只有2419對，它們共出現了23532次；此外，隨著時間間隔的減少，C₂和L₂的數目也在減少，這與實際情況一致。

固定頻繁集的最小支持度TH_s=5秒，時間間隔閾值TH_t=30秒，得到的挖掘結果見表3。從表3可知，隨著k值的增大，頻繁k項集L_k的數目也隨著下降，這與實際情況符合。

4 結論

本文根據汽車電子標識系統中對伴隨車輛檢測的需求，提出了基于頻繁項集的伴隨車輛挖掘算法，通過實際數據測試證明了算法的有效性。相比于以前的伴隨車輛檢測算法，本文算法在總體上是增量變化，因此算法可靠性更高。且當數據發生變化時只需將新數據加入到1項集的頻次中，不需要再次掃描數據庫，節省了大量時間，適用于實時數據挖掘。由于構建器算法在本質上是并行，因此，將其改進為Map/Reduce計算模式，完全可以適合于實時伴隨車輛檢測和多目標的伴隨車輛檢測。