李 湘 劉 奕

(武漢理工大學(xué)航運(yùn)學(xué)院1) 武漢 430063) (內(nèi)河航運(yùn)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室2) 武漢 430063)(國家水運(yùn)安全工程技術(shù)研究中心3) 武漢 430063)

0 引 言

船舶軌跡由一系列二維經(jīng)緯度點(diǎn)構(gòu)成，因此船舶相似度度量方法能夠測量不同軌跡間的距離[1-3]．在歐式距離測量算法中，要求船舶軌跡點(diǎn)的長度必須對齊，即每艘船的軌跡點(diǎn)數(shù)量必須相同，而在實(shí)際中因每艘船的航速不同導(dǎo)致AIS基站獲取每艘船舶的AIS報(bào)文數(shù)量也各不相同，因此該算法無法很好的應(yīng)用在船舶軌跡相似性度量中．Hausdorff距離、隱馬爾科夫模型無需要求船舶軌跡點(diǎn)數(shù)量必須相同，但二者卻不能很好的對船舶軌跡進(jìn)行相似度度量，存在較大的測量誤差．最長公共子序列(LCSS)算法適用于測量形狀相似度，且計(jì)算時(shí)間開銷較大．動態(tài)時(shí)間規(guī)整(DTW)算法能夠計(jì)算出船舶軌跡間的形狀相似度與距離相似度，且該算法被廣大學(xué)者用于度量船舶軌跡間相似度，進(jìn)行語音信號分類識別、時(shí)間序列信號分析和手寫信號識別分類分析．Liu等[4]運(yùn)用DTW度量船舶軌跡間的相似度距離并根據(jù)該距離對船舶軌跡進(jìn)行聚類以此挖掘船舶習(xí)慣航路．Li等[5]運(yùn)用DTW度量船舶軌跡間距離并提出多步聚類算法用于船舶異常軌跡識別．Zhao等[6]將船舶軌跡形狀結(jié)合DTW算法用于分析船舶軌跡間距離并挖掘船舶習(xí)慣航路．DTW算法雖被廣大學(xué)者應(yīng)用于船舶軌跡間相似度度量，但該算法由于其復(fù)雜度為O(n2)，且在應(yīng)用于海量船舶AIS數(shù)據(jù)中存在計(jì)算時(shí)間開銷過大的問題．基于此，文中相似度度量算法能夠?qū)Υ败壽E進(jìn)行快速特征提取，并快速測量船舶軌跡間相似度，提升了相似度度量算法的速度性能，且不影響最終聚類性能．

在將海量AIS數(shù)據(jù)結(jié)合聚類算法分析船舶運(yùn)動特征、船舶整體運(yùn)動規(guī)律并為挖掘船舶習(xí)慣航路、探索發(fā)現(xiàn)、分析船舶異常行為的過程中，密度聚類算法(DBSCAN)被廣泛應(yīng)用．Zhen等[7]利用AIS數(shù)據(jù)結(jié)合密度聚類算法挖掘船舶會遇場景．Pallottad等[8]提出一種基于密度聚類的偏差變化算法結(jié)合船舶轉(zhuǎn)向點(diǎn)用以挖掘船舶交通流習(xí)慣航路．Yan等[9]提出一種基于密度聚類的非監(jiān)督學(xué)習(xí)算法用以識別船舶停止與航行點(diǎn)特征．Liu等[10]對密度聚類算法進(jìn)行改進(jìn)并考慮船舶軌跡點(diǎn)速度與方向特征用以提取船舶正常航行軌跡．

由于密度聚類算法其自身存在參數(shù)半徑r與最少點(diǎn)數(shù)minpts難以確定，且該算法人為操作量較大．文獻(xiàn)[11]雖提出了自適應(yīng)密度聚類算法，但在確定參數(shù)r與minpts過程中的擬合分布算法導(dǎo)致密度聚類存在普適性問題，導(dǎo)致該算法無法適用于其他水域．因此本文為對這一缺陷采用核密度估計(jì)算法改進(jìn)自適應(yīng)密度聚類，完全依據(jù)原始數(shù)據(jù)自身特性，從數(shù)據(jù)自身實(shí)際出發(fā)對數(shù)據(jù)分布進(jìn)行擬合進(jìn)而確定密度聚類算法中的r與minpts參數(shù)，提升了算法的智能性與適用性，且不影響最終的密度聚類性能，并以長江南槽交匯水域AIS數(shù)據(jù)作為算法驗(yàn)證集，分別驗(yàn)證了快速相似度度量與改進(jìn)自適應(yīng)密度聚類算法．

1 快速相似度度量方法

船舶軌跡間的相似度是對船舶軌跡群聚類分析的重要因素，目前存在很多測量軌跡間相似度的方法，動態(tài)時(shí)間規(guī)整(dynamic time warping，DTW)在測量船舶軌跡間相似性領(lǐng)域中應(yīng)用較多且性能較其他算法突出，DTW計(jì)算公式為

DTW(1,1)=d(1,1)

DTW(i,j)=d(i,j)+min[DTW(i,j-1),

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

(1)

式中：i,j分別為相似度距離矩陣中的行列值．

但DTW仍需要遍歷計(jì)算所有對應(yīng)點(diǎn)之間的距離，其復(fù)雜度為O(N2)，在涉及計(jì)算大量船舶軌跡間相似度時(shí)，該方法存在復(fù)雜度過高，計(jì)算時(shí)間過長的缺陷，不利于快速提取船舶軌跡間相似程度．針對DTW復(fù)雜度過高的問題，本文提出了一種基于船舶軌跡經(jīng)緯度均值特征的新型快速相似度度量方法．快速相似度度量算法流程見圖1．

圖1 快速相似度度量算法

方法建模過程如下.

步驟1提取AIS數(shù)據(jù)中各船舶軌跡經(jīng)緯度信息，為

route1=[[X1,y1],[X2,y2],…]

…

(2)

式中：X為經(jīng)度；y為緯度．

對各船舶軌跡經(jīng)緯度進(jìn)行均值處理，將多點(diǎn)二維信息轉(zhuǎn)換為單點(diǎn)二維信息，為

route1=[Xmean,ymean]

…

步驟2設(shè)定方向判別閾值 本實(shí)驗(yàn)水域?yàn)殚L江南槽交匯水域，水域經(jīng)度范圍為東經(jīng)121.68°至東經(jīng)121.75°，水域緯度范圍為北緯31.27°至北緯31.35°，水域航道見圖2．

圖2 航道水域

圖2中箭頭所指向的豎線為方向判別閾值，該豎線對應(yīng)經(jīng)度121.70°，將其設(shè)定為方向判別閾值，若軌跡起點(diǎn)經(jīng)度大于121.70°，則判定該船舶自右向左航行，對該船舶軌跡提取的二維特征信息增加-1值作為方向判別特征，即

routeright=[Xmean,ymean,-1];

若軌跡起點(diǎn)經(jīng)度小于121.70°，則該船舶自左向右航行，則對該船舶軌跡提取的二維信息增加1值作為方向判別特征，即

routeleft=[Xmean,ymean,1];

對所有軌跡均按照上述方式增加方向特征信息．船舶間的相似度度量轉(zhuǎn)換為兩兩軌跡間三維信息特征的歐式距離，即兩船舶軌跡間相似度度量值的平方

(方向值′-方向值″)2

步驟3方法驗(yàn)證 提取該水域中120條船舶軌跡的AIS信息，總計(jì)39 241對經(jīng)緯坐標(biāo)，且該水域航道為兩路交叉水域航道，且同一航道內(nèi)存在東西雙向航行船舶即雙向航路，因此，交叉水域內(nèi)按照航道的不同將船舶軌跡分類兩類，同一航道內(nèi)又存在雙向航路，所以最終將軌跡聚類簇?cái)?shù)設(shè)定為四類，同時(shí)為驗(yàn)證快速相似度度量方法的適用性，本實(shí)驗(yàn)將快速相似度度量方法結(jié)合k-means聚類(k=4)與DTW結(jié)合k-means(k=4)進(jìn)行聚類效果對比與運(yùn)算速度分析, 聚類效果對比見圖3～4．

圖4 k-means結(jié)合DTW

由圖3～4可知：在驗(yàn)證快速相似度度量方法的適用性時(shí)，快速相似度度量方法結(jié)合k-means與DTW結(jié)合k-means的最終聚類效果相同，均能夠?qū)⒔徊嫠虿煌篮脚c各自航道內(nèi)不同方向的船舶軌跡群區(qū)分開來，得到最終的四類簇．

在驗(yàn)證快速相似度度量運(yùn)算速度的過程中，本實(shí)驗(yàn)分別對兩種測量方法運(yùn)行6次，觀測運(yùn)算時(shí)間，見表1．

表1 運(yùn)算時(shí)間表

由表1可知：快速相似度度量算法相比較傳統(tǒng)DTW算法，聚類速度提升近5 061倍．在計(jì)算處理大數(shù)據(jù)船舶軌跡時(shí)，該方法可大幅縮短聚類計(jì)算時(shí)間且不影響聚類性能．

2 改進(jìn)自適應(yīng)密度聚類

密度聚類可用于對船舶軌跡分析、挖掘船舶習(xí)慣航路，該算法可快速識別具有相似特征的船舶軌跡簇，且能夠剔除噪聲、船舶離群軌跡點(diǎn)等．但該算法存在參數(shù)r與minpts難以確定的問題，需要多次人工實(shí)驗(yàn)以獲得最優(yōu)參數(shù)．本文提出改進(jìn)自適應(yīng)密度聚類算法以提升算法性能，流程圖見圖5．

圖5 改進(jìn)自適應(yīng)密度聚類流程圖

DBSCAN算法原理：基于密度的空間聚類算法能根據(jù)樣本分布的緊密程度將數(shù)據(jù)分為幾類簇，以數(shù)據(jù)集在空間分布的稠密程度為標(biāo)準(zhǔn)進(jìn)行聚類處理，若某一區(qū)域中樣本的密度值大于設(shè)定的某個(gè)閾值，則將該樣本劃入與之相近的類簇中．密度聚類能夠識別所有密度相連的樣本集，并將這些樣本集聚成多個(gè)類簇，其主要特點(diǎn)為：能夠發(fā)現(xiàn)任意不規(guī)則形狀的簇、對噪聲數(shù)據(jù)不敏感．

1) 參數(shù)選取 DBSCAN算法中有兩個(gè)重要的參數(shù)鄰域半徑r和最少數(shù)據(jù)量minpts需要人為確定，在設(shè)定這兩個(gè)參數(shù)的過程中，不同的參數(shù)組合將對最終聚類效果產(chǎn)生很大影響，特別是在對大量船舶軌跡數(shù)據(jù)進(jìn)行聚類時(shí)，參數(shù)的確定較為困難，且參數(shù)選取范圍較廣泛，只能由操作人員逐個(gè)嘗試選取最優(yōu)結(jié)果．

根據(jù)參考文獻(xiàn)[11]中參數(shù)確定的方法包括：運(yùn)用統(tǒng)計(jì)學(xué)方法計(jì)算兩個(gè)參數(shù)之間最優(yōu)的參數(shù)選擇．具體確定方法如下：在確定鄰域半徑r的過程中，鄰域半徑r能夠保證該元素成為核心點(diǎn)，在理想化的密度聚類過程中，數(shù)據(jù)較為集中的高密度區(qū)域內(nèi)數(shù)據(jù)都能夠各自成為核心點(diǎn)，并且各數(shù)據(jù)能夠匯聚成簇使得該類簇的密度最大．針對一個(gè)單獨(dú)的數(shù)據(jù)而言，在給定minpts時(shí)，最小半徑r能使得該數(shù)據(jù)成為核心數(shù)據(jù)點(diǎn)并且保證類簇成形，因此在給定minpts條件下最優(yōu)的半徑r能使得最多的數(shù)據(jù)點(diǎn)成為核心數(shù)據(jù)點(diǎn)并且類簇成形．

根據(jù)這一原理，首先采取文獻(xiàn)[11]對半徑數(shù)據(jù)集樣本點(diǎn)采取逆高斯概率密度函數(shù)(3)擬合后求取半徑數(shù)據(jù)集核心距離的眾數(shù)(6)以確定最終半徑參數(shù)r:

(3)

(4)

(5)

(6)

式中：逆高斯分布中的λ和μ均分別由最大似然估計(jì)法(4)和(5)獲得，經(jīng)過計(jì)算得出r=0.002 26．

在最小元素?cái)?shù)量minpts參數(shù)確定過程中，minpts的取值范圍是從1開始增加到樣本總數(shù)的整數(shù)值，當(dāng)minpts為1時(shí)，單個(gè)數(shù)據(jù)也可成為一簇，隨著minpts數(shù)量的持續(xù)增加，聚類過程中的可以看做是每個(gè)子類簇持續(xù)合并周圍數(shù)據(jù)的過程，但隨著minpts數(shù)量逐漸增加，許多較近的類簇之間被互相吸納合并為一類，因此在聚類在達(dá)到穩(wěn)定理想態(tài)之前，類簇之間合并速度較快，類簇和噪聲的數(shù)量均大幅減少，隨著聚類狀態(tài)趨向理想穩(wěn)態(tài)化，各簇之間的距離相對較遠(yuǎn)，類簇和噪聲的數(shù)量趨于穩(wěn)定，在達(dá)到理想狀態(tài)時(shí)，最終類簇和噪聲數(shù)量維持恒定．由圖6觀測到類簇和噪聲數(shù)量趨于平穩(wěn)處的minpts為13．

圖6 類簇和噪聲數(shù)量

因此，將0.002 26和13作為密度聚類的r和minpts參數(shù)，聚類結(jié)果見圖7．

圖7 DBSCAN結(jié)合逆高斯分布

實(shí)驗(yàn)結(jié)果圖7表明采用文獻(xiàn)中[11]所提供的自適應(yīng)密度聚類算法無法將交叉水域不同道航與各航道內(nèi)不同方向的船舶軌跡群區(qū)分開來，僅得到兩類聚類簇．經(jīng)分析得出結(jié)論該算法強(qiáng)制采用逆高斯分布擬合密度聚類過程中的半徑分布而沒有從實(shí)際數(shù)據(jù)出發(fā)對半徑分布進(jìn)行擬合．

因此針對文獻(xiàn)[11]中方法存在聚類性能不足的問題，文中考慮更換擬合函數(shù)算法．經(jīng)查閱資料，核密度估計(jì)算法存在普適性優(yōu)點(diǎn)，包括擬合過程完全從數(shù)據(jù)自身特性出發(fā)，利用數(shù)據(jù)自身的實(shí)際值去估計(jì)總體樣本的概率密度函數(shù)，依據(jù)樣本點(diǎn)對應(yīng)的概率密度函數(shù)值越大越接近峰值，則該樣本點(diǎn)附近的數(shù)據(jù)越集中且該樣本極具代表性的這一原理，文中采取核密度估計(jì)擬合核心距離半徑r的概率密度函數(shù)．核密度估計(jì)公式：

(7)

式中：n為數(shù)據(jù)個(gè)數(shù)；k為本文采用的高斯核函數(shù)；Xi為不同的半徑r；h為本文采取的平均積分最小誤差帶寬,

(8)

其中：σ為數(shù)據(jù)r樣本方差；n為數(shù)據(jù)個(gè)數(shù)．

根據(jù)概率密度函數(shù)的實(shí)際意義可知，在概率密度函數(shù)峰值處左右的數(shù)據(jù)較為集中，原始數(shù)據(jù)集中數(shù)據(jù)點(diǎn)越稠密的區(qū)間內(nèi)概率密度函數(shù)值越大．依據(jù)這一原理，在給定minpts下，文中從多個(gè)實(shí)際核心距離r為出發(fā)點(diǎn)，利用核密度估計(jì)求取核心距離r的概率密度函數(shù)，將核心距離r帶入到概率密度函數(shù)中，概率密度函數(shù)值越大其對應(yīng)的核心距離r代表數(shù)據(jù)越集中且類簇成形，所求得最大概率密度函數(shù)值對應(yīng)的r即為最優(yōu)核心距離．核密度擬合見圖8．

圖8 核密度估計(jì)擬合

因此在給定minpts時(shí)，最小成簇半徑

r=max(f(x),x∈[r1,r2,…,rn])．

繪制在類簇和噪聲數(shù)量即將接近穩(wěn)定態(tài)時(shí)參數(shù)minpts圖，見圖9．

圖9 類簇和噪聲數(shù)量

由圖9可知：在確定參數(shù)minpts的過程中，圖中minpts在17至18位置附近處類簇和噪聲數(shù)量共同趨向穩(wěn)定，實(shí)驗(yàn)采取minpts=17時(shí)作為密度聚類中的最少元素?cái)?shù)量，應(yīng)用核密度估計(jì)minpts=17時(shí)對應(yīng)的半徑r為0.003 3，在密度聚類過程中對軌跡間進(jìn)行相似度度量時(shí)仍采用本文中快速相似度度量方法計(jì)算船舶軌跡間的相似度，其聚類結(jié)果見圖10．

圖10 DBSCAN結(jié)合KDE

由圖7與圖10對比可以觀測到結(jié)合核密度估的DBSCAN聚類結(jié)果比結(jié)合文獻(xiàn)[11]中逆高斯得到的聚類結(jié)果好，結(jié)合核密度估計(jì)的自適應(yīng)密度聚類算法可將不同航道以及航道內(nèi)不同航向的船舶軌跡明顯區(qū)分開來，而結(jié)合逆高斯分布密度聚類算法無法區(qū)分不同航道內(nèi)的船舶軌跡．若無法區(qū)分不同航道內(nèi)的船舶軌跡將對探索各航道內(nèi)船舶習(xí)慣航路以及研究船舶安全航行造成重大影響．

3 結(jié) 論

1) 文中提出的一種基于經(jīng)緯度均值和方向閾值組合的快速相似度度量方法，在不影響聚類性能的前提下對船舶軌跡間進(jìn)行相似度度量，縮短測量時(shí)間，減小內(nèi)存開支，能夠針對數(shù)量龐大、運(yùn)算復(fù)雜的AIS數(shù)據(jù)進(jìn)行快速計(jì)算．

2) 針對DBSCAN密度聚類中的參數(shù)minpts與r需要多次人為嘗試設(shè)定的問題，利用統(tǒng)計(jì)學(xué)與核密度估計(jì)來確定最優(yōu)參數(shù)minpts與r，該方法快速高效．

3) 通過應(yīng)用本文相似度度量方法能夠?qū)粎R水域交通流中船舶軌跡進(jìn)行快速相似度度量，對U形水域以及其他異形水域的快速相似度度量方法還需進(jìn)一步研究；在密度聚類過程中針對交通流過于集中的水域，如何進(jìn)行更加精準(zhǔn)的提取軌跡類簇、交通流特征與船舶異常軌跡識別是下一步的重點(diǎn)研究方向．