基于DBSCAN和iForest算法的船舶異常行為分析?

（蘭州大學(xué)信息科學(xué)與工程學(xué)院 蘭州 730000）

1 引言

隨著5G時代的來臨與物聯(lián)網(wǎng)行業(yè)的興起，海量數(shù)據(jù)蜂擁而至，船舶自動識別系統(tǒng)（AIS）的數(shù)據(jù)量也與日俱增。同時伴隨著一帶一路發(fā)展戰(zhàn)略，繁雜的數(shù)據(jù)為海洋監(jiān)管提出了更多的挑戰(zhàn)。船舶在航行過程中，受到風(fēng)、流和雷電等氣象環(huán)境異常時，容易造成航道偏差，造成位置異常；追越，橫越，多船舶會遇等人為因素或其他突發(fā)情況也會給水上交通帶來安全隱患。特別是大型船舶的異常航行，若未及時發(fā)現(xiàn)并糾正，最終會造成失控風(fēng)險，損失難以估量。因此，船舶在第一時間發(fā)現(xiàn)行為異常時，如果及時監(jiān)測到并報警，就能大大降低船舶異常行為的危害性，保證航行安全。在當(dāng)前大型船舶數(shù)量與快速增長的情況下，異常識別，不僅對于船舶駕駛?cè)藛T，船舶航運(yùn)監(jiān)管人員，甚至整個航運(yùn)業(yè)來說，都是非常現(xiàn)實(shí)的問題。海上交通特征規(guī)律蘊(yùn)含于海量的船舶AIS歷史數(shù)據(jù)中。從海上交通工程的角度研究船舶行為模式，利用數(shù)據(jù)挖掘技術(shù)對AIS數(shù)據(jù)進(jìn)行分析，所挖掘的船舶行為知識可以運(yùn)用到船舶航行位置預(yù)測、船舶異常行為檢測及海上交通流模擬等研究領(lǐng)域，為港口主管部門的通航環(huán)境管理等提供理論依據(jù)［1］。本文目的是通過AIS數(shù)據(jù)的分析，感知海上交通態(tài)勢以及識別異常船舶，使得海事部門及船舶公司盡早發(fā)現(xiàn)異常，及時預(yù)警，快速排查問題船舶。采用該方法進(jìn)行船舶異常識別的穩(wěn)定性較好，結(jié)合線性時間復(fù)雜度的iForest算法［2］，化繁為簡，同時也提高了船舶異常行為識別的準(zhǔn)確性。

近年來，隨著AIS（Automatic Identification Sys?tem，船舶自動識別系統(tǒng)）設(shè)備的應(yīng)用，通過海量的AIS數(shù)據(jù)，可以實(shí)現(xiàn)船舶全球監(jiān)控。每個AIS解碼消息，由MMSI編號標(biāo)識，包含靜態(tài)和動態(tài)信息，前者與船舶的識別有關(guān)（如船型、呼號、名稱、國際海事組織（IMO）編號、長寬），后者則與狀態(tài)向量有關(guān)（如位置、對地航向（COG）、對地航速（SOG）），以及歷史和當(dāng)前航線模式有關(guān)）［3］。本文主要針對AIS動態(tài)信息進(jìn)行實(shí)驗(yàn)分析。

2 船舶異常行為概念及研究現(xiàn)狀

船舶異常行為指的是與所期望的船舶活動相偏離的行為，即與船舶群體運(yùn)動總體行為相偏離的行為。通常包括船舶偏離正常航道，突然加速、減速，出現(xiàn)在不該進(jìn)入的區(qū)域等。而船舶異常行為檢測是從船舶軌跡歷史記錄提取出船舶運(yùn)動總體的宏觀行為，依此找出與總體特征差異較大的個體行為［4］。通過分析船舶的一般行為，某些數(shù)據(jù)對象與其不一致時，可得到部分離群點(diǎn)。從異常檢測算法來說，離群值是一種觀測值，它與其他觀測值偏差大，以至于懷疑它就是一個不同機(jī)制生產(chǎn)的數(shù)據(jù)點(diǎn)［5］。Richard O.Lane介紹了船舶的五種異常行為：偏離標(biāo)準(zhǔn)航線、意外的AIS活動、意外的入港、接近和區(qū)域進(jìn)入［6］。常見的異常成因：數(shù)據(jù)來源于不同的類（異常對象來自于一個與大多數(shù)數(shù)據(jù)對象源（類）不同的源（類）的思想），自然變異，以及數(shù)據(jù)測量或收集誤差［7］。海上AIS數(shù)據(jù)的運(yùn)動軌跡本來會有一些不確定性，本文旨在發(fā)現(xiàn)這些數(shù)據(jù)潛在規(guī)律，針對這些數(shù)據(jù)，結(jié)合地理領(lǐng)域知識，專家知識，進(jìn)行統(tǒng)計與分析，并建立數(shù)據(jù)驅(qū)動的異常檢測器，合理可靠地檢測異常行為。通過不斷地更新數(shù)據(jù)，建立更大的正常數(shù)據(jù)樣本，為研究海洋船舶運(yùn)動模型打下基礎(chǔ)。

利用船舶AIS數(shù)據(jù)對船舶異常行為檢測監(jiān)控是現(xiàn)今船舶的熱點(diǎn)問題，B.Ristic等人利用核密度估計的方法，在零假設(shè)的條件下，從實(shí)際AIS歷史數(shù)據(jù)中，構(gòu)建正常模型識別船舶異常［8］。Rikard?Laxhammar使用無監(jiān)督學(xué)習(xí)，高斯混合模型的方式，使用EM算法構(gòu)建船舶軌跡檢測模型，通過概率密度函數(shù)識別船舶異常行為［9］。甄榮利用統(tǒng)計學(xué)曲線擬合最小二乘法，得到正常船舶的數(shù)學(xué)表達(dá)模型［10］。姜佰辰同樣使用高斯混合模型及EM算法實(shí)現(xiàn)異常檢測，主要針對大連港渤海區(qū)域船舶軌跡主成分分析［11］。這些方法在宏觀上建立模型，對于具體船舶所處海域港口以及船舶所處環(huán)境和船舶軌跡航速等特征提取較少。本文主要是面向北部灣海域，對船舶軌跡點(diǎn)及對地航速進(jìn)行重點(diǎn)分析，結(jié)合聚類與異常檢測算法，對比不同模型下的評估標(biāo)準(zhǔn)，針對性找尋適合北部灣區(qū)域的船舶異常識別方法。

由于采集到的原始AIS信息沒有標(biāo)簽，一般采取無監(jiān)督方式的機(jī)器學(xué)習(xí)，實(shí)驗(yàn)方法與評判難度較大。本文通過化繁為簡，不直接對系統(tǒng)正常行為建模，因?yàn)榇祟愑绊憦?fù)雜，且未知。定義一個先驗(yàn)假設(shè)，即異常并不是集中的。離群點(diǎn)檢測是監(jiān)督學(xué)習(xí)的一種替代方法，特別是標(biāo)簽信息難以獲取或不可靠的應(yīng)用中，將非監(jiān)督方法轉(zhuǎn)化為分類。該方案將檢測密度水平定義為一個分類問題，很好地采用了所使用的分類算法［12］。由于缺乏經(jīng)驗(yàn)性的度量方式，我們將通過預(yù)先的速度（SOG）聚類，結(jié)合地理環(huán)境港口碼頭情況，對比支持向量機(jī)，協(xié)方差穩(wěn)健估計，孤立森林和局部異常因子檢測等方法，選取最優(yōu)模型，判斷出速度及位置異常。

3 研究方法

在異常檢測算法中，大多數(shù)方法傾向于首先對軌跡進(jìn)行預(yù)處理［4］。在預(yù)處理過程中，采用聚類分析，這是一種無監(jiān)督的機(jī)器學(xué)習(xí)方法。一般根據(jù)數(shù)據(jù)本身的性質(zhì)，固有屬性，按照某種內(nèi)在指標(biāo)將其分成若干個簇，使得簇內(nèi)相似度大，不同簇之間相似度小。本文根據(jù)領(lǐng)域知識定義模式之間的距離測度并選取DBSCAN算法對船舶軌跡點(diǎn)及速度進(jìn)行聚類。該算法利用基于密度聚類的概念，即要求聚類空間中的一定區(qū)域內(nèi)所包含對象的數(shù)目不小于某一給定閥值［13］。借此，以快速處理噪聲并構(gòu)建任意形狀的聚類。通過聚類比較其輪廓系數(shù)，選擇合適的分簇，合理分配速度比例，能夠有效提取速度異常。

本文通過一類支持向量機(jī)（One-Class SVM），協(xié)方差穩(wěn)健估計（Robust covariance），局部異常因子（Local Outlier Factor）以及孤立森林（iForest）算法對比，擇優(yōu)選取iForest算法為主要的識別方法。其中，One-Class SVM對異常值敏感并因此對異常值檢測執(zhí)行得較好。當(dāng)訓(xùn)練集不受異常值污染時，此估計器最適合異常檢測［12］。也就是說，在高維中進(jìn)行離群點(diǎn)檢測，或者不對基礎(chǔ)數(shù)據(jù)的分布進(jìn)行任何假設(shè)時，一類支持向量機(jī)可以給出有效的結(jié)果。Robust covariance的協(xié)方差矩陣對異常值的變化非常敏感，如果波動較大，評價結(jié)果將產(chǎn)生不穩(wěn)定因素。當(dāng)出現(xiàn)差異較大的個體時，將會導(dǎo)致協(xié)方差發(fā)生較大變化，主成分提取會產(chǎn)生較大變化，穩(wěn)健協(xié)方差估計的核心就是利用迭代思想，不斷計算離群點(diǎn)和中心的馬氏距離，最終找到一個穩(wěn)定的中心群點(diǎn)，形成所需要的協(xié)方差估計［14］。Local Outlier Factor（LOF）通過計算一個數(shù)值來反映一個樣本的異常程度，其核心部分是關(guān)于數(shù)據(jù)點(diǎn)密度的表達(dá)。這個數(shù)值的大致意思是：一個樣本點(diǎn)周圍的樣本點(diǎn)所處位置的平均密度比上該樣本點(diǎn)所在位置的密度。比值越大于1，則該點(diǎn)所在位置的密度越小于其周圍樣本所在位置的密度，這個點(diǎn)就越有可能是異常點(diǎn)［15］。局部離群點(diǎn)檢測是基于最鄰近方法，有較高的計算要求，因?yàn)樽罱彿椒ㄐ枰鎯λ谢虼蟛糠诌^去的實(shí)例，以便對未來的數(shù)據(jù)進(jìn)行有效的分類。

孤立森林（Isolation Forest）算法是一種集成算法（類似于隨機(jī)森林），主要用于挖掘異常數(shù)據(jù)，或者說離群點(diǎn)挖掘，是在一大堆數(shù)據(jù)中，找出與其它數(shù)據(jù)的規(guī)律不太符合的數(shù)據(jù)。該算法不采樣任何基于聚類或距離的方法，因此他和那些基于距離的異常值檢測算法有著根本上的不同，孤立森林認(rèn)定異常值的原則是異常值是少數(shù)的和不同的數(shù)據(jù)，能夠產(chǎn)生一個更接近數(shù)據(jù)的邊界，而且顯得較為平滑。

整個算法的過程就是隨機(jī)選擇一個特征，再在該特征下最大與最小值間隨機(jī)選擇一個值作為切分點(diǎn)，遞歸切分?jǐn)?shù)據(jù)集，直到每個樣本點(diǎn)被隔開，從而構(gòu)建一棵類似分類樹的隨機(jī)樹。重復(fù)構(gòu)建多顆隨機(jī)樹。從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑越長，代表該點(diǎn)越難被隔離，即該點(diǎn)越不可能是異常點(diǎn)。計算每個樣本點(diǎn)路徑長的平均值，即得到該點(diǎn)得分，得分越低越可能是異常點(diǎn)。在定義的二叉樹中，不成功搜索的平均路徑長度為

其中 H（i）為調(diào)和數(shù)，可由 ln(i)+0.5772156649(歐拉常數(shù))估計。由于c（Ψ）是h（x）的平均值，我們用它來標(biāo)準(zhǔn)化h（x）。則x的異常得分s定義為

式中，E（h（x））是集合中h（x）的平均值。以下條件提供了異常值的三個特殊值：

1）當(dāng)E（h（x））→0，s→1；

2）當(dāng)E（h（x））→ψ-1，s→0；

3）當(dāng)E（h（x））→c（ψ），s→0.5。

使用異常評分s，我們可以進(jìn)行以下評估：

1）如果最后返回的s非常接近1，那么它們肯定是異常；

2）如果最后的s遠(yuǎn)遠(yuǎn)小于0.5，那么它們被視為正常，且相當(dāng)安全的；

3）當(dāng)s約等于0.5時，整個樣本并沒有任何明顯的異常。

經(jīng)比較，本文重點(diǎn)使用孤立森林算法對船舶劃分決策區(qū)間，分析識別異常點(diǎn)。在數(shù)據(jù)集中，異常數(shù)據(jù)往往占據(jù)極少數(shù)且與正常數(shù)據(jù)有所差異，因此在整個數(shù)據(jù)集中易于分開。iForest使用了一套非常高效的策略，借鑒了隨機(jī)森林集成學(xué)習(xí)的思想，不需要計算點(diǎn)對點(diǎn)的距離或每個點(diǎn)的密度，大大的降低了算法的復(fù)雜度［16］。

4 實(shí)驗(yàn)過程及分析

實(shí)驗(yàn)使用的計算機(jī)配置為英特爾酷睿i5 CPU M430@2.27 GHz，內(nèi)存：4.7GB，Linux操作系統(tǒng)。實(shí)驗(yàn)數(shù)據(jù)來自美國marinetraffic網(wǎng)站（https：//www.marinetraffic.com），實(shí)驗(yàn)使用Python語言在Spyder環(huán)境下訓(xùn)練擬合。

4.1 實(shí)驗(yàn)過程

首先進(jìn)行數(shù)據(jù)預(yù)處理：在全球2G大小，1.6億條船舶數(shù)據(jù)中篩選出北部灣區(qū)域的AIS數(shù)據(jù)，本實(shí)驗(yàn)使用某時刻該海域一千余條船舶分布點(diǎn)進(jìn)行實(shí)驗(yàn)。先刪除MMSI、SOG、COG為空的行。刪除速度，經(jīng)緯度異常值（如速度負(fù)值或大于100，經(jīng)度大于180°，緯度大于90°）。定義一個圍繞北部灣內(nèi)部，約150km的數(shù)據(jù)集，經(jīng)緯度范圍為經(jīng)度介于108°E到110°E，緯度介于20°N到22°N，從已獲取的23萬條船舶中篩選出該范圍內(nèi)的一千條船，可視化如圖2所示，與船訊網(wǎng)分布（圖1）大體一致，然后進(jìn)行聚類分析。通過這樣的選擇性抽樣可以簡化問題，同時針對性更強(qiáng)。

圖1 船訊網(wǎng)北部灣海域

圖2 實(shí)驗(yàn)下北部灣數(shù)據(jù)

預(yù)先通過DBSCAN算法對船舶位置及航速航向（見圖3）分別聚類。位置聚類大致效果如圖4，重點(diǎn)是將速度分簇（見圖5），針對AIS數(shù)據(jù)進(jìn)行船舶軌跡數(shù)據(jù)挖掘，找出異常點(diǎn)并分析異常行為，可以通過軌跡聚類，首先將船舶軌跡相似性分組。然后利用分類或者離群點(diǎn)檢測、奇異值檢驗(yàn)的方式，從規(guī)則的模式中檢測出異常。在船舶運(yùn)動規(guī)律中，除了軌跡點(diǎn)經(jīng)緯度信息，更重要的就是其SOG速度信息。對于速度信息，SOG取值范圍為0～1022，以1/10節(jié)距為單位，最高為1022也就是102.2節(jié)［17］。

圖3 船舶航速航向散點(diǎn)圖

圖4 基于DBSCAN的船舶分布

圖5 分簇不同情況下的輪廓系數(shù)及速度分布

針對北部灣海域的某時刻船舶AIS數(shù)據(jù)，SOG取值從0～54，即，此區(qū)域船舶速度在0～5.4節(jié)，對此進(jìn)行速度聚類。在聚類方式上，由于K-means需要預(yù)先設(shè)定K值，對最先的K個點(diǎn)選取很敏感，且數(shù)據(jù)較大時容易陷入局部最優(yōu)，而DBSCAN能發(fā)現(xiàn)任意形狀的聚類，根據(jù)船舶密度稀疏不同，改進(jìn)了DBSCAN當(dāng)中eps參數(shù)的選擇，根據(jù)船舶間的歐氏距離，定義模式之間的距離測度，使得eps與船舶間平均距離相關(guān)，最終將船舶與北部灣海域地理環(huán)境較好匹配，基本分布在不同港口范圍內(nèi)。將速度分成三簇，以便與后續(xù)iForest的算法結(jié)合，綜合判別異常行為。

在評價中，當(dāng)然是希望聚類的簇內(nèi)凝聚度越高越好，同時簇間的分離度也越高越好，但事實(shí)上這兩者在某些情況下需要平衡。輪廓系數(shù)（Silhou?ette Coefficient）這一指標(biāo)結(jié)合了聚類的凝聚度和分離度，能夠很好地用于評估聚類的效果。該值處于-1與1之間，值越大，表示聚類效果越好。可以用來在相同原始數(shù)據(jù)的基礎(chǔ)上用來評價不同算法、或者算法不同運(yùn)行方式對聚類結(jié)果所產(chǎn)生的影響。具體輪廓系數(shù)如下式：

其中a（i）為i向量到同一簇內(nèi)其他點(diǎn)不相似程度的平均值，b（i）為i向量到其他簇的平均不相似程度的最小值［18］。

通過對已處理的AIS數(shù)據(jù)的對地航速，將SOG進(jìn)行速度聚類。在該情況下，速度分別被聚為2，3，4，5，6類時，所對應(yīng)的輪廓系數(shù)見表1。

表1 不同速度分簇下的輪廓系數(shù)

按照輪廓系數(shù)的比較，當(dāng)速度聚為6簇時，輪廓系數(shù)最大，但根據(jù)圖5（a），圖5（b）比較，可視化后，速度分為3簇更為合適。當(dāng)錨泊或系泊且移動速度不超過3節(jié)的船舶AIS發(fā)送間隔較長［17］，通常是3min。換而言之，船速在3節(jié)以下的船舶都是低速航行。因此我們將SOG按照相對低中高的速度分為［0，25］，［25，40］，［40，60］三個區(qū)間。

在速度分為3簇的情況下，分別用紫色，藍(lán)色和黃色表示船舶某時刻在當(dāng)前海域中所對應(yīng)的低速，中速，高速這三個劃分狀態(tài)，見圖6。

圖6 船舶速度狀態(tài)分類

根據(jù)船舶在北部灣海域分布情況，構(gòu)造一個包含第3節(jié)介紹的四種模型的分類器，將預(yù)處理的數(shù)據(jù)擬合到每個模型，然后對比每個模型如何檢測異常值。預(yù)處理后的數(shù)據(jù)內(nèi)部遵循一些船舶運(yùn)動真實(shí)情形下的隱藏約束。計算出各個模型的輪廓系數(shù)（見表2）以及對比各模型的異常邊界（見圖7）。

表2 模型指標(biāo)對比

圖7 四種算法決策邊界對比

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

根據(jù)四種模型比對，一類支持向量機(jī)與孤立森林能夠很好的將位于（21.7°N，109.8°E）異常點(diǎn)識別出來，經(jīng)查驗(yàn)，此點(diǎn)位于沿岸陸地。而對于（20.2°N，110°E）附近的點(diǎn)，主要是瓊州海峽進(jìn)出港船舶，屬于正常船舶停靠及低速航行。針對（21.2°N，109°E）速度異常點(diǎn)查驗(yàn)，發(fā)現(xiàn)該點(diǎn)船舶狀態(tài)AIS?VesselType為Fishing，與周圍船舶相比這個速度捕魚，明顯異常。由于在海圖上截取部分區(qū)域，因此對于（20°N，108°E）附近海域的局部識別效果不是特別好。相對于其他三種算法，iForest的輪廓系數(shù)最高，運(yùn)行時間也相對較高，但整體劃分效果較好，決策邊界能夠與海岸線相接近匹配，決策邊界更友好。

考慮到海上航行及錨地港口停泊，進(jìn)出港速度及航行的位置不同，結(jié)合地理領(lǐng)域知識，港口及海岸線等情況，可以更好地分析判別船舶異常點(diǎn)。

孤立森林的算法本質(zhì)上是一個無監(jiān)督學(xué)習(xí)，不需要數(shù)據(jù)的類標(biāo)，但根據(jù)算法所給出的結(jié)果找這個數(shù)據(jù)的內(nèi)在結(jié)構(gòu)，尤其是對于海岸線結(jié)構(gòu)，港口情況都能較好擬合。因?yàn)槭羌蓪W(xué)習(xí)的方法，所以可以用在含有海量數(shù)據(jù)的數(shù)據(jù)集上面。通常樹的數(shù)量越多，算法越穩(wěn)定。由于每棵樹都是互相獨(dú)立生成的，因此可以部署在大規(guī)模分布式系統(tǒng)上來減少運(yùn)行時間，加快速度［19］。

5 結(jié)語

通過聚類及異常點(diǎn)識別的算法，經(jīng)可視化識別分析，結(jié)合DBSCAN的iForest算法能夠準(zhǔn)確地找到船舶間的這種相對隔離程度。針對北部灣區(qū)域進(jìn)行船舶的聚類分析，并結(jié)合船舶歷史軌跡研究發(fā)現(xiàn)，大部分船舶分布在（20.2°N，110°E）瓊州海峽，（21.5°N，109.5°E）鐵山港，（21.5°N，109°E）北海港，（21.75°N，108.5°E）欽州港，（21.5°N，108.3°E）防城港附近區(qū)域，這里的船舶港口或者錨地行駛，其航跡點(diǎn)分布及速度規(guī)律符合航行與停泊大致規(guī)律，分布密度稀疏程度已形成模式，離群點(diǎn)（孤立點(diǎn)）或異常點(diǎn)區(qū)別于正常船舶軌跡點(diǎn)分布。結(jié)合速度規(guī)律，通過iForest模型擬合，可以對今后海洋監(jiān)管當(dāng)中的實(shí)時數(shù)據(jù)，進(jìn)行早期預(yù)警。進(jìn)行這種融合的好處在于將船舶位置與速度的異常結(jié)合起來，充分利用港口信息和AIS基本信息，高效快速發(fā)現(xiàn)異常點(diǎn)，對應(yīng)異常船舶的MMSI和船舶名稱，找到相關(guān)所述單位或集團(tuán)公司，及時上報排疑，便于監(jiān)控人員及時發(fā)現(xiàn)問題，有利于加強(qiáng)船舶的岸基管控把關(guān)。

后續(xù)，通過對異常行為分析中的高發(fā)地點(diǎn)進(jìn)行標(biāo)記，記錄船舶發(fā)生故障地點(diǎn)并結(jié)合當(dāng)?shù)貧庀髼l件和故障時間，還可以為船隊(duì)航行保障提供參考。