船舶AIS 數據時空共現模式挖掘?

包 磊 彭慶喜

（武漢東湖學院計算機科學學院 武漢 430079）

1 引言

隨著地理信息的不斷泛化，船舶軌跡數據的獲取與計算能力不斷發展。其中船舶自動識別系統（Auto Identification System，AIS）網絡所收集的大量船舶航跡信息眾源數據，是船舶軌跡數據的重要組成部分。同時，雷達、觀通以及衛星系統主動獲取的大量情報態勢數據和Argo、海王星等諸多海洋觀測計劃所采集的海量海洋環境數據，構成一個數據量龐大、內容豐富，且數據量急劇增長的數據集。運動模式挖掘是目前領域中一個發展迅速的前沿研究課題，通過軌跡模式挖掘算法可以發現軌跡大數據中有價值的模式從而分析船舶的運動趨勢和運動規律，以感知態勢、獲取更經濟安全的導航信息。

2 相關研究現狀

時空共現模式挖掘［1］是運動模式挖掘的一個典型問題，是指2 種（或2 種以上）對象實例在空間和時間上處于鄰近。利用船舶軌跡數據進行時空共現模式挖掘具有巨大的應用價值。例如，走私交易船舶在航行中會出現長時間處于共現行為模式；艦艇海上執行任務期間常以編隊出航，不同的編隊組織形式意味著執行不同的作戰任務，這種編隊組織形式可以基于時空共現模式進行挖掘分析；海盜在實施非法行動之前的航行行為常會進行長時間近距離的跟蹤觀察，同樣可以使用時空共現模式挖掘方法進行實時發現，進而為軍事領域作戰計劃和戰術動作發現，交通領域道路和網絡計劃，以及國土防衛中的標志性事件關聯分析［2］提供有效的分析計算手段。

目前與時空共現模式相關的大多數研究結果都在空間共現模式基礎上進行時間維擴展得到，所采用的方法基礎以Apriori 算法為主，如celik 定義了一種混合時空共現模式度量方法，提出一種混合時空共生模式算法，并對該算法進行了正確性和完備性分析［2］，以及一種時空部分共現模式的挖掘算法［3］，用于發現動物遷徙中的固定模式和運動常用的戰術行動［4～5］。文獻［6］分析了從時空數據中挖掘不同移動對象間頻繁共現子序列的問題，提出一種二階段挖掘算法，先用hash函數將原始軌跡轉換成具有相近特征的子序列，然后利用Apriori算法挖掘其中的頻繁片段。文獻［7］結合了時間維和空間維的度量問題，提出一種時空共現模式發現算法COSTCOP，在模式挖掘過程中綜合考慮了時間維度量和空間維度量問題。

然而，海量的海上位置數據為時空共現模式的挖掘提出了新的要求，而目前海上位置數據信息量早已達到了TB 級別，且呈持續增長的趨勢。僅僅以AIS 數據為例，全球每天通過衛星和基站收集的AIS 數據約為4G，一年產生的AIS 數據量可達1.4TB。現有的研究成果多基于少量數據樣本，無法應對巨大的數據量。且傳統挖掘算法的串行計算方式和空間特征不敏感的特點限制了共現模式挖掘的速度。針對這些問題，本文基于空間Hadoop分析平臺架構，提出了海上位置大數據下的時空共現模式挖掘算法，通過采用兩級空間索引劃分原始數據集，在給出的擴展MapReduce架構上實現了船舶軌跡數據中的時空共現模式挖掘。基于AIS 實際數據集的實驗結果顯示，能夠有效處理大規模船舶軌跡數據，并保持良好的效率和正確性。

3 船舶時空共現模型

船舶時空共現模式指船舶在位置和時間標識上滿足某種鄰近關系。這種鄰近關系的判定通過實例時空鄰近參與度來描述。

1）鄰近關系

鄰近關系包括空間鄰近關系和時間鄰近關系。空間鄰近關系采用歐式距離來衡量。時間鄰近關系采用船舶位置數據實例的時間戳的差值來衡量。

在圖1 中，實線相連的實例間滿足空間鄰近關系。既滿足空間鄰近關系又滿足時間鄰近關系的時空共現實例有A1B1，C1D1，C3D3，C4D4，C5D5。

圖1 船舶時空共現模式示例圖

2）支持度

支持度是指數據集中對象鄰近實例的出現數量。當鄰近實例出現的數量多于設定的某個閾值時，判定為時空共現模式。

3）置信度

CPR為時空共現模式實例參與率，其計算公式為

其中Ck=｛f0，…，fk-1｝為k 元候選時空共現模式，fi∈E，E 為時空對象全集。計算圖1 數據集的時空共現模式實例參與率CPR，計算結果見表1。

表1 時空共現模式實例參與率

船舶對象之間的各種組合構成候選時空共現模式。若仍滿足置信度條件，則為時空共現模式。

其中θ 為置信度閾值。若設定θ=0.5，則表1中候選時空共現模式｛C，D｝為二元時空共現模式。

4 基于Hadoop架構的共現挖掘算法設計

基于Hadoop 的時空共現模式挖掘算法的核心問題為數據分區和挖掘算法并行化。

4.1 數據分區

船舶位置數據的空間分布特征存在明顯的不均勻性，因此均勻的數據分區方法會出現數據負載不均衡的現象，這會導致并行化計算速度下降，影響算法的整體執行效率。同時，數據分區必須考慮到空間局部性，即空間上相近的對象應當被分割在相同的分區內。

數據分區算法分為三個步驟:1）計算分區數量。分區數量根據輸入數據文件的大小，和系統開銷確定，主要用于保存重復的空間記錄和存儲本地索引。2）確定分割邊界，在分割階段，為了簡化計算將輸入文件進行隨機采樣。輸入文件的隨機采樣率默認為1%。當輸入文件較大時，構建MapReduce任務分布式瀏覽所有記錄并輸出1%的采樣文件。當得到的采樣文件尺寸大于給定閾值時，需要進行二次采樣。針對采樣文件，進行邊界劃分，保存每個數據塊的最小外接矩形，形成邊界劃分矩形集。3）實現物理分割。根據已知分割邊界實現數據物理分割操作，是原始數據與分割區域的匹配問題。由于原始數據間分割區域匹配是相互獨立的，所以可以進行并行化處理。首先將原始數據平均分成n 塊，針對每塊數據建立一個Map 過程，將執行結果送入Reduce 過程進行化簡，從而加快處理速度。

4.2 時空共現挖掘算法

時空共現模式挖掘算法實質上是經典Apriori算法面向船舶位置大數據的適應性改進［8～10］。算法步驟包括數據分區、并行挖掘分區數據［11］、剔除結果中的邊界共現實例、執行Apriori挖掘算法［12］。如圖2所示。

圖2 時空共現模式挖掘過程

圖中分割邊界確定算法的并行化計算只涉及到各垂直切塊的并行排序和水平切割。對于最終切割結果需要獲得每個分塊的矩形區域范圍，并將其結果作為最終結果輸出。

分割函數Splitter 的輸入為形式為

Splitter函數偽代碼輸入:

時空共現模式挖掘算法涉及Map 函數和Reduce 函數的設計，用于挖掘時空共現模式的Map_Reduce計算。

Map 函數的功能在于計算時空共現實例對。函數的數據輸入形式為

Map函數偽代碼輸入:

Reduce 函數的功能在于合并相同的時空共現實例對。函數的輸入形式為

Reduce函數偽代碼輸入:

5 算例與結果分析

5.1 實驗環境與數據準備

使用4臺計算機搭建Hadoop平臺，每臺計算機作為一個計算節點，其中一臺機器作為Master 和JobTracker 控制節點，其余三臺機器作為Slave 和TaskTracker 計算節點。計算機操作系統采用Ubuntu Linux 14.04，Hadoop 版 本 為Hadoop1.2.1。計算機基本配置為InterQ8300，內存4G，硬盤500G。

實驗數據選自真實的AIS 歷史數據。選取2012 年1 月 和7 月 的 全 球AIS 數 據，數 據 量 約400GB，選取的海區為我國瓊洲海峽附近。實驗之前，對數據采取預處理操作，剔除了錯誤數據和格式有誤數據。

5.2 實驗結果

1）2012年1月份數據集

實驗參數設置:輸入數據量=224GB，分塊大小=1MB，鄰近距離=500m，支持度=10000，置信度=0.1。實驗結果見表2。

表2 時空共現模式挖掘結果

2）2012年7月份數據集

實驗參數設置:輸入數據量=186GB，分塊大小=1MB，鄰近距離=500m，支持度=10000，置信度=0.2。實驗結果見表3。

表3 時空共現模式挖掘結果

5.3 算法分析

共現模式挖掘算法有4 個可控參數，其分別為分塊大小、鄰近距離閾值、支持度和置信度。在設定其余變量的前提下，本文分析討論了各個參數對算法執行效率的影響。所用數據為2012 年1 月份數據，約224GB。

圖3 分塊大小影響分析

圖4 距離閾值影響分析

圖5 支持度影響分析

圖6 置信度影響分析

如圖3～6 所示，結果表明:隨著分塊大小的增加，算法執行時間呈先減后增的變化趨勢，在分塊大小為1MB 時取得最小值。鄰近距離參數是時空共現模式非常重要的參數，直接影響實驗結果的可靠性。鄰近距離選擇過大，會出現時空共現關系弱化的現象，鄰近距離選擇過小，會導致部分時空共現模式被忽略的情況。支持度大小的選擇關系到時空共現模式挖掘的核心問題。支持度增大一個數量級，鄰近實例對數量減小4 個數量級，也反映出支持度參數設定的重要性。而置信度的大小反映出時空共現關系的可靠性，有強時空共現關系的時空共現模式才具有實際意義。隨置信度參數增加，共現實例對數量迅速減少。

6 結語

船舶AIS 數據中時空共現模式挖掘通過計算AIS 海量數據中對象間的時空鄰近關系，發現鄰近關系背后的模式與規律，對于海洋交通以及安全監管等軍事、民用領域具有十分重要的實用價值。本文提出了一種基于Hadoop 的船舶時空共現模式挖掘算法，通過采用并行化分區算法劃分原始數據集，在擴展的MapReduce架構上實現了船舶軌跡數據中的時空共現模式挖掘，并基于AIS 實際數據集進行了實驗和分析。

由于硬件條件限制，本文中只選取的實驗數據規模仍然較小，采用更大規模的全域數據進行實驗，并結合其他數據來源，對船只異常行為進行綜合判斷也是一個重要的研究方向。