基于Spark的船舶航行軌跡聚類方法

彭祥文, 高 曙, 初秀民, 何 陽, 陸 叢

(武漢理工大學(xué) a.計算機科學(xué)與技術(shù)學(xué)院；b.國家水運安全工程技術(shù)研究中心, 武漢 430063)

2017-04-25

國家自然科學(xué)基金(51479155);城市災(zāi)害地圖可視化方法研究(JD20150301)

彭祥文(1992—)，男，江西上饒人，碩士生，研究方向為云計算應(yīng)用。E-mail:616456468@qq.com

高 曙(1967—)，女，安徽蕪湖人，教授，研究方向為數(shù)據(jù)挖掘及應(yīng)用、智能交通。E-mail:gshu418@163.com

1000-4653(2017)03-0049-05

基于Spark的船舶航行軌跡聚類方法

彭祥文a, 高 曙a, 初秀民b, 何 陽a, 陸 叢a

(武漢理工大學(xué) a.計算機科學(xué)與技術(shù)學(xué)院；b.國家水運安全工程技術(shù)研究中心, 武漢 430063)

依托船舶自動識別系統(tǒng)(Automatic Identification System,AIS)數(shù)據(jù)，利用云計算并結(jié)合聚類算法，對船舶歷史數(shù)據(jù)進(jìn)行軌跡聚類分析，構(gòu)建船舶航行正常軌跡模型，為實時檢測船舶異常軌跡奠定基礎(chǔ)，進(jìn)而為提高水上交通監(jiān)管智能化水平提供新方法。針對目前軌跡聚類算法效率低等問題，基于Spark內(nèi)存計算技術(shù)及數(shù)據(jù)分區(qū)思想，提出一種改進(jìn)的并行子軌跡聚類算法SPDBSCANST(Parallel DBSCAN of Sub Trajectory Based on Spark)。以長江航道武漢段船舶航行數(shù)據(jù)為例進(jìn)行試驗驗證，并通過可視化方式呈現(xiàn)。結(jié)果表明，改進(jìn)后的算法的聚類效率和效果都有明顯提升。

水路運輸;船舶自動識別系統(tǒng)；Spark；軌跡聚類；正常軌跡建模

近年來，隨著國內(nèi)水運業(yè)迅速發(fā)展，長江干線的交通壓力日益增大,迫切需要提高水上交通監(jiān)管的智能化水平。因此，依托船舶自動識別系統(tǒng)(Automatic Identification System,AIS)數(shù)據(jù)，基于Spark云平臺，采用數(shù)據(jù)挖掘技術(shù)，對船舶航行軌跡進(jìn)行聚類分析，構(gòu)建正常軌跡模型，為發(fā)現(xiàn)和研究船舶運動特征及行為模式提供新思路。

現(xiàn)有的軌跡聚類算法[1]主要分為以下2大類:

1) 將整條軌跡作為研究對象進(jìn)行聚類。該類方法能比較直觀地評價軌跡間的相似性，受輸入?yún)?shù)的影響較小，但對復(fù)雜的軌跡容易忽略局部異常信息，且對高維軌跡數(shù)據(jù)的聚類效果欠佳。

2) 對復(fù)雜軌跡進(jìn)行劃分，將子軌跡作為聚類目標(biāo)。該方法能很好地識別軌跡的局部特征，有效處理高維軌跡數(shù)據(jù)，結(jié)合基于密度的DBSCAN聚類算法發(fā)現(xiàn)任意形狀的軌跡簇，但隨著數(shù)據(jù)規(guī)模的增大，DBSCAN算法會因消耗大量的I/O而造成聚類效率低下。

對此，結(jié)合數(shù)據(jù)分區(qū)思想和Spark云平臺高效并行的優(yōu)勢，提出一種改進(jìn)的基于軌跡分區(qū)預(yù)處理的并行化子軌跡聚類算法SPDBSCANST(Parallel DBSCAN of Sub Trajectory Based on Spark)。

1 子軌跡劃分及相似性度量方法

1.1基于AIS數(shù)據(jù)的船舶軌跡提取

受AIS設(shè)備自身及外界條件的限制[2]，通過AIS設(shè)備獲得的軌跡數(shù)據(jù)需經(jīng)過一系列預(yù)處理才可采用。將解碼后的AIS數(shù)據(jù)上傳到HDFS，使用Spark的filter算子選取一定范圍及一段時間內(nèi)的AIS數(shù)據(jù)，依據(jù)船舶水上移動通信業(yè)務(wù)標(biāo)識碼(Maritime Mobile Service Identity,MMSI),按時間順序提取出船舶軌跡。使用該方法提取出的軌跡通常會出現(xiàn)以下情況：

1) 區(qū)域內(nèi)存在多個往返。采用的解決方法是將MMSI相同的船舶軌跡分為多個軌跡，主要依據(jù)的是軌跡點之間的時間間隔。船舶在航行時，其AIS數(shù)據(jù)更新間隔一般不會超過10 min;而對于折返情況，其時間間隔通常遠(yuǎn)大于10 min。因此,可將往返軌跡劃分為多個軌跡。

2) 軌跡點位置偏移。計算軌跡點與其前后軌跡點之間的時間間隔及距離間隔,若該軌跡點與其前后點之間的時間間隔較小、距離間隔較大，而其前后點之間的時間間隔較小、距離間隔在正常范圍內(nèi)，則可將該軌跡點作為位置偏移點去除。

1.2子軌跡劃分

船舶在內(nèi)河航行時，受內(nèi)河形狀、寬度和深度等自身條件及橋梁、風(fēng)等周圍環(huán)境的影響，其航行軌跡和航速都會發(fā)生變化。通過設(shè)置船舶轉(zhuǎn)向角閾值及速度變化率閾值，對船舶軌跡進(jìn)行劃分，其中船舶轉(zhuǎn)向角是指相鄰子軌跡段的航跡向之差(見圖1)。

圖1 船舶轉(zhuǎn)向角

圖1中:a和b為船舶軌跡中相鄰的2條子軌跡段，其航跡向的夾角(即轉(zhuǎn)向角)為θ1。

速度變化率α的計算式為

(1)

式(1)中:υ2和υ1為相鄰軌跡點航速;Δt為相鄰時間間隔。

子軌跡劃分主要步驟：

1) 計算相鄰子軌跡段航跡向差值及相鄰軌跡點速度變化率。

2) 將所求值與預(yù)先設(shè)定的閾值相比較。

3) 若航跡向差值或速度變化率大于閾值，則使用該軌跡點對軌跡進(jìn)行劃分；否則返回步驟1)，繼續(xù)采樣。

1.3子軌跡相似性度量

船舶AIS數(shù)據(jù)中蘊含有豐富的信息[3]，在度量子軌跡的相似性時，應(yīng)充分考慮各類信息對子軌跡相似性的影響，從而提高聚類質(zhì)量。這里主要從船舶位置、航向和航速等3個方面進(jìn)行距離計算[1,4]，并通過歸一化加權(quán)求和得到子軌跡多特征距離，以此度量子軌跡之間的相似性。

1.3.1子軌跡間位置與航向距離計算

船舶軌跡劃分后可表示為子軌跡的集合。在進(jìn)行軌跡劃分時考慮軌跡段航跡向的變化，因此將劃分后的子軌跡近似作為線段進(jìn)行處理。

圖2為子軌跡間距離度量，其中:Li=siei和Lj=sjej分別為2條子軌跡;si和sj分別為子軌跡Li及Lj的起點;ei和ej分別為子軌跡Li及Lj的終點;ps和pe分別為sj及ej在Li(或Li延長線)上的投影。

圖2 子軌跡間距離度量

d//(Li,Lj),d⊥(Li,Lj)和dθ(Li,Lj)分別為子軌跡Lj到Li的水平距離、垂直距離及航向距離，具體計算式為

d//(Li,Lj)=min(l//1,l//2)

(2)

(3)

(4)

同理，可求得子軌跡Li到Lj的水平距離d//(Lj,Li)及垂直距離d⊥(Lj,Li)。根據(jù)Hausdroff距離定義，取二者中的較大值作為軌跡間的距離。即將子軌跡Li與Lj之間的水平距離d//,垂直距離d⊥及航向距離dθ定義為

1.3.2子軌跡間航速距離計算

船舶在內(nèi)河航行時，受內(nèi)河航道條件的限制，航行軌跡都比較固定，因此船舶航速是軌跡聚類的一個非常重要的要素。在現(xiàn)有的軌跡聚類算法中，通常只考慮平均航速，對航速信息的利用較少，從最大航速、最小航速、中位數(shù)航速及平均航速等4個方面綜合考慮航速距離的度量。其計算方法為

(8)

式(8)中:Smax(Li,Lj)=|Vmax(Li)-Vmax(Lj)|為2個子軌跡中軌跡點最大航速的差異值;Savg,Smin和Smed分別為平均航速、最小航速及中位數(shù)航速的差異值。

1.3.3綜合距離

在得到4種距離的度量方法之后，首先分別對4種距離進(jìn)行歸一化處理，然后定義相應(yīng)的權(quán)重W={W//,W⊥,Wθ,WS}，權(quán)重應(yīng)滿足：

(1) 均>0，即非負(fù)性；

(2)W//+W⊥+Wθ+WS=1。

在定義權(quán)重時，在不同的內(nèi)河航道條件及外部環(huán)境中所取的權(quán)重可以不同，例如：在較寬的航道，子軌跡間允許的垂直距離會增大，可減小W⊥。由于4種距離的量綱不同，因此在計算綜合距離之前需對4種距離進(jìn)行歸一化，歸一化公式為

(9)

式(9)中:d為處理前距離;dmax和dmin分別為該類距離的最大值及最小值;d′為處理后距離。由此,對4種歸一化后的距離進(jìn)行加權(quán)求和即可得到綜合距離，即

(10)

2 SPDBSCANST聚類算法

在采用DBSCAN算法對數(shù)據(jù)進(jìn)行聚類時，大量的I/O消耗導(dǎo)致時間劇增。[5]Spark分布式云平臺引入彈性分布式數(shù)據(jù)庫RDD(Resilient Distributed Dataset)的概念[6]，在計算中將數(shù)據(jù)分布式緩存在各節(jié)點內(nèi)存中，從而降低大量的磁盤I/O消耗?；赟park實現(xiàn)并行子軌跡DBSCAN聚類算法，首先對軌跡數(shù)據(jù)進(jìn)行分區(qū)預(yù)處理，分別對各分區(qū)子軌跡進(jìn)行聚類;然后對各鄰近區(qū)域進(jìn)行類簇合并，從而得到最終的軌跡聚類結(jié)果。由于Spark所有的計算都在內(nèi)存中對RDD進(jìn)行計算，中間無需與磁盤進(jìn)行I/O，因此能極大地提高聚類效率。SPDBSCANST聚類算法總體流程見圖3。

圖3 SPDBSCANST聚類算法總體流程

SPDBSCANST聚類算法偽代碼描述如下：

SPDBSCANST聚類算法

算法名稱：SPDBSCANST聚類算法

輸入：(1)鄰域ε，密度閾值minStr;

(2)軌跡數(shù)據(jù)，各分區(qū)經(jīng)度范圍;

(3)分區(qū)距離權(quán)重W{W//,W⊥,Wθ,WS}

輸出：全局軌跡類簇

BEGIN

1. rdd=sc.textFile(hdfs文件路徑) //將軌跡數(shù)據(jù)存入到rdd

2. rdd.map(d=>(num,d)) //依據(jù)分區(qū)經(jīng)度的范圍對軌跡數(shù)據(jù)進(jìn)行劃分，num為劃分后分區(qū)號

3. rdd.groupByKey() //按分區(qū)號聚合軌跡數(shù)據(jù)

4. rdd.map(BinOrderKey(_)) //對各分區(qū)內(nèi)數(shù)據(jù)進(jìn)行二次排序，提取船舶軌跡

5. rdd.map(seprate(_)) //分區(qū)子軌跡劃分

6. rdd.map(DBSCANST(_)) //子軌跡DBSCAN聚類

7. rdd.map(c=>(cnum,c)).reduceByKey() //合并鄰接子軌跡類簇

END

2.1軌跡數(shù)據(jù)分區(qū)處理

軌跡數(shù)據(jù)的分區(qū)可看作是對軌跡的初次子軌跡劃分。在進(jìn)行軌跡數(shù)據(jù)劃分時，由于內(nèi)河環(huán)境復(fù)雜，不一定依據(jù)經(jīng)度值(長江在緯度上可看成一條曲線)均勻劃分，可根據(jù)內(nèi)河特征進(jìn)行劃分，將軌跡劃分為橋梁區(qū)域、支流區(qū)域和彎道區(qū)域等。軌跡分區(qū)完成后，采用“1.2”節(jié)中的子軌跡劃分方法對各區(qū)域內(nèi)的軌跡進(jìn)行劃分。

2.2分區(qū)子軌跡聚類

采用DBSCAN聚類算法對各分區(qū)子軌跡進(jìn)行聚類[8]，使用式(10)度量子軌跡的相似性，依據(jù)分區(qū)特征，利用分區(qū)權(quán)值代替全局權(quán)值，從而提高聚類質(zhì)量。子軌跡DBSCAN聚類方法與典型的DBSCAN聚類方法類似，不同之處在于距離的度量方法。子軌跡DBSCAN聚類方法使用的距離為子軌跡對象之間的距離，而典型的DBSCAN聚類方法使用的距離為點對象之間的距離。鄰域為ε,密度閾值為minStr的子軌跡DBSCAN聚類算法相關(guān)定義如下。

1) 核心對象：給定子軌跡Li的ε鄰域內(nèi)的子軌跡數(shù)目大于或等于密度閾值minStr，具體定義為

2) 直接密度可達(dá)：對于子軌跡集合DTD，若子軌跡Li在Lj的鄰域ε內(nèi)，且子軌跡Lj為核心對象，則稱子軌跡Li為Lj直接密度可達(dá)。

3) 密度可達(dá)：對于子軌跡集合DTD，若存在子軌跡鏈L1，L2，…，Ln，對于Li∈DTD(1≤i≤n)存在Li+1從Li關(guān)于ε和minStr直接密度可達(dá)，則稱Ln為L1密度可達(dá)。

4) 密度相連：若存在子軌跡Lk，使得子軌跡Li和Lj都從Lk密度可達(dá)，則稱Li和Lj密度相連。

2.3局部類簇合并

在進(jìn)行區(qū)域劃分時，可將原本在全局中為同一類簇的子軌跡類簇劃分成2個局部類簇(見圖4)[9]。

圖4 軌跡類簇合并

圖4中,黑點代表子軌跡，p和q兩條子軌跡同時屬于分區(qū)L1及分區(qū)L2中的類簇，因此可對類簇進(jìn)行合并。具體合并方法為：

1) 確定劃分邊界鄰接區(qū)域，若子軌跡中存在軌跡點在鄰接區(qū)域內(nèi)，則將該子軌跡劃分到鄰接區(qū)域內(nèi)。

2) 遍歷鄰接區(qū)域內(nèi)所有的子軌跡，若存在子軌跡為核心對象且同時屬于2個局部類簇，則合并該局部類簇。

2.4船舶航行軌跡建模

經(jīng)過以上聚類過程即可得到船舶子軌跡類簇，在各子軌跡類簇中提取一系列采樣點(用SP表示采樣點)表征船舶典型軌跡。以下為船舶航行軌跡建模過程。

2.4.1確定各子軌跡類簇的方向(簇向)

取各子軌跡類簇中所有軌跡點航向的平均值作為簇向，具體計算方法為

(13)

2.4.2沿著對應(yīng)簇向劃分網(wǎng)格

沿著對應(yīng)簇向?qū)ψ榆壽E類簇進(jìn)行網(wǎng)格劃分(見圖5)。

圖5 類簇網(wǎng)格劃分

圖5中:矩形框表示子軌跡類簇;箭頭方向表示簇向;n為類簇劃分后的塊數(shù)，即該子軌跡類簇采樣點個數(shù)。n的值通過對類簇內(nèi)所有完整軌跡(同一MMSI)的軌跡點總數(shù)取平均確定，計算式為

(14)

式(14)中:numPi為第i條完整軌跡中軌跡點個數(shù);m為完整軌跡數(shù)。

2.4.3構(gòu)建采樣點

圖5中，每個網(wǎng)格構(gòu)建1個采樣點SPi，采樣點有4個特征屬性,分別為平均經(jīng)度LONavg,平均緯度LATavg,平均航速SPDavg和平均航向COUavg，具體表示為

SPi={LONavg,LATavg,SPDavg,COUavg}

(15)

使用采樣點表征船舶典型軌跡，具體表示為

TR={SP1,SP2,…,SPn}

(16)

3 試驗及分析

試驗在武漢理工大學(xué)國家水運安全工程技術(shù)研究中心的Spark云服務(wù)平臺上完成，創(chuàng)建6臺虛擬機組成一個集群。處理器配置：8核；內(nèi)存8G；硬盤300G。軟件環(huán)境選擇CentOS系統(tǒng)；Spark1.6.1；Hadoop2.6.4；IDEA3.4；Scala2.10.8；可視化工具使用Mapv。選取一臺虛擬機作為主節(jié)點master，其余為工作節(jié)點worker。試驗分為改進(jìn)后算法對聚類效率的提升和聚類效果的展示2部分。

3.1Spark云平臺下軌跡聚類效率分析

選取長江航道武漢段2016年2月份的AIS數(shù)據(jù)作為試驗數(shù)據(jù)。為在不同數(shù)據(jù)量下對算法的效率進(jìn)行對比，分別選取大約500M(1 000萬條預(yù)處理后AIS數(shù)據(jù)，只包含緯度、經(jīng)度、速度、方向、MMSI及時間)和2G的數(shù)據(jù)量進(jìn)行試驗，結(jié)果見圖6。

圖6 算法執(zhí)行時間對比

從圖6中可看出:隨著集群節(jié)點個數(shù)的增加，算法執(zhí)行時間縮短，最后趨于平穩(wěn);數(shù)據(jù)量越大，算法的加速比越高，從而說明改進(jìn)后的算法對大數(shù)據(jù)具有很好的適應(yīng)性。

由此可見，利用Spark云平臺能有效提高海量AIS數(shù)據(jù)的處理效率，數(shù)據(jù)量越大，效果越明顯，從而為高效、大規(guī)模地進(jìn)行船舶航行軌跡分析奠定基礎(chǔ)。

3.2聚類效果展示

選取長江航道武漢段2016年2月份大船(船長>80 m)的AIS數(shù)據(jù)作為試驗數(shù)據(jù)，經(jīng)度值在[114.23°,114.56°]，緯度值在[30.447°,30.73°]，對數(shù)據(jù)進(jìn)行預(yù)處理之后，有效AIS數(shù)據(jù)為1 948 581條;將軌跡數(shù)據(jù)劃分為20個區(qū)域，對各分區(qū)進(jìn)行子軌跡劃分，劃分后子軌跡有96 566條。該部分試驗主要分為3部分進(jìn)行，分別為鄰域ε及密度閾值minStr的確定、不同航道條件下綜合距離權(quán)值的確定和典型軌跡提取。

3.2.1鄰域ε及密度閾值minStr的確定

在距離權(quán)值(如式(10)所示)相等(都為0.25)的情況下，對軌跡間距離進(jìn)行統(tǒng)計，結(jié)果表明軌跡間距離大多集中在(0～0.01)范圍內(nèi)，故取鄰域ε=0.01。由于船舶軌跡受航道限制，故軌跡間相似性都比較高，經(jīng)過多次試驗后，當(dāng)密度閾值minStr=20時，聚類結(jié)果比較理想。圖7為船舶軌跡聚類前后對比。

a) 聚類前船舶軌跡

b) 聚類后船舶軌跡

3.2.2綜合距離權(quán)值的確定

從圖7a)中可看出，對所有分區(qū)使用相同的距離權(quán)值時，一些分區(qū)內(nèi)的聚類結(jié)果不盡如人意(圖8a)和9a)為放大后的2個分區(qū))，因此需基于航道特征確定各距離權(quán)值。綜合距離從垂直距離、平行距離、角度距離及速度距離等4方面考慮，依據(jù)航道特征將航道劃分為限速區(qū)域(橋區(qū)，港口等)、限寬區(qū)域(寬航道/窄航道)及彎道區(qū)域。

由圖8a)可知，該航道內(nèi)有武漢長江大橋、長江二橋及漢江匯流，因此該區(qū)域內(nèi)船舶的航速會受到限制，增大航速距離權(quán)值將加大航速對軌跡聚類的影響；圖8b)為修改權(quán)重W=(0.2,0.2,0.2,0.4)后的聚類效果，可發(fā)現(xiàn)修改權(quán)值后聚類效果有明顯提升。

b) 修改后

由圖9a)可知，該航道為夾水道，航道較窄，在該區(qū)域內(nèi)船舶間垂直距離受到限制，故增大垂直距離權(quán)值，從而增大垂直距離對聚類效果的影響;圖9b)為修改權(quán)值W=(0.15,0.4,0.2,0.25)后聚類效果，可發(fā)現(xiàn)聚類效果有較大改善。

a) 修改前

b) 修改后

3.2.3典型軌跡提取

在確定各分區(qū)距離權(quán)值之后，采用“2.4”節(jié)給出的方法構(gòu)建船舶航行軌跡。圖10為船舶典型軌跡提取，其中黑點為提取出的2條典型軌跡(分別為上行和下行)。

圖10 船舶典型軌跡提取

4 結(jié)束語

基于Spark云平臺，對船舶子軌跡聚類方法進(jìn)行研究，構(gòu)建船舶航行軌跡，并以長江航道武漢段2016年2月份的AIS數(shù)據(jù)為試?yán)M(jìn)行驗證。通過在Spark云平臺上對船舶子軌跡聚類算法進(jìn)行并行化設(shè)計，可極大地提高軌跡聚類效率，為進(jìn)一步研究船舶運動特征、行為模式及船舶軌跡實時異常檢測等提供技術(shù)保障。

[1] 肖瀟, 邵哲平, 潘家財,等. 基于AIS信息的船舶軌跡聚類模型及應(yīng)用[J]. 中國航海, 2015, 38(2):82-86.

[2] 魏照坤. 基于 AIS 的船舶軌跡聚類與應(yīng)用[D]. 大連： 大連海事大學(xué),2015.

[3] 劉暢. 船舶自動識別系統(tǒng)(AIS)關(guān)鍵技術(shù)研究[D].大連:大連海事大學(xué),2013.

[4] LIU B, DE SOUZA E N, MATWIN S, et al. Know-ledge-Based Clustering of Ship Trajectories Using Density-Based Approach[C]// IEEE International Conference on Big Data. IEEE, 2014:603-60.

[5] 賴麗萍, 聶瑞華, 汪疆平,等. 基于MapReduce的改進(jìn)DBSCAN算法[J]. 計算機科學(xué), 2015(S2):396-399.

[6] 王桂蘭, 周國亮, 薩初日拉,等. Spark環(huán)境下的并行模糊C均值聚類算法[J]. 計算機應(yīng)用, 2016, 36(2):342-347.

[7] 朱飛祥, 張英俊, 高宗江. 基于數(shù)據(jù)挖掘的船舶行為研究[J]. 中國航海, 2012, 35(2):50-54.

[8] DAI B R, LIN I C. Efficient Map/Reduce-Based DBSCAN Algorithm with Optimized Data Partition[C]// IEEE Fifth International Conference on Cloud Computing. IEEE Computer Society, 2012:59-66.

[9] SARAZIN T, AZZAG H, LEBBAH M. SOM Clustering Using Spark-MapReduce[C]// Parallel & Distributed Processing Symposium Workshops. IEEE, 2015.

ClusteringMethodofShip’sNavigationTrajectorySetBasedonSpark

PENGXiangwena,GAOShua,CHUXiuminb,HEYanga,LUConga

(a. School of Computer Science and Technology; b. National Water Transportation Safety Engineering Technology Research Center, Wuhan University of Technology, Wuhan 430063, China)

Constructing normal navigation trajectory model through processing historical AIS(Automatic Identification System) data of ships with the trajectory clustering algorithm is a way of setting up the reference for real-time detection of abnormal ships trajectory. Aimed at the problem of low efficiency of the current trajectory clustering algorithm, an improved parallel sub trajectory clustering algorithm is proposed named as SPDBSCANST (Parallel DBSCAN of Sub Trajectory Based on Spark) featuring Spark memory computing technology and data partition. The algorithm is verified with the ship navigation data of Yangtze River Waterway. The visualization of the trajectories is also achieved. The experiments show that the efficiency of the improved clustering algorithm is increased significantly.

waterway transportation; AIS； Spark； trajectory clustering； normal trajectory modeling

U675.7

A