一種基于長短記憶模型的交通軌跡異常挖掘模型

秦勝君　李婷

摘? 要：針對現有異常軌跡檢測方法沒有捕捉軌跡數據時序特征，不能有效識別業務異常和新型異常等問題，提出基于長短記憶模型的異常軌跡挖掘模型.首先通過優化長短記憶模型進行軌跡預測，然后基于進化理論將預測軌跡轉化為異常軌跡，從而構建了基于長短記憶模型的異常判別模型.該模型可以有效地識別業務異常和新型異常，提高了異常檢測的精準度和可擴展性，同時適用于無標簽數據，解決了傳統神經網絡必須應用于有監督學習的問題.最后通過與改進的密度聚類算法和馬爾科夫過程的對比實驗驗證了該模型在交通軌跡異常檢測的優越性.

關鍵詞：長短記憶模型;異常軌跡;交通大數據;深度學習

中圖分類號：TP273;U491? DOI：10.16375/j.cnki.cn45-1395/t.2021.02.010

0引言

隨著傳感器網絡和無線通信等新興技術的不斷發展，越來越多的軌跡數據被收集和保存，軌跡數據挖掘有助于找出移動對象隱藏的模式信息或行為意圖[1].異常軌跡數據挖掘是指識別隱藏在正常軌跡數據中的異常軌跡.異常軌跡不同于噪聲點，噪聲點會干擾挖掘工作，降低結果的有效性，而異常軌跡可能預示著有趣事件的發生，比如公共安全中的突發事件、交通事故、高速逃費行為等，從而具有更高的研究價值[2].

根據實現方法的不同，異常軌跡檢測方法可以分為4類：基于聚類的檢測方法、基于網格的檢測方法、 基于分類的檢測方法、基于統計學的檢測方法.

基于聚類的檢測方法是使用密度聚類、模糊聚類等方法，發現遠離主體軌跡的少部分軌跡.例如，文獻[3]先對軌跡進行切分分組，然后使用密度聚類方法找出異常軌跡.何明等[4]提出改進密度聚類與模式信息挖掘的異常軌跡識別方法，結合上海市與北京市出租車軌跡進行實驗，驗證了該算法的有效性.

基于網格的檢測方法是將城市路網劃分成均等大小的網格單元，從而識別出異常的網格單元序列.主要的實現方法有基于似然比統計量的檢測方法[5]和基于隔離機制的異常檢測方法[6].也有學者提出路網空間下基于馬爾科夫決策過程的異常軌跡檢測方法[7].

基于分類的檢測方法是使用有監督的分類方法識別正常軌跡和異常軌跡.如俞慶英等[8]提出基于BP神經網絡的異常軌跡檢測方法.Li等[9]使用支持向量機進行特征學習，該方法可處理高維特征空間的異常檢測.

基于統計學的檢測方法是應用統計學相關理論進行異常檢測.例如，安計勇等[10]提出一種多因素異常檢測集成算法.首先通過統計數據分布給每種特征賦予一個異常分值，然后利用組合函數對分值集成，由此進行最終異常檢測.汪霜霜等[11]研究了一種車輛軌跡學習自適應稀疏重構方法，以識別一場車輛運動模式.

綜上所述，異常軌跡領域已有很多研究成果，為數據挖掘和智能交通提供了重要的理論基礎和應用支撐.但是上述研究存在以下兩個問題：1）基于聚類或分類的方法都沒有考慮時序問題，交通軌跡是時序數據，分析軌跡時序有助于提高異常檢測有效性;2）業務異常問題，現有的方法大多是根據歷史數據中正常軌跡和異常軌跡的距離來判斷是否異常，但是并沒有考慮過業務異常問題，因此無法有效識別業務異常.為解決上述問題，本文提出基于長短記憶模型的異常軌跡檢測方法.首先優化長短記憶模型預測下一階段軌跡，在已預測出的軌跡數據中進行特征值的變異從而形成異常軌跡，再將正常軌跡和異常軌跡輸入神經網絡模型進行訓練，最終形成基于長短記憶模型的異常軌跡檢測方法.該模型解決了傳統算法在識別業務異常時需要大量有標簽數據的問題，并且在異常檢測時加入變異因子，提高了模型在識別新型異常時的有效性.

1相關定義

車輛行駛軌跡本質是多屬性的時間空間點序列，聚類等方法是使用距離來判別異常，該方法可以有效地判別數值異常，也就是在數值上偏離大部分軌跡的異常軌跡，而無法判斷業務異常. 比如高速路上大貨車的行駛軌跡，兩段路程中車輛載重變化在核定載重范圍內浮動都屬正常，但是速度變化過大則有可能是超速，屬于異常事件，因此不能僅僅以兩條軌跡的距離來判斷是否異常，以非線性的判別方式更符合需求.

1.1?? 軌跡基本定義

軌跡數據集中包含多輛車的多條軌跡.假設車輛軌跡數據集[CTD={CT1， CT2， …， CTi， …， CTn}]，[i=0， 1， …， n].每輛車的軌跡數據集合可以表示為：[CTi={Ti1， Ti2， …， Tij， …， Tim}]，[j=0， 1， …， m].單條軌跡[T]又包含相關特征，表示為：[Tj=（pj1， pj2， …， pjs， tj）]，[t0

軌跡[T]包含地理位置、速度、平均速度、時長、載重等相關特征.

1）地理位置：該特征表明車輛的行駛路線，可能是車輛所在的經緯度，也可以是車輛的出發地點.地理位置標志著車輛在運動空間內的位置移動情況.

2）速度：速度指的是在某個時刻車輛的行駛速度，一般是使用GPS等設備采集.

3）平均速度：該特征表示在某一段時間內車輛運行的平均速度.

4）時長：表明車輛從軌跡的出發點到某個位置的行駛時長.

5）載重：表示車輛所載重量.比如高速路上貨車的載重量是判斷異常的指標之一;出租車是否載人也有助于判斷出租車軌跡是否異常.

除上述特征之外，還有加速度、轉角等可用于識別軌跡異常，根據實際情況不同，可選擇不同的特征.

1.2?? 異常相關定義

文中根據軌跡異常情況不同，將異常分為數值異常和業務異常.

1）數值異常

數值異常（data anomaly，DA）也可稱為線性異常，指與正常軌跡的距離超過某個閾值的異常軌跡.可如下定義：

[Ti-Ta≥Av]? （1）

式（1）中：假設[Ti]為正常軌跡，[Av]為設定的閾值，[·]為距離度量，可以是歐式距離或者Hausdorff等距離度量方式.如果兩條軌跡滿足式（1），則[Ta]為數值異常軌跡.

在實際業務中，有可能出現距離度量無法判別異常軌跡.例如一輛貨車在高速公路的正常行駛軌跡為120 km/h，載重20 t，該軌跡可表述為（120，20）.假如軌跡變換為（120，40），沒有超出載重范圍，因此該軌跡仍然為正常軌跡，但是如果軌跡變為（140，20），則被認為是超速，視為不安全駕駛行為，由此該軌跡檢測為異常軌跡.雖然上述假設的兩條軌跡與原始軌跡的距離一樣，但是前者為正常，后者為異常.文中將此類異常定義為業務異常.

2）業務異常

業務異常（business anomaly，BA）也可稱為非線性異常，指正常軌跡和異常軌跡經過某個非線性函數映射為指定值，例如1或者0.文中設置1為異常值，而0為正常值.于是，業務異常可定義如下：

[F（Ta）=1]，[F（Ti）=0]（2）

式（2）中：[F]為非線性函數;[Ti]為正常軌跡.如果滿足式（2），則[Ta]為業務異常軌跡.

識別業務異常類似于分類算法，但是和分類不同之處在于，一方面異常數據大多是無標簽數據，而且異常數據量較少.另一方面，業務異常是從數值上變換而來，通過業務分析也可以捕捉到業務異常，此方法比有監督的分類算法更靈活，更適合于快速變換的數據模式.由于業務異常分析比分類或數值異常更復雜，因此需要進行深入研究，建立有效的異常判別模型.

2異常挖掘模型

本文首先將軌跡點[（T1， T2， …， Ti-1）]輸入到長短記憶模型預測出軌跡[Ty]，[Ty]是[Ti]的預測軌跡，然后在軌跡[Ty]基礎上加入變異因子生成異常軌跡[Ta]，再將正常軌跡[Ti]和異常軌跡[Ta]輸入到邏輯回歸模型中進行異常檢測訓練，最終構建了基于長短記憶模型的異常判別檢測框架.

2.1長短記憶模型

長短記憶模型（long short term memory，LSTM）是循環神經網絡（recurrent neural network，RNN）的擴展.RNN不同于傳統神經網絡之處在于其輸入和輸出序列之間的映射過程中利用了上下文相關信息.RNN是由輸入層、一個隱含層和一個輸出層組成，展開之后的結構如圖1所示.

由圖1可知，[x]是輸入向量;h是隱含層，該層其實是多個節點，節點數與h的維度相同;[U]和[V]分別表示輸入層和隱含層的權重矩陣;[o]表示輸出層的值.從RNN的結構可看出，隱含層h的值不僅取決于當前的輸入[x]，還取決于上一次隱含層的h值.權重矩陣[W]為上一次隱含層的值作為這一次的輸入權重.可以用以下公式來表示RNN的計算方法：

[st=f（Uxt+Wst-1）]?? （3）

[ot=g（Vst）]?? （4）

式（3）、式（4）中：[g]和[f]都是激活函數.從以上公式可以看出RNN的輸出值受前面歷次輸入值的影響.但是RNN存在著梯度消失或梯度爆炸等問題[12]，為解決上述問題LSTM誕生了[13].

LSTM通過設計記憶單元保存歷史信息，記憶單元包括輸入門、遺忘門、輸出門等主要部分[14].LSTM可以選擇遺忘或更新記憶單元存儲的信息，由于LSTM考慮輸入對應輸出之間的時間滯后性，使得該網絡可以處理和預測時間序列中間隔和延遲相對較長的重要事件.LSTM關鍵的擴展是使自循環的權重視上下文而定，而不是固定的.

LSTM通過設計“門”的結構來遺忘或增加信息到細胞狀態的能力.門是一種讓信息選擇式通過的方法，其包含一個sigmoid函數和一個pointwise乘法操作.Sigmoid層輸出[0，1]之間的數值，描述每個部分的通過量.0表示不許任意量通過，1表示允許任意量通過.

由于車輛軌跡具有變換性，比如經過很長一段時間直線行駛之后轉彎，因此軌跡數據帶有一定的不平衡性.為避免軌跡預測時偏向大類數據，本文提出對LSTM模型優化，在原有的結構中加入變換門，從而提高預測精度.優化之后的結構如圖2所示.

2.2?? 異常挖掘模型

LSTM可以保存歷史信息，獲取時間序列的特征，因此，使用LSTM進行軌跡預測有助于提高預測結果的精確度.假設[（T1， T2， …， Ti-1， Ti）]為某輛車的行駛軌跡，Lstm為長短記憶模型，[Ty]是[Ti]的預測軌跡，則預測模型可表示如下.

[Ty=Lstm（T1， T2， …， Ti-1）]?? （13）

在預測軌跡的基礎上對軌跡進行變異形成異常軌跡.軌跡變異的思想主要來源于進化算法，與進化算法不同之處在于，進化算法是為尋找最優解，而文中的變異相對較為簡單，其目標是獲得不同于正常軌跡的異常軌跡.

假設s為軌跡的特征數，則每次隨機選擇m個特征進行變異，其中[m≤s/3].假設[pi]為被選中的特征之一，[1≤i≤m]，[pmin]和[pmax]分別為該特征的最小值和最大值.則[pi]的變異過程如下：

首先設定一個超參數[λ∈[0， 1]]為變異因子，表示變異的幅度，[λ]越大則變異幅度越大，反之越小.隨機生成一個數[θ∈{-1， 1}]，如果[θ=-1]，隨機生成某個數[a]，使得[0

[pia=pi+θ·a]（14）

將所有被選擇的特征進行變異之后，則生成了異常軌跡，然后再訓練分類算法，文中選用神經網絡作為異常判別算法.在訓練時，如果正常軌跡和異常軌跡共同輸入到判別算法中，結果應該為異常值1.如果是正常軌跡和正常軌跡，結果是0.如 式（15）所示.

[σ（Ta， Ti）=1]，[σ（Ty， Ti）=0]? （15）

式（15）中：[Ty]是預測軌跡;[Ta]是根據預測軌跡變異之后的軌跡;[Ti]是真實軌跡.如果滿足式（15），則[Ta]為異常軌跡.整個異常檢測訓練模型的結構圖如圖3所示.

模型訓練完成之后，在實際應用時，首先對軌跡進行預測，然后將預測的結果和真實軌跡輸入到異常判別模型中，如果結果為1，則說明真實軌跡為異常軌跡，否則為正常軌跡.

3實驗和結果分析

為了驗證模型的適應性和有效性，本文對所提出的基于長短記憶模型的異常檢測模型進行了實驗分析.該模型的開發環境是Python 3.5，操作系統是Windows 10.實驗的硬件環境為：CPU為Intel（R）i5-4590@ 3.30 GHz，內存是12 G.

3.1?? 實驗數據集

經過相關部門的同意，本文將使用GPS采集到的貨車軌跡數據集作為實驗數據.總共采集到450臺貨車的運行數據，每臺車大概有2萬～5萬條行駛記錄不等，經過數據處理之后，可用的軌跡記錄約為1 100萬條.每條記錄中包括車輛編號、經度、緯度、速度、時間、載貨量、行駛公里數等特征.

3.2?? 性能評價指標

異常檢測的最終目標是提高少數類（異常數據）的判別結果，因此，將正類作為異常樣本，而負類作為正常樣本.表1為二分類的混淆矩陣.

使用召回率（R）、假陽率（FPR）、精確率（P）和F1值作為算法性能的評價指標.前三者衡量的是算法判別正樣本的性能，而F值是精確率和召回率的調和平均.其計算方式分別如下：

[R=TPTP+FN][FPR=FPFP+TN]

[P=TPFP+TP] [F1=2PRP+R]

3.3?? 結果分析

文中隨機選擇了350輛車的數據作為訓練樣本，100輛車作為測試樣本.首先通過實驗驗證了模型的性能，然后對本異常檢測方法和聚類進行了性能比較.實驗的步驟如下：

1）數據進行歸一化處理，然后將訓練樣本輸入LSTM.本實驗中將模型可記憶的長度設置為10，也就是每10條軌跡預測一次軌跡.

2）LSTM訓練完成之后，使用LSTM進行軌跡預測，然后將預測軌跡進行變異產生異常軌跡，把預測軌跡和真實行駛軌跡合并成訓練樣本的負類，把預測軌跡和異常軌跡合并成訓練樣本的正類，并放置于異常檢測模型的訓練樣本中.

3）建立神經網絡作為異常判別模型.該網絡的輸入節點個數為12，輸出節點的個數是1，訓練該網絡直到結果達到預期精度.

4）模型訓練完成之后，將測試樣本輸入到LSTM模型，得到預測軌跡，再把真實軌跡和預測軌跡合并成一個測試樣本輸入到異常判別模型，得到測試結果，測試結果的值是0或1，1表示真實軌跡是異常軌跡，0則是正常軌跡.

圖4表示隨著變異因子的變化，異常軌跡識別的精確度和召回率的變化.

由圖4可知，隨著變異因子的變大，判別模型的召回率（R）和精確率（P）都在逐漸增大.精確率在變異因子λ=0.5時，便達到了0.820，之后緩慢增加，在λ=1.0時，精確率最大P=0.927.召回率整體略低于精確率，但是在λ=0.4之后，增長的速度高于精確率，召回率同樣也是在λ=1.0時達到最大值0.890.假陽率（FPR）隨著λ的變大而變小，主要是λ變大之后，FP值變小.FPR在λ=0.6之后，減小的速度變緩，最后FPR值可達到最小0.040.整體來看，模型在λ=0.8時便可以取得較好的性能，之后速度變緩.從實驗結果可以看出，變異因子越大，模型的精確度越大，并逐漸穩定.主要是由于變異因子過小，和正常軌跡差距較小，不利于檢測出異常軌跡;而變異因子變大，被構建的異常軌跡的范圍變大，因此，更能有效地檢測出異常軌跡.

本文分析LSTM判別算法的性能，還將該算法與改進的密度聚類算法（DBSCAN）[4]以及馬爾科夫決策的異常檢測算法（MDP）進行性能比較，圖5和圖6分別表示3種算法在數據異常（DA）和業務異常（BA）上的表現.

從實驗結果可以看出，對于數據異常（DA），3種算法性能評價值結果相近，改進的DBSCAN稍好一些，精確度達到92.2%，然后是馬爾科夫過程的異常檢測算法，而LSTM算法稍微落后一下，但是整體差異并不明顯.但是對于業務異常（BA），DBSCAN算法接近于崩潰，精確度只有68.7%，各種性能都無法達到要求;MDP算法比DBSCAN稍好一些，精確度達到78.2%;表現最優異的是LSTM模型，該模型的精確度并沒有受到影響，仍然達到了90.6%.由此表明，在3種算法中，本文提出的LSTM異常判別模型對于業務異常具有較優的性能，主要是由于該模型并不是直接使用距離來判別異常軌跡，而是通過邏輯回歸模型來判別異常.

除上述實驗之外，本文在數據中加入3%的新型異常，即在已有數據中沒有出現過，但是在未來有可能出現的異常，由此對比3種算法的可擴展性.實驗結果如圖7所示.

從圖7可以看出，對于新型異常，LSTM仍具有較好的表現能力，性能上都要優于另外2種算法.其次是密度聚類算法，精度仍然可以達到80.3%.基于馬爾科夫過程的異常檢測算法表現最弱，精度只有69.5%.

文中提出的LSTM異常判別模型能有效識別業務異常的原因在于應用隨機變異的方式，使模型可以識別出非線性異常，同時也跳出只能識別歷史數據異常的范圍，可以有效判別新型異常.聚類算法一般使用距離或其他測度去判別異常，適合查找數值異常，在查找業務異常時性能較低.馬爾科夫過程在識別業務異常時比聚類算法稍好一些，但是馬爾科夫過程也需要在歷史數據基礎上找到轉移概率，使得馬爾科夫過程識別新型異常時表現較弱.從整體上看，本文提出的LSTM異常判別模型在識別業務異常和新型異常時具有較好的優勢.另外，該模型可應用于無監督數據，比傳統的BP神經網絡異常識別方法應用范圍更廣.

4結語

交通軌跡是具有時間序列特征的數據，而長短記憶模型能有效地捕捉數據的時序特征，提高預測的精確度.本文結合優化的長短記憶模型和進化算法，通過長短記憶模型預測移動對象的軌跡，然后將軌跡變異為異常軌跡，最后訓練異常判別模型，解決異常模型訓練時無標簽問題，同時提高模型對識別業務異常的有效性.通過實驗證明，本文提出的LSTM異常判別模型在識別業務異常時具有較高的精準率和召回率，而且可以有效識別新型異常，表明該模型具有較好的擴展性和適應性.該模型不足之處在于沒有考慮軌跡數據的空間變換問題，有待于進一步深入研究.

參考文獻

[1] 劉良旭，樂嘉錦，喬少杰，等.基于軌跡點局部異常度的異常點檢測算法[J].計算機學報，2011，34（10）：1966-1975.

[2] 毛嘉莉，金澈清，章志剛，等. 軌跡大數據異常檢測：研究進展及系統框架[J].軟件學報，2017，28（1）：17-34.

[3] BIRANT D，KUT A. ST-DBSCAN：an algorithm for clustering spatial-temporal data[J].Data & Knowledge Engineering，2007，60（1）：208-221.

[4] 何明，仇功達，周波，等.基于改進密度聚類與模式信息挖掘的異常軌跡識別方法[J].通信學報，2017，38（12）：21-33.

[5] PANG X L，CHAWLA S，LIU W，et al. On mining anomalous patterns in road traffic streams[C]//International Conference on Advanced Data Mining and Applications，2011.DOI：10.1007/978-3-642-25856-5_18.

[6] ZHANG D Q，LI N，ZHOU Z H，et al. IBAT：detecting anomalous taxi trajectories from GPS traces[C]//13th International Conference on Ubiquitous Computing， Beijing，China，September 17-21，2011.DOI：10.1145/2030112.2030127.

[7] 毛江云，吳昊，孫未未.路網空間下基于馬爾科夫決策過程的異常車輛軌跡檢測算法[J].計算機學報，2018，41（8）：1928-1942.

[8] 俞慶英，李倩，陳傳明，等.基于BP神經網絡的異常軌跡檢測方法[J].計算機工程，2019，45（7）：229-236.

[9] LI X L，HAN J W，KIM S. Motion-alert： automatic anomaly detection in massive moving objects[C]//Proceedings? of the International Conference on Intelligence and Security Informatics，San Diego，CA，USA，May 23-24， 2006.DOI：10.1007/11760146_15.

[10]?? 安計勇，朱猛，翟靖軒，等.軌跡多因素異常集成檢測[J].計算機工程與設計，2015，36（10）：2700-2705.

[11]?? 汪霜霜，李春貴. 一種lp正則化改進的車輛軌跡學習算法[J].廣西科技大學學報，2019，30（2）：53-60.

[12]?? HOCHREITER S.The vanishing gradient problem during learning recurrent neural nets and problem solutions[J].International Journal of Uncertainty， Fuzziness and Knowledge-based Systems，1998，6（2）：107-116.

[13]?? SCHUSTER M，PALIWAL K K.Bidrectional recurrent neural networks[C].IEEE Transaction on Signal Processing，1997，45（11）：2673-2681.DOI：10.1109/78.650093.

[14]?? 張洪剛，李煥.基于雙向長短時記憶模型的中文分詞方法[J].華南理工大學學報（自然科學版），2017，45（3）：61-67.

An anomaly detection algorithm for traffic trajectory data based on long short term memory model

QIN Shengjun， LI Ting

（School of Economics and Management， Guangxi University of Technology， Liuzhou 545006， China）

Abstact： An abnormal trajectory detection method based on Long Short Term Memory model is ?proposed to solve the problem that the existing anomaly detection algorithm can't capture the timing characteristics of trajectory data， and can't effectively identify business anomalies and novel anomalies. In this paper， Long Short Term Memory model is used to predict trajectory which can improve the prediction accuracy， then the predicted trajectory is transformed into an abnormal trajectory based on the theory of evolution. Finally， an anomaly discrimination model based on Long Short Term Memory model has been constructed. The proposed model can effectively identify business anomalies and new types of anomalies， and improves the accuracy and scalability of anomaly detection. At the same time， the model is suitable for unlabeled data and solves the problem that traditional neural networks must be applied to supervised learning. In the end， comparative experiments with the improved densityclustering algorithm and Markov process verify the superiority of the model in detecting abnormal traffic trajectory.

Key words： long short term memory; abnormal trajectory; traffic big data; deep learning

（責任編輯：黎 ?婭）

收稿日期：2020-10-21

基金項目：廣西高校中青年教師科研基礎能力提升項目（2019KY0373）資助.

作者簡介：秦勝君，博士，副教授，研究方向：交通大數據、數據挖掘、復雜網絡，E-mail：shengjun_2012@foxmail.com.