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

(1.中國科學院大學電子電氣與通信工程學院,北京 100049; 2.中國科學院電子學研究所,北京 100190; 3.中國科學院空間信息處理與應用系統(tǒng)技術(shù)重點實驗室,北京 100190)

0 引 言

隨著定位技術(shù)、空間通信技術(shù)和計算能力的快速發(fā)展，人們積累了海量的時空軌跡數(shù)據(jù)，如船舶軌跡數(shù)據(jù)、人類活動軌跡、動物遷徙軌跡和氣候氣流數(shù)據(jù)等。大規(guī)模的軌跡數(shù)據(jù)蘊含了移動對象豐富的時空和行為信息，分析挖掘軌跡數(shù)據(jù)中有價值的信息在學術(shù)科學領(lǐng)域、商業(yè)應用領(lǐng)域和政府管理領(lǐng)域都具有重大現(xiàn)實意義[1]。其中，船舶軌跡數(shù)據(jù)是船舶行為規(guī)律挖掘、海事監(jiān)管和船舶交通流預測的重要數(shù)據(jù)源。

在現(xiàn)實生活中，軌跡數(shù)據(jù)從來都不是完全準確的。由于定位技術(shù)的局限和外界干擾因素的影響(如設(shè)備故障、人為操作誤差)，軌跡數(shù)據(jù)中存在大量的異常點[2]。軌跡中的異常點為嚴重偏離軌跡的不合理的采樣點。這些異常點的存在嚴重降低了軌跡數(shù)據(jù)的質(zhì)量，同時引起后續(xù)軌跡知識發(fā)現(xiàn)結(jié)果的不準確，例如軌跡壓縮[3]、軌跡聚類[4]、路徑規(guī)劃[5]、異常模式檢測[6]和航跡關(guān)聯(lián)分析[7-8]。因此，對軌跡異常點的檢測是十分必要的。

目前應用最廣泛的軌跡異常點檢測算法為恒定閾值法，尤其是速度閾值法[9]。當與前一個點計算得到的當前定位點的即時速度超出設(shè)定閾值時，采樣點被標記為異常點并被剔除。這種方法主要存在以下問題：1)對于大部分的軌跡數(shù)據(jù)，用戶難以找到一個準確的閾值；2)移動目標的運動狀態(tài)在不同情況下不可能是完全相同的，采用恒定的閾值有明顯的不足；3)只考慮前一個點的信息來檢測異常點，有可能導致正常點被誤判為異常值。

針對上述方法存在的問題，本文提出一種基于自適應閾值的軌跡異常點檢測算法(Trajectory Outlier Detection Algorithm based on adaptive Threshold, TODAT)。算法考慮相鄰一段時間內(nèi)船舶的運動狀態(tài)和數(shù)據(jù)中噪聲的影響，分別采用局部閾值窗和均值濾波窗來計算閾值和速度。通過分析實際的實驗數(shù)據(jù)，本文還引入了經(jīng)濟航速閾值和連續(xù)異常點放回機制。TODAT能夠根據(jù)船舶整條軌跡和軌跡段上的運動信息自動得到自適應的合理的閾值。實驗結(jié)果表明TODAT算法可以實時檢測船舶軌跡數(shù)據(jù)中的異常點。

1 相關(guān)工作

Hawkins在1980年對異常點提出的正式定義為：異常點是指在數(shù)據(jù)集中顯著偏離其它絕大部分數(shù)據(jù)的那些數(shù)據(jù)對象，以至于引起人們懷疑它們是由完全不同的機制產(chǎn)生的[10]。異常點檢測算法在國內(nèi)外都得到了廣泛的研究，主要分為以下4類[11]。

1)基于統(tǒng)計的方法。假設(shè)正常的數(shù)據(jù)是由一個統(tǒng)計模型產(chǎn)生，而不遵守該模型的數(shù)據(jù)是異常點。該方法的有效性高度依賴于數(shù)據(jù)的分布假設(shè)是否成立。

2)基于距離的方法。Knorr等人[12]提出了經(jīng)典的DB(p, D)算法，如果數(shù)據(jù)集中至少有p部分數(shù)據(jù)對象與對象o的距離大于D，則o是一個基于距離的關(guān)于參數(shù)p和D的異常點。該方法需要恰當?shù)木嚯x度量，不能檢測出具有不同密度分布數(shù)據(jù)中的局部異常點。

3)基于密度的方法。該方法假設(shè)異常點周圍的密度顯著不同于其鄰域周圍的密度。Breunig等人[13]已經(jīng)提出了局部異常因子(LOF)算法，根據(jù)鄰域中全部點的局部可達密度計算出每一個點的LOF值，高LOF值的點為異常點。該算法可以檢測出全局異常點和局部異常點。

4)基于分類的方法。訓練一個可以區(qū)分正常數(shù)據(jù)和異常點的分類模型，用預先訓練好的模型來判斷新的觀測點是否異常。該方法依賴于已標注的訓練數(shù)據(jù)集。

軌跡數(shù)據(jù)是基于時間和空間的位置序列，傳統(tǒng)的檢測方法不能直接用于檢測軌跡數(shù)據(jù)中的異常點。針對軌跡數(shù)據(jù)，Chen等人[5]、Alvares等人[14]和Zheng等人[15]采用恒定閾值法來檢測異常值，剔除即時速度超出設(shè)置閾值的軌跡點后再進行各自的軌跡數(shù)據(jù)挖掘任務(wù)。Zhang等人[16]提出了TODMF算法，算法在基于距離的檢測方法上改進，組合速度、加速度和轉(zhuǎn)角等多個因素來檢測軌跡異常點。Chen等人[17]提出了一種基于模型的GPS軌跡清理算法來檢測低成本GPS軌跡上的異常值，采用3次平滑樣條和時間序列方法對軌跡的趨勢進行自適應建模。上述方法主要針對GPS軌跡上的應用，但是不適用于由多種定位手段得到的船舶軌跡數(shù)據(jù)。不同于GPS高達米級的定位精度，船舶多種來源的軌跡數(shù)據(jù)的精度均較低，且定位精度和軌跡采樣率差異較大。本文將針對多種探測手段獲取的船舶軌跡數(shù)據(jù)，研究基于自適應閾值的異常點檢測方法。

2 算 法

本文提出的TODAT算法針對船舶航跡數(shù)據(jù)。船舶的航跡由一系列時空數(shù)據(jù)點(即經(jīng)度、緯度和時間)組成，通常由多種定位手段獲得。由于不同數(shù)據(jù)源定位誤差的差異、環(huán)境干擾和人為操作失誤，船舶軌跡數(shù)據(jù)中存在大量不符合目標運動規(guī)律的異常點。船舶的原始航跡如圖1所示，數(shù)據(jù)中有許多嚴重偏離航跡的異常點。軌跡異常點檢測是數(shù)據(jù)處理應用前最重要的一步。

TODAT算法的核心思想是：在短時間內(nèi)船舶的運動狀態(tài)相似，即速度、加速度不會發(fā)生突變。算法依次計算當前時刻的閾值和當前點的即時速度，速度超出閾值則判定為異常點。根據(jù)具體的數(shù)據(jù)情況，算法設(shè)定了一系列的參數(shù)規(guī)則：1)由局部閾值窗或經(jīng)濟航速閾值規(guī)則得到對應的自適應閾值；2)采取均值濾波窗來降低噪聲對檢測結(jié)果的影響；3)采用連續(xù)異常點放回機制降低誤檢率。

(a) 軌跡1 (b) 軌跡2圖1 船舶的原始軌跡

2.1 局部閾值窗

考慮到待檢測點的運動狀態(tài)與相鄰一段航跡的運動狀態(tài)有很大關(guān)系，算法引入局部閾值滑動窗口。局部閾值窗內(nèi)放置當前點之前的一連串已經(jīng)判定的正確點。通過對軌跡數(shù)據(jù)的觀察分析，本文設(shè)定了窗口時長和點數(shù)的限制條件(見3.1節(jié)表1)。當限制條件滿足時，本文選擇由窗口內(nèi)點計算得到的局部閾值，否則，選用由整段軌跡信息計算得到的全局閾值。對于目標以平穩(wěn)速度行駛一段航跡后速度突然增大很多的異常點，采用局部閾值窗可以有效檢測出。

(1)

(2)

2.2 均值濾波窗

軌跡數(shù)據(jù)中每個點都是存在著噪聲的。為了減少噪聲對異常點檢測的影響，本文采用均值濾波滑動窗口。均值濾波窗內(nèi)同樣放置了已檢測的一系列的好點，但是根據(jù)數(shù)據(jù)情況本文選取了不同的點數(shù)和時長設(shè)置(見3.1節(jié)表1)。

均值濾波是典型的線性濾波算法，通常用于去除圖像和信號中的噪聲[19]。本文計算均值濾波窗內(nèi)全部點的經(jīng)度、緯度和時間的平均值作為一個濾波新點Pf。濾波窗的限制條件符合時選擇濾波新點，否則選擇前一個點為參照點Pr來計算當前點的即時速度。當前點Pi的速度計算公式為：

vi=dist(Pi,Pr)/(ti-tr)

(3)

其中，dist(Pi,Pr)表示點Pi和Pr之間的距離，ti、tr分別表示2點的時間。濾波窗可以有效提高參照點的精度，保留速度微小波動的點，從而降低誤檢率。

當前點Pi被判定為異常點當速度vi超出了速度閾值vth即vi>vth成立。算法中，局部閾值窗決定了閾值的選取，均值濾波窗則用來選擇參照點和即時速度的計算。檢測算法示意圖如圖2所示，目標點Pi為檢測出的異常點。

圖2 算法示意圖

2.3 算法流程

船舶行駛中，經(jīng)常會出現(xiàn)長時間沒有采集到軌跡點的情況，前后2點間隔時長非常大。本文假設(shè)船舶此時是以經(jīng)濟航速[20]行進的，即每海里燃油消耗量可以達到最少值。算法在2點間隔時長超出設(shè)定時間時，采用經(jīng)濟航速閾值。與2.1節(jié)中閾值公式設(shè)計相同，經(jīng)濟航速閾值計算公式如下：

(4)

其中，Vemin、Vemax分別為速度閾值下界和上界，Mve為經(jīng)濟航速倍數(shù)。經(jīng)濟航速閾值可以使算法檢測出2點間隔時間非常大情況下的異常點，降低漏檢率。

通過觀察數(shù)據(jù)發(fā)現(xiàn)，數(shù)據(jù)中不會出現(xiàn)連續(xù)多個異常點的情況。本文采取連續(xù)異常點放回規(guī)則，如果連續(xù)異常點個數(shù)超過設(shè)定值且首尾時間在設(shè)定范圍內(nèi)，則重新判定這些點為正常點。該規(guī)則可以避免將速度微小波動的點錯判為異常點，減少算法中各參數(shù)的調(diào)整，提高閾值的自適應性。

本文對軌跡點的加速度屬性作了同樣的處理，點Pi的加速度計算公式為：

ai=(vi-vi-1)/(ti-ti-1)

(5)

與公式(1)、公式(2)類似，由整條軌跡和局部窗口軌跡的點分別得到全局加速度閾值agth和局部加速度閾值alth，當采樣點的速度和加速度都超過對應閾值時，采樣點被檢測為異常點。

算法的流程如圖3所示。

圖3 TODAT算法流程圖

3 實驗結(jié)果分析

3.1 實驗設(shè)置

本文采用一個真實的船舶軌跡數(shù)據(jù)集來驗證算法的有效性。該數(shù)據(jù)集記錄了100艘船舶一個月的實時航跡，包含有超過2000條軌跡和百萬個軌跡點。本文實驗的運行環(huán)境為Intel Core i7-6700 3.4 GHz、內(nèi)存為8 GB的PC，算法由Python實現(xiàn)。

表1 算法中參數(shù)值的設(shè)置

參數(shù)名稱值速度閾值下界15節(jié)速度閾值上界40節(jié)全局速度倍數(shù)5局部速度倍數(shù)7加速度閾值下界0.5 m/s2加速度閾值上界15 m/s2全局加速度倍數(shù)5局部加速度倍數(shù)7經(jīng)濟航速間隔時長90 min經(jīng)濟航速倍數(shù)3參數(shù)名稱值閾值窗的最小點數(shù)7閾值窗的最大點數(shù)31閾值窗的最小時長20 s閾值窗的最大時長5 min均值濾波窗的點數(shù)11均值濾波窗的時長11 min連續(xù)異常點個數(shù)7連續(xù)異常點時長80 min經(jīng)濟航速閾值下界10節(jié)經(jīng)濟航速閾值上界30節(jié)

TODAT算法中各個參數(shù)和其預設(shè)的值如表1所示。其中，速度、加速度和經(jīng)濟航速閾值上下界的設(shè)定是為了保證速度全局閾值、加速度全局閾值和經(jīng)濟航速閾值的有效性，避免由軌跡點直接計算得到的閾值過大或過小引發(fā)漏檢或錯檢。參照3準則[18]，閾值應設(shè)為均值加上一定倍數(shù)的標準差，本文通過對船舶運動數(shù)據(jù)的統(tǒng)計與分析，確定了全局速度、局部速度、全局加速度、局部加速度和經(jīng)濟航速的標準差倍數(shù)。為了更加貼近實際情況，本文進一步考慮了目標在一段時間內(nèi)的運動信息，設(shè)置了局部閾值窗的最小點數(shù)、最大點數(shù)、最小時長和最大時長的限制條件，在此條件下計算對應的局部閾值。均值濾波窗點數(shù)和時長的設(shè)置是為了判定濾波窗是否起作用，當點數(shù)時長條件符合時，算法采用濾波新點來計算即時速度。當2個點的時間間隔過長，采用局部閾值是不合理的，因此本文設(shè)置了經(jīng)濟航速間隔時長，在2點間隔超過經(jīng)濟航速間隔時長時，算法將采用經(jīng)濟航速閾值。最后，本文設(shè)置了連續(xù)異常點個數(shù)和時長，以此判斷是否采用連續(xù)點放回機制。

所有這些參數(shù)的設(shè)置取值都是為了盡可能采樣到較多的影響當前點檢測的有價值信息，獲得自適應的閾值，從而使得檢測結(jié)果更準確。根據(jù)船舶固有的最高速度為15～32節(jié)(7.72～16.46 m/s)[21]和數(shù)據(jù)集上的速度分析，本文在數(shù)據(jù)集上測試調(diào)整了各個參數(shù)的取值，最終選取了檢測效果最符合船舶運動狀態(tài)的一組參數(shù)值。

3.2 實驗結(jié)果

3.2.1 可視化效果分析

本文算法在船舶數(shù)據(jù)集上檢測出3種類型的異常點，包括孤立異常點、連續(xù)異常點和明顯判識異常點，其可視化結(jié)果如圖4所示，異常點用三角形標記出。圖4(a)為檢測出的孤立異常點，算法通過局部閾值可以有效檢測出平穩(wěn)軌跡中的速度波動的異常點。圖4(b)中，算法識別出了連續(xù)的5個異常點，這5個點明顯偏離了船的航跡，速度與其余點的速度值相差較大。由圖4(c)可見，左側(cè)一段航跡與右側(cè)船航跡顯著不同，2段軌跡其實是2艘船的，但在數(shù)據(jù)收集過程中被判識成一個運動對象，異常由判識錯誤引起。

(a) 孤立異常點

(b) 連續(xù)異常點

(c) 明顯判識異常點圖4 檢測出的異常點類型

圖1中2條軌跡原圖在檢測并去除異常點后的軌跡圖如圖5所示。為了直觀地體現(xiàn)TODAT算法的有效性，圖6給出了更多的檢測前和剔除異常點后的軌跡對比。從這些圖中可以明顯觀察出，檢測后的軌跡更為平滑，符合船舶的運動情況，算法有效檢測出了原始軌跡中的偏離航跡的不合理的異常點。船舶的軌跡數(shù)據(jù)只有在檢測完異常點之后，才可以用來做后續(xù)的處理和知識挖掘工作。

(a) 軌跡1 (b) 軌跡2圖5 圖1中剔除異常點后的軌跡

(a) 檢測前 (b) 檢測后圖6 原始軌跡與檢測后軌跡對比圖

3.2.2 檢測結(jié)果對比與分析

為驗證本文算法的有效性與合理性，本文抽取100條船舶軌跡，24295個航跡點作為實驗數(shù)據(jù)集，并將本文提出的算法與恒定速度閾值法進行對比。通過對數(shù)據(jù)集中船舶運動狀態(tài)的統(tǒng)計和分析，本文將恒定速度閾值設(shè)為20 m/s，并根據(jù)每個軌跡點與前一個已判定的正常點來計算即時速度，速度超過恒定速度閾值則被標記為異常點。

圖7給出了TODAT算法與恒定速度閾值法在3段軌跡上檢測結(jié)果的對比圖。圖7(a)為本文算法檢測結(jié)果，正常點用圓點表示，異常點用三角形表示；圖7(b)為恒定速度閾值法的檢測結(jié)果，其中菱形標記為檢測出的異常點。從第1幅圖中可以看出，恒定閾值法未能將明顯的孤立異常點檢測出來，該點速度為15.58 m/s，遠遠超出了其鄰近點3～5 m/s的速度值，而TODAT算法能夠很好地檢測出孤立的異常點。這是因為TODAT算法能夠根據(jù)移動目標的運動狀態(tài)得到自適應的閾值。從第2、第3幅圖中可以看出，恒定速度閾值法不僅沒檢測出正確的異常點，反而將較多的正常點錯判為異常點，而TODAT能夠?qū)Ξ惓｜c進行正確的判別，且沒有對正常點的錯判。其原因是位置明顯波動的異常點速度沒有超出根據(jù)船舶最大運動能力設(shè)定的恒定速度閾值而被錯判，而在此之后的軌跡點根據(jù)這些錯判點計算的即時速度超出了恒定速度閾值，進而引發(fā)漏檢和錯檢。而TODAT算法則能根據(jù)數(shù)據(jù)得到自適應的合理的閾值，從而得到更準確的檢測結(jié)果。

(a) TODAT算法 (b) 恒定速度閾值法圖7 軌跡異常點檢測結(jié)果對比圖

實驗結(jié)果表明，TODAT算法檢測出851個異常點(所有異常點均檢測出來)；而恒定速度閾值法檢測出的異常點共833個，其中還包含了一些錯判的正常點。原始軌跡和TODAT算法、恒定速度閾值算法檢測后軌跡各個點的速度分布直方圖分別如圖8所示，圖中的橫縱坐標軸均為對數(shù)刻度，每個點速度按前一個點來計算。

(a) 原始軌跡

(b) TODAT算法

(c) 恒定速度閾值算法圖8 速度直方圖對比

由圖8和統(tǒng)計結(jié)果可知，船舶的速度主要集中在1.5～10 m/s范圍內(nèi)，TODAT算法有效檢測出了速度超出絕大部分20 m/s的異常點，共有693個點；與此同時，算法也檢測出來158個與相鄰點運動狀態(tài)波動較大的異常點。而恒定速度閾值算法只是簡單地將速度為20 m/s以上的點判為異常點，這樣極易引發(fā)漏檢和錯檢?？梢暬Y(jié)果和速度直方圖對比圖均表明，本文TODAT算法可根據(jù)不同的數(shù)據(jù)實時得到自適應的閾值，相比于恒定速度閾值法得到更準確的檢測結(jié)果，非常適用于艦船軌跡數(shù)據(jù)中異常點的實時檢測。

4 結(jié)束語

本文提出一種基于自適應閾值的軌跡異常點檢測算法TODAT。算法能夠根據(jù)船舶整條軌跡和軌跡段上的數(shù)據(jù)，采用局部閾值窗、均值濾波窗和設(shè)定參數(shù)規(guī)則來得到自適應的閾值，實現(xiàn)對船舶軌跡數(shù)據(jù)實時的異常點檢測。實驗結(jié)果表明本文算法能夠有效檢測出明顯偏離航跡、速度波動較大的不合理的軌跡點，大幅度提高軌跡數(shù)據(jù)的質(zhì)量，為后續(xù)數(shù)據(jù)處理和知識發(fā)現(xiàn)提供保障。在下一步工作中，將在該算法的基礎(chǔ)上，提取軌跡數(shù)據(jù)的特征，引入機器學習分類方法，實現(xiàn)船舶數(shù)據(jù)點是否異常的自動分類。