基于DBSCAN算法的船舶軌跡自適應層次聚類

趙梁濱， 史國友， 楊家軒

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

隨著國家大數據戰略的穩步推進及船舶自動識別系統(Automatic Identification System，AIS)的普及，海事領域的數據產業蓬勃發展。傳統的海事監管模式受人為因素的制約導致低效。順應著對 “更好地感知交通態勢”及“更及時地識別異常船舶”的迫切需求，隨著“智能航海”及“海上智能監管”等新概念的提出，“互聯網+”及“云計算”等理念與海事領域的結合越來越緊密。

每艘搭載AIS設備的船舶能向外播發包括船舶軌跡在內的AIS數據，由于AIS數據量龐大，其中蘊藏著海上復雜交通環境中的潛在規律，能保持穩定且快速增長，為水上交通數據挖掘理論提供基礎。

軌跡數據的分析方法包括聚類、數理統計、貝葉斯網絡及神經網絡等。其中，聚類算法(Density-Based Spatial Clustering of Applications with Noise,DBSCAN[1])作為一種經典的空間聚類算法，已遍及各類交通情景的研究。LEE等[2]基于DBSCAN算法提出一種軌跡聚類的框架“TRACLUS”,該框架先將軌跡分裂成子軌跡片段，再用最小描述長度距離衡量片段間的相似度，最后采用DBSCAN算法對所有片段進行聚類來獲得軌跡分布特征。該方法被后續的相關研究所廣泛借鑒[3]。

以船舶作為研究對象時，在水上交通環景中由于移動對象在空間上更加自由無約束，軌跡分布更加零散、復雜，所以DBSCAN算法的應用效果不佳。LIU等[4]提出一種考慮國際海事組織(International Maritime Organization,IMO)規則和非空間屬性的方法，作為聚類后的輔助手段以提取類簇的特征。此外，PALLOTTA等[5]提出名為“TREAD”(Traffic Route Extraction and Anomaly Detection)的方法，考慮船舶軌跡數據點集中的間歇性、持續性等因素。基于DBSCAN算法的船舶軌跡分析研究還包括文獻[6]等，但是其均未考慮算法自身的參數設置問題。DBSCAN算法對全局性參數十分敏感,因此,根據經驗所設置的單一參數難以在軌跡密度不均的水上交通環境下完成各局部合理的聚類，且其物理意義抽象，很難找到與實際水域情況的關聯性。

為了克服DBSCAN算法在水上交通環境中的應用難題，本文基于其原理，通過統計分析數據的核心距離[7]來確定參數，提出針對船舶軌跡的層次聚類方法，并結合實例驗證該方法的有效性。

1 自適應層次聚類方法

1.1 DBSCAN算法原理

DBSCAN算法是一種基于密度的聚類算法，它能發現任意形狀的類簇，自動確定簇的數量，可適用于噪聲環境。拓展到線的DBSCAN算法原理定義為

1)ε-鄰域集Nε：Nε(Li)為Li在線段集D內所有與Li距離小于領域范圍ε的線段集合為

Nε(Li)={Lj∈D|ddist(Li,Lj)≤ε}

(1)

2)核心線段：給定領域范圍參數ε和領域最少線段參數MinLns，若Nε(Li)中的線段數量≥MinLns，則認為Li為核心線段。

3)直接密度可達：給定參數ε，MinLns，若存在核心線段Li，Lj包含在Nε(Li)中，則認為Lj從Li直接密度可達。

4)密度可達：給定參數ε，MinLns，若存在從Li到Lk直接密度可達，從Lk到Lj也直接密度可達，則認為從Li到Lj密度可達。

5)密度相連：給定參數ε，MinLns，若存在Lk，Lj和Li同時從Lk密度可達，則認為Li和Lj密度相連。

DBSCAN算法的思想就是找出所有密度相連的線段，并各自為簇(見圖1)。算法唯一需要人為參與的部分就是參數設置，因此，參數的確定是DBSCAN算法減少誤差的關鍵。

圖1 DBSCAN算法偽代碼

1.2 DBSCAN算法參數的自適應確定

核心距離是指在給定參數MinLns下，使樣本數據能夠成為核心線段的最小距離Dist(MinLns)。

聚類的目的是將較密集的樣本盡可能地聚合成簇。在理想的簇中，樣本數量應得到保證，且分布密度應最大。從單個數據樣本為中心的局部DBSCAN聚類效果來看，若ε取該樣本數據的核心距離，恰好能最準確地完成滿足密度要求的聚類。因此，可通過所有樣本的核心距離分布情況，找到分布密度最大值來確定合適的全局參數ε。

采用Inverse Gaussian擬合分布密度曲線的方法[8]來確定在給定MinLns情況下的領域范圍參數ε，它的概率密度和極值為

(2)

式(2)中:λ和μ可通過最大似然估計法獲得。

(3)

參數MinLns的值域為從1到樣本總數，根據上述方法可確定所有MinLns所對應的參數ε。接著根據DBSCAN擬聚類的效果，來確定合適的參數MinLns。

用噪聲數量來表征數據集的聚類效果。以瓊州海峽某時間段的船舶軌跡數據集為例，所有參數取值情況下的噪聲數量統計見圖2。

圖2中隨參數MinLns的增大，聚類后的噪聲數量逐漸減少，且變化趨勢呈現出向下凸的圖形。

參數MinLns在一定程度上反映著數據間能夠被聚合成簇的最大距離，故隨著MinLns的增大，在達到理想的聚類效果之前，類簇應快速地吸納周圍高密度的數據，導致噪聲數量急劇減少，然后類簇周圍的數據則變得稀疏，其擴張的速率應急劇下降，噪聲減少的速率也隨之下降。基于這一原則，合適的MinLns應在噪聲數量下降率變化最大的橫坐標位置，即圖2中O點所在位置。

圖3是上述最優參數情況下的聚類結果。由圖3可知，瓊州海峽南北方向上的主要交通流數據已被識別出來，并劃分為紅、綠兩類，剩余相對稀疏的數據則被歸為噪聲。從結果可知，軌跡集被全面且合理地識別劃分，但是卻沒有體現局部的交通流特性，例如航向相對的軌跡區分及各航道中的軌跡分布。這是因為在密度不均的數據集中，全局參數無法使各局部都達到最優化的聚類效果。而船舶軌跡是一種典型的密度不均衡數據，因此需采用層次進行聚類的方法。

1.3 層次聚類

層次聚類的原理是在每個層次都確定與該層次數據集密度最匹配的參數，其聚類精度隨層級遞增，從而達到適應各局部密度環境的聚類效果，以下是層次聚類的具體方法。

根據1.2節所述方法，確定該層次的參數取值，并完成聚類，得到包含類簇集和噪聲集在內的子數據集。接著，根據容量閾值分揀子數據集，其中小于容量閾值的數據集將被作為最終子數據集而輸出，容量閾值可根據實際情況設定，剩余的數據將被作為下一個層次的數據源。下一個層次則重復上述步驟，直到滿足停止條件為止。停止條件包括：

1)該層次聚類后產生的所有子數據集均小于容量閾值。

2)該層次無法再選取出合適的參數。

由于每個層次數據數量及變化規律的不同，其選取參數的具體方法也不同，例如在層次聚類的初期，噪聲數量還存在著較多異常波動，此時用圖形中距直線y=-x最近的點近似代替該點作為該層次參數的取值，往往能夠獲得較好的聚類效果。根據經驗確定了3種參數選取的具體方法(見表1)。

表1 選取參數的方法

當使用某一種選取方法進行聚類后，沒有新類簇產生，且新產生的噪聲數量小于容量閾值，則采用下一優先級方法重新進行聚類。當采用第3優先級方法進行聚類時，若兩個類簇的數據量分別大于和小于容量閾值，則視為無法再選取出合適參數。綜上所述，自適應層次聚類的方法見圖4。

d) 聚類結果函數的偽代碼

圖4 基于DBSCAN的自適應層次聚類算法

2 實例分析

為了驗證該聚類方法對于船舶軌跡數據的有效性，本文以瓊州海峽水域(110°06′00″E,20°18′00″N,111°24′00″E,20°00′00″N)2006年4月21日至22日內88艘船舶的332 525條AIS軌跡數據作為對象進行了試驗。

2.1 試驗過程

在數據庫中篩出研究范圍水域的全部數據，對數據進行解碼存儲、坐標轉換[9]、噪聲清洗等預處理。然后，采用Douglas-Peucker算法[10-11]對航跡點進行了壓縮，采用分解為垂直、水平、方向、速度的結構化距離[2]進行了軌跡線段間距離的度量。最后，完成基于DBSCAN的自適應層次聚類，部分過程及結果見圖5和圖6。

2.2 結果分析

試驗共得到28個類簇。根據實際航路中各類簇之間的連通性，將秀英港、海安港以及海口新港之間的船舶軌跡分為了4組(見圖7)。分析試驗結果，可得到以下結論。

圖5 部分層次聚類過程

1)該方法能夠發現內部具有相似性的軌跡類簇，例如聚類可以識別出從秀英港進入主航道的軌跡、主航道上的出港軌跡、離開主航道后繼續北上的軌跡以及向北航行一段距離后向東轉向的軌跡等(對應圖7a)中C-1、C-3、C-10、C-8)。此外聚類還能夠發現并識別出同一水域中不同航法的軌跡類簇，例如C-15、C-20、C-25，它們都是北上準備進入海安港主航道的船舶軌跡，C-24和C-26則都是在海安港主航道上的進港軌跡。

2)類簇結果能夠反映水域的交通情況[12]。從圖7a)和圖7c)中可知，海峽西側的軌跡類簇數量較多，說明該水域交通流量大。此外相向軌跡的分布存在著部分重合，說明該水域的交通流混亂、不分明，可能存在著較多的對遇局面。從圖7b)和圖7d)中可知，海峽東側的軌跡類簇數量較少，說明該水域交通流量小，軌跡分布零散。這些類簇結果都與瓊州海峽水域當時的交通情況相符。瓊州海峽當時并沒有實施定線制來拓寬南北方向的航路，因此交通流量都集中在海峽的偏西側，而偏東側水域的客船交通流量小，散亂無序。

3 結束語

本文針對DBSCAN算法在水上交通情景中的參數選取問題，提出一種能夠自適應確定算法參數，且適用于船舶軌跡數據的層次聚類方法，并通過瓊州海峽水域的實船AIS數據，完成了實例分析。試驗結果表明，該方法能夠在復雜的船舶軌跡中發現具有相似性的軌跡并將其聚集成簇，且聚類結果與實際情況相符，在航道規劃及海事監管等方面具有一定的應用價值。

圖7 4個類簇分組

該方法需要獲取每個層次中所有軌跡相互之間的距離以及所有參數取值的擬聚類結果，大量的遍歷計算使得方法的效率低。此外，用于類簇篩選的容量閾值需要人為設置，若設置不當，會導致局部交通流特征的喪失或對軌跡的過度分類。今后的工作可從優化方法效率及結果的工程應用方面開展。