, ,
(南京船舶雷達研究所,南京 211106)
由于海上目標的異常多表現(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)最終的密度聚類,挖掘出不同方向上航道的位置信息。
本文基于網(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)測儀器在一段相當長的時間內丟失對這個目標的跟蹤,而且在再次跟蹤到該目標時,無法忽略中間缺失過程產生的誤差,這段缺失過程就是該目標的一個空窗期。
實際中,因為船舶的航速較低,一般大約在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)格化壓縮。
而壓縮后的航跡數(shù)據(jù)失去了航向信息,所以本節(jié)提出了一種九宮格矢量化的方法為壓縮后的航跡重構方向屬性。而為了能并行化的挖掘出不同航向上船舶航道的位置信息模型,需要從不同航向上分別進行航道位置挖掘,但由于矢量化后的不同航向上的航跡數(shù)據(jù)的分布存在差異,所以本節(jié)采用變閾值的方法分別設置密度閾值從而實現(xiàn)在不同航向上航道位置的提取。
經過上一節(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)計分析。
本文實現(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)格進行展示和選擇。
本實驗的硬件平臺為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.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 提取的航道位置信息效果
為了從海量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ù)從時序角度進一步挖掘提取。