一致性檢測和航向編碼的船舶航跡聚類

何春城,曹 偉,管志強

(中國船舶重工集團公司第七二四研究所,江蘇 南京 211106)

1 引言

AIS點跡數(shù)據(jù)是近年來海事安全中的重要數(shù)據(jù)源,國內(nèi)的研究集中在軌跡跟蹤、軌跡聚類、軌跡重構(gòu)等方面[1]。

其中軌跡聚類多用于建立船舶航行的模型,基于密度的聚類算法[2-4]不需要預(yù)先設(shè)定聚類的簇數(shù),并且可以過濾噪聲,非常適合AIS點跡這類數(shù)據(jù)。聚類過程中,相似性度量包括hausdorff距離[5]、DTW距離[2],文獻[2,5]中的聚類方法都需要遍歷AIS軌跡中的每一個點,復(fù)雜度比較大。針對目標活動模式的挖掘手段一般分為網(wǎng)格法[6-8,15]和矢量法[9]兩種,Alvares[10]論證了帶有語義信息的軌跡數(shù)據(jù)性對于傳統(tǒng)的時空數(shù)據(jù)處理上的優(yōu)越性,提出軌跡信息與相關(guān)地理信息離線交叉的算法IB-SMoT。除此之外還有根據(jù)軌跡的速度聚類出停留點的方法CB-SMoT,缺點在于船舶進出停留點附近時噪聲較多[11]導(dǎo)致聚類空間區(qū)域遠大于實際。Jose Antonio[12]提出了可靠性更高的基于方向的停留點檢測方法DB-SMoT。但是上述的停留點檢測方法都是以矢量的方法遍歷處理點跡信息,復(fù)雜度高,而網(wǎng)格化處理便于壓縮軌跡信息提高效率。網(wǎng)格化的缺點在于以網(wǎng)格為單元處理軌跡信息丟失了不同網(wǎng)格點跡之間的時空關(guān)系,為此劉亞帥[13]提出了一種基于九宮格的網(wǎng)格編碼方案,從而得到船舶經(jīng)過的網(wǎng)格序列保留了點跡的時空關(guān)系,但此方法不適用于大范圍的海域,且將網(wǎng)格內(nèi)點跡壓縮到網(wǎng)格中心的方法丟失了較多的軌跡空間信息。

針對網(wǎng)格化方法丟失點跡之間的時空關(guān)系問題,提出了一種基于航向的編碼方案,采用基于網(wǎng)格化的軌跡點“抽取”的方式來壓縮軌跡,保留了軌跡點之間的相對時空關(guān)系及軌跡形狀的語義信息,精度取決網(wǎng)格劃分的精細程度。在該航向編碼的基礎(chǔ)上,采用DTW算法完成了軌跡的聚類,避免了遍歷所有點跡,且簡化了DTW算法中序列點之間的距離度量。

2 船舶航跡一致性檢測及聚類步驟

將數(shù)據(jù)庫中的提取的數(shù)據(jù)進行清洗,去除無效數(shù)據(jù)之后進行MMSI一致性檢測,同時篩除軌跡中不符合運動邏輯的飛點,將相關(guān)性不強的軌跡分段,提高數(shù)據(jù)的質(zhì)量。預(yù)處理完成之后在網(wǎng)格化的基礎(chǔ)上對軌跡進行航向編碼,對航向序列應(yīng)用改進的DTW算法進行密度聚類并將結(jié)果可視化。

3 基于一致性檢測的點跡分離

AIS數(shù)據(jù)在實際應(yīng)用中經(jīng)常會碰到多艘船舶共用一個MMSI號的問題,如果這些船舶在鄰近的時間內(nèi)出現(xiàn)在研究海域會出現(xiàn)軌跡反復(fù)跳躍的問題,除此之外由于AIS數(shù)據(jù)中的位置信息由GPS等提供,當出現(xiàn)誤差時會導(dǎo)致軌跡出現(xiàn)明顯不符合運動邏輯的飛點(定義1)導(dǎo)致相關(guān)軌跡數(shù)據(jù)的可用性非常低。

為了解決上述問題,本文提出了一種基于狀態(tài)信息觸發(fā)的點跡來源一致性檢測,在去除軌跡飛點、分離共用MMSI船舶點跡的同時提高了算法的處理速度。具體過程如圖1所示,首先保存軌跡第一個點所在的網(wǎng)格位置,后續(xù)處于相同網(wǎng)格的點跡視為具有相同狀態(tài)信息的點跡即正常點跡,直到一個點跡進入新的網(wǎng)格,視為出現(xiàn)了新的狀態(tài)信息,此時觸發(fā)算法的檢測過程,若判定新狀態(tài)點為飛點,則將其加入other＿point集合,若不是飛點,則更新當前網(wǎng)格位置同時繼續(xù)進行斷點(定義2)檢測,若是斷點則認為該點前后軌跡不具有較強的相關(guān)性,將前面的點保存為一段軌跡,后續(xù)點跡重復(fù)進行前述操作,最后對other＿point集合進行遞歸操作。其中飛點檢測是為了排除不符合運動邏輯的點跡,因此利用該點跡與之前的合理點跡之間的位置與時間差計算出兩點之間的速度,若速度明顯大于合理值則認為該點為飛點。斷點檢測是為了將相關(guān)性不強的軌跡段分割,因此當軌跡之間的間距大于一個閾值時判定為斷點,本文根據(jù)經(jīng)驗將該閾值設(shè)為10000m,同時只保留長度達到閾值Thr(取100)的軌跡段。

圖1 基于一致性檢測的點跡分離

圖2 航向編碼

定義:

1)飛點:一串正常的軌跡點中出現(xiàn)的偏離了船舶的正常航道的點,且不符合船舶的運動邏輯,一般會導(dǎo)致船舶的軌跡出現(xiàn)毛刺。

2)斷點:當同一個軌跡中出現(xiàn)較長的一段空白,認為這個軌跡缺口的前后兩端軌跡之間的相關(guān)性較弱,將軌跡在此處分段,并將缺口定義為斷點。

4 基于航向編碼的船舶航跡聚類

當前船舶航跡聚類算法都需要計算每一個軌跡點,如甄榮[14]使用hausdorff距離作為軌跡相似性度量,趙梁濱[2]使用DTW距離作為相似性度量,且算法中每兩點之間的距離使用歐氏距離,計算量非常大。為了避免計算所有點跡之間的距離,需要在壓縮軌跡的數(shù)據(jù)量的基礎(chǔ)上提取軌跡形狀信息,為此提出了基于網(wǎng)格化的航向編碼,利用航向序列中包含的軌跡形狀信息進行聚類。

4.1 基于網(wǎng)格化的航向編碼

Arguedas[8]認為船舶時空行為的變化的主要標志是船舶對地航向的變化,船舶的航向保持代表了船舶維持的一種航行狀態(tài)。當船舶出現(xiàn)穩(wěn)定的航向變化代表船舶進入另外一種航行狀態(tài),船舶的一段軌跡由多個航行狀態(tài)組成。軌跡語義信息的挖掘模型DB-SMoT(Direction Based-Stop and Move of Trajectory)正是基于船舶航行過程中的航向信息聚類出停留點從而挖掘語義信息,現(xiàn)有的研究中對航向變化的定義為

D(Pi)=abs(direction(Pi-1,Pi)-direction(Pi,Pi+1))

(1)

針對航向信息的提取需要遍歷計算所有點跡,但海上風(fēng)浪以及其它客觀因素的影響會使船舶在短時間內(nèi)可能會出現(xiàn)劇烈的航向抖動導(dǎo)致出現(xiàn)大量誤檢的航跡拐點。為了解決上述問題,保證提取的航向變化為船舶的累計變化、過濾航跡的抖動,本文在網(wǎng)格劃分的基礎(chǔ)上以網(wǎng)格為單位提取航向信息,具體過程如下:

每當軌跡點進入一個新的網(wǎng)格,記錄該軌跡點,同時計算該軌跡點與上一個被記錄的軌跡點之間的方位角,最終按照方位角所在的區(qū)間值保存航向:

Course=direction(record＿Pi-1,record＿Pi)∥22.5+1

(2)

其中a∥b表示a除以b并向下取整,下圖3中每當軌跡進入一個新的網(wǎng)格時觸發(fā)一次航向編碼,編碼數(shù)值的大小代表了不同的航向,最終編碼為一串航向序列:

圖3 基于網(wǎng)格的航向編碼

由于網(wǎng)格的大小是固定的,因此航向序列的長度在以網(wǎng)格寬度為單位的基礎(chǔ)上反應(yīng)了軌跡的長度。網(wǎng)格的大小對該方法影響較大,較小的網(wǎng)格劃分使同一條軌跡會被提取更多次航向,編碼出一串更長的航向序列從而更還原軌跡的航行狀態(tài),但過小的網(wǎng)格也會導(dǎo)致船舶航行過程中一些無意義的航向抖動被捕捉以及更大的計算量。當網(wǎng)格較大時可能會導(dǎo)致對原軌跡的采樣率不夠,丟失過多原軌跡的航行信息。綜合以上考慮本文選取網(wǎng)格劃分的大小為0.02°×0.02°,即每個網(wǎng)格的邊長約為2224 m,如式(3),此劃分下數(shù)據(jù)的壓縮可以達到200倍左右[13]。

(3)

4.2 基于航向序列及DTW優(yōu)化的密度聚類

考慮到AIS的特點,使用密度聚類方法,優(yōu)點在于不需要事先知道聚類的簇的數(shù)量,且可以過濾噪聲數(shù)據(jù),由于航向序列是不等長的序列,采用DTW算法來計算序列之間的相似度。DTW算法的核心思想是:

D(i,j)=dist(i,j)+min[D(i-1,j),

D(i,j-1),D(i-1,j-1)]

(4)

長度為i和長度為j的X,Y兩個序列之間的距離為|D(i,j)|,dist(i,j)為X的第i個值和Y的第j個值之間的距離,本文中dist的定義如下,其中d(i,j)=X(i)-Y(j):

(5)

(5)式中dist的計算結(jié)果可能為負,因此最終的距離D(i,j)需要取絕對值,這樣構(gòu)造dist的優(yōu)點在于當進行兩條軌跡的相似度量時,如果其中一條軌跡出現(xiàn)了航向偏離導(dǎo)致距離|D|增大,如圖4 a段軌跡,當該軌跡航向回歸時由于dist計算結(jié)果符號相異從而抵消|D|的變化,如圖4 b段軌跡,但航向偏離需要保證在|D(m,n)|小于閾值Exp的前提下。

圖4 軌跡航向偏離后回歸

DTW算法多應(yīng)用壓縮語音序列來匹配語音序列,如圖5(a)所示DTW算法通過將序列中的多個點匹配到同一個點來達到壓縮語音中部分拉長的發(fā)音的目的,這個特點非常適合應(yīng)用到船舶航向序列中,增加了船舶航行模式匹配的靈活度,但是由于航向序列的長度代表了船舶航跡的長度,必須防止過多的點對應(yīng)同一個點,如圖5(b)。

圖5 DTW算法中點的匹配

因此DTW路徑搜索的過程中將搜索范圍限定在對角線附近,如圖6,保證了航向序列中匹配上的狀態(tài)在實際中航跡長度不會相差過大,同時減小了搜索的范圍。為進一步減少計算量,如(6)式,當搜索路徑中所有候選項已經(jīng)大于閾值Exp時可以直接判定不相似,這樣也保證了所允許的(5)式對航向偏離的糾正范圍限定在Exp以內(nèi)

圖6 路徑搜索過程優(yōu)化

dist(m,n)+min[D(m-1,n),D(m,n-1),

D(m-1,n-1)]>Exp(0

(6)

聚類采用DBSCAN算法,由于其時間復(fù)雜度為O(N2),因此本文從全部的10494條軌跡中抽樣出部分軌跡,通過對樣本聚類得到核心軌跡,再將所有的軌跡與核心軌跡進行匹配,如果距離小于閾值Exp,則認為被聚類到該簇中,抽樣的數(shù)量如下:

(7)

其中f是一個0到1之間的分數(shù),當樣本的大小為s時,對于數(shù)量為mi的一個簇,將以概率1-δ(0≤δ≤1)從該簇中得到至少f*mi個對象,本文s=5389。在使用DBSCAN聚類時,將形成聚類核的近鄰數(shù)量閾值MinPts設(shè)置為5,衡量對象之間是否為近鄰的距離閾值為Exp=log1.8min(l1,l2),其中l(wèi)1,l2分別是兩個序列的長度。

5 實驗結(jié)果分析

本實驗的硬件平臺為Windows10 x64位系統(tǒng),內(nèi)存為16 GB,處理器為AMD Ryzen 7 4800HS CPU @ 2.9 GH,軟件平臺為python 3.8版本。實驗使用的是山東半島附近海域近半個月的AIS數(shù)據(jù)。

5.1 點跡分離結(jié)果分析

經(jīng)過點跡分離處理之后,能夠有效地將具有相同MMSI號的異源點跡分離,避免了軌跡在兩條航道上反復(fù)跳躍。

上圖7的上部分中分離了分屬兩艘船的航道且保留了AIS點跡數(shù)量大于100的航跡,下半部分是部分軌跡的處理結(jié)果,一致性檢測算法有效地篩選出了軌跡的斷點和飛點,并做出相應(yīng)的處理以提高數(shù)據(jù)的質(zhì)量。本文提出的基于狀態(tài)信息觸發(fā)檢測的點跡分離在具有以上功能的同時還可以省略對具有相同狀態(tài)信息的點跡的檢測過程,算法效率對比遍歷所有點的檢測算法如表1所示。

表1 檢測算法對比表

表2 不同相似性度量方法下密度聚類的效率對比

圖7 部分軌跡一致性檢測處理結(jié)果

5.2 基于航向編碼的聚類結(jié)果分析

基于航向編碼的軌跡聚類優(yōu)勢在于處理速度高于傳統(tǒng)的方法,在DBSCAN算法復(fù)雜度高的前提下,著重于簡化聚類的數(shù)據(jù),以及數(shù)據(jù)之間相似性度量的算法?；跉W式距離的DTW是將一串AIS點跡作為比對的序列,序列元素之間的距離度量采用歐式距離,這種方法優(yōu)勢在于可以識別軌跡之間細微的不同,但是計算量非常大,當軌跡數(shù)量多且單條軌跡較長時算法幾乎不可行。Hausdorff距離是一種計算最大最小值的相似性度量方法,受異常點影響非常大,實驗中采用從軌跡中固定間隔抽樣的方法來降低異常點影響以及提高效率。通過對比可以看到這兩種傳統(tǒng)的方法在效率上遠低于基于航向編碼的聚類方法。

圖8的聚類結(jié)果中同一個簇中的軌跡形狀并不完全相同,部分軌跡的部分航段的航向可能偏離其它軌跡,對于軌跡航向偏離的容忍度取決于使用DTW衡量相似度時對路徑寬度的限制以及密度聚類算法對判斷近鄰的閾值Exp的設(shè)置,本文的Exp根據(jù)航向序列的長度動態(tài)設(shè)置,能夠在軌跡長度較長時放寬對類內(nèi)相似性的要求,提高了軌跡的聚類程度。路徑寬度的限定,避免了多點對應(yīng)一點的匹配方式,這使得判定為近鄰的兩條軌跡的航向序列的長度不能相差過大,在圖中表現(xiàn)為同一個簇中的軌跡長度近似。

圖8 基于航向編碼的聚類部分結(jié)果

圖8(a)中標記了不同軌跡段的航向編碼,基于航向編碼的方法提取了軌跡中的形狀信息,保留了軌跡點之間相對的時空關(guān)系,也在聚類結(jié)果中保留了軌跡的航向信息。其中左上和右上圖中標記了部分軌跡的航向抖動的位置,得益于網(wǎng)格化的編碼過濾了抖動,避免了其對DTW算法的影響。a)左下圖的不同軌跡中5航向軌跡段與3航向軌跡段長度不同,體現(xiàn)了DTW算法的壓縮匹配效果;a)右下圖中將軌跡尾部較長一段航向為6以及7的軌跡聚為一類,體現(xiàn)了動態(tài)設(shè)置Exp的優(yōu)勢。但由于航向編碼忽略了軌跡點的地理位置信息,航向序列代表了船舶的航向狀態(tài)而不包含船舶的位置信息,因此聚類的結(jié)果中會出現(xiàn)分布在不同位置的具有相同航行模式的簇,如圖8(b)。

6 結(jié)束語

為了解決船舶共用MMSI以及定位誤差導(dǎo)致出現(xiàn)軌跡跳躍的問題,本文提出了一套檢測飛點以及斷點的方法,有效分離了軌跡點以及關(guān)聯(lián)性不強的軌跡段,為了提高該流程的效率,提出了基于狀態(tài)信息更新的觸發(fā)檢測方法。為了解決軌跡信息數(shù)據(jù)量大導(dǎo)致現(xiàn)有的針對軌跡的密度聚類方法效率不高的問題,提出在網(wǎng)格化的基礎(chǔ)上對船舶軌跡中的航向信息進行提取,從而對航向序列進行聚類的方法,同時改進DTW算法并且采用抽樣聚類的方法以進一步提高效率同時改善航向聚類的結(jié)果。

實驗中的可視化結(jié)果表明,點跡分離流程處理之后的軌跡數(shù)據(jù)中航道更加清晰合理,數(shù)據(jù)質(zhì)量明顯提高,基于航向的聚類方法有效地聚類了船舶的軌跡,且效率遠高于傳統(tǒng)算法。但航向聚類忽略了船舶的地理位置信息,使得同一個簇中的軌跡地理分布不集中,需要根據(jù)地理位置信息進一步進行分離。