基于最小二乘支持向量機的AIS數據修復方法

2019-01-08 03:38:10王永明劉興龍桑凌志

上海海事大學學報 2018年4期

王永明，劉興龍，桑凌志

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

0 引言

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

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

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

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

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

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

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

1 基礎理論與方法

1.1 時空軌跡相似度

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

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

(1)

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

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

Hausdorff距離主要描述的是兩組軌跡點之間的相似度，它是采用一條軌跡中每個軌跡點與另一條軌跡中軌跡點距離最小值中的最大值來表示的。設兩條船的軌跡分別用軌跡點集合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年代中期被提出來的一種分類學習機，其內涵是根據小樣本數據建立一種非線性的高維映射，從而回歸出一個超平面，進而實現數據的分類。LSSVM是SUYKENS等[18]提出的一種改進的SVM模型，它將傳統SVM中的不等式約束改為等式約束，采用最小二乘線性系統作為損失函數，代替傳統的SVM采用的二次規劃方法，將其轉化為求解線性方程組的問題。LSSVM方法提高了求解速度和收斂精度。

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

(3)

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

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

(4)

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

(5)

這將優化問題轉變為線性求解問題，即

(6)

(7)

2 AIS動態數據可靠性評估

2.1 數據丟失時間匹配

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

圖1AIS數據丟失時間匹配流程

2.2 完備AIS軌跡庫制定

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

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

a)經度和緯度

b)航速

c)航向

2.3 相似AIS數據查詢與檢索

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

圖3 軌跡粗匹配示意圖

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

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

2.4 AIS數據相似度評判

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

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

(8)

式中:Np和Nq分別表示軌跡p和q的節點數量。

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

3 基于LSSVM的AIS數據修復

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

圖4基于LSSVM的AIS數據修復步驟

圖5 PSO算法流程

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

基本粒子群算法的應用具體包括算法流程、算法的參數設置和算法的終止條件。PSO算法流程見圖5。

4 案例驗證

4.1 歷史軌跡庫制定

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

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

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

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

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

4.2 相似軌跡樣本搜尋

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

4.3 動態AIS數據修復

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

表1 快速檢索結果

表2 軌跡相似度匹配結果

圖7 相似樣本訓練和數據修復流程

4.3.1 樣本訓練

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

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

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

4.3.2 數據修復

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