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

（蘭州大學信息科學與工程學院 蘭州 730000）

1 引言

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

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

2 船舶異常行為概念及研究現狀

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

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

由于采集到的原始AIS信息沒有標簽，一般采取無監督方式的機器學習，實驗方法與評判難度較大。本文通過化繁為簡，不直接對系統正常行為建模，因為此類影響復雜，且未知。定義一個先驗假設，即異常并不是集中的。離群點檢測是監督學習的一種替代方法，特別是標簽信息難以獲取或不可靠的應用中，將非監督方法轉化為分類。該方案將檢測密度水平定義為一個分類問題，很好地采用了所使用的分類算法［12］。由于缺乏經驗性的度量方式，我們將通過預先的速度（SOG）聚類，結合地理環境港口碼頭情況，對比支持向量機，協方差穩健估計，孤立森林和局部異常因子檢測等方法，選取最優模型，判斷出速度及位置異常。

3 研究方法

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

本文通過一類支持向量機（One-Class SVM），協方差穩健估計（Robust covariance），局部異常因子（Local Outlier Factor）以及孤立森林（iForest）算法對比，擇優選取iForest算法為主要的識別方法。其中，One-Class SVM對異常值敏感并因此對異常值檢測執行得較好。當訓練集不受異常值污染時，此估計器最適合異常檢測［12］。也就是說，在高維中進行離群點檢測，或者不對基礎數據的分布進行任何假設時，一類支持向量機可以給出有效的結果。Robust covariance的協方差矩陣對異常值的變化非常敏感，如果波動較大，評價結果將產生不穩定因素。當出現差異較大的個體時，將會導致協方差發生較大變化，主成分提取會產生較大變化，穩健協方差估計的核心就是利用迭代思想，不斷計算離群點和中心的馬氏距離，最終找到一個穩定的中心群點，形成所需要的協方差估計［14］。Local Outlier Factor（LOF）通過計算一個數值來反映一個樣本的異常程度，其核心部分是關于數據點密度的表達。這個數值的大致意思是：一個樣本點周圍的樣本點所處位置的平均密度比上該樣本點所在位置的密度。比值越大于1，則該點所在位置的密度越小于其周圍樣本所在位置的密度，這個點就越有可能是異常點［15］。局部離群點檢測是基于最鄰近方法，有較高的計算要求，因為最近鄰方法需要存儲所有或大部分過去的實例，以便對未來的數據進行有效的分類。

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

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

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

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

1）當E（h（x））→0，s→1；

2）當E（h（x））→ψ-1，s→0；

3）當E（h（x））→c（ψ），s→0.5。

使用異常評分s，我們可以進行以下評估：

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

2）如果最后的s遠遠小于0.5，那么它們被視為正常，且相當安全的；

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

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

4 實驗過程及分析

實驗使用的計算機配置為英特爾酷睿i5 CPU M430@2.27 GHz，內存：4.7GB，Linux操作系統。實驗數據來自美國marinetraffic網站（https：//www.marinetraffic.com），實驗使用Python語言在Spyder環境下訓練擬合。

4.1 實驗過程

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

圖1 船訊網北部灣海域

圖2 實驗下北部灣數據

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

圖3 船舶航速航向散點圖

圖4 基于DBSCAN的船舶分布

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

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

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

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

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

表1 不同速度分簇下的輪廓系數

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

在速度分為3簇的情況下，分別用紫色，藍色和黃色表示船舶某時刻在當前海域中所對應的低速，中速，高速這三個劃分狀態，見圖6。

圖6 船舶速度狀態分類

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

表2 模型指標對比

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

4.2 實驗結果分析

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

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

孤立森林的算法本質上是一個無監督學習，不需要數據的類標，但根據算法所給出的結果找這個數據的內在結構，尤其是對于海岸線結構，港口情況都能較好擬合。因為是集成學習的方法，所以可以用在含有海量數據的數據集上面。通常樹的數量越多，算法越穩定。由于每棵樹都是互相獨立生成的，因此可以部署在大規模分布式系統上來減少運行時間，加快速度［19］。

5 結語

通過聚類及異常點識別的算法，經可視化識別分析，結合DBSCAN的iForest算法能夠準確地找到船舶間的這種相對隔離程度。針對北部灣區域進行船舶的聚類分析，并結合船舶歷史軌跡研究發現，大部分船舶分布在（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）防城港附近區域，這里的船舶港口或者錨地行駛，其航跡點分布及速度規律符合航行與停泊大致規律，分布密度稀疏程度已形成模式，離群點（孤立點）或異常點區別于正常船舶軌跡點分布。結合速度規律，通過iForest模型擬合，可以對今后海洋監管當中的實時數據，進行早期預警。進行這種融合的好處在于將船舶位置與速度的異常結合起來，充分利用港口信息和AIS基本信息，高效快速發現異常點，對應異常船舶的MMSI和船舶名稱，找到相關所述單位或集團公司，及時上報排疑，便于監控人員及時發現問題，有利于加強船舶的岸基管控把關。

后續，通過對異常行為分析中的高發地點進行標記，記錄船舶發生故障地點并結合當地氣象條件和故障時間，還可以為船隊航行保障提供參考。