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

楊 樂 包 磊 羅 兵

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

?

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

楊 樂 包 磊 羅 兵

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

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

位置大數(shù)據(jù) 熱點探測 空間大數(shù)據(jù)平臺 空間索引

0 引 言

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

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

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

1 相關研究

1.1 空間大數(shù)據(jù)平臺

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

1.2 熱點區(qū)域探測

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

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

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

2 熱點海域探測算法

2.1 算法設計思路

船舶熱點海域探測算法是在已知的全海域?qū)ふ掖胺植急容^密集的網(wǎng)格子海域集，其算法內(nèi)容包括：基于SpatialHadoop平臺實現(xiàn)敏感海域船舶位置數(shù)據(jù)提取，網(wǎng)格化分區(qū)和網(wǎng)格子海域內(nèi)船舶數(shù)量統(tǒng)計的MapReduce化，以及使用迭代裁剪的方法獲取熱點海域。

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

圖1 敏感海域船舶位置數(shù)據(jù)提取技術(shù)圖

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

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

2.2 算法高效性理論分析

從理論角度分析，該算法較傳統(tǒng)方法有更高的執(zhí)行效率，其主要表現(xiàn)在兩個方面：

(1) 并行化處理

該算法從敏感海域位置數(shù)據(jù)提取、網(wǎng)格化分區(qū)和網(wǎng)格子海域內(nèi)船舶數(shù)量統(tǒng)計均采用了并行化處理方式。因此該算法并行化程度強，與傳統(tǒng)串行方法相比較而言，必然較大程度上提高了執(zhí)行效率。

(2) 空間數(shù)據(jù)索引

在并行化基礎之上，該算法建立了位置數(shù)據(jù)空間索引。該算法在并行化處理之前基于空間索引結(jié)構(gòu)已經(jīng)濾除了大量的不相關數(shù)據(jù)分區(qū)。因此，減少了計算量，提高了計算效率。性能遠遠優(yōu)于傳統(tǒng)的串行處理方法，與優(yōu)于純粹的算法并行化。

2.3 算法具體實現(xiàn)步驟

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

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

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

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

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

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

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

圖2 海域裁剪過程圖

3 實驗結(jié)果及分析

3.1 實驗環(huán)境

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

表1 各個節(jié)點的基本配置

3.2 實驗數(shù)據(jù)選取

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

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

3.3 結(jié)果對比分析

獲取敏感海域船舶交通位置數(shù)據(jù)后，依照經(jīng)緯度將敏感海域等值網(wǎng)格化，網(wǎng)格的劃分數(shù)量確定為100×100個網(wǎng)格。統(tǒng)計各網(wǎng)格內(nèi)船舶數(shù)量并繪制海域船舶存在密度圖態(tài)勢圖，如圖3所示。

圖3 海域船舶存在密度態(tài)勢圖

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

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

3.3.1 不同海域?qū)嶒灲Y(jié)果對比

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

(a) 近岸海域

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

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

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

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

(a) 近岸海域

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

3.3.2 算法性能比較

選擇不同的網(wǎng)格劃分數(shù)量，比較基于傳統(tǒng)處理工具的探測算法與基于SpatialHadoop的探測算法的運行速度，實驗結(jié)果見表2。

表2 算法執(zhí)行速度比較表

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

4 結(jié) 語

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

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

[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īng)南, 方媛, 郭遲,等. 位置大數(shù)據(jù)的分析處理研究進展[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] 宮夏屹, 李伯虎, 柴旭東,等. 大數(shù)據(jù)平臺技術(shù)綜述[J]. 系統(tǒng)仿真學報, 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。楊樂，碩士生，主研領域：時空數(shù)據(jù)挖掘。包磊，教授。羅兵，講師。

TP311

A

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