基于改進(jìn)DBSCAN的船舶軌跡聚類方法研究*

劉 鈺 彭鵬菲

（海軍工程大學(xué)電子工程學(xué)院 武漢 430033）

1 引言

近年來，貿(mào)易全球化趨勢日益強(qiáng)勁，海上運(yùn)輸已經(jīng)成為貿(mào)易往來最重要的方式之一，隨著海上船舶數(shù)量急劇增加，船舶交通現(xiàn)狀日益復(fù)雜，與此同時(shí)也產(chǎn)生了大量的船舶航行軌跡，這給船舶交通管理部門的工作帶來了不小的挑戰(zhàn)，而研究這些船舶軌跡對全球海運(yùn)的運(yùn)輸分析和監(jiān)管具有重要意義。隨著技術(shù)的不斷發(fā)展，船舶自動識別系統(tǒng)（AIS）已成為全球海上實(shí)時(shí)交通信息重要來源［1］，根據(jù)AIS獲取到的大量船舶特征信息來進(jìn)行聚類分析，可以得到特定區(qū)域的船舶典型運(yùn)動軌跡，對后續(xù)該區(qū)域的船舶進(jìn)行軌跡預(yù)測打下基礎(chǔ)，并且聚類效果越好，預(yù)測準(zhǔn)確度也會越高，能夠給船舶交通管理部門在海上運(yùn)輸安全和監(jiān)管服務(wù)方面提供技術(shù)支持。

目前，國內(nèi)外研究學(xué)者對船舶軌跡聚類進(jìn)行了一系列研究。其中，利用AIS數(shù)據(jù)進(jìn)行相關(guān)研究主要存在兩種方式：基于軌跡點(diǎn)聚類以及基于軌跡段聚類?；谲壽E點(diǎn)的聚類主要以船舶位置（即經(jīng)緯度）為特征來進(jìn)行聚類簇的劃分。Liu等［2］為了提取船舶航行的主軌跡，就是通過AIS數(shù)據(jù)對船舶軌跡點(diǎn)進(jìn)行聚類。Yan等［3］通過對船舶軌跡點(diǎn)進(jìn)行分類，從而得到船舶行為狀態(tài)分別是在航和拋錨?；谲壽E點(diǎn)的聚類主要關(guān)注于船舶經(jīng)緯度的變化，而對船舶相鄰軌跡點(diǎn)之間的時(shí)空關(guān)聯(lián)性缺乏考慮?；谲壽E段的聚類主要是將船舶的部分連續(xù)軌跡點(diǎn)作為整體來進(jìn)行聚類，并且為了得到聚類簇，會對軌跡段進(jìn)行相似度度量，因此，使用基于軌跡段的聚類方法來研究船舶軌跡特征會比基于軌跡點(diǎn)的聚類方法效果更好。LEE等［4］使用線性化的方式來處理軌跡段，通過最小描述長度距離選取特征點(diǎn)并進(jìn)行相似度度量，從而獲得了軌跡分布特征。魏照坤等［5～6］同樣采用基于軌跡段的聚類方法實(shí)現(xiàn)了對船舶軌跡的線性化分。肖瀟等［7］為了獲得水域船舶的主要航路，通過選取船舶軌跡特征點(diǎn)劃分軌跡段，并結(jié)合DBSCAN算法對軌跡段聚類。周海等［8］為研究船舶行為模式特征，采用融合距離（MD）來相似度度量船舶軌跡，但在船舶聚類特征的選取上只考慮了船舶軌跡的經(jīng)緯度信息，忽略了同樣能影響船舶航行的航向、航速等動態(tài)信息，并且使用的DBSCAN算法也只對船舶軌跡點(diǎn)進(jìn)行聚類。

文獻(xiàn)［9］可知研究船舶聚類的重要特征有船舶的經(jīng)緯度、航向、航速等。因此，本文在對原始AIS數(shù)據(jù)進(jìn)行預(yù)處理后，結(jié)合航向變化率和航速變化率獲取特征點(diǎn)的方式來進(jìn)行軌跡分段，充分考慮航向信息和航速信息后，采用融合距離（MD）進(jìn)行船舶軌跡相似度度量，改進(jìn)軌跡段的DBSCAN算法可以對軌跡分段后的軌跡子段進(jìn)行聚類分析，通過實(shí)驗(yàn)分析，可以得到船舶典型運(yùn)動軌跡，實(shí)驗(yàn)對比結(jié)果顯示，本文所提聚類方法在一定程度上可以獲得更好的聚類效果。

2 基于改進(jìn)DBSCAN的船舶軌跡聚類模型構(gòu)建

2.1 船舶軌跡聚類定義

船舶軌跡是指船舶在不同港口之間從事海上運(yùn)輸?shù)热蝿?wù)時(shí)的航行軌跡。也就是說，船舶軌跡也就是一組軌跡的序列［10］。

船舶軌跡聚類是指將船舶航行軌跡按照相似度分成不同的類或簇，相似度高的軌跡歸為同一簇，并且不同簇之間的軌跡特征差別較大。

2.2 船舶軌跡聚類的總體流程設(shè)計(jì)

通過比較現(xiàn)有文獻(xiàn)可知，通過對船舶AIS數(shù)據(jù)的分析，可以提取軌跡的重要特征。采用軌跡聚類方法進(jìn)行軌跡分析會遇到兩類問題：軌跡相似度度量，以及選擇適合的聚類算法。

圖1 基于AIS數(shù)據(jù)的船舶軌跡聚類流程圖

2.2.1 AIS數(shù)據(jù)預(yù)處理

AIS數(shù)據(jù)包含了特定區(qū)域內(nèi)的所有船舶的歷史航行數(shù)據(jù)，而為了獲得船舶的有序數(shù)據(jù)，需要人為地根據(jù)船舶MMSI以及采集時(shí)間進(jìn)行篩選排序。

1）AIS數(shù)據(jù)清洗

數(shù)據(jù)清洗：刪除各種異常數(shù)據(jù)，消除對后續(xù)軌跡建模的影響。

因此，需要刪除船舶前后時(shí)間差較大的數(shù)據(jù)，擬合漂移數(shù)據(jù)，剔除噪聲數(shù)據(jù)，對稀疏數(shù)據(jù)進(jìn)行填補(bǔ)。

2）AIS數(shù)據(jù)缺失值處理

數(shù)據(jù)清洗后，容易存在前后兩個(gè)軌跡點(diǎn)時(shí)間間隔較長的情況，為保證軌跡的完整性和精確性，需要對缺失值進(jìn)行插補(bǔ)處理。

2.2.2 船舶軌跡分段

船舶軌跡分段是在原始航行軌跡中選取一些特征點(diǎn)，并且保證這些特征點(diǎn)之間的連線與原始軌跡盡可能地相似。在進(jìn)行軌跡分段時(shí)，要盡量滿足完整性和簡潔性兩個(gè)原則。

由船舶軌跡定義可知，大量船舶軌跡點(diǎn)組成了船舶軌跡，因此船舶軌跡序列可表示為

其中，pi表示船舶的第 i個(gè)軌跡點(diǎn)，pi={ti，loni，lati，sogi，cogi}，ti表示時(shí)間，loni表示經(jīng)度，lati表示維度，sogi表示ti時(shí)刻的船舶航速，cogi表示ti時(shí)刻的船舶航向。

船舶軌跡示意圖如圖2所示。假設(shè) p1-p9為某條船舶軌跡的數(shù)據(jù)采集點(diǎn)，船舶沿著p1-p9實(shí)線運(yùn)動。如果將p1-p9全部作為船舶軌跡的特征點(diǎn)，雖然可以使船舶軌跡完整性更大程度的保留，但是會因?yàn)樘卣鼽c(diǎn)選取過多，計(jì)算復(fù)雜，時(shí)間消耗大；如果只將 p1點(diǎn)、p5點(diǎn)、p9點(diǎn)作為特征點(diǎn)，雖然保證了較好的簡潔性，但會丟失船舶原始軌跡的基本特征，不能保證軌跡的完整性。因此，最終選擇 p1點(diǎn)、p4點(diǎn)、p6點(diǎn)、p8點(diǎn)作為特征點(diǎn)，這樣得到的船舶軌跡 p1-p4-p6-p8能夠同時(shí)保證完整性和簡潔性。

圖2 船舶軌跡劃分實(shí)例

由圖2可知，選擇特征點(diǎn)對于進(jìn)行船舶軌跡分段非常重要。根據(jù)文獻(xiàn)［11］所提計(jì)算方法獲取特征點(diǎn)，具體公式如下：

根據(jù)式（2），可以得到每個(gè)軌跡點(diǎn)的航向變化率和航速變化率，標(biāo)記大于閾值的軌跡點(diǎn)，該類點(diǎn)即為特征點(diǎn)。

1）船舶航向信息度量

提前設(shè)定航向閾值來完成船舶航向信息的度量，由文獻(xiàn)［12］可知，船舶航向轉(zhuǎn)向角的定義：相鄰船位連接的兩個(gè)軌跡子段的航向差。在圖3中，p3-p4和 p4-p5是兩條軌跡子段，設(shè)定航向轉(zhuǎn)向角閾值為θmax，將相鄰船位船舶軌跡航向以及時(shí)間間隔代入式（2），就可以得到兩條軌跡子段的航向變化率θ。將θ與θmax對比，如果θ≥θmax，則 p4點(diǎn)為特征點(diǎn)；如果θ＜θmax，就繼續(xù)循環(huán)采樣，直到遍歷所有軌跡點(diǎn)。

圖3 船舶軌跡轉(zhuǎn)向角

2）船舶航速信息度量

設(shè) p4點(diǎn)的鄰域距離為（dmin，dmax)，設(shè)定船舶航速閾值為vmax，假設(shè) p4點(diǎn)的航速變化率為v，如果p4點(diǎn)的航速變化率與其他任意點(diǎn)的航速變化率的差的絕對值≥vmax，那么 p4點(diǎn)就叫變速點(diǎn)，也是需要被選定的特征點(diǎn)。如果p4點(diǎn)的航速變化率與其他任意點(diǎn)的航速變化率的差的絕對值＜vmax，那么繼續(xù)采樣，重復(fù)上述操作，直到遍歷所有軌跡點(diǎn)。

通過上述兩種信息度量方法可以確定特征點(diǎn)，連接相鄰特征點(diǎn)，即可得到船舶軌跡子段。

2.2.3 船舶軌跡相似度度量

對船舶軌跡進(jìn)行相似度度量是實(shí)現(xiàn)船舶軌跡聚類的基礎(chǔ)，船舶動態(tài)信息是影響軌跡相似度度量的主要因素，例如經(jīng)緯度、航向、航速等。因此，在實(shí)現(xiàn)船舶軌跡聚類時(shí)，將這些影響相似度度量的主要特征考慮在內(nèi)，可以提高聚類效果。

針對不同的實(shí)際問題，運(yùn)用不同的相似度度量方法會產(chǎn)生不同的聚類效果［13］。因此，需要根據(jù)船舶的特點(diǎn)來選擇軌跡相似度度量方法。本文通過對航向和航速信息度量，從而對船舶軌跡進(jìn)行相似度度量。假設(shè)船舶軌跡分段后的特征點(diǎn)表達(dá)式為T={p1，p2， ···，pn} 。

1）航向信息度量

由圖4可知，Ta和Tb表示兩條軌跡段；Pa1，Pb1和 Pa2，Pb2分別為軌跡段Ta，Tb的起點(diǎn)和終點(diǎn)；為Pa1，Pa2在Tb上的投影點(diǎn)，θ表示Ta和Tb之間的夾角。

圖4 軌跡段距離計(jì)算示意圖

Ta和 Tb之間的距離可表示為 d(Ta，Tb)=d∥+d⊥+dθ，其中 d∥表示水平距離，d⊥表示垂直距離，dθ表示角度距離，定義如下：

2）航速信息度量

文獻(xiàn)［8］提出一種融合距離（the merge distance，MD）來進(jìn)行軌跡段相似度度量，這種距離計(jì)算方法表示兩軌跡段融合后的距離最短。圖5為融合距離求最短軌跡段示意圖。

圖5 融合距離求最短軌跡段示意圖

如圖5所示，Tc和Td表示兩條軌跡段，Tc和Td分 別 由 點(diǎn) 序 列 {pc1，pc2，···，pcm} ，{pd1，pd2，···，pdn} 構(gòu)成，d(Pci，Pdj)表示兩點(diǎn)之間的歐氏距離，其中1≤i≤m ，1≤j≤n，L(Tc)和 L(Td)分別表示軌跡段Tc和Td的長度；S(Tc，Td)表示軌跡段Tc和Td的最短超軌跡，用L(Tc，Td)表示其長度，即為最短超距離。

假設(shè)Tc[1 ， i]和Td[1 ， j] 分別為{pc1，pc2， ···，pci}和 {pd1，pd2，···，pdj}的超軌跡，用和表示，那么和中的最小值即為最短超距離L(Tc，Td)。

根據(jù)文獻(xiàn)［8］，軌跡段Tc和Td之間的融合距離 MD(Tc，Td)表示為

一般情況下，融合距離MD(Tc，Td)會大于或等于 L(Tc)或者 L(Td)。將最短超距離 L(Tc，Td)除以L(Tc)與L(Td)和的平均值是為了進(jìn)行歸一化處理，此結(jié)果減1，MD(Tc，Td)的值也大于0。實(shí)際上，如果從同一軌跡上采樣到軌跡段Tc和Td，那么兩者的融合距離MD(Tc，Td)應(yīng)接近于0，因?yàn)榇藭r(shí)軌跡段Tc和Td的長度 L(Tc)、L(Td)和最短超距離L(Tc，Td)基本一致。因此，融合距離可以用在船舶軌跡相似度度量上。

2.2.4 改進(jìn)軌跡段的DBSCAN算法

DBSCAN是一種最典型的基于密度的空間聚類算法［14］。該算法以劃分簇的形式來聚類相似度高的軌跡，而簇的定義是密度相連的點(diǎn)的最大集合。因此，DBSCAN算法可以將數(shù)據(jù)密度足夠的區(qū)域劃分為簇，并且對噪聲數(shù)據(jù)較為不敏感。

此前，研究人員大多使用DBSCAN算法對軌跡點(diǎn)進(jìn)行聚類，而文獻(xiàn)［4］、文獻(xiàn)［15］、文獻(xiàn)［16］、文獻(xiàn)［17］則是利用改進(jìn)軌跡段的DBSCAN算法進(jìn)行聚類。基于改進(jìn)軌跡段的DBSCAN算法的思想步驟：輸入為所有軌跡段，并且將其全部標(biāo)記為未聚類，讀取某條軌跡段，然后根據(jù)ε鄰域和minLns閾值來判斷此軌跡段是否為核心軌跡段。如果是，則將此軌跡段標(biāo)記為核心軌跡段，那么此核心軌跡段的ε鄰域就形成了一個(gè)新簇C，然后將ε鄰域內(nèi)的所有點(diǎn)都加入簇C中，簇C通過ε鄰域的核心軌跡段不斷向外延伸判斷，直到簇不再增長為止。基于軌跡段的DBSCAN算法的相關(guān)定義如下

定義1 Li鄰域的公式化定義為

其中，ε表示軌跡段的密度半徑；D為軌跡子段Li、Lj的數(shù)據(jù)空間，即 Li、Lj∈D ，與 Li的空間距離不超過ε的所有軌跡子段構(gòu)成了Li的鄰域。

定義2 對于Li∈D，Li為核心軌跡段的條件為：Li的鄰域需滿足

定義3 給定數(shù)據(jù)空間 D（Li∈D），Li為 Lj直接密度可達(dá)的條件為

其中，式（11）表示 Li在 Lj的 ε鄰域范圍內(nèi)，式（12）表示Lj是核心軌跡段。

定義4 給定數(shù)據(jù)空間D（Li∈D），Ln為L1的密度可達(dá)的條件為：存在 L1，L2，L3，…，Li，…，Ln(1≤i≤n)，使得所有的 Li+1都是從 Li出發(fā)的關(guān)于ε和minLns的直接密度可達(dá)。

定義5 給定數(shù)據(jù)空間 D（Li，Lj∈D），Li和Lj是密度相連的條件為：存在任意軌跡段 Lk（Lk∈D），使得Li和Lj都是從Lk出發(fā)的關(guān)于ε和minLns的密度可達(dá)［18］。

圖6是基于改進(jìn)軌跡段的DBSCAN算法流程。

圖6 基于改進(jìn)軌跡段的DBSCAN算法流程圖

經(jīng)過上述算法流程可知，想要最終確定簇C，必須要遍歷所有軌跡段。圖7為核心軌跡段搜索區(qū)域示意圖。從圖中可知，搜索核心軌跡段的區(qū)域是一個(gè)半徑為ε、密度閾值為minLns的外包橢圓，此時(shí)橢圓區(qū)域內(nèi)的所有軌跡段構(gòu)成了最終的簇。

圖7 核心軌跡段搜索區(qū)域示意圖

2.2.5 獲取典型運(yùn)動軌跡

為了獲得船舶的典型運(yùn)動軌跡，在經(jīng)過改進(jìn)DBSCAN算法劃分軌跡段簇后，需要對每個(gè)簇中所包含的全部軌跡段的經(jīng)度、緯度、航向和航速取平均值。

3 實(shí)驗(yàn)結(jié)果

本文從MarineCadastre.gov下載船舶的AIS數(shù)據(jù)，為了保證軌跡聚類的規(guī)律性，篩選出具有非對抗行為的商船和民船作為實(shí)驗(yàn)對象。因此下載了2019年8月27日至2019年8月28日在經(jīng)緯度范圍為（132.98E，34.01N）～（133.20E，34.16N）內(nèi)的200條船的184998條軌跡數(shù)據(jù)進(jìn)行聚類測試。

圖8 測試海域范圍示意圖

根據(jù)航向信息和航速信息劃分軌跡段后，得到了1564條軌跡子段，再利用本文方法對軌跡子段進(jìn)行相似度度量和聚類。DBSCAN算法對ε和minLns的值比較敏感，并且ε和minLns參數(shù)值需要人為選擇［19］。為了聚類效果更好，對于值的選取需要反復(fù)試驗(yàn)，經(jīng)過多次試驗(yàn)，選定ε=0.003n mile，密度閾值minLns=7。根據(jù)此參數(shù)最后得到的船舶的典型運(yùn)動軌跡如圖9所示。

圖9 船舶典型運(yùn)動軌跡

在此范圍內(nèi)，經(jīng)過聚類分析得到了3類簇。為了驗(yàn)證算法性能，采用緊密性（CP）這一無監(jiān)督聚類指標(biāo)來進(jìn)行定量分析，定義如下：

其中，Ω為聚類后所形成的簇，K為聚類數(shù)量，wi為第i個(gè)簇。緊密性（CP）主要是計(jì)算每一個(gè)簇內(nèi)各點(diǎn)到聚類中心的平均距離，CP值越低則表示簇內(nèi)聚類的距離越近，那么聚類效果也越好。

將本文所用的融合距離（MD）與文獻(xiàn)［10］所用的基于最長公共子序列（LCSS）、文獻(xiàn)［20］所用的基于動態(tài)時(shí)間扭曲法（DTW）進(jìn)行緊密性對比，結(jié)果如表1所示。

表1 三種算法緊密性結(jié)果對比

從實(shí)驗(yàn)結(jié)果可以看出，基于融合距離（MD）的相似度度量算法在聚類效果上比另外兩種算法好，因?yàn)榛趧討B(tài)時(shí)間扭曲法（DTW）是通過壓縮的方法，實(shí)現(xiàn)軌跡之間距離最小，并且對相似軌跡短時(shí)間內(nèi)的個(gè)別差異非常敏感，無法準(zhǔn)確衡量此類軌跡的相似度；基于最長公共子序列（LCSS）可以解決DTW方法存在的問題，但LCSS卻把關(guān)注度放在了相似軌跡上，而忽略了不相似部分。因此采用基于融合距離（MD）的相似度度量軌跡段，可以有效地進(jìn)行相似軌跡的歸并與擬合，使得聚類結(jié)果更可靠。

為了更全面地體現(xiàn)本文算法的優(yōu)勢，將三種算法在聚類上所需時(shí)間進(jìn)行對比，如表2所示。

表2 三種算法的運(yùn)行時(shí)間對比

由表2可知：本文使用的基于融合距離的DBSCAN聚類算法在運(yùn)行時(shí)間上多于另外的兩種算法，因?yàn)楦倪M(jìn)軌跡段的DBSCAN算法使用了船舶航向和航速信息度量來進(jìn)行軌跡分段，相似度度量更為復(fù)雜。但正因?yàn)榭紤]了更多影響船舶聚類的特征，雖然運(yùn)行時(shí)間增加，但是得到了更好的聚類結(jié)果。

4 結(jié)語

本文考慮到船舶AIS數(shù)據(jù)特征，結(jié)合航向信息和航速信息來軌跡分段，利用融合距離對軌跡段相似度度量，以及基于軌跡段的DBSCAN算法來聚類分析，對比另外兩種相似度度量方法可以得到更好的聚類效果，通過實(shí)驗(yàn)可以獲得聚類后各簇內(nèi)船舶的典型運(yùn)動軌跡。

船舶AIS數(shù)據(jù)量龐大且復(fù)雜，應(yīng)考慮更為完善的數(shù)據(jù)處理方法。DBSCAN算法嚴(yán)重依賴ε和minLns參數(shù)值，而此參數(shù)值的選取又需要人為設(shè)置，如果設(shè)置不當(dāng)，會造成聚類結(jié)果產(chǎn)生較大偏差，因此接下來應(yīng)該考慮優(yōu)化此算法以獲得更優(yōu)結(jié)果。