， ，

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

0 引言

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

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

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

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

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

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

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

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

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

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

定義1：空窗期。

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

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

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

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

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

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

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

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

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

而壓縮后的航跡數(shù)據(jù)失去了航向信息，所以本節(jié)提出了一種九宮格矢量化的方法為壓縮后的航跡重構方向屬性。而為了能并行化的挖掘出不同航向上船舶航道的位置信息模型，需要從不同航向上分別進行航道位置挖掘，但由于矢量化后的不同航向上的航跡數(shù)據(jù)的分布存在差異，所以本節(jié)采用變閾值的方法分別設置密度閾值從而實現(xiàn)在不同航向上航道位置的提取。

3.1 九宮格矢量化

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

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

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

假設1：九宮格編碼假設。

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

圖3 九宮格編碼圖 圖4 假設軌跡圖

如圖4是一個假設的航跡，根據(jù)矢量化規(guī)則與九宮格編碼假設可以得出軌跡點a的軌跡方向編碼為7，軌跡點b的軌跡方向編碼為5，軌跡點c的軌跡方向編碼為2。這樣這條軌跡方向的整體編碼形式就是7-5-2。如此這般即可將所有的壓縮后的航跡點重構出其航向屬性。

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

3.2 變閾值設置挖掘航道

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

定義3：軌跡格點閾值。

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

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

TD=μ+m·σ

(1)

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

4 實驗過程及結果分析

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

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

4.2 實驗結果分析

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

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

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

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

(2)

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

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

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

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

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

4.2.2 聚類效果展示

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

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

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

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

5 結束語

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

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