基于iBAT和DTW算法的異常軌跡檢測

逄煥利, 李紅巖

(長春工業大學 計算機科學與工程學院， 吉林 長春 130012)

0 引 言

近年來，隨著GPS(Global Positioning System)技術在各類電子產品和移動終端上的廣泛使用，生成大量軌跡數據，軌跡異常檢測已成為時空軌跡模式挖掘的重要研究內容。 軌跡異常檢測可以為不同的應用服務，例如城市的氣象監測[1]、交通實時路況監控[2-3]和熱點路徑發現[4]等。軌跡頻繁模式挖掘[5]和軌跡異常檢測[6]是軌跡數據挖掘的主要研究內容。

目前，學者們對時空軌跡的異常檢測做了大量研究，并提出了許多異常檢測算法。文獻[7]提出了經典的TRAOD算法,但是該算法計算效率不高、結果的準確性低；韓博洋等[8]提出了一種基于出租車GPS時空軌跡數據的異常軌跡檢測算法，該算法將離線挖掘與在線實時檢測相結合，其優點是具有實時性，可以快速反饋實時檢測的結果，但是由于時間和空間兩個維度的閾值設置比較困難，如果不能合理設置閾值，會在一定程度上影響到檢測效果；唐夢萌等[9]提出的算法效率在一定程度上得到了提高，但算法并沒有充分考慮軌跡的其他特征。因此，該算法不能提高異常軌跡檢測效果。在分析了異常“少而不同”的特征后，文獻[10-11]提出了一種基于隔離的異常軌跡(iBAT)，與其他異常檢測方法相比，該算法更接近于基于異常數據特征的異常檢測初衷。但是該算法在用網格表示軌跡的過程中，由于相似的軌跡可以生成不同的網格序列，結果一些正常軌跡被檢測為異常軌跡，不能達到期望的效果。

為了提高軌跡異常檢測效果，文中設計了一種結合iBAT和DTW算法的異常軌跡檢測算法。在使用iBAT發現異常的結果上加入相似軌跡度量的過程，應用相似性度量在出租車軌跡的異常檢測上，實現了降低軌跡異常檢測誤報率的目的。

1 相關原理

1.1 軌跡與軌跡異常

軌跡是記錄運動物體的歷史位置信息的時空數據，令Tr表示二維空間中的運動物體的軌跡:

Tr={(x1,y1,t1),(x2,y2,t2),…,(xn,yn,tn),…}

式中：(xi,yi,ti)----移動對象在ti時刻的經緯度，即該對象的位置信息。

異常軌跡是不遵循預期規則模式的事件，即表現出不符合相似性標準的行為。

1.2 軌跡異常檢測

1.2.1 時空軌跡相似性度量

軌跡異常檢測的前提是定義軌跡相似性度量的標準，通常使用軌跡點或軌跡段之間的距離測量來描述軌跡之間的相似度。有幾種典型的軌跡相似性度量，包括歐幾里德距離、Hausdorff、DTW、LCSS等。

歐幾里德距離是解決序列相似性問題的一種方法，但是，它不適用于長度不等或時間尺度不一致的軌跡數據，并且對噪聲數據敏感；Hausdorff距離是兩組點之間距離的度量(不匹配程度)；DTW方法首先應用于語音識別領域，并應用于軌道距離的計算，解決了不同采樣率和規模的問題；LCSS方法通常用于計算兩個軌道之間的最長相似子軌道序列的長度，其表示軌道之間的相似度。盡管LCSS可以處理噪聲軌跡數據，但是該方法不考慮軌道之間類似子序列之間的不同間隙的大小，降低了相似性測量的準確度。

1.2.2 軌跡異常檢測方法的分類

到目前為止，學者們提出了許多檢測軌跡異常的方法，大致可分為四類：基于分類的檢測方法、基于歷史相似性的檢測方法、基于距離的檢測方法和基于網格的檢測方法。時空軌跡數據異常檢測技術分類如圖1所示。

圖1 時空軌跡數據異常檢測技術分類

基于分類的檢測方法在給定一個訓練數據集后，可以取得很好的檢測效果，但是由于時空軌跡數據中的異常通常是未知的，所以很難找到一個完備的訓練數據集，因此基于分類的異常檢測方法并不適用于在線異常檢測；基于歷史相似性的檢測方法通過大量歷史軌跡數據構建模型，在交通異常檢測中有著廣泛的應用，但是增量更新會有較高的計算開銷；基于距離的異常檢測通常關注異常子軌跡、異常片段，所以忽略了軌跡的時空相似性；基于網格劃分的異常檢測通過城市路網劃分成相等大小的網格單元，通過識別網格單元的單元序列進行異常檢測，可分為基于似然比檢驗統計量的異常軌跡檢測、基于隔離機制的異常軌跡檢測、基于方向和密度的進化異常軌跡檢測。

2 iBAT+DTW方法

文中提出的異常軌跡檢測方法采用基于隔離機制(iBAT)的異常軌跡檢測方法來檢測軌跡異常。 在得到正常和異常軌跡之后，再結合動態時間規整方法進行軌跡相似性測量，進一步劃分軌跡，從而達到降低異常檢測誤報率的目的。文中異常軌跡檢測過程如圖2所示。

圖2 異常檢測流程

步驟如下：

1)預處理軌跡并提取相同的起始軌跡；

2)使用iBAT算法進行異常檢測(計算異常分數)；

3)根據異常分值初步劃分異常軌跡集合與正常軌跡集合；

4)計算DTW分值ScoreDTW，并使用DTW算法測量相似度；

5)若ScoreDTW>DTW閾值，則標記為異常軌跡，否則標記為正常軌跡。

iBAT算法描述如下：

輸入：t-待檢測軌跡；T-軌跡集合；m-二叉樹的個數；ψ-二次采樣樣本大小。

輸出：異常分值s(t,ψ)。

過程：

ni=0

for i=1 to m do

T'←隨機從軌跡集合T中選取樣本，樣本大小為ψ

repeat

ni←ni+1

隨機從軌跡t中選取一個網格p

T'←從樣本T'中選取包含網格P的軌跡

until直到T'為空

end for

根據公式計算異常分值s(t,ψ)。

2.1 預處理

由于GPS裝置收集的數據具有一些偏差數據，如數據異常、緯度和經度越界等，這些數據將影響軌跡異常檢測結果的準確性。為了降低噪聲數據對異常檢測性能的影響，首先要對數據進行分析，刪除無用屬性，清洗噪聲數據如空值或者無效地址和時間。預處理數據見表1。

表1 GPS軌跡數據表

2.2 異常檢測

地圖首先被劃分為250 m×250 m的統一網格。 根據每個網格單元在網格中的位置分配給每個網格單元一個網格ID(Grid_ID)。 之后，每個滑行軌跡的坐標被映射到網格單元，并且網格ID用于表示軌跡的緯度和經度坐標。 將這個過程進行下去，每個軌跡的輸出就是一組網格ID序列(Grid_Seq)，完成用網格序列表示軌跡。 以兩條軌跡Tra1和Tra2為例，過程如圖3所示。

完成以上過程后，所有的軌跡都被表示成一組網格序列，將通過相同起-終點網格對的軌跡劃分為一組，這樣問題就被轉化為尋找相同起-終點網格對中的異常軌跡。軌跡相同起-終點分類的過程如圖4所示。

圖3 網格序列表示軌跡過程

圖4 軌跡相同起-終點分類過程

一個特定的網格代表一個特定的區域，在劃分區域時，使用的網格大小為250 m×250 m。

iBAT異常檢測的最后一步是計算異常分值，來決定軌跡是異常軌跡還是正常軌跡，公式如下：

(1)

(2)

式中：t----要隔離的軌跡數據；

n(t)----隔離t用到的網格數；

E(n(t))----平均網格數，也表示數據t在N棵iTree的路徑長度的均值；

s(t,N)----數據t在由N個樣本的訓練數據構成的iTree的異常指數，數據t最終的異常分值是綜合了多棵iTree的結果；

c(N)----用N條數據構建的二叉樹的平均路徑長度，在這里主要用來做歸一化。

其中，H(N-1)可用ln(N-1)+0.577 215 66估算，這里的常數是歐拉系數。

從異常分值的公式看，異常分值s(t,N)越接近于1，表明數據t越異常；異常分值s(t,N)越接近于0，表明數據t越正常；如果異常分值s(t,N)在0.5附近，表明數據t在多棵iTree中的平均路徑長度接近整體的平均值。

2.3 相似性度量

在根據iBAT算法獲得正常和異常軌跡之后，下一步是使用動態時間扭曲(DTW)算法測量所有軌跡的相似性。 正常軌跡被定義為軌跡-1，異常軌跡被定義為軌跡-2。相似性度量過程如圖5所示。

圖5 相似性度量過程

當前研究的輸入數據是有經度坐標和緯度坐標的GPS數據，d為兩點間距離：

(3)

同時使用的分值ScoreDTW是坐標之間的平均距離，即：

(4)

公式計算的結果是軌跡的相似度，分值越小，則軌跡越相似。公式中使用0.000 7閾值，在實驗環節這個閾值會更精確。

3 仿真實驗與分析

3.1 實驗準備

文中所有算法均通過python編程實現，并結合MATLAB進行了實驗數據的仿真測試。實驗運行機器為i5-5300U，64位Windows7操作系統，2.4 GHz CPU，4.0 GB內存。

該實驗使用Cabspotting項目提供的真實出租車GPS軌跡數據，其中包括2008年在美國舊金山收集的出租車軌跡。每條記錄每隔1 min采集一次位置信息。為了驗證算法的有效性，文中設計了五組異常檢測實驗。從數據集中選出5個相同起-終點的網格對作為實驗數據集，人工標記出異常軌跡，實驗數據集見表2。

表2 實驗數據集

3.2 網格單元大小實驗

本實驗環節是為了確定用以軌跡分類的網格單元的大小，實驗用到的網格大小為100～500 m，網格單元大小實驗如圖6所示。

圖6 網格單元大小實驗

由圖6可以看出，網格越寬，可以形成的簇越少，然而包含最少3個成員的簇的數量會增加，這是因為網格的大小會極大地影響被覆蓋的軌跡數量，如果網格太大，那么大多軌跡會在一個簇中被包含，從而發現異常水平會越低。基于地理位置信息和實際路徑信息，將所研究區域劃分為100 m×200 m統一的網格，使用的網格大小為250 m×250 m。

3.3 iBAT變量實驗

異常檢測性能評價指標包括檢測率(Detection Rate, DR)、誤報率(False Alarm Rate, FAR)、ROC曲線、查準率等，文中選擇前3個指標對算法進行評價。DR是異常軌跡被成功檢測出來的比率，FAR是正常軌跡被檢測為異常的比率，這是評價異常檢測方法的兩個重要指標。一個好的異常檢測算法應該同時具備高檢測率(DR)和低誤報率(FAR)，ROC曲線可以用來描述兩者之間的均衡程度，在算法評估時，需要一個量化指標來衡量檢測效果的好壞，可以用ROC曲線下的面積(Area Under Curve, AUC)來量化，通常，AUC越大，表示檢測算法性能越好。

除了待檢測軌跡t和軌跡集合T，影響iBAT算法效果和時間效率的主要參數有兩個：二叉樹個數m和二次采樣樣本大小ψ。通過實驗對比不同取值的AUC值，分別如圖7和圖8所示。

圖7 iBAT參數m實驗

圖8 iBAT參數ψ實驗

圖7是m取值[1,200]時AUC值的曲線，圖8為ψ={2，4，8，16，32，…,1 024}時AUC值的曲線，由圖中可以得出兩個參數分別設置為m=100，ψ=256實驗效果最好。

3.4 DTW閾值實驗

本實驗的目的是確定最優閾值作為判斷軌跡正常還是異常的極限值。DTW閾值實驗如圖9所示。

圖9 DTW閾值實驗

閾值為0.000 7時，錯誤檢測達到最低值。0.000 7的值有一個十進制單位，其中1個十進制等于111 319 m。這表明，在研究中，軌跡之間的平均公差大約是77.9 m。

3.5 實驗結果

通過比較iBAT和iBAT+DTW的檢測結果，將iBAT+DTW進行分析，結果表明，使用iBAT+DTW方法誤報率為0.027，使用iBAT的誤報率達到0.124，見表3。

表3 異常檢測結果

比較兩種算法的AUC值，可以得出iBAT+DTW比iBAT檢測精度更高的結論，如圖10所示。

圖10 實驗對比圖

由圖中可見,iBAT+DTW是合適的度量相似性以及減少錯誤檢測的軌跡異常檢測方法。

4 結 語

從降低軌跡異常檢測誤報率的角度出發，提出了一種結合iBAT和DTW的軌跡異常檢測算法，其在應用基于隔離機制的異常檢測算法基礎上加入相似性度量，并從網格單元大小、iBAT變量實驗以及DTW閾值方面對算法進行了仿真分析，結果表明，相比iBAT算法，iBAT+DTW性能較優，能有效降低軌跡異常檢測的誤報率。