基于時(shí)空密度的船載AIS數(shù)據(jù)聚類分析方法研究

李永攀，劉正江，鄭中義

(1. 大連海事大學(xué) 航海學(xué)院，遼寧 大連 116026；2. 舟山海事局 船舶交通管理中心，浙江 舟山 316000)

0 引 言

船舶自動(dòng)識(shí)別系統(tǒng)(automatic identification system，AIS)是一種船載設(shè)備，向岸基及周邊船舶發(fā)送自身的靜態(tài)、動(dòng)態(tài)和航次數(shù)據(jù)。AIS的強(qiáng)制配備和廣泛應(yīng)用，不僅提高了船舶航行安全和效率，且為開(kāi)展相關(guān)數(shù)據(jù)挖掘、尋找海上交通規(guī)律、協(xié)助海上交通規(guī)劃與管理提供了寶貴素材。

近年來(lái)船載AIS數(shù)據(jù)挖掘方法和應(yīng)用迅速發(fā)展。學(xué)者們主要基于AIS數(shù)據(jù)點(diǎn)[1]或軌跡線[2]的經(jīng)緯度、航向和航速等屬性，利用一定數(shù)學(xué)模型和信息技術(shù)開(kāi)展相關(guān)數(shù)據(jù)挖掘。通過(guò)挖掘AIS數(shù)據(jù)可識(shí)別海上錨泊區(qū)、作業(yè)區(qū)和擁擠區(qū)等特殊區(qū)域[1]、識(shí)別主要船舶航路[3]、分析船舶領(lǐng)域和運(yùn)動(dòng)模式[4]、研究船舶密度和速度分布[5]、評(píng)估船舶會(huì)遇或碰撞風(fēng)險(xiǎn)[6]、推算到港概率或航跡趨勢(shì)[7]、開(kāi)展異常檢測(cè)、設(shè)計(jì)或?qū)彶槎ň€制、評(píng)估碳排放等。

在海上交通特征方面：潘家財(cái)?shù)确治鯝IS蘊(yùn)含的航向、航速變化率，提出船舶會(huì)遇的時(shí)空數(shù)據(jù)挖掘算法[6-8]；唐存寶等研究了基于AIS的船舶航跡分布算法[9]；肖瀟等提出基于AIS信息的船舶軌跡線聚類模型[2]；寧建強(qiáng)等提出一種基于海量船舶軌跡數(shù)據(jù)的細(xì)粒度網(wǎng)格海上交通密度計(jì)算方法[10]；劉濤等將船舶領(lǐng)域的概念引入DBSCAN(density-based spatial clustering of applications with noise)算法并開(kāi)展水上交通擁擠區(qū)域的聚類分析與識(shí)別[11]；丁兆穎等提出一種基于改進(jìn)DBSCAN的面向海量船舶位置數(shù)據(jù)碼頭挖掘算法[12]；魏照坤等引入AIS數(shù)據(jù)運(yùn)動(dòng)軌跡特征，利用DBSCAN算法開(kāi)展船舶運(yùn)動(dòng)模式識(shí)別與應(yīng)用[13]；G. PALLOTTA等基于船載AIS數(shù)據(jù)點(diǎn)提出無(wú)監(jiān)督的航路辨識(shí)和異常檢測(cè)模型[1]；LIU Bo等引入航向、航速的概念拓展DBSCAN算法，驗(yàn)證船舶是否遵守航路規(guī)定及查找異常情形[14]。

以上文獻(xiàn)較少綜合考慮時(shí)間和空間兩方面對(duì)船載AIS數(shù)據(jù)進(jìn)行時(shí)空聚類分析。然而船載AIS數(shù)據(jù)包含位置、時(shí)間和其他屬性，屬于典型時(shí)空數(shù)據(jù)，隱含著時(shí)空耦合特征和模式。筆者旨在開(kāi)展AIS數(shù)據(jù)時(shí)空聚類分析、挖掘隱含的海上交通時(shí)空特征。

1 相關(guān)工作

時(shí)空數(shù)據(jù)是對(duì)現(xiàn)實(shí)世界中時(shí)空特征和過(guò)程的抽象概括。隨著傳感技術(shù)、計(jì)算機(jī)和大數(shù)據(jù)技術(shù)的發(fā)展，時(shí)空聚類成為海量時(shí)空數(shù)據(jù)分析的一個(gè)重要手段和前沿研究方向[15]。時(shí)空聚類是一個(gè)無(wú)需先驗(yàn)知識(shí)的非監(jiān)督分類過(guò)程，依據(jù)一定相似性準(zhǔn)則將時(shí)空實(shí)體劃分成一系列子類，同一類內(nèi)實(shí)體間的相似度盡可能大于不同類實(shí)體間的相似度[15]。

目前常見(jiàn)時(shí)空聚類分析算法大多從DBSCAN發(fā)展而來(lái)。DBSCAN算法不提前設(shè)置簇?cái)?shù)量，在含有噪聲的數(shù)據(jù)空間中，通過(guò)不斷擴(kuò)展有足夠高密度的區(qū)域來(lái)進(jìn)行聚類，可發(fā)現(xiàn)任意形狀的高密度簇集，并有效地處理噪聲點(diǎn)，過(guò)濾低密度區(qū)域[16]。該算法提出較早，聚類效果、時(shí)間復(fù)雜度和算法復(fù)雜度的綜合評(píng)價(jià)較高，在空間位置分析領(lǐng)域得到了廣泛的應(yīng)用，已經(jīng)成為很多學(xué)者進(jìn)一步完善的主要方法[17]。G-DBSCAN(general-DBSCAN)算法除了空間屬性外，還引入權(quán)重值考慮了其他非空間屬性，認(rèn)為DBSCAN只是一種特殊情況[18]。ST-DBSCAN(spatio-temporal-DBSCAN)算法在DBSCAN算法的基礎(chǔ)上，引入時(shí)間維和非空間屬性，通過(guò)指定空間半徑、時(shí)間窗口與密度閾值，計(jì)算、識(shí)別出核心對(duì)象和噪聲對(duì)象，從而構(gòu)建任意形狀的時(shí)空鄰近簇[19]。4D+SNN(a spatio-temporal density-based clustering approach with 4D similarity)算法在共享近鄰方法基礎(chǔ)上，綜合考慮空間(2D)、時(shí)間(1D)和語(yǔ)義屬性(1D)，是DBSCAN算法的新發(fā)展[20]。

ST-DBSCAN和4D+SNN算法屬于綜合時(shí)間、空間維度和其他屬性的時(shí)空聚類分析，筆者借鑒上述算法理念，考慮船載AIS數(shù)據(jù)報(bào)告特征并加以時(shí)間切片化處理，在DBSCAN算法基礎(chǔ)上提出船載AIS數(shù)據(jù)時(shí)空聚類算法。

2 AIS數(shù)據(jù)約簡(jiǎn)

船載AIS設(shè)備分A、B兩類，300 GT以上船舶安裝A級(jí)AIS，航行時(shí)報(bào)告間隔2～12 s，錨泊時(shí)報(bào)告間隔3 min。其他小型船舶及漁船安裝B級(jí)AIS，移動(dòng)速度不超過(guò)2節(jié)時(shí)報(bào)告間隔3 min，錨泊時(shí)報(bào)告間隔6 min，其他均小于30 s[21]。

定義1基于AIS數(shù)據(jù)的船舶運(yùn)動(dòng)點(diǎn)集為三維時(shí)空域中的有限序列P={p1,p2,p3,,pn}。第i個(gè)船舶運(yùn)動(dòng)點(diǎn)pi=(time, mmsi, lon, lat)，經(jīng)度lon、緯度lot和時(shí)間time構(gòu)成三維時(shí)空域，屬性mmsi為海上移動(dòng)通信業(yè)務(wù)標(biāo)識(shí)(maritime mobile service identity)，可推斷該船為國(guó)際船舶、國(guó)內(nèi)船舶或漁船[22]。

船載AIS設(shè)備連續(xù)發(fā)送數(shù)據(jù)報(bào)告，但報(bào)告間隔不同[21]。在相同時(shí)間內(nèi)，不同船舶報(bào)告AIS數(shù)據(jù)對(duì)象的數(shù)量可能相差十幾倍。指定時(shí)間內(nèi)AIS數(shù)據(jù)點(diǎn)數(shù)與船舶數(shù)不成一定比例，使盲目指定時(shí)間距離開(kāi)展時(shí)空聚類分析沒(méi)有實(shí)際意義。為便于時(shí)空聚類分析，僅考慮速度大于2節(jié)的在航船載AIS數(shù)據(jù)點(diǎn)，并對(duì)其開(kāi)展時(shí)間切片化約簡(jiǎn)，即每分鐘只選取第一個(gè)報(bào)告點(diǎn)，去除該分鐘內(nèi)其他報(bào)告點(diǎn)。

定義2AIS數(shù)據(jù)時(shí)間切片化指對(duì)某船所有AIS數(shù)據(jù)點(diǎn)根據(jù)時(shí)間量度進(jìn)行約簡(jiǎn)，即按時(shí)間先后排序，只保留每分鐘內(nèi)第一個(gè)報(bào)告點(diǎn)。

算法1AIS數(shù)據(jù)時(shí)間切片化

輸入：某區(qū)域某時(shí)間段內(nèi)的原始AIS數(shù)據(jù)集D1={p1,p2,p3,,pn}。

輸出：該區(qū)域該時(shí)間段內(nèi)每艘船舶每分鐘有且僅有第一個(gè)報(bào)告點(diǎn)的新數(shù)據(jù)集D2。

步驟：

1)去除速度小于2節(jié)、屬性值缺失和MMSI不合規(guī)范的點(diǎn)。

2)將D1中所有數(shù)據(jù)pi以mmsi為主要關(guān)鍵字、time為次要關(guān)鍵字排序。

3)將time的秒位設(shè)置成0。

4)去掉mmsi、time均相同的數(shù)據(jù)元素。

對(duì)于速度大于2節(jié)的在航船舶，不論裝載A或B級(jí)AIS系統(tǒng)，報(bào)告間隔均小于30 s，其AIS數(shù)據(jù)經(jīng)算法1處理后每分鐘內(nèi)有且僅有第一個(gè)AIS報(bào)告點(diǎn)。比如，某船舶以10節(jié)速度航行，時(shí)間屬性值分別為12:31:02、12:31:13、12:31:21、12:31:32的4條連續(xù)報(bào)告AIS數(shù)據(jù)經(jīng)算法1處理后，變?yōu)?2:31(12:31:00，實(shí)際為12:31:02)時(shí)間點(diǎn)數(shù)據(jù)，即只取第1條(12:31:02)，后3條舍去，誤差為2 s，10.3 m。根據(jù)AIS報(bào)告間隔規(guī)律和實(shí)際數(shù)據(jù)抽樣查證，正常情況下某分鐘內(nèi)第一條數(shù)據(jù)都在其前30 s內(nèi)，且大部分都在前20 s內(nèi)。由于沿海船舶平均速度較低，約10節(jié)左右，30 s內(nèi)僅航行百余米，故將某分鐘的第一條數(shù)據(jù)看作整分時(shí)刻的數(shù)據(jù)所造成的誤差在可接受范圍之內(nèi)。

3 AIS數(shù)據(jù)時(shí)空聚類算法

作為DBSACN在時(shí)空域的拓展，將密度、鄰域、噪聲等在時(shí)空域進(jìn)行新的定義。

定義3任意一點(diǎn)的時(shí)空密度是以該點(diǎn)為圓心、鄰域半徑Eps為半徑、2倍時(shí)間距離Δt為高的圓柱體內(nèi)所包含的點(diǎn)的數(shù)量。如圖1，p點(diǎn)的時(shí)空密度為7。

圖1 船載AIS數(shù)據(jù)時(shí)空維度Fig. 1 Spatio-temporal dimension of shipborne AIS data

定義5若滿足條件點(diǎn)q在點(diǎn)p的時(shí)空鄰域內(nèi)，且p是時(shí)空核心點(diǎn)，則稱點(diǎn)p到點(diǎn)q時(shí)空直接密度可達(dá)。

定義6若有一組有序集Y={p1,p2,,pn}(其中，p1=p，pn=q)，對(duì)于任意的k(k

定義7若存在點(diǎn)o∈D使得點(diǎn)p和點(diǎn)q均從點(diǎn)o時(shí)空密度可達(dá)，則稱點(diǎn)p和點(diǎn)q時(shí)空密度連接。

定義8若集合C是數(shù)據(jù)庫(kù)D的一個(gè)非空子集，點(diǎn)p∈C時(shí)空密度到達(dá)的任一點(diǎn)q∈C，且任意p∈C、q∈C，p和q是時(shí)空密度連接的，那么稱集合C是一個(gè)時(shí)空簇。

定義9時(shí)空核心點(diǎn)是在指定鄰域半徑Eps和時(shí)間距離Δt的時(shí)空鄰域中含有大于最小鄰域?qū)ο髷?shù)MinPts的點(diǎn)。

定義10時(shí)空邊界點(diǎn)是在時(shí)空域中自身不是時(shí)空核心點(diǎn)，但是與某一個(gè)或者幾個(gè)時(shí)空核心點(diǎn)密度連接的點(diǎn)。

定義11時(shí)空噪聲點(diǎn)是不屬于任何時(shí)空簇的點(diǎn)。

在上述定義的基礎(chǔ)上，基于船載AIS數(shù)據(jù)的時(shí)空密度聚類算法的步驟如下：

算法2船載AIS數(shù)據(jù)時(shí)空聚類算法

輸入：數(shù)據(jù)點(diǎn)集D、MinPts、Eps和Δt。

輸出：時(shí)空聚類簇。

步驟：

1)將數(shù)據(jù)集D中的所有對(duì)象指定為未標(biāo)記狀態(tài)。

2)讀取一個(gè)未標(biāo)記的對(duì)象p，在D中尋找未標(biāo)記的所有滿足dist(p,q)

3)如果查找出的對(duì)象數(shù)大于等于MinPts，則標(biāo)記該對(duì)象為時(shí)空核心點(diǎn)，建立新的時(shí)空簇C，簇號(hào)為ClusterID；反之則標(biāo)記為時(shí)空噪聲點(diǎn)，并且轉(zhuǎn)步驟2。

4)將p時(shí)空鄰域內(nèi)所有對(duì)象加入C，將其的簇號(hào)賦值為ClusterID。從C中未被標(biāo)記的對(duì)象開(kāi)始逐一繼續(xù)搜索，將所有時(shí)空密度可達(dá)的對(duì)象簇號(hào)賦值為ClusterID。

5)ClusterID+1，轉(zhuǎn)步驟2，直到D中所有點(diǎn)都被標(biāo)記為止。

上述算法和DBSCAN擁有相同的時(shí)間復(fù)雜度O(n2)。

4 實(shí)例分析

以浙滬交界水域?yàn)檠芯繉?duì)象，浙江沿海東航路、中航路、洋山港主航道、小型船舶和漁船習(xí)慣航路等在這里交匯，交通流密集，通航狀態(tài)復(fù)雜，2016年7—12月的船舶流量線如圖2。在圖2中ABCD四邊形界限內(nèi)提取2017年1月5、10、15、20、25日共40萬(wàn)余條船載AIS數(shù)據(jù)。

圖2 研究區(qū)域Fig. 2 Research area

4.1 數(shù)據(jù)預(yù)處理

以1月15日75 722條數(shù)據(jù)為例，經(jīng)算法1處理后，即對(duì)于同一艘船舶每分鐘內(nèi)僅保留第一條AIS數(shù)據(jù)，得到20 850條AIS數(shù)據(jù)，見(jiàn)表1。

表1 處理后的AIS數(shù)據(jù)列表Table 1 AIS data list after preprocessing

4.2 時(shí)空聚類分析

以上述20 850條AIS數(shù)據(jù)為基礎(chǔ)，使用JAVA語(yǔ)言編寫(xiě)并借助WEKA軟件運(yùn)行船載AIS數(shù)據(jù)時(shí)空聚類算法。反復(fù)調(diào)整參數(shù)，當(dāng)Eps=0.9 n mile、Δt=3 min、MinPts=35時(shí)，即對(duì)于任意一點(diǎn)p，在以p為圓心、Eps=0.9 n mile為半徑、分別向上向下延伸高度為Δt=3 min的圓柱體內(nèi)至少有MinPts=35個(gè)點(diǎn)，該圓柱體在三維時(shí)空域內(nèi)不斷游走，直至不再包含35個(gè)點(diǎn)，所有網(wǎng)進(jìn)的點(diǎn)形成一個(gè)時(shí)空鄰近簇。所選數(shù)據(jù)集形成2個(gè)時(shí)空簇，如圖3、表2。

圖3 聚類結(jié)果示意Fig. 3 Clustering result visualization

時(shí)間MMSI經(jīng)度/(°)緯度/(°)簇20:50412425318122.656 230.511 73cluster020:49412425318122.654 930.510 25cluster017:25412427363122.545 930.515 62cluster117:50412427363122.560 630.503 11noise

聚類結(jié)果特征參見(jiàn)表3。從19∶18至21∶14時(shí)，該水域有31艘船舶(根據(jù)MMSI編碼規(guī)律分析[22]，含25艘漁船，3艘國(guó)際航行船舶，3艘國(guó)內(nèi)貨船)的1 725個(gè)AIS數(shù)據(jù)點(diǎn)在圖中位置集中出現(xiàn)，滿足時(shí)空密度條件構(gòu)成簇0(cluster0)。從17∶15至17∶30時(shí)，該水域有9艘船舶(含8艘漁船，1艘國(guó)際航行船舶)的121個(gè)AIS數(shù)據(jù)點(diǎn)在圖中位置集中出現(xiàn)，滿足時(shí)空密度條件構(gòu)成簇1(cluster1)。

由此可看出，當(dāng)日17∶00、20∶00前后該水域漁船結(jié)伴而行、密集活動(dòng)的情況較突出，東航路、中航路雖然AIS數(shù)據(jù)點(diǎn)密集，但由于商船之間獨(dú)立性較強(qiáng)，并未發(fā)生AIS數(shù)據(jù)點(diǎn)在時(shí)空鄰域內(nèi)密集出現(xiàn)的情況。

表3 聚類結(jié)果特征Table 3 Clustering result characteristics

4.3 聚類對(duì)比分析

按照4.1、4.2節(jié)所述方法對(duì)該月其他4天(為總結(jié)規(guī)律，不選擇連續(xù)日期)的AIS數(shù)據(jù)開(kāi)展時(shí)空聚類分析，參數(shù)Eps=0.9 n mile、Δt=3 min、MinPts=30或35，最后形成1或2個(gè)簇，如圖4。

圖4 聚類結(jié)果示意Fig. 4 Clustering result visualization

當(dāng)月5天的數(shù)據(jù)聚類結(jié)果對(duì)比如表4。

表4 聚類結(jié)果特征對(duì)比Table 4 Contrast of clustering result characteristics

5天AIS數(shù)據(jù)聚類形成多個(gè)不同的簇，各簇的點(diǎn)在空間分布上相對(duì)分散，但時(shí)間分布上呈現(xiàn)一定規(guī)律，18∶00～19∶00時(shí)左右船舶在時(shí)空域上比較密集(占總簇?cái)?shù)60%以上)。

5 結(jié) 語(yǔ)

通過(guò)分析船載AIS數(shù)據(jù)特征，提出時(shí)間切片化約簡(jiǎn)方法，在DBSCAN算法基礎(chǔ)上引入時(shí)間和空間元素給出船載AIS數(shù)據(jù)時(shí)空聚類算法，并對(duì)浙滬交界復(fù)雜水域的船載AIS數(shù)據(jù)開(kāi)展時(shí)空聚類分析，得出漁船結(jié)伴而行、18∶00～19∶00左右船舶密集的常見(jiàn)交通模式。與其他船載AIS數(shù)據(jù)挖掘算法相比，筆者所提算法能更好地顧及船舶交通流的時(shí)空耦合特征，發(fā)現(xiàn)隱含的時(shí)空模式，為主管機(jī)關(guān)開(kāi)展船舶交通管理、優(yōu)化通航秩序、保障航行安全等提供了一種新途徑。

該算法對(duì)參數(shù)較敏感，參數(shù)選擇需較多專業(yè)背景知識(shí)，部分小型船舶存在不開(kāi)啟AIS或AIS數(shù)據(jù)報(bào)告間隔過(guò)大的情況，以上問(wèn)題影響數(shù)據(jù)分析結(jié)果，有待下一步深入研究。