采用軌跡壓縮和路網(wǎng)劃分的車輛異常軌跡檢測

蘇建花，趙旭俊，蔡江輝

(太原科技大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030024)

1 引 言

隨著社會的進(jìn)步，出租車和網(wǎng)約車逐漸成為人們出行的重要選擇，隨之出現(xiàn)的是層出不窮的網(wǎng)約平臺.由于故意繞路使乘客支付不必要的費(fèi)用等欺詐行為以及因軌跡存在異常隱含的刑事案件不斷增多，保障乘客在乘車過程中的權(quán)益和人身安全已經(jīng)成為亟待解決的問題.快速有效地從海量軌跡數(shù)據(jù)集中發(fā)現(xiàn)存在異常的車輛軌跡，挖掘背后有意義的隱藏信息，已成為眾多學(xué)者研究的熱點(diǎn)之一.

異常軌跡是指軌跡數(shù)據(jù)集中不符合給定條件或與大多數(shù)軌跡顯著不同的軌跡[1].現(xiàn)有的檢測算法根據(jù)軌跡之間的關(guān)系確定數(shù)據(jù)集中的異常軌跡.對于異常軌跡的檢測非常有成效，并被廣泛地應(yīng)用于各個方面.

但仍存在一些不可避免的問題:1)TRAOD算法[2]和R-Tree算法[3]將軌跡劃分為軌跡段集，通過與大多數(shù)軌跡之間的距離關(guān)系判斷軌跡是否異常.但是其只突出位置信息對評估軌跡離群程度的影響，忽略了其他因素的作用.同時TRAOD需要人工設(shè)置許多參數(shù)，而參數(shù)越多，人為因素對檢測結(jié)果的干擾就越大；2)參與檢測的數(shù)據(jù)質(zhì)量低.DBTOD算法[4]和SHNN-CAD算法[5]直接使用位置設(shè)備獲取的數(shù)據(jù)，未考慮值丟失，數(shù)據(jù)失真等問題，忽略正常軌跡與異常軌跡的差異，導(dǎo)致檢測結(jié)果準(zhǔn)確率較低；3)文獻(xiàn)[6]和文獻(xiàn)[7]只適合出發(fā)地(S)和目的地(D)相同的軌跡，無法適應(yīng)大范圍的檢測.而實(shí)際上車輛行駛是沒有規(guī)律的，故存在一定的局限性.

針對上述問題，提出了一種采用軌跡壓縮和路網(wǎng)劃分的車輛異常軌跡檢測算法(Vehicle anomalous detection based on trajectory compression and road network partition，PC-ATD)，將檢測問題模型轉(zhuǎn)化為道路的消耗，同時考慮位置變換和時間變化的影響，具體分為3個階段:第1個階段為數(shù)據(jù)預(yù)處理.首先，使用地圖匹配概率將軌跡轉(zhuǎn)化為遵循道路走向的點(diǎn)序列組合，解決了數(shù)據(jù)質(zhì)量低的問題；其次，根據(jù)軌跡點(diǎn)序列，在道路交叉處填補(bǔ)缺失數(shù)據(jù)，確保軌跡劃分后能夠完整表示在每一路段上的軌跡段；然后，依據(jù)道路節(jié)點(diǎn)和車輛行駛方向是否改變對軌跡進(jìn)行壓縮，以減少內(nèi)存消耗和后期參與計算的數(shù)據(jù)量；最后，以插點(diǎn)為節(jié)點(diǎn)將軌跡按照所在路段進(jìn)行劃分.第2個階段為離線訓(xùn)練階段.訓(xùn)練歷史數(shù)據(jù)的時間和距離消耗構(gòu)建道路消耗模型，并使用Dijkstra[8]算法獲取路網(wǎng)中所有S-D對的最小消耗值.第3個階段為檢測階段.計算支撐檢測的消耗閾值矩陣，通過目標(biāo)軌跡消耗與對應(yīng)閾值的關(guān)系確定軌跡是否異常.由于異常軌跡在行駛過程中的消耗遠(yuǎn)遠(yuǎn)大于正常軌跡的消耗，因此行駛消耗高出閾值范圍的軌跡就是要找的異常軌跡.

2 相關(guān)工作

近年來，關(guān)于異常軌跡檢測的研究，眾多學(xué)者已經(jīng)提出許多優(yōu)秀的算法[9，10].本節(jié)中主要研究了4種類型的異常軌跡檢測算法：基于分類的算法、基于距離的算法、基于歷史相似性的算法和基于網(wǎng)格的算法.

2.1 基于分類的檢測方法

Wu等人[11]在雙流體系結(jié)構(gòu)中嵌入VAE/GAN，通過對先驗(yàn)數(shù)據(jù)進(jìn)行離線訓(xùn)練構(gòu)造一個分類器.該算法隨著軌跡數(shù)據(jù)的不斷收集，無法有效檢測到進(jìn)化的未知的異常.針對這一問題，Laxhammar等人[5]提出了SHNN-CAD算法，將舊的測試集不斷的加入到訓(xùn)練集中，實(shí)現(xiàn)進(jìn)化的未知的軌跡異常檢測.當(dāng)更新訓(xùn)練集時，需要動態(tài)的調(diào)整異常閾值，并將更新后的距離度量作為SHNN-CAD的輸入，對下一個測試示例進(jìn)行分類.當(dāng)訓(xùn)練集增大到一定程度時，異常閾值的動態(tài)調(diào)整將會需要更高的計算成本.

基于分類的算法需要人工對數(shù)據(jù)進(jìn)行準(zhǔn)確標(biāo)注，導(dǎo)致高昂的計算開銷.且當(dāng)缺失具有標(biāo)簽的訓(xùn)練集時，無法構(gòu)建合適的分類器.

2.2 基于距離的檢測方法

Liu等人[3]通過R-Tree以及軌跡基本比較單元之間的距離依次找到所有局部匹配的基本比較單元對，根據(jù)各軌跡比較單元之間的匹配情況確定它們是否全局匹配.該算法需要頻繁計算各軌跡單元之間的距離，時間開銷較大，執(zhí)行效率較低.為避免以軌跡基本比較單元直接表示軌跡特征帶來的問題，Bae等人[12]使用局部運(yùn)動代替物體的運(yùn)動，對物體的局部運(yùn)動進(jìn)行特征提取，依次連接具有時空連續(xù)性的特征點(diǎn)形成部分軌跡，并建立起相應(yīng)的運(yùn)動模式.但收集的軌跡數(shù)據(jù)無法涵蓋所有異?，F(xiàn)象，故構(gòu)建的運(yùn)動模式無法完全準(zhǔn)確的檢測到所有可能存在的異常.Lu等人[13]通過特征相似性度量將軌跡聚類到m簇，通過目標(biāo)軌跡段與簇中心的距離確定軌跡屬于已存在的簇還是一個新的簇.以上3種算法只適合在靜態(tài)軌跡數(shù)據(jù)集下的檢測.

針對軌跡流數(shù)據(jù)，Yu等人[14]在前期方法的基礎(chǔ)上，對軌跡在時間軸上進(jìn)行了縱向劃分，設(shè)置恰當(dāng)?shù)拈撝?，從時間和空間的相關(guān)性上確定軌跡之間的關(guān)系.

基于距離的算法重點(diǎn)監(jiān)測位置特征表現(xiàn)出來的異常，忽略了其他因素的作用，無法有效檢測到與位置無關(guān)的特征所導(dǎo)致的異?，F(xiàn)象.

2.3 基于歷史相似性的檢測方法

Fu等人[15]通過離線訓(xùn)練建立了一個關(guān)于行為特征的全局特征模型，使用時間感知和空域相關(guān)的協(xié)同算法對軌跡進(jìn)行檢測.此算法在不考慮軌跡時變進(jìn)化特性時具有較高的檢測精度，但隨著軌跡數(shù)據(jù)飛速增加，新的異?，F(xiàn)象隨之產(chǎn)生，異常檢測精度越來越低.針對這一現(xiàn)象，Mao等人[16]定義了局部異常軌跡碎片和進(jìn)化異常運(yùn)動目標(biāo)的概念，從軌跡段集中獲取所有特征點(diǎn)，搜索軌跡碎片領(lǐng)域，計算局部異常因子，通過局部異常因子生成演化異常因子.不僅能檢測靜態(tài)軌跡數(shù)據(jù)集中的異?，F(xiàn)象，還能在模型的不斷更新中捕捉軌跡流中時變的異常.Mao等人[7]通過無監(jiān)督的貝葉斯反向增強(qiáng)算法對車輛的駕駛行為進(jìn)行建模，并新增路段獎勵函數(shù)和路段潛在開銷函數(shù).但是實(shí)際上道路狀況是瞬息萬變的，該算法無法適應(yīng)動態(tài)變化的道路狀況檢測.

基于歷史相似性的方法在采集到足夠的軌跡數(shù)據(jù)時具有較高的檢測精度，但是隨著數(shù)據(jù)規(guī)模的不斷增大，需對模型進(jìn)行階段性重建，需要較高的計算開銷.

2.4 基于網(wǎng)格的檢測方法

Chen等人[6]通過比較異常路由與正常路由在線監(jiān)測軌跡中出現(xiàn)的異常，并確定異常發(fā)生的起因.但需要對檢測范圍進(jìn)行網(wǎng)格劃分，當(dāng)軌跡超出一定數(shù)目，網(wǎng)格劃分需要巨額的時間開銷.Liu等人[4]通過確定目標(biāo)軌跡與子軌跡的距離和在給定范圍內(nèi)鄰域子軌跡的個數(shù)來判定目標(biāo)軌跡是否異常.此算法只適合軌跡密度較大時的檢測，當(dāng)軌跡數(shù)目稀疏時，無法獲取足夠的領(lǐng)域子軌跡來判定軌跡是否異常.

基于網(wǎng)格劃分的方法需要多次調(diào)整參數(shù)尋找合適的網(wǎng)格大小，在這個過程中將消耗大量的時間，導(dǎo)致檢測效率低的問題.

3 基于地圖匹配和軌跡插點(diǎn)壓縮的路網(wǎng)劃分

3.1 地圖匹配

針對大部分算法直接使用位置設(shè)備獲取的數(shù)據(jù)進(jìn)行建模，未考慮數(shù)據(jù)實(shí)際質(zhì)量導(dǎo)致檢測精度偏低的問題，選擇將軌跡數(shù)據(jù)映射到路網(wǎng)中，使最終得到的軌跡遵循真實(shí)路徑的走向.相關(guān)定義如下：

定義1.道路網(wǎng)絡(luò).道路網(wǎng)絡(luò)G是一個有向圖網(wǎng)絡(luò)，其中V表示道路節(jié)點(diǎn)集，E表示道路路段集.對路段e∈E，其起點(diǎn)為ei.s，終點(diǎn)為ei.d，有ei.d=ei+1.s，s，d∈V.

定義2.軌跡.軌跡是指運(yùn)動物體的位置記錄序列，由定位設(shè)備獲得的一系列具有時空連續(xù)性的GPS軌跡點(diǎn)組成，即：

T={P1，P2，…，Pn}

(1)

考慮在地圖匹配中空間坐標(biāo)的變換，后期需計算軌跡在道路節(jié)點(diǎn)處的速度和時間戳，以及根據(jù)插點(diǎn)和行駛方向變換實(shí)現(xiàn)軌跡壓縮，選擇以七維矢量表示軌跡點(diǎn)，即pi=〈Idi，ti，loni，lati，vi，θi，si〉，其中Id是軌跡的唯一標(biāo)識；t表示設(shè)備報告軌跡點(diǎn)的時間戳；lon和lat為軌跡點(diǎn)的空間坐標(biāo)；v和θ分別是車輛在當(dāng)前時間戳的瞬時速度和順時針方向與北方的夾角；s是此刻車輛的狀態(tài).軌跡點(diǎn)按時間順序到達(dá)，即滿足：t1

路網(wǎng)中路段量大，將軌跡點(diǎn)在每一路段上進(jìn)行投影計算成本過高，而實(shí)際上位置接收設(shè)備的誤差是有限的，因此選取與軌跡點(diǎn)在一定路網(wǎng)距離內(nèi)的路段作為候選路段，并選擇路段上與軌跡點(diǎn)距離最近的點(diǎn)作為候選點(diǎn)來表示軌跡點(diǎn)在候選道路上的映射位置.定義如下：

定義3.候選路段.對于?e∈E，若軌跡點(diǎn)p到路段e的距離d(p，e)滿足：d(p，e)

定義4.候選點(diǎn).軌跡點(diǎn)p在候選路段e上的候選點(diǎn)，記作mp，e，定義為e上與p距離最近的點(diǎn)，即滿足：

d(p，mp，e)=min(d(me，p))

(2)

其中：me為e上的任意一點(diǎn).

為了將軌跡數(shù)據(jù)更準(zhǔn)確地映射到路網(wǎng)空間，使用匹配概率度量候選點(diǎn)與軌跡點(diǎn)的匹配度，以確定候選點(diǎn)在映射序列中被選中的可能性.匹配概率由候選點(diǎn)的觀測概率和轉(zhuǎn)移概率得出.所以在介紹匹配概率的形式化定義之前，將先給出觀測概率和轉(zhuǎn)移概率的定義.

給定一個軌跡點(diǎn)pi∈T，一條路段ej∈E且d(pi，ej)

(3)

其中：δ是標(biāo)準(zhǔn)偏差；d(pi，mpi，ej)為pi與mpi，ej之間的距離.

候選點(diǎn)的觀測概率與候選點(diǎn)與軌跡點(diǎn)的距離相關(guān)，其隨著候選點(diǎn)與軌跡點(diǎn)距離的減小而變大，即對于距離較近的候選點(diǎn)給予較大的觀察概率.

假設(shè)映射序列中mpi，ej的上一映射點(diǎn)為mpi-1，et，mpi，ej的轉(zhuǎn)移概率為映射序列中由mpi-1，et轉(zhuǎn)移至mpi，ej的可能性，定義為：

(4)

其中：d(pi-1→pi)是相鄰軌跡點(diǎn)pi-1和pi之間的空間距離；td(mpi-1，et→mpi，ej)是相鄰候選點(diǎn)mpi-1，et和mpi，ej之間的最短路網(wǎng)轉(zhuǎn)移距離.

映射序列的路網(wǎng)轉(zhuǎn)移距離越小，映射轉(zhuǎn)移的概率可能性越高.但要最終確定候選點(diǎn)與軌跡點(diǎn)的匹配程度，需要同時考慮候選點(diǎn)的觀測概率和轉(zhuǎn)移概率.根據(jù)公式(3)和公式(4)可以得到mpi，ej的匹配概率為：

MP(mpi，ej)=MP(mpi-1，et)+OP(mpi，ej|pi)×
DP(mpi-1，et→mpi，ej)

(5)

OP(mpi，ej|pi)和DP(mpi-1，et→mpi，ej)越大，mpi，ej的匹配概率越高，即在映射序列中被選中的可能性越大.在地圖匹配過程中，考慮到路網(wǎng)的連通性，保存所有匹配步驟的最小總代價以及該代價情況下所有匹配步驟的選擇，在所有軌跡點(diǎn)的候選點(diǎn)狀態(tài)計算結(jié)束后，利用Viterbi算法通過回溯的方法找到軌跡點(diǎn)匹配序列中匹配概率最大的映射路徑作為最終的匹配結(jié)果.

3.2 基于軌跡插點(diǎn)的軌跡壓縮

由于軌跡收集率高，對內(nèi)存和計算提出了新的挑戰(zhàn)，因此選擇通過軌跡壓縮緩解內(nèi)存壓力，并減少后期參與計算的數(shù)據(jù)量.且在異常軌跡檢測中，需將軌跡按照軌跡點(diǎn)所在路段進(jìn)行劃分，并加入到所在路段的軌跡段集合中.但實(shí)際情況下無法保證軌跡發(fā)生路段轉(zhuǎn)移時，在相鄰兩路段的交叉口處存在軌跡點(diǎn)，導(dǎo)致劃分后，在路段的起點(diǎn)和終點(diǎn)處可能存在信息丟失.

為保證劃分后路段上軌跡段的完整性，且在離線訓(xùn)練和檢測過程中僅考慮空間位置的變換和時間的消耗.在軌跡壓縮和劃分前，選擇在軌跡發(fā)生路段轉(zhuǎn)移的交叉口處進(jìn)行插點(diǎn).并根據(jù)前后軌跡點(diǎn)的時間戳和速度計算插點(diǎn)的相關(guān)信息.給定軌跡T′∈地圖匹后的軌跡數(shù)據(jù)集TD′，且?pi-1，pi∈T′.假設(shè)et，ej，為相鄰兩路段，存在以下4種情況：

1)pi為T′在ej上的第一個采樣點(diǎn)且為T′的起始軌跡點(diǎn)，則在ej和et的交叉口處插入pet，ej.此時vi-1和ti-1均為0.

2)pi是et的最后一個采樣點(diǎn)且是ej的第一個采樣點(diǎn)，即pi為T′在et和ej交叉口處的軌跡點(diǎn)，則在交叉口插入pet，ej.此時pet，ej=.

3)pi-1為et上的最后一個采樣點(diǎn)，pi為ej上的第一個采樣點(diǎn)，且pi-1≠pi，則在et與ej交叉口插入pet，ej.pet，ej的空間坐標(biāo)即為該交叉口的空間坐標(biāo)，其行駛速度以及時間戳計算公式如下：

(6)

(7)

其中：d(pi-1，pet，ej)和d(pi，pet，ej)分別表示pet，ej與pi-1和pi的距離；S=d(pi-1，pet，ej)+d(pi，pet，ej).

4)pi-1為T′在et上的最后一個采樣點(diǎn)且為T′的結(jié)束軌跡點(diǎn)，則在et和ej的交叉口處插入pet，ej.此時vi和ti均為0.

插點(diǎn)后得到的新數(shù)據(jù)集TD″.根據(jù)插點(diǎn)和車輛行駛方向是否發(fā)生變化對TD″中的軌跡依次進(jìn)行壓縮.軌跡壓縮是輸入一條軌跡數(shù)據(jù)后，輸出一條新的軌跡，其含軌跡點(diǎn)更少但能最大限度的表示原始軌跡.壓縮過程中，通過保留滿足要求的軌跡點(diǎn)，刪除不必要的數(shù)據(jù)樣本以減小數(shù)據(jù)量的大小.即保留軌跡插點(diǎn)和行駛方向發(fā)生變化前后的軌跡點(diǎn)，刪除不是插點(diǎn)且行駛方向未變化的點(diǎn).

詳細(xì)地，假設(shè)運(yùn)動對象在路段e上行駛，e的兩個端點(diǎn)分別是e.s和e.d.如果軌跡點(diǎn)pi滿足：d(pi，e.s)=0或者d(pi，e.d)=0，即pi是道路節(jié)點(diǎn)處的插點(diǎn)，直接保留.當(dāng)運(yùn)動對象在e上由pi-1途經(jīng)pi駛向pi+1，且pi-1和pi+1不是e的起點(diǎn)和終點(diǎn)時，若滿足：d(pi+1，pi-1)>d(pi，pi-1)，即pi+1不是插點(diǎn)且行駛方向未發(fā)生變化，則刪除點(diǎn)pi+1；否則保留pi+1.可得到壓縮后的數(shù)據(jù)集TD?.可以發(fā)現(xiàn)在不丟失重要信息的前提下，通過軌跡壓縮可以最大限度的減少原始軌跡中的軌跡點(diǎn)量和檢測過程中的計算量，且不會影響數(shù)據(jù)的后續(xù)使用.

3.3 軌跡劃分

軌跡壓縮后，以插點(diǎn)為節(jié)點(diǎn)對軌跡進(jìn)行劃分，給定一條軌跡T?∈TD?，劃分步驟如下：

Step 1.假設(shè)pet，ej為T?的第1個插入點(diǎn)，T?在ej的初始軌跡段為Tsej，T?={pet，ej}.若pi?∈T?(i≥1)不是插入點(diǎn)，則Tsej，T?=Tsej，T?∪pi；若pi為pet，ej的相鄰插入點(diǎn)pej，es，則Tsej，T?=Tsej，T?∪pej，es.則得到T?在ej上的軌跡段.

Step 2.以pej，es為新的起點(diǎn)，T?在es的初始軌跡段為Tses，T?={pej，es}，尋找T?中與pej，es相鄰的插入點(diǎn)pes，eu，并作為新的終點(diǎn)，將pej，es和pes，eu以及兩點(diǎn)之間的軌跡點(diǎn)劃分至路段es的軌跡段集合中，步驟同Step 1.

Step 3.重復(fù)Step 2，直至軌跡在當(dāng)前路段的軌跡段終點(diǎn)為軌跡的最后一個軌跡點(diǎn)，即最后一個插入點(diǎn).可得到軌跡T?劃分后的軌跡段集合為：{Tsej，T?={pet，ej，…，pej，es}，Tses，T?={pej，es，…，pes，eu}，…}.

根據(jù)插點(diǎn)對軌跡進(jìn)行分割后，既可以正確表示軌跡在每一路段上的完整軌跡段，重新整合后又不會丟失原始軌跡的重要信息.

TD?中所有軌跡劃分結(jié)束后，將各軌跡中屬于同一路段的軌跡段加入到該路段的軌跡段集中.即給定一個路段ej，ej的軌跡段集合記做Tssej，則Tssej={Tsej，Ti?，j=1，2，3，…，m}，其中Tsej，T?為T?在ej上的軌跡段.

3.4 系統(tǒng)流程及算法描述

基于地圖匹配和軌跡插點(diǎn)壓縮的路網(wǎng)劃分的流程圖如圖1所示，實(shí)現(xiàn)過程見算法1.首先，在地圖匹配階段，從路網(wǎng)空間中尋找軌跡點(diǎn)的候選路段集和候選點(diǎn)集.根據(jù)公式(3)-公式(5)計算候選點(diǎn)的匹配概率，并使用Viterbi算法進(jìn)行回溯找到匹配概率和最大的映射序列(參見算法1中1-8行).當(dāng)相鄰兩軌跡點(diǎn)匹配至相鄰兩路段時，根據(jù)公式(6)和公式(7)計算出運(yùn)動對象在兩路段交叉點(diǎn)處的行駛速度和時間戳，并插入軌跡中(參見算法1中9-14行).在劃分前根據(jù)道路節(jié)點(diǎn)和車輛在單道路上的行駛方向是否發(fā)生變化對軌跡進(jìn)行壓縮，以減少離線訓(xùn)練時參與計算的數(shù)據(jù)量(參見算法1中15-19行).最后根據(jù)插點(diǎn)將軌跡劃分至所在路段的軌跡段集合中(參見算法1中20-24行).

圖1 路網(wǎng)劃分流程圖Fig.1 Flow chart of road network division

算法1.基于地圖匹配和軌跡插點(diǎn)壓縮的路網(wǎng)劃分

輸入：軌跡T={p1，p2，…，pn}∈TD，其中pi∈T，i∈{1，2，…，n}

輸出：匹配后的軌跡T′={p1′，p2′，…，pn′}

劃分后的軌跡段Tsej，T?

1.For eachpi(i∈{1，2，…，n}) inT

2.根據(jù)定義3和定義4計算pi的候選路段集和候選點(diǎn)集M

3.For eachmpi，ejinM

4. 根據(jù)公式(3)-公式(5)計算mpi，ej的匹配概率MP(mpi，ej)

5. end for；

6.end for；

7.使用Viterbi算法找到匹配概率和最大的映射序列T′

8.end for；

9.For eachpi′ inT′

10.ifpi′滿足插點(diǎn)的4種情況

11. 根據(jù)公式(6)和公式(7)計算插點(diǎn)pet，ej的速度和時間戳

12.T″←T″∪pet，ej

13.end if；

14.end for；

15. For eachpi″ inT″

16. ifpi″為T″為插點(diǎn)或pi″與pi+1″出現(xiàn)方向的轉(zhuǎn)換

17.T?←T?∪pi″

18. end if；

19.end for；

20.For eachpi? inT?for

21. ifpi?和pk?分別為T?在et和ej，ej和es交叉處的插點(diǎn)

22.Tsej，T?={pi?，…，pk?}

23. end if；

24.end for；

4 異常軌跡檢測

4.1 離線訓(xùn)練

軌跡劃分后，通過挖掘所有軌跡段的時間戳及空間坐標(biāo)變換信息對路段消耗值進(jìn)行建模，由Dijkstra算法[8]使用該模型生成路網(wǎng)中所有S-D對的最小消耗路徑和最小消耗值.

首先，獲取路網(wǎng)中的所有路段，及在每一路段上的軌跡段集合.其次，根據(jù)所有軌跡段的信息依次訓(xùn)練出各路段的消耗值.一般情況下，駕駛員在選擇駕駛路線時會同時考慮路程的距離和時間需求，因此構(gòu)建路段消耗函數(shù)時，將綜合考慮時間和距離的消耗.在計算路段的消耗值前，首先給出軌跡段消耗值的定義.

定義5.軌跡段Ts的消耗值.給定一個軌跡段Ts={p0，p1，…，pk}，其消耗值Tse可定義為：

(8)

給定一個路段e∈E，假設(shè)經(jīng)過劃分后，得到e上的軌跡段集合為Tsse={Tse，T1?，Tse，T2?，…，Tse，Tl?}，根據(jù)定義5可得e的消耗值為：

(9)

式中：l為e上軌跡段的數(shù)量.

依次獲取所有路段的消耗值后，使用Dijkstra算法求解路網(wǎng)中所有S-D對間的最小消耗路徑和最小消耗值.

給定某一S-D對間所有路段的集合Rss，假設(shè)從Rss中得到S-D對間的最小消耗路徑為mlS-D=，每一路段的消耗值可由公式(8)計算得到，可得mlS-D的最小消耗值為：

(10)

重復(fù)上述步驟直至得到路網(wǎng)中所有S-D對間的最小消耗值.

4.2 異常軌跡檢測

當(dāng)收集到一條新的軌跡數(shù)據(jù)時，通過地圖匹配、軌跡插點(diǎn)、軌跡壓縮及路網(wǎng)劃分得到當(dāng)前軌跡分布在不同道路的軌跡段集合.確定該軌跡是否為異常軌跡的過程可以分為以下兩個步驟：

1)通過挖掘軌跡的時間戳和空間坐標(biāo)信息計算該軌跡的消耗值.軌跡劃分后得到軌跡段序列，其中每一軌跡段的消耗值可直接由公式(8)得到.則軌跡消耗的定義如下：

對一條新的軌跡T，其從S點(diǎn)出發(fā)駛向D點(diǎn)，通過地圖匹配、軌跡插點(diǎn)、軌跡壓縮得到軌跡T?，假設(shè)由T?劃分得到的軌跡段序列為T?=，T的消耗值，記做Te，定義為軌跡段序列中所有軌跡段消耗值之和，即：

(11)

其中：Tsej為軌跡段Tsj的消耗值.

2)檢測異常軌跡.檢測異常軌跡需要一個統(tǒng)一的評估標(biāo)準(zhǔn)(消耗閾值)，最簡單直接的方法就是將軌跡消耗值與消耗閾值比較以確定目標(biāo)軌跡是否異常.

給定對應(yīng)S-D對消耗閾值φS-D∈消耗閾值矩陣φ，對軌跡T，若其對應(yīng)軌跡T?的消耗值Te>φS-D，則T為異常軌跡，反之為正常軌跡.即：

然而，車輛行駛受道路狀況的影響極大，在車流量較大時，道路出現(xiàn)堵塞，導(dǎo)致行駛距離較近，但實(shí)際行駛時間明顯高于路況正常時期.而且，部分司機(jī)會主動避開堵塞路段選擇行駛時間或距離相對較短的路線代替.因此，在檢測異常軌跡時給消耗閾值一個可控的波動范圍，以增強(qiáng)算法的容錯率.根據(jù)公式(10)得到各S-D對的消耗閾值，定義如下：

φS-D=McS-D×γ

(12)

其中：γ為消耗閾值影響因子.

由所有S-D對的消耗閾值可得到消耗閾值矩陣φ.在實(shí)驗(yàn)中，動態(tài)調(diào)整γ的大小，從而找到最恰當(dāng)?shù)南拈撝稻仃囀巩惓＼壽E的檢測結(jié)果準(zhǔn)確率最高.

4.3 系統(tǒng)流程及算法描述

異常軌跡檢測流程如圖2所示，挖掘算法1中得到的各路段軌跡段集，獲取各路段的消耗值以及路網(wǎng)中各S-D對的最小消耗值，運(yùn)算過程見算法2.首先，使用時間和距離消耗計算路段上每一軌跡段的消耗值，并通過所有軌跡段的消耗值計算該路段的消耗值(參見算法2中1-4行)；其次，利用Dijkstra算法獲取S-D對的最小消耗路徑，根據(jù)公式(10)計算最小道路消耗值，并根據(jù)公式(12)得到消耗閾值矩陣(參見算法2中5-7行)；最后，當(dāng)一條新的軌跡被收集到時，通過算法1對T進(jìn)行地圖匹配、軌跡插點(diǎn)、壓縮和劃分，根據(jù)公式(8)和公式(11)計算軌跡的消耗值，將其與對應(yīng)S-D對的消耗閾值進(jìn)行比較，當(dāng)消耗值高于相應(yīng)S-D對的消耗閾值時，認(rèn)為該軌跡對象為異常軌跡(參見算法2中8-14行).

圖2 異常軌跡檢測流程圖Fig.2 Flow chart of abnormal trajectory detection

算法2.異常軌跡檢測

輸入：ej的軌跡段集Tssej={Tsej，T1?，Tsej，T2?，…，Tse，Tl?}

S-D對間路段集Rss，測試軌跡T

輸出：所有S-D對的最小消耗值MleS-D

消耗閾值矩陣φ；T是否為異常軌跡

1.forTsej，Ti?inTssej

2. 根據(jù)公式(8)，計算Tsej，Ti?的消耗值Tseej，Ti?

3. 根據(jù)公式(9)，計算路段ej的消耗值

4.end for；

5.使用Dijkstra生成最小消耗路徑mlS-D={e1，e2，…，eh}

6.根據(jù)公式(10)計算S-D對的最小路徑消耗值MleS-D

7.根據(jù)公式(12)計算消耗閾值矩陣φ

8.使用算法1對T進(jìn)行地圖匹配、插點(diǎn)、壓縮

9.根據(jù)公式(8)和公式(11)計算T的消耗值Te

10.ifTe>φS-D(φS-D∈φ) then

11. Return true

12.else

13. return false

14.end if；

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

本節(jié)使用2007年2月20日來自中國上海的出租車軌跡數(shù)據(jù)集驗(yàn)證了PC-ATD的有效性和效率.并與TADSS[1]、TRAOD[2]、iBOAT[6]和TPRO[17]進(jìn)行比較，證實(shí)PC-ATD具有改進(jìn)的性能.

該數(shù)據(jù)集受限于道路網(wǎng)絡(luò)，包括大約4000輛出租車的4316條軌跡(約6060079條軌跡點(diǎn)記錄)，每個GPS軌道的接收速度約為1次/分鐘.考慮到范圍跨度大，信息可能存在偏差導(dǎo)致結(jié)果精度較低的問題，從數(shù)據(jù)集中提取了徐匯區(qū)范圍內(nèi)的605條軌跡，經(jīng)切分處理得到1772條時間連續(xù)且具有研究意義的軌跡作為最終實(shí)驗(yàn)數(shù)據(jù)進(jìn)行效果測試，記作TD.

所有實(shí)驗(yàn)都是在具有Intel(R)Core(TM)i5-8250U CPU，8GB主內(nèi)存和以64位Windows 10作為操作系統(tǒng)的工作站上使用真實(shí)數(shù)據(jù)集進(jìn)行的，該算法在JDK8中實(shí)現(xiàn).

5.1 實(shí)驗(yàn)的有效性

為驗(yàn)證PC-ATD的有效性，我們將TD劃分為由1329條軌跡組成的訓(xùn)練集和由443條軌跡組成的測試集.對訓(xùn)練集進(jìn)行離線訓(xùn)練構(gòu)建道路消耗模型，在軌跡的動態(tài)進(jìn)入中實(shí)現(xiàn)異常軌跡的實(shí)時檢測.

首先，比較位置信息評估算法和PC-ATD算法，以注意結(jié)果的不同之處.使用位置信息評估算法時α=1，在測試集中檢測到107條異常軌跡.使用PC-ATD算法時α=0.9，β=0.1，γ=1.4，在測試集中檢測到65條異常軌跡.與位置信息評估算法相比，PC-ATD算法檢測到的異常軌跡數(shù)量明顯較少.原因在于，位置信息評估只考慮位置屬性的變化，人為忽略了駕駛?cè)藢r間的考慮，導(dǎo)致將一些距離較遠(yuǎn)，行駛時間較短滿足客戶需求，且與正常軌跡差異微小的軌跡錯誤的歸為異常，證明多屬性異常評價方法是有意義的.

其次，在不同規(guī)模訓(xùn)練集下對PC-ATD進(jìn)行測試，以注意訓(xùn)練集規(guī)模對檢測結(jié)果的影響，參數(shù)設(shè)置為α=0.9，β=0.1，γ=1.4.可以觀察到隨著訓(xùn)練集規(guī)模的增大，一些被檢測為異常的軌跡被評估為正常.原因是隨著數(shù)據(jù)訓(xùn)練集的不斷增大，得到的道路消耗值越接近普遍情況，消耗閾值矩陣中的元素越貼近多數(shù)情況，從而檢測的準(zhǔn)確度越高.

通過地圖匹配解決了位置設(shè)備獲取數(shù)據(jù)存在的設(shè)備誤差問題，使軌跡數(shù)據(jù)的走向嚴(yán)格受限于路網(wǎng)；并通過軌跡壓縮減少了后期參與計算的數(shù)據(jù)量，壓縮率達(dá)到60%，有效的降低了內(nèi)存占用率，提高了運(yùn)算效率.

5.2 參數(shù)影響

實(shí)驗(yàn)分別以位置信息變化和時間戳變化作為距離消耗和時間消耗的量度，并以路段上所有軌道段的平均消耗值表示相應(yīng)路段的消耗值，訓(xùn)練路網(wǎng)中所有S-D對間的最小消耗值及消耗閾值矩陣.此過程中涉及到3個影響因子：消耗函數(shù)影響因子α，β和消耗閾值影響因子γ.其三者的大小決定了檢測結(jié)果的準(zhǔn)確度.通過動態(tài)調(diào)整α，β和γ，分別評估了消耗影響因子和消耗閾值影響因子對異常軌跡挖掘準(zhǔn)確度的影響，從而確定一組使檢測結(jié)果更準(zhǔn)確的影響因子值.

經(jīng)過大量實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)設(shè)置不同的影響因子時，得到的異常軌跡有所區(qū)別，且α和γ越大，檢測到的異常軌跡數(shù)目越少.其原因在于：1)當(dāng)α增大時，得到的各道路消耗值越高，得到的各S-D對最小消耗值越大;2)當(dāng)γ增大時，支撐異常軌跡檢測的消耗閾值矩陣中的各元素越大，意味著相同數(shù)據(jù)搜索范圍內(nèi)，得到的異常軌跡數(shù)目越少，當(dāng)消耗閾值到達(dá)一定極限，一些明顯異常的軌跡被錯誤認(rèn)定為正常.

因地圖匹配后軌跡遵循道路走向，繪制圖像后出現(xiàn)軌跡間的覆蓋，故采用局部數(shù)據(jù)來體現(xiàn)兩者之間的區(qū)別(后同).圖3顯示了在不同組α和β作用下的局部數(shù)據(jù)檢測結(jié)果，此時γ=1.4.圖4顯示了在不同γ值作用下的局部數(shù)據(jù)檢測結(jié)果，此時α=0.9，β=0.1.可以發(fā)現(xiàn)，當(dāng)α=0.9，β=0.1，γ=1.4時，整個算法的結(jié)果準(zhǔn)確度最高且最接近真實(shí)情況.由此可知，尋找一組最佳的α，β和γ的值，能夠極有效的提高算法檢測結(jié)果的準(zhǔn)確率.

(a) α=0.7,β=0.3 (b) α=0.8,β=0.2 (c) α=0.9,β=0.1圖3 參數(shù)α和β對算法的影響Fig.3 Influence of parameters α and β

(a) γ=1.2 (b) γ=1.3 (c) γ=1.4圖4 參數(shù)γ對算法的影響Fig.4 Influence of parameter γ

5.3 算法比較

為驗(yàn)證對道路消耗建模的性能優(yōu)于從軌跡出發(fā)建模的性能，在不同規(guī)模的數(shù)據(jù)集上，使用不同的參數(shù)方案，比較了PC-ATD、TRAOD、iBOAT、TPRO和TADSS的性能，測試集規(guī)模分別為100、200、400，參數(shù)設(shè)置見表1.PC-ATD算法需要的初始道路模型由訓(xùn)練集訓(xùn)練得到.

表1 PC-ATD、TRAOD 、iBOAT、TADSS和TPRO的參數(shù)設(shè)置Table 1 Parameters setting of PC-ATD、TRAOD、iBOAT、TADSS and TPRO

首先，TRAOD只能實(shí)現(xiàn)對小規(guī)模軌跡數(shù)據(jù)的檢測，需對數(shù)據(jù)進(jìn)行過濾，效率較低，且需設(shè)置6個參數(shù).在iBOAT和TPRO中，網(wǎng)格大小需多次調(diào)整，消耗大量的時間，TADSS直接從軌跡出發(fā)建模未考慮道路狀況的影響.而PC-ATD可以對大規(guī)模的數(shù)據(jù)集進(jìn)行檢測，且只需要很少的參數(shù)調(diào)整.其次結(jié)果表明，對于同一軌跡數(shù)據(jù)集，各參數(shù)對TRAOD算法運(yùn)行時間的影響是顯著的.但各種參數(shù)對PC-ATD運(yùn)行時間的影響很小.

觀察圖5可以發(fā)現(xiàn)，在初期與iBOAT和TRDSS相比，PC-ATD效率較高，但明顯低于TRAOD和TPRO，隨著軌跡的不斷收集，PC-ATD的效率逐漸超過iBOAT 和TADSS，并存在明顯優(yōu)勢.實(shí)驗(yàn)證明，PC-ATD的檢測結(jié)果更準(zhǔn)確，且在真實(shí)情況下更有效.更重要的是，提出了消耗閾值矩陣的概念，將檢測的角度從軌跡本身轉(zhuǎn)移到道路消耗，突破了只能檢測同一S-D對之間軌跡的局限，可以實(shí)現(xiàn)更大范圍的軌跡檢測.

(a) 軌跡測試集規(guī)模=100 (b) 軌跡測試集規(guī)模=200 (c)軌跡測試集規(guī)模=400圖5 PC-ATD、TRAOD、iBOAT、TADSS和TPRO的效率比較Fig.5 Comparison of experiment efficiency between PC-ATD、TRAOD、iBOAT、TADSS and TPRO

6 結(jié)束語

本文提出了一種基于軌跡壓縮和路網(wǎng)劃分的車輛異常軌跡檢測算法，通過地圖匹配將位置設(shè)備收集到的軌跡數(shù)據(jù)映射到路網(wǎng)空間，采用軌跡插點(diǎn)確保路網(wǎng)劃分后各路段上軌跡段的完整性，并根據(jù)插點(diǎn)和車輛在單一路段行駛方向是否改變對軌跡進(jìn)行壓縮，最后對軌跡數(shù)據(jù)進(jìn)行訓(xùn)練得到道路消耗模型，實(shí)現(xiàn)異常軌跡的實(shí)時檢測.經(jīng)過大量實(shí)驗(yàn)表明，該算法能夠有效檢測到數(shù)據(jù)集中的異常軌跡.將PC-ATD算法擴(kuò)展到基于分布式計算平臺上的分布是下一步工作重點(diǎn).