基于Bi-LSTM模型的軌跡異常點檢測算法

韓昭蓉 黃廷磊 任文娟 許光鑾

①(中國科學院大學 北京 100049)

②(中國科學院電子學研究所 北京 100190)

③(中國科學院空間信息處理與應用系統技術重點實驗室 北京 100190)

1 引言

隨著定位技術、無線通信技術和存儲計算能力的飛速發展，大量移動目標的軌跡數據呈爆炸式的增長，包括人類活動軌跡、交通軌跡數據和動物遷徙數據等。軌跡大數據中蘊藏著豐富的有價值的目標活動信息，因此國內外學者對軌跡數據挖掘任務進行了大量的探索和研究，如軌跡聚類[1]、軌跡關聯分析[2，3]、目標運動模式識別[4]、路徑規劃[5]和異常模式檢測[6]等。分析挖掘時空軌跡數據在科研領域和人類生活應用方面都具有重大意義。但是，軌跡數據在現實環境下從來都不是完全準確的[7]，數據中存在許多與其鄰近大部分軌跡點在運動特征上有顯著差異的不合理的采樣點，這些點稱為軌跡數據中的異常點。異常點的存在嚴重降低了軌跡數據的質量，同時會引起后續軌跡知識發現結果的不準確甚至錯誤。因此，軌跡異常點檢測是軌跡數據挖掘前至關重要的一步。

本文以實驗室現有的船舶軌跡數據為研究對象，數據由多種不同數據源偵測獲得，各個數據源之間定位精度差異較大，由于不同數據源定位誤差的差異、環境干擾、人為操作失誤或是目標刻意偽裝欺騙，船舶軌跡數據中存在著大量不符合目標運動規律的異常點。Hawkins在1980年對異常點提出的定義為：異常點是指在數據集中顯著偏離其它絕大部分數據的那些數據對象，以至于引起人們懷疑它們是由完全不同的機制產生的[8]。傳統異常點檢測算法主要分為基于統計的方法、基于距離的方法、基于密度的方法和基于分類的方法等[9]。在基于分類的檢測方法中，首先訓練一個可以區分正常數據和異常點的分類模型，然后用預先訓練好的模型來判斷新的觀測點是否異常。方法學到的模型能夠更加接近數據的實際規律，具有良好的可擴展性。

在軌跡的異常點檢測問題上，由于軌跡數據是基于時間和空間的位置序列，相鄰點有著上下文關系，這使得傳統的異常點檢測方法不能直接用于檢測軌跡序列數據中的異常點。Alvares等人[10]、Chen等人[11]和Zheng等人[12]均采用恒定速度閾值法來檢測出軌跡數據中的異常點，依次選取每個軌跡點與其前一個點計算即時速度，速度超出設定的恒定閾值即判定為異常點，去除檢測出的異常點后再進行軌跡數據挖掘任務。Chen等人[13]提出了一種基于模型的GPS軌跡清理算法，采用三次平滑樣條和時間序列方法分別對軌跡的趨勢和殘差進行自適應建模，可有效檢測出低精度GPS軌跡上的異常點。Hu[14]結合規則軌跡集對監控區域內的船舶實時軌跡數據進行異常檢測，船舶航速超出區域內正常最高航速則為異常的船舶軌跡點，進而識別異常船舶并進行預警。Wu等人[15]通過分析大量AIS(Automatic Identification System，船舶自動識別)軌跡數據，歸納出幾種類型的軌跡異常點，并設計了對應的規則來實現檢測，包括有：根據兩點間的經緯度差值所對應的邏輯距離來判斷；不在正常的AIS通信范圍內為異常點；兩點間實際距離與理論距離(由航速及時間計算出)的差值超過一定閾值則為異常點，最后采用擬合插值法對軌跡進行修復。上述方法均根據特定的軌跡數據人工設置了相應的參數和規則來完成檢測，其存在的主要問題是：(1)參數設置過程需要大量的人工分析和測試調整，較為繁瑣；(2)由于移動目標會有不同的運動狀態，人工難以設定出契合數據的準確的參數閾值或模型，方法容易出現漏檢和錯檢的情況；(3)方法通常只適用于特定類型的軌跡數據，擴展性不強。總地來說，這些方法的檢測性能高度依賴于參數是否準確，不能自動學習軌跡異常點和正常數據的差異，對復雜類型數據適用性較差。

目前，深度學習方法已被證實可以直接從大數據中自動學習特征，在異常檢測任務中也具有較大的潛力。Bessa等人[16]提出了一種交互可視化和檢測異常軌跡段的工具RioBusData，工具基于一個多層的卷積神經網絡(Convolutional Neural Network， CNN)，在公交車軌跡數據上的實驗結果表明，方法可以有效檢測出異常線路的公交車、時間異常軌跡段和空間異常軌跡段。Fernando等人[17]提出了一種新穎的基于長短時記憶網絡(Long Short-Term Memory， LSTM)的編碼器-解碼器框架，引入了注意力機制，能夠根據行人和其周圍鄰居的歷史軌跡預測出感興趣行人的未來位置，方法在兩個具有挑戰性的數據集上均表現出了出色的性能，同時通過對比預測路徑和行人的真實路徑可以檢測出異常的行為。

在實際問題的驅動和上述深度學習應用的啟發下，考慮到長短時記憶網絡在序列處理任務中優異的特征學習能力，本文提出了一種基于雙向長短時記憶網絡(Bidirectional LSTM， Bi-LSTM)的軌跡異常點檢測算法。本文設計了一個Bi-LSTM模型，對每個軌跡點構建一個6維的運動特征向量，選取一段時間的軌跡數據特征向量作為模型的輸入，模型輸出為軌跡點的分類結果(1為異常點，0為正常點)。同時，算法采用了欠采樣和過采樣的組合方法緩解類別不平衡對檢測性能的影響。最后通過實驗驗證了基于Bi-LSTM模型的軌跡異常點檢測算法的有效性。

2 算法描述

本文算法的核心思想是將軌跡異常點檢測問題轉化為有監督的分類問題，然后構建能夠有效處理時序數據的長短時記憶網絡模型予以解決。以下本文將首先介紹軌跡點的特征向量提取過程，然后對長短時記憶網絡的相關理論知識進行描述，最后介紹本文模型的網絡結構和整個算法的流程。

2.1 特征提取

特征提取是指應用專業領域知識從原始數據中找出一些具有物理意義的特征，是機器學習算法能夠有效工作的重要過程。好的特征可以極大提高學習系統的性能。軌跡數據是由一系列隨時間變化的時空數據點組成，即 TR：P1→P2→???→Plen，這里第i個軌跡點可以表示為Pi=(loni,lati,ti)，loni， l ati為軌跡點的經度和緯度值，ti為該點的時間戳信息。對每個軌跡點，本文提取了一個6維的運動特征向量，包括航速(speed)、加速度(acceleration)、航向(course)、轉角(turning angle)、轉角率(turning rate)和曲率(sinuosity)。這些參數特征均為移動目標運動特性的重要表征。

以圖1為例，本文對每個特征進行介紹。航速是移動目標位置變化的速率，用于表示運動快慢的程度。加速度是目標航速對于時間的變化率，描述航速變化的快慢。軌跡中異常點通常比其鄰近點有更大的航速或加速度值。對軌跡點Pi，其航速和加速度計算公式分別如下：

其中，dist(Pi,Pi-1) 表示點Pi和其前一個點Pi-1間的距離。

圖1 軌跡示意圖Fig.1 A diagram of trajectory segment

航向定義為軌跡中連續點之間的移動朝向，本文取當前軌跡點與后一時刻軌跡點的連線與正北方向的夾角來表示，而轉角表示兩個連續軌跡點航向間的變化。與周圍軌跡點相比，那些航向值和轉角值明顯不同的點為異常點的可能性更大。轉角率表示連續軌跡點轉角變化量與時間的比值。航向、轉角、轉角率的計算公式分別如下所示：

曲率定義為兩點之間移動距離與直線距離的比值。如式(6)所示，本文計算軌跡點的曲率為該點與前后兩個時刻軌跡點的距離和與前后時刻軌跡點直接距離的比值。從軌跡曲線可以看出來，正常點的曲率值要遠小于異常點的曲率值。

本文提取的6個特征值都能真實反映目標在時空上的運動狀態，可為軌跡點的分類提供有用信息，從而有助于提高檢測精度。

2.2 長短時記憶網絡

長短時記憶網絡(Long Short-Term Memory，LSTM)[18]是循環神經網絡(Recurrent Neural Network， RNN)的一種特殊形式，通過引入記憶單元和門限機制的巧妙構思，能夠學習長期依賴關系，緩解RNN存在的梯度消失和梯度爆炸問題，已廣泛應用在序列處理任務中。

如圖2所示，LSTM單元主要由4個部分組成：記憶單元(Memory cell)，輸入門(Input gate)，輸出門(Output gate)及遺忘門(Forget gate)。記憶單元之間彼此循環連接，3個非線性門控單元可以調節流入和流出記憶單元的信息。LSTM的前向計算公式如下所示：

其中，t是當前時刻輸入向量，， ， 分別為遺忘門、輸入門、輸出門的激活向量，為記憶單元向量，是LSTM單元的輸出向量，， 分別為權重矩陣和偏置向量，σ為激活函數，本文選用sigmod函數，符號“°”為哈達瑪積(矩陣對應元素相乘)。

圖2 LSTM模塊單元Fig.2 LSTM model unit

LSTM在預測當前時刻輸出時，只利用前面時刻的歷史序列信息，但往往輸出同樣取決于后續時刻的信息。為了充分利用上下文信息，Graves提出了Bi-LSTM模型[19]，Bi-LSTM網絡結合時間上從序列起點開始移動的LSTM和另一時間上從序列末尾開始移動的LSTM，其輸出單元由正向LSTM和反向LSTM的狀態連接得到。融合了LSTM單元和雙向網絡，雙向LSTM模型在語音識別、手寫體識別、序列標注等學習任務中性能均有一定的提升。

2.3 模型構建

本文設計了一個雙向LSTM (Bi-LSTM)模型，結構如圖3所示。Bi-LSTM模型由兩層Bi-LSTM網絡和兩層全連接層組成，用到了當前時刻和前后t時刻的上下文信息，通過正向、反向LSTM分別提取軌跡特征信息，適合離線檢測軌跡數據中的異常點。

圖3 雙向LSTM模型Fig.3 A bidirectional LSTM network

在特征構建過程后，每一個軌跡點均由一個6維向量來表示，即i=｛vi,ai,coursei,turnAnglei,ωi,si｝。模型結構圖中，0表示當前時刻的軌跡點輸入信息，-i和i分別表示0前后i時刻的軌跡點信息。模型的輸入為一定序列長度的軌跡點向量，由Bi-LSTM自動提取序列間的特征，最后再通過兩層全連接層對軌跡點進行分類。其中，異常點類標號為1(正類)，正常點類標號為0(負類)，Bi-LSTM模型序列長度為 2t+1。由于充分考慮到一段時間內軌跡數據點的運動特征信息，Bi-LSTM模型在訓練過程中可以自動學習到復雜軌跡序列中異常點和正常點的差異，模型一經訓練好即可以用于軌跡異常點的檢測，具有較高的實用性。為了提高模型的泛化能力，本文在Bi-LSTM層和第1層全連接層之間添加了dropout機制[20]，dropout通過部分連接來防止模型過擬合。

對每個軌跡點提取一定長度軌跡序列的運動特征后，算法采用訓練好的Bi-LSTM模型來進行預測判斷。算法流程如圖4所示。

3 實驗驗證

3.1 數據集

本文采用了一個真實的船舶軌跡數據集來驗證算法的有效性。船舶軌跡數據來源于實際項目，由多種數據源探測獲得。本文隨機抽取了船舶的300條軌跡數據，由多個有經驗的判讀員根據整條軌跡的統計分析和每個軌跡點相對于其鄰近點的位置、航速和加速度信息對軌跡數據進行檢驗標注，數據集的標注具有較高的可靠度，由此，本文建立了一個船舶軌跡標記數據集，其中，異常點標記為1(正類)，正常數據標記為0(負類)。在具體的數據分析標注過程中，本文發現船舶軌跡數據中的異常點主要分為以下幾種情形：(1)船舶運動平穩，異常點速度超出其周圍點的速度但是沒有超出目標的運動能力；(2)由于某些數據源定位精度較低或存在干擾情況，異常點嚴重偏離船舶航跡，其速度值超出目標最高航速；(3)目標軌跡點來回跳躍，航跡明顯由兩段不同的軌跡組成，這是由于在數據收集過程中錯誤地將兩艘船的軌跡判識為同一個運動對象的。異常點通常為單個孤立的，同時也會有幾個連續異常點的情況出現，軌跡異常點與其鄰近點均有著較大的差異。圖5為兩段軌跡的標注結果，異常點用紅色三角形表示。從圖中可以看出，去除異常點的軌跡更為平滑，符合船舶的運動情況。

數據集中，正常點個數為60872，異常點個數為1456。負樣本和正樣本的比例約為42：1，可見存在數據類別分布不平衡的問題，這通常會影響學習系統的性能。本文將數據集隨機劃分為訓練集(70%)和測試集(30%)。本文采用欠采樣和過采樣的組合方法SMOTE+ENN[21]來平衡訓練數據的類別分布。SMOTE (Synthetic Minority Oversampling Technique)是一種過采樣方法，其主要思想是通過在幾個少數類樣本間插值來形成新的少數類樣本。但是，在插值過程中，SMOTE會產生噪聲樣本。這個問題可以通過使用欠采樣方法ENN (Edited Nearest Neighbor)對插值結果進行清理來解決，任何與其k個最近鄰居類別不同的樣本都會被移除，從而產生一個類別平衡的訓練集。本文最終在測試集上評估各個模型的檢測性能。

圖4 算法流程圖Fig.4 The flowchart of our proposed algorithm

圖5 兩段軌跡的標記結果Fig.5 Tagging results for two track segments

表1 分類結果混淆矩陣Tab.1 Confusion matrix of classification results

3.2 評價指標

本文采用多種常用的機器學習評價指標[22]，包括精度(Accuracy)、準確率(Precision)、召回率(Recall)、F1值(F1-score)、ROC曲線(Receiver Operating Characteristic Curve)和AUC值(Area Under ROC Curve)。對于二分類問題，可將樣例根據真實情況和模型預測類別的組合劃分為真正例、假正例、真反例和假反例，分類結果的混淆矩陣如表1所示。

精度定義為正確預測樣本數占總樣本數的比率。準確率定義為正確預測的正樣本數占總的預測為正樣本數的比率，召回率則定義為正確預測的正樣本數占實際正樣本總數的比率，在異常檢測應用中，相比于不將正常值錯判為異常值，盡可能多地捕捉到所有的異常值更為重要，本文將更加關注召回率指標。F1值是準確率和召回率的調和均值，值較高時說明分類器性能好。這4種指標的公式分別如下所示：

ROC曲線表示真正例率(True Positive Rate，TPR)和假正例率(False Positive Rate， FPR)的關系。TPR為成功檢測到的異常點的比率，FPR為錯判為異常的正常點的比率，定義如式(12)所示。顯然，異常檢測算法應該具有較高的TPR值和較低的FPR值。當無法從ROC曲線直觀比較出不同模型性能時，可以通過比較ROC曲線下的面積，即AUC值，AUC值越接近于1，表示算法的性能越好。而且，ROC曲線和AUC值對類別分布不平衡的數據不敏感[23]。

3.3 實驗設置

本文采用Pytorch框架構建Bi-LSTM模型，在NVIDIA GTX 1080顯卡上訓練模型。每個軌跡點的輸入向量維度為6， Bi-LSTM單元的隱藏層維度設置為3， dropout比例設置為0.5，兩層全連接層節點數分別設置為6和2，最終模型輸出為0(正常)或1(異常)。本文嘗試采用單層和多層Bi-LSTM實現軌跡異常點檢測，雙層網絡性能較優異，所以在實驗中采用圖3所示模型。

軌跡序列長度并不確定，本文測試驗證了截取時間長度t在1～25之間的模型性能，采用較短的時間長度會造成信息丟失，而采用較長的時間長度造成較長的訓練時間同時由于目標運動狀態變化影響檢測性能，經過實驗驗證，本文時間序列長度t設置為10可以取得較好的實驗結果。

3.4 實驗結果與分析

為了驗證本文Bi-LSTM模型的有效性和創新性，將網絡模型與恒定速度閾值法、4種經典的機器學習分類方法和卷積神經網絡模型做了對比實驗。在恒定速度閾值方法(Constant Velocity Threshold Algorithm， CVTA)中，通過對數據集上的速度分析，設定恒定速度閾值為20 m/s，依次計算每個軌跡點的速度值，速度值超過閾值則判定為異常點。4種分類算法在工業界都得到了廣泛使用，分別為：邏輯回歸(Logistic Regression， LR)，決策樹(Decision Tree， DT)，隨機森林(Random Forest， RF)， XGBoost (eXtreme Gradient Boosting)。本文采用scikit-learn包[24]實現了上述4種分類算法，其輸入為每個軌跡點的6維運動特征向量。CNN網絡結構參考文獻[16]，修改模型輸入為軌跡點的6維向量，輸出為2維向量。

本文采用5折交叉驗證法對4種分類模型分別調整了參數，通過統計算法分類精度隨每個參數的變化，選擇分類精度達到最高值時的參數值，從而使得這些分類算法均能獲得較好性能。表2是不同方法在測試集上的檢測性能指標及所用時間的比較。圖6描述了不同分類模型的ROC曲線圖。從表2和圖6可以看出，本文提出的算法各項指標均高于其他對比方法，尤其是召回率和AUC值，Bi-LSTM模型遠高于其他機器學習分類算法和速度閾值方法。高召回率意味著模型檢測到更多真實的異常點，這在異常檢測問題中是非常重要的。

表2 不同方法指標對比Tab.2 The performance of different models

圖6 不同模型的ROC曲線圖Fig.6 ROC curves of different models

在軌跡異常點檢測問題中，一個異常軌跡點通常跟其周圍正常的鄰近點在運動特征上有著較大的差異。由于恒定速度閾值法未考慮每個軌跡段上目標運動狀態，LR， DT， RF， XGBoost算法和CNN模型僅使用了當前檢測點的特征信息，沒有考慮到當前點相鄰時間內的目標運動信息，這些算法檢測性能均較低。特別是LR和CNN模型召回率較低，這意味著算法漏檢了許多軌跡異常點。從測試時長對比可以發現，本文Bi-LSTM模型速度快于同樣為深度學習的CNN網絡，可以用于軌跡異常點的快速檢測。

Bi-LSTM模型利用了當前點和其前后t時刻內的軌跡上下文信息。由于LSTM單元和雙向網絡的獨特設計，雙向LSTM能夠自動學習正常點和異常點在序列運動特征上的差異性，免除了與數據時序性相關繁重的特征工程，為異常檢測提供有效決策支持。本文提出的Bi-LSTM模型還可以方便地移植到其他不同軌跡數據或類似的處理任務上。在類別已標記好的軌跡數據集上，Bi-LSTM模型可以預先訓練好。在對軌跡數據進行后續挖掘任務之前，可以采用預訓練好Bi-LSTM模型準確地去除異常點，從而大幅度提高數據質量，提高挖掘任務精度。

4 結論

本文提出了一種基于雙向長短時記憶網絡模型的軌跡異常點檢測算法。首先對每個軌跡點提取了6維的運動特征向量來表示軌跡點，然后將軌跡異常點檢測問題轉化為有監督的分類問題，通過對軌跡異常點檢測問題的分析，構建了Bi-LSTM模型來自動學習一段長度軌跡數據中的抽象特征。同時，采取了過采樣和欠采樣的組合方法緩解類別不平衡對算法性能的影響。Bi-LSTM考慮了軌跡點的歷史和未來信息，適用于離線處理時準確地檢測異常點，模型訓練好后檢測過程非?？焖?，而且擴展性強。在真實的船舶軌跡標注數據集上，實驗結果表明算法相對于不考慮時序特征的機器學習經典分類算法和卷積神經網絡的有效性。在下一步工作中，本文將研究采用LSTM的變體單元(如QRNN，SRU)，通過提高網絡的計算速度來加快軌跡異常點的檢測速度，同時，將算法擴展至更多不同目標的軌跡數據上也是其中的一個重要研究方向。