基于DBTCAN算法的船舶軌跡聚類與航路識別

楊家軒，劉元

(大連海事大學 a.航海學院；b.遼寧省航海安全保障重點實驗室，遼寧 大連 116026)

0 引 言

在經(jīng)濟全球化背景下，海運在國際貿(mào)易中的作用越來越重要?，F(xiàn)在超過90%的國際貿(mào)易是通過海運完成的，沿海和港口附近的船舶密度日益增大，船舶運輸條件日益復雜，對水域通航管理能力的要求也日益提高。船舶自動識別系統(tǒng)(automatic identification system, AIS)是獲取船舶航行數(shù)據(jù)、分析海上船舶行為特征和交通流信息的重要數(shù)據(jù)來源。對AIS數(shù)據(jù)進行聚類分析，可以為海上船舶行為和交通流特征的提取、航線規(guī)劃、海上船舶異常行為檢測等技術的開發(fā)和應用提供基本的手段和關鍵的方法，為海事監(jiān)管機構的決策提供支持和科學依據(jù)。

船舶軌跡聚類的目的是找到那些具有相同運動模式的軌跡，通過分析船舶運動模式和軌跡特征信息來確定軌跡之間的相似度，然后將相似度較高的軌跡歸為一類。目前，軌跡聚類的研究主要分兩類：對整條軌跡進行聚類;先對軌跡分段再對軌跡段進行聚類。LEE等將軌跡劃分成多個子軌跡段，采用最小描述長度(the minimum description length, MDL)來計算各軌跡段之間的相似度，最后結合軌跡聚類框架從真實的軌跡數(shù)據(jù)中提取公共子軌跡段。陳錦陽等先根據(jù)軌跡特征點將整條軌跡進行分割得到子軌跡段，然后利用基于改進Hausdorff距離的軌跡聚類算法對子軌跡段進行聚類。江玉玲等利用船位轉(zhuǎn)向角和航速變化量作為信息度量對船舶軌跡進行分段，采用離散Frechet 距離作為軌跡相似度度量對子軌跡段進行聚類得到船舶運動典型軌跡。軌跡段聚類在分段的過程中會舍棄軌跡段內(nèi)部的特征點，可能丟失軌跡的局部關鍵運動特征，而且大多數(shù)分段方法只考慮單一指標，主觀性太強，無法找到最優(yōu)的分段方法。LI等以船舶軌跡整體為聚類對象，建立軌跡之間的空間距離矩陣，實現(xiàn)不同空間分布和方向的軌跡聚類。牟軍敏等采用自適應譜聚類算法對長江口完整船舶軌跡進行分析，成功提取出該水域的6條主要航線。劉岳豪等利用骨架提取技術，先將船舶軌跡數(shù)據(jù)轉(zhuǎn)化為圖像數(shù)據(jù)再進行聚類分析，成功分析出船舶較頻繁行進的路線。然而，由于AIS數(shù)據(jù)量巨大，而且每條船舶軌跡長度不同，直接對完整船舶軌跡進行聚類的效率不高，且檢測精度低。因此，如何度量不同長度船舶軌跡之間的相似度并結合聚類算法對船舶軌跡進行分析是本文研究的重點。

為解決船舶軌跡聚類算法在實際應用中遇到的問題，本文把具有噪聲的基于密度的空間聚類(density-based spatial clustering of applications with noise, DBSCAN)算法從點聚類推廣到線聚類，提出一種可以適用于完整船舶軌跡的聚類算法——具有噪聲的基于密度的軌跡聚類(density-based trajectory clustering of applications with noise, DBTCAN)算法。該算法利用Hausdorff距離作為船舶軌跡之間的相似度度量，無須對軌跡進行分段處理，可以對不同長度的船舶軌跡進行聚類分析。

1 DBTCAN算法

1.1 相似度度量

空間距離不僅可以用來描述物體的位置分布，而且可以用來表示物體之間的相似度。距離小意味著差異小，相似度高。以空間距離為基礎的相似度度量方法有很多，如歐氏距離、曼哈頓距離、閔可夫斯基距離、切比雪夫距離和Hausdorff距離等，其中Hausdorff距離常用于計算曲線之間的相似度。Hausdorff距離是一種定義兩組點集之間距離的方法，可用于描述兩組點集之間的相似度。兩組點集之間的 Hausdorff距離越大，相似度越低。給定2條由若干有序軌跡點構成的軌跡={}，={}，則集合與集合的Hausdorff距離為

(,)=max((,),(,))

(1)

(2)

(3)

相對于傳統(tǒng)的距離度量，運用Hausdorff距離公式無須對軌跡集進行插值處理，可以直接計算軌跡之間的相似度，避免了給軌跡數(shù)據(jù)添加噪聲，減少了噪聲對原始數(shù)據(jù)的影響。另一方面，由于播發(fā)時間間隔不一致，不同船舶產(chǎn)生和記錄的AIS數(shù)據(jù)長度不同。Hausdorff距離可以很好地適用于計算船舶軌跡之間的相似度，因此本文采用Hausdorff距離作為船舶軌跡之間的相似度度量。

1.2 DBTCAN算法原理

DBSCAN算法是一種基于密度的聚類算法，可以應用于有噪聲的環(huán)境，利用它可以找到任意形狀的簇，并自動確定簇的數(shù)量。然而，DBSCAN算法多用于點聚類，不能直接對船舶軌跡進行分析。AIS數(shù)據(jù)中船舶位置信息是一系列由經(jīng)緯度坐標構成的點集，Hausdorff距離可以直接用來度量船舶軌跡之間的相似度，無須對AIS數(shù)據(jù)進行插值處理。因此，本文將DBSCAN算法由傳統(tǒng)的點聚類推廣為線聚類，并采用Hausdorff距離作為相似度度量，提出一種可以適用于不同長度船舶軌跡聚類的DBTCAN算法。

DBTCAN算法思路如下。選中給定軌跡集中任意一條軌跡，通過計算找到與該軌跡相似度小于等于相似度閾值的所有軌跡：若軌跡數(shù)量小于鄰域密度閾值，則該軌跡被標記為噪聲軌跡；若軌跡數(shù)量大于等于，則該軌跡為核心軌跡。接著判斷在這條軌跡鄰域內(nèi)的軌跡是否為核心軌跡，如果是，則這些軌跡屬于一個簇。再對軌跡集內(nèi)其他未被選中的軌跡進行判斷，直到所有軌跡判斷完畢完成聚類為止。DBTCAN算法的相關定義如下：

定義軌跡的鄰域為

()={∈|(,)≤}

(4)

式中：為給定的軌跡集，∈,∈。()由所有與的相似度不超過的軌跡構成。

對于∈，如果的鄰域滿足

|()|≥

(5)

則為核心軌跡。式中，|()|為的鄰域內(nèi)包含的軌跡數(shù)量，為軌跡鄰域密度閾值。

在軌跡集內(nèi)，如果滿足

∈()

(6)

|()|≥

(7)

則到是直接密度可達的。

太陽能供電系統(tǒng)通過30W太陽能單晶硅面板采能、12V/20Ah蓄電池儲電[7]。選擇EPOW-PS10太陽能控制器,該控制器是基于智能芯片控制的太陽充放電管理系統(tǒng)，具有防反充、三級過載、短路、反接、過充電、過放電等完善的系統(tǒng)保護功能，保證蓄電池工作在最佳的狀態(tài)。蓄電池是12V輸出，系統(tǒng)只需5V供電，所以還用了一個低紋波的LM2596超小型DC-DC 12V轉(zhuǎn)5V降壓模塊，該模塊最大連續(xù)輸出電流3A，模塊還具有輸出短路、過熱保護功能，這樣就提高了系統(tǒng)的安全性能。

在軌跡集內(nèi)，如果存在,,…,,…,，使得所有的到+1關于和都是直接密度可達的，則稱到是密度可達的。

存在一條任意軌跡，∈，若到、到關于和是密度可達的，則稱與關于和是密度相連的。

DBTCAN算法流程見圖1。

圖1 DBTCAN算法流程

1.3 DBTCAN算法參數(shù)的自適應確定

基于密度的聚類算法本質(zhì)上是在數(shù)據(jù)集中發(fā)現(xiàn)高密度的數(shù)據(jù)集，即該數(shù)據(jù)集中數(shù)據(jù)點之間的平均距離較小，而高密度數(shù)據(jù)集之間存在著低密度區(qū)域。DBTCAN算法采用參數(shù)和來確定劃分高密度軌跡集的閾值，不同的參數(shù)組合對最后的聚類效果有較大影響。要想實現(xiàn)參數(shù)的自適應確定，關鍵在于確定合適的候選閾值參數(shù)集合，參數(shù)的取值范圍和參數(shù)間距決定了聚類的精度和運算量?；谝陨峡紤]，本文利用軌跡集自身的空間分布特性，基于平均最近鄰(-average nearest neighbor, KANN)算法和數(shù)學期望法生成DBTCAN算法的最優(yōu)輸入?yún)?shù)，步驟如下：

采用KANN算法生成候選集合。KANN算法的基本思想是通過計算軌跡集中每條軌跡與其第條最近鄰軌跡之間的最近鄰距離，并對所有軌跡的最近鄰距離求平均值，得到軌跡集的平均最近鄰距離。對所有的值進行計算，得到平均最近鄰距離向量。具體步驟如下：

步驟① 計算軌跡集的距離矩陣，即

×={(,)|1≤≤,1≤≤}

(8)

式中：為軌跡集所包含的軌跡數(shù)量。

步驟② 對距離矩陣×中的每行元素按升序進行排序后，則該矩陣第一列元素(其所組成的距離向量記為)表示軌跡到自身的距離(全為0)，第列元素構成所有軌跡的最近鄰距離向量。

(9)

采用數(shù)學期望法生成候選集合。依次求出每個候選對應的鄰域內(nèi)軌跡數(shù)量，并計算所有軌跡的鄰域內(nèi)軌跡數(shù)量的數(shù)學期望值，作為軌跡集的鄰域密度閾值，表示為

(10)

式中：為第條軌跡鄰域內(nèi)的軌跡數(shù)量。

確定最優(yōu)聚類簇數(shù)。依次選取候選和由式(10)計算得到的，將其輸入DBTCAN算法對軌跡集進行聚類分析，可以得到不同值下的聚類簇數(shù)。當聚類簇數(shù)連續(xù)3次或3次以上相同時，則認為聚類結果趨于穩(wěn)定，記該聚類簇數(shù)為最優(yōu)聚類簇數(shù)。

2 實驗設計與結果分析

為驗證DBTCAN算法的有效性，選取渤海水域(36°08′16″～40°27′26″N,117°42′46″～123°50′35″E)2018年1月1—4日121艘船的739 629條軌跡數(shù)據(jù)作為研究對象進行實驗。

2.1 實驗過程

對AIS數(shù)據(jù)進行解碼存儲、坐標轉(zhuǎn)換、噪聲清洗等預處理后，設置合適的閾值，利用Douglas-Peucker算法對船舶軌跡進行壓縮，預處理后的船舶軌跡見圖2。

圖2 預處理后的渤海水域船舶軌跡

圖3 聚類簇數(shù)與K值的關系

值是一種評價聚類結果的綜合指標。設正確率為判斷正確的軌跡數(shù)量占識別出的軌跡數(shù)量的百分比；召回率為判斷正確的軌跡數(shù)量占實際的總軌跡數(shù)量的百分比，則值為

(11)

由圖4可知，在=16時，值最大，聚類結果較優(yōu)，說明利用參數(shù)自適應確定方法得到的參數(shù)為最優(yōu)參數(shù)。將最優(yōu)參數(shù)輸入DBTCAN算法，得到渤海水域船舶軌跡聚類結果，見圖5。

圖4 聚類結果的F值曲線

圖5 渤海水域船舶軌跡聚類結果

2.2 結果分析

實驗共得到4個簇。根據(jù)實際航路與各簇之間的對應關系，對圖5中4種不同顏色的簇進行分析與整合，得到渤海水域4條主要的航路:

航路1(圖6a)：成山角→老鐵山水道→天津港、曹妃甸港。航路起點為成山角附近水域，經(jīng)(37°38′30″N,122°38′48″E)轉(zhuǎn)向305°到達老鐵山水道水域。在老鐵山水道定線制的警戒圈經(jīng)(38°36′06″N,120°51′18″E)到達(38°48′00″N,118°45′12″E)，進入曹妃甸水域，再按曹妃甸水域船舶定線制航法，航行至天津港。

航路2(圖6b)：成山角→老鐵山水道→唐山港。航路起點為成山角船舶定線制水域，經(jīng)(37°38′30″N,122°38′48″E)轉(zhuǎn)向305°到達老鐵山水道水域。在(38°37′06″N,120°51′48″E)沿航向305°航行至唐山港附近水域。

航路3(圖6c)：成山角→老鐵山水道→渤海灣北部。航路起點為成山角水域，經(jīng)(37°38′30″N,122°38′48″E)轉(zhuǎn)向305°到達老鐵山水道水域。經(jīng)(38°37′06″N,120°51′48″E)沿航向8°航行至(39°32′18″N,121°01′42″E)，再轉(zhuǎn)向31°航行至(40°08′06″N,121°29′12″E)，再轉(zhuǎn)向69°航行至終點(40°13′12″N,121°47′24″E)。反之，依次沿航向249°、211°、188°航行至老鐵山水道水域，再沿航向125°到達成山角水域。

航路4(圖6d)：成山角→老鐵山水道→秦皇島港。航路起點為成山角船舶定線制水域，經(jīng)(37°38′30″N,122°38′48″E)轉(zhuǎn)向305°到達老鐵山水道定線制水域。經(jīng)(38°37′06″N,120°51′48″E)轉(zhuǎn)向334°航行至(38°54′30″N,120°41′36″E)，再轉(zhuǎn)向319°航行至(39°40′42″N,119°51′42″E)，最終抵達秦皇島港水域。反之，由139°轉(zhuǎn)向到154°航行到老鐵山水道水域，再沿航向125°航行至成山角水域。

a)航路1

由渤海及黃海北部航法圖可知，船舶通過老鐵山水道后大致有3個主要航向，分別是向西沿著推薦航線前往天津港和曹妃甸港及其附近水域，向西北沿推薦航線前往秦皇島港附近水域，向北前往渤海灣北部水域。由此可知，本文提出的DBTCAN算法可以對渤海水域的船舶軌跡進行聚類，能準確提取該水域船舶的主要航線，且聚類結果符合渤海水域?qū)嶋H的交通流現(xiàn)狀。

3 結束語

本文針對聚類算法在船舶軌跡聚類應用中的不足，提出能夠適用于完整船舶軌跡聚類的DBTCAN算法。該算法利用Hausdorff距離作為船舶軌跡之間的相似度度量，可以對不同長度的船舶軌跡進行聚類。同時針對DBTCAN算法需要人工確定輸入?yún)?shù)的問題，提出一種參數(shù)自適應確定方法，可以自適應得到DBTCAN算法的最優(yōu)輸入?yún)?shù)，使得聚類過程無須人為干預，聚類結果具有高的準確率。最后，利用渤海水域的船舶軌跡數(shù)據(jù)對DBTCAN算法進行實例驗證。結果表明，該算法能夠在大量復雜船舶軌跡中找到相似軌跡并對其進行聚類，且聚類結果與實際交通流情況一致。本文成果可以為相關部門在航道規(guī)劃、分道通航方面以及開展渤海水域船舶定線制工作提供一定的參考。

在基于DBTCAN算法進行聚類的過程中需要計算每兩條軌跡之間的Hausdorff距離，如果數(shù)據(jù)量太大，則算法運行效率將大大降低，運行時間將成倍增加。后續(xù)的研究工作可以從提高算法運行效率和推動聚類結果的實際應用等方面展開。