一種高效的船舶活動熱點海域探測算法

楊 樂 包 磊 羅 兵

(海軍工程大學電子工程學院 湖北 武漢 430033)

?

一種高效的船舶活動熱點海域探測算法

楊 樂 包 磊 羅 兵

(海軍工程大學電子工程學院 湖北 武漢 430033)

針對傳統數據處理工具處理海洋船舶位置大數據效率低、空間特征不敏感的問題，引入SpatialHadoop空間大數據處理平臺，提出一種基于SpatialHadoop的船舶活動熱點海域探測算法。該算法結合空間索引和MapReduce分布式處理框架實現了基于區域統計的熱點海域探測方法。從理論上分析，該方法能夠高效地探測船舶活動熱點海域。利用真實AIS數據進行實驗，并從不同海域和算法運行效率兩個方面對實驗結果進行了對比分析，結果表明該算法具有有效的探測結果和較高的處理效率，驗證了理論分析的正確性。

位置大數據 熱點探測 空間大數據平臺 空間索引

0 引 言

隨著船載自動定位系統(AIS)的安裝普及[1]，規模巨大的海洋船舶活動所產生的軌跡數據呈現大數據態勢。海洋船舶軌跡大數據富含位置信息和時間標識，屬于位置大數據的范疇，具有數據量大、信息碎片化、單記錄價值低和準確性低等位置大數據普遍擁有的特點[2]。海洋船舶位置數據與城市交通軌跡數據類似，在時空域內并不是均勻分布的，而是表現出明顯的聚集特性，這種聚集性常用“熱點海域”來表達。熱點海域較其余海域而言，具有數據集中、信息豐富、模式多樣等特點，因此熱點海域的研究具有十分重要的價值。研究熱點海域首先需要探測發現熱點海域，有效的探測結果為熱點海域的研究提供基礎支撐。

熱點海域探測是指通過某種方法識別船舶活動密集且彼此分離的區域或時段。該方向的研究國內外較少，但是對于船舶位置數據的分析與研究較為豐富，其主要涉及聚類分析、關聯分析和異常檢測等方向，也取得了一定的研究成果[3-5]。但是，大多研究仍沿用傳統的分析工具，這導致船舶位置數據的分析面臨著兩大瓶頸問題：① 傳統工具的串行處理方式無法滿足海量位置數據對于處理速度的要求；② 傳統工具的空間數據特征不敏感性制約著處理效率的提升。

針對上述問題，本文結合了位置數據熱點探測相關方法，提出了基于空間大數據平臺的熱點海域探測算法。該算法彌補了傳統位置數據熱點探測算法串行計算方式和數據空間特征不敏感性的缺點，很好地提升了探測效率，為下一步熱點海域模式挖掘和價值提取提供了支撐。文中采用真實AIS數據進行實驗，實驗結果也驗證了該算法的高效性。

1 相關研究

1.1 空間大數據平臺

大數據處理工具與方法的研究是目前研究的熱點領域，分析該領域國內外研究現狀可以發現，該領域的研究仍處于起步階段。大數據處理工具的架構大多基于Hadoop技術，同時大量的研究集中在大數據分析方法上，支撐大數據平臺開發的相關技術體系還沒有形成[6]。關于大數據處理平臺工具，國內已有一些研究開發，比如中國移動研究院研發的基于云計算平臺的并行數據挖掘工具BC-PDM，廈門大學數據挖掘研究中心與臺灣銘傳大學、中華資料采礦協會合作開發的一套基于云計算的數據挖掘決策支持系統─—云端數據挖掘決策系統(MCU Smart Score)，以及基于Hadoop中科院計算所研制的并行數據挖掘工具平臺PDMiner。以上大數據處理工具只是實現了對事務性海量數據的并行化挖掘分析，并沒有針對空間數據進行特殊設計，還無法高效存儲、分析和挖掘空間數據。關于空間大數據平臺，國外已有相關研究實踐，明尼蘇達大學計算科學與工程系Ahmed和Mohamed兩人基于Hadoop大數據平臺進行拓展，開發了一款專門用于空間大數據處理的平臺SpatialHadoop[7]。該平臺改變了傳統Hadoop數據存儲的堆文件方式，使用全局索引和局部索引相結合的兩級大數據空間索引結構。該空間索引結構為平臺提供了數據空間特征的敏感性，使數據的選取十分高效，從而提高了空間數據的處理效率。目前該平臺提供空間Grid、Rtree和R+tree三類空間索引。

1.2 熱點區域探測

由于海洋船舶交通位置數據與犯罪位置數據、交通軌跡數據在數據特征上存在著極大的相似性，加之犯罪熱點區域探測和交通軌跡熱點區域探測的一些理論方法對于熱點海域的探測具有十分重要的借鑒意義。因此可將熱點海域探測問題、犯罪熱點區域探測問題以及交通軌跡熱點區域探測問題統稱為位置數據熱點區域探測問題。

關于位置數據熱點區域探測方法的研究，主要是面向小量數據集。成熟的探測方法可分為兩大類：基于離散點的熱點區域探測方法和基于區域統計數據的熱點區域探測方法[8]。基于離散點的熱點區域探測方法主要是指模式分析中的空間聚類方法，主要有統計法、分割法、層次聚類法和密度估計法。基于區域統計數據的熱點區域探測方法，一般是指以某固定大小的區域為單位子區域計算每個子區域內的位置點總量、位置點密度等統計指標，再利用相關算法確定某時段內的“熱點區域”或者某區域內的“熱點時間段”，也可對熱點區域數據類型進行分析，從而探測“熱點類型”。兩類方法的區別在于：前者基于離散點進行聚類處理，探測結果精度相對較高，而計算復雜度非常高；而后者基于子區域位置數據點統計結果進行處理，結果的精確度相對減小，但是計算復雜度降低的程度更加可觀。熱點海域探測對于探測結果精度的要求并非很高，使用基于離散點的熱點探測方法造成精度冗余的同時又增加了算法的復雜度，因此本文采用基于區域統計的熱點海域探測方法。

對于海洋船舶交通大數據而言，熱點海域的實時探測和海量歷史積累數據的熱點區域探測處理對于算法計算速度的要求非常高。基于區域統計的熱點海域探測方法雖然在一定程度上降低了計算復雜度，但是仍不滿足實際要求。因此，本文引入空間大數據處理平臺，提出了一種基于SpatialHadoop的熱點海域探測算法，較大程度上提高了計算效率。

2 熱點海域探測算法

2.1 算法設計思路

船舶熱點海域探測算法是在已知的全海域尋找船舶分布比較密集的網格子海域集，其算法內容包括：基于SpatialHadoop平臺實現敏感海域船舶位置數據提取，網格化分區和網格子海域內船舶數量統計的MapReduce化，以及使用迭代裁剪的方法獲取熱點海域。

基于SpatialHadoop平臺的敏感海域數據提取的實現首先需要為全球海域數據建立空間Rtree索引。空間Rtree索引的建立包括數據分割，本地索引建立和全區索引建立三個階段。在數據分割階段需要滿足三個要求：① 每個分割塊的數據量滿足HDFS塊大小；② 空間相鄰的位置點被分割在同一個塊內；③ 所有分割塊的負載均衡。本地索引是為數據分割結果建立Rtree索引，以便實現節點內數據的快速查找。全局索引建立于節點之間，索引文件存儲于主節點，一旦MapReduce開始運行，可快速定位存儲數據的子節點位置。然后，使用SpatialHadoop自帶的區域查詢功能，獲取敏感區域的船舶位置數據集。區域查詢是在Rtree空間索引結構之上實現的MapReduce并行化數據提取處理。該功能首先基于Rtree索引結構濾除不包含查詢區域的數據分區，接著針對剩余的數據分區實行并行化篩選處理。基于SpatialHadoop平臺實現敏感海域船舶位置數據提取的技術框架見圖1。

圖1 敏感海域船舶位置數據提取技術圖

獲取敏感海域船舶位置數據之后，由于敏感海域范圍的粗略性，需要進行細化分區統計處理。該步采用網格化分區方法對敏感海域船舶位置數據進行分區處理，并統計每個子網格內的船舶數量。由于船舶位置數據實例的相互獨立性，因此可以采用MapReduce編程框架進行并行化處理。Map函數的數目由網格子海域分區的數量確定，在Map階段實現船舶位置數據與網格子海域的匹配。由于Map與Reduce階段不涉及Map間的數據交換，每個Map函數對應一個Reduce函數，因此Reduce函數的數量與Map函數保持一致，在Reduce階段實現網格子海域船舶數量的統計。

船舶活動熱點海域的獲取是建立在網格子海域船舶數量統計結果的基礎之上實現的。通過迭代裁剪敏感海域中對船舶存在密度沒有貢獻或者貢獻較小的網格子海域，直至滿足最終的熱點海域船舶存在密度閾值，具體的裁剪方法在后文有詳細描述。

2.2 算法高效性理論分析

從理論角度分析，該算法較傳統方法有更高的執行效率，其主要表現在兩個方面：

(1) 并行化處理

該算法從敏感海域位置數據提取、網格化分區和網格子海域內船舶數量統計均采用了并行化處理方式。因此該算法并行化程度強，與傳統串行方法相比較而言，必然較大程度上提高了執行效率。

(2) 空間數據索引

在并行化基礎之上，該算法建立了位置數據空間索引。該算法在并行化處理之前基于空間索引結構已經濾除了大量的不相關數據分區。因此，減少了計算量，提高了計算效率。性能遠遠優于傳統的串行處理方法，與優于純粹的算法并行化。

2.3 算法具體實現步驟

(1) 建立全球海域船舶位置數據Rtree索引。

(2) 設定敏感海域C，提取敏感海域船舶位置數據。

(3) 計算敏感海域C的初始船舶存在密度，記為ρ0(船舶存在密度計算公式為：ρ=Q/S，其中Q表示海域的船舶總量，S表示海域面積；初始船舶存在密度ρ0=Q0/S0，其中Q0表示敏感海域的初始船舶總量，S0表示敏感海域初始面積)。

(4) 將敏感海域C按經緯度平均劃分為N(N=X×Y，X為行數Y為列數)塊網格子海域，并分別記為Rij(i表示行號，j表示第列號)，統計網格子海域Rij內的船舶數量。

(5) 裁剪C的任意行網格子海域Ri或列網格子海域Rj，使裁剪后海域C的船舶存在密度最大并記為ρ(如果裁剪多行網格子海域或多列網格子海域或多行列網格子海域組合后，海域C的船舶存在密度相同，那么同時裁剪該多行或多列或多行列組合)。

(6) 判斷C的存在密度ρ是否滿足條件：ρ≥n×ρ0，如果滿足算法結束，否則返回執行步驟5(其中n∈N+)。

為了讀者更清楚地了解裁剪步驟，本節提供一個裁剪示例。設有敏感海域C，其中Q0=50，S0=25，計算得ρ0=2。將全海域C平均劃分為25(X=Y=5)個子海域，存在密度閾值取n=3。經過三次迭代裁剪后獲得最終結果，裁剪具體過程見圖2。

圖2 海域裁剪過程圖

3 實驗結果及分析

3.1 實驗環境

實驗選取4臺計算機搭建SpatialHadoop平臺，計算機系統采用Ubuntu Linux 14.04，SpatialHadoop版本采用SpatialHadoop 2.3，其中1臺機器作為Master和JobTracker控制節點，其余3臺機器作為Slave和TaskTracker計算節點。機器的基本配置見表1。

表1 各個節點的基本配置

3.2 實驗數據選取

實驗數據選自真實的AIS歷史數據。AIS是海上船舶自動定位數據，數據屬于結構化數據，有著規整的數據格式，十分利于實驗處理。本實驗選取2012年1月的全球AIS數據，數據量約102 GB。實驗之前，對數據采取預處理操作，剔除了錯誤數據和格式有誤數據。

選取南沙群島及周邊海域作為敏感海域，通過查閱世界地圖確定粗略的南沙島嶼經緯度范圍為110°E～118°E，4°N～12°N，其中包括遠洋海域數據(南沙海域)和近岸海域數據(馬來西亞西海岸)。

3.3 結果對比分析

獲取敏感海域船舶交通位置數據后，依照經緯度將敏感海域等值網格化，網格的劃分數量確定為100×100個網格。統計各網格內船舶數量并繪制海域船舶存在密度圖態勢圖，如圖3所示。

圖3 海域船舶存在密度態勢圖

觀察圖3易見，遠洋海域數據與近岸海域數據在數據密度上存在較大的差異，直接影響算法處理結果的準確性，因此將遠洋海域數據與近岸海域數據區分處理。依據我國南海劃界九段線將研究海域劃分為遠洋海域和近岸海域，劃分結果見圖3，其中虛線以上為遠洋海域，虛線以下為近岸海域。

下面從不同海域和算法性能兩個角度對實驗結果和算法性能進行了對比分析。

3.3.1 不同海域實驗結果對比

實驗對近岸海域數據與遠洋海域數據分別進行處理，根據處理結果繪制熱點海域面積占比與熱點海域船舶數量占比隨n值增大的變化趨勢，如圖4所示。

(a) 近岸海域

(b) 遠洋海域圖4 熱點海域面積占比與熱點海域船舶數量占比隨n值增大變化趨勢圖

由圖4可見，隨n值增大，熱點海域船舶數量占比和熱點海域面積占比普遍呈減小趨勢。但是，熱點海域船舶數量占比減小的速度較為平穩，減小速度沒有明顯的變小或變大趨勢，而熱點海域面積占比的減小速度隨n值增大呈下降趨勢，以致于最后熱點海域面積占比趨于穩定。由此可見，隨n值增大熱點海域面積占比存在一個臨界穩定值，此臨界穩定值對應的算法探測結果可被確定為熱點海域。

另外，近岸海域與遠洋海域相比較而言，近岸熱點海域臨界穩定值對應的n值較大且隨n值增大近岸熱點海域船舶數量占比下降速度較慢。這與近岸海域船舶存在密度普遍較大，船舶空間分布較均勻的事實相一致，這證實了算法的有效性和實驗結果的正確性。

基于上圖實驗結果分析，選取n=100和n=39為近岸海域和遠洋海域的熱點海域探測閾值，并將所對應的熱點海域探測結果顯示在船舶存在密度態勢圖中，見圖5。

(a) 近岸海域

(b) 遠洋海域圖5 熱點海域探測結果顯示圖

3.3.2 算法性能比較

選擇不同的網格劃分數量，比較基于傳統處理工具的探測算法與基于SpatialHadoop的探測算法的運行速度，實驗結果見表2。

表2 算法執行速度比較表

由表2可見，基于SpatialHadoop船舶交通位置數據熱點海域探測算法執行速度明顯快于基于傳統工具的船舶交通位置數據熱點海域探測算法，與實驗設計的初衷相符，同時驗證了SpatialHadoop平臺在處理空間大數據上的優勢。

4 結 語

對于海洋船舶交通位置大數據分析而言，傳統處理工具與方法暴露出時間復雜度高，空間特征不敏感等缺點。針對這些缺點，本文提出了基于SpatialHadoop的熱點海域探測算法。該算法結合了空間數據索引和MapReduce并行化處理方法，很好地解決了上述缺點。

正如前文所述，船舶活動熱點海域具有數據集中、信息豐富、模式多樣等特點。熱點海域內部信息提取與模式挖掘具有十分重要的價值與意義。利用相關統計與挖掘方法分析熱點海域，這是下一步研究的內容之一。同時，海洋探測較普通空間位置探測而言存在其獨特性。將更多地挖掘分析海洋探測較普通空間位置探測的特點，提出適應性更強的海洋探測算法。

[1] Iphar C, Napoli A, Ray C. Data Quality Assessment For Maritime Situation Awareness[J]. Remote Sensing and Spatial Information Sciences, 2015, 2(3): 291-295.

[2] 劉經南, 方媛, 郭遲,等. 位置大數據的分析處理研究進展[J]. 武漢大學學報(信息科學版), 2014, 39(4):379-385.

[3] Scrofani J W, Tummala M, Miller D, et al. Behavioral detection in the maritime domain[C]// System of Systems Engineering Conference. IEEE, 2015:380-385.

[4] Iphar C, Napoli A, Ray C. Detection of false AIS messages for the improvement of maritime situational awareness[C]// Oceans’2015, Oct 2015, Washington, DC, United Stateds.

[5] Liu B, De Souza E N, Matwin S, et al. Knowledge-based clustering of ship trajectories using density-based approach[C]// IEEE International Conference on Big Data. IEEE, 2014:603-608.

[6] 宮夏屹, 李伯虎, 柴旭東,等. 大數據平臺技術綜述[J]. 系統仿真學報, 2014, 26(3):489-496.

[7] Eldawy A, Mokbel M F. SpatialHadoop: A MapReduce framework for spatial data[C]// IEEE, International Conference on Data Engineering. IEEE, 2015:1352-1363.

[8] 陸娟, 湯國安, 張宏,等. 犯罪熱點時空分布研究方法綜述[J]. 地理科學進展, 2012, 31(4):29-35.

ANEFFICIENTHOTSPOTSDETECTIONALGORITHMOFVESSELSACTIVITY

Yang Le Bao Lei Luo Bing
(SchoolofElectronicEngineering,NavalUniversityofEngineering,Wuhan430033,Hubei,China)

Traditional data processing tools were inefficient and not sensitive to spatial characteristics when processing traffic location big data of marine vessel. Aiming at the problem, the SpatialHadoop platform is introduced and a hotspots detection algorithm based on this platform is proposed. The algorithm combined the spatial index with MapReduce distributed processing framework which realized the method of hotspots detection based on regional statistics. In theory, the method could efficiently detect hotspots of vessels activities. Experiment was done on the real AIS data and the result indicated that the method had effective detection result and higher efficiency.

Position big data Hotspots detection SpatialHadoop Spatial index

2016-07-26。楊樂，碩士生，主研領域：時空數據挖掘。包磊，教授。羅兵，講師。

TP311

A

10.3969/j.issn.1000-386x.2017.08.053