基于改進DBSCAN的船舶軌跡聚類方法研究*

劉 鈺 彭鵬菲

（海軍工程大學電子工程學院 武漢 430033）

1 引言

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

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

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

2 基于改進DBSCAN的船舶軌跡聚類模型構建

2.1 船舶軌跡聚類定義

船舶軌跡是指船舶在不同港口之間從事海上運輸等任務時的航行軌跡。也就是說，船舶軌跡也就是一組軌跡的序列［10］。

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

2.2 船舶軌跡聚類的總體流程設計

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

圖1 基于AIS數據的船舶軌跡聚類流程圖

2.2.1 AIS數據預處理

AIS數據包含了特定區域內的所有船舶的歷史航行數據，而為了獲得船舶的有序數據，需要人為地根據船舶MMSI以及采集時間進行篩選排序。

1）AIS數據清洗

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

因此，需要刪除船舶前后時間差較大的數據，擬合漂移數據，剔除噪聲數據，對稀疏數據進行填補。

2）AIS數據缺失值處理

數據清洗后，容易存在前后兩個軌跡點時間間隔較長的情況，為保證軌跡的完整性和精確性，需要對缺失值進行插補處理。

2.2.2 船舶軌跡分段

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

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

其中，pi表示船舶的第 i個軌跡點，pi={ti，loni，lati，sogi，cogi}，ti表示時間，loni表示經度，lati表示維度，sogi表示ti時刻的船舶航速，cogi表示ti時刻的船舶航向。

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

圖2 船舶軌跡劃分實例

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

根據式（2），可以得到每個軌跡點的航向變化率和航速變化率，標記大于閾值的軌跡點，該類點即為特征點。

1）船舶航向信息度量

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

圖3 船舶軌跡轉向角

2）船舶航速信息度量

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

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

2.2.3 船舶軌跡相似度度量

對船舶軌跡進行相似度度量是實現船舶軌跡聚類的基礎，船舶動態信息是影響軌跡相似度度量的主要因素，例如經緯度、航向、航速等。因此，在實現船舶軌跡聚類時，將這些影響相似度度量的主要特征考慮在內，可以提高聚類效果。

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

1）航向信息度量

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

圖4 軌跡段距離計算示意圖

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

2）航速信息度量

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

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

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

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

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

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

2.2.4 改進軌跡段的DBSCAN算法

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

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

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

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

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

定義3 給定數據空間 D（Li∈D），Li為 Lj直接密度可達的條件為

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

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

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

圖6是基于改進軌跡段的DBSCAN算法流程。

圖6 基于改進軌跡段的DBSCAN算法流程圖

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

圖7 核心軌跡段搜索區域示意圖

2.2.5 獲取典型運動軌跡

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

3 實驗結果

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

圖8 測試海域范圍示意圖

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

圖9 船舶典型運動軌跡

在此范圍內，經過聚類分析得到了3類簇。為了驗證算法性能，采用緊密性（CP）這一無監督聚類指標來進行定量分析，定義如下：

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

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

表1 三種算法緊密性結果對比

從實驗結果可以看出，基于融合距離（MD）的相似度度量算法在聚類效果上比另外兩種算法好，因為基于動態時間扭曲法（DTW）是通過壓縮的方法，實現軌跡之間距離最小，并且對相似軌跡短時間內的個別差異非常敏感，無法準確衡量此類軌跡的相似度；基于最長公共子序列（LCSS）可以解決DTW方法存在的問題，但LCSS卻把關注度放在了相似軌跡上，而忽略了不相似部分。因此采用基于融合距離（MD）的相似度度量軌跡段，可以有效地進行相似軌跡的歸并與擬合，使得聚類結果更可靠。

為了更全面地體現本文算法的優勢，將三種算法在聚類上所需時間進行對比，如表2所示。

表2 三種算法的運行時間對比

由表2可知：本文使用的基于融合距離的DBSCAN聚類算法在運行時間上多于另外的兩種算法，因為改進軌跡段的DBSCAN算法使用了船舶航向和航速信息度量來進行軌跡分段，相似度度量更為復雜。但正因為考慮了更多影響船舶聚類的特征，雖然運行時間增加，但是得到了更好的聚類結果。

4 結語

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

船舶AIS數據量龐大且復雜，應考慮更為完善的數據處理方法。DBSCAN算法嚴重依賴ε和minLns參數值，而此參數值的選取又需要人為設置，如果設置不當，會造成聚類結果產生較大偏差，因此接下來應該考慮優化此算法以獲得更優結果。