李 麗，賴俊星

(1.中國人民解放軍91001部隊(duì)通頻室，北京 100072;2.中國船舶工業(yè)綜合技術(shù)經(jīng)濟(jì)研究院，北京 100072)

當(dāng)前，自動(dòng)識(shí)別系統(tǒng)(Automatic Identification System，AIS)在船運(yùn)領(lǐng)域中廣泛應(yīng)用，以提高船舶航行的安全性與效率。AIS數(shù)據(jù)內(nèi)部蘊(yùn)含著大量的海上交通時(shí)序信息，包括航速、航向、經(jīng)緯度等船舶的動(dòng)態(tài)信息和船名、呼號(hào)等船舶靜態(tài)信息。船載AIS數(shù)據(jù)是記錄船舶航行與作業(yè)信息的大規(guī)模數(shù)據(jù)，包含船舶行為特征與航行規(guī)律，AIS數(shù)據(jù)挖掘，是研究船舶行為特點(diǎn)的重要方法。在眾多AIS數(shù)據(jù)挖掘方法中，相似性搜索可以幫助人們進(jìn)行相似航線識(shí)別以及異常船只的檢測(cè)，在提升船舶航行安全以及船舶目標(biāo)信息識(shí)別等方面具有重要的實(shí)際應(yīng)用與研究意義。

AIS數(shù)據(jù)屬于時(shí)間序列數(shù)據(jù)，在時(shí)間序列數(shù)據(jù)挖掘領(lǐng)域中，給定待查詢數(shù)據(jù)段在數(shù)據(jù)庫中搜索到與其相似的數(shù)據(jù)是較為基本的要求。然而，對(duì)于AIS數(shù)據(jù)進(jìn)行相似性搜索是一種具有挑戰(zhàn)性的工作，主要由于：1)相比于單變量時(shí)間序列數(shù)據(jù)，AIS數(shù)據(jù)這種多變量時(shí)間序列數(shù)據(jù)具有海量、高維的特點(diǎn)，使得捕獲其數(shù)據(jù)特征更加困難；2)由于AIS數(shù)據(jù)中時(shí)序特征以及屬性變量潛在關(guān)聯(lián)關(guān)系的存在，為相似性表示增加困難。

在眾多時(shí)間序列相似性搜索方法中，基于二進(jìn)制編碼的模型被廣泛使用，例如：局部敏感哈希(LSH)通過計(jì)算產(chǎn)生編碼的漢明距離來得到最相似的數(shù)據(jù)段，這種方法相比于傳統(tǒng)相似性方法可以降低計(jì)算過程中的時(shí)間復(fù)雜度。另外一種廣泛使用的方法是使用滑動(dòng)窗口切割原始時(shí)間序列數(shù)據(jù)，然后通過最小距離方差法生成搜索索引并計(jì)算索引結(jié)構(gòu)來搜索時(shí)間序列數(shù)據(jù)段。近年來，深度學(xué)習(xí)成為最廣泛應(yīng)用的數(shù)據(jù)挖掘技術(shù)之一，其可以自動(dòng)地對(duì)原始數(shù)據(jù)進(jìn)行特征的抽取。在這種情境下，基于深度學(xué)習(xí)的二進(jìn)制編碼生成模型便有潛力進(jìn)行AIS數(shù)據(jù)的相似性搜索。注意力機(jī)制在深度學(xué)習(xí)領(lǐng)域被廣泛應(yīng)用，通過利用注意力機(jī)制可以幫助深度學(xué)習(xí)模型對(duì)輸入的部分賦予不同的權(quán)重，從而提升模型的判斷能力。基于此，本文提出基于Attention機(jī)制的Seq2Seq模型來完成AIS數(shù)據(jù)相似性搜索任務(wù)。其中，基于GRU的Seq2Seq網(wǎng)絡(luò)可以學(xué)習(xí)AIS原始數(shù)據(jù)中的時(shí)序特征，Attention機(jī)制可以捕獲AIS數(shù)據(jù)中各參數(shù)變量之間的依賴關(guān)系。

1 研究背景和相關(guān)工作

時(shí)間序列相似性搜索是一個(gè)熱點(diǎn)問題，在工業(yè)界、金融界等多個(gè)行業(yè)展開了廣泛的研究。對(duì)時(shí)間序列數(shù)據(jù)進(jìn)行相似性搜索有助于促進(jìn)其他時(shí)間序列數(shù)據(jù)挖掘領(lǐng)域的分析工作，例如：異常數(shù)據(jù)檢測(cè)、序列數(shù)據(jù)標(biāo)注、數(shù)據(jù)狀態(tài)識(shí)別以及基于相似性搜索結(jié)果進(jìn)行時(shí)間序列預(yù)測(cè)等。同樣地，在AIS數(shù)據(jù)挖掘領(lǐng)域，相似性搜索可以進(jìn)一步輔助行業(yè)工作人員進(jìn)行航跡分析、相同航跡匹配以及異常船只識(shí)別等，具有較為重要的研究意義。對(duì)于時(shí)間序列相似性搜索，前人的工作主要可分為：傳統(tǒng)時(shí)間序列數(shù)據(jù)表示以及基于深度學(xué)習(xí)的時(shí)間序列數(shù)據(jù)表示方法。本部分主要介紹傳統(tǒng)時(shí)間序列表示方法以及Seq2Seq模型和Attention機(jī)制。

1.1 傳統(tǒng)時(shí)間序列表示方法

傳統(tǒng)的時(shí)間序列數(shù)據(jù)表示方法主要通過對(duì)原始數(shù)據(jù)進(jìn)行降維，并使用降維后的數(shù)據(jù)空間進(jìn)行時(shí)序數(shù)據(jù)的相似性搜索。近二十年來，多種基于降維的時(shí)間序列相似性搜索方法被提出，例如：離散傅里葉變換(Discrete Fourier Transform，DFT)、離散小波變換(Discrete Wavelet Transform，DWT)、符號(hào)近似聚合(Piecewise Aggregate Approximation，PAA)、主成分分析(Principle Component Analysis，PCA)、基于動(dòng)態(tài)時(shí)間彎曲(Dynamic Time Warping，DTW)等。然而，通過這些方法得到的向量表示通常需要相應(yīng)領(lǐng)域的先驗(yàn)知識(shí)，也存在查詢結(jié)果有效性和查詢效率偏低、算法復(fù)雜度較高等問題。

1.2 Seq2Seq模型和Attention機(jī)制

Seq2Seq模型通常與自動(dòng)編碼器相關(guān)聯(lián)，其中包括編碼器以及解碼器，并且編碼器或解碼器也通常使用訓(xùn)練神經(jīng)網(wǎng)絡(luò)進(jìn)行模型學(xué)習(xí)。編碼器讀取輸入序列=(,,…,)并將其轉(zhuǎn)換為固定長(zhǎng)度的向量表示或內(nèi)容向量。接下來，解碼器將向量表示進(jìn)一步轉(zhuǎn)換為與輸入數(shù)據(jù)長(zhǎng)度相同的輸出序列=(,,…,)。

Seq2Seq模型在處理時(shí)間序列數(shù)據(jù)時(shí)存在著相應(yīng)弱點(diǎn)，主要是因?yàn)槟Ｐ椭械南蛄勘硎緹o法對(duì)輸入時(shí)序數(shù)據(jù)的特征進(jìn)行完全的捕獲。對(duì)此，研究者們提出Attention機(jī)制來使解碼器對(duì)編碼器相應(yīng)的隱藏層進(jìn)行選擇。近年來，研究者們提出了幾種Attention模型。通常地，Attention模型的操作如下：在時(shí)刻的解碼過程中，Attention模型通過對(duì)編碼器中所有隱藏層進(jìn)行加權(quán)求和計(jì)算得到相應(yīng)的內(nèi)容向量。通過打分函數(shù)計(jì)算得到求和過程的權(quán)重，從而對(duì)解碼器中各隱藏層的相似性進(jìn)行測(cè)量。最后，相應(yīng)的分?jǐn)?shù)通過softmax函數(shù)進(jìn)行歸一化。

2 基于Seq2Seq的AIS數(shù)據(jù)段相似性搜索模型

本部分提出基于Attention機(jī)制的Seq2Seq模型來進(jìn)行AIS數(shù)據(jù)段的相似性搜索。在詳細(xì)介紹該模型之前，先對(duì)本文研究的基本問題進(jìn)行初步介紹。該相似性搜索模型包含：GRU編碼器、時(shí)序Attention機(jī)制以及GRU解碼器三部分。

2.1 問題描述

AIS數(shù)據(jù)是記錄船舶航行與作業(yè)信息的大規(guī)模數(shù)據(jù)，包含船舶行為特征與航行規(guī)律。主要包括船舶靜態(tài)數(shù)據(jù)、船舶動(dòng)態(tài)數(shù)據(jù)和船舶航程數(shù)據(jù)。船舶靜態(tài)數(shù)據(jù)包括船名、呼號(hào)、MMSI、IMO、船舶類型、船長(zhǎng)和船寬等; 船舶動(dòng)態(tài)數(shù)據(jù)包括經(jīng)度、緯度、船首向、航跡向和航速等; 船舶航程數(shù)據(jù)包括船舶狀態(tài)、吃水和目的地等。其中，船舶動(dòng)態(tài)數(shù)據(jù)是船舶位置經(jīng)緯數(shù)據(jù)的主要來源。

給定待查詢AIS數(shù)據(jù)段，通過構(gòu)建基于Attention機(jī)制的Seq2Seq模型，在AIS時(shí)間序列數(shù)據(jù)庫中搜索到與之相似的數(shù)據(jù)段具有重要的實(shí)際應(yīng)用意義。

2.2 模型定義

基于Attention機(jī)制的Seq2Seq相似性搜索模型結(jié)合了時(shí)間序列數(shù)據(jù)與Seq2Seq模型的特點(diǎn)，使用Seq2Seq模型中GRU編碼器產(chǎn)生的二進(jìn)制編碼進(jìn)行AIS時(shí)間序列數(shù)據(jù)的相似性搜索。如圖1所示，預(yù)處理后的AIS數(shù)據(jù)段作為GRU編碼器的輸入，通過編碼過程來進(jìn)一步獲取輸入AIS數(shù)據(jù)的時(shí)序信息，并通過GRU解碼器來重構(gòu)AIS輸入數(shù)據(jù)。此外，用于衡量AIS數(shù)據(jù)段之間相似性的二進(jìn)制編碼在GRU編碼器與解碼器之間生成。整個(gè)模型通過計(jì)算輸入數(shù)據(jù)與GRU解碼器生成的重構(gòu)數(shù)據(jù)之間的均方誤差損失來進(jìn)行訓(xùn)練。

圖1 基于Attention的AIS數(shù)據(jù)段相似性搜索模型

由于船舶的速度和航向經(jīng)常發(fā)生變化，經(jīng)緯度值具有較大的波動(dòng)性，使用原始的AIS數(shù)據(jù)進(jìn)行建模預(yù)測(cè)容易造成較大的誤差。因此，本文采用中值濾波的方法對(duì)AIS數(shù)據(jù)預(yù)處理，分析該時(shí)刻鄰域內(nèi)的多個(gè)數(shù)據(jù)來計(jì)算在該時(shí)刻的信息。使其更接近于真實(shí)值。

設(shè)AIS在時(shí)段的數(shù)據(jù)為()，由其周圍2個(gè)數(shù)據(jù)點(diǎn)組成的數(shù)據(jù)集合為

[(-),…,(),…,(+)]

則進(jìn)行中值濾波后該點(diǎn)的值為

()=Med[(-),…,(),…,(+)]

中值濾波的優(yōu)點(diǎn)在于對(duì)如AIS數(shù)據(jù)這種單位時(shí)間內(nèi)的位移波動(dòng)較大的數(shù)據(jù)，起到較好的消噪效果，使其更接近于真實(shí)值。

GRU網(wǎng)絡(luò)是用來學(xué)習(xí)原始時(shí)間序列數(shù)據(jù)時(shí)序依賴特征的常用模型。典型的GRU單元包含2個(gè)門，分別是更新門(update gate)和重置門(reset gate)，其分別具有不同的作用：1)更新門：控制前一步隱藏層保留至當(dāng)前狀態(tài)下的信息量； 2)重置門：控制當(dāng)前輸入信息與之前記憶信息的結(jié)合，GRU內(nèi)部原理如圖2所示。

圖2 GRU網(wǎng)絡(luò)內(nèi)部結(jié)構(gòu)

其中，更新門和重置門所對(duì)應(yīng)的公式如下：

=(+-1+)

=(+-1+)

此外，內(nèi)部狀態(tài)的計(jì)算公式如下：

最終傳遞給外界的外部狀態(tài)為：

然而，傳統(tǒng)的GRU在挖掘時(shí)間序列數(shù)據(jù)中有著相應(yīng)弱點(diǎn)，其只能學(xué)習(xí)到先前的時(shí)間序列數(shù)據(jù)特征，對(duì)于后續(xù)時(shí)間序列的時(shí)序關(guān)系特征無法進(jìn)行捕獲。因此，本文使用雙向GRU網(wǎng)絡(luò)(Bi-GRU)作為編碼器，通過兩個(gè)相互關(guān)聯(lián)的隱藏層單元在不同的方向同時(shí)進(jìn)行輸入時(shí)間序列數(shù)據(jù)的處理。

選用兩層單向的GRU網(wǎng)絡(luò)作為解碼器，對(duì)輸入AIS數(shù)據(jù)進(jìn)行重構(gòu)。解碼器中隱藏層可通過公式進(jìn)行更新。對(duì)于解碼器得到的重構(gòu)數(shù)據(jù)，通過兩層的全連接網(wǎng)絡(luò)以得到與輸入數(shù)據(jù)相同的尺寸，便于進(jìn)行均方誤差的計(jì)算。此外，為防止過擬合，在解碼器中的GRU層以及全連接層也加入Dropout層以及正則化層。

其中，-1為解碼器的隱藏層，,為編碼器的輸出與-1的點(diǎn)積操作結(jié)果。計(jì)算出的作為編碼器所有隱藏層輸出的加權(quán)和。

對(duì)于GRU編碼器的輸出數(shù)據(jù)，本文使用一層全連接神經(jīng)網(wǎng)絡(luò)來產(chǎn)生特征向量[,,…,]。并使用二進(jìn)制嵌入映射方程將該特征向量壓縮為二進(jìn)制編碼，其中映射方程具體可表示為

=sgn(),=1,2,…,

其中sgn(·)為信號(hào)方程，當(dāng)輸入值大于0時(shí)該方程的輸出為1，小于0時(shí)輸出結(jié)果為-1。對(duì)于生成的二進(jìn)制編碼，我們通過計(jì)算其漢明距離來進(jìn)行AIS數(shù)據(jù)的相似性搜索。

對(duì)于基于Attention機(jī)制的Seq2Seq的相似性搜索模型，損失函數(shù)定義為輸入與輸出時(shí)序數(shù)據(jù)之間的重構(gòu)誤差。重構(gòu)誤差的計(jì)算過程如下：

其中，、為數(shù)據(jù)段的長(zhǎng)度與屬性參數(shù)數(shù)量，與′分別表示模型輸入與輸出數(shù)據(jù)。本文使用Adam優(yōu)化器來訓(xùn)練模型并且最小化損失函數(shù)。在訓(xùn)練合適的回合數(shù)后，相應(yīng)的模型參數(shù)將用于測(cè)試數(shù)據(jù)集進(jìn)行相似性搜索。

3 實(shí)驗(yàn)驗(yàn)證與結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)選用的自有北斗定位的AIS數(shù)據(jù)集，數(shù)據(jù)集包括了3502條船體的定位信息，共232.5萬條數(shù)據(jù)信息，AIS數(shù)據(jù)是一種時(shí)間序列數(shù)據(jù)，本文所用的每一個(gè)時(shí)間點(diǎn)的數(shù)據(jù)所包含的信息主要包含船體ID信息、經(jīng)度、維度、速度、方向、時(shí)間及工作類型，單個(gè)船體具體數(shù)據(jù)示例如表1所示。

表1 AIS數(shù)據(jù)實(shí)例

實(shí)驗(yàn)中將已知的航道作為“標(biāo)簽變量”使用，計(jì)算實(shí)際的軌跡數(shù)據(jù)與這些已知航道之間的距離。在進(jìn)行相似性查詢之前，還需要在這些距離結(jié)果的基礎(chǔ)上做一些初步的處理：

1)將軌跡數(shù)據(jù)歸類到某個(gè)航道。對(duì)于這一功能的實(shí)現(xiàn)，會(huì)設(shè)置一個(gè)閾值，當(dāng)一條軌跡數(shù)據(jù)到某個(gè)航道的距離小于這個(gè)閾值時(shí)，就將相應(yīng)的軌跡歸類到這個(gè)航道。

2)軌跡數(shù)據(jù)偏離航道檢測(cè)。當(dāng)軌跡數(shù)據(jù)到所有已知航道的距離都大于閾值時(shí)，就可以將這條軌跡數(shù)據(jù)歸類為異常數(shù)據(jù)。

3)未知新航道檢測(cè)。對(duì)于異常數(shù)據(jù)，可以使用非監(jiān)督的聚類算法，再次重復(fù)上面的算法得到相應(yīng)的航道發(fā)現(xiàn)結(jié)果。

經(jīng)過數(shù)據(jù)預(yù)處理后得到的航道發(fā)現(xiàn)結(jié)果如圖3。其中,坐標(biāo)分別對(duì)應(yīng)經(jīng)緯度值，舉例了兩個(gè)航道的軌跡數(shù)據(jù)，偏離航道的異常數(shù)據(jù)用黑色點(diǎn)表示。

圖3 AIS數(shù)據(jù)預(yù)處理后的航道軌跡圖

3.2 模型參數(shù)設(shè)定與評(píng)估方式

上文提到在模型訓(xùn)練過程中，使用Adam優(yōu)化器，學(xué)習(xí)率設(shè)定為0.0002。模型實(shí)驗(yàn)使用的batch-size為128。AIS相似性搜索模型中GRU編碼器與解碼器的hidden-size設(shè)定為100。此外，GRU網(wǎng)絡(luò)以及全連接層中Dropout的值設(shè)定為0.3。

為評(píng)估相似性搜索模型的性能，對(duì)于給定的查詢數(shù)據(jù)段，在數(shù)據(jù)集中基于歐氏距離計(jì)算待查詢數(shù)據(jù)段的近鄰數(shù)據(jù)段作為基準(zhǔn)結(jié)果。對(duì)于搜索模型產(chǎn)生的二進(jìn)制編碼，使用漢明距離來找出帶查詢數(shù)據(jù)的相似數(shù)據(jù)段。相似性搜索模型的有效性將通過三種指標(biāo)進(jìn)行評(píng)估，分別為平均精度均值(Mean Average Precision, MAP)、Top-k準(zhǔn)確率(precision at top-K position, Precision@K)以及Top-k召回率(recall at top-K position, Recall K)。

3.3 實(shí)驗(yàn)結(jié)果與分析

將基于Attention機(jī)制的Seq2Seq的相似性搜索模型與不包含Attention機(jī)制的Seq2Seq模型以及傳統(tǒng)的時(shí)間序列相似性搜索方法LSH進(jìn)行實(shí)驗(yàn)對(duì)比以驗(yàn)證本文所提模型的有效性。

為評(píng)估基于Attention機(jī)制的Seq2Seq的相似性搜索及其對(duì)比模型的有效性，表2給出了不同二進(jìn)制編碼維度下(=64，128，256)，三種模型的平均精度均值。從表2中可以看出：相比于傳統(tǒng)的時(shí)間序列相似性搜索方法LSH，基于Seq2Seq的相似性搜索模型展現(xiàn)出更好的搜索結(jié)果，這主要?dú)w因于LSH無法捕獲AIS時(shí)間序列數(shù)據(jù)中的時(shí)序依賴關(guān)系，進(jìn)而導(dǎo)致在相似性搜索過程中無法形成適合的時(shí)間序列向量表示。此外，相比于不包含Attention機(jī)制的Seq2Seq模型，基于Attention機(jī)制的Seq2Seq模型展現(xiàn)出更為優(yōu)異的AIS時(shí)序數(shù)據(jù)相似性搜索性能，這主要是由于Attention機(jī)制可以進(jìn)一步學(xué)習(xí)AIS時(shí)序數(shù)據(jù)中各參數(shù)變量之間的依賴關(guān)系，從而提升整個(gè)模型的相似性搜索性能。

表2 三種方法在AIS數(shù)據(jù)集上的MAP值

為了進(jìn)一步驗(yàn)證本文所提出模型的有效性，圖4以及圖5分別給出了基于Attention機(jī)制的Seq2Seq模型與其他模型的Top-k準(zhǔn)確率以及Top-k召回率的對(duì)比結(jié)果。如圖5所示，基于Attention機(jī)制的Seq2Seq模型相比于對(duì)比模型展現(xiàn)出更高的Top-k準(zhǔn)確率。同樣地，通過圖5可以看出：在Top-k召回率上，本文所提出的模型也均優(yōu)于對(duì)比模型。以上結(jié)果表明，本文所提模型在基于漢明距離的搜索Top-k列表中展現(xiàn)出較高的準(zhǔn)確率及召回率，這意味著這種基于Attention機(jī)制的Seq2Seq模型，不僅可以捕獲AIS數(shù)據(jù)中的時(shí)序信息，而且由于Attention機(jī)制的存在也可對(duì)AIS數(shù)據(jù)中各參數(shù)變量之間的依賴關(guān)系進(jìn)行學(xué)習(xí)，從而進(jìn)一步提升模型的相似性搜索性能。

圖4 三種方法在AIS數(shù)據(jù)上的Top-k準(zhǔn)確率曲線(v=256)

圖5 三種方法在AIS數(shù)據(jù)上的Top-k召回率曲線(v=256)

4 結(jié)束語

本文提出了一種基于Attention機(jī)制的Seq2Seq模型用于AIS時(shí)序數(shù)據(jù)的相似性搜索任務(wù)。通過實(shí)驗(yàn)對(duì)比了LSH，不包含Attention機(jī)制的Seq2Seq模型以及本文所提出模型在AIS數(shù)據(jù)集上的相似性搜索效果，驗(yàn)證了所提模型的有效性。在AIS數(shù)據(jù)集上，本文提出的基于Attention機(jī)制的Seq2Seq模型展現(xiàn)出優(yōu)異的時(shí)間序列數(shù)據(jù)相似性搜索性能，可以為AIS數(shù)據(jù)挖掘的相關(guān)應(yīng)用提供便利。