基于改進(jìn)K中心點(diǎn)聚類的船舶典型軌跡自適應(yīng)挖掘算法

李倍瑩 張新宇 沈忱 姚海元 齊越

摘要：針對目前船舶典型軌跡的挖掘多以軌跡段作為基本單元，導(dǎo)致聚類對象較為復(fù)雜且聚類參數(shù)難以確定的問題，本文提出一種基于改進(jìn)K中心點(diǎn)聚類的船舶典型軌跡自適應(yīng)挖掘算法。算法以軌跡點(diǎn)作為聚類對象，分析船舶的航速、航向特征并對軌跡點(diǎn)進(jìn)行壓縮;將分段均方根誤差引入K中心點(diǎn)聚類算法，實(shí)現(xiàn)聚類參數(shù)的自適應(yīng)選擇;提取其中的聚類中心點(diǎn)作為軌跡特征點(diǎn)，得到不同類別船舶的典型軌跡。以天津港主航道船舶自動識別系統(tǒng)（automatic identification system， AIS）數(shù)據(jù)為例，基于地理信息系統(tǒng)平臺ArcGIS實(shí)現(xiàn)聚類結(jié)果的可視化展示。實(shí)驗(yàn)結(jié)果表明，運(yùn)用該算法得到的船舶典型軌跡與實(shí)際相符，自適應(yīng)程度較高。研究結(jié)果對于輔助船舶軌跡異常檢測及挖掘海上交通特征具有重要意義。

關(guān)鍵詞：? 海上交通數(shù)據(jù)挖掘; 船舶典型軌跡; K中心點(diǎn)聚類; 軌跡特征點(diǎn); 自適應(yīng)

中圖分類號：? U675.79

文獻(xiàn)標(biāo)志碼：? A

收稿日期： 2021-03-25

修回日期： 2021-05-12

基金項(xiàng)目： 國家自然科學(xué)基金（51779028）

作者簡介：

李倍瑩（1997—），女，黑龍江鶴崗人，碩士研究生，研究方向?yàn)楹Ｊ麓髷?shù)據(jù)挖掘，（E-mail）libeiying0413@163.com;

張新宇（1978—），男，吉林長春人，教授，博導(dǎo)，博士，研究方向?yàn)楹Ｊ麓髷?shù)據(jù)、船舶交通組織，（E-mail）zhangxy@dlmu.edu.com

Meeting of the Waterborne Transport Division， World Transport Convention 2021 （WTC 2021）

Adaptive algorithm for ship typical trajectory mining based on improved K-medoids clustering

LI Beiying1， ZHANG Xinyu1， SHEN Chen2， YAO Haiyuan2， QI Yue2

（1. Navigation College， Dalian Maritime University， Dalian 116026， Liaoning， China;

2. Transport Planning and Research Institute， Ministry of Transport， Beijing 100028， China）

Abstract： Currently， the trajectory segment is taken as the basic unit in the ship typical trajectory mining， which leads to complex clustering objects and difficulty in determining cluster parameters. To solve the problem， the adaptive algorithm for ship typical trajectory mining based on the improved K-medoids clustering is proposed. The algorithm takes trajectory points as clustering objects. The characteristics of ship speed and course are analyzed， and the trajectory points are compressed; the segmented root mean square error is introduced into the K-medoids clustering algorithm to realize the adaptive selection of clustering parameters; the cluster center points are extracted as the trajectory feature points， and the typical trajectories of different types of ships are obtained. Taking automatic identification system （AIS） data of the main channel of Tianjin Port as an example， this paper realizes the visualization of clustering results based on the geographic information system platform ArcGIS. The experimental results show that the ship typical trajectories obtained by the algorithm are consistent with the actual situation， and the degree of self-adaptation is high. The research results are of great significance to assist the detection of abnormal ship trajectories and mine the characteristics of marine traffic flow.

Key words： marine traffic data mining; ship typical trajectory; K-medoids clustering; trajectory feature point; self-adaption

0 引 言

隨著經(jīng)濟(jì)的快速發(fā)展，海上交通密度逐年上升，船舶也呈現(xiàn)出大型化、高速化發(fā)展趨勢，海上通航安全管理變得愈發(fā)困難。船舶自動識別系統(tǒng)（automatic identification system， AIS）作為一種新型助航系統(tǒng)，能夠發(fā)送海量的、表征船舶運(yùn)動狀態(tài)的數(shù)據(jù)。對AIS數(shù)據(jù)進(jìn)行深度挖掘，可發(fā)現(xiàn)船舶的典型行為模式，其中，最為直觀的船舶行為模式由船舶軌跡體現(xiàn)。對船舶軌跡數(shù)據(jù)進(jìn)行聚類分析，挖掘出船舶典型的運(yùn)動軌跡，可為船舶軌跡異常檢測[1]和航跡預(yù)測[2]提供技術(shù)支持，還可用于船舶航行時(shí)間預(yù)測[3]、航路規(guī)劃[4]和船舶交通流特征分析[5]等。

目前，船舶軌跡數(shù)據(jù)聚類分析方法主要有：基于軌跡段的聚類方法和基于軌跡點(diǎn)的聚類方法[6]?；谲壽E段的聚類方法通過采用相關(guān)的聚類算法對船舶軌跡數(shù)據(jù)進(jìn)行聚類，得到具有相似運(yùn)動模式的軌跡簇。根據(jù)聚類對象的不同，基于軌跡段的聚類可分為基于軌跡整體的聚類和基于軌跡片段的聚類兩種模式。LI等[7]將船舶軌跡整體作為聚類對象，用不同軌跡間的距離衡量軌跡之間的相似度;牟軍敏等[8]、曹妍妍等[9]運(yùn)用軌跡整體的典型特征對物體的軌跡進(jìn)行聚類，將改進(jìn)的Hausdorff距離作為度量軌跡整體間相似度的指標(biāo)，得到最終的聚類結(jié)果。LEE等[10]首先提出一種基于軌跡段的聚類算法，用最小描述長度原則對軌跡進(jìn)行分割，然后運(yùn)用基于密度的線段聚類算法，得到船舶的公共子軌跡;江玉玲等[11]提出一種改進(jìn)的軌跡段聚類算法DBSCAN（density-based spatial clustering of applications with noise），將離散Fréchet距離作為軌跡段間相似度的衡量標(biāo)準(zhǔn)，最終得出船舶典型軌跡。以上將船舶軌跡段作為聚類對象的方法雖能夠較好地反映軌跡片段的特征，但難以確定軌跡之間的相似度閾值，且對線段進(jìn)行聚類的算法較為復(fù)雜，難以將軌跡片段相連構(gòu)成船舶典型軌跡?；谲壽E點(diǎn)的聚類方法通常將AIS數(shù)據(jù)中由經(jīng)緯度坐標(biāo)表示的船舶位置散點(diǎn)作為聚類對象，進(jìn)而劃分船舶軌跡的類簇，得到船舶的軌跡特征模式。LIU等[12]結(jié)合船舶的航速和航向特征，在DBSCAN的基礎(chǔ)上提出DBSCANSD算法，對AIS數(shù)據(jù)中船舶軌跡點(diǎn)進(jìn)行聚類，提取船舶的主要航行軌跡;王莉莉等[13]提出基于航跡點(diǎn)特征的時(shí)間窗分割算法，并運(yùn)用K均值聚類算法進(jìn)行聚類得到航空器的中心航跡;王森杰等[14]以船舶軌跡點(diǎn)為研究對象，提出一種分層建模的船舶軌跡聚類算法，并通過改進(jìn)道格拉斯-普克算法提取船舶軌跡特征點(diǎn)，實(shí)現(xiàn)船舶軌跡點(diǎn)的快速聚類。運(yùn)用船舶軌跡點(diǎn)進(jìn)行聚類具有運(yùn)算效率高、聚類對象簡單的特點(diǎn)，但聚類參數(shù)的確定也是一大難點(diǎn)。

針對船舶軌跡段聚類算法復(fù)雜程度較高的問題，本文將經(jīng)過壓縮后的船舶軌跡點(diǎn)作為聚類對象，簡化聚類過程，降低其復(fù)雜程度;為解決傳統(tǒng)的軌跡點(diǎn)聚類算法自適應(yīng)程度較低的問題，本文提出一種綜合考慮船舶航速、航向特征，結(jié)合分段均方根誤差，實(shí)現(xiàn)自適應(yīng)地對不同類別船舶的軌跡點(diǎn)進(jìn)行聚類的典型軌跡挖掘算法。

1 船舶軌跡點(diǎn)數(shù)據(jù)預(yù)處理

經(jīng)過解碼后的船舶AIS數(shù)據(jù)，還需要經(jīng)過清洗才能使用。清洗過程包括刪除重復(fù)的AIS數(shù)據(jù)，刪除有明顯錯誤的數(shù)據(jù)，刪除不符合常識的異常數(shù)據(jù)等。為減少計(jì)算量，提高算法的運(yùn)行效率，首先需要構(gòu)建能夠表示船舶軌跡點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，在此基礎(chǔ)上對船舶的軌跡點(diǎn)進(jìn)行壓縮，得到用于船舶典型軌跡挖掘的聚類點(diǎn)集。

1.1 船舶軌跡點(diǎn)數(shù)據(jù)結(jié)構(gòu)的建立

AIS數(shù)據(jù)中蘊(yùn)含了豐富的表示船舶特性的信息，包括船舶海上移動通信業(yè)務(wù)識別碼（maritime mobile service identity， MMSI）、船名、船舶呼號、船舶類型、船長、船寬、船舶吃水等靜態(tài)信息，以及船舶位置（經(jīng)度、緯度）、對地船速、對地航向、船首向、接收時(shí)間等動態(tài)信息。

船舶航行的軌跡點(diǎn)是由一系列隨空間和時(shí)間變化的散點(diǎn)表征和確定的，而這些散點(diǎn)可以用上述AIS數(shù)據(jù)中的部分信息表示?；诖?，本文的船舶軌跡點(diǎn)數(shù)據(jù)結(jié)構(gòu)包括：經(jīng)度、緯度，表示船舶的位置屬性;對地船速，表示船舶的速度屬性;對地航向，表示船舶的方向?qū)傩?接收時(shí)間，表示船舶位置的時(shí)間屬性;船舶類型、船長、船寬，表示船舶的靜態(tài)屬性。

通過建立船舶軌跡點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，保留了能夠反映船舶軌跡點(diǎn)的信息，剔除了冗余信息，從而提高了軌跡數(shù)據(jù)的存儲效率和船舶典型軌跡的挖掘效率。

1.2 船舶軌跡點(diǎn)壓縮

設(shè)Ti，j為在某時(shí)刻某船的軌跡信息，其中，i為該船的MMSI，j為具有同一MMSI的船舶的軌跡點(diǎn)次序。因此，Ti，j和Ti，j+1分別表示具有相同MMSI的船舶按照接收時(shí)間進(jìn)行排序后得到的相鄰軌跡點(diǎn)信息，其中，tj和tj+1分別表示相鄰軌跡點(diǎn)的發(fā)送時(shí)間，vj和vj+1分別表示相鄰軌跡點(diǎn)處的航速大小，cj和cj+1分別表示相鄰軌跡點(diǎn)處的航向。船舶相鄰軌跡點(diǎn)的航速變化率和航向變化率計(jì)算方法如下：

v′=ΔvΔt=vj+1-vjtj+1-tj

c′=ΔcΔt=cj+1-cjtj+1-tj

（1）

航速變化率和航向變化率的示意圖見圖1。

在對船舶軌跡點(diǎn)進(jìn)行壓縮之前，需要確定航速變化率和航向變化率的閾值。若選擇的閾值太小，則會導(dǎo)致軌跡點(diǎn)數(shù)量過多，在進(jìn)行數(shù)據(jù)存儲時(shí)會浪費(fèi)一定的空間，且算法的運(yùn)行時(shí)間會增加;若選擇的

閾值太大，則會導(dǎo)致軌跡點(diǎn)數(shù)量過少，用于聚類的點(diǎn)較少，難以保證聚類結(jié)果的準(zhǔn)確度。因此，一般將航速變化率和航向變化率的閾值設(shè)為各自的平均值[15]，分別記為v′、c′。

船舶軌跡點(diǎn)壓縮的流程如下：

（1）分別將每艘船軌跡的起點(diǎn)、終點(diǎn)作為備選點(diǎn)。

（2）計(jì)算每艘船軌跡點(diǎn)的航速變化率、航向變化率及各自的平均值。

（3）從第二個軌跡點(diǎn)開始，首先判斷軌跡點(diǎn)處的航速變化率情況。若v′>v′，則將該點(diǎn)作為備選點(diǎn)，否則改為判斷航向變化率情況;若c′>

c′，則將該點(diǎn)選為備選點(diǎn)，否則該點(diǎn)不是備選點(diǎn)。依次遍歷直至倒數(shù)第二個軌跡點(diǎn)。

（4）將篩選出的船舶軌跡點(diǎn)依次按照MMSI、接收時(shí)間進(jìn)行排序，得到船舶軌跡備選點(diǎn)的集合，作為壓縮后的船舶軌跡點(diǎn)集，用于后續(xù)船舶典型軌跡的挖掘。

2 船舶典型軌跡挖掘模型

本文的船舶典型軌跡挖掘算法是基于軌跡點(diǎn)的聚類算法，在得到經(jīng)過清洗和預(yù)處理的船舶軌跡點(diǎn)數(shù)據(jù)后，運(yùn)用自適應(yīng)K中心點(diǎn)聚類算法進(jìn)行聚類，通過將傳統(tǒng)的K中心點(diǎn)聚類算法與分段均方根誤差評價(jià)指標(biāo)相結(jié)合，自適應(yīng)尋找局部最佳K值，最終將聚類中心點(diǎn)相連得到船舶典型軌跡，具體的技術(shù)路線見圖2。

2.1 K中心點(diǎn)聚類算法原理

K均值聚類算法和K中心點(diǎn)聚類算法是兩種典型的基于劃分的聚類方法。當(dāng)樣本數(shù)據(jù)中存在噪聲點(diǎn)時(shí)，使用K均值聚類算法進(jìn)行聚類會導(dǎo)致結(jié)果產(chǎn)生一定的誤差。為削弱噪聲數(shù)據(jù)對聚類結(jié)果的影響，本文采用K中心點(diǎn)聚類算法對船舶軌跡特征點(diǎn)進(jìn)行聚類。該算法步驟與K均值聚類算法步驟大體相似，區(qū)別在于：K均值聚類算法通過計(jì)算當(dāng)前類簇中所有數(shù)據(jù)點(diǎn)的平均值來確定聚類中心，而K中心點(diǎn)聚類算法將聚類中心選為當(dāng)前類簇?cái)?shù)據(jù)點(diǎn)中的一點(diǎn)。

算法所需的定義如下：

定義1 任意兩樣本點(diǎn)i（xi，yi）與點(diǎn)j（xj，yj）之間的距離d采用歐幾里得距離公式進(jìn)行計(jì)算：

d=（xi-xj）2+（yi-yj）2

（2）

式中：i，j=1，2，…，n。

定義2 聚類的絕對誤差E：

E=wm=1P∈cnPO2m

（3）

式中：Om為選取的聚類中心點(diǎn)，m=1，2，…，w;P為類簇cn中的樣本點(diǎn)。

具體的算法流程[16]如下：

步驟1 從樣本數(shù)據(jù)中隨機(jī)選取w個初始對象（O1，O2，…，Ow）作為初始聚類中心點(diǎn)。

步驟2 根據(jù)式（2）計(jì)算其他樣本點(diǎn)到各聚類中心點(diǎn)的距離，將各樣本點(diǎn)劃分到與各聚類中心點(diǎn)最近的類簇中。

步驟3 隨機(jī)選擇一個非中心點(diǎn)Or，使得根據(jù)式（3）計(jì)算得到的絕對誤差減小，不斷用Or代替Om。

步驟4 重復(fù)執(zhí)行步驟2和步驟3，直至計(jì)算出的相鄰兩次絕對誤差值保持不變，即聚類中心不再發(fā)生變化，否則繼續(xù)執(zhí)行步驟3。

步驟5 算法終止，輸出最終的聚類中心點(diǎn)和類簇。

2.2 基于自適應(yīng)K中心點(diǎn)聚類算法的船舶典型軌跡挖掘

由于K中心點(diǎn)聚類算法是一種無監(jiān)督學(xué)習(xí)方法，K值的選擇受人的因素影響較大。為實(shí)現(xiàn)K中心點(diǎn)聚類算法中參數(shù)的自適應(yīng)確定，結(jié)合概率論與數(shù)理統(tǒng)計(jì)理論將分段均方根誤差作為評價(jià)指標(biāo)，與K中心點(diǎn)聚類算法相結(jié)合對傳統(tǒng)的K中心點(diǎn)聚類算法進(jìn)行改進(jìn)，形成自適應(yīng)K中心點(diǎn)聚類算法。均方根誤差利用觀測值與真實(shí)值之間的差值計(jì)算得到，可以反映線段對點(diǎn)的擬合程度，其計(jì)算式為

ERMS=1NNi=1（yoi-ypi）2

（4）

式中：N為觀測樣本的數(shù)量;yo，i為觀測樣本的因變量;yp，i為觀測樣本的預(yù)測值，該值越小，表明擬合程度越好。

均方根誤差通常將整個樣本點(diǎn)數(shù)據(jù)作為真實(shí)值，導(dǎo)致其不能很好地反映局部樣本的擬合效果?；诖?，本文提出分段均方根誤差，即將誤差的計(jì)算對象縮小為局部樣本點(diǎn)，實(shí)現(xiàn)誤差的局部最小化，并將其與傳統(tǒng)K中心點(diǎn)聚類算法相結(jié)合，作為基于自適應(yīng)K中心點(diǎn)聚類的船舶典型軌跡挖掘算法的參數(shù)確定依據(jù)。分段均方根誤差計(jì)算式為

ESRMS=1K+1K+1l=1ERMS，l

（5）

式中：K為最終確定的聚類中心點(diǎn)數(shù)，K+1為樣本被聚類中心點(diǎn)所分成的總段數(shù);l為段的次序。

運(yùn)用自適應(yīng)K中心點(diǎn)聚類算法挖掘船舶典型軌跡的偽代碼如下：

輸入：經(jīng)壓縮的軌跡數(shù)據(jù)集T，最大聚類簇Kmax

輸出：船舶典型軌跡

1： for K=2 to Kmax do

2：? get Or//隨機(jī)生成K個初始聚類中心點(diǎn)

3：? for i=1 to n do

4：? d=compute d（Ti，O1）//根據(jù)式（2）計(jì)算各軌跡點(diǎn)到初始聚類中心之間的歐幾里得距離，并將各軌跡點(diǎn)劃分到與各聚類中心點(diǎn)最近的類簇中

5：?? setlabeli=1

6：?? for j=2 to K do

7：new_d=d（Ti，Oj）

8：if new_d

9： setlabeli=j

10：d=new_d

11：? end if

12：? compute new_E//在每一類簇中，根據(jù)式（3）計(jì)算各軌跡點(diǎn)之間的絕對誤差，將具有最小絕對誤差的點(diǎn)作為新的聚類中心點(diǎn)

13：?? if new_E = = E then

14：break

15：?? else

16：E=new_E

17：?? end if

18：?? end for

19：? end for

20：? rank Om//將最終的聚類中心點(diǎn)按經(jīng)度進(jìn)行排序

21：? L=K+1//根據(jù)聚類中心點(diǎn)將船舶軌跡點(diǎn)劃分到不同的航段（航段數(shù)=K+1）

22：? compute equation//根據(jù)相鄰兩個聚類中心點(diǎn)的經(jīng)緯度坐標(biāo)值計(jì)算出每一航段的斜截式直線方程

23：? compute yp，i//根據(jù)每一航段的斜截式方程計(jì)算出對應(yīng)航段內(nèi)觀測軌跡點(diǎn)的預(yù)測值

24：? compute ESRMS //根據(jù)式（5）分別求取在不同K值條件下的觀測軌跡點(diǎn)的分段均方根誤差值

25：? if （ESRMS，K-1>ESRMS，K） and （ESRMS，K+1>ESRMS，K）//尋找局部最小分段均方根誤差值所對應(yīng)的K值，作為自適應(yīng)K中心點(diǎn)聚類算法所確定的參數(shù)

26：?? get K//為防止K值過大，導(dǎo)致分段均方根誤差值無限趨近于0，造成過擬合現(xiàn)象，本文選擇具有局部最優(yōu)特征的K值

27：?? break

28：? end if

29： end for

30： save Om to list//將最終的聚類中心存儲到數(shù)據(jù)表中，作為船舶典型軌跡的軌跡特征點(diǎn)

船舶典型軌跡挖掘示意圖見圖3。

3 實(shí)驗(yàn)及分析

3.1 AIS數(shù)據(jù)選取

天津港是我國重要的交通、貿(mào)易樞紐，每天進(jìn)出港船舶較多，交通情況復(fù)雜多樣，對天津港主航道內(nèi)的船舶典型軌跡進(jìn)行研究具有重要意義。選取2019年7月1日至8月31日兩個月內(nèi)進(jìn)出天津港主航道的貨船AIS數(shù)據(jù)，通過數(shù)據(jù)清洗篩選出301艘貨船的9 553條AIS數(shù)據(jù)，以篩選出的數(shù)據(jù)為研究對象，對船舶典型軌跡挖掘算法進(jìn)行驗(yàn)證。將船舶噸級按照《海港總體設(shè)計(jì)規(guī)范》（JTS 165—2013）中船長與噸位的對應(yīng)關(guān)系進(jìn)行劃分，將船舶的進(jìn)出港情況按照航向進(jìn)行劃分[17]，得到不同噸級船舶的AIS數(shù)據(jù)，見表1。從表1可以看出，經(jīng)過壓縮后軌跡點(diǎn)數(shù)量大幅減少（壓縮率在58%左右）。

3.2 聚類參數(shù)的選擇

將進(jìn)出天津港主航道的貨船按照表1所示的方式對船舶噸級進(jìn)行劃分，運(yùn)用自適應(yīng)K中心點(diǎn)聚類算法分別計(jì)算K取2，3，…，20時(shí)的分段均方根誤差，從而自適應(yīng)地確定K值。進(jìn)港、出港貨船分段均方根誤差的變化趨勢分別見圖4和5。

從圖4和5可以看出，分段均方根誤差隨K值的增加總體呈下降趨勢，這是因?yàn)镵值越大，用于描述船舶軌跡的特征點(diǎn)越多，總體擬合結(jié)果越接近實(shí)際船舶軌跡。設(shè)分段均方根誤差取極小值時(shí)的K值為Kmin，當(dāng)KKmin時(shí)會出現(xiàn)過擬合的現(xiàn)象（如圖6b所示），導(dǎo)致擬合軌跡難以很好地反映真實(shí)情況。由于Kmin并不唯一，所以需要確定唯一極小值點(diǎn)，以相對較少的軌跡特征點(diǎn)較好地反映船舶軌跡特征，從而保留關(guān)鍵特征，減少冗余信息，提高后續(xù)研究的計(jì)算效率。以（3.5，10.0]萬噸級出港貨船為例，當(dāng)K值取11、15和18時(shí)，均出現(xiàn)了分段均方根誤差的極小值點(diǎn)，因此，在對此類船舶的聚類參數(shù)進(jìn)行選擇時(shí)，將取K=11（能使分段均方根誤差取極小值的最小K值）作為聚類參數(shù)的最優(yōu)值（如圖6c所示）。

為驗(yàn)證K=11為（3.5，10.0]萬噸級出港貨船典型軌跡的最佳聚類參數(shù)值，用式（3）分別計(jì)算在不同K值條件下聚類的絕對誤差均值，計(jì)算結(jié)果見表2。

由表2可知，當(dāng)K=11時(shí)聚類的絕對誤差均值最小，將該值作為聚類參數(shù)可以達(dá)到最佳的擬合效果。以此類推，在其他分類情況下自適應(yīng)K中心點(diǎn)聚類算法中的K值選擇情況見表3。

3.3 船舶典型軌跡挖掘結(jié)果

通過分別設(shè)置相應(yīng)的K值，運(yùn)用自適應(yīng)K中心點(diǎn)聚類算法挖掘不同噸級貨船進(jìn)出天津港的典型軌跡，并基于地理信息系統(tǒng)平臺ArcGIS進(jìn)行可視化展示（見圖7）。圖7中，黃色折線表示進(jìn)港軌跡，紅色折線表示出港軌跡。

挖掘結(jié)果可以從側(cè)面反映不同噸級的貨船在天津港主航道內(nèi)的通航情況及習(xí)慣航路。例如，進(jìn)港船舶典型軌跡在主航道北側(cè)，出港船舶典型軌跡在主航道南側(cè)，符合靠右行駛的規(guī)則。1萬噸級及以下的貨船在主航道南北兩側(cè)的小船航道行駛，3.5萬噸級及以下的貨船通常從錨地進(jìn)入航道，而3.5萬噸級以上的貨船大多從航道入口處進(jìn)入航道。通過將挖掘出的典型軌跡與實(shí)際的天津港航道情況對比可知，二者基本吻合，因此實(shí)驗(yàn)結(jié)果具有可信度。

為比較本文算法與基于軌跡段的聚類常用的DBSCAN算法的優(yōu)劣，將運(yùn)行時(shí)間和準(zhǔn)確率作為評價(jià)指標(biāo)，基于同一數(shù)據(jù)集對兩種算法分別進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境為：IntelCoreTMi5-3470 @ 3.20 GHz CPU，4 GB內(nèi)存，500 GB硬盤，Windows 10操作系統(tǒng)，Python 3.6編程環(huán)境。聚類的準(zhǔn)確率RI計(jì)算式為

RI=NTP+NTNNTP+NFP+NFN+NTN

（6）

式中：NTP表示被正確分類的正例個數(shù);NFP表示被錯分為正例的負(fù)例個數(shù);NFN表示被錯分為負(fù)例的正例個數(shù);NTN表示被正確分類的負(fù)例個數(shù)。RI值越大意味著聚類結(jié)果與真實(shí)情況越吻合，準(zhǔn)確率越高。兩種聚類算法的比較結(jié)果見表4。

由對比結(jié)果可知：自適應(yīng)K中心點(diǎn)聚類算法在準(zhǔn)確率上稍低于DBSCAN算法，其原因?yàn)閷④壽E段作為聚類對象使得聚類信息更為豐富，在描述船舶軌跡點(diǎn)特征時(shí)具有較好的表現(xiàn)性，但自適應(yīng)K中心點(diǎn)聚類算法的準(zhǔn)確率在90%以上，典型軌跡的挖掘結(jié)果可信;在運(yùn)行時(shí)間方面，自適應(yīng)K中心點(diǎn)聚類算法表現(xiàn)更優(yōu)，算法的運(yùn)行效率較高。

4 結(jié) 論

本文基于AIS數(shù)據(jù)，結(jié)合船舶的航速、航向特征實(shí)現(xiàn)船舶軌跡點(diǎn)的壓縮，提高了軌跡點(diǎn)數(shù)據(jù)的存儲效率;將軌跡點(diǎn)作為聚類對象，使得聚類對象簡單化，算法運(yùn)行效率得到提升;根據(jù)分段均方根誤差值改進(jìn)了K中心點(diǎn)聚類算法，提高了傳統(tǒng)算法的自適應(yīng)程度;最終選取天津港主航道貨船AIS數(shù)據(jù)，將船舶典型軌跡的挖掘結(jié)果基于地理信息系統(tǒng)平臺ArcGIS進(jìn)行可視化展示，結(jié)果表明，改進(jìn)的K中心點(diǎn)聚類算法可有效地對不同類別的船舶軌跡點(diǎn)進(jìn)行聚類，具有較好的自適應(yīng)性和準(zhǔn)確性。

研究結(jié)果可為實(shí)現(xiàn)船舶典型軌跡挖掘提供參考，為航線規(guī)劃、船舶交通行為特征挖掘等提供技術(shù)支持，具有借鑒意義。本文算法在準(zhǔn)確率等方面有待進(jìn)一步提高，運(yùn)用該結(jié)果進(jìn)一步實(shí)現(xiàn)船舶的異常行為檢測將是下一步的重點(diǎn)研究方向。

參考文獻(xiàn)：

[1]HAN X， ARMENAKIS C， JADIDI M. DBSCAN optimization for improving marine trajectory clustering and anomaly detection[J]. The International Archives of the Photogrammetry， Remote Sensing and Spatial Information Sciences， 2020， XLIII-B4-2020： 455-461. DOI： 10.5194/isprs-archives-XLIII-B4-2020-455-2020.

[2]MURRAY B， PERERA L P. Ship behavior prediction via trajectory extraction-based clustering for maritime situation awareness[J]. Journal of Ocean Engineering and Science， 2021. DOI： 10.1016/j.joes. 2021.03.001.

[3]唐國磊， 趙宇迪， 于菁菁， 等. 基于AIS數(shù)據(jù)的集裝箱船舶到港時(shí)間預(yù)測研究[J/OL]. 重慶交通大學(xué)學(xué)報(bào)（自然科學(xué)版）： 1-5[2021-05-09]. http：//kns.cnki.net/kcms/detail/50.1190.U.20181116.0958.008.html.

[4]姜大鵬. 基于船舶交通流特征的通航寬度計(jì)算及其應(yīng)用[D]. 大連： 大連海事大學(xué)， 2020.

[5]宋鵬. 基于C-OPTICS算法的船舶軌跡聚類與應(yīng)用[D]. 大連： 大連海事大學(xué)， 2017.

[6]張春瑋， 馬杰， 牛元淼， 等. 基于行為特征相似度的船舶軌跡聚類方法[J]. 武漢理工大學(xué)學(xué)報(bào)（交通科學(xué)與工程版）， 2019， 43（3）： 517-521. DOI： 10.3963/j.issn.2095-3844.2019.03.028.

[7]LI Huanhuan， LIU Jingxian， LIU R W， et al. A dimensionality reduction-based multi-step clustering method for robust vessel trajectory analysis[J]. Sensors， 2017， 17： 1792-1817. DOI： 10.3390/s17081792.

[8]牟軍敏， 陳鵬飛， 賀益雄， 等. 船舶AIS軌跡快速自適應(yīng)譜聚類算法[J]. 哈爾濱工程大學(xué)學(xué)報(bào)， 2018， 39（3）： 428-432. DOI： 10.11990/jheu.201609033.

[9]曹妍妍， 崔志明， 吳健， 等. 一種改進(jìn)Hausdorff距離和譜聚類的車輛軌跡模式學(xué)習(xí)方法[J]. 計(jì)算機(jī)應(yīng)用與軟件， 2012， 29（5）： 38-40. DOI： 10.3969/j.issn.1000-386X.2012.05.011.

[10]LEE J-G， HAN Jiawei， WHANG K-Y. Trajectory clustering： a partition-and-group framework[C]//Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. New York： Association for Computing Machinery， 2007： 593-604. DOI： 10.1145/1247480.1247546.

[11]江玉玲， 熊振南， 唐基宏. 基于軌跡段DBSCAN的船舶軌跡聚類算法[J]. 中國航海， 2019， 42（3）： 1-5.

[12]LIU Bo， DE SOUZA E N， SYDOW M， et al. Knowledge-based clustering of ship trajectories using density-based approach[C]//2014 IEEE International Conference on Big Data. IEEE， 2014： 603-608. DOI： 10.1109/BigData.2014.7004281.

[13]王莉莉， 彭勃. 航跡點(diǎn)特征的時(shí)間窗分割算法的航跡聚類[J]. 空軍工程大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2018， 19（3）： 19-23. DOI： 10.3969/j.issn.1009-3516.2018.03.004.

[14]王森杰， 何正偉. 分層建模的船舶軌跡快速聚類算法[J]. 武漢理工大學(xué)學(xué)報(bào)（交通科學(xué)與工程版）， 2021， 45（3）： 596-601. DOI： 10.3963/j.issn.2095-3844.2021.03.036.

[15]唐國磊， 趙宇迪， 宋向群， 等. 基于AIS數(shù)據(jù)的集裝箱船舶典型運(yùn)動軌跡研究[J]. 港工技術(shù)， 2018， 55（6）： 6-9. DOI： 10.16403/j.cnki.ggjs20180602.

[16]ZHEN Rong， JIN Yongxing， HU Qinyou， et al. Maritime anomaly detection within coastal waters based on vessel trajectory clustering and Nave Bayes classifier[J]. Journal of Navigation， 2017， 70（3）： 1-23. DOI： 10.1017/S0373463316000850.

[17]陳向. 復(fù)式航道條件下的港口船舶調(diào)度優(yōu)化[D]. 大連： 大連海事大學(xué)， 2017.

（編輯 賈裙平）