夏 英,張安潔

(重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,重慶 400065)

0 引 言

近年來(lái),大量研究人員致力于研究如何處理軌跡數(shù)據(jù)并使其服務(wù)于智能交通、智慧城市等領(lǐng)域[1-3]。基于度量的方法主要根據(jù)軌跡段之間的距離進(jìn)行異常檢測(cè)。文獻(xiàn)[4]提出基于Hausdorff距離進(jìn)行軌跡劃分的異常軌跡檢測(cè)框架。文獻(xiàn)[5]在聚類基礎(chǔ)上建立基于離散狀態(tài)的路徑模型。文獻(xiàn)[6]結(jié)合有向Hausdorff距離進(jìn)行異常檢測(cè),考慮方向差的同時(shí)降低計(jì)算復(fù)雜度?；诙攘康姆椒ㄖ饕紤]軌跡的距離特征,對(duì)軌跡的序列信息考慮不足。

基于統(tǒng)計(jì)的方法主要依賴歷史數(shù)據(jù)的支持。文獻(xiàn)[7]通過(guò)計(jì)算網(wǎng)格序列頻度來(lái)檢測(cè)異常軌跡。文獻(xiàn)[8]提出一種兩階段軌跡異常檢測(cè)框架,解決尋找局部異常軌跡和繞行問(wèn)題。文獻(xiàn)[9]在網(wǎng)格序列基礎(chǔ)上提出新的DIS距離計(jì)算軌跡之間的相似度。這類方法未充分考慮到歷史數(shù)據(jù)少、數(shù)據(jù)規(guī)模大等情形。

基于學(xué)習(xí)的方法主要利用序列建模。文獻(xiàn)[10]提出的XGBoost方案是經(jīng)典的分類算法;文獻(xiàn)[11]基于循環(huán)神經(jīng)網(wǎng)絡(luò),采用軌跡嵌入捕捉軌跡序列信息;文獻(xiàn)[12]基于行駛時(shí)間和距離的循環(huán)神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)異常檢測(cè);文獻(xiàn)[13]結(jié)合循環(huán)神經(jīng)網(wǎng)絡(luò)和卷積神經(jīng)網(wǎng)絡(luò)檢測(cè)異常軌跡?；趯W(xué)習(xí)的方法目前較為主流,但循環(huán)神經(jīng)網(wǎng)絡(luò)存在長(zhǎng)距離依賴問(wèn)題,無(wú)法長(zhǎng)久記憶。對(duì)網(wǎng)格化軌跡進(jìn)行序列建模僅提取軌跡時(shí)序特征,難以充分提取軌跡空間特征,如軌跡偏轉(zhuǎn)角度、行駛距離等[11]。

為充分利用軌跡數(shù)據(jù)的時(shí)空特征,本文提出融合時(shí)序和空間特征的車輛異常軌跡檢測(cè)方法(vehicle abnormal trajectory detection method based on fusing temporal and spatial features, ATD-TS)。該方法具有以下特點(diǎn):①在編碼器部分引入自注意力機(jī)制(stacked sequence auto-encoder with self-attention, SSA),解決傳統(tǒng)循環(huán)神經(jīng)網(wǎng)絡(luò)的長(zhǎng)序列依賴問(wèn)題,充分提取軌跡時(shí)序特征;②提取軌跡偏轉(zhuǎn)量和行駛距離,并使用全連接神經(jīng)網(wǎng)絡(luò)進(jìn)行特征提取(full connected network with deflection and driving-distance, FDD),以此挖掘軌跡中更多空間信息。

1 相關(guān)基礎(chǔ)

1.1 原始軌跡

原始軌跡T={p1,p2,…,pn}是記錄位置信息的時(shí)間序列[14],位置點(diǎn)pi由(loni,lati,ti)表示,其中(loni,lati)是位置經(jīng)緯度,ti是對(duì)應(yīng)的時(shí)間戳。p1和pn是原始軌跡的起點(diǎn)和終點(diǎn)。

1.2 映射軌跡

根據(jù)原始軌跡經(jīng)緯度的空間范圍,將空間區(qū)域分割成相同大小的網(wǎng)格grid[14],建立網(wǎng)格與原始軌跡點(diǎn)的對(duì)應(yīng)關(guān)系,將原始軌跡T={p1,p2,…,pn}映射為tr={grid1,grid2,…,gridn}。

1.3 異常軌跡

在出租車、物流等特定應(yīng)用場(chǎng)景下,車輛移動(dòng)軌跡會(huì)有預(yù)設(shè)的正常路徑,通過(guò)這些路徑的概率相對(duì)較高,異常軌跡產(chǎn)生的原因可能是主觀上的(如繞路行為)或客觀上的(如道路擁堵等)。

1.4 行駛距離

已知軌跡起點(diǎn)p1和終點(diǎn)pn,p1和pn的行駛距離s表示為[15]

(1)

(1)式中,dist(pi,pi+1)表示相鄰兩點(diǎn)之間的空間距離。

1.5 軌跡偏轉(zhuǎn)角

偏轉(zhuǎn)角[16]是相鄰兩個(gè)軌跡運(yùn)動(dòng)方向上的夾角。已知由p1、p2、p3這3個(gè)點(diǎn)構(gòu)成的夾角稱為開(kāi)放角θ,開(kāi)放角的補(bǔ)角稱為偏轉(zhuǎn)角β,偏轉(zhuǎn)角與開(kāi)放角如圖1所示。偏轉(zhuǎn)角越大表明運(yùn)動(dòng)發(fā)生偏轉(zhuǎn)程度越大。β和θ的計(jì)算式為

(2)

θ=π-β

(3)

圖1 軌跡偏轉(zhuǎn)角與開(kāi)放角Fig.1 Trajectory deflection angle and opening angle

1.6 軌跡偏轉(zhuǎn)量

軌跡偏轉(zhuǎn)量為軌跡偏轉(zhuǎn)角度的和,計(jì)算公式為

(4)

(4)式中:βk表示第k個(gè)相鄰兩軌跡運(yùn)動(dòng)方向上的夾角,即軌跡偏轉(zhuǎn)角;n表示一條軌跡有n個(gè)偏轉(zhuǎn)角。

2 ATD-TS方法設(shè)計(jì)

2.1 總體框架

ATD-TS總體框架分為軌跡預(yù)處理、軌跡特征提取和異常檢測(cè)3個(gè)組成部分,如圖2所示。軌跡預(yù)處理將原始軌跡轉(zhuǎn)換為映射軌跡,同時(shí)提取軌跡偏轉(zhuǎn)量和軌跡行駛距離;軌跡特征提取在編碼器(Encoder)每層引入SSA,構(gòu)建融合SSA的堆疊序列自編碼器模型以提取軌跡偏轉(zhuǎn)量和軌跡行駛距離等空間特征;異常檢測(cè)融合軌跡偏轉(zhuǎn)量、軌跡行駛距離和軌跡時(shí)序特征,輸入到多層感知機(jī)(multilayer perceptron, MLP)降維后輸入softmax層計(jì)算軌跡的異常概率,進(jìn)而對(duì)軌跡進(jìn)行異常檢測(cè)。

圖2 車輛異常軌跡檢測(cè)總體框架Fig.2 Overall framework of vehicle abnormal trajectory detection

2.2 融合自注意力機(jī)制的堆疊序列自編碼器模型構(gòu)建

車輛軌跡數(shù)據(jù)相鄰點(diǎn)有著上下文關(guān)系,本文引入自注意力機(jī)制結(jié)合堆疊的序列自編碼器來(lái)自適應(yīng)學(xué)習(xí)。圖3為融合自注意力機(jī)制的堆疊序列自編碼器示意圖。圖4為門控循環(huán)單元(gate recurrent unit,GRU)結(jié)合自注意力機(jī)制示意圖。

圖3 融合自注意力機(jī)制的堆疊序列自編碼器Fig.3 Stacked sequence auto-encoder fusing self-attention

2.2.1 堆疊序列自編碼器

為充分提取軌跡時(shí)序特征,采用GRU作為基礎(chǔ)單元構(gòu)建堆疊序列自編碼器,其結(jié)構(gòu)如圖5所示[17]。堆疊序列自編碼器通過(guò)編解碼過(guò)程提高特征提取能力。

圖4 GRU結(jié)合自注意力機(jī)制Fig.4 GRU combined with self-attention

圖5 序列自編碼器網(wǎng)絡(luò)結(jié)構(gòu)Fig.5 Network structure of sequence auto-encoder

假設(shè)GRUEncoder(·)是編碼函數(shù),GRUDecoder(·)是解碼函數(shù),對(duì)每個(gè)時(shí)間步驟t、輸入xt,軌跡序列編碼表示為

ht=GRUEncoder(xt,ht-1)

(5)

獲取編碼后得到語(yǔ)義向量S,并由解碼器解碼得

S=f(h1,h2,…,hn)

(6)

(7)

(6)式中:語(yǔ)義向量S作為解碼器的初始隱藏狀態(tài),并不作用于之后的時(shí)刻;f(·)是從編碼器隱藏層中總結(jié)信息并為解碼器生成上下文向量的函數(shù)。

單層序列自編碼器雖能學(xué)習(xí)軌跡的上下文關(guān)系,但對(duì)于軌跡數(shù)據(jù)更為抽象的內(nèi)在特征的提取較欠缺,為進(jìn)一步提高特征提取能力,本文將圖3和圖4所示結(jié)構(gòu)擴(kuò)展為四層堆疊序列自編碼器,原始數(shù)據(jù)作為最底層的輸入,每一層的輸入都是上一層的輸出,使用dropout機(jī)制避免過(guò)擬合問(wèn)題。

在四層堆疊序列自編碼器中,使用局部無(wú)監(jiān)督準(zhǔn)則對(duì)每一層進(jìn)行預(yù)訓(xùn)練操作,優(yōu)化堆疊序列自編碼器以提高后續(xù)分類性能,預(yù)訓(xùn)練目標(biāo)函數(shù)為

(8)

(8)式中:n為批量樣本個(gè)數(shù);xt為輸入數(shù)據(jù);yt為解碼器的擬合分布。利用上述預(yù)訓(xùn)練好的編碼器對(duì)軌跡數(shù)據(jù)進(jìn)行特征提取,編碼器最后一層輸出則可作為最終的時(shí)序特征。

2.2.2 自注意力機(jī)制

自注意力機(jī)制的核心就是在不依靠外來(lái)信息的情況下根據(jù)輸入數(shù)據(jù)自適應(yīng)選擇最相關(guān)的特征[18]。在堆疊序列自編碼器的每一層引入自注意力機(jī)制,上一層編碼器的輸出作為自注意力機(jī)制的輸入,得到的特征向量作為下一層編碼器的輸入,編碼器的輸出狀態(tài)H為

H=(h1,h2,…,hn)

(9)

(9)式中,ht表示t時(shí)刻編碼狀態(tài)。注意力向量a的計(jì)算公式為

a=softmax(Ws2tanh(Ws1HT))

(10)

(10)式中:向量a的每一個(gè)元素代表一個(gè)概率;Ws1∈Rda×u以及Ws2∈Rda是可學(xué)習(xí)參數(shù),da是一個(gè)超參數(shù)。將H的每個(gè)元素與a中對(duì)應(yīng)的元素相乘后相加得到最終的編碼狀態(tài)A為

A=aH

(11)

將編碼狀態(tài)A與輸出狀態(tài)H對(duì)應(yīng)相加以進(jìn)行特征融合,得到下一層的輸入H′,最終堆疊序列自編碼器中編碼公式可更新為

(12)

2.3 結(jié)合偏轉(zhuǎn)量和行駛距離的特征模型構(gòu)建

在具有相同起點(diǎn)與終點(diǎn)的軌跡中,正常行駛的車輛其軌跡偏轉(zhuǎn)量及行駛距離等特征往往在一定范圍內(nèi)具有一定的相似性。圖6為行駛距離實(shí)例,圖7為偏轉(zhuǎn)角度實(shí)例。當(dāng)發(fā)生異常行為時(shí),軌跡行駛距離及偏轉(zhuǎn)角度通常與正常軌跡具有較大差異。正常軌跡的偏轉(zhuǎn)量遠(yuǎn)低于異常軌跡的偏轉(zhuǎn)量,軌跡偏轉(zhuǎn)量也是異常軌跡檢測(cè)的一個(gè)重要依據(jù)。因此,為進(jìn)一步提高車輛異常軌跡的檢測(cè)效果,提取軌跡偏轉(zhuǎn)量和軌跡行駛距離特征作為參考指標(biāo)。

圖6 行駛距離實(shí)例Fig.6 Driving-distance example

圖7 偏轉(zhuǎn)角度實(shí)例Fig.7 Deflection example

軌跡行駛距離為軌跡中相鄰兩點(diǎn)的空間距離之和,Haversine方法[19]能夠有效減少相鄰兩點(diǎn)之間的短距離求解誤差,其滿足的關(guān)系為

cos(φ1)·cos(φ2)·hav(σ2-σ1)

(13)

(13)式中:R為地球半徑;φ1和φ2分別表示pi和pi+1的緯度;σ1和σ2分別表示pi和pi+1的經(jīng)度。

全連接神經(jīng)網(wǎng)絡(luò)作為特征提取網(wǎng)絡(luò),包含輸入層、隱藏層和輸出層。將軌跡偏轉(zhuǎn)量和行駛距離作為輸入數(shù)據(jù)分別輸入到兩個(gè)全連接神經(jīng)網(wǎng)絡(luò)中,通過(guò)隱藏層進(jìn)行訓(xùn)練得到最終的軌跡偏轉(zhuǎn)量和行駛距離等特征。假設(shè)輸入特征向量為x,輸出為y,則計(jì)算公式為

z=Wx+b

(14)

y=f(z)

(15)

(16)

(14)—(16)式中:z為未激活的輸出;W和b為可學(xué)習(xí)參數(shù);f(·)為非線性的激活函數(shù)sigmod。

2.4 異常檢測(cè)

經(jīng)過(guò)特征提取階段,原始軌跡被表示為一個(gè)融合后的特征序列。異常軌跡標(biāo)號(hào)為1(正類),正常軌跡標(biāo)號(hào)為0(負(fù)類)。為有效檢測(cè)異常,利用多層感知機(jī)實(shí)現(xiàn)特征降維,降維公式為

Mi=σ(Wi·Ei+bi)

(17)

(18)

3 實(shí)驗(yàn)與分析

3.1 數(shù)據(jù)集

實(shí)驗(yàn)采用葡萄牙波爾圖市的出租車軌跡數(shù)據(jù)集,包含442輛出租車在2013年1月到2014年6月的軌跡數(shù)據(jù),每輛出租車每隔15 s報(bào)告其位置。為與傳統(tǒng)的異常軌跡檢測(cè)方法進(jìn)行對(duì)比,在給定源-目的地對(duì)(SDPair)之間進(jìn)行對(duì)比試驗(yàn),抽取5對(duì)含有充分軌跡的SDPair。本文采用文獻(xiàn)[20]中的方法,每對(duì)SDPair包含5%左右的異常軌跡,具體數(shù)據(jù)描述如表1所示。實(shí)驗(yàn)按8∶1∶1劃分訓(xùn)練集、驗(yàn)證集與測(cè)試集,對(duì)原始軌跡進(jìn)行網(wǎng)格劃分,網(wǎng)格大小為100 m×100 m,然后利用唯一標(biāo)識(shí)標(biāo)記網(wǎng)格,建立網(wǎng)格與原始軌跡點(diǎn)的一一對(duì)應(yīng)關(guān)系。

表1 SDPair的軌跡數(shù)據(jù)信息

3.2 對(duì)比方法及參數(shù)設(shè)置

為驗(yàn)證所提方法的有效性,將本文方法與XGBoost[10]、IBAT[7]、ATDC[9]等方法進(jìn)行比較。實(shí)驗(yàn)在64位Ubuntu18.04操作系統(tǒng)下的Intel Xeon W-2133@3.6GHz CPU上進(jìn)行,使用Tensorflow框架和python3.6完成神經(jīng)網(wǎng)絡(luò)的搭建,堆疊序列自編碼器的層數(shù)設(shè)置為4,詞向量降維之后的向量維度為64, dropout機(jī)制比例為0.5,神經(jīng)網(wǎng)絡(luò)模型優(yōu)化器為Adam。

3.3 評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)選用準(zhǔn)確率(Accuracy, ACC)及F1評(píng)分(F1-score)作為實(shí)驗(yàn)定量評(píng)估指標(biāo),其定義式為

(19)

(20)

(21)

(22)

(19)—(22)式中:P為精確率,表示正確預(yù)測(cè)為正的占全部預(yù)測(cè)為正的比例;R為召回率,表示正確預(yù)測(cè)為正的占全部實(shí)際為正的比例;F1為對(duì)P與R的綜合評(píng)估。

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

實(shí)驗(yàn)均在同一實(shí)驗(yàn)環(huán)境下進(jìn)行,且均選用最優(yōu)結(jié)果。ATD-TS方法與XGBoost、IBAT、ATDC、ATD-LSTM和ATD-GRU 5種異常軌跡檢測(cè)方法的異常檢測(cè)效果如表2所示。從表2可知,本文提出的ATD-TS方法無(wú)論是在準(zhǔn)確率還是F1評(píng)分上均有所提升。這表明在捕捉軌跡序列信息的同時(shí),結(jié)合軌跡的偏轉(zhuǎn)量和行駛距離信息能夠有效提高異常軌跡檢測(cè)質(zhì)量。XGBoost方法表現(xiàn)較差的原因是該方法只考慮到軌跡的形狀,對(duì)于軌跡的序列信息考慮不全;基于統(tǒng)計(jì)的IBAT方法優(yōu)于ATDC方法,原因是使用DIS距離度量的ATDC方法對(duì)于異常閾值的選擇具有較高要求,在不同數(shù)據(jù)集上該方法的共通性較弱;同為深度學(xué)習(xí)的ATD-GRU方法優(yōu)于ATD-LSTM方法,原因是在同樣的參數(shù)設(shè)置下,GRU捕獲時(shí)序特征的能力優(yōu)于長(zhǎng)短時(shí)記憶單元LSTM。

為驗(yàn)證不同模塊對(duì)車輛異常軌跡檢測(cè)的效果,使用ATD-SAE_att表示僅使用融合自注意力機(jī)制的堆疊序列自編碼器進(jìn)行異常軌跡檢測(cè)的方法,ATD-TS在ATD-SAE_att的基礎(chǔ)上融合了軌跡偏轉(zhuǎn)量和軌跡行駛距離等空間特征。在參數(shù)設(shè)置相同的條件下,ATD-GRU表示僅使用門控GRU的方法。ATD-GRU、ATD-SAE_att、ATD-TS 3種方法的消融實(shí)驗(yàn)結(jié)果如表3所示。

表3 消融實(shí)驗(yàn)結(jié)果

使用柱形圖直觀分析ATD-GRU、ATD-SAE_att、ATD-TS 3種方法的準(zhǔn)確率和F1評(píng)分,結(jié)果如圖8—圖9所示。ATD-SAE_att與ATD-GRU比較,準(zhǔn)確率和F1評(píng)分均有一定程度提升,SDPair1、4、5檢測(cè)效果提升更為明顯。這是由于SDPair1、4、5比SDPari2、3數(shù)據(jù)量更大,使得注意力向量和自編碼器得到了更加充分的訓(xùn)練。在融合軌跡偏轉(zhuǎn)量和行駛距離之后,與ATD-SAE_att方法相比,ATD-TS又有不同程度的提升,尤其在SDPair1、2、3上提升效果明顯,這表明在數(shù)據(jù)較少時(shí),結(jié)合軌跡偏轉(zhuǎn)量和行駛距離信息可有效提高模型性能。

圖9 異常檢測(cè)F1評(píng)分Fig.9 Abnormal detection F1 score

為研究軌跡數(shù)據(jù)中異常軌跡比例較低時(shí)算法的有效性,對(duì)于實(shí)驗(yàn)中選取的5個(gè)給定異常軌跡標(biāo)簽的SDPair對(duì),分別設(shè)置數(shù)據(jù)集的異常比例從1%、3%到5%變化,即給定一個(gè)數(shù)據(jù)集,其中正常軌跡數(shù)據(jù)量不變,異常軌跡的比例按1%、3%和5%抽樣,然后重新組合訓(xùn)練集、驗(yàn)證集和測(cè)試集。為驗(yàn)證不同情況下的性能,實(shí)驗(yàn)采用提出的ATD-TS方法,并使用相同參數(shù),不同異常比例檢測(cè)結(jié)果如表4所示。當(dāng)異常軌跡的比例從低到高變化時(shí),算法模型的性能也在穩(wěn)步提升,并且當(dāng)異常軌跡的比例為1%時(shí),與表2相比,除SDPair5和SDPair3的準(zhǔn)確率和F1評(píng)分受異常比例影響較大外,其余數(shù)據(jù)集的檢測(cè)性能均優(yōu)于對(duì)比算法。這表明即使面對(duì)異常軌跡數(shù)據(jù)比例降低的問(wèn)題,本文提出的ATD-TS方法仍具有一定優(yōu)勢(shì)。

表4 不同異常比例檢測(cè)結(jié)果

4 結(jié)束語(yǔ)

本文提出了一種融合時(shí)序和空間特征的車輛異常軌跡檢測(cè)方法,能有效增強(qiáng)軌跡的時(shí)空特征提取能力,提高異常軌跡檢測(cè)性能。在特征提取部分,構(gòu)建融合自注意力機(jī)制的堆疊序列自編碼器,提高網(wǎng)格化軌跡時(shí)序特征的提取能力,引入全連接網(wǎng)絡(luò)提取軌跡偏轉(zhuǎn)量和行駛距離等空間特征,最后融合時(shí)空特征實(shí)現(xiàn)車輛軌跡異常檢測(cè)。本文ATD-TS方法無(wú)論是在數(shù)據(jù)量較少還是較大的情況下,都具有較高的準(zhǔn)確率和F1評(píng)分。 未來(lái)將考慮結(jié)合瞬時(shí)速度、加速度等更多運(yùn)動(dòng)特征,提升復(fù)雜場(chǎng)景下異常軌跡檢測(cè)準(zhǔn)確率。