基于最小二乘支持向量機的AIS數(shù)據(jù)修復(fù)方法

王永明，劉興龍，桑凌志

(1.大連海事大學(xué)航海學(xué)院，遼寧 大連 116026；2.閩江學(xué)院物理與電子信息工程學(xué)院，福州 350108；3.中國交通通信信息中心交通安全應(yīng)急信息技術(shù)國家工程實驗室，北京 100011)

0 引 言

我國是世界主要航運大國，航運的安全有序?qū)揖哂兄匾膽?zhàn)略意義。水上交通安全是航運發(fā)展永恒的主題，加強水上交通管理的信息化、智能化是維護水上交通安全的重要方式。在水上智能交通運輸體系中，船舶時空軌跡信息的感知和處理是整個體系的核心。傳統(tǒng)船舶軌跡數(shù)據(jù)的獲取方式非常有限，主要是依靠航海日志、船舶進出港報告和海事雷達回波信號等，而且獲取成本高、樣本少、時間跨度短，難以長時間地觀測和記錄大量船舶在海上的行駛過程。

自2002年《國際海上人命安全公約》(SOLAS公約)強制推行船舶自動識別系統(tǒng)(automatic identification system,AIS)以來，AIS受到了全球航運界的廣泛關(guān)注。AIS通過甚高頻(VHF)將船舶靜態(tài)信息和動態(tài)信息廣播至附近水域的他船和岸基，使船舶之間可進行相互協(xié)調(diào),同時使海事部門能夠?qū)Υ斑M行監(jiān)控和管理，提高了船舶通行能力和安全保障能力。[1]AIS數(shù)據(jù)在航道通過能力評估、船舶交通流分析[2-3]、水上交通安全評價[4-6]等方面具有廣泛的應(yīng)用。

船舶靜態(tài)信息指船舶MMSI號、船名、船舶類型、船寬、船長等信息，在一般情況下不允許修改。船舶動態(tài)信息指船舶航行位置(一般用船舶的經(jīng)緯度坐標表示)、航速、航向(包括對地航向、真航向)等，這類數(shù)據(jù)大多由設(shè)備獲取，受人的因素影響較小。當AIS設(shè)備未與羅經(jīng)連接或舶舶位置數(shù)據(jù)轉(zhuǎn)換信號出現(xiàn)較大誤差時，發(fā)送的AIS動態(tài)數(shù)據(jù)會出錯。動態(tài)數(shù)據(jù)的發(fā)送也可能受到干擾，導(dǎo)致數(shù)據(jù)異常。BALDAUF等[7]對實地AIS數(shù)據(jù)發(fā)送時間間隔和動態(tài)數(shù)據(jù)可靠性進行了調(diào)查研究，發(fā)現(xiàn)大量AIS數(shù)據(jù)不符合技術(shù)規(guī)范。常會振等[8-9]等通過統(tǒng)計分析發(fā)現(xiàn),大量AIS數(shù)據(jù)不符合IMO規(guī)范。

基于上述原因，對AIS數(shù)據(jù)進行可靠性評估和錯誤數(shù)據(jù)識別方法研究具有重要意義。國內(nèi)外已經(jīng)開展了一些研究：吳建華等[10]對錯誤致因進行分類并據(jù)此對異常軌跡進行分類，分別提出了各類異常數(shù)據(jù)自動檢測依據(jù)。ZHANG等[11]、劉磊等[12]和SANG等[13]通過構(gòu)建AIS異常數(shù)據(jù)識別規(guī)則、設(shè)置數(shù)據(jù)閾值，將異常軌跡點或異常航速等數(shù)據(jù)刪除。衛(wèi)桂榮等[14]提出了MMSI校驗碼、填充位和校驗碼的綜合檢測，靜態(tài)信息與動態(tài)信息匹配校驗，以及異常點數(shù)據(jù)檢測等數(shù)據(jù)檢測方法，以減少AIS數(shù)據(jù)庫中的異常數(shù)據(jù)?？傊?，AIS錯誤數(shù)據(jù)識別主要依靠的仍是設(shè)置閾值，缺乏有效的評估并修復(fù)數(shù)據(jù)的模型。

以往主要使用數(shù)據(jù)插值方法對AIS軌跡數(shù)據(jù)進行修復(fù)：吳建華等[10]和田利芹等[15]均采用三次樣條插值修復(fù)數(shù)據(jù)，取得了一定的效果；劉磊等[12]采用分段三次Hermite插值修復(fù)數(shù)據(jù)；鑒于AIS數(shù)據(jù)標準時間間隔的差異性，NGUYEN等[16]首先對時間序列進行特征識別，繼而采用分段線性插值或分段三次Hermite插值修復(fù)數(shù)據(jù),該方法對一類AIS數(shù)據(jù)具有自適應(yīng)修復(fù)能力;SANG等[17]分別采用分段線性插值、分段三次樣條插值和分段三次插值對船舶軌跡進行了還原，發(fā)現(xiàn)分段三次樣條插值的軌跡還原精度最高。

AIS作為重要的水上交通信息感知工具，在海事監(jiān)管和船舶避碰方面有著極其重要的作用。然而，當前的AIS數(shù)據(jù)由于存在大量錯誤和缺失，尚不滿足船舶避碰決策和海事監(jiān)管的要求。在基于AIS數(shù)據(jù)的船舶時空軌跡修復(fù)方面，目前基于插值的AIS數(shù)據(jù)修復(fù)方法只考慮AIS數(shù)據(jù)中的船舶位置信息，故需要引入AIS數(shù)據(jù)中的航速和航向信息以提高軌跡還原的精度，同時修復(fù)AIS數(shù)據(jù)中的航速和航向信息。

本文首先解決AIS動態(tài)數(shù)據(jù)發(fā)送周期的不同步問題，通過時間匹配解決模型的時間參數(shù)輸入問題，然后利用AIS歷史數(shù)據(jù)庫中的相似軌跡建立船舶軌跡回歸模型，最后基于最小二乘支持向量機(least squares support vector machine,LSSVM)對船舶位置、航速、航向等分別進行訓(xùn)練，通過案例實現(xiàn)對AIS動態(tài)數(shù)據(jù)的有效修復(fù)。本方法可以有效幫助航程較遠船舶AIS軌跡數(shù)據(jù)的還原，進而幫助水上交通主管部門準確獲取船舶航行軌跡、船舶行為、避碰決策等相關(guān)信息，推進現(xiàn)有各類信息化系統(tǒng)的使用，為海事大數(shù)據(jù)的應(yīng)用、智慧海事的發(fā)展提供良好的AIS數(shù)據(jù)基礎(chǔ)。

1 基礎(chǔ)理論與方法

1.1 時空軌跡相似度

船舶時空軌跡相似度反映的是兩艘船空間運動趨勢的一致性和軌跡曲線的貼近程度。評估船舶時空軌跡的相似度并不是根據(jù)一定準則給兩條軌跡的相似程度“評分”，而是對一條指定的船舶軌跡，從歷史船舶軌跡數(shù)據(jù)庫中找出一條與其趨勢最一致的軌跡曲線。對于一條指定的軌跡Trj，給出一個包含若干條軌跡的軌跡數(shù)據(jù)庫T，從T中返回一條軌跡T′∈T，使得

d(T′,Trj)≤d(X,Trj), ?X∈T

(1)

式中，d(·)為兩條軌跡間的距離度量函數(shù)。

可見，在查詢相似軌跡時，度量軌跡相似度的核心是距離度量函數(shù)。AIS數(shù)據(jù)發(fā)送周期隨船舶運動狀態(tài)而變化，導(dǎo)致不同船舶的軌跡點數(shù)且不同，因此船舶運動軌跡相似度的衡量，是不同軌跡點數(shù)目下軌跡間的距離度量。兩條軌跡之間的距離通常由軌跡點之間距離的聚合來度量。Hausdorff距離是常用的能夠處理軌跡點數(shù)目不等情形下軌跡間距離度量的方法，具有計算復(fù)雜度相對較小的優(yōu)點。

Hausdorff距離主要描述的是兩組軌跡點之間的相似度，它是采用一條軌跡中每個軌跡點與另一條軌跡中軌跡點距離最小值中的最大值來表示的。設(shè)兩條船的軌跡分別用軌跡點集合A(a∈A)和集合B(b∈B)表示，則兩條軌跡的Hausdorff距離計算式為

H(A,B)=max(h(A,B),h(B,A))

(2)

式(2)是兩條軌跡間的雙向Hausdorff距離,其中：

從式(2)可以看出，兩條軌跡間的雙向Hausdorff距離H(A,B)是兩條軌跡間的單向Hausdorff距離h(A,B)和h(B,A)中的較大值，它描述兩條軌跡之間的最大不匹配度。

1.2 LSSVM

支持向量機(support vector machine，SVM)是20世紀90年代中期被提出來的一種分類學(xué)習(xí)機，其內(nèi)涵是根據(jù)小樣本數(shù)據(jù)建立一種非線性的高維映射，從而回歸出一個超平面，進而實現(xiàn)數(shù)據(jù)的分類。LSSVM是SUYKENS等[18]提出的一種改進的SVM模型，它將傳統(tǒng)SVM中的不等式約束改為等式約束，采用最小二乘線性系統(tǒng)作為損失函數(shù)，代替?zhèn)鹘y(tǒng)的SVM采用的二次規(guī)劃方法，將其轉(zhuǎn)化為求解線性方程組的問題。LSSVM方法提高了求解速度和收斂精度。

在修復(fù)船舶軌跡時，可以把經(jīng)度、緯度、速度和航向均當作一維時間序列。假設(shè)有N條相似軌跡樣本集合{xk,yk,vk,αk}作為訓(xùn)練樣本集，其中k=1,2,…,N,x、y、v、α分別代表軌跡數(shù)據(jù)中的經(jīng)度、緯度、速度、航向。每個軌跡樣本包含4個一維向量，對應(yīng)輸出4個預(yù)測值。根據(jù)統(tǒng)計學(xué)理論，船舶軌跡回歸預(yù)測優(yōu)化問題可描述為

(3)

式中:φ(·)為核空間映射函數(shù)；ω∈RN為權(quán)矢量；ek∈R為誤差變量;e=(e1,e2,…,eN)T；c為偏差量；γ為正則化參數(shù)。核函數(shù)φ(·)可以將船舶軌跡數(shù)據(jù)原始序列樣本映射成為高維特征空間中的一個向量，從而解決線性不可分的問題。一般用拉格朗日法求解這個優(yōu)化問題：

Γ(ω,c,e,α)=JP(ω,e)-

(4)

其中：αk為拉格朗日乘子,αk∈R,k=1,2,…,N;α=(α1,α2,…,αN)T。根據(jù)KKT條件可得到

(5)

這將優(yōu)化問題轉(zhuǎn)變?yōu)榫€性求解問題，即

(6)

(7)

2 AIS動態(tài)數(shù)據(jù)可靠性評估

2.1 數(shù)據(jù)丟失時間匹配

AIS動態(tài)信息的發(fā)送周期與船舶的航行動態(tài)相關(guān)。高航速和轉(zhuǎn)向都會導(dǎo)致AIS動態(tài)信息發(fā)送時間間隔縮短。根據(jù)實際航行情況，一般船舶的AIS船臺動態(tài)信息報文發(fā)送周期主要為10 s和30 s[19]。然而，現(xiàn)實中存在很多不符合規(guī)范的AIS船臺，如存在大量周期為15 s的AIS船臺。因此，需要對周期不符合規(guī)范的AIS船臺數(shù)據(jù)進行處理，使它們與常見周期匹配。本次匹配周期選擇為3 s，數(shù)據(jù)明顯超出此周期才能判定為數(shù)據(jù)丟失。具體的丟失時間匹配流程見圖1。

圖1AIS數(shù)據(jù)丟失時間匹配流程

2.2 完備AIS軌跡庫制定

采用分段三次Hermite插值可以對3個連續(xù)軌跡點以內(nèi)的AIS數(shù)據(jù)進行高精度修復(fù)，因此首先需要對短距離(3個連續(xù)軌跡點以內(nèi))的AIS數(shù)據(jù)進行修復(fù)，得到完備的AIS軌跡數(shù)據(jù)庫,再對長距離的AIS動態(tài)數(shù)據(jù)，采用相似軌跡回歸預(yù)測的方法進行修復(fù)。

以長江武漢段為例，原始AIS數(shù)據(jù)經(jīng)過數(shù)據(jù)清洗和甄別之后，會出現(xiàn)大量的軌跡點空缺。當前后兩條數(shù)據(jù)的時間差大于90 s時，該條船舶軌跡會被截斷，形成兩條單獨的軌跡。如果所有的船舶軌跡連續(xù)丟失點數(shù)量均少于3個點，則可以采用分段三次Hermite插值予以修復(fù)，形成完備的AIS軌跡歷史數(shù)據(jù)庫。選取2015年6月2日中午11:04至11:15某船(MMSI為413940407)的AIS動態(tài)數(shù)據(jù),采用分段三次Hermite插值對該船的經(jīng)度、緯度、航速和航向的修復(fù)結(jié)果見圖2。由圖2可見，采用分段三次Hermite插值能夠有效修復(fù)短距離的AIS數(shù)據(jù)，形成完備的AIS軌跡數(shù)據(jù)庫。

a)經(jīng)度和緯度

b)航速

c)航向

2.3 相似AIS數(shù)據(jù)查詢與檢索

船舶軌跡數(shù)據(jù)具有時空和大數(shù)據(jù)特征(即數(shù)據(jù)體量巨大)，且軌跡點序列在時空上并非嚴格匹配對齊。為解決搜索大數(shù)據(jù)樣本效率低的問題，本文提出一種兩層匹配方法。若使用該方法時出現(xiàn)無法匹配的情況，則需要進一步擴大AIS數(shù)據(jù)搜索的時間范圍。

圖3 軌跡粗匹配示意圖

(1)粗匹配。以序列初始坐標值起始點(X,Y)為中心，200 m為半徑，由近至遠搜索軌跡點，若搜索到的點處于待匹配軌跡集內(nèi)，則將該點納入備選點，同時將該點軌跡納入粗匹配軌跡集?？紤]到內(nèi)河船舶航速通常不超過10 kn，在AIS數(shù)據(jù)發(fā)送周期(30 s)內(nèi)船舶運動距離不超過155 m，以及GPS的漂移等因素，以200 m作為半徑可以保證相近軌跡點被選中。圖3中，軌跡1為樣本軌跡，以200 m為搜索半徑，軌跡3中存在一個點處于搜索范圍內(nèi)，因此將軌跡3選中。為提高算法效率，設(shè)定粗匹配搜索結(jié)束的兩個終止條件為：①備選點達到50個；② 200 m內(nèi)沒有其他待匹配點。

(2)細匹配。在粗匹配軌跡集Tx={T1,T2,…,Tn}中，對每條軌跡Ti進行跟蹤搜索，直到該條軌跡中存在點滿足如下條件：O(Ni,Ne)

2.4 AIS數(shù)據(jù)相似度評判

船舶航速的不同，在一個AIS動態(tài)報文發(fā)送周期內(nèi)，船舶的航程也不同，導(dǎo)致軌跡點集的疏密程度不同，使得待匹配序列點與模板點無法實現(xiàn)精確對齊。針對不匹配的兩個AIS序列集，本文采用Hausdorff距離作為其相似度度量空間。設(shè)兩條軌跡相似度可表示為S(p,q)，其定義為

S(p,q)=H(p,q)+|Np-Nq|

(8)

式中:Np和Nq分別表示軌跡p和q的節(jié)點數(shù)量。

船舶軌跡信息中，最能表征船舶運動信息的特征即為航向特征和航速特征?；贖ausdorff距離的相似度可以表征船舶在航向特征上的相似度。

3 基于LSSVM的AIS數(shù)據(jù)修復(fù)

船舶在航道中的行為通常隱藏著固定的模式，這種行為模式實際上是歷史AIS數(shù)據(jù)和當前AIS數(shù)據(jù)都具有的一種函數(shù)關(guān)系。基于LSSVM的AIS數(shù)據(jù)修復(fù)步驟見圖4。LSSVM中核函數(shù)是關(guān)鍵要素。核函數(shù)有很多種，徑向基函數(shù)(radial basis function，RBF)是最為常用的，對不同大小的樣本和不同的維度都具有很好的適應(yīng)性。本文選定RBF作為模型的核函數(shù)。

圖4基于LSSVM的AIS數(shù)據(jù)修復(fù)步驟

圖5 PSO算法流程

基于RBF的LSSVM回歸模型的兩個超參數(shù)(懲罰系數(shù)和核函數(shù)寬度)決定船舶軌跡數(shù)據(jù)回歸中LSSVM的泛化能力。隨著智能優(yōu)化算法的發(fā)展，粒子群算法、蟻群算法、遺傳算法等被用于求取LSSVM模型參數(shù)，其中粒子群算法以其編程簡單、搜尋速度快的優(yōu)點，成為應(yīng)用最廣的參數(shù)確定算法。本文采用粒子群優(yōu)化(particle swarm optimization，PSO)算法得到LSSVM回歸模型的兩個超參數(shù)值。

基本粒子群算法的應(yīng)用具體包括算法流程、算法的參數(shù)設(shè)置和算法的終止條件。PSO算法流程見圖5。

4 案例驗證

4.1 歷史軌跡庫制定

為驗證本文提出方法的有效性，在長江中游的武漢段開展驗證試驗。從寶船網(wǎng)取得2015年6月1日至8月31日3 001萬余個原始AIS數(shù)據(jù)。地域范圍為東經(jīng)114.21°至114.56°，北緯30.48°至30.70°，河段長度大約為30 km。

將獲取的原始AIS數(shù)據(jù)列表后，制定分段規(guī)則：(1)對MMSI進行排序，如果前后MMSI不一樣，則確定前后軌跡為不同船舶的軌跡。(2)對于每艘船的AIS軌跡數(shù)據(jù)，根據(jù)時間順序排序，獲取AIS時序數(shù)列。對于AIS船臺，信息發(fā)送周期以30 s居多，如果前后軌跡的時間間隔大于90 s，則確定前后軌跡為不同船舶的軌跡。

首先對AIS數(shù)據(jù)根據(jù)MMSI進行排序操作，共分離得到8 520條船舶軌跡，其中上水船軌跡4 000條，下水船軌跡4 520條。根據(jù)UTC時間對軌跡數(shù)據(jù)排序，當前后數(shù)據(jù)的時間差大于90 s時，則認為出現(xiàn)長距離的數(shù)據(jù)丟失，確定前后軌跡為不同船的軌跡。分離后的時間間隔小于90 s的子軌跡共有18 520條。經(jīng)過清洗后的軌跡數(shù)據(jù)見圖6，淺色點為下行船的軌跡，深色點為上行船的軌跡。

圖6 長江武漢段水域船舶軌跡庫

清除錯誤的AIS數(shù)據(jù)后，需要重新計算時間差，將時間間隔大于90 s的軌跡分離為兩條單獨的子軌跡。針對少量缺失的AIS軌跡，采用分段三次Hermite插值進行初始修復(fù)，獲取完備AIS軌跡庫。

4.2 相似軌跡樣本搜尋

在已建立好的AIS軌跡數(shù)據(jù)庫中，選取一條軌跡數(shù)據(jù)進行相似軌跡樣本搜尋。選擇長江武漢段天興洲下游航道中間部分為起始點，一條下行船軌跡為目標軌跡，進行軌跡庫快速檢索。共得到14條待匹配軌跡，見表1。在檢索結(jié)果集中，使用第2.4節(jié)的方法進行計算，結(jié)果見表2。根據(jù)計算結(jié)果，第8條軌跡為匹配結(jié)果。

4.3 動態(tài)AIS數(shù)據(jù)修復(fù)

圖7為AIS動態(tài)數(shù)據(jù)修復(fù)流程。在預(yù)報過程中，每修復(fù)一個點的數(shù)據(jù)，就將該數(shù)據(jù)加入LSSVM模型輸入中，并去除最后一個舊數(shù)據(jù)點，以構(gòu)成新的模型輸入，進行循環(huán)預(yù)報，直至完成全部AIS數(shù)據(jù)的修復(fù)工作。n為所構(gòu)造的相似軌跡樣本的長度，m為自相關(guān)時間序列長度，Yt為t時刻所預(yù)報的值。因此，AIS動態(tài)數(shù)據(jù)修復(fù)分為相似樣本訓(xùn)練、數(shù)據(jù)修復(fù)兩個步驟。

表1 快速檢索結(jié)果

表2 軌跡相似度匹配結(jié)果

圖7 相似樣本訓(xùn)練和數(shù)據(jù)修復(fù)流程

4.3.1 樣本訓(xùn)練

長距離AIS數(shù)據(jù)的修復(fù)準確程度由兩方面的因素決定:一方面是相似樣本與待修復(fù)軌跡的相似程度;另一方面是LSSVM方法對相似樣本的建模精度。使用PSO算法優(yōu)化后的LSSVM方法對相似樣本進行建模(記為PSO-LSSVM模型)，當擬合精度達到要求后，進行缺失數(shù)據(jù)的預(yù)報。由于AIS數(shù)據(jù)樣本量較大，采用實時性好的全局PSO算法進行優(yōu)化。試驗對比分為兩組:一組是優(yōu)化前后的LSSVM方法對相似樣本建模精度的對比;另一組是優(yōu)化后LSSVM方法與插值法對丟失數(shù)據(jù)修復(fù)的對比。共有4條軌跡及其相似軌跡被選中作為驗證。

根據(jù)訓(xùn)練模型預(yù)報的擬合程度來評價LSSVM方法對相似樣本的建模精度，選取均方根誤差作為擬合程度的目標函數(shù)。

由上述相似樣本所訓(xùn)練的模型(PSO-LSSVM模型)可以直接進行待修復(fù)軌跡的預(yù)報，經(jīng)度、緯度、航速、航向的修復(fù)模型參數(shù)見表3。

4.3.2 數(shù)據(jù)修復(fù)

訓(xùn)練完P(guān)SO-LSSVM模型參數(shù)后，即可進行該航段長距離AIS數(shù)據(jù)的修復(fù)。由于實際修復(fù)時待修復(fù)樣本數(shù)據(jù)不可知，使用一組相似樣本中的一條軌跡數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，另一條作為假設(shè)待修復(fù)數(shù)據(jù)。分別利用分段三次Hermite插值、LSSVM、PSO-LSSVM方法對數(shù)據(jù)進行修復(fù)，結(jié)果對比見表3，修復(fù)效果見圖8。從表3可以得出，對于選定的4組數(shù)據(jù)樣本，在船舶AIS數(shù)據(jù)的經(jīng)度、緯度、航速、航向數(shù)據(jù)修復(fù)中，采用PSO算法優(yōu)化后的LSSVM修復(fù)誤差要遠小于未優(yōu)化的LSSVM和傳統(tǒng)的分段三次Hermite插值的修復(fù)誤差。

表3 PSO-LSSVM模型參數(shù)及3種方法的修復(fù)誤差對比

a)第1組的經(jīng)度、緯度

b)第2組的經(jīng)度、緯度

c)第3組的經(jīng)度、緯度

d)第4組的經(jīng)度、緯度

e)第1組的航速

f)第2組的航速

g)第3組的航速

h)第4組的航速

i)第1組的航向

j)第2組的航向

k)第3組的航向

l)第4組的航向

圖84組數(shù)據(jù)的修復(fù)結(jié)果

5 結(jié) 論

(1)AIS在海事監(jiān)管和船舶避碰方面有著極其重要的作用。由于AIS數(shù)據(jù)存在大量錯誤和缺失，當前AIS數(shù)據(jù)質(zhì)量尚不能滿足船舶避碰決策和海事監(jiān)管的要求。

(2)通過匹配AIS數(shù)據(jù)丟失時間，制定完備AIS數(shù)據(jù)庫；采用改進的Hausdorff距離計算公式，融合了軌跡空間相似度和船舶航行速度相似度，為AIS數(shù)據(jù)修復(fù)提供數(shù)據(jù)基礎(chǔ)。

(3)選取長江武漢段進行驗證。采用相似軌跡作為LSSVM方法的輸入樣本，通過數(shù)據(jù)訓(xùn)練得到回歸模型，結(jié)果顯示本文提出的PSO-LSSVM方法與其他方法相比，能夠準確地還原AIS數(shù)據(jù)。

(4)研究結(jié)果有助于改善AIS數(shù)據(jù)連續(xù)性差、完整性不足的問題,通過提高AIS數(shù)據(jù)質(zhì)量，進一步實現(xiàn)對船舶運動規(guī)律等的有效分析，推進現(xiàn)有各類信息化系統(tǒng)的使用，為海事大數(shù)據(jù)的應(yīng)用、智慧海事的發(fā)展提供良好的AIS數(shù)據(jù)基礎(chǔ)。