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

趙秋實(shí)　史燕中　方志　蔣遂平

摘要：為從海量機(jī)動(dòng)車行駛數(shù)據(jù)中找出車輛的伴隨車輛信息，本文依據(jù)伴隨車輛的行為特點(diǎn)及關(guān)聯(lián)挖掘原理提出了一種基于頻繁項(xiàng)集的伴隨車輛檢測(cè)算法。通過分析伴隨車輛的行駛特點(diǎn)，設(shè)定頻繁項(xiàng)集的支持度和時(shí)間閾值，實(shí)現(xiàn)了從單項(xiàng)集到多項(xiàng)集的迭代過程。利用流數(shù)據(jù)處理方法，添加了針對(duì)伴隨車輛檢測(cè)的流數(shù)據(jù)處理方法，最終使算法可以快速的在海量數(shù)據(jù)中檢測(cè)到車輛的伴隨車輛信息。經(jīng)實(shí)驗(yàn)驗(yàn)證，本算法可以快速正確的檢測(cè)出車輛的伴隨車輛信息。

關(guān)鍵詞：機(jī)動(dòng)車；數(shù)據(jù)挖掘；頻繁集；伴隨車輛：大數(shù)據(jù)

中圖分類號(hào)：TP391.41 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.3969/j.issn.1003-6970.2016.04.018

0 引言

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

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

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

1 相關(guān)定義及算法原理

1.1 相關(guān)定義

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

定義2如果I是一個(gè)項(xiàng)集，I的支持度（support）是指包含I向集合T（即I？T）數(shù)量。

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

定義4伴隨車輛指在某一特定時(shí)間段內(nèi)，多個(gè)車輛一起通過多個(gè)卡點(diǎn)，且時(shí)間差小于預(yù)設(shè)時(shí)間閾值，當(dāng)檢測(cè)次數(shù)超過假定檢測(cè)閾值時(shí)，稱這些通過多個(gè)卡點(diǎn)的車輛為伴隨車輛。

1.2 算法原理

在卡點(diǎn)采集車輛行駛數(shù)據(jù)時(shí)，每采集到一條數(shù)據(jù)就傳遞到后臺(tái)服務(wù)器進(jìn)行處理和存儲(chǔ)，因此數(shù)據(jù)的存儲(chǔ)順序和時(shí)間相關(guān)，是典型的時(shí)間序列。分析伴隨車輛定義可知，若選定查找車輛A的伴隨車輛，則需要查找在一定時(shí)間內(nèi)伴隨車輛A通過多個(gè)卡點(diǎn)的車輛，假設(shè)此時(shí)有車輛B是車輛A的伴隨車輛，則在數(shù)據(jù)庫中應(yīng)有如圖1所示的數(shù)據(jù)關(guān)系：

從圖1中可以看出，特定車輛和其伴隨車輛在數(shù)據(jù)庫中具有較強(qiáng)的關(guān)聯(lián)性，大多數(shù)關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘過程可以分解為兩步：

1.頻繁項(xiàng)集產(chǎn)生：發(fā)現(xiàn)滿足最小支持度閾值的所有項(xiàng)集，即頻繁項(xiàng)集；

2.規(guī)則產(chǎn)生：從頻繁項(xiàng)集中提取具有高置信度的規(guī)則。

在這兩步中，第一步花費(fèi)了挖掘過程的大部分時(shí)間和計(jì)算量，也是算法的關(guān)鍵所在。頻繁項(xiàng)集產(chǎn)生算法基本過程為：

1.掃描數(shù)據(jù)庫，計(jì)算單項(xiàng)集支持度，生成頻繁1-項(xiàng)集L₁；

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

3.在生成頻繁項(xiàng)集的基礎(chǔ)上，得到滿足最小置信度的關(guān)聯(lián)規(guī)則。

在迭代過程中每一次擴(kuò)展都需要掃描一次數(shù)據(jù)庫，這極大的延長(zhǎng)了挖掘時(shí)間，因此需要設(shè)計(jì)減少數(shù)據(jù)庫掃描次數(shù)。在頻繁項(xiàng)集生成過程中會(huì)產(chǎn)生大量候選集，在候選項(xiàng)集和頻繁項(xiàng)集加上頻次統(tǒng)計(jì)，則候選項(xiàng)集和頻繁集即可等同于數(shù)據(jù)庫數(shù)據(jù)，因此可利用第k步生成的所有項(xiàng)集內(nèi)容及其頻次來計(jì)算生成（k+1）項(xiàng)集。即為本文中檢測(cè)伴隨車輛所使用的算法。

2 伴隨車輛頻繁項(xiàng)集挖掘算法

伴隨車輛挖掘算法利用頻繁項(xiàng)集挖掘算法。根據(jù)頻繁集挖掘方法，頻繁項(xiàng)挖掘的主要計(jì)算過程就是從k項(xiàng)集合（在機(jī)動(dòng)車數(shù)據(jù)挖掘過程中即為有k個(gè)汽車電子標(biāo)識(shí)的集合）到下（k+1）項(xiàng)集的轉(zhuǎn)移過程。對(duì)于元素?cái)?shù)目為k的集合，存在兩個(gè)頻繁項(xiàng)集集合：

（1）候選的k項(xiàng)集集合C_k，這個(gè)集合中的k項(xiàng)集需要計(jì)算后才能確定是否為真正的頻繁項(xiàng)集；

（2）大小為k的真正頻繁k項(xiàng)集L_k。

整個(gè)轉(zhuǎn)移過程由一系列構(gòu)建器和過濾器組成，如圖2所示，其中，構(gòu)建器用于產(chǎn)生候選的k項(xiàng)集集合C_k，過濾器用于產(chǎn)生真正頻繁k項(xiàng)集L_k，整個(gè)過程可以進(jìn)行到過濾器輸出的頻繁k項(xiàng)集L_k為空才結(jié)束。

在異常群組挖掘中，k項(xiàng)集表示為：

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

其中，{V₁，V₂，…，V_k}是汽車電子標(biāo)識(shí)的集合，T_b是k輛機(jī)動(dòng)車中最早到達(dá)卡點(diǎn)的時(shí)間，T_e是k輛機(jī)動(dòng)車中最后離開卡點(diǎn)的時(shí)間，S是卡點(diǎn)，C是k項(xiàng)集出現(xiàn)的次數(shù)。K=1時(shí)稱為汽車電子標(biāo)識(shí)的單項(xiàng)集，此時(shí)T_b=T_e。

構(gòu)建器k的算法和過濾器k的算法分別如算法1、算法2所示。構(gòu)建器k產(chǎn)生候選k項(xiàng)集集合C_k，過濾器k生成頻繁k項(xiàng)集L_k。在構(gòu)建器1中，初始輸入的單項(xiàng)集都是頻繁的。

算法1構(gòu)建器k算法

輸入：頻繁的k項(xiàng)集：

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

輸出：候選的（k+1）項(xiàng)集：

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

偽代碼：

1）k項(xiàng)集的{V₁，V_k，…，V_k}，T_b，T_e，S，C>隊(duì)列Q₁初始化為空

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

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

4）For each Q₂中k項(xiàng)集{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₂中已經(jīng)有{V"₁，V"₂，…，V"_k，V"_k+1}

7）Q<{₂中<{V"₁，V"₂，…，V"_k，V"_k+1}，T_b，T_e，S，C>的計(jì)數(shù)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>的計(jì)數(shù)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）項(xiàng)集：

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

輸出：頻繁的（k+1）項(xiàng)集：

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

偽代碼：

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

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

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

4.If Q₂中已經(jīng)有<{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>的計(jì)數(shù)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>的計(jì)數(shù)C≥TH_s

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

14.End if

15.End for

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

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

在整個(gè)挖掘過程中，涉及2個(gè)閾值，TH_t和TH_s。其中，TH_t是時(shí)間閾值，當(dāng)k輛機(jī)動(dòng)車在時(shí)間間隔TH_t內(nèi)出現(xiàn)在某個(gè)采集點(diǎn)時(shí)，就認(rèn)為這k輛機(jī)動(dòng)車時(shí)同時(shí)出現(xiàn)；TH_s是頻繁集的支持度，當(dāng)某個(gè)k項(xiàng)集<{V₁，V₂，…，V_k}，T_b，T_e，S>的{V₁，V₂，…，V_k}出現(xiàn)次數(shù)不小于TH_s，才認(rèn)為是頻繁的。

整個(gè)挖掘過程采用頻繁集遞增的轉(zhuǎn)移方式，在每個(gè)采集點(diǎn)，一旦有機(jī)動(dòng)車被識(shí)別到，就與前面指定時(shí)間間隔內(nèi)的其它機(jī)動(dòng)車組合成候選的2項(xiàng)集，然后逐步向k項(xiàng)集轉(zhuǎn)移，并沒有采用直接枚舉出某個(gè)采集點(diǎn)在指定時(shí)間間隔內(nèi)識(shí)別的機(jī)動(dòng)車的全部組合的方式。因?yàn)椴捎妹髅杜e指定時(shí)間間隔內(nèi)的機(jī)動(dòng)車的組合，將產(chǎn)生大量的候選數(shù)據(jù)，另外，如果兩個(gè)時(shí)間間隔有重疊，還需要消除組合枚舉中的重復(fù)，效率極低。

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

3 實(shí)驗(yàn)及結(jié)果分析

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

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

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

4 結(jié)論

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