分層建模的船舶軌跡快速聚類算法

王森杰 何正偉

(武漢理工大學航運學院1) 武漢 430063) (內河航運技術湖北省重點實驗室2) 武漢 430063) (國家水運安全工程技術研究中心3) 武漢 430063)

0 引 言

船舶自動識別系統(auto identification system，AIS)[1]是一種實現船船、船岸通信的安全助航設備，船舶通過搭載AIS終端實時將自身船舶運動信息進行廣播，通過岸基終端可以快速采集移動船舶的AIS數據.AIS數據不僅記錄船舶的空間信息、時間信息，同時集成了對地航向、船首向和對地速度等船舶運動數據，蘊含豐富的語義和行為模式.對船舶軌跡數據進行聚類分析，可為船舶交通流特征提取、航路安全規劃、船舶異常檢測等技術研發和應用提供基礎手段和關鍵方法，為航運規劃、海事監管等工作開展提供決策支持和科學依據[2].在軌跡數據激增和大數據技術發展的背景下，如何從軌跡數據中挖掘積累的物體運動模式，已經成為軌跡數據分析領域的研究熱點之一.馬文耀等[3]提出了一種基于單向距離的軌跡相似度計算方法，該方法將單向距離定義為一條船舶軌跡上各個點到另一軌跡各個點的最小距離的平均值，利用譜聚類算法對軌跡的空間分布進行學習，獲取船舶的正常運動模式.Zhen等[4]人整合k-medoids聚類和樸素貝葉斯分類器，實現了船舶行為的分類和異常行為檢測.Zhao等[5]人基于原始樸素DP算法和DBSCAN算法實現船舶軌跡模式的快速分類辨識.江玉玲等[6]采取Frechet距離對船舶軌跡相似度進行建模，基于DBSCAN聚類方法對典型軌跡得到了的符合實際的聚類結果.張春瑋等[7]綜合船舶位置、航速、航向等信息，對不同屬性數據進行加權求和得到軌跡特征，利用DBASCAN算法實現了航道內船舶異常行為的分類辨識.彭祥文等[8]設計了一種基于軌跡分區預處理的并行化子軌跡聚類算法，通過數據分區并行實現了聚類加速.綜上，這些專家學者對于船舶軌跡聚類研究都取得了相應的結論，但是以上方法依然在兩個方面存在限制.一方面，單一特征的軌跡相似度模型沒有充分利用AIS數據多維船舶屬性特點，對復雜船舶軌跡的辨識能力不足；另一方面，多特征的軌跡相似度模型采取歸一化參數對不同特征進行加權求和計算軌跡相似度，導致權重參數設置難，當耦合參數超過三個時，在某些特征參數分布下不同特征的差異相互疊加可能會導致一些隱蔽軌跡簇無法辨識.因此如何充分利用AIS多維船舶屬性數據，建立魯棒的軌跡相似度模型，提高聚類算法對隱蔽軌跡簇的辨識和聚類效率是當前船舶軌跡聚類研究的重點.

針對AIS數據集成空間、時間和其他多維屬性的特點，文中提出了一種分層建模的船舶軌跡快速聚類算法.通過分層建模，以非全耦合的方式對不同特征參數進行有效利用，解決傳統融合特征建模中參數權重設置困難，某些隱蔽軌跡簇無法辨識的問題.該算法將軌跡點的經緯度、對地航速、加速度、船艏向、對地航向共五種特征參數根據特征特點劃分為空間、速度和方向三大特征類型，在不同層次建立對應特征軌跡相似度模型，通過三次自上而下的層次遞進聚類，逐步放大聚類的分辨率，完成對船舶隱蔽軌跡簇的挖掘.同時針對傳統軌跡聚類計算量大、聚類時間長等缺點，本文提出一種DP改進算法對船舶AIS軌跡特征點進行提取，實現數據壓縮和聚類加速.

1 多特征層次軌跡聚類

1.1 相似度分層建模

軌跡聚類的本質是按照軌跡數據的相似性進行對象的劃分，而聚類劃分的結果嚴重取決于軌跡相似度模型的構建方式.因此，如何評價軌跡數據間距離或相似度是聚類處理的關鍵問題之一.船舶AIS軌跡數據是一種多維數據，它包括船舶位置、對地航速、對地航向、船艏向、轉向率等船舶運動狀態信息.針對AIS數據多維屬性特點，本文將多種船舶狀態數據劃分為三組，在層次聚類中的上、中、下層中依次建立軌跡相似度模型，不同層次的軌跡相似度計算過程如下.

設兩條不等長軌跡時間序列P=(p1,p2,…,pM)和Q=(q1,q2,…,qN)，每個軌跡點包含六種船舶狀態參數.

(1)

(2)

式中：x為經度；y為緯度；s為對地航速；a為加速度；c為對地航向；h為船首向；i和j為軌跡序列第i和第j個軌跡點.在多特征層次聚類過程中，上層利用船舶位置信息進行聚類，其中任意軌跡點pi和qj的空間差異r1(pi,qj)為

(3)

中層利用船舶速度、加速度信息聚類，其中任意軌跡點pi和qj的速度差異r2(pi,qj)為

(4)

下層利用船舶對地航向、船首向信息聚類，其軌跡點pi和qj的航向差異r3(pi,qj)為

(5)

(6)

r3(pi,qj)=Δc+Δh

(7)

本文采取DTW算法[9]計算兩條軌跡間的相似度.對于兩條不等長軌跡序列P和Q，軌跡間相似度為各個軌跡點的累積最小差異.利用動態規劃思想，從兩條軌跡一端(p1,q1)遍歷到另一端(pM,qN)的累計最小差異為

W(pM,qN)=r(pi,qj)+

min{W(pM-1,qN),W(pM,qN-1),W(pM-1,qN-1)}

(8)

式中：r(·)在不同層次聚類過層中分別表示特征相似度函數r1(·)、r2(·)、r3(·).

1.2 分層聚類

本文提出了一種自頂而下的層次聚類算法，見圖1.其中船舶AIS數據多維屬性被分層利用：基于經緯度聚類實現軌跡的空間分布分析；基于速度、加速度聚類實現船舶的加、減速行為辨識；基于船艏向、對地航向聚類實現船舶避讓、掉頭等行為識別.在多次遞進聚類過程中，簇間差異被逐步放大，而不是一次性聚類，從而實現隱蔽軌跡簇辨識.同時分層建模有效解決了傳統融合特征建模中參數權重設置困難的問題.

圖1 多特征分層聚類示意圖

采用DBSCAN算法作為層次聚類算法的核算法.DBSCAN算法需要預先設置的領域半徑ε和簇內元素最小數目minPts.該算法通過遍歷軌跡集合，計算兩兩軌跡之間的相似度，將相似度低于ε的軌跡劃分到一個新集合內，如果該集合元素數目大于minPts則被定義為一個新類，否則劃為噪聲類.DBSCAN算法對噪聲數據不敏感，無須事先設定簇個數，非常適合船舶AIS軌跡數據噪聲點多，軌跡模式不確定性高等情況下的聚類[10-11].其多特征分層聚類步驟如下.

步驟1將空間位置信息作為上層特征，聚類得到大類軌跡簇.

步驟2將船舶對地航速、加速度作為中間層特征對得到的每一個大類軌跡簇進行進一步聚類得到中類軌跡簇.

步驟3將對地航向、船首向作為下層特征，同時對下層聚類條件進行約束，僅對中層聚類結果中軌跡數目最多的軌跡簇進行進一步下層聚類，其他簇不進行下層聚類，直接作為最后結果.

2 聚類加速

2.1 快速軌跡聚類框架

圖2 軌跡特征點提取

2.2 壓縮算法

DP算法是一種基于軌跡形狀的軌跡壓縮算法，在壓縮軌跡的同時能夠保存軌跡的形狀特征[15].但是DP算法僅僅考慮了軌跡點的空間位置，而沒有考慮船舶對地速度、船首向、對地航向等信息，導致對于直線加速、減速、減速轉向等特殊軌跡段進行壓縮時會發生關鍵特征軌跡點提取丟失.本文綜合船舶位置、對地速度、對地航向、船首向信息對DP算法進行改進，提出了一種軌跡特征點提取算法.該算法在壓縮軌跡點數量的同時，可以保留船舶不同駕駛行為特征信息.軌跡點提取算法流程見圖3.

圖3 船舶軌跡特征點提取流程

3 實驗及分析

3.1 試驗數據

蝦峙門口外深水航槽是一條供大吃水受限船舶進出蝦峙門的人工航槽.由于該區域沒有采取定線制，導致進出蝦峙門國際航道的船舶和南下北上的穿越船舶在此區域形成復雜的交通環境.本文提取2018年1月份100條船舶軌跡，共12 118條AIS數據作為試驗數據對分層建模聚類算法進行驗證.

對原軌跡集合100條軌跡，先利用上層特征船舶位置信息進行上層聚類，見圖4.其領域半徑ε設置為0.15，簇內元素最小數目minPts設置為15.由圖4可知：上層特征將100條船舶軌跡辨識為3類，“class 1”標記軌跡被辨識為下行出港船舶，“class 3”標記的軌跡被辨識為上行進港船舶，“class 2”標記軌跡被辨識為噪聲數據，即橫穿等異常行為軌跡數據.

圖4 上層特征聚類結果

對于上層聚類結果，繼續利用中層特征進行進一步聚類.中層聚類的領域半徑ε設置為300，簇內元素最小數目minPts設置為5.圖5a)為大類下行出港船舶進一步聚類結果，中層聚類將其進一步聚為兩類，其中“class 2”標記的軌跡均為減速的高速行駛船舶 “class 1”標記的軌跡均為低速行駛的加速船舶.圖5b)為大類異常行為軌跡的中層聚類結果.中層聚類將其進一步聚為兩類，其中“class 2”標記的軌跡均為中高速船舶，“class 1”標記的噪聲軌跡均為低速游蕩船舶.圖5c)為大類上行進港船舶進一步聚類結果.中層聚類將其進一步聚為兩類，其中“class 1”標記的軌跡均為減速行為，“class 2”標記的軌跡存在勻速行為.根據蝦峙門口外深水航槽通航安全規定，進港船舶應采取減速行為.因此“class 2”標記的軌跡應該被識別船舶非法行為.

圖5 中層特征聚類結果

對于中層聚類結果，由于聚類條件約束，下層聚類僅選取中層聚類結果中簇內元素最多的中類進行下層聚類.下層聚類的領域半徑ε設置為3 000，簇內元素最小數目minPts設置為5.圖6a)為中類加速出港船舶的進一步聚類，下層聚類將其進一步聚為兩類，其中標記為“class 1”的軌跡均為直線加速出港船舶，而標記為“class 2”的軌跡被辨識為加速出港南下船舶.圖6b)為中類穿越船舶的進一步聚類，下層聚類將其辨識為兩類，其中標記為“class 1”的軌跡均為南下橫穿船舶，而標記為“class 2”的軌跡被辨識為北上橫穿船舶.圖6c)為中類減速進港船舶的進一步聚類結果.下層聚類將其進一步聚為兩類，其中標記為“class 1”的軌跡均為直線減速進港船舶，而標記為“class 2”的軌跡被辨識為東北向匯入減速進港船舶.

圖6 下層特征聚類結果

圖7 軌跡特征柱狀統計分析圖

圖8 聚類結果的層次樹狀關系

經過3層層次聚類后，所有船舶軌跡被聚類為9類軌跡，見圖7.對每一類船舶軌跡的平均速度、平均對地航向、平均壓差角和平均加速度共4個屬性進行柱狀圖統計分析，9類軌跡被辨識為9種不同船舶行為模式的船舶，并且9類軌跡擁有圖8的層次樹狀關系.其中“class 1”為高速出港船舶，其船舶行為特征表現為初始速度快、存在小幅度減速；“class 2”為低速游蕩船舶，其船舶行為特征為平均速度低、頻繁轉向、頻繁減速；“class 3”為勻速進港船舶，其船舶行為特征變現為速度適中、速度穩定；“class 4”為加速南下出港船舶，其船舶行為特征為速度適中、下幅度加速、負壓差角；“class 5”為加速直線出港、其船舶行為特征為速度適中、加速度適中、直線行駛.“class 6”為北上橫穿船舶，船舶行為特征表現為速度適中、大幅度轉向.“class7”為南下橫穿船舶，船舶行為特征表現為速度適中、大幅度轉向.“class 8”為減速東北向匯入進港船舶、其船舶行為特征表現為速度適中、減速度適中、負壓差角.“class 9”為減速直線進港船舶、其船舶行為特征表現為速度適中、減速度適中、正壓差角.統計結果表明，分層建模的船舶軌跡聚類算法能夠有效將船舶軌跡辨識為9類軌跡模式，并且不同軌跡模式具有各自典型的軌跡特征分布.

3.3 聚類速度測試

以100條軌跡，共12 118個軌跡點作為測試數據，本文對傳統DTW-DBSCAN、LCSS-DBSCAN、Frechet-DBSCAN和分層快速聚類算法進行了聚類速度對比實驗.實驗環境：python3.5，實驗設備：i5-8250，內存8g.對于分層快速軌跡聚類算法，設置壓縮閾值參數Th1=0.000 15，Th2=2，Th3=10，Th4=10.表1為目前算法和分層快速聚類算法在實驗數據上的聚類時間結果.可以發現，DTW-DBSCAN、LCSS-DBSCAN、Frechet-DBSCAN在聚類速度速度上大致相等，約為283 s.而分層快速聚類算法，在4.025壓縮倍率下，聚類速度約為傳統無壓縮算法的16倍.通過對比發現本文提出的聚類加速框架能夠明顯提升聚類速度，其速度提升倍率約為軌跡壓縮倍率ρ的平方，與理論提升效率一致.

表1 聚類速度結果

4 結 束 語

針對目前軌跡聚類算法存在的缺點，本文充分利用船舶AIS數據的多維屬性數據，提出了一種分層建模的軌跡聚類算法.通過分層建模，解決了融合特征模型中權重參數取值困難的問題，提高了模型的魯棒性.通過遞進聚類，依次放大類間差異，從而達到對隱蔽軌跡簇的辨識.同時改進DP算法，在軌跡聚類前先對軌跡進行特征點提取，通過數據規整和壓縮有效提高了聚類效率.利用蝦峙門深水航槽的數據進行了實驗和分析，結果表明，分層建模的軌跡聚類算法能夠有效辨識復雜船舶交通環境下各種船舶軌跡模式，同時該算法能夠在層次聚類過層中有效挖掘不同船舶軌跡模式的樹狀層次關系，對于加強船舶交通行為分析和船舶交通監管具有重要意義.同時聚類速度對比實驗的結果證明該框架能夠極大提高聚類速度時間，對于目前快速增長的船舶AIS大數據分析極具現實意義.