基于加權樸素貝葉斯的船舶軌跡分類算法

王維剛， 初秀民， 蔣仲廉， 劉 磊

(1.武漢理工大學 a.智能交通系統研究中心； b.能源與動力工程學院；c.國家水運安全工程技術研究中心,武漢 430063； 2.東南大學 交通學院,南京 211189)

隨著我國經濟的不斷發展，內河水運日益繁忙，船舶交通流量越來越大，通航飽和度逐漸升高，航道通過能力趨于飽和，內河通航水域海事安全監管面臨的挑戰越來越大。[1]船舶自動識別系統(Automatic Identification System，AIS)能為水路交通安全研究提供海量的基礎數據，在不同的研究方向都有廣泛的應用。[2]隨著智能航運的發展，AIS等數據呈現出指數級的遞增趨勢,開展船舶軌跡分類算法研究，有助于提高數據處理效率，為航運大數據的信息融合和綜合利用奠定基礎。通過基于AIS的船舶軌跡快速分類，有助于開展船舶運動模式識別和航行風險分析等，從而推動水路運輸和海事安全監管向智能化、信息化方向發展。[3]

在船舶軌跡分類研究方面：PAN等[4]提出一種基于AIS數據的軌跡聚類模型，采用該模型分析航線，實現在沒有先驗知識的情況下自動對具有軌跡特征的不同航運路線進行分類。LI等[5]結合軌跡映射和聚類方法探索從AIS中獲取的大數據，提出一種改進的基于密度的噪聲應用空間聚類(Density-Based Spatial Clustering of Applications with Noise，DBSCAN)算法，采用該算法聚類空間點，從而獲得最優聚類。彭祥文等[6]利用云計算并結合聚類算法對船舶歷史數據進行軌跡聚類分析，構建船舶航行正常軌跡模型，相比傳統算法，能提升聚類效率。劉磊等[7]對軌跡間的平均距離、航速距離和航向距離進行融合，提出船舶軌跡間綜合距離的概念，結合K最鄰近(K-Nearest Neighbor，KNN)分類器進行內河船舶軌跡分類，效果較好。牟軍敏等[8]提出一種基于豪斯多夫距離的船舶軌跡快速自適應譜聚類算法，實現高效快速的聚類，可準確地提取通航水域的主要船舶航路。朱姣等[9]提出增量式算法改進DBSCAN算法，用以高效地計算不同船舶的行為模式，基于軌跡分析挖掘船舶行為模式。這些研究主要采用聚類算法，以提高算法的效率和準確率為目的進行研究。在實際條件下，船舶航路較為固定，因而存在一些可利用的先驗信息，采用有監督的學習優化分類效果。樸素貝葉斯法是基于貝葉斯定理和特征條件獨立假設的分類方法，是眾多的分類模型中應用最廣泛的分類模型之一[10]，所需的估計參數較少，對缺失數據不太敏感，相對簡單。魏照坤等[11]利用AIS提供的數據分析通航水域船舶信息的分布情況，根據其概率分布，采用樸素貝葉斯算法，從船舶航速、航向和距航道邊界距離等3個方面構建船舶異常行為檢測模型，實現高精度的船舶異常行為檢測。AUNG等[12]使用貝葉斯分類器對車輛行為進行分類,以預測道路網絡的流量。ZHEN等[13]使用樸素貝葉斯分類器對廈門灣和城三角水域的船舶運動進行分類，據此檢測船舶異常行為,研究中未見基于樸素貝葉斯模型的AIS軌跡分類相關研究。

本文以船舶AIS歷史數據為基礎，提出一種基于樸素貝葉斯算法的船舶軌跡分類方法，針對AIS軌跡分類場景，提出一種船舶軌跡特征組合，并對分類器進行加權優化，以提高分類效果。首先，通過AIS數據預處理提取軌跡特征；其次，選取最優特征集合并訓練分類器，實現AIS軌跡數據的自動分類；最后，以長江武漢河段為例，對軌跡分類算法的有效性進行驗證。

1 樸素貝葉斯軌跡分類算法

1.1 樸素貝葉斯

假設Y為要預測的某一軌跡類，X是包含n個特征屬性X1,X2,…,Xn的已知軌跡，需求出軌跡X屬于Y類的概率p(Y|X),以對比出X屬于哪個軌跡類的概率最大，進而進行分類。[14]貝葉斯定理為

p(Y|X)=p(X,Y)/p(X)=

p(X|Y)p(Y)/p(X)

(1)

式(1)中:p(Y)為先驗概率;p(Y|X)為后驗概率;p(X|Y)為類條件概率;p(X)為證據。

樸素貝葉斯在計算p(X|Y)時，假設特征屬性相彼此獨立，該假設大大減少了估計的參數數量，由該假設可得

p(X|Y)=p(X1,X2,…,Xn|Y)

=p(X1,X2,…,Xn-1|Xn,Y)p(Xn|Y)

=p(X1|Y)p(X2|Y) …p(Xn|Y)

(2)

式(2)表明需要一部分已知類別的軌跡數據來訓練分類器，統計得到各類別下各軌跡特征屬性的條件概率估計值p(Xi|Y)。根據上述假設，式(1)可寫為

(3)

式(3)為樸素貝葉斯分類器的基本方程。因為P(X)對每個軌跡類別都是常量，可忽略，僅考慮分子部分即可，所以基于樸素貝葉斯的AIS軌跡分類算法可定義為

(4)

式(4)中：X為待分類軌跡；yj為類別變量；Xi為X的軌跡特征。對于任一條軌跡X={X1,X2,…,Xn}，該分類算法選擇使后驗概率p(yj|X)最大的類別作為該軌跡的類。

基于樸素貝葉斯的AIS軌跡分類算法流程為

1) 對AIS數據進行清洗與分包，得到有效的船舶軌跡數據。

2) 根據軌跡包含的AIS數據為每條軌跡計算相應的特征數據，并對特征數據進行高斯擬合，得到在不同類下各特征的高斯概率分布。

3) 計算各軌跡特征屬性的條件概率估計值p(Xi|Y)。

4) 使p(X|Yj)P(Yj)最大的類作為分類結果，見圖1。

1.2 軌跡特征

AIS軌跡特征的提取主要分為初步選擇特征和尋找最優特征子集2步。初步選擇特征是指根據AIS軌跡的特點，初步選擇一些能區分不同類別的特征。根據初步選擇的特征集合不一定能得到性能最好的分類器，可能會因冗余的特征項使分類器的精度降低，因此需進一步篩選尋找最優特征子集。

圖1 分類流程

1.2.1特征初步選擇

AIS船臺發送的報文中主要包含靜態信息和動態信息。其中:靜態信息包括水上移動通信業務標識碼(Maritime Mobile Service Identiftion，MMSI)、船名、呼號和船舶尺寸等；動態信息包括經緯度坐標、協調世界時間(Coordinated Universal Time，UTC)、航跡向、速度、艏向和轉向率等。[2]借助船舶MMSI和時間信息，可對AIS數據進行分包處理，獲得船舶軌跡信息[15],1條軌跡由若干離散的AIS數據組成，見圖2。

圖2 AIS軌跡圖示例

1.2.1.1 方向

本文采用平均航向、航向最大值和航向最小值作為船舶軌跡特征等來反映軌跡的方向。不同類的船舶軌跡對應的航向會有顯著差異，尤其是內河上行和下行的船舶航向相差約180°。

1.2.1.2 線形

軌跡的線形是軌跡最直觀的特征，主要體現在軌跡的曲直上。順直的軌跡與曲折的軌跡的最大轉向率差異明顯；同時，彎曲的軌跡相比順直的軌跡，其航向方差要大很多。因此，本文選用最大轉向速率和航向方差作為軌跡特征，以區分不同的軌跡線形。

1.2.1.3 動態信息

不同的軌跡類代表不同的航路和不同的運動模式，不同航路的通航環境一般存在著差異，導致船舶在不同航路上航行時存在速度上的顯著差異，比如上行船舶與下行船舶受水流速度的影響，在對地速度上存在顯著差異。因此，選用平均速度、平均加速度和平均角速度作為軌跡特征。

對于1條包含若干AIS信息的船舶軌跡，對所有速度信息進行平均得到平均速度為

(5)

對所有航向信息進行平均得到平均航向，并求出最大航向值、最小航向值與航向值的方差為

Hmax=max{H1,H2,…,Hn}

(6)

Hmin=min{H1,H2,…,Hn}

(7)

(8)

(9)

將所有AIS信息按時間排序，并將時間與航向差分得到前后兩點的時間差和航向差，將航向差除以時間差得到轉向率，可得到最大轉向率和平均轉向率為

(10)

(11)

(12)

同理，將速度差分可得加速度。

am=(vm+1-vm)/(tm+1-tm)

(13)

(14)

1.2.2序列前向選擇算法

因船舶AIS軌跡的特征量較小，船舶軌跡分類算法采用一種啟發式搜索方法,即序列前向選擇算法。該算法適用于特征量較小的場合，是一種貪心算法。[16]以分類精度f為評價函數，Ωs為最優特征集合，Ω為所有特征集合，算法描述如下：

(1) 初始化Ωs為空集，則此時算法的分類精度fbest為占比最多的類的先驗概率max{P(yj)}。

(2) 計算fmax=max{f(Ωs∪{F})}，F∈(Ω-Ωs),F為某一特征。即選擇一個在非最優特征集合中能得到最大精度的特征加入Ωs。

(3) 若fmax≥fbest，且Ω-Ωs≠?,則令fbest=fmax轉步驟(2)，否則轉步驟(4)。

(4) 得到最優特征子集Ωs，在Ωs上構建船舶軌跡分類器。

1.3 連續數據的處理與加權

在AIS軌跡分類算法中，需計算各軌跡特征屬性的類條件概率估計值p(Xi|Y)；AIS軌跡分類算法所選特征屬性值均為連續值，不能直接估計出類條件概率。鑒于此，一般有2種處理方法：

1) 將連續值離散化[17]，但該方法中離散區間劃分的粒度控制難度較大，太細易導致某區間樣本太少而不能可靠估計p(Xi|Y)，太粗會使某些區間包含來自于不同類的樣本，影響分類精度。

2) 假設連續變量服從某種概率分布，采用樣本估計概率分布的參數，以類條件概率密度替代p(Xi|Y)。

本文采用第2種方法，結合高斯分布。對于每個類yi，屬性xi的條件概率密度為

(15)

樸素貝葉斯分類器除了假設各特征相互獨立以外，認為分類時各特征的重要程度相當；事實上，不同類別對不同特征的敏感性不同。為改進分類器的性能，可采用加權的方法[17-18]，提出一種針對連續特征值的加權方法，對于任一條軌跡X={x1,x2,…,xn}，其某個特征在類下服從正態分布N(uij,σij)，則計算貝葉斯后驗概率的每項P(Xi=xi|Y=yi)，定義加權系數wij為

(16)

式(16)中：當σij較大時，表明在該類別下，特征值取值比較分散，反之表明取值較為集中。當特征取值集中時，表示對于類Yi，特征Xi具有較強的規律性，因此可提高其權重。

加權后的樸素貝葉斯軌跡分類器定義為

(17)

2 試驗分析

2.1 試驗數據集

以長江與漢江交匯河段為研究區域，開展船舶軌跡分類算法的驗證研究。選取2017年5—7月的船舶AIS數據進行軌跡分類試驗，試驗原始數據中包含220多萬條AIS數據。以5—6月份的數據訓練分類器并測試準確率，以7月份的數據測試算法的分類效果。研究區域取左下角坐標(114.20 E，30.47 N)至右上角坐標(114.38 E，30.64 N)的矩形區域；分別定義長江航道上下游斷面為A和B，漢江斷面為C。因此，研究區域中存在船舶軌跡類1(A→B)、船舶軌跡類2(A→C)、船舶軌跡類3(B→A)、船舶軌跡類4(B→C)、船舶軌跡類5(C→A)和船舶軌跡類6(C→B)等6種類別軌跡。

經AIS數據經清洗和軌跡分離后，共得到7 095條船舶軌跡,其中5—6月份有4 826條，每條軌跡包含上百條到上千條AIS數據不等，通過繪圖觀察人工分類，構建原始數據集，分類結果見表1。

表1 人工軌跡分類

由表1可知:分布于長江主航道A與B之間的軌跡數量占絕大多數(約90.38%)，去往漢江(支流)C截面的船舶軌跡相對較少，數據集的類別嚴重失衡。為減小算法的泛化誤差、增強算法的泛化能力，采用欠采樣的方式對數據集進行平衡。以軌跡類5為基準，在其余各類中隨機采樣70條軌跡，總共420條軌跡構成樸素貝葉斯軌跡分類模型的數據集。因訓練集數量較少，為排除特殊情況，取10組平衡數據集計算結果的平均值作為最終結果。

試驗時采用交叉驗證的方式[19]，將420條軌跡分層隨機平均分為5組，每組各類別軌跡數量占比相當，依次以其中一組為測試集，其余4組為訓練集進行模型的訓練與測試，共5次。取每次的分類準確率的平均值作為整體的分類準確率，計算方法為

(18)

式(18)中:ACC為準確率;T為預測與實際相符的軌跡數量;E為預測與實際不相符的軌跡數量。

2.2 尋找最優特征子集

本文重點考慮8個軌跡特征,其編號為：

1) 平均速度；

2) 平均航向；

3) 平均加速度；

4) 平均轉向率；

5) 最大轉向率；

6) 航向方差；

7) 最大航向；

8) 最小航向。

按編號順序累加觀察算法的ACC變化，結果見表2。由表2可知:ACC不隨特征的累積而穩定提升。例如：取前4個特征時的ACC相比取前3個特征有所降低，說明初步選取的特征存在冗余，會對ACC產生負面影響，需尋找最優特征子集，以提高算法分類ACC。

表2 特征累積下的模型準確率 %

采用序列向前算法尋找最優特征子集，經計算,依次向最優特征子集中添加特征2)、特征6)、特征7)、特征8)、特征1)和特征5)，直至ACC達到99.05%；此后再添加，特征ACC不再提高。因此，最優特征子集包含平均航向、航向方差、最大航向、最小航向、平均速度和最大轉向率，而平均加速度和平均角速度均為冗余特征。計算結果見表3。

2.3 特征加權

為揭示特征加權對軌跡分類效果的影響，對比分析加權前后的船舶軌跡分類算法的ACC。在研究過程中，將數據集分為平衡數據集和非平衡數據集(原始數據集)，其結果對比見表4。

表3 尋找最優特征集合 %

表4 加權前后結果對比 %

由表4可知：基于特征加權的AIS軌跡分類算法準確率較高，而非平衡數據集效果略差。上述結果表明，對于平衡數據集，本文建立的加權方法有助于提高算法的ACC。此外，平衡數據集的分類準確率整體低于非平衡數據集的原因在于數據量的差距；在非平衡數據集下，特征加權后ACC會相對下降的原因在于未加權時部分數據量占比小的類會被錯誤地分到數據量占比大的類中，特征加權放大相應特征對相應類別的影響，引起數據量較少的類的分類ACC提高，而數據量較大的類ACC相對減小,導致整體ACC有所下降。

3 分類效果與對比

為進一步測試算法對船舶軌跡的分類效果，采用訓練好的分類器對研究區域7月份的船舶AIS數據進行分類。經數據清洗與軌跡分離之后，共得到2 274條待分類軌跡，采用加權的樸素貝葉斯軌跡分類算法對其進行分類，結果見圖3。

除類2、類4和類6存在少許分類錯誤的軌跡，絕大部分船舶軌跡分類正確，分類效果良好，如表4所示。采用未加權的樸素貝葉斯軌跡分類算法進行分類，結果見圖4。

由圖4可知：類1、類3、類5和類6無明顯錯誤，類4有少量錯誤，類2存在一定數量的分類錯誤。經驗證，采用加權的船舶軌跡分類算法在新的樣本上準確率約為98.96%，高于未加權算法結果(約98.24%)，說明本文所建船舶軌跡分類算法具有良好的泛化能力。

a)類1(A到B)

a)類1(A到B)

本文采用相同的數據集，與其他常用分類算法進行對比分析；試驗計算機條件為CPU i7-6700HQ 2.6 GHz、內存12 GB，對比各算法的分類準確率和處理速度，結果見表5。由表5可知：本文建立的改進樸素貝葉斯模型ACC最高，處理速度略低于未加權的樸素貝葉斯，相比其他方法優勢明顯。

表5 不同分類器對比結果

4 結束語

本文針對內河船舶軌跡分類算法開展研究,提出一種特征為連續值時的加權方式，構建加權的樸素貝葉斯軌跡分類模型，提高船舶軌跡分類ACC。試驗結果顯示：船舶軌跡算法分類ACC不隨特征數量的累積而單調遞增；最優特征集合為軌跡平均速度、平均航向、航向方差、最大轉向率、最大航向和最小航向；基于最優特征集合的分類算法ACC約為98.57%；基于最優特征集合的加權分類模型ACC約為99.05%；經加權的分類算法實際分類效果表現良好。

船速等運動特征可作為船舶軌跡分類的重要依據，基于樸素貝葉斯的船舶軌跡分類模型分類ACC達99%以上，可有效實現內河船舶軌跡分類，特征加權能有效提升算法分類的ACC和速度。該研究成果可為船舶異常軌跡識別、船舶航行風險分析等提供技術支撐。