基于加權(quán)樸素貝葉斯的船舶軌跡分類算法

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

(1.武漢理工大學(xué) a.智能交通系統(tǒng)研究中心； b.能源與動(dòng)力工程學(xué)院；c.國(guó)家水運(yùn)安全工程技術(shù)研究中心,武漢 430063； 2.東南大學(xué) 交通學(xué)院,南京 211189)

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

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

本文以船舶AIS歷史數(shù)據(jù)為基礎(chǔ)，提出一種基于樸素貝葉斯算法的船舶軌跡分類方法，針對(duì)AIS軌跡分類場(chǎng)景，提出一種船舶軌跡特征組合，并對(duì)分類器進(jìn)行加權(quán)優(yōu)化，以提高分類效果。首先，通過(guò)AIS數(shù)據(jù)預(yù)處理提取軌跡特征；其次，選取最優(yōu)特征集合并訓(xùn)練分類器，實(shí)現(xiàn)AIS軌跡數(shù)據(jù)的自動(dòng)分類；最后，以長(zhǎng)江武漢河段為例，對(duì)軌跡分類算法的有效性進(jìn)行驗(yàn)證。

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

1.1 樸素貝葉斯

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

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

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

(1)

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

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

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)表明需要一部分已知類別的軌跡數(shù)據(jù)來(lái)訓(xùn)練分類器，統(tǒng)計(jì)得到各類別下各軌跡特征屬性的條件概率估計(jì)值p(Xi|Y)。根據(jù)上述假設(shè)，式(1)可寫為

(3)

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

(4)

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

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

1) 對(duì)AIS數(shù)據(jù)進(jìn)行清洗與分包，得到有效的船舶軌跡數(shù)據(jù)。

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

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

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

1.2 軌跡特征

AIS軌跡特征的提取主要分為初步選擇特征和尋找最優(yōu)特征子集2步。初步選擇特征是指根據(jù)AIS軌跡的特點(diǎn)，初步選擇一些能區(qū)分不同類別的特征。根據(jù)初步選擇的特征集合不一定能得到性能最好的分類器，可能會(huì)因冗余的特征項(xiàng)使分類器的精度降低，因此需進(jìn)一步篩選尋找最優(yōu)特征子集。

圖1 分類流程

1.2.1特征初步選擇

AIS船臺(tái)發(fā)送的報(bào)文中主要包含靜態(tài)信息和動(dòng)態(tài)信息。其中:靜態(tài)信息包括水上移動(dòng)通信業(yè)務(wù)標(biāo)識(shí)碼(Maritime Mobile Service Identiftion，MMSI)、船名、呼號(hào)和船舶尺寸等；動(dòng)態(tài)信息包括經(jīng)緯度坐標(biāo)、協(xié)調(diào)世界時(shí)間(Coordinated Universal Time，UTC)、航跡向、速度、艏向和轉(zhuǎn)向率等。[2]借助船舶MMSI和時(shí)間信息，可對(duì)AIS數(shù)據(jù)進(jìn)行分包處理，獲得船舶軌跡信息[15],1條軌跡由若干離散的AIS數(shù)據(jù)組成，見圖2。

圖2 AIS軌跡圖示例

1.2.1.1 方向

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

1.2.1.2 線形

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

1.2.1.3 動(dòng)態(tài)信息

不同的軌跡類代表不同的航路和不同的運(yùn)動(dòng)模式，不同航路的通航環(huán)境一般存在著差異，導(dǎo)致船舶在不同航路上航行時(shí)存在速度上的顯著差異，比如上行船舶與下行船舶受水流速度的影響，在對(duì)地速度上存在顯著差異。因此，選用平均速度、平均加速度和平均角速度作為軌跡特征。

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

(5)

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

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

(6)

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

(7)

(8)

(9)

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

(10)

(11)

(12)

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

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

(13)

(14)

1.2.2序列前向選擇算法

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

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

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

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

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

1.3 連續(xù)數(shù)據(jù)的處理與加權(quán)

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

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

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

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

(15)

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

(16)

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

加權(quán)后的樸素貝葉斯軌跡分類器定義為

(17)

2 試驗(yàn)分析

2.1 試驗(yàn)數(shù)據(jù)集

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

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

表1 人工軌跡分類

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

試驗(yàn)時(shí)采用交叉驗(yàn)證的方式[19]，將420條軌跡分層隨機(jī)平均分為5組，每組各類別軌跡數(shù)量占比相當(dāng)，依次以其中一組為測(cè)試集，其余4組為訓(xùn)練集進(jìn)行模型的訓(xùn)練與測(cè)試，共5次。取每次的分類準(zhǔn)確率的平均值作為整體的分類準(zhǔn)確率，計(jì)算方法為

(18)

式(18)中:ACC為準(zhǔn)確率;T為預(yù)測(cè)與實(shí)際相符的軌跡數(shù)量;E為預(yù)測(cè)與實(shí)際不相符的軌跡數(shù)量。

2.2 尋找最優(yōu)特征子集

本文重點(diǎn)考慮8個(gè)軌跡特征,其編號(hào)為：

1) 平均速度；

2) 平均航向；

3) 平均加速度；

4) 平均轉(zhuǎn)向率；

5) 最大轉(zhuǎn)向率；

6) 航向方差；

7) 最大航向；

8) 最小航向。

按編號(hào)順序累加觀察算法的ACC變化，結(jié)果見表2。由表2可知:ACC不隨特征的累積而穩(wěn)定提升。例如：取前4個(gè)特征時(shí)的ACC相比取前3個(gè)特征有所降低，說(shuō)明初步選取的特征存在冗余，會(huì)對(duì)ACC產(chǎn)生負(fù)面影響，需尋找最優(yōu)特征子集，以提高算法分類ACC。

表2 特征累積下的模型準(zhǔn)確率 %

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

2.3 特征加權(quán)

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

表3 尋找最優(yōu)特征集合 %

表4 加權(quán)前后結(jié)果對(duì)比 %

由表4可知：基于特征加權(quán)的AIS軌跡分類算法準(zhǔn)確率較高，而非平衡數(shù)據(jù)集效果略差。上述結(jié)果表明，對(duì)于平衡數(shù)據(jù)集，本文建立的加權(quán)方法有助于提高算法的ACC。此外，平衡數(shù)據(jù)集的分類準(zhǔn)確率整體低于非平衡數(shù)據(jù)集的原因在于數(shù)據(jù)量的差距；在非平衡數(shù)據(jù)集下，特征加權(quán)后ACC會(huì)相對(duì)下降的原因在于未加權(quán)時(shí)部分?jǐn)?shù)據(jù)量占比小的類會(huì)被錯(cuò)誤地分到數(shù)據(jù)量占比大的類中，特征加權(quán)放大相應(yīng)特征對(duì)相應(yīng)類別的影響，引起數(shù)據(jù)量較少的類的分類ACC提高，而數(shù)據(jù)量較大的類ACC相對(duì)減小,導(dǎo)致整體ACC有所下降。

3 分類效果與對(duì)比

為進(jìn)一步測(cè)試算法對(duì)船舶軌跡的分類效果，采用訓(xùn)練好的分類器對(duì)研究區(qū)域7月份的船舶AIS數(shù)據(jù)進(jìn)行分類。經(jīng)數(shù)據(jù)清洗與軌跡分離之后，共得到2 274條待分類軌跡，采用加權(quán)的樸素貝葉斯軌跡分類算法對(duì)其進(jìn)行分類，結(jié)果見圖3。

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

由圖4可知：類1、類3、類5和類6無(wú)明顯錯(cuò)誤，類4有少量錯(cuò)誤，類2存在一定數(shù)量的分類錯(cuò)誤。經(jīng)驗(yàn)證，采用加權(quán)的船舶軌跡分類算法在新的樣本上準(zhǔn)確率約為98.96%，高于未加權(quán)算法結(jié)果(約98.24%)，說(shuō)明本文所建船舶軌跡分類算法具有良好的泛化能力。

a)類1(A到B)

a)類1(A到B)

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

表5 不同分類器對(duì)比結(jié)果

4 結(jié)束語(yǔ)

本文針對(duì)內(nèi)河船舶軌跡分類算法開展研究,提出一種特征為連續(xù)值時(shí)的加權(quán)方式，構(gòu)建加權(quán)的樸素貝葉斯軌跡分類模型，提高船舶軌跡分類ACC。試驗(yàn)結(jié)果顯示：船舶軌跡算法分類ACC不隨特征數(shù)量的累積而單調(diào)遞增；最優(yōu)特征集合為軌跡平均速度、平均航向、航向方差、最大轉(zhuǎn)向率、最大航向和最小航向；基于最優(yōu)特征集合的分類算法ACC約為98.57%；基于最優(yōu)特征集合的加權(quán)分類模型ACC約為99.05%；經(jīng)加權(quán)的分類算法實(shí)際分類效果表現(xiàn)良好。

船速等運(yùn)動(dòng)特征可作為船舶軌跡分類的重要依據(jù)，基于樸素貝葉斯的船舶軌跡分類模型分類ACC達(dá)99%以上，可有效實(shí)現(xiàn)內(nèi)河船舶軌跡分類，特征加權(quán)能有效提升算法分類的ACC和速度。該研究成果可為船舶異常軌跡識(shí)別、船舶航行風(fēng)險(xiǎn)分析等提供技術(shù)支撐。