采用編碼降維及DTW算法改進的船舶航跡聚類

曹偉，劉亞帥，管志強

(南京船舶雷達研究所，江蘇 南京 211106)

0 引言

在船舶航跡異常檢測研究中，部分異常船舶會偽裝在正常航道中航行，從航跡位置信息無法檢測該類異常，需要通過對這類異常船舶的異常機動進行檢測來檢測異常。而檢測這種異常機動，需要首先提取正常船舶航跡在時間維度上的各點的航行狀態，然后在時間維度上對比檢測。這種時間維度上的航行狀態特性就是航跡時序特性。

由于傳統船舶航道聚類多基于密度聚類算法，例如Pallotta G等人[1]采用DBSCAN (density-based spatial clustering of applications with noise)算法實現航道聚類，這些算法只能挖掘出航道的位置信息，無法提取船舶航跡的時序特性。所以為了提取出船舶航跡的時序特性，本文采用時間序列聚類的方法對航跡進行聚類。時間序列聚類算法的關鍵點在于時間序列的相似性度量。由于船舶航跡時間序列是不等長的，為了度量該類時間序列，本文采用了Berndt等人[2-3]于1994年提出了DTW算法。

雖然DTW算法可以實現不等長時間序列的度量，但是在海量船舶航跡時間序列上使用DTW算法存在2個問題：①DTW算法主要適用于一元時間序列(univariate time series,UTS)[4]，對于多元時間序列(multivariate time series,MTS)[4]只有屬性之間相關性較低時才能有效度量，否則很容易失去屬性之間的相關性。而船舶航跡時間序列中的經緯度相關性很高，無法有效應用DTW算法實現相似性度量;②DTW時間復雜度高達O(n2)，雖然近年來不少學者提出了許多改進方法，比如LB_Keogh下界函數[5]，微分動態彎曲距離(derived dynamic time waping,DDTW)[6-7]，加權動態彎曲距離(weighted dynamic time warping,WDTW)以及加權微分動態彎曲距離(weighted derived dynamic time warping,WDDTW)[8-9]，添加窗口的DTW距離[10-11]等，但是這些算法都只從DTW的路徑搜索空間進行改進，在點跡數很高的海量時間序列背景下，依然無法滿足計算效率的要求。

所以針對二維船舶航跡時間序列應用DTW算法度量容易丟失屬性之間相關性的問題，本文采用降維編碼的方法在不丟失經緯度相關性的前提下，將二維航跡時間序列轉化為一維航跡時間序列。同時，針對傳統DTW改進算法在點跡數很高的海量數據背景下計算效率依然無法滿足要求的問題，本文分別從最小粒度壓縮角度和聚類度量搜索角度對DTW算法進行了改進，實驗結果表明該改進實現了對DTW算法計算效率的提升。

1 船舶航道聚類系統架構

本文設計的聚類算法的架構如圖1所示。

由于從數據庫抽取的原始數據中包含有噪聲數據，所以需要對原始數據先進行數據清洗，去除噪聲數據；處理后的船舶航跡數據由于存在停泊斷點和時間斷點，并不是連續的時間序列，為了后續聚類的航道是連續的，本文通過對同一MMSI (maritime mobile service Identity)[12]號下的船舶航跡時間序列進行切割，將其切割成連續的航跡時間序列。之后應用改進的DTW算法對切割后的時間序列進行聚類，最后通過可視化方法進行判決。

2 編碼降維及DTW算法改進

由于船舶航跡時間序列中經緯度屬性之間相關性很高，如果將屬性分開進行DTW度量，會造成屬性之間經緯度相關性的丟失，所以本文提出了一種編碼降維的方法，在不丟失相關性的前提下，將航跡二維時間序列轉化為一維時間序列。之后在進行DTW度量中，由于單條航跡點跡數較高，航跡數量大，傳統DTW改進算法依然無法滿足計算效率的要求，所以為了提高計算效率，本文根據船舶航跡時間序列特點從最小粒度壓縮角度和聚類搜索角度對DTW算法進行了改進，從而提高了計算效率。具體算法改進如下所述。

圖1 聚類算法架構圖Fig.1 Clustering algorithm architecture diagram

2.1 編碼降維

在進行DTW度量時，由于船舶航跡時間序列是一個經緯度時間序列，其經緯度的相關性很高，如果拆開分別進行DTW度量很容易丟失經緯度的相關性。所以為了能夠應用DTW算法對船舶航跡時間序列進行有效的相似性度量，本文提出了一種編碼降維的方法將二維的船舶航跡時間序列轉換成一維船舶航跡編碼時間序列。

具體方法如圖2所示，首先將研究區域依據經緯度值按照如圖2所示方法進行切割，將原始區域切割為9個區域，對落入各個區域的航跡點分別編碼為1～9；之后分別對這9個區域再次應用圖2的方法進行切割，則此時對落入每個格子中的航跡點的編碼為CU×10+CN，其中CU為航跡點的上一級編碼值(例如圖3所示，第1次的CU值是9，第2次的CU值是99)，CN的值為1～9，表示每次9個格子中的第幾個。編碼后的序列如定義1。

圖2 相關編碼Fig.2 Relevant coding

圖3 總體編碼過程Fig.3 Overall coding process

定義1：船舶航跡編碼時間序列

S={Coding(i)∈R:i=1,2,…,m},

(1)

式中：S為預處理中切割出來的連續的航跡時間序列；Coding為船舶航跡時間序列S中的每個航跡點的編碼值，是一個長度為m的一元時間序列。

根據相關編碼的原理可以看出，在地理上相近的點，其編碼值相差較小，說明編碼后的船舶航跡編碼序列既實現了降維，又將原始船舶航跡時間序列中經緯度的相關性轉化為編碼值的大小了。

2.2 最小粒度壓縮改進DTW算法

標準DTW算法[13]的核心思想為

D(i,j)=Dist(i,j)+min[D(i-1,j),
D(i,j-1),D(i-1,j-1)]，

(2)

式中：D(i，j)表示長度i和j的2個時間序列X，Y之間的歸整路徑距離；Dist(i，j)表示X序列第i個點與Y序列第j個點之間的距離。

想求D(i，j)，需要先求出D(i-1，j)，D(i-1，j-1)，D(i，j-1)，依此類推，直到遍歷整個序列，所以DTW算法的時間復雜度為O(N2)。

可見DTW算法的計算效率主要與以下2點有關：①時間序列的點跡數量N值；②D的搜索空間的大小。所以本文通過從這2個方面對DTW算法進行了改進(如圖4所示)。

針對船舶時間序列點跡N較大的問題，采用最小粒度壓縮方法(如圖5所示)將網格中的點跡壓縮成一點，從而將N點的航跡壓縮成M點(N?M)的航跡，從而實現對DTW算法的改進。

圖4 DTW算法改進Fig.4 DTW algorithm improvement

圖5 最小粒度壓縮Fig.5 Minimum granularity compression

之后采用編碼降維后，為了從DTW算法D搜索空間進行改進，本文采用如下方法進行處理：

(1) 進行粗粒度化，將多個細粒度的數據點以平均值形式抽象成為一個點，從而形成一個較粗粒度的序列。具體的方法采用的是PAA(piecewise aggregate approximation)方法[14-15]。

(2) 采用細粒化搜索循環，直到達到最小粒度為止。其中投影是指當前搜索區域下進行DTW運算，而細粒化是指在投影中產生的歸整路徑進一步細化到較細粒度上，同時為了避免粗粒度造成的路徑偏差，在細化后的路徑空間外延伸R個格子作為下一次D搜索空間，如圖6為細粒化搜索過程。

圖6 細粒化搜索過程Fig.6 Fine-grained searching process

2.3 聚類搜索改進DTW算法

傳統時間序列聚類算法會將所有序列之間都進行度量，包括類內和類間的，這實際上會增加大量的時間開銷。所以本文針對航跡類別間差異較大的特點，采用如圖7所示的搜索流程對DTW算法進行改進，提升計算效率。

圖7 搜索改進Fig.7 Search improvement

假設第1次選取S1作為種子航跡，依次與其他航跡進行相似性度量，再假設度量結果顯示{S2,S3,…,Sn}與S1之間的相似性度量值D1y都小于聚類閾值ThD，則認為{S1,S2,…,Sn}聚集為一類，則將{S1,S2,…,Sn}從原始數據集中刪除，之后選取Sn+1作為種子航跡與刪除后的數據集中的數據進行相似性度量，依次類推聚類下去。

3 實驗結果分析

3.1 實驗環境與數據來源

本文前期數據預處理過程采用R語言實現，其硬件平臺為Window7×64位系統，內存為24.0 GB，處理器為Intel(R) Core(TM) i7-4770KCPU@3.50 GH，軟件平臺為R-3.4.3版本。使用的是XX雷達基站采集的XX海域的近1個月28.8 GB的AIS數據。聚類及可視化判決是基于Python語言實現，其硬件平臺為Window8.1×64位系統，內存為4 GB，處理器為Intel(R) Core(TM) i3-3120M CPU @ 2.50 GH，軟件平臺為Python-3.6.4版本。

3.2 航跡時間序列聚類實驗分析

3.2.1 最小粒度壓縮效果分析

最小粒度壓縮效果如表1所示。

表1 壓縮效果表Table 1 Table of compression effect

本文采用的是0.02°×0.02°的最小粒度網格進行壓縮。由于原始數據量太大，本文按照時間將其分割成3個數據集處理。由表1可見，3次壓縮效果都是在200倍左右，說明最小粒度壓縮方法對每條航跡都平均壓縮了200倍，使得DTW計算時間降低了2002倍。

3.2.2 航跡聚類時間分析

如圖8所示，是本文在不同閾值(ThD)下的聚類的時間開銷折線圖。

圖8 ThD與聚類時間的關系折線圖Fig.8 ThD and clustering time line chart

隨著ThD的增加，聚類時間總體上呈現逐漸降低的趨勢，這是由于隨著閾值的增加，聚類越來越充分，同一類中聚集航跡數增多，聚集形成的類增多，所以根據DTW搜索改進思路，需要進行相似性度量的次數就減少了，從而降低了計算時間開銷。

3.2.3 航跡聚類結果分析

如表2所示是實驗中不同ThD下的聚類的總數、正常聚類航道及航道真偽比的統計值。

表2 聚類結果記錄Table 2 Report of clustering result

可以看出當ThD<1 000時，隨著ThD的增加，聚類效果越來越充分，無論從總體的聚類數還是正常的航道數都在增加；當ThD到達1 000時，聚類最充分，此時正常航道數最多，真偽比最大；當ThD>1 000時，由于閾值太大，大量的偽航道開始聚集，此時正常航道間也發生了多個類的融合，所以雖然聚類總數在增加，但是正常航道卻在急劇減少，偽航道大量產生。由此可見最佳的ThD值應當在1 000左右，此時聚類最充分，聚類效果最好。

本文提出的基于改進DTW的聚類算法，由于聚類本身就是基于時間序列的，所以實際上聚類形成的航道本身就具有時序性。

如圖9所示是Pallotta G等人[1]采用DBSCAN算法實現的聚類效果圖，可以看出采用DBSCAN算法聚類結果只有位置信息，沒有方向信息，也沒有時序信息。圖10是本文在ThD=1000時，聚類得到的部分航道效果圖，其中圖10b)是航道中的2條正常航道效果圖，這2條航道經緯度位置相近，只是方向不同(圖b_1航道方向為右上至左下，即●表示序列起始位置，▲表示序列終止位置；圖b_2航道方向為左下至右上)，而這個方向就是時序性，已知任何一點的航行狀態，可以通過這個航道方向知道其前后任何點的航行狀態。

圖9 DBSCAN算法聚類效果Fig.9 DBSCAN algorithm clustering effect chart

圖10 航道效果對比圖Fig.10 Channel comparison chart

4 結束語

本文針對船舶航跡異常檢測中需要提取航跡時序特性的問題，采用基于編碼降維及改進的DTW算法實現了船舶航跡聚類，有效提取出正常航道的時序特性，為后續異常檢測研究提高了先驗知識，同時該算法也為需要時序特性的路徑研究提供了一種算法支持。在該算法中從最小粒度壓縮角度和度量搜索角度改進后的DTW算法有效提高了相似性度量過程的計算效率，基本滿足了聚類度量要求對計算效率的要求，為大點跡量的海量不等長時間序列的相似性度量提供了一種算法支持；為了滿足DTW度量的條件，算法提出的編碼降維方法既完整保留了原始數據的地理相關性，又將地理數據實現了降維，其為地理數據的降維提供了一種新的思路。雖然本文提出的聚類算法實現了提取航跡的時間序列特性，但是由于算法本身對于路徑的規整度依賴較高，對于不規整路徑聚類效果不好，需要進一步改進。