基于網(wǎng)格化的船舶航跡異常檢測算法

劉亞帥，曹 偉，管志強(qiáng)

（中國船舶重工集團(tuán)公司第七二四研究所，南京211153）

0 引 言

由于海上異常軍事目標(biāo)的航跡多表現(xiàn)為位置異常與航向異常，所以為了能夠檢測出異常航跡，識別出異常船舶，需要首先構(gòu)建出正常船舶航路的位置與航向模型，然后在此模型下與待檢測航跡進(jìn)行對比檢測。

當(dāng)前，船舶自動識別系統(tǒng)（Automatic Identification System，AIS）［1］的廣泛應(yīng)用為基于 AIS數(shù)據(jù)構(gòu)建正常船舶航路模型及檢測異常航跡提供了海量數(shù)據(jù)儲備?？v觀國內(nèi)外基于AIS數(shù)據(jù)對航路建模的研究，多基于單一目標(biāo)的小樣本進(jìn)行。例如，Pallotta等［2］采用改進(jìn)后的 DBSCAN （density?based spatial clustering of appli?cations with noise）聚類算法進(jìn)行航道挖掘，Guillarme等［3］采用軌跡分割聚類的方法實(shí)現(xiàn)軌跡數(shù)據(jù)的聚類，Osekowska 等［4?6］將勢場的概念應(yīng)用于船舶航道的提取，寧建強(qiáng)等人［7］采用一種細(xì)粒度網(wǎng)格化的方法對海上船舶航道進(jìn)行提取。這些方法在海量數(shù)據(jù)背景下都會導(dǎo)致樣本描述整體出現(xiàn)偏差的可能性增大，甚至發(fā)生錯誤和遺漏［8］。

為了基于海量AIS數(shù)據(jù)實(shí)現(xiàn)正常船舶航路的建模，從而實(shí)現(xiàn)異常航跡的檢測，本文提出了一種基于網(wǎng)格化的船舶航跡異常檢測算法。該算法首先采用了一種網(wǎng)格化壓縮方法對原始航跡進(jìn)行壓縮處理，去除冗余數(shù)據(jù)；然后基于網(wǎng)格化重構(gòu)了航跡方向?qū)傩?，為壓縮后的航跡增加了方向?qū)傩裕恢蟛捎梅诸愄幚淼乃悸泛妥冮撝翟O(shè)計(jì)方法實(shí)現(xiàn)了航路建模；最后設(shè)計(jì)了一種基于滑窗檢測的方法，實(shí)現(xiàn)了異常航跡的檢測。實(shí)驗(yàn)結(jié)果表明，該算法可以有效實(shí)現(xiàn)部分類型的異常航跡檢測。

1 異常檢測算法的總體架構(gòu)

本文基于網(wǎng)格化的船舶航跡異常檢測算法的總體架構(gòu)，如圖1所示。

圖1 船舶航跡異常檢測算法總體流程

由于從數(shù)據(jù)庫中抽取的原始AIS數(shù)據(jù)存在大量噪聲信息，所以本文首先通過從MMSI（Maritime Mobile Service Identity）號及經(jīng)緯度角度對其進(jìn)行篩選去噪。

定義1空窗期

由于主觀或客觀環(huán)境的干擾導(dǎo)致目標(biāo)離開監(jiān)控窗口，監(jiān)測儀器在一段相當(dāng)長的時(shí)間內(nèi)丟失對這個(gè)目標(biāo)的跟蹤，而且在再次跟蹤到該目標(biāo)時(shí)無法忽略中間缺失過程產(chǎn)生的誤差。這段缺失過程就是該目標(biāo)的一個(gè)空窗期。

由于同一MMSI號的航跡存在多個(gè)空窗期，為了滿足后續(xù)網(wǎng)格化壓縮處理中對軌跡數(shù)據(jù)連續(xù)性的要求，需要將同一MMSI號對應(yīng)的AIS數(shù)據(jù)根據(jù)空窗期分割成若干連續(xù)的航跡，即航跡切割。

2 網(wǎng)格化航路建模

為了基于海量AIS數(shù)據(jù)實(shí)現(xiàn)正常航路的建模，本節(jié)通過以下3步進(jìn)行處理：

（1）為了從海量AIS數(shù)據(jù)中提取出有用的航跡信息，去除冗余信息，本節(jié)提出一種網(wǎng)格化壓縮的方法直接剔除了航跡數(shù)據(jù)中的冗余信息，提取出航跡數(shù)據(jù)中的有用信息；

（2）由于壓縮后的航跡缺失了航跡的航向?qū)傩裕罄m(xù)異常檢測過程需要航向信息，所以本節(jié)基于網(wǎng)格化為航跡重構(gòu)了航向?qū)傩裕?/p>

（3）在上述兩步的基礎(chǔ)上，本節(jié)在重構(gòu)的8個(gè)航向上分別建立了8個(gè)航向上的航路模型。

2.1 網(wǎng)格化壓縮

定義2網(wǎng)格化壓縮方法

如公式（1）所示，已知一條連續(xù)的航跡是S，其中（loni，lati）是航跡S的第i個(gè)航跡點(diǎn)的經(jīng)緯度坐標(biāo)；然后，通過坐標(biāo)變換，使得（lon′i，lat′i）等于航跡點(diǎn)（loni，lati）所在網(wǎng)格中心點(diǎn)的坐標(biāo)，從而形成航跡S′；最后，對航跡S′按照點(diǎn)跡的先后順序進(jìn)行去重壓縮，最終得到壓縮后的航跡S″，而且n＞m。

網(wǎng)格化壓縮具體操作流程如下所述：

（1）如圖2所示，對研究區(qū)域W根據(jù)經(jīng)緯度值劃分成大小為step的網(wǎng)格（圖中A′是A的放大）；

（2）將落在網(wǎng)格中的所有航跡點(diǎn)的經(jīng)緯度坐標(biāo)都壓縮成為網(wǎng)格中心點(diǎn)的經(jīng)緯度坐標(biāo)（對于落在網(wǎng)格邊界線上的點(diǎn)統(tǒng)一移到左側(cè)或上側(cè)的格子中），即將所有落到A′格子中的點(diǎn)都壓縮到中心點(diǎn)處；

（3）將每一條連續(xù)的航跡按照時(shí)間屬性（UDT_TM）進(jìn)行排序，并對經(jīng)緯度采用一階差分的算法進(jìn)行計(jì)算；

（4）將經(jīng)緯度差分為零的點(diǎn)去掉，至此實(shí)現(xiàn)了網(wǎng)格化壓縮。

圖2 網(wǎng)格化壓縮過程圖

2.2 航向?qū)傩灾貥?gòu)

定義3航向?qū)傩灾貥?gòu)規(guī)則

設(shè)初始軌跡點(diǎn)為P0（Lon0，Lat0），下一軌跡點(diǎn)位置為P1（Lon1，Lat1），根據(jù)矢量的定義法則，P0點(diǎn)的矢量方向（Lon1?Lon0，Lat1?Lat0）。 圖 3 是一個(gè)九宮格編碼格，9號格為初始軌跡點(diǎn)P0，下一軌跡點(diǎn)P1將會落到剩余的軌跡格中的任意一個(gè)格中，則P0的方向編碼為P1點(diǎn)落到的格子對應(yīng)的編碼號。

圖3 九宮格編碼圖

在定義3的基礎(chǔ)上，首先假設(shè)一條航跡（如圖4所示），則軌跡點(diǎn)a的軌跡方向編碼為7，軌跡點(diǎn)b的軌跡方向編碼為2，軌跡點(diǎn)c的軌跡方向編碼為1。這樣這條軌跡方向的整體編碼形式就是7?2?1。依此原理對所有壓縮后的點(diǎn)跡進(jìn)行航向?qū)傩灾貥?gòu)。

圖4 假設(shè)軌跡圖

2.3 正常航路建模

為了便于后續(xù)從不同航向角度對航跡進(jìn)行異常檢測，本節(jié)首先按照重構(gòu)的航向?qū)傩缘?個(gè)編碼值將航跡數(shù)據(jù)分成8個(gè)數(shù)據(jù)集，之后在每個(gè)數(shù)據(jù)集上分別建立該航向上對應(yīng)的航路模型，以此實(shí)現(xiàn)不同航向上的航路建模。具體算法流程如圖5所示。

圖5 正常航路建模流程圖

定義4核心密度網(wǎng)格

在網(wǎng)格密度值計(jì)算中，一般直接對每個(gè)網(wǎng)格中點(diǎn)跡數(shù)量進(jìn)行計(jì)數(shù)從而作為其相應(yīng)的密度。同時(shí)規(guī)定，若某個(gè)網(wǎng)格中的點(diǎn)跡數(shù)（即網(wǎng)格密度）大于等于設(shè)置的密度閾值，則該網(wǎng)格被稱為核心密度網(wǎng)格，否則稱為噪聲網(wǎng)格。

定義5密度閾值設(shè)置方法

設(shè)航向i（i＝1，2，…，8）上的網(wǎng)格密度值集合為DIi（Di1，…，Dij，…，Din），其中Dij是航向i上的第j個(gè)網(wǎng)格中的密度值（Dij＞0），則如公式（2）所示，其中μi為航向i上的網(wǎng)格密度值的均值，σi為航向i上的網(wǎng)格密度值的標(biāo)準(zhǔn)差，TDi為航向i上的密度閾值，m為一個(gè)系數(shù)（m＞0）。

由于本文是通過提取核心密度網(wǎng)格作為正常航路模型，所以需要設(shè)置密度閾值來過濾噪聲網(wǎng)格。因?yàn)橹貥?gòu)的8個(gè)航向上的數(shù)據(jù)分布存在差異，為了適應(yīng)不同航向上數(shù)據(jù)分布的特點(diǎn)，本文采用定義5的方法分別設(shè)置不同航向上的密度閾值TDi，之后通過閾值判決實(shí)現(xiàn)不同航向上的航路建模。

詩意美是《雨巷》最為突出的特點(diǎn)之一?！八囆g(shù)作品的形式美，歸根結(jié)底，也正是這樣一種生命感應(yīng)的產(chǎn)物”。詩歌作為一種充滿藝術(shù)性的作品形式，與其他體裁相比，簡潔而又含蓄，卻能將作者的心緒、感受完美地詮釋；精練的語言，短小的篇幅，卻能引人遐想。

3 航跡異常檢測

本文采用的異常檢測流程如圖6所示。

圖6 異常檢測流程圖

為了便于航跡與航路模型對比，首先需要對航跡也進(jìn)行網(wǎng)格化壓縮及航向重構(gòu)，其壓縮方法和航向重構(gòu)方法與航路建模中的一致。之后設(shè)置滑窗大小為N2，對滑窗內(nèi)的航跡采用滑窗異常檢測方法進(jìn)行檢測（見定義 6）。

定義6滑窗異常檢測方法

首先采用滑窗N2對航跡按照時(shí)間順序截取矩陣A，其中矩陣A中航跡所在位置的元素值為1，其余位置的元素值為0（如圖7所示）。同時(shí)采用滑窗分別對8個(gè)模型截取矩陣B1至B8，其中Bm矩陣對應(yīng)模型中核心密度網(wǎng)格的元素值為α（α＞0），其余元素為β（β＜0）。

圖7 窗口截取矩陣過程

如公式（3）所示，其中P為整個(gè)滑窗中的航跡異常度，M是模型的個(gè)數(shù)，本文中取M＝8，N是滑窗的大小，ωm中是每個(gè)模型輸出異常度的權(quán)值，fm（Ym）是一個(gè)sigmoid函數(shù)，其輸出值是每個(gè)模型對應(yīng)的異常度，Ym是矩陣A與矩陣Bm點(diǎn)乘之后并求和的結(jié)果。

通過比較滑窗內(nèi)的航跡異常度P與異常度閾值ThP來檢驗(yàn)滑窗內(nèi)的航跡是否異常。當(dāng)P低于ThP時(shí)表示航跡異常，則結(jié)束檢測并輸出異常；當(dāng)P高于ThP時(shí)表示航跡正常，則進(jìn)一步判斷該條航跡是否已檢測完成，如果檢測完成，將結(jié)束檢測并輸出正常；如果未檢測完成，將向下一時(shí)間節(jié)點(diǎn)處移動滑窗繼續(xù)檢測，依次循環(huán)直到檢測完成。

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

4.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)

本實(shí)驗(yàn)使用的是基站采集的廈門港口海域近一個(gè)月的AIS數(shù)據(jù)，其總量達(dá)到300 496 123條數(shù)據(jù)。

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

4.2.1 網(wǎng)格化壓縮效果分析

本文采用 0.02°×0.02°網(wǎng)格進(jìn)行劃分，這樣既可以充分壓縮又不會丟失轉(zhuǎn)向信息。由于數(shù)據(jù)量太大，受硬件平臺的限制，無法對原始數(shù)據(jù)進(jìn)行一次性壓縮，所以將1個(gè)月的數(shù)據(jù)分割成3個(gè)數(shù)據(jù)集分別進(jìn)行處理。表1所示是3次數(shù)據(jù)壓縮的效果，其壓縮的倍數(shù)都在250～300倍之間。

表1 數(shù)據(jù)壓縮效果表

4.2.2 航跡異常檢測效果

本實(shí)驗(yàn)中采用表1中的前20天數(shù)據(jù)構(gòu)建航路模型，采用最后10天數(shù)據(jù)進(jìn)行航路檢測。參數(shù)設(shè)置：航路模型構(gòu)建中，密度閾值設(shè)置中（即公式（2）中）的m＝0.3；異常檢測中α＝1，β＝-1，ωm＝1 且ThP＝0.5。 實(shí)驗(yàn)中通過對這10天中較長的3 018條待檢測航跡進(jìn)行異常檢測，檢測出38條異常航跡，檢測過程耗時(shí)63.86 s。其中較明顯異常航跡有26條，圖8所示是其中部分異常航跡。

圖8 部分異常航跡展示

圖8（a）～（d）中船舶航跡發(fā)生異常轉(zhuǎn)向問題，尤其是圖8（a），所以該類異常航跡主要表現(xiàn)為轉(zhuǎn)向異常；圖8（e）中正常船舶不可能在短時(shí)間內(nèi)發(fā)生如此大的位移，所以該類異常航跡表現(xiàn)為偽裝異常；圖8（f）～（h）由于航跡進(jìn)入異常區(qū)域，所以該類異常表現(xiàn)為區(qū)域異常。

除了以上圖8中檢測出來的異常，實(shí)驗(yàn)中還將部分正常航跡誤判為異常航跡（如圖9所示）。這主要是由于基站雷達(dá)存在威力范圍，在雷達(dá)威力邊緣區(qū)域收集的AIS數(shù)據(jù)較少，使得其航跡密度值較低，很容易將其誤判成噪聲區(qū)域，從而使得部分航行到該區(qū)域的正常航跡誤判成異常航跡。

圖9 部分誤判航跡展示

5 總結(jié)及展望

為了基于海量AIS數(shù)據(jù)實(shí)現(xiàn)正常船舶航路的建模，從而實(shí)現(xiàn)異常航跡的檢測，本文提出一種基于網(wǎng)格化的船舶航跡異常檢測算法。該算法針對原始AIS數(shù)據(jù)中存在冗余信息并嚴(yán)重影響后續(xù)處理效率和航道模型建立的問題，提出了一種網(wǎng)格化壓縮方法，有效去除了航跡數(shù)據(jù)中的冗余數(shù)據(jù)，提高了海量數(shù)據(jù)處理的計(jì)算效率。由于壓縮后的航跡數(shù)據(jù)缺少航向信息，不利于后續(xù)異常檢測中航向的檢測，本文在網(wǎng)格化的基礎(chǔ)上重構(gòu)了船舶航向?qū)傩?，為壓縮后的航跡增加方向?qū)傩裕瑫r(shí)也有效去除了原始航跡中航向抖動的問題，為后續(xù)航向異常檢測提供條件。之后本文采用分類處理的思想在重構(gòu)的8個(gè)航向上分別構(gòu)建正常航路模型，為異常檢測提供了模型條件。最后本文借助構(gòu)建的8個(gè)航向的正常航路模型采用一種滑窗檢測方法，通過計(jì)算滑窗內(nèi)航跡的異常度實(shí)現(xiàn)最終的航跡異常檢測。實(shí)驗(yàn)結(jié)果顯示可以有效提取出部分類型的異常航跡。該算法為船舶航跡異常檢測提供了一種算法支持。

本文雖然可以檢測部分類型的異常檢測，但是對于超出雷達(dá)威力范圍的航跡容易出現(xiàn)誤判，尤其當(dāng)密度閾值TDi選取較大時(shí)越發(fā)明顯；同時(shí)由于異常檢測閾值ThP是一個(gè)經(jīng)驗(yàn)值，不便于后續(xù)遷移到其他數(shù)據(jù)進(jìn)行應(yīng)用，所以需要進(jìn)一步閾值的設(shè)置進(jìn)行實(shí)驗(yàn)探索研究及理論證明。