趙梁濱， 史國友， 楊家軒

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

隨著國家大數(shù)據(jù)戰(zhàn)略的穩(wěn)步推進(jìn)及船舶自動識別系統(tǒng)(Automatic Identification System，AIS)的普及，海事領(lǐng)域的數(shù)據(jù)產(chǎn)業(yè)蓬勃發(fā)展。傳統(tǒng)的海事監(jiān)管模式受人為因素的制約導(dǎo)致低效。順應(yīng)著對 “更好地感知交通態(tài)勢”及“更及時地識別異常船舶”的迫切需求，隨著“智能航海”及“海上智能監(jiān)管”等新概念的提出，“互聯(lián)網(wǎng)+”及“云計算”等理念與海事領(lǐng)域的結(jié)合越來越緊密。

每艘搭載AIS設(shè)備的船舶能向外播發(fā)包括船舶軌跡在內(nèi)的AIS數(shù)據(jù)，由于AIS數(shù)據(jù)量龐大，其中蘊(yùn)藏著海上復(fù)雜交通環(huán)境中的潛在規(guī)律，能保持穩(wěn)定且快速增長，為水上交通數(shù)據(jù)挖掘理論提供基礎(chǔ)。

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

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

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

1 自適應(yīng)層次聚類方法

1.1 DBSCAN算法原理

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

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

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

(1)

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

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

4)密度可達(dá)：給定參數(shù)ε，MinLns，若存在從Li到Lk直接密度可達(dá)，從Lk到Lj也直接密度可達(dá)，則認(rèn)為從Li到Lj密度可達(dá)。

5)密度相連：給定參數(shù)ε，MinLns，若存在Lk，Lj和Li同時從Lk密度可達(dá)，則認(rèn)為Li和Lj密度相連。

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

圖1 DBSCAN算法偽代碼

1.2 DBSCAN算法參數(shù)的自適應(yīng)確定

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

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

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

(2)

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

(3)

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

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

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

參數(shù)MinLns在一定程度上反映著數(shù)據(jù)間能夠被聚合成簇的最大距離，故隨著MinLns的增大，在達(dá)到理想的聚類效果之前，類簇應(yīng)快速地吸納周圍高密度的數(shù)據(jù)，導(dǎo)致噪聲數(shù)量急劇減少，然后類簇周圍的數(shù)據(jù)則變得稀疏，其擴(kuò)張的速率應(yīng)急劇下降，噪聲減少的速率也隨之下降?；谶@一原則，合適的MinLns應(yīng)在噪聲數(shù)量下降率變化最大的橫坐標(biāo)位置，即圖2中O點(diǎn)所在位置。

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

1.3 層次聚類

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

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

1)該層次聚類后產(chǎn)生的所有子數(shù)據(jù)集均小于容量閾值。

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

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

表1 選取參數(shù)的方法

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

d) 聚類結(jié)果函數(shù)的偽代碼

圖4 基于DBSCAN的自適應(yīng)層次聚類算法

2 實例分析

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

2.1 試驗過程

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

2.2 結(jié)果分析

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

圖5 部分層次聚類過程

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

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

3 結(jié)束語

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

圖7 4個類簇分組

該方法需要獲取每個層次中所有軌跡相互之間的距離以及所有參數(shù)取值的擬聚類結(jié)果，大量的遍歷計算使得方法的效率低。此外，用于類簇篩選的容量閾值需要人為設(shè)置，若設(shè)置不當(dāng)，會導(dǎo)致局部交通流特征的喪失或?qū)壽E的過度分類。今后的工作可從優(yōu)化方法效率及結(jié)果的工程應(yīng)用方面開展。