曹偉，劉亞帥，管志強(qiáng)

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

0 引言

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

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

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

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

1 船舶航道聚類系統(tǒng)架構(gòu)

本文設(shè)計的聚類算法的架構(gòu)如圖1所示。

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

2 編碼降維及DTW算法改進(jìn)

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

圖1 聚類算法架構(gòu)圖Fig.1 Clustering algorithm architecture diagram

2.1 編碼降維

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

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

圖2 相關(guān)編碼Fig.2 Relevant coding

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

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

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

(1)

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

根據(jù)相關(guān)編碼的原理可以看出，在地理上相近的點(diǎn)，其編碼值相差較小，說明編碼后的船舶航跡編碼序列既實現(xiàn)了降維，又將原始船舶航跡時間序列中經(jīng)緯度的相關(guān)性轉(zhuǎn)化為編碼值的大小了。

2.2 最小粒度壓縮改進(jìn)DTW算法

標(biāo)準(zhǔn)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個點(diǎn)與Y序列第j個點(diǎn)之間的距離。

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

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

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

圖4 DTW算法改進(jìn)Fig.4 DTW algorithm improvement

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

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

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

(2) 采用細(xì)粒化搜索循環(huán)，直到達(dá)到最小粒度為止。其中投影是指當(dāng)前搜索區(qū)域下進(jìn)行DTW運(yùn)算，而細(xì)?；侵冈谕队爸挟a(chǎn)生的歸整路徑進(jìn)一步細(xì)化到較細(xì)粒度上，同時為了避免粗粒度造成的路徑偏差，在細(xì)化后的路徑空間外延伸R個格子作為下一次D搜索空間，如圖6為細(xì)?；阉鬟^程。

圖6 細(xì)?；阉鬟^程Fig.6 Fine-grained searching process

2.3 聚類搜索改進(jìn)DTW算法

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

圖7 搜索改進(jìn)Fig.7 Search improvement

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

3 實驗結(jié)果分析

3.1 實驗環(huán)境與數(shù)據(jù)來源

本文前期數(shù)據(jù)預(yù)處理過程采用R語言實現(xiàn)，其硬件平臺為Window7×64位系統(tǒng)，內(nèi)存為24.0 GB，處理器為Intel(R) Core(TM) i7-4770KCPU@3.50 GH，軟件平臺為R-3.4.3版本。使用的是XX雷達(dá)基站采集的XX海域的近1個月28.8 GB的AIS數(shù)據(jù)。聚類及可視化判決是基于Python語言實現(xiàn)，其硬件平臺為Window8.1×64位系統(tǒng)，內(nèi)存為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°的最小粒度網(wǎng)格進(jìn)行壓縮。由于原始數(shù)據(jù)量太大，本文按照時間將其分割成3個數(shù)據(jù)集處理。由表1可見，3次壓縮效果都是在200倍左右，說明最小粒度壓縮方法對每條航跡都平均壓縮了200倍，使得DTW計算時間降低了2002倍。

3.2.2 航跡聚類時間分析

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

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

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

3.2.3 航跡聚類結(jié)果分析

如表2所示是實驗中不同ThD下的聚類的總數(shù)、正常聚類航道及航道真?zhèn)伪鹊慕y(tǒng)計值。

表2 聚類結(jié)果記錄Table 2 Report of clustering result

可以看出當(dāng)ThD<1 000時，隨著ThD的增加，聚類效果越來越充分，無論從總體的聚類數(shù)還是正常的航道數(shù)都在增加；當(dāng)ThD到達(dá)1 000時，聚類最充分，此時正常航道數(shù)最多，真?zhèn)伪茸畲?；?dāng)ThD>1 000時，由于閾值太大，大量的偽航道開始聚集，此時正常航道間也發(fā)生了多個類的融合，所以雖然聚類總數(shù)在增加，但是正常航道卻在急劇減少，偽航道大量產(chǎn)生。由此可見最佳的ThD值應(yīng)當(dāng)在1 000左右，此時聚類最充分，聚類效果最好。

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

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

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

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

4 結(jié)束語

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