基于時空密度的船載AIS數據聚類分析方法研究

李永攀，劉正江，鄭中義

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

0 引 言

船舶自動識別系統(automatic identification system，AIS)是一種船載設備，向岸基及周邊船舶發送自身的靜態、動態和航次數據。AIS的強制配備和廣泛應用，不僅提高了船舶航行安全和效率，且為開展相關數據挖掘、尋找海上交通規律、協助海上交通規劃與管理提供了寶貴素材。

近年來船載AIS數據挖掘方法和應用迅速發展。學者們主要基于AIS數據點[1]或軌跡線[2]的經緯度、航向和航速等屬性，利用一定數學模型和信息技術開展相關數據挖掘。通過挖掘AIS數據可識別海上錨泊區、作業區和擁擠區等特殊區域[1]、識別主要船舶航路[3]、分析船舶領域和運動模式[4]、研究船舶密度和速度分布[5]、評估船舶會遇或碰撞風險[6]、推算到港概率或航跡趨勢[7]、開展異常檢測、設計或審查定線制、評估碳排放等。

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

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

1 相關工作

時空數據是對現實世界中時空特征和過程的抽象概括。隨著傳感技術、計算機和大數據技術的發展，時空聚類成為海量時空數據分析的一個重要手段和前沿研究方向[15]。時空聚類是一個無需先驗知識的非監督分類過程，依據一定相似性準則將時空實體劃分成一系列子類，同一類內實體間的相似度盡可能大于不同類實體間的相似度[15]。

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

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

2 AIS數據約簡

船載AIS設備分A、B兩類，300 GT以上船舶安裝A級AIS，航行時報告間隔2～12 s，錨泊時報告間隔3 min。其他小型船舶及漁船安裝B級AIS，移動速度不超過2節時報告間隔3 min，錨泊時報告間隔6 min，其他均小于30 s[21]。

定義1基于AIS數據的船舶運動點集為三維時空域中的有限序列P={p1,p2,p3,,pn}。第i個船舶運動點pi=(time, mmsi, lon, lat)，經度lon、緯度lot和時間time構成三維時空域，屬性mmsi為海上移動通信業務標識(maritime mobile service identity)，可推斷該船為國際船舶、國內船舶或漁船[22]。

船載AIS設備連續發送數據報告，但報告間隔不同[21]。在相同時間內，不同船舶報告AIS數據對象的數量可能相差十幾倍。指定時間內AIS數據點數與船舶數不成一定比例，使盲目指定時間距離開展時空聚類分析沒有實際意義。為便于時空聚類分析，僅考慮速度大于2節的在航船載AIS數據點，并對其開展時間切片化約簡，即每分鐘只選取第一個報告點，去除該分鐘內其他報告點。

定義2AIS數據時間切片化指對某船所有AIS數據點根據時間量度進行約簡，即按時間先后排序，只保留每分鐘內第一個報告點。

算法1AIS數據時間切片化

輸入：某區域某時間段內的原始AIS數據集D1={p1,p2,p3,,pn}。

輸出：該區域該時間段內每艘船舶每分鐘有且僅有第一個報告點的新數據集D2。

步驟：

1)去除速度小于2節、屬性值缺失和MMSI不合規范的點。

2)將D1中所有數據pi以mmsi為主要關鍵字、time為次要關鍵字排序。

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

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

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

3 AIS數據時空聚類算法

作為DBSACN在時空域的拓展，將密度、鄰域、噪聲等在時空域進行新的定義。

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

圖1 船載AIS數據時空維度Fig. 1 Spatio-temporal dimension of shipborne AIS data

定義5若滿足條件點q在點p的時空鄰域內，且p是時空核心點，則稱點p到點q時空直接密度可達。

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

定義7若存在點o∈D使得點p和點q均從點o時空密度可達，則稱點p和點q時空密度連接。

定義8若集合C是數據庫D的一個非空子集，點p∈C時空密度到達的任一點q∈C，且任意p∈C、q∈C，p和q是時空密度連接的，那么稱集合C是一個時空簇。

定義9時空核心點是在指定鄰域半徑Eps和時間距離Δt的時空鄰域中含有大于最小鄰域對象數MinPts的點。

定義10時空邊界點是在時空域中自身不是時空核心點，但是與某一個或者幾個時空核心點密度連接的點。

定義11時空噪聲點是不屬于任何時空簇的點。

在上述定義的基礎上，基于船載AIS數據的時空密度聚類算法的步驟如下：

算法2船載AIS數據時空聚類算法

輸入：數據點集D、MinPts、Eps和Δt。

輸出：時空聚類簇。

步驟：

1)將數據集D中的所有對象指定為未標記狀態。

2)讀取一個未標記的對象p，在D中尋找未標記的所有滿足dist(p,q)

3)如果查找出的對象數大于等于MinPts，則標記該對象為時空核心點，建立新的時空簇C，簇號為ClusterID；反之則標記為時空噪聲點，并且轉步驟2。

4)將p時空鄰域內所有對象加入C，將其的簇號賦值為ClusterID。從C中未被標記的對象開始逐一繼續搜索，將所有時空密度可達的對象簇號賦值為ClusterID。

5)ClusterID+1，轉步驟2，直到D中所有點都被標記為止。

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

4 實例分析

以浙滬交界水域為研究對象，浙江沿海東航路、中航路、洋山港主航道、小型船舶和漁船習慣航路等在這里交匯，交通流密集，通航狀態復雜，2016年7—12月的船舶流量線如圖2。在圖2中ABCD四邊形界限內提取2017年1月5、10、15、20、25日共40萬余條船載AIS數據。

圖2 研究區域Fig. 2 Research area

4.1 數據預處理

以1月15日75 722條數據為例，經算法1處理后，即對于同一艘船舶每分鐘內僅保留第一條AIS數據，得到20 850條AIS數據，見表1。

表1 處理后的AIS數據列表Table 1 AIS data list after preprocessing

4.2 時空聚類分析

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

圖3 聚類結果示意Fig. 3 Clustering result visualization

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

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

由此可看出，當日17∶00、20∶00前后該水域漁船結伴而行、密集活動的情況較突出，東航路、中航路雖然AIS數據點密集，但由于商船之間獨立性較強，并未發生AIS數據點在時空鄰域內密集出現的情況。

表3 聚類結果特征Table 3 Clustering result characteristics

4.3 聚類對比分析

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

圖4 聚類結果示意Fig. 4 Clustering result visualization

當月5天的數據聚類結果對比如表4。

表4 聚類結果特征對比Table 4 Contrast of clustering result characteristics

5天AIS數據聚類形成多個不同的簇，各簇的點在空間分布上相對分散，但時間分布上呈現一定規律，18∶00～19∶00時左右船舶在時空域上比較密集(占總簇數60%以上)。

5 結 語

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

該算法對參數較敏感，參數選擇需較多專業背景知識，部分小型船舶存在不開啟AIS或AIS數據報告間隔過大的情況，以上問題影響數據分析結果，有待下一步深入研究。