船舶AIS 數(shù)據(jù)時(shí)空共現(xiàn)模式挖掘?

包 磊 彭慶喜

（武漢東湖學(xué)院計(jì)算機(jī)科學(xué)學(xué)院 武漢 430079）

1 引言

隨著地理信息的不斷泛化，船舶軌跡數(shù)據(jù)的獲取與計(jì)算能力不斷發(fā)展。其中船舶自動(dòng)識(shí)別系統(tǒng)（Auto Identification System，AIS）網(wǎng)絡(luò)所收集的大量船舶航跡信息眾源數(shù)據(jù)，是船舶軌跡數(shù)據(jù)的重要組成部分。同時(shí)，雷達(dá)、觀通以及衛(wèi)星系統(tǒng)主動(dòng)獲取的大量情報(bào)態(tài)勢(shì)數(shù)據(jù)和Argo、海王星等諸多海洋觀測(cè)計(jì)劃所采集的海量海洋環(huán)境數(shù)據(jù)，構(gòu)成一個(gè)數(shù)據(jù)量龐大、內(nèi)容豐富，且數(shù)據(jù)量急劇增長(zhǎng)的數(shù)據(jù)集。運(yùn)動(dòng)模式挖掘是目前領(lǐng)域中一個(gè)發(fā)展迅速的前沿研究課題，通過軌跡模式挖掘算法可以發(fā)現(xiàn)軌跡大數(shù)據(jù)中有價(jià)值的模式從而分析船舶的運(yùn)動(dòng)趨勢(shì)和運(yùn)動(dòng)規(guī)律，以感知態(tài)勢(shì)、獲取更經(jīng)濟(jì)安全的導(dǎo)航信息。

2 相關(guān)研究現(xiàn)狀

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

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

然而，海量的海上位置數(shù)據(jù)為時(shí)空共現(xiàn)模式的挖掘提出了新的要求，而目前海上位置數(shù)據(jù)信息量早已達(dá)到了TB 級(jí)別，且呈持續(xù)增長(zhǎng)的趨勢(shì)。僅僅以AIS 數(shù)據(jù)為例，全球每天通過衛(wèi)星和基站收集的AIS 數(shù)據(jù)約為4G，一年產(chǎn)生的AIS 數(shù)據(jù)量可達(dá)1.4TB?，F(xiàn)有的研究成果多基于少量數(shù)據(jù)樣本，無(wú)法應(yīng)對(duì)巨大的數(shù)據(jù)量。且傳統(tǒng)挖掘算法的串行計(jì)算方式和空間特征不敏感的特點(diǎn)限制了共現(xiàn)模式挖掘的速度。針對(duì)這些問題，本文基于空間Hadoop分析平臺(tái)架構(gòu)，提出了海上位置大數(shù)據(jù)下的時(shí)空共現(xiàn)模式挖掘算法，通過采用兩級(jí)空間索引劃分原始數(shù)據(jù)集，在給出的擴(kuò)展MapReduce架構(gòu)上實(shí)現(xiàn)了船舶軌跡數(shù)據(jù)中的時(shí)空共現(xiàn)模式挖掘?；贏IS 實(shí)際數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果顯示，能夠有效處理大規(guī)模船舶軌跡數(shù)據(jù)，并保持良好的效率和正確性。

3 船舶時(shí)空共現(xiàn)模型

船舶時(shí)空共現(xiàn)模式指船舶在位置和時(shí)間標(biāo)識(shí)上滿足某種鄰近關(guān)系。這種鄰近關(guān)系的判定通過實(shí)例時(shí)空鄰近參與度來(lái)描述。

1）鄰近關(guān)系

鄰近關(guān)系包括空間鄰近關(guān)系和時(shí)間鄰近關(guān)系?？臻g鄰近關(guān)系采用歐式距離來(lái)衡量。時(shí)間鄰近關(guān)系采用船舶位置數(shù)據(jù)實(shí)例的時(shí)間戳的差值來(lái)衡量。

在圖1 中，實(shí)線相連的實(shí)例間滿足空間鄰近關(guān)系。既滿足空間鄰近關(guān)系又滿足時(shí)間鄰近關(guān)系的時(shí)空共現(xiàn)實(shí)例有A1B1，C1D1，C3D3，C4D4，C5D5。

圖1 船舶時(shí)空共現(xiàn)模式示例圖

2）支持度

支持度是指數(shù)據(jù)集中對(duì)象鄰近實(shí)例的出現(xiàn)數(shù)量。當(dāng)鄰近實(shí)例出現(xiàn)的數(shù)量多于設(shè)定的某個(gè)閾值時(shí)，判定為時(shí)空共現(xiàn)模式。

3）置信度

CPR為時(shí)空共現(xiàn)模式實(shí)例參與率，其計(jì)算公式為

其中Ck=｛f0，…，fk-1｝為k 元候選時(shí)空共現(xiàn)模式，fi∈E，E 為時(shí)空對(duì)象全集。計(jì)算圖1 數(shù)據(jù)集的時(shí)空共現(xiàn)模式實(shí)例參與率CPR，計(jì)算結(jié)果見表1。

表1 時(shí)空共現(xiàn)模式實(shí)例參與率

船舶對(duì)象之間的各種組合構(gòu)成候選時(shí)空共現(xiàn)模式。若仍滿足置信度條件，則為時(shí)空共現(xiàn)模式。

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

4 基于Hadoop架構(gòu)的共現(xiàn)挖掘算法設(shè)計(jì)

基于Hadoop 的時(shí)空共現(xiàn)模式挖掘算法的核心問題為數(shù)據(jù)分區(qū)和挖掘算法并行化。

4.1 數(shù)據(jù)分區(qū)

船舶位置數(shù)據(jù)的空間分布特征存在明顯的不均勻性，因此均勻的數(shù)據(jù)分區(qū)方法會(huì)出現(xiàn)數(shù)據(jù)負(fù)載不均衡的現(xiàn)象，這會(huì)導(dǎo)致并行化計(jì)算速度下降，影響算法的整體執(zhí)行效率。同時(shí)，數(shù)據(jù)分區(qū)必須考慮到空間局部性，即空間上相近的對(duì)象應(yīng)當(dāng)被分割在相同的分區(qū)內(nèi)。

數(shù)據(jù)分區(qū)算法分為三個(gè)步驟:1）計(jì)算分區(qū)數(shù)量。分區(qū)數(shù)量根據(jù)輸入數(shù)據(jù)文件的大小，和系統(tǒng)開銷確定，主要用于保存重復(fù)的空間記錄和存儲(chǔ)本地索引。2）確定分割邊界，在分割階段，為了簡(jiǎn)化計(jì)算將輸入文件進(jìn)行隨機(jī)采樣。輸入文件的隨機(jī)采樣率默認(rèn)為1%。當(dāng)輸入文件較大時(shí)，構(gòu)建MapReduce任務(wù)分布式瀏覽所有記錄并輸出1%的采樣文件。當(dāng)?shù)玫降牟蓸游募叽绱笥诮o定閾值時(shí)，需要進(jìn)行二次采樣。針對(duì)采樣文件，進(jìn)行邊界劃分，保存每個(gè)數(shù)據(jù)塊的最小外接矩形，形成邊界劃分矩形集。3）實(shí)現(xiàn)物理分割。根據(jù)已知分割邊界實(shí)現(xiàn)數(shù)據(jù)物理分割操作，是原始數(shù)據(jù)與分割區(qū)域的匹配問題。由于原始數(shù)據(jù)間分割區(qū)域匹配是相互獨(dú)立的，所以可以進(jìn)行并行化處理。首先將原始數(shù)據(jù)平均分成n 塊，針對(duì)每塊數(shù)據(jù)建立一個(gè)Map 過程，將執(zhí)行結(jié)果送入Reduce 過程進(jìn)行化簡(jiǎn)，從而加快處理速度。

4.2 時(shí)空共現(xiàn)挖掘算法

時(shí)空共現(xiàn)模式挖掘算法實(shí)質(zhì)上是經(jīng)典Apriori算法面向船舶位置大數(shù)據(jù)的適應(yīng)性改進(jìn)［8～10］。算法步驟包括數(shù)據(jù)分區(qū)、并行挖掘分區(qū)數(shù)據(jù)［11］、剔除結(jié)果中的邊界共現(xiàn)實(shí)例、執(zhí)行Apriori挖掘算法［12］。如圖2所示。

圖2 時(shí)空共現(xiàn)模式挖掘過程

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

分割函數(shù)Splitter 的輸入為形式為

Splitter函數(shù)偽代碼輸入:

時(shí)空共現(xiàn)模式挖掘算法涉及Map 函數(shù)和Reduce 函數(shù)的設(shè)計(jì)，用于挖掘時(shí)空共現(xiàn)模式的Map_Reduce計(jì)算。

Map 函數(shù)的功能在于計(jì)算時(shí)空共現(xiàn)實(shí)例對(duì)。函數(shù)的數(shù)據(jù)輸入形式為

Map函數(shù)偽代碼輸入:

Reduce 函數(shù)的功能在于合并相同的時(shí)空共現(xiàn)實(shí)例對(duì)。函數(shù)的輸入形式為

Reduce函數(shù)偽代碼輸入:

5 算例與結(jié)果分析

5.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)準(zhǔn)備

使用4臺(tái)計(jì)算機(jī)搭建Hadoop平臺(tái)，每臺(tái)計(jì)算機(jī)作為一個(gè)計(jì)算節(jié)點(diǎn)，其中一臺(tái)機(jī)器作為Master 和JobTracker 控制節(jié)點(diǎn)，其余三臺(tái)機(jī)器作為Slave 和TaskTracker 計(jì)算節(jié)點(diǎn)。計(jì)算機(jī)操作系統(tǒng)采用Ubuntu Linux 14.04，Hadoop 版 本 為Hadoop1.2.1。計(jì)算機(jī)基本配置為InterQ8300，內(nèi)存4G，硬盤500G。

實(shí)驗(yàn)數(shù)據(jù)選自真實(shí)的AIS 歷史數(shù)據(jù)。選取2012 年1 月 和7 月 的 全 球AIS 數(shù) 據(jù)，數(shù) 據(jù) 量 約400GB，選取的海區(qū)為我國(guó)瓊洲海峽附近。實(shí)驗(yàn)之前，對(duì)數(shù)據(jù)采取預(yù)處理操作，剔除了錯(cuò)誤數(shù)據(jù)和格式有誤數(shù)據(jù)。

5.2 實(shí)驗(yàn)結(jié)果

1）2012年1月份數(shù)據(jù)集

實(shí)驗(yàn)參數(shù)設(shè)置:輸入數(shù)據(jù)量=224GB，分塊大小=1MB，鄰近距離=500m，支持度=10000，置信度=0.1。實(shí)驗(yàn)結(jié)果見表2。

表2 時(shí)空共現(xiàn)模式挖掘結(jié)果

2）2012年7月份數(shù)據(jù)集

實(shí)驗(yàn)參數(shù)設(shè)置:輸入數(shù)據(jù)量=186GB，分塊大小=1MB，鄰近距離=500m，支持度=10000，置信度=0.2。實(shí)驗(yàn)結(jié)果見表3。

表3 時(shí)空共現(xiàn)模式挖掘結(jié)果

5.3 算法分析

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

圖3 分塊大小影響分析

圖4 距離閾值影響分析

圖5 支持度影響分析

圖6 置信度影響分析

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

6 結(jié)語(yǔ)

船舶AIS 數(shù)據(jù)中時(shí)空共現(xiàn)模式挖掘通過計(jì)算AIS 海量數(shù)據(jù)中對(duì)象間的時(shí)空鄰近關(guān)系，發(fā)現(xiàn)鄰近關(guān)系背后的模式與規(guī)律，對(duì)于海洋交通以及安全監(jiān)管等軍事、民用領(lǐng)域具有十分重要的實(shí)用價(jià)值。本文提出了一種基于Hadoop 的船舶時(shí)空共現(xiàn)模式挖掘算法，通過采用并行化分區(qū)算法劃分原始數(shù)據(jù)集，在擴(kuò)展的MapReduce架構(gòu)上實(shí)現(xiàn)了船舶軌跡數(shù)據(jù)中的時(shí)空共現(xiàn)模式挖掘，并基于AIS 實(shí)際數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)和分析。

由于硬件條件限制，本文中只選取的實(shí)驗(yàn)數(shù)據(jù)規(guī)模仍然較小，采用更大規(guī)模的全域數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，并結(jié)合其他數(shù)據(jù)來(lái)源，對(duì)船只異常行為進(jìn)行綜合判斷也是一個(gè)重要的研究方向。