王保全，蔣同海，周 喜，馬 博，趙 凡

(1.中國科學(xué)院 新疆理化技術(shù)研究所，烏魯木齊 830011； 2.中國科學(xué)院大學(xué)，北京 100049；3.新疆理化技術(shù)研究所 新疆民族語音語言信息處理實(shí)驗(yàn)室，烏魯木齊 830011)

類自動(dòng)車牌識(shí)別軌跡數(shù)據(jù)的伴隨車輛組挖掘

王保全1,2,3，蔣同海1,3*，周 喜1,3，馬 博1,3，趙 凡1,3

(1.中國科學(xué)院 新疆理化技術(shù)研究所，烏魯木齊 830011； 2.中國科學(xué)院大學(xué)，北京 100049；3.新疆理化技術(shù)研究所 新疆民族語音語言信息處理實(shí)驗(yàn)室，烏魯木齊 830011)

自動(dòng)車牌識(shí)別(ANPR)數(shù)據(jù)比私人全球定位系統(tǒng)(GPS)數(shù)據(jù)更易獲得，且包含更有用的信息，但是相對(duì)成熟的針對(duì)GPS軌跡數(shù)據(jù)挖掘伴隨車輛組方法并不適用于自動(dòng)車牌識(shí)別數(shù)據(jù)，現(xiàn)有的少量自動(dòng)車牌識(shí)別數(shù)據(jù)伴隨車輛組挖掘算法存在重視軌跡相似而忽視時(shí)間因素的缺陷，因此提出一種基于軌跡特征的聚類方法挖掘伴隨車輛組。針對(duì)自動(dòng)車牌識(shí)別數(shù)據(jù)中采樣點(diǎn)固定而采樣時(shí)間不定的特點(diǎn)，通過軌跡中共現(xiàn)的次數(shù)判定兩個(gè)對(duì)象構(gòu)成伴隨模式。該共現(xiàn)定義引入豪斯多夫距離，綜合考慮軌跡的地點(diǎn)、方向和時(shí)間特征，旨在挖掘數(shù)據(jù)中采樣點(diǎn)不同但采樣點(diǎn)距離近且軌跡相似的伴隨車輛組，以此提高伴隨車輛組挖掘效率。實(shí)驗(yàn)結(jié)果表明，所提方法較現(xiàn)有方法更能有效挖掘伴隨車輛組，識(shí)別非伴隨模式數(shù)據(jù)，效率提升了近兩倍。

自動(dòng)車牌識(shí)別軌跡數(shù)據(jù)；伴隨車輛組；基于密度的空間聚類；豪斯多夫距離；共現(xiàn)

0 引言

感應(yīng)器、位置捕獲和跟蹤設(shè)備的廣泛使用產(chǎn)生了大量的全球定位系統(tǒng)(Global Positioning System, GPS)數(shù)據(jù)，但是個(gè)人的GPS數(shù)據(jù)具有私密性，往往不易獲得，而近幾年圖像識(shí)別技術(shù)的極大發(fā)展使交通系統(tǒng)卡口自動(dòng)車牌識(shí)別(Automatic Number Plate Recognition, ANPR)[1]數(shù)據(jù)的可靠性大幅增強(qiáng)，且ANPR數(shù)據(jù)較GPS數(shù)據(jù)更易獲得，包含的信息也更有價(jià)值。伴隨車輛組是指具有相同或者相似軌跡的車輛群組，這種信息與人的關(guān)系緊密，可用于群體發(fā)現(xiàn)、頻繁路徑挖掘以及異常檢測。挖掘GPS數(shù)據(jù)伴隨模式的方法很多，并取得了長足的發(fā)展，然而ANPR數(shù)據(jù)與GPS數(shù)據(jù)相比具有采樣點(diǎn)固定而時(shí)間戳不同的特點(diǎn)，在ANPR數(shù)據(jù)上應(yīng)用GPS數(shù)據(jù)的挖掘方法需要作出一些修改，甚至有的方法并不適用。另外類ANPR數(shù)據(jù)伴隨模式挖掘的研究還比較少，現(xiàn)有的少數(shù)的針對(duì)類ANPR數(shù)據(jù)伴隨模式挖掘的方法也存在性能上的缺陷。因此本文提出一種針對(duì)類ANPR軌跡數(shù)據(jù)共現(xiàn)次數(shù)特征的方法(Trajectory Based Density-Based Spatial Clustering of Applications with Noise，TB-DBSCAN)挖掘軌跡數(shù)據(jù)中采樣點(diǎn)不同但采樣點(diǎn)距離近且軌跡相似的伴隨車輛組。本文的主要貢獻(xiàn)是：1)借鑒GPS軌跡數(shù)據(jù)相似度計(jì)算方法，提出一種新的方法衡量類ANPR軌跡數(shù)據(jù)中共現(xiàn)的次數(shù)作為軌跡的相似度，該方法綜合考慮了ANPR軌跡的地點(diǎn)、方向和時(shí)間特征。2) 基于軌跡的相似度，運(yùn)用基于密度的空間聚類(Density-Based Spatial Clustering of Applications with Noise,DBSCAN)算法[2]方法有效挖掘類ANPR數(shù)據(jù)的伴隨車輛組。

1 研究現(xiàn)狀

挖掘軌跡數(shù)據(jù)伴隨模式的研究從數(shù)據(jù)類型可以分為兩類：基于GPS數(shù)據(jù)和基于ANPR數(shù)據(jù)。

1.1 基于GPS數(shù)據(jù)

伴隨模式是指具有相同或者相似軌跡的移動(dòng)對(duì)象群體，伴隨模式的定義經(jīng)歷了從Flock[3]、Convoy[4]到Swarm[5]的衍變，這三者的區(qū)別主要在于“相近的空間距離”以及“共同移動(dòng)一段時(shí)間”這兩個(gè)概念定義上的區(qū)別。

構(gòu)成伴隨模式的移動(dòng)對(duì)象其軌跡是相似的，那么可以通過衡量軌跡的相似度挖掘伴隨模式[6]。CPD(Closest-Pair Distance)以軌跡間歐氏距離[7]的最小值作為軌跡間的距離；SPD(Sum-of-Pairs Distance)[8]使用兩條軌跡對(duì)應(yīng)點(diǎn)的距離之和衡量兩條軌跡的相似度，要求兩條軌跡具有相同長度或者截取相同長度; 但是這一約束在應(yīng)用中難以實(shí)現(xiàn)，DTW(Dynamic Time Wrapping)[9]改善這一約束，其基本思想是可以對(duì)某些點(diǎn)重復(fù)多次以獲得最優(yōu)的點(diǎn)與點(diǎn)的對(duì)應(yīng)效果，再通過對(duì)應(yīng)點(diǎn)歐氏距離計(jì)算軌跡相似度。以上方法將每一個(gè)點(diǎn)都看作正常的數(shù)據(jù)，但是現(xiàn)實(shí)中噪聲數(shù)據(jù)往往是不可避免的，如何降低噪聲數(shù)據(jù)對(duì)結(jié)果的影響也是不可忽視的問題。將軌跡數(shù)據(jù)看作一個(gè)序列，找出其中最長共同子序列(Longest Common Sub Sequence，LCSS)[10]，則可衡量軌跡的相似程度，這個(gè)方法需要一個(gè)匹配閾值α和一個(gè)時(shí)間閾值β，由于不需要軌跡中所有的點(diǎn)都有匹配，這在一定程度上降低了噪聲的影響。與LCSS尋找最長共同子序列相反，實(shí)時(shí)序列編輯距離(Edit Distance on Real Sequence，EDR)[11]借鑒編輯距離的思想，通過軌跡中不同部分的大小來衡量軌跡的相似程度。ERP(Edit distance with Real Penalty)算法[12]則綜合了DTW算法和EDR算法，該算法使用恒定參考點(diǎn)計(jì)算距離。

利用最小邊界矩形(Minimum Bounding Rectangle, MBR)[13]計(jì)算軌跡的距離主要考慮軌跡端點(diǎn)，軌跡距離就是構(gòu)成最小邊界矩形的距離，如圖1(a)所示。計(jì)算方法如下：

DMBR=

Δ([xl，xu]，[xl′，xu′])=

將豪斯多夫距離(Hausdorff Distance)運(yùn)用在軌跡距離方面就產(chǎn)生了軌跡豪斯多夫距離(Trajectory-Hausdorff Distance)[14]，如圖1(b)所示，該方法對(duì)軌跡中的每一段作如下處理：

DHausdorff=ω1d⊥+ω2d‖+ω3dθ

圖1 距離圖示Fig. 1 Distance description

最小邊界矩形距離與豪斯多夫距離相比，豪斯多夫距離的計(jì)算較為復(fù)雜，最小邊界矩形距離只考慮軌跡段的端點(diǎn)，豪斯多夫距離還考慮了軌跡段的方向差異與長度差異，更能標(biāo)識(shí)軌跡間的相似度。而在伴隨車輛組的挖掘中，軌跡段端點(diǎn)相同并不代表軌跡中移動(dòng)對(duì)象的伴隨，因此豪斯多夫距離更適用于伴隨車輛組的挖掘。

1.2 基于ANPR數(shù)據(jù)

Convy[4]的概念也可用于ANPR數(shù)據(jù)，文獻(xiàn)[1]中將Convy的概念引入ANPR數(shù)據(jù)，并運(yùn)用聚類的方法挖掘伴隨車輛組。

挖掘ANPR數(shù)據(jù)中的伴隨模式，符合伴隨模式的移動(dòng)對(duì)象在多個(gè)采樣點(diǎn)共現(xiàn)，這些采樣點(diǎn)構(gòu)成的序列在這組移動(dòng)對(duì)象的軌跡中是頻繁的，將挖掘伴隨車輛組轉(zhuǎn)化為利用關(guān)聯(lián)分析算法挖掘軌跡序列頻繁模式。利用FP-Growth算法結(jié)合滑動(dòng)時(shí)間窗口[15-16]以減少階段數(shù)據(jù)量挖掘伴隨車輛組取得較好的效果，F(xiàn)P-DTC(FP-Growth to Discover Travelling Companions)[17]算法通過Spark框架優(yōu)化了FP-Growth算法。但是對(duì)于ANPR數(shù)據(jù)，該類方法以移動(dòng)對(duì)象作為索引將ANPR數(shù)據(jù)轉(zhuǎn)化為事務(wù)集[16]進(jìn)行挖掘有兩個(gè)缺點(diǎn)：1)任意兩個(gè)對(duì)象其軌跡數(shù)據(jù)往往只有一小部分軌跡序列相同，也就是共享前綴少，那么構(gòu)建FP-Tree就需要為每條事物建立分支，造成內(nèi)存的大量消耗。2)挖掘不同時(shí)間段的ANPR軌跡數(shù)據(jù)，都需要轉(zhuǎn)化為事務(wù)集并重新構(gòu)建FP-Tree，頻繁地構(gòu)建FP-Tree則造成效率降低。

點(diǎn)伴隨[18]則以一個(gè)采樣點(diǎn)(如一個(gè)攝像頭)的數(shù)據(jù)作為挖掘單元來挖掘動(dòng)態(tài)ANPR數(shù)據(jù)的伴隨車輛組，但是對(duì)同一個(gè)伴隨車輛組的對(duì)象分別通過距離特別相近的采樣點(diǎn)(比如并行車道的兩個(gè)攝像頭)的情形不能有效挖掘，缺乏對(duì)采樣點(diǎn)距離的考慮。

2 挖掘伴隨模式

2.1 問題定義及分析

圖2 類ANPR軌跡中的伴隨模式Fig. 2 Accompanying model in analogous ANPR trajectories

這樣的軌跡在現(xiàn)實(shí)生活中符合伴隨模式，但是點(diǎn)伴隨方法對(duì)于這樣的數(shù)據(jù)并不能有效地挖掘。因此本文提出基于軌跡共現(xiàn)次數(shù)的軌跡相似度，其中引入軌跡豪斯多夫距離處理距離特別相近的采樣點(diǎn)，豪斯多夫距離不僅衡量了采樣點(diǎn)的地理距離，同時(shí)可以考慮采樣點(diǎn)周圍軌跡的相似度?；谠撓嗨贫龋\(yùn)用DBSCAN方法進(jìn)行聚類，與FP-Growth方法相比具有較優(yōu)的效率。圖3為本文方法的總體流程。

圖3 TB-DBSCAN總體流程Fig. 3 Overall flow of TB-DBSCAN

2.2 計(jì)算軌跡相似度

算法1 計(jì)算軌跡相似度。

輸出 軌跡間的共現(xiàn)次數(shù)。

1)

returnn

2)

n=0

n=n+1

//計(jì)算在時(shí)間差閾值τ內(nèi)的點(diǎn)構(gòu)成的豪斯多夫距離

n=n+1

returnn

2.3 移動(dòng)對(duì)象聚類

軌跡相似程度作為移動(dòng)對(duì)象之間的距離，可以對(duì)移動(dòng)對(duì)象進(jìn)行聚類。聚類的方法采用基于密度的DBSCAN算法，該算法需要兩個(gè)參數(shù)：掃描半徑ε和最小包含點(diǎn)數(shù)minPts，DBSCAN算法的幾個(gè)定義如下：

ε鄰域 給定對(duì)象半徑為ε內(nèi)的區(qū)域稱為該對(duì)象的ε鄰域。

核心對(duì)象 如果給定對(duì)象ε鄰域內(nèi)的樣本點(diǎn)數(shù)大于等于minPts，則稱該對(duì)象為核心對(duì)象。

直接密度可達(dá) 對(duì)于樣本集合D，如果樣本點(diǎn)q在p的ε鄰域內(nèi)，且p為核心對(duì)象，則對(duì)象q從對(duì)象p直接密度可達(dá)。

密度可達(dá) 對(duì)于樣本集合D，給定一串樣本點(diǎn)p1,p2,…,pn，p=p1，q=pn，對(duì)象pi從pi-1直接密度可達(dá)，則對(duì)象q從對(duì)象p密度可達(dá)。

密度相連 存在樣本集合D中的一點(diǎn)o，若對(duì)象o到對(duì)象p和對(duì)象q都是密度可達(dá)，則p和q密度相連。

DBSCAN算法通過檢查數(shù)據(jù)集中每個(gè)對(duì)象的ε鄰域搜索簇，如果對(duì)象p的ε鄰域包含的點(diǎn)數(shù)多于minPts，則創(chuàng)建一個(gè)以p為核心對(duì)象的簇；之后DBSCAN迭代地聚集從核心對(duì)象直接密度可達(dá)的對(duì)象，并合并一些密度可達(dá)簇；當(dāng)所有對(duì)象都被歸于某個(gè)簇，算法結(jié)束。

算法2 移動(dòng)對(duì)象聚類。

輸入 數(shù)據(jù)集D、半徑ε、最小包含點(diǎn)數(shù)minPts；

輸出 移動(dòng)對(duì)象類簇集合。

1)

DBSCAN(數(shù)據(jù)集D，半徑ε，最小包含點(diǎn)數(shù)minPts)

Cid=0

//類別標(biāo)示

for each unvisited pointPin datasetD

//遍歷

markPas visited

//已經(jīng)訪問

NeighborPts=regionQuery(P，ε)

//計(jì)算這個(gè)點(diǎn)的鄰域

if sizeof(NeighborPts)

//不能作為核心點(diǎn)

markPas NOISE

//標(biāo)記為噪聲數(shù)據(jù)

else

//作為核心點(diǎn)，根據(jù)該點(diǎn)創(chuàng)建一個(gè)類別

Cid=next cluster

expandCluster(P，NeighborPts，Cid，ε，minPts)

//根據(jù)該核心對(duì)象擴(kuò)展類別

2)

expandCluster(P，NeighborPts，Cid，ε，minPts)

addPto clusterCid

//擴(kuò)展類別，核心對(duì)象先加入

for each pointP′ in NeighborPts

//然后針對(duì)核心對(duì)象ε鄰域內(nèi)的點(diǎn)

ifP′ is not visited

//如果該點(diǎn)沒有被訪問

markP′ as visited

//進(jìn)行訪問

NeighborPts′=regionQuery(P′，ε)

//如果該對(duì)象為核心對(duì)象，則擴(kuò)充該類別

if sizeof(NeighborPts′) >=minPts

NeighborPts=NeighborPtsjoined withNeighborPts′

ifP′ is not yet member of any cluster

//如果鄰域內(nèi)點(diǎn)不是核心點(diǎn)，并且無類別，比如噪

//聲數(shù)據(jù)，則加入此類別

addP′ to clusterCid

3)

regionQuery(P，ε)

//計(jì)算ε鄰域

return all points withinP′sε-neighborhood

3 實(shí)驗(yàn)

為了驗(yàn)證所提方法對(duì)車輛伴隨模式挖掘的準(zhǔn)確性和有效性，本文進(jìn)行了多組實(shí)驗(yàn)。采用的數(shù)據(jù)為中國某省份交通系統(tǒng)數(shù)據(jù)，該數(shù)據(jù)經(jīng)過融合、清洗，最終形成類ANPR數(shù)據(jù)。為評(píng)估本文所提出的算法，通過與FP-Growth算法的實(shí)驗(yàn)比較，分析算法的性能和有效性，實(shí)驗(yàn)機(jī)器系統(tǒng)為Windows 7 64位，CPU型號(hào)為Intel Core i7-6700 CPU 3.40 GHz,內(nèi)存16 GB，JDK版本為1.80，其中使用的數(shù)據(jù)庫為MongDB3.0及Redis3.0.5。

本文提出的方法有4個(gè)參數(shù)，分別是計(jì)算軌跡相似度的時(shí)間差閾值τ、距離閾值ω，DBSCAN算法的掃描半徑ε和最小包含點(diǎn)數(shù)minPts。這些參數(shù)的選擇應(yīng)該根據(jù)應(yīng)用場景估算。對(duì)于類ANPR數(shù)據(jù)的伴隨模式，伴隨車輛的距離一般不超過1 km，1 km地理距離經(jīng)緯度的差距約為0.01，據(jù)此估算出兩段首位端點(diǎn)各相差0.01時(shí)軌跡段的豪斯多夫距離為0.05；由于本文數(shù)據(jù)采集區(qū)域大，訪問一個(gè)地點(diǎn)的時(shí)間差距不超過60 km；掃描半徑ε代表兩個(gè)移動(dòng)對(duì)象可以判定為伴隨模式的最小距離，若兩個(gè)移動(dòng)對(duì)象有20個(gè)點(diǎn)符合共現(xiàn)的要求則視為伴隨模式，則掃描半徑ε應(yīng)設(shè)為0.05；最小包含點(diǎn)數(shù)minPts則對(duì)應(yīng)伴隨模式包含移動(dòng)對(duì)象的個(gè)數(shù)，按照最小值則為2。

3.1 性能測試與分析

為檢驗(yàn)此方法的效率，本文通過與FP-Growth算法進(jìn)行比較以評(píng)估該算法的性能。本文選擇了不同時(shí)間段的數(shù)據(jù)比較在不同數(shù)據(jù)規(guī)模下的效率，各實(shí)驗(yàn)數(shù)據(jù)集描述如表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集Tab. 1 Experimental data set

不同規(guī)模數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果如圖4所示，對(duì)比發(fā)現(xiàn)在相同數(shù)據(jù)量下，本文算法運(yùn)行時(shí)間要少于FP-Growth算法。主要有以下原因：1)本文算法是基于軌跡特征的聚類方法，軌跡特征只需要計(jì)算一次，在實(shí)際應(yīng)用中可以采用增量方法，而FP-Growth算法基于FP-Tree，對(duì)不同的數(shù)據(jù)集都要建立FP-Tree。2)對(duì)于類ANPR數(shù)據(jù)而言，在數(shù)據(jù)集中共享前綴的事物比較少，造成FP-Tree要為每一條事物建立分支，使算法內(nèi)存消耗增大，造成在數(shù)據(jù)量較大時(shí)運(yùn)行時(shí)間急劇增大，而本文的算法只需要存儲(chǔ)軌跡特征值。3)軌跡特征值數(shù)據(jù)結(jié)構(gòu)簡單，方便存儲(chǔ)，可做增量處理(實(shí)驗(yàn)中存儲(chǔ)在Redis中，一種內(nèi)存鍵值數(shù)據(jù)庫，便于管理，也可持久化)，而FP-Tree結(jié)構(gòu)復(fù)雜，只能存儲(chǔ)于內(nèi)存中。

圖4 FP-Growth與TB-DBSCAN對(duì)不同數(shù)據(jù)集的效率對(duì)比Fig. 4 Efficiency comparison between FP-Growth and TB-DBSCAN for different data sets

3.2 有效性測試與分析

表2為在不同數(shù)據(jù)規(guī)模下FP-GROWTH算法和本文算法挖掘出的伴隨模式個(gè)數(shù)及平均大小對(duì)比。

表2 FP-Growth算法與TB-DBSCAN算法結(jié)果對(duì)比Tab. 2 Comparison results of FP-Growth and TB-DBSCAN

圖5對(duì)比顯示了表2第6組伴隨模式的可視化效果,其中非伴隨車輛組軌跡顏色為灰色，不同伴隨車輛組軌跡以不同的非灰顏色進(jìn)行著色，其軌跡為實(shí)線，所有非伴隨車輛組軌跡為虛線。圖5(a)、(c)為FP-Growth算法的結(jié)果，圖5(b)、(d)為本文TB-DBSCAN算法的結(jié)果，其中圖5(a)、(b)分別顯示了兩種算法結(jié)果的整體情況，圖5(c)、(d)分別顯示了圖5(a)、(b)中A區(qū)域的細(xì)節(jié)情況。圖5(a)中實(shí)線軌跡標(biāo)識(shí)FP-Growth挖掘的第一個(gè)伴隨車輛組，圖5(c)中虛線軌跡標(biāo)識(shí)第二個(gè)伴隨車輛組；圖5(b)中虛線軌跡標(biāo)識(shí)本文算法挖掘出的伴隨車輛組軌跡。

圖5 第6組FP-Growth與TB-DBSCAN結(jié)果可視化對(duì)比Fig. 5 Comparison results of the 6th group between FP-Growth and TB-DBSCAN

從圖5(a)、(b)對(duì)比看出FP-Growth算法沒有挖掘出本文算法挖掘出的伴隨模式，而且圖(a)顯示挖掘出的模式內(nèi)部軌跡并不相似，圖(c)、(d)對(duì)比顯示了FP-Growth算法判定為伴隨車輛組的軌跡在本文算法中為噪聲數(shù)據(jù)，而實(shí)際上圖(c)中的虛線軌跡部分并不是伴隨車輛組，圖(c)中的伴隨車輛組其軌跡數(shù)據(jù)端點(diǎn)相同，但是序列是相反的，這里體現(xiàn)使用豪斯多夫距離區(qū)分軌跡段方向差異的優(yōu)勢(shì)。

以上對(duì)比表明本文算法相比FP-Growth算法，能夠區(qū)分具有相似軌跡但是移動(dòng)方向不同的移動(dòng)對(duì)象，避免如圖5(b)中軌跡數(shù)據(jù)的干擾，更能有效區(qū)分噪聲數(shù)據(jù)和伴隨車輛組。同時(shí)由于文中2.2節(jié)共現(xiàn)的定義，對(duì)于在小型區(qū)域內(nèi)移動(dòng)的對(duì)象不完全在相同地點(diǎn)出現(xiàn)而在距離較近地點(diǎn)出現(xiàn)的軌跡也可進(jìn)行挖掘，從而保證合理模式的挖掘。

4 結(jié)語

本文論述并借鑒了比較成熟的基于GPS數(shù)據(jù)伴隨模式挖掘方法，鑒于現(xiàn)有類ANPR數(shù)據(jù)伴隨車輛組挖掘方法的缺陷，提出一種統(tǒng)計(jì)類ANPR軌跡數(shù)據(jù)共現(xiàn)的方法，該方法從整體軌跡出發(fā)，不僅考慮的了ANPR軌跡中編號(hào)相同的點(diǎn)，還通過豪斯多夫距離衡量編號(hào)不同采樣點(diǎn)周圍的子軌跡相似度，有效表征了ANPR軌跡的相似度，并基于此相似度通過聚類方法挖掘伴隨車輛組，改善挖掘效果。但是在實(shí)驗(yàn)過程中發(fā)現(xiàn)將軌跡歸納為共現(xiàn)次數(shù)這一特征也有缺陷，在后續(xù)的研究中將探索更有效的軌跡特征化方法。另外類ANPR數(shù)據(jù)量巨大，在后續(xù)工作中將采用Spark框架進(jìn)行并行化處理。

References)

[1] HOMAYOUNFAR A, HO A T S, ZHU N, et al. Multi-vehicle convoy analysis based on ANPR data[C]// Proceedings of the 4th International Conference on Imaging for Crime Detection and Prevention. Piscataway, NJ: IEEE, 2011: 38.

[2] ESTER M, KRIEGEL H P, SANDER J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]// Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Menlo Park, CA: AAAI Press, 1996: 226-231.

[3] GUDMUNDSSON J, VAN KREVELD M. Computing longest duration flocks in trajectory data[C]// Proceedings of Annual ACM International Symposium on Advances in Geographic Information Systems. New York: ACM, 2006:35-42.

[4] JEUNG H, YIU M L, ZHOU X, et al. Discovery of convoys in trajectory databases[J]. Proceedings of the VLDB Endowment, 2008, 1(1):1068-1080.

[5] LI Z, DING B, HAN J, et al. Swarm: mining relaxed temporal moving object clusters[J]. Proceedings of the VLDB Endowment, 2010, 3(1/2):723-734.

[6] TANG L, ZHENG Y, YUAN J, et al. A framework of traveling companion discovery on trajectory data streams[J]. ACM Transactions on Intelligent Systems and Technology, 2014, 5(1):1-34.

[7] DEZA E, DEZA M M. Encyclopedia of Distances[M]. Berlin: Springer, 2009: 94.

[8] AGRAWAL R, FALOUTSOS C, SWAMI A. Efficient similarity search in sequence databases[C]// Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms. Berlin: Springer, 1993: 69-84.

[9] YI B K, JAGADISH H V, FALOUTSOS C. Efficient retrieval of similar time sequences under time warping[C]// Proceedings of the 14th International Conference on Data Engineering. Piscataway, NJ: IEEE, 1998: 201-208.

[10] VLACHOS M, KOLLIOS G, GUNOPULOS D. Discovering similar multidimensional trajectories[C]// Proceedings of the 18th International Conference on Data Engineering. Piscataway, NJ: IEEE, 2002: 673-684.

[11] CHEN L, ?ZSU M T, ORIA V. Robust and fast similarity search for moving object trajectories[C]// Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2005: 491-502.

[12] CHEN L, NG R. On the marriage of Lp-norms and edit distance[C]// Proceedings of the 13th International Conference on Very Large Data Bases. Toronto: VLDB Endowment, 2004, 30: 792-803.

[13] JEUNG H, YIU M L, JENSEN C S. Trajectory Pattern Mining[M]. New York: Springer, 2011: 143-177.

[14] LEE J G, HAN J, WHANG K Y. Trajectory clustering: a partition-and-group framework[C]// Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2007: 593-604.

[15] 方艾芬, 李先通, 蔄世明,等. 基于關(guān)聯(lián)規(guī)則挖掘的伴隨車輛發(fā)現(xiàn)算法[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2012, 29(2):94-96.(FANG A F，LI X T，MAN S M，et al．A discovery algorithm of traveling companions based on association rule mining[J]. Computer Applications and Software,2012,29(2): 94-96.)

[16] HAN J, PEI J, YIN Y. Mining frequent patterns without candidate generation[J].ACM SIGMOD Record, 2000, 29(2): 1-12.

[17] 曹波, 韓燕波, 王桂玲. 基于車牌識(shí)別大數(shù)據(jù)的伴隨車輛組發(fā)現(xiàn)方法[J]. 計(jì)算機(jī)應(yīng)用, 2015, 35(11): 3203-3207.(CAO B, HAN Y B, WANG G L. Discovery method of travelling companions based on big data of license plate recognition[J]. Journal of Computer Applications, 2015, 35(11): 3203-3207.)[18] 朱美玲, 王雄斌, 張守利, 等. 基于大規(guī)模流式車牌識(shí)別數(shù)據(jù)的即時(shí)伴隨車輛發(fā)現(xiàn)[J]. 中國科學(xué)技術(shù)大學(xué)學(xué)報(bào), 2016, 46(1): 47-55.(ZHU M L, WANG X B, ZHANG S L, et al. Instant traveling companion discovery based on large scale streaming ANPR data[J]. Journal of University of Science and Technology of China, 2016, 46(1): 47-55.)

This work is partially supported by the Xinjiang Uygur Autonomous Region Key Laboratory Project (2016D03019); the Xinjiang Uygur Autonomous Region High Technology Project (201512103); Chinese Academy of Sciences Science and Technology Service Network (STS) Project (KFJ-EW-STS-129).

WANGBaoquan, born in 1990, Ph. D. candidate. His research interests include big data analysis, data mining.

JIANGTonghai, born in 1963, Ph. D., research fellow. His research interests include multi-lingual information processing, E-government, multi-lingual text recognition.

ZHOUXi, born in 1978, Ph. D., research fellow. His research interests include Internet of things, big data analysis.

MABo, born in 1984, Ph.D., associate research fellow. His research interests include data analysis and knowledge discovery, machine learning.

ZHAOFan,born in 1980, Ph.D., associate research fellow. His research interests include information security, large data analysis.

Miningofaccompanyingvehiclegroupfromtrajectorydatabasedonanalogousautomaticnumberplaterecognition

WANG Baoquan1,2,3, JIANG Tonghai1,3*, ZHOU Xi1,3, MA Bo1,3, ZHAO Fan1,3

(1.XinjiangTechnicalInstituteofPhysicsandChemistry,ChineseAcademyofSciences,UrumqiXinjiang830011,China;2.UniversityoftheChineseAcademyofSciences,Beijing100049,China;3.XinjiangLaboratoryofMinoritySpeechandLanguageInformationProcessing,UrumqiXinjiang8300111,China)

Automatic Number Plate Recognition (ANPR) data is easier to obtain than private Global Positioning System (GPS) data, and it contains more useful information, but the relatively mature GPS track data mining with vehicle group method did not apply to ANPR data, the existing accompanying vehicle group mining algorithm pays attention to the similarity of the trajectory and ignores the time factor when dealing with small amount of ANPR data. A clustering method based on trajectory feature to excavate the accompanying vehicle group was proposed. Aiming at the fact that the sampling points are fixed and the sampling time is uncertain in the ANPR data, whether two objects were accompanied was determined by the number of co-occurrence in the trajectory. The co-occurrence definition introduced the Hausdorff distance, taking into account the location, direction and time characteristics of the trajectory. The accompanying vehicle group with different but adjacent sampling points and similar trajectories was minned to improve the mining efficiency. The experimental results show that the proposed method is more effective than the existing method to excavate the vehicle group, and improves the efficiency by nearly two times when identifying the non-accompanying mode data.

Automatic Number Plate Recognition (ANPR) trajectory data; traveling companions; Density-Based Spatial Clustering of Applications with Noise (DBSCAN); Hausdorff distance; co-occurrence

2017- 05- 16;

2017- 06- 05。

新疆維吾爾自治區(qū)重點(diǎn)實(shí)驗(yàn)室項(xiàng)目(2016D03019);新疆維吾爾自治區(qū)高技術(shù)計(jì)劃項(xiàng)目(201512103);中國科學(xué)院科技服務(wù)網(wǎng)絡(luò)計(jì)劃(STS計(jì)劃)項(xiàng)目(KFJ-EW-STS- 129)。

王保全(1990—)，男，新疆昌吉人，博士研究生，主要研究方向:大數(shù)據(jù)分析、數(shù)據(jù)挖掘； 蔣同海(1963—)，男，新疆福海人，研究員，博士生導(dǎo)師，主要研究方向:多語種信息處理、電子政務(wù)、多語種文字語音識(shí)別； 周喜(1978—)，男，湖南雙峰人，研究員，博士，CCF會(huì)員，主要研究方向:物聯(lián)網(wǎng)、大數(shù)據(jù)分析； 馬博(1984—)，男，遼寧鞍山人，副研究員，博士，CCF會(huì)員，主要研究方向:數(shù)據(jù)分析與知識(shí)發(fā)現(xiàn)、機(jī)器學(xué)習(xí)；趙凡(1980—)，男，山西介休人，副研究員，博士研究生，CCF會(huì)員，主要研究方向:信息安全、大數(shù)據(jù)分析。

1001- 9081(2017)11- 3064- 05

10.11772/j.issn.1001- 9081.2017.11.3064

(*通信作者電子郵箱jth@ms.xjb.ac.cn)

TP311.5

A