基于GRU 自編碼器的船舶航線提取

任成杰，陳懷新，謝衛(wèi)

（1.電子科技大學 資源與環(huán)境學院,四川 成都 611731;2.中國電子科技集團公司第十研究所,四川 成都 610036）

隨著船舶自動識別系統(tǒng)(automatic identification system,AIS) 在船上的廣泛應用，船舶軌跡數據的獲取越來越容易，如何從這些海量的數據中挖掘出有價值的信息，對于研究船舶交通行為模式、分析船舶交通流特征具有重要的意義[1]。

在眾多軌跡分析任務中，航線提取可以從凌亂繁雜的軌跡中得到船舶運動的主要線路，是船舶軌跡異常檢測、位置預測等研究的基礎。目前，有關航線的研究主要存在于航線設計[2-5]和航線規(guī)劃[6-10]方面，有關航線提取方面的研究較少。船舶航線指特定海域內大量船舶航行軌跡反映出的航線簇的特征線[11]，Halpern 等[12]利用格網統(tǒng)計法，通過統(tǒng)計網格內船舶出現的頻次來反映船舶的分布，進一步判斷主要航線。Lin 等[13]對不同的軌跡進行比較，將相似的軌跡合并得到船舶航線。Wang 等[14]利用核密度方法對南海的主要航線進行了提取。具體而言，提取船舶航線可分為軌跡聚類和提取聚類典型軌跡兩個問題。

軌跡聚類旨在發(fā)現具有相似運動模式的軌跡簇，揭示運動目標的潛在特征[15]。傳統(tǒng)軌跡聚類方法在定義了軌跡相似度的基礎上，利用基于距離和基于密度的算法對軌跡進行聚類。Lee 等[16]首次將每條軌跡劃分為軌跡段，并利用基于密度的聚類算法對軌跡段進行聚類。Pallotta 等[17-19]利用增量DBSCAN 算法對AIS 船舶軌跡中的特征點進行聚類，并在次基礎上提取了船舶交通運動模式。Vries 等[20]將船舶軌跡看作時間序列，采用動態(tài)時間規(guī)整(dynamic time warping，DTW)和編輯距離(edit distance，ED)來計算軌跡的相似度，并且結合軌跡壓縮的方法，利用核k均值算法對船舶AIS 軌跡聚類。Wang 等[21]提出一種基于Hausdorff 距離和HDBSCAN 的船舶軌跡聚類方法，這種方法可以自適應地將船舶軌跡的形狀特征進行聚類，并具有良好的可擴展性。

聚類典型軌跡是指能代表每一類軌跡整體的長度、方向、位置和形狀的軌跡。Coelho 等[22]利用定義的投票函數從軌跡簇中選擇典型軌跡。Lee 等[16]將軌跡段視為向量并通過計算平均向量來得到代表軌跡。王加勝等[11]采用基于三角網的兩線中心線提取算法，將聚類中心線計算轉化為兩條中心線進行計算，通過迭代的方法得到最終的聚類中心線。

基于傳統(tǒng)軌跡聚類的方法雖然可以對一定時間和區(qū)域內的船舶軌跡進行聚類，但在定義不同長度軌跡間的距離度量時較為困難。而在提取典型軌跡時，傳統(tǒng)方法定義較復雜，且需要一定的后續(xù)處理才能得到最終的典型軌跡。針對以上問題，本文提出采用GRU 自編碼器（GRU-AE）進行AIS 數據的深度信息編碼，可將不同長度的軌跡編碼表示為統(tǒng)一格式的深度特征，結合DBSCAN算法，再利用聚類簇中心解碼反演進行船舶航線提取，從海量AIS 數據中挖掘船舶軌跡規(guī)律。

1 基于GRU-AE 的航線提取方法

船舶航線是指能代表眾多船舶軌跡在空間上的整體特征（長度、方向、位置和形狀）的特征線。利用AIS 數據挖掘的船舶航線提取流程如圖1 所示。

圖1 利用AIS 數據的船舶航線提取流程Fig.1 Ship route extraction process using AIS data

提取流程可分為兩個主要過程。其一是利用GRU 自編碼器提取船舶軌跡中的深度特征，該過程包含AIS 原始數據的預處理，以及GRU 自編碼器的構建與訓練。首先根據速度與時間閾值從原始AIS 數據中分離出合理的船舶軌跡，其次將船舶軌跡通過編碼器生成其深度特征，再通過解碼器生成解碼軌跡，根據解碼軌跡與原始船舶軌跡間的差異來調整GRU 自編碼的參數，使得解碼軌跡盡可能地接近原始船舶軌跡，由于此時可以從深度特征中完全還原出原始船舶軌跡，故認為此時提取的深度特征是合理的。其二是深度特征的聚類和船舶航線的生成，該過程利用DBSCAN算法對船舶軌跡的深度特征進行聚類，并將聚類后的類簇中心通過訓練后的解碼器解碼反生成船舶航線。

1.1 門控循環(huán)單元

門控循環(huán)單元(gate recurrent unit,GRU)是由Cho 等[23-24]在2014 年提出的一種特殊類型的循環(huán)神經網絡(recurrent neural networks,RNN)，它旨在解決標準RNN 中出現的梯度消失問題。GRU的功能類似于著名的LSTM 網絡，不同之處在于，GRU 中只存在兩個門，比LSTM 少一個門，因此GRU 中包含的參數更少，訓練速度更快，使用的內存更少。GRU 利用重置門和更新門來解決梯度消失問題，這些門能夠長時間保存信息，而不會在一段時間內丟失信息[25]。GRU 單元的圖形表示如圖2 所示。

圖2 門控循環(huán)單元(GRU)Fig.2 Gate recuurent unit (GRU)

更新門決定了有多少過去的信息應該被傳遞到之后的模型中：

式中：xt為t時刻的輸入；ht-1保存了t-1時刻的信息；xt、ht-1分別與權重矩陣Wz、Uz相乘并經過激活函數后得到更新門在t時刻的輸出zt。

GRU 利用重置門來決定有多少過去的信息需要被遺忘，其輸出表達式與更新門類似：

當前記憶內容利用重置門來存儲與過去相關的信息：

當前時間最終記憶內容會保留當前單元的信息并傳遞到下一個單元中：

1.2 GRU 自編碼器

本文利用GRU 自編碼器來重建預處理后的軌跡序列，并產生每條軌跡的固定長度的深度特征。自編碼器模型由兩個GRU 網絡組成，包括圖3 中左邊所展示的編碼器GRU 部分以及右邊所展示的解碼器GRU。

圖3 自編碼器結構Fig.3 Auto-encoder structure

該模型的輸入是軌跡序列 TRi={p1,p2,···,pT}，當最后的pT被處理后，編碼器的隱藏狀態(tài)h被用來作為整個軌跡序列的深度特征。

解碼器將h作為初始隱藏狀態(tài)，產生輸出q1，并進一步產生 (q2,q3,···,qT)，它的目標是重建輸入軌跡序列 TRi。通過最小化重建誤差，編碼器GRU 和解碼器GRU 被放在一起進行訓練，其中重建誤差由均方誤差產生：

固定長度的深度特征h是輸入軌跡序列 TRi的合理表示，因為利用解碼器可以從h中重建整個輸入軌跡序列。將深度特征作為DBSCAN 聚類算法的輸入，選擇歐氏距離作為距離度量方法，得到聚類結果。

1.3 航線提取

經過DBSCAN 聚類，得到不同的軌跡簇。對于某一個軌跡簇，取其中的核心對象集合為Ci，將對象集合的中心作為航線的深度特征：

2 實驗及結果分析

2.1 實驗一：利用模擬數據測試算法的合理性

在仿真數據中，基于3 條不同形狀的航線，包括直線型航線、曲線型航線及橢圓形航線，通過添加一定的噪聲，并且將軌跡的長度取為50～100的隨機值，以此生成30 條模擬軌跡，如圖4(a)所示，其中紅色曲線為預設航線，綠色曲線為合成軌跡。

圖4 合成軌跡與生成航線Fig.4 Synthetic trajectories and generated routes

本次實驗中將GRU 自編碼器的隱藏層大小設置為30，學習率設為0.000 1，迭代次數設為1 000。經過DBSCAN 算法聚類后，得到3 個軌跡聚類簇并生成相應的航線，如圖4(b)所示，其中3 種不同顏色的曲線代表3 個不同的軌跡簇，藍色曲線代表生成航線。對比生成航線與預設航線可以看出，本文算法所提取的航線與實際航線基本一致，且由于合成軌跡的長度并不相同，這說明本文算法適用于實際中不同長度的船舶運動軌跡聚類，免去了傳統(tǒng)軌跡聚類中定義不同長度軌跡間距離度量的步驟。

2.2 實驗二：采用實際數據驗證算法的效能

該實驗在真實數據集中測試本文算法，研究區(qū)域選擇美國波士頓港口附近海域。波士頓港是美國馬薩諸塞州波士頓的一座港口，位于波士頓灣之內，是馬薩諸塞州規(guī)模最大的港口，也是美國東海岸的主要港口之一。研究數據采用海洋能源管理局（BOEM）和美國國家海洋與大氣管理局（NOAA）提供的2018 年AIS 數據，如圖5 所示。

圖5 研究區(qū)域及研究數據Fig.5 Research area and data

2.2.1 軌跡預處理

AIS 數據中包含眾多與船舶運動相關的信息，包括船舶的水上移動業(yè)務標識(maritime mobile service identify,MMSI)、所處的經緯度、航向和航速等信息。考慮具有不同MMSI 標識的船舶目標集合O={o1,o2,···,oL}，對每個目標o，它的歷史AIS 數據按時間排序后形成序列So={p1,p2,···,pn} 。對于軌跡序列So，即使它是來自同一艘船的軌跡，也會有不同航次的軌跡的區(qū)別，而不同航次的軌跡應被認為是不同的軌跡。為區(qū)分不同航次的軌跡，利用時間和速度閾值對軌跡序列進行預處理，得到處理后的軌跡集合TRS={TR1,TR2,···,TRN}，由于后續(xù)將對軌跡中包含的空間信息進行處理，故保留各軌跡點的經緯度信息，即TRi={(lon1,lat1),(lon2,lat2),···,(lonm,latm)}。

對波士頓港口附近的AIS 數據進行預處理，其中時間閾值取為30 min，速度閾值取為0.5 kn，如圖6 所示，經過預處理后不同航次的軌跡被明顯地區(qū)分開來。

圖6 預處理前后的軌跡Fig.6 Trajectories before and after preprocessing

2.2.2 軌跡聚類及航線提取

預處理后一共形成918 條軌跡，將軌跡作為輸入。將自編碼器的隱藏層大小設置為100，學習率為0.000 1，迭代次數設為3 000。經過訓練后，918 條不同長度的軌跡被統(tǒng)一編碼為長度為100的深度表示，利用DBSCAN 算法對其進行聚類，經過反復實驗，將密度半徑設為0.8，密度閾值設為5，此時聚類效果最佳，去除不在主要路線上的噪聲軌跡后一共得到16 個軌跡簇，如圖7 所示。

圖7 軌跡聚類后形成的不同軌跡簇Fig.7 Different trajectory clusters after trajectory clustering

分析聚類后的16 個軌跡簇可知，該區(qū)域內船舶運動的起點和終點主要包括圖7 中A～G共7 個位置，其中A、B為進出目標區(qū)域的地點，C～G為不同城市。由于運動方向相反，運動形狀相似的軌跡簇被認為是不同的軌跡簇。例如圖7 中軌跡簇(1)和(2)，簇(1)由A點出發(fā)運動到B點，而簇(2)由B點出發(fā)運動到A點。軌跡簇(3)(4)、(5)(6)、(7)(8)、(9)(10)和(11)(12)同樣具有運動方向相反的特征。在16 個軌跡簇中，大部分簇內的軌跡具有相同且唯一的起點和終點，而對于簇(10)和(16)，它們存在兩個不同的起點，導致該現象的原因可能是AE (auto encoder)結構中的編碼器沒有很好地區(qū)分這兩種起點不同的軌跡，使得兩種軌跡的深度特征間距離相近，因而在聚類過程中被認為是同一類軌跡。

通過統(tǒng)計各個不同軌跡簇內的船舶類型可知，經過實驗區(qū)域且不做停留的軌跡簇(1)(2)中主要包括拖船和領航船，而起點和終點均在實驗區(qū)域內的軌跡簇(3)～(14)主要包括的是客船的軌跡。客船在城市C、D、E、F間航行，其中城市C、D之間的客船流量最大，且往返間具有兩條明顯不同的航線，見圖7 中軌跡簇(3)(4)(5)(6)。

由以上分析可知，聚類后各軌跡簇在軌跡形狀、方向和船舶類型等特征上各不相同，這說明利用船舶軌跡的深度表示對軌跡進行聚類具有較好的效果。對聚類后的每個軌跡簇，計算其在深度空間中的中心，并通過解碼器生成對應的航線，如圖8 所示。

圖8 航線提取Fig.8 Route extraction

圖8 中航線的寬度代表了通過該航線的船舶流量，其中航線(5)和(6)流量最大，其余航線流量相近。對比圖7 與圖8 可知，提取的航線在整體上較好地體現了各軌跡簇在空間上的長度、方向、位置和形狀等特征，這說明了航線的合理性。

2.2.3 實驗結果對比

本文方法與相關論文航線提取方法（Hausdorff[21]、DTW[20]、三角網[11]）進行對比分析，其處理結果如圖9 所示。

圖9 中基于Hausdorff 距離的聚類無法分辨出相同路徑上不同航向的軌跡，需進行一定的后處理；而利用三角網提取的航線均存在以下缺點，即起點或終點不明確、存在航線折返、航線不平滑等。

圖9 不同航線提取方法對比Fig.9 Comparison of different route extraction methods

對此，本文還提出航線評價的量化指標，即整體軌跡與航線間的平均距離：

式中：Davg為平均距離，Davg越小說明航線提取越準確DIS (DIS_Hausdorff/DIS_DTW)為軌跡相似性度量方法；Routej為與軌跡 TRi最近的航線。不同方法的對比結果如表1 所示，可以看出本文方法在兩種度量方法下的性能均優(yōu)于傳統(tǒng)方法。

表1 航線提取效果對比Table 1 Route-extraction effect comparison

3 結束語

本文提出了一種基于GRU 自編碼器的船舶航線提取方法，通過深度學習的GRU 自編碼器進行AIS 數據的深度特征信息提取。在實驗一中，基于合成數據集測試驗證了航線提取算法的有效性以及對不同長度軌跡的適應性；在實驗二中，采用波士頓港附近海域2018 年內的AIS 數據，利用時間和速度閾值對不同航次的軌跡進行分割與預處理，采用GRU 自編碼器將船舶軌跡編碼為固定長度的深度表示，并在深度空間中利用DBSCAN 算法對船舶軌跡進行聚類，共得到16 個軌跡簇，通過航線提取算法得到研究區(qū)域內的16 條航線，對比原始數據與所提取的航線，表明了本文方法可以有效地進行海量船舶航行數據挖掘，提取不同模式下船舶的軌跡航線。本文方法對比傳統(tǒng)航線提取方法具有精確提取和無需后處理的優(yōu)點，且同時可以提取出各航線的船舶流量和船舶類型等有價值的信息，為后續(xù)目標區(qū)域內的船舶路徑規(guī)劃、異常檢測和位置預測等研究與應用打下了基礎。