分層建模的船舶軌跡快速聚類算法

王森杰 何正偉

(武漢理工大學(xué)航運(yùn)學(xué)院1) 武漢 430063) (內(nèi)河航運(yùn)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室2) 武漢 430063) (國家水運(yùn)安全工程技術(shù)研究中心3) 武漢 430063)

0 引 言

船舶自動(dòng)識別系統(tǒng)(auto identification system，AIS)[1]是一種實(shí)現(xiàn)船船、船岸通信的安全助航設(shè)備，船舶通過搭載AIS終端實(shí)時(shí)將自身船舶運(yùn)動(dòng)信息進(jìn)行廣播，通過岸基終端可以快速采集移動(dòng)船舶的AIS數(shù)據(jù).AIS數(shù)據(jù)不僅記錄船舶的空間信息、時(shí)間信息，同時(shí)集成了對地航向、船首向和對地速度等船舶運(yùn)動(dòng)數(shù)據(jù)，蘊(yùn)含豐富的語義和行為模式.對船舶軌跡數(shù)據(jù)進(jìn)行聚類分析，可為船舶交通流特征提取、航路安全規(guī)劃、船舶異常檢測等技術(shù)研發(fā)和應(yīng)用提供基礎(chǔ)手段和關(guān)鍵方法，為航運(yùn)規(guī)劃、海事監(jiān)管等工作開展提供決策支持和科學(xué)依據(jù)[2].在軌跡數(shù)據(jù)激增和大數(shù)據(jù)技術(shù)發(fā)展的背景下，如何從軌跡數(shù)據(jù)中挖掘積累的物體運(yùn)動(dòng)模式，已經(jīng)成為軌跡數(shù)據(jù)分析領(lǐng)域的研究熱點(diǎn)之一.馬文耀等[3]提出了一種基于單向距離的軌跡相似度計(jì)算方法，該方法將單向距離定義為一條船舶軌跡上各個(gè)點(diǎn)到另一軌跡各個(gè)點(diǎn)的最小距離的平均值，利用譜聚類算法對軌跡的空間分布進(jìn)行學(xué)習(xí)，獲取船舶的正常運(yùn)動(dòng)模式.Zhen等[4]人整合k-medoids聚類和樸素貝葉斯分類器，實(shí)現(xiàn)了船舶行為的分類和異常行為檢測.Zhao等[5]人基于原始樸素DP算法和DBSCAN算法實(shí)現(xiàn)船舶軌跡模式的快速分類辨識.江玉玲等[6]采取Frechet距離對船舶軌跡相似度進(jìn)行建模，基于DBSCAN聚類方法對典型軌跡得到了的符合實(shí)際的聚類結(jié)果.張春瑋等[7]綜合船舶位置、航速、航向等信息，對不同屬性數(shù)據(jù)進(jìn)行加權(quán)求和得到軌跡特征，利用DBASCAN算法實(shí)現(xiàn)了航道內(nèi)船舶異常行為的分類辨識.彭祥文等[8]設(shè)計(jì)了一種基于軌跡分區(qū)預(yù)處理的并行化子軌跡聚類算法，通過數(shù)據(jù)分區(qū)并行實(shí)現(xiàn)了聚類加速.綜上，這些專家學(xué)者對于船舶軌跡聚類研究都取得了相應(yīng)的結(jié)論，但是以上方法依然在兩個(gè)方面存在限制.一方面，單一特征的軌跡相似度模型沒有充分利用AIS數(shù)據(jù)多維船舶屬性特點(diǎn)，對復(fù)雜船舶軌跡的辨識能力不足；另一方面，多特征的軌跡相似度模型采取歸一化參數(shù)對不同特征進(jìn)行加權(quán)求和計(jì)算軌跡相似度，導(dǎo)致權(quán)重參數(shù)設(shè)置難，當(dāng)耦合參數(shù)超過三個(gè)時(shí)，在某些特征參數(shù)分布下不同特征的差異相互疊加可能會導(dǎo)致一些隱蔽軌跡簇?zé)o法辨識.因此如何充分利用AIS多維船舶屬性數(shù)據(jù)，建立魯棒的軌跡相似度模型，提高聚類算法對隱蔽軌跡簇的辨識和聚類效率是當(dāng)前船舶軌跡聚類研究的重點(diǎn).

針對AIS數(shù)據(jù)集成空間、時(shí)間和其他多維屬性的特點(diǎn)，文中提出了一種分層建模的船舶軌跡快速聚類算法.通過分層建模，以非全耦合的方式對不同特征參數(shù)進(jìn)行有效利用，解決傳統(tǒng)融合特征建模中參數(shù)權(quán)重設(shè)置困難，某些隱蔽軌跡簇?zé)o法辨識的問題.該算法將軌跡點(diǎn)的經(jīng)緯度、對地航速、加速度、船艏向、對地航向共五種特征參數(shù)根據(jù)特征特點(diǎn)劃分為空間、速度和方向三大特征類型，在不同層次建立對應(yīng)特征軌跡相似度模型，通過三次自上而下的層次遞進(jìn)聚類，逐步放大聚類的分辨率，完成對船舶隱蔽軌跡簇的挖掘.同時(shí)針對傳統(tǒng)軌跡聚類計(jì)算量大、聚類時(shí)間長等缺點(diǎn)，本文提出一種DP改進(jìn)算法對船舶AIS軌跡特征點(diǎn)進(jìn)行提取，實(shí)現(xiàn)數(shù)據(jù)壓縮和聚類加速.

1 多特征層次軌跡聚類

1.1 相似度分層建模

軌跡聚類的本質(zhì)是按照軌跡數(shù)據(jù)的相似性進(jìn)行對象的劃分，而聚類劃分的結(jié)果嚴(yán)重取決于軌跡相似度模型的構(gòu)建方式.因此，如何評價(jià)軌跡數(shù)據(jù)間距離或相似度是聚類處理的關(guān)鍵問題之一.船舶AIS軌跡數(shù)據(jù)是一種多維數(shù)據(jù)，它包括船舶位置、對地航速、對地航向、船艏向、轉(zhuǎn)向率等船舶運(yùn)動(dòng)狀態(tài)信息.針對AIS數(shù)據(jù)多維屬性特點(diǎn)，本文將多種船舶狀態(tài)數(shù)據(jù)劃分為三組，在層次聚類中的上、中、下層中依次建立軌跡相似度模型，不同層次的軌跡相似度計(jì)算過程如下.

設(shè)兩條不等長軌跡時(shí)間序列P=(p1,p2,…,pM)和Q=(q1,q2,…,qN)，每個(gè)軌跡點(diǎn)包含六種船舶狀態(tài)參數(shù).

(1)

(2)

式中：x為經(jīng)度；y為緯度；s為對地航速；a為加速度；c為對地航向；h為船首向；i和j為軌跡序列第i和第j個(gè)軌跡點(diǎn).在多特征層次聚類過程中，上層利用船舶位置信息進(jìn)行聚類，其中任意軌跡點(diǎn)pi和qj的空間差異r1(pi,qj)為

(3)

中層利用船舶速度、加速度信息聚類，其中任意軌跡點(diǎn)pi和qj的速度差異r2(pi,qj)為

(4)

下層利用船舶對地航向、船首向信息聚類，其軌跡點(diǎn)pi和qj的航向差異r3(pi,qj)為

(5)

(6)

r3(pi,qj)=Δc+Δh

(7)

本文采取DTW算法[9]計(jì)算兩條軌跡間的相似度.對于兩條不等長軌跡序列P和Q，軌跡間相似度為各個(gè)軌跡點(diǎn)的累積最小差異.利用動(dòng)態(tài)規(guī)劃思想，從兩條軌跡一端(p1,q1)遍歷到另一端(pM,qN)的累計(jì)最小差異為

W(pM,qN)=r(pi,qj)+

min{W(pM-1,qN),W(pM,qN-1),W(pM-1,qN-1)}

(8)

式中：r(·)在不同層次聚類過層中分別表示特征相似度函數(shù)r1(·)、r2(·)、r3(·).

1.2 分層聚類

本文提出了一種自頂而下的層次聚類算法，見圖1.其中船舶AIS數(shù)據(jù)多維屬性被分層利用：基于經(jīng)緯度聚類實(shí)現(xiàn)軌跡的空間分布分析；基于速度、加速度聚類實(shí)現(xiàn)船舶的加、減速行為辨識；基于船艏向、對地航向聚類實(shí)現(xiàn)船舶避讓、掉頭等行為識別.在多次遞進(jìn)聚類過程中，簇間差異被逐步放大，而不是一次性聚類，從而實(shí)現(xiàn)隱蔽軌跡簇辨識.同時(shí)分層建模有效解決了傳統(tǒng)融合特征建模中參數(shù)權(quán)重設(shè)置困難的問題.

圖1 多特征分層聚類示意圖

采用DBSCAN算法作為層次聚類算法的核算法.DBSCAN算法需要預(yù)先設(shè)置的領(lǐng)域半徑ε和簇內(nèi)元素最小數(shù)目minPts.該算法通過遍歷軌跡集合，計(jì)算兩兩軌跡之間的相似度，將相似度低于ε的軌跡劃分到一個(gè)新集合內(nèi)，如果該集合元素?cái)?shù)目大于minPts則被定義為一個(gè)新類，否則劃為噪聲類.DBSCAN算法對噪聲數(shù)據(jù)不敏感，無須事先設(shè)定簇個(gè)數(shù)，非常適合船舶AIS軌跡數(shù)據(jù)噪聲點(diǎn)多，軌跡模式不確定性高等情況下的聚類[10-11].其多特征分層聚類步驟如下.

步驟1將空間位置信息作為上層特征，聚類得到大類軌跡簇.

步驟2將船舶對地航速、加速度作為中間層特征對得到的每一個(gè)大類軌跡簇進(jìn)行進(jìn)一步聚類得到中類軌跡簇.

步驟3將對地航向、船首向作為下層特征，同時(shí)對下層聚類條件進(jìn)行約束，僅對中層聚類結(jié)果中軌跡數(shù)目最多的軌跡簇進(jìn)行進(jìn)一步下層聚類，其他簇不進(jìn)行下層聚類，直接作為最后結(jié)果.

2 聚類加速

2.1 快速軌跡聚類框架

圖2 軌跡特征點(diǎn)提取

2.2 壓縮算法

DP算法是一種基于軌跡形狀的軌跡壓縮算法，在壓縮軌跡的同時(shí)能夠保存軌跡的形狀特征[15].但是DP算法僅僅考慮了軌跡點(diǎn)的空間位置，而沒有考慮船舶對地速度、船首向、對地航向等信息，導(dǎo)致對于直線加速、減速、減速轉(zhuǎn)向等特殊軌跡段進(jìn)行壓縮時(shí)會發(fā)生關(guān)鍵特征軌跡點(diǎn)提取丟失.本文綜合船舶位置、對地速度、對地航向、船首向信息對DP算法進(jìn)行改進(jìn)，提出了一種軌跡特征點(diǎn)提取算法.該算法在壓縮軌跡點(diǎn)數(shù)量的同時(shí)，可以保留船舶不同駕駛行為特征信息.軌跡點(diǎn)提取算法流程見圖3.

圖3 船舶軌跡特征點(diǎn)提取流程

3 實(shí)驗(yàn)及分析

3.1 試驗(yàn)數(shù)據(jù)

蝦峙門口外深水航槽是一條供大吃水受限船舶進(jìn)出蝦峙門的人工航槽.由于該區(qū)域沒有采取定線制，導(dǎo)致進(jìn)出蝦峙門國際航道的船舶和南下北上的穿越船舶在此區(qū)域形成復(fù)雜的交通環(huán)境.本文提取2018年1月份100條船舶軌跡，共12 118條AIS數(shù)據(jù)作為試驗(yàn)數(shù)據(jù)對分層建模聚類算法進(jìn)行驗(yàn)證.

對原軌跡集合100條軌跡，先利用上層特征船舶位置信息進(jìn)行上層聚類，見圖4.其領(lǐng)域半徑ε設(shè)置為0.15，簇內(nèi)元素最小數(shù)目minPts設(shè)置為15.由圖4可知：上層特征將100條船舶軌跡辨識為3類，“class 1”標(biāo)記軌跡被辨識為下行出港船舶，“class 3”標(biāo)記的軌跡被辨識為上行進(jìn)港船舶，“class 2”標(biāo)記軌跡被辨識為噪聲數(shù)據(jù)，即橫穿等異常行為軌跡數(shù)據(jù).

圖4 上層特征聚類結(jié)果

對于上層聚類結(jié)果，繼續(xù)利用中層特征進(jìn)行進(jìn)一步聚類.中層聚類的領(lǐng)域半徑ε設(shè)置為300，簇內(nèi)元素最小數(shù)目minPts設(shè)置為5.圖5a)為大類下行出港船舶進(jìn)一步聚類結(jié)果，中層聚類將其進(jìn)一步聚為兩類，其中“class 2”標(biāo)記的軌跡均為減速的高速行駛船舶 “class 1”標(biāo)記的軌跡均為低速行駛的加速船舶.圖5b)為大類異常行為軌跡的中層聚類結(jié)果.中層聚類將其進(jìn)一步聚為兩類，其中“class 2”標(biāo)記的軌跡均為中高速船舶，“class 1”標(biāo)記的噪聲軌跡均為低速游蕩船舶.圖5c)為大類上行進(jìn)港船舶進(jìn)一步聚類結(jié)果.中層聚類將其進(jìn)一步聚為兩類，其中“class 1”標(biāo)記的軌跡均為減速行為，“class 2”標(biāo)記的軌跡存在勻速行為.根據(jù)蝦峙門口外深水航槽通航安全規(guī)定，進(jìn)港船舶應(yīng)采取減速行為.因此“class 2”標(biāo)記的軌跡應(yīng)該被識別船舶非法行為.

圖5 中層特征聚類結(jié)果

對于中層聚類結(jié)果，由于聚類條件約束，下層聚類僅選取中層聚類結(jié)果中簇內(nèi)元素最多的中類進(jìn)行下層聚類.下層聚類的領(lǐng)域半徑ε設(shè)置為3 000，簇內(nèi)元素最小數(shù)目minPts設(shè)置為5.圖6a)為中類加速出港船舶的進(jìn)一步聚類，下層聚類將其進(jìn)一步聚為兩類，其中標(biāo)記為“class 1”的軌跡均為直線加速出港船舶，而標(biāo)記為“class 2”的軌跡被辨識為加速出港南下船舶.圖6b)為中類穿越船舶的進(jìn)一步聚類，下層聚類將其辨識為兩類，其中標(biāo)記為“class 1”的軌跡均為南下橫穿船舶，而標(biāo)記為“class 2”的軌跡被辨識為北上橫穿船舶.圖6c)為中類減速進(jìn)港船舶的進(jìn)一步聚類結(jié)果.下層聚類將其進(jìn)一步聚為兩類，其中標(biāo)記為“class 1”的軌跡均為直線減速進(jìn)港船舶，而標(biāo)記為“class 2”的軌跡被辨識為東北向匯入減速進(jìn)港船舶.

圖6 下層特征聚類結(jié)果

圖7 軌跡特征柱狀統(tǒng)計(jì)分析圖

圖8 聚類結(jié)果的層次樹狀關(guān)系

經(jīng)過3層層次聚類后，所有船舶軌跡被聚類為9類軌跡，見圖7.對每一類船舶軌跡的平均速度、平均對地航向、平均壓差角和平均加速度共4個(gè)屬性進(jìn)行柱狀圖統(tǒng)計(jì)分析，9類軌跡被辨識為9種不同船舶行為模式的船舶，并且9類軌跡擁有圖8的層次樹狀關(guān)系.其中“class 1”為高速出港船舶，其船舶行為特征表現(xiàn)為初始速度快、存在小幅度減速；“class 2”為低速游蕩船舶，其船舶行為特征為平均速度低、頻繁轉(zhuǎn)向、頻繁減速；“class 3”為勻速進(jìn)港船舶，其船舶行為特征變現(xiàn)為速度適中、速度穩(wěn)定；“class 4”為加速南下出港船舶，其船舶行為特征為速度適中、下幅度加速、負(fù)壓差角；“class 5”為加速直線出港、其船舶行為特征為速度適中、加速度適中、直線行駛.“class 6”為北上橫穿船舶，船舶行為特征表現(xiàn)為速度適中、大幅度轉(zhuǎn)向.“class7”為南下橫穿船舶，船舶行為特征表現(xiàn)為速度適中、大幅度轉(zhuǎn)向.“class 8”為減速東北向匯入進(jìn)港船舶、其船舶行為特征表現(xiàn)為速度適中、減速度適中、負(fù)壓差角.“class 9”為減速直線進(jìn)港船舶、其船舶行為特征表現(xiàn)為速度適中、減速度適中、正壓差角.統(tǒng)計(jì)結(jié)果表明，分層建模的船舶軌跡聚類算法能夠有效將船舶軌跡辨識為9類軌跡模式，并且不同軌跡模式具有各自典型的軌跡特征分布.

3.3 聚類速度測試

以100條軌跡，共12 118個(gè)軌跡點(diǎn)作為測試數(shù)據(jù)，本文對傳統(tǒng)DTW-DBSCAN、LCSS-DBSCAN、Frechet-DBSCAN和分層快速聚類算法進(jìn)行了聚類速度對比實(shí)驗(yàn).實(shí)驗(yàn)環(huán)境：python3.5，實(shí)驗(yàn)設(shè)備：i5-8250，內(nèi)存8g.對于分層快速軌跡聚類算法，設(shè)置壓縮閾值參數(shù)Th1=0.000 15，Th2=2，Th3=10，Th4=10.表1為目前算法和分層快速聚類算法在實(shí)驗(yàn)數(shù)據(jù)上的聚類時(shí)間結(jié)果.可以發(fā)現(xiàn)，DTW-DBSCAN、LCSS-DBSCAN、Frechet-DBSCAN在聚類速度速度上大致相等，約為283 s.而分層快速聚類算法，在4.025壓縮倍率下，聚類速度約為傳統(tǒng)無壓縮算法的16倍.通過對比發(fā)現(xiàn)本文提出的聚類加速框架能夠明顯提升聚類速度，其速度提升倍率約為軌跡壓縮倍率ρ的平方，與理論提升效率一致.

表1 聚類速度結(jié)果

4 結(jié) 束 語

針對目前軌跡聚類算法存在的缺點(diǎn)，本文充分利用船舶AIS數(shù)據(jù)的多維屬性數(shù)據(jù)，提出了一種分層建模的軌跡聚類算法.通過分層建模，解決了融合特征模型中權(quán)重參數(shù)取值困難的問題，提高了模型的魯棒性.通過遞進(jìn)聚類，依次放大類間差異，從而達(dá)到對隱蔽軌跡簇的辨識.同時(shí)改進(jìn)DP算法，在軌跡聚類前先對軌跡進(jìn)行特征點(diǎn)提取，通過數(shù)據(jù)規(guī)整和壓縮有效提高了聚類效率.利用蝦峙門深水航槽的數(shù)據(jù)進(jìn)行了實(shí)驗(yàn)和分析，結(jié)果表明，分層建模的軌跡聚類算法能夠有效辨識復(fù)雜船舶交通環(huán)境下各種船舶軌跡模式，同時(shí)該算法能夠在層次聚類過層中有效挖掘不同船舶軌跡模式的樹狀層次關(guān)系，對于加強(qiáng)船舶交通行為分析和船舶交通監(jiān)管具有重要意義.同時(shí)聚類速度對比實(shí)驗(yàn)的結(jié)果證明該框架能夠極大提高聚類速度時(shí)間，對于目前快速增長的船舶AIS大數(shù)據(jù)分析極具現(xiàn)實(shí)意義.