基于網(wǎng)格化壓縮挖掘船舶航道位置信息

， ，

(南京船舶雷達(dá)研究所，南京 211106)

0 引言

由于海上目標(biāo)的異常多表現(xiàn)為航跡位置的異常，所以為了能夠檢測出這種位置異常，需要對正常船舶航道的位置信息進(jìn)行提取。而船舶自動識別系統(tǒng)(Automatic Identification System，AIS)[1]的廣泛應(yīng)用生成了海量的航跡數(shù)據(jù)，這為基于AIS數(shù)據(jù)挖掘正常船舶航道位置信息提供了條件。

就現(xiàn)階段而言，國內(nèi)外對航路模型的構(gòu)建過程多基于單一目標(biāo)的小樣本進(jìn)行。比如國內(nèi)的寧建強(qiáng)等[2]提出一種細(xì)粒度網(wǎng)格的方法，通過對航跡從不同粒度上進(jìn)行處理從而提取航路模型；國外的Pallotta等[3]通過采用改良后的的DBSCAN (density-based spatial clustering of applications with noise)聚類算法構(gòu)建相應(yīng)的船舶航路模型；而Guillarme等[4]則采用軌跡分割的方法完成航路聚類構(gòu)建；至于Osekowska等[5-7]則通過將勢場的概念應(yīng)用于船舶航路的構(gòu)建和提取中。

這些航路模型構(gòu)建的方法在海量數(shù)據(jù)背景下，都會存在樣本描述整體出現(xiàn)偏差的問題，更有甚者發(fā)生錯誤與遺漏[8]。所以為了從海量AIS數(shù)據(jù)中提取出船舶的主航道位置信息，為海上目標(biāo)的異常檢測提供位置上的先驗(yàn)知識，本文提出了一種基于網(wǎng)格化壓縮提取船舶航道位置信息的算法。首先為了提高海量數(shù)據(jù)的挖掘效率問題，該算法根據(jù)AIS航跡特點(diǎn)提出采用網(wǎng)格化壓縮的方法將航跡數(shù)據(jù)進(jìn)行壓縮，從而在保證不丟失航跡位置信息的基礎(chǔ)上降低數(shù)據(jù)量，從而提高了處理效率；之后由于壓縮后的航跡數(shù)據(jù)缺少航向信息，所以該算法采用了九宮格矢量化的方法重新構(gòu)建方向?qū)傩裕戎貥?gòu)了方向?qū)傩?，又消除了原始AIS數(shù)據(jù)中的船首向抖動的問題；最后在重構(gòu)的八個方向上分別采用變閾值設(shè)置方法實(shí)現(xiàn)最終的密度聚類，挖掘出不同方向上航道的位置信息。

1 航道位置信息挖掘算法模型

本文基于網(wǎng)格化壓縮挖掘船舶航道位置信息算法的總體模型架構(gòu)如圖1中的船舶航道位置挖掘算法流程圖所示：

圖1 船舶航道位置挖掘算法流程

根據(jù)流程圖可以看出，本文主要從四部分進(jìn)行處理和研究的：1)數(shù)據(jù)預(yù)處理；2)網(wǎng)格化處理；3)九宮格矢量化；4)航道位置信息模型的挖掘與展示。

其中數(shù)據(jù)預(yù)處理過程主要是從數(shù)據(jù)去噪和航跡切割角度進(jìn)行。具體過程如下所述。

因?yàn)榻?jīng)由數(shù)據(jù)庫中提取出的AIS原始數(shù)據(jù)存在大量噪聲數(shù)據(jù)，例如MMSI噪聲，航跡位置噪聲及航向信息噪聲等。為了能夠剔除噪聲數(shù)據(jù)，本文通過從MMSI(Maritime Mobile Service Identity)號，航以及航跡經(jīng)度、緯度等角度對其進(jìn)行篩選去噪，即數(shù)據(jù)去噪。

因?yàn)橥粋€MMSI號對應(yīng)的航跡實(shí)際上存在有多個空窗期(見定義1)，所以為了能夠滿足后續(xù)在網(wǎng)格化壓縮過程中對船舶航跡數(shù)據(jù)連續(xù)性的要求，需要將同一個MMSI號對應(yīng)的AIS數(shù)據(jù)依照空窗期進(jìn)行分割，將其切割成若干連續(xù)的航跡，即航跡切割。

定義1：空窗期。

由于主觀或客觀環(huán)境的干擾導(dǎo)致目標(biāo)離開監(jiān)控窗口，監(jiān)測儀器在一段相當(dāng)長的時間內(nèi)丟失對這個目標(biāo)的跟蹤，而且在再次跟蹤到該目標(biāo)時，無法忽略中間缺失過程產(chǎn)生的誤差，這段缺失過程就是該目標(biāo)的一個空窗期。

2 網(wǎng)格化壓縮方法

實(shí)際中，因?yàn)榇暗暮剿佥^低，一般大約在30幾節(jié)以下，對于超過30節(jié)的船舶很少，而相較之下AIS信號產(chǎn)生的頻率卻很高，一般在十幾秒到幾十秒之間，最快的2到3秒就發(fā)射一次，這就導(dǎo)致在相當(dāng)長的一段時間之中，AIS系統(tǒng)生成了大量的航跡點(diǎn)，而實(shí)際上船舶的位置和航向等航行狀態(tài)卻并未發(fā)生太大的實(shí)質(zhì)性的變化，所以這就使得船舶的航跡數(shù)據(jù)里包含了大量的冗余狀態(tài)信息。為了去除這些冗余的數(shù)據(jù)，本節(jié)提出了一種網(wǎng)格化壓縮的方法，通過對每條連續(xù)的航跡數(shù)據(jù)進(jìn)行壓縮處理，從而實(shí)現(xiàn)了冗余數(shù)據(jù)的去除，同時也有效提高了后續(xù)處理過程的計(jì)算效率。

網(wǎng)格化壓縮方法主要是通過以下四個步驟進(jìn)行處理的：

第一步：首先對待研究的區(qū)域W按照經(jīng)緯度的值劃分成大小為step的網(wǎng)格，如圖2的網(wǎng)格化過程圖所示(圖中A'是A的放大)，這里的step就是網(wǎng)格的最小粒度大小，該值的大小選擇決定著網(wǎng)格化壓縮的效果；

第二步：然后將落在網(wǎng)格中的所有航跡點(diǎn)的經(jīng)緯度坐標(biāo)都改成網(wǎng)格的中心點(diǎn)的經(jīng)緯度坐標(biāo)，而對于落在網(wǎng)格邊界線上的點(diǎn)統(tǒng)一移到左側(cè)或上側(cè)的格子中，即將圖2中所有落到A'格子中的點(diǎn)都壓縮到點(diǎn)1位置。

第三步：之后將每一條連續(xù)的航跡按照時間屬性(UDT_TM)進(jìn)行排序，并對經(jīng)緯度采用一階差分的算法進(jìn)行計(jì)算；

第四步：最后將經(jīng)緯度差分為零的點(diǎn)去掉。至此實(shí)現(xiàn)了網(wǎng)格化壓縮。

3 九宮格矢量化及航道位置挖掘

而壓縮后的航跡數(shù)據(jù)失去了航向信息，所以本節(jié)提出了一種九宮格矢量化的方法為壓縮后的航跡重構(gòu)方向?qū)傩浴６鵀榱四懿⑿谢耐诰虺霾煌较蛏洗昂降赖奈恢眯畔⒛Ｐ?，需要從不同航向上分別進(jìn)行航道位置挖掘，但由于矢量化后的不同航向上的航跡數(shù)據(jù)的分布存在差異，所以本節(jié)采用變閾值的方法分別設(shè)置密度閾值從而實(shí)現(xiàn)在不同航向上航道位置的提取。

3.1 九宮格矢量化

經(jīng)過上一節(jié)中的網(wǎng)格化壓縮之后，船舶的航跡數(shù)據(jù)只剩下位置信息，而缺失航向信息，所以為了能夠使網(wǎng)格化之后的航跡數(shù)據(jù)準(zhǔn)確反映航向信息，同時去除原始航跡中航向抖動的問題，本節(jié)提出了一種九宮格矢量化的方法重構(gòu)航跡的航向?qū)傩浴?/p>

定義2：矢量化規(guī)則。

假設(shè)航跡的初始航跡點(diǎn)的經(jīng)緯度坐標(biāo)為P0 (LON0，LAT0)，其下一航跡點(diǎn)的經(jīng)緯度坐標(biāo)為P1 (LON1，LAT1)，則根據(jù)代數(shù)矢量的定義法則可以得出P0點(diǎn)的矢量為(LON1-LON0，LAT1-LAT0)。

假設(shè)1：九宮格編碼假設(shè)。

如圖3所示，首先對九宮格進(jìn)行編碼形成編碼格，然后假設(shè)9號格為初始航跡點(diǎn)的位置P0，則下一航跡點(diǎn)的位置P1定會落到剩余的八個格中的任意一個格中，則此時P0的方向編碼即為P1點(diǎn)落到的格子對應(yīng)的編碼號。

圖3 九宮格編碼圖 圖4 假設(shè)軌跡圖

如圖4是一個假設(shè)的航跡，根據(jù)矢量化規(guī)則與九宮格編碼假設(shè)可以得出軌跡點(diǎn)a的軌跡方向編碼為7，軌跡點(diǎn)b的軌跡方向編碼為5，軌跡點(diǎn)c的軌跡方向編碼為2。這樣這條軌跡方向的整體編碼形式就是7-5-2。如此這般即可將所有的壓縮后的航跡點(diǎn)重構(gòu)出其航向?qū)傩浴?/p>

但是該矢量化方法需要滿足假設(shè)1的條件，否則編碼不成立。所以為了確定壓縮后的航跡數(shù)據(jù)是否滿足假設(shè)1，需要對網(wǎng)格化壓縮后的航跡數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析，具體過程可見第四章節(jié)實(shí)驗(yàn)中的概率密度統(tǒng)計(jì)分析。

3.2 變閾值設(shè)置挖掘航道

本文實(shí)現(xiàn)航道位置信息挖掘的過程基于的是網(wǎng)格密度聚類思想，網(wǎng)格密度聚類需要設(shè)置密度閾值TD。而為了從不同航向角度分別實(shí)現(xiàn)航路位置模型的提取，同時考慮到九宮格矢量化的8個方向的航跡數(shù)存在差異的問題，如果設(shè)置固定的密度閾值TD，會導(dǎo)致一些方向的航跡數(shù)據(jù)被其他方向的航跡數(shù)據(jù)沖淡，而誤判為噪聲網(wǎng)格，為此本節(jié)提出采用一種變閾值設(shè)置的方法(見定義3)對不同航向的航跡數(shù)據(jù)分別設(shè)置密度閾值TD。

定義3：軌跡格點(diǎn)閾值。

設(shè)網(wǎng)格密度值為D(D1，D2，…，Dn)，則如公式1所示，其中μ為網(wǎng)格密度值的均值，σ為網(wǎng)格密度值的標(biāo)準(zhǔn)差，TD為密度閾值，m為一個系數(shù)(m>0)。

μ=(D1+D2+...+Dn)/n

TD=μ+m·σ

(1)

之后通過閾值判決，將超過閾值TD的網(wǎng)格判為正常航道網(wǎng)格，將低于閾值TD的網(wǎng)格設(shè)置為噪聲網(wǎng)格，并將其直接去除，最后通過可視化的方法對航道網(wǎng)格進(jìn)行展示和選擇。

4 實(shí)驗(yàn)過程及結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)

本實(shí)驗(yàn)的硬件平臺為Window7 x64位系統(tǒng)，內(nèi)存為24.0 GB，處理器為Intel(R) Core(TM) i7-4770K CPU @ 3.50 GH，軟件平臺為R-3.4.3版本。本實(shí)驗(yàn)使用的是XX雷達(dá)基站采集的廈門港口海域的近一個月的AIS數(shù)據(jù)，其數(shù)據(jù)總量達(dá)到28.8 GB。

4.2 實(shí)驗(yàn)結(jié)果分析

4.2.1 網(wǎng)格化壓縮效果分析

根據(jù)文獻(xiàn)[2]介紹，圖2中的Step大小是網(wǎng)格劃分的關(guān)鍵。Step太大，容易丟失船舶軌跡中的一些轉(zhuǎn)向信息；Step太小，壓縮不充分。所以根據(jù)兩個先驗(yàn)知識：1)在船舶的正常航行中，正常轉(zhuǎn)彎過程都是在4到5倍的船長為半徑的區(qū)域內(nèi)進(jìn)行；2)地球的經(jīng)緯度每0.01度對應(yīng)實(shí)際的地理距離約是1.1公里左右(見公式2)。而由于正常船舶最長400多米，所以本文采用0.02°×0.02°網(wǎng)格進(jìn)行劃分，這樣既可以充分壓縮，又不會丟失轉(zhuǎn)向信息。

L1°=2πR/360°≈111.139km

L0.01°=L1°/100≈1.1km

(2)

實(shí)驗(yàn)中，由于數(shù)據(jù)量太大，R語言對于硬件平臺的內(nèi)存要求較高，在對原始數(shù)據(jù)進(jìn)行處理時，無法一次性將所有數(shù)據(jù)進(jìn)行展開，所以本文通過將一個月的數(shù)據(jù)依據(jù)時間屬性分割成為三個數(shù)據(jù)集分別進(jìn)行網(wǎng)格化壓縮處理。

表1 數(shù)據(jù)壓縮效果表

如表1所示是原始數(shù)據(jù)集分割成的三個數(shù)據(jù)集的三次數(shù)據(jù)壓縮的效果，由此可見網(wǎng)格化壓縮的倍數(shù)都在200倍左右，所以可見網(wǎng)格化壓縮方法的壓縮效果顯著，可以在很大程度上去除冗余航跡信息，提高后續(xù)航跡位置信息提取過程中的計(jì)算效率。

為了確定壓縮后的數(shù)據(jù)分布情況，從而確定壓縮后的航跡數(shù)據(jù)是否滿足九宮格矢量化假設(shè)要求，本實(shí)驗(yàn)對差分后數(shù)據(jù)的經(jīng)度差分值屬性(DLON)和緯度差分值屬性(DLAT)進(jìn)行了概率密度值統(tǒng)計(jì)。如圖5所示，分別對應(yīng)的是差分后的經(jīng)度差分值屬性(DLON)和緯度差分值屬性(DLAT)，其二者的分布主要集中在0.02°，0°和-0.02°，其中中心最高峰值對應(yīng)的是0，左側(cè)次高峰對應(yīng)的是-0.02，右側(cè)次高峰對應(yīng)的是0.02。這就表明差分后的航跡數(shù)據(jù)依然是連續(xù)的，壓縮并沒有失真。由此也可以證明，壓縮后的航跡數(shù)據(jù)是滿足九宮格編碼假設(shè)的，因此壓縮后的航跡數(shù)據(jù)是可以通過九宮格矢量化規(guī)則進(jìn)行航向?qū)傩缘闹貥?gòu)。

圖5 差分后概率密度統(tǒng)計(jì)

4.2.2 聚類效果展示

本實(shí)驗(yàn)采用并行化的思想，從重構(gòu)的八個航向向上分別進(jìn)行提取船舶航路位置模型，其網(wǎng)格密度閾值的選取是根據(jù)公式1進(jìn)行的。實(shí)驗(yàn)中分別選取取m值為0，1，1.5和2進(jìn)行了研究。實(shí)驗(yàn)結(jié)果顯示，不同航向上航路的密度閾值中的m值的選擇影響航路位置模型提取的效果。其中網(wǎng)格密度值較大的航向上，m值選擇較大時效果顯著，而網(wǎng)格密度值較小是，m值的選擇較小時效果較好。

這是由于當(dāng)網(wǎng)格密度較大時，該航向上航行船舶較多，出現(xiàn)異常的船舶也較多，只有提高m值，才能有效去除航路中的異常航跡；而當(dāng)網(wǎng)格密度較小時，表示該航向上航行的船舶較少，尤其是受地理地形影響較大的航向區(qū)域，其基本上很少有異常航跡，所以只需要取較小的m值就可以完全實(shí)現(xiàn)航路位置模型的提取，反而較大的m值易于造成正常航路被誤判而去除。

如圖6所示是部分方向在適當(dāng)?shù)膍下的航道位置聚類效果圖，其中圖6.1是m=1.5時，3號航向上的航道位置模型提取的效果圖；圖6.2是m=1時，5號航向上的航道位置模型提取的效果圖。由于采用了網(wǎng)格化壓縮，所以航道點(diǎn)跡成為離散狀態(tài)，即圖中顯示的航路是有一個一個的航跡點(diǎn)組合而成的航跡區(qū)域。這也同時指出，在后續(xù)的海上目標(biāo)的異常檢測過程中，也需要對船舶目標(biāo)的航跡進(jìn)行網(wǎng)格化壓縮，使其成為離散轉(zhuǎn)態(tài)后再進(jìn)行對比判決檢測。

圖6 提取的航道位置信息效果

5 結(jié)束語

為了從海量AIS數(shù)據(jù)中挖掘出船舶航道的位置信息模型，本文根據(jù)船舶航跡存在冗余的特點(diǎn)，提出一種基于網(wǎng)格化壓縮挖掘船舶航道位置信息的算法。其中針對計(jì)算效率低的問題，該算法提出采用網(wǎng)格化壓縮方法有效去除了航跡數(shù)據(jù)中的冗余數(shù)據(jù)，提高了海量數(shù)據(jù)聚類的計(jì)算效率。同時該壓縮方法也為海量路徑數(shù)據(jù)的壓縮提供了一種算法支持。為了解決壓縮后的航跡數(shù)據(jù)缺少航向信息的問題，本文采用的九宮格矢量化方法在網(wǎng)格化的基礎(chǔ)上重構(gòu)了船舶航向?qū)傩?，為壓縮后的航跡增加方向?qū)傩裕瑫r也有效去除了原始航跡中航向抖動的問題。最后為了避免不同方向上數(shù)據(jù)相互干擾，易將核心網(wǎng)格誤判成噪聲網(wǎng)格的問題，本文在矢量化的八個方向上，分別采用不同的閾值實(shí)現(xiàn)航道位置信息模型的提取。

本實(shí)驗(yàn)中可視化的結(jié)果表明在選擇合適的閾值下，該算法可以有效提取船舶的主航道位置信息。但是該算法提取的船舶航道只有一個位置信息，缺少航跡中的時序信息，需要后續(xù)從時序角度進(jìn)一步挖掘提取。