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

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

2017-04-25

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

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

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

1000-4653(2017)03-0049-05

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

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

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

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

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

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

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

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

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

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

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

1.1基于AIS數據的船舶軌跡提取

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

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

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

1.2子軌跡劃分

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

圖1 船舶轉向角

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

速度變化率α的計算式為

(1)

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

子軌跡劃分主要步驟：

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

2) 將所求值與預先設定的閾值相比較。

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

1.3子軌跡相似性度量

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

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

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

圖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)。根據Hausdroff距離定義，取二者中的較大值作為軌跡間的距離。即將子軌跡Li與Lj之間的水平距離d//,垂直距離d⊥及航向距離dθ定義為

1.3.2子軌跡間航速距離計算

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

(8)

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

1.3.3綜合距離

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

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

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

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

(9)

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

(10)

2 SPDBSCANST聚類算法

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

圖3 SPDBSCANST聚類算法總體流程

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

SPDBSCANST聚類算法

算法名稱：SPDBSCANST聚類算法

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

(2)軌跡數據，各分區(qū)經度范圍;

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

輸出：全局軌跡類簇

BEGIN

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

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

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

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

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

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

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

END

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

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

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

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

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

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

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

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

2.3局部類簇合并

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

圖4 軌跡類簇合并

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

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

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

2.4船舶航行軌跡建模

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

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

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

(13)

2.4.2沿著對應簇向劃分網格

沿著對應簇向對子軌跡類簇進行網格劃分(見圖5)。

圖5 類簇網格劃分

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

(14)

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

2.4.3構建采樣點

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

SPi={LONavg,LATavg,SPDavg,COUavg}

(15)

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

TR={SP1,SP2,…,SPn}

(16)

3 試驗及分析

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

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

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

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

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

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

3.2聚類效果展示

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

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

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

a) 聚類前船舶軌跡

b) 聚類后船舶軌跡

3.2.2綜合距離權值的確定

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

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

b) 修改后

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

a) 修改前

b) 修改后

3.2.3典型軌跡提取

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

圖10 船舶典型軌跡提取

4 結束語

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

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

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

[3] 劉暢. 船舶自動識別系統(tǒng)(AIS)關鍵技術研究[D].大連:大連海事大學,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的改進DBSCAN算法[J]. 計算機科學, 2015(S2):396-399.

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

[7] 朱飛祥, 張英俊, 高宗江. 基于數據挖掘的船舶行為研究[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