蔣 通 崔良中 周 鋼 張社國(guó)

（1.海軍工程大學(xué)電子工程學(xué)院 武漢 430033）（2.中國(guó)人民解放軍92682部隊(duì) 湛江 524000）

1 引言

船舶自動(dòng)識(shí)別系統(tǒng)是船舶航行安全和海上監(jiān)視的關(guān)鍵，在船舶行為模式分析［1］和海上交通規(guī)律挖掘［2］的研究與應(yīng)用中受到了廣泛關(guān)注。對(duì)AIS船舶軌跡數(shù)據(jù)開(kāi)展聚類(lèi)分析研究，可以跟蹤與預(yù)測(cè)船舶航行軌跡，檢測(cè)與識(shí)別船舶異常行為［3］，從而為航運(yùn)規(guī)劃和海事監(jiān)管等工作開(kāi)展提供決策支持和科學(xué)依據(jù)。目前，國(guó)內(nèi)外學(xué)者對(duì)于船舶軌跡聚類(lèi)的研究主要從以下三個(gè)方面展開(kāi)。

在研究對(duì)象方面，21世紀(jì)初Knorr等人以整條航跡為聚類(lèi)的對(duì)象，使用位置、方向和速度等三個(gè)維度組成的序列來(lái)表示每個(gè)位置點(diǎn)，運(yùn)用傳統(tǒng)距離函數(shù)來(lái)計(jì)算軌跡之間距離并對(duì)航跡進(jìn)行聚類(lèi)。而Lee等［4］將整條航跡劃分成子航跡，考慮航跡的結(jié)構(gòu)性特征，來(lái)計(jì)算子航跡段之間的相似性。此后肖瀟等［5］將航跡方向變化較大的點(diǎn)作為整條航跡的分割點(diǎn)，對(duì)分割后的子航跡進(jìn)行聚類(lèi)。

在相似性度量方面，大多數(shù)是基于距離進(jìn)行計(jì)算，諸如歐幾里得距離、hausdorff距離和最長(zhǎng)公共子序列距離等。然而，航跡的速度、方向等特征都應(yīng)當(dāng)被考慮在內(nèi)。牟軍敏等［6］基于hausdorff距離，設(shè)計(jì)自動(dòng)選取尺度參數(shù)的相似度度量函數(shù)，構(gòu)造相似度矩陣；雷鵬［7］將包含多個(gè)特征的結(jié)構(gòu)化距離進(jìn)行歸一化，避免由于各項(xiàng)特征的取值范圍差別較大而造成的實(shí)驗(yàn)誤差。

在算法選擇方面，目前常用的航跡聚類(lèi)算法主要包括基于密度［8～9］（DBSCAN、OPTICS）、基于統(tǒng)計(jì)學(xué)（GMM、KDE）和基于網(wǎng)格（CLIQUE、STING）的軌跡聚類(lèi)算法等。其中，DBSCAN算法因其能夠發(fā)現(xiàn)任意形狀的簇類(lèi)而被廣泛改進(jìn)和應(yīng)用。江玉玲等［10］采用離散Frechet距離作為軌跡相似度度量，利用類(lèi)似DBSCAN算法對(duì)軌跡段進(jìn)行聚類(lèi)，得出船舶運(yùn)動(dòng)典型軌跡；PALLOTTA等［11］采用增量DBSCAN算法對(duì)AIS船舶軌跡數(shù)據(jù)中的轉(zhuǎn)向點(diǎn)進(jìn)行聚類(lèi)，在此基礎(chǔ)上分析船舶的交通流模式。

然而，原始AIS數(shù)據(jù)是如何一步步變成可以為我們所用的有效信息，相關(guān)系統(tǒng)完整的研究較少。為解決這一問(wèn)題，本文在對(duì)AIS數(shù)據(jù)進(jìn)行預(yù)處理后，提出一種多步驟船舶軌跡聚類(lèi)方法，主要包括軌跡壓縮、軌跡點(diǎn)匹配與距離相似性度量和軌跡聚類(lèi)等三部分，并利用真實(shí)AIS數(shù)據(jù)進(jìn)行實(shí)例驗(yàn)證。

2 數(shù)據(jù)預(yù)處理

原始AIS數(shù)據(jù)預(yù)處理過(guò)程如圖1所示。

圖1 AIS數(shù)據(jù)預(yù)處理流程圖

AIS報(bào)告種類(lèi)包括船位報(bào)告、基地臺(tái)報(bào)告和信道管理等13種，長(zhǎng)度從168～1192比特?cái)?shù)不等。對(duì)AIS數(shù)據(jù)進(jìn)行預(yù)處理首先需要對(duì)其各個(gè)組成部分進(jìn)行剖析，將信息進(jìn)行解碼處理，才能轉(zhuǎn)化成我們需要的水上移動(dòng)通信業(yè)務(wù)標(biāo)識(shí)碼（MMSI）、IMO編號(hào)、船長(zhǎng)和船寬和船舶類(lèi)型等靜態(tài)信息，以及船舶位置、對(duì)地航速、對(duì)地航向和航行狀態(tài)等動(dòng)態(tài)信息。

AIS數(shù)據(jù)經(jīng)過(guò)解析后主要存在三個(gè)方面的數(shù)據(jù)質(zhì)量問(wèn)題：1）重復(fù)（連續(xù)兩行數(shù)據(jù)完全一致）；2）缺失（如某一行數(shù)據(jù)中某個(gè)屬性數(shù)據(jù)為空）；3）錯(cuò)誤（某些數(shù)據(jù)明顯與客觀事實(shí)不符，如實(shí)際航向超出0～3599、實(shí)際航速超出0～1022等）。這些數(shù)據(jù)都應(yīng)該去除，否則會(huì)對(duì)實(shí)驗(yàn)結(jié)果產(chǎn)生不可忽視的影響。

每一條AIS數(shù)據(jù)中記錄著大量信息，在本文對(duì)船舶軌跡聚類(lèi)的研究中，我們只需提取MMSI、時(shí)刻、實(shí)際航速、經(jīng)度、緯度和實(shí)際航向等六種屬性信息，這樣可以有效提高后續(xù)計(jì)算效率。

為方便后續(xù)研究的開(kāi)展，一般需要先對(duì)數(shù)據(jù)進(jìn)行無(wú)量綱化處理，這樣表征不同屬性的各數(shù)據(jù)之間才有可比性。數(shù)據(jù)規(guī)范化的常用方法主要包括z分?jǐn)?shù)規(guī)范化、正則化、小數(shù)定標(biāo)規(guī)范化和最小-最大規(guī)范化。根據(jù)AIS航跡數(shù)據(jù)的特點(diǎn)，本文選用最小-最大規(guī)范化。

假設(shè)minA和maxA分別為屬性A的最小值和最大值。最小-最大規(guī)范化通過(guò)計(jì)算：

把A的值vi映射到區(qū)間［0，1］中的v'i。最小-最大規(guī)范化既可以放大某些標(biāo)準(zhǔn)差較小的特征之間的差異，又能夠保留原始數(shù)據(jù)中由標(biāo)準(zhǔn)差所反映的潛在權(quán)重關(guān)系，因此被廣泛應(yīng)用。

對(duì)AIS數(shù)據(jù)進(jìn)行預(yù)處理后的結(jié)果及對(duì)部分?jǐn)?shù)據(jù)進(jìn)行規(guī)范化的結(jié)果如圖2所示。

圖2 規(guī)范化前后的AIS數(shù)據(jù)對(duì)比

3 多步驟船舶軌跡聚類(lèi)方法

完成對(duì)AIS數(shù)據(jù)的預(yù)處理后，本文提出多步驟船舶軌跡聚類(lèi)方法［12］，主要由軌跡壓縮、軌跡點(diǎn)匹配與距離相似性度量和軌跡聚類(lèi)等三部分組成。完整流程如圖3所示。

圖3 多步驟船舶軌跡聚類(lèi)方法

3.1 軌跡壓縮

每一條軌跡都可以看做是一條不規(guī)則曲線，在對(duì)軌跡數(shù)字化時(shí)，要對(duì)曲線進(jìn)行采樣，即在曲線上取有限個(gè)點(diǎn)，將其變?yōu)檎劬€，并且能夠在一定程度上保持原有的形狀。經(jīng)典算法步驟如下。

運(yùn)用經(jīng)典 Douglas-Peucker（DP）［13］算法壓縮軌跡時(shí)，只考慮了軌跡點(diǎn)的經(jīng)度和緯度，而忽略了航向和航速對(duì)壓縮結(jié)果的影響，往往會(huì)導(dǎo)致不能將“轉(zhuǎn)折點(diǎn)”或“變速點(diǎn)”保留下來(lái)。因此，本文在經(jīng)典DP算法的基礎(chǔ)上進(jìn)行改進(jìn)，通過(guò)查閱相關(guān)文獻(xiàn)資料以及咨詢(xún)航海領(lǐng)域?qū)I(yè)人士，保留符合以下條件中至少一條的軌跡點(diǎn)：

也即保留航向或航速變化較大的點(diǎn)。

以經(jīng)度為橫坐標(biāo)、緯度為縱坐標(biāo)，經(jīng)改進(jìn)的DP軌跡壓縮算法處理前后的軌跡對(duì)比如圖4所示。原始軌跡包括73個(gè)軌跡點(diǎn)，壓縮后軌跡包括58個(gè)軌跡點(diǎn)，軌跡點(diǎn)減少的同時(shí)能夠基本保持原有形狀。

圖4 軌跡壓縮前后對(duì)比

3.2 軌跡點(diǎn)匹配和距離相似性度量

在某一區(qū)域、某一時(shí)間段內(nèi)的所有AIS航跡數(shù)據(jù)中，不同航跡包含的軌跡點(diǎn)數(shù)量往往不同，而且，僅依據(jù)經(jīng)緯度作為衡量軌跡間距離的指標(biāo)往往是片面的，因此如何更全面、更準(zhǔn)確地對(duì)不同軌跡的軌跡點(diǎn)進(jìn)行匹配以及軌跡間距離相似性如何度量成為目前研究的熱點(diǎn)問(wèn)題。

每一條航跡都可以看作是由相鄰軌跡點(diǎn)連接而成的子航跡段組成，我們采用動(dòng)態(tài)時(shí)間規(guī)整算法（DTW）［14］對(duì)不同航跡之間的軌跡點(diǎn)進(jìn)行匹配，保證每條航跡的任一軌跡點(diǎn)在另一條航跡當(dāng)中都能找到與之匹配的軌跡點(diǎn)，把它們之間的等效認(rèn)為是以此軌跡點(diǎn)為起點(diǎn)的子航跡段之間的“距離”。算法的思想是使用迭代的方法求出任意兩條航跡的匹配路徑，使得“距離”最小。

假設(shè)有兩條軌跡為T(mén)raj1和Traj2，T1i表示第一條軌跡的第i個(gè)軌跡點(diǎn)，T2j表示第二條軌跡的第j個(gè)軌跡點(diǎn)，DTW(i,j)表示Traj1的前i個(gè)軌跡點(diǎn)組成的軌跡和Traj2的前j個(gè)軌跡點(diǎn)組成的軌跡之間的最小“距離”。那么：

不同軌跡之間的結(jié)構(gòu)化距離中除了幾何距離外，還包括由于航向和航速的差異而導(dǎo)致的“距離”［15］，我們也需要對(duì)此進(jìn)行度量。假設(shè)m和n是任意兩條不同軌跡上的點(diǎn)跡，可以用四維向量來(lái)描述其特征，以點(diǎn)m為例：

其中，lat表示緯度，lng表示經(jīng)度，cog表示航向，sog表示航速。以點(diǎn)跡m為例，將sogm在兩個(gè)方向軸進(jìn)行水平和垂直投影分解為Vm//和Vm⊥兩個(gè)分量：

對(duì)sogn進(jìn)行同樣分解，則不同軌跡上的點(diǎn)跡之間的速度差異可以表示為

同理，將兩軌跡點(diǎn)之間的幾何距離d(m,n)分解為d//和d⊥兩個(gè)分量，由于地球?yàn)榻频臋E球體，可以用如式（8）進(jìn)行計(jì)算：

其中，C表示兩點(diǎn)與球心連線的夾角，Rc為地球的平均半徑。

那么m、n兩點(diǎn)之間地結(jié)構(gòu)化距離為

上式中，μi表示各“距離”所占權(quán)重，需滿足條件：μi≥0,i=1,2,3,4且∑μi=1。

3.3 軌跡聚類(lèi)

在應(yīng)用比較廣泛的幾類(lèi)軌跡聚類(lèi)算法中，DBSCAN算法是一種有代表性的基于密度的無(wú)監(jiān)督聚類(lèi)算法。它將簇定義為密度相連的點(diǎn)的最大集合，在無(wú)須事先設(shè)定簇的個(gè)數(shù)前提下，能夠發(fā)現(xiàn)任意形狀和大小的簇，而AIS數(shù)據(jù)具有噪聲點(diǎn)多、軌跡不確定的特性，應(yīng)用DBSCAN算法能夠獲得較好的聚類(lèi)效果。

應(yīng)用DBSCAN算法進(jìn)行軌跡聚類(lèi)的結(jié)果取決于鄰域半徑參數(shù)ε和鄰域密度閾值MinPts的確定。本文對(duì)DBSCAN算法的改進(jìn)正是體現(xiàn)在這兩個(gè)參數(shù)的選取方法上。

聚類(lèi)的目的是將樣本數(shù)據(jù)集盡可能地聚合成簇。鄰域密度MinPts一定的情況下，鄰域半徑ε過(guò)大會(huì)導(dǎo)致簇之間區(qū)分度很小，ε過(guò)小會(huì)導(dǎo)致得到的簇較少，而噪聲點(diǎn)較多；鄰域半徑ε一定的情況下，鄰域密度MinPts過(guò)大會(huì)導(dǎo)致噪聲點(diǎn)較多，MinPts過(guò)小會(huì)導(dǎo)致聚成的簇?cái)?shù)較多，不能實(shí)現(xiàn)聚類(lèi)的目的。本文采用基于核密度估計(jì)和噪聲數(shù)據(jù)量變化的方法來(lái)確定合適的鄰域半徑參數(shù)ε和鄰域密度閾值MinPts。

核密度估計(jì)（KDE）是一種用于估計(jì)概率密度函數(shù)的非參數(shù)方法，x1,x2,…,xn為獨(dú)立同分布F的n個(gè)樣本點(diǎn)，其概率密度函數(shù)為f，則核密度估計(jì)可表示為

其中，K(.)為核函數(shù)，h為一個(gè)平滑參數(shù)，稱(chēng)作帶寬或窗口，Kh(.)為縮放核函數(shù)。

高斯核函數(shù)是比較常用的核函數(shù)，對(duì)于噪音數(shù)據(jù)有著較好的抗干擾能力，其數(shù)學(xué)形式如下：

其參數(shù)決定了函數(shù)作用范圍，因此其性能對(duì)參數(shù)十分敏感。為降低函數(shù)對(duì)參數(shù)的依賴(lài)性，本文選用指數(shù)函數(shù)，其數(shù)學(xué)形式如下：

將式（13）、（15）兩式聯(lián)立，可得到概率密度函數(shù)表達(dá)式為

鄰域密度閾值MinPts∈[1 ,n]，其中n為樣本總數(shù)，根據(jù)上述方法可確定MinPts不同取值下對(duì)應(yīng)的鄰域半徑參數(shù)ε。

噪聲數(shù)據(jù)量的變化可以用來(lái)衡量聚類(lèi)的效果。隨著鄰域密度閾值MinPts的增大，噪聲數(shù)據(jù)量逐漸減少，且速度呈現(xiàn)出由慢到快再到慢的趨勢(shì)，部分學(xué)者［16］基于此認(rèn)為使得噪聲數(shù)據(jù)量變化率最大的MinPts最為合適，然后這并不能保證將樣本數(shù)據(jù)集盡可能地聚合成簇，因此本文對(duì)此進(jìn)行改進(jìn)，假設(shè)g為鄰域密度閾值MinPts到噪聲數(shù)據(jù)量的一個(gè)映射：

最合適的MinPts應(yīng)滿足以下要求：

其中，n為樣本總數(shù)。從上式中可以看出，MinPts的取值應(yīng)保證噪聲數(shù)據(jù)不超過(guò)樣本總數(shù)的5%，這樣可以取得更好的聚類(lèi)效果。

4 實(shí)驗(yàn)驗(yàn)證與分析

4.1 實(shí)驗(yàn)準(zhǔn)備

本文基于Python語(yǔ)言編寫(xiě)程序并進(jìn)行了實(shí)驗(yàn)。選取2013年1月某連續(xù)10h內(nèi)在長(zhǎng)江入海口河段部分水域（119.0°E～119.5°E、32.2°N～32.3°N）測(cè)得的115098條AIS數(shù)據(jù)作為樣本。利用DP算法壓縮軌跡時(shí)的閾值dMax取0.01，距離結(jié)構(gòu)化度量中的權(quán)重參數(shù)μ1、μ2、μ3、μ4均取 0.25，改進(jìn)的基于DBSCAN算法的軌跡聚類(lèi)算法中的兩個(gè)重要參數(shù)ε取52.5，MinPts取20。

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

對(duì)AIS數(shù)據(jù)進(jìn)行預(yù)處理后，篩選出至少包含100個(gè)軌跡點(diǎn)的194條航跡，運(yùn)用本文提出的多步驟船舶估計(jì)聚類(lèi)方法進(jìn)行聚類(lèi)，并與文獻(xiàn)［15］提出的基于行為特征相似度的船舶軌跡聚類(lèi)方法進(jìn)行對(duì)比，結(jié)果如表2所示。

從表1中可以看出，本文方法在獲取更多簇?cái)?shù)的情況下，噪聲數(shù)據(jù)反而較少，且通過(guò)下文的主航道提取可以得出本文方法更加合理的結(jié)論。

表1 軌跡聚類(lèi)結(jié)果

利用Python作圖，以經(jīng)度為橫坐標(biāo)、以緯度為縱坐標(biāo)，分別將每一類(lèi)航跡進(jìn)行展示，如圖5所示。

從圖5中可以看出，船舶在該水域航行的軌跡主要有三條，以類(lèi)別二為代表的軌跡主要位于所選區(qū)域的西南一側(cè)，大致航向?yàn)闁|北-東南，并且轉(zhuǎn)向過(guò)程基本在119.10°E～119.15°E完成；以類(lèi)別三為代表的軌跡主要位于所選區(qū)域的東南一側(cè)，大致航向?yàn)闁|北-正東，轉(zhuǎn)向角度小于“類(lèi)別一”；而以類(lèi)別一為代表的軌跡顯著特點(diǎn)是航向的多次改變。

為能更好地表示聚類(lèi)結(jié)果，利用Matlab作圖，取每一類(lèi)軌跡的均值，得到平均軌跡，也可以理解為船舶在該水域航行的三條主要航道，如圖5所示。

圖5 軌跡聚類(lèi)結(jié)果示意圖

圖6 長(zhǎng)江口某水域主航道示意圖

值得注意的是，樣本數(shù)據(jù)中有四條航跡沒(méi)有被聚到任何簇中，可以認(rèn)為它們是“異?！钡?，往往代表著船舶比較特殊的行為模式，不同于海上目標(biāo)一般的行動(dòng)規(guī)律。通過(guò)整合和比較可知，每一條軌跡都會(huì)出現(xiàn)一段基本與y軸平行的部分，而且4條軌跡的航速最大航速不超過(guò)7節(jié)（圖7），航行過(guò)程中基本保持在3節(jié)～5節(jié)（圖8）。通過(guò)對(duì)該水域?qū)嶋H情況的調(diào)查，得知可能是從事拖帶、引航、水下作業(yè)等活動(dòng)的特殊船舶的軌跡。

圖7 異常軌跡位置變化

圖8 異常軌跡航速變化

5 結(jié)語(yǔ)

本文針對(duì)目前AIS船舶軌跡聚類(lèi)過(guò)程不夠系統(tǒng)完整的問(wèn)題，首先對(duì)原始AIS數(shù)據(jù)進(jìn)行預(yù)處理，提出主要包括軌跡壓縮、子軌跡匹配、相似性度量和軌跡聚類(lèi)等三部分的多步驟船舶軌跡聚類(lèi)方法，并以長(zhǎng)江入海口河段部分水域的真實(shí)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)驗(yàn)證，結(jié)果表明該方法不僅可以找出船舶在該水域航行的主要航道，而且能夠發(fā)現(xiàn)異常軌跡的存在，在航道規(guī)劃和海事監(jiān)管方面有一定的應(yīng)用意義，對(duì)AIS船舶軌跡聚類(lèi)的研究有一定的參考價(jià)值。