多算法結(jié)合的船舶交通流框架提取

王震 李偉峰 高邈

摘要：為提高船舶進(jìn)出交通流密集區(qū)域的安全性、解決數(shù)據(jù)挖掘不充分的問題，基于AIS數(shù)據(jù)，將多種算法相結(jié)合，提出一種多元化的船舶交通流框架提取方法。利用Douglas-Peucker壓縮算法和航跡交會算法分別提取交通流中的船舶轉(zhuǎn)向點(diǎn)和航跡交會點(diǎn)。利用密度聚類算法對包括船位點(diǎn)在內(nèi)的3種特征點(diǎn)進(jìn)行數(shù)據(jù)挖掘，提取出更有代表性的特征點(diǎn)。將3種特征點(diǎn)進(jìn)行加權(quán)融合，得到新的多元特征點(diǎn)，以點(diǎn)的大小表示其重要程度，最終生成某水域的船舶交通流框架。實(shí)驗(yàn)結(jié)果表明，通過以上方法能夠獲得老鐵山水道附近水域船舶交通流框架。該框架融合了多種航跡特征點(diǎn)，能夠顯示附近水域的重要航跡分布，充分體現(xiàn)船舶交通流的總體態(tài)勢和密集區(qū)域;該框架從統(tǒng)計(jì)學(xué)角度凝結(jié)了該水域船舶行駛的習(xí)慣航線，這些航線具有較好的適航度，既可用于航路規(guī)劃，還能為海事部門選取推薦航道提供參考。

關(guān)鍵詞：

數(shù)據(jù)挖掘; 船舶交通流; 特征點(diǎn); 船舶自動(dòng)識別系統(tǒng)（AIS）

中圖分類號：? U692.37

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

收稿日期： 2020-09-07

修回日期： 2020-12-16

基金項(xiàng)目：

中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金（3132020134，3132020139）

作者簡介：

王震（1996—），男，山東聊城人，碩士研究生，研究方向?yàn)锳IS大數(shù)據(jù)挖掘，（E-mail）1506216436@qq.com;

李偉峰（1983—），男，山東菏澤人，副教授，碩士，研究方向?yàn)榇爸悄鼙芘?，（E-mail）sddmlwf@163.com

Framework extraction of ship traffic flow with

multi-algorithm combination

WANG Zhen， LI Weifeng， GAO Miao

（

Navigation College， Dalian Maritime University， Dalian 116026， Liaoning， China）

Abstract：

In order to improve the safety of ships entering and leaving traffic-intensive waters and to solve the problem of insufficient data mining， a diversified method for extracting the framework of ship traffic flow is proposed based on AIS data and with the combination of multiple algorithms. The Douglas-Peucker compression algorithm and the trajectory crossing algorithm are used to extract the ship turning points and the trajectory crossing points in the traffic flow. The density clustering algorithm is used to conduct data mining on the three types of characteristic points including the ship position points， so as to extract more representative characteristic points. The three types of characteristic points are weighted and fused to obtain new multivariate characteristic points， and the framework of ship traffic flow in a certain waters is generated， in which the size of a point represents the importance. The experimental results show that the framework of ship traffic flow in the local waters of Laotieshan channel can be obtained through the above method. The framework integrates a variety of trajectory characteristic points， which can display the distribution of important trajectories nearby and fully reflects the overall situation and dense areas of ship traffic flow. It also condenses the customary routes of ships in the waters statistically， and the customary routes have good seaworthiness and can be used for route planning and reference for maritime departments to select recommended channels.

Key words：

data mining; ship traffic flow; characteristic point; automatic identification system （AIS）

0 引 言

隨著船舶自動(dòng)識別系統(tǒng)（automatic identification system，AIS）的廣泛使用，海事系統(tǒng)及船公司接收了大量包括船舶航跡及海上交通環(huán)境等多種信息在內(nèi)的AIS數(shù)據(jù)。為獲取AIS數(shù)據(jù)中蘊(yùn)藏的船舶交通流和航行環(huán)境的特征及規(guī)律，運(yùn)用大數(shù)據(jù)算法對其進(jìn)行數(shù)據(jù)挖掘已成為一個(gè)重要研究方向。近年來，國內(nèi)外專家學(xué)者通過各種方法對船舶交通流進(jìn)行深入研究，并取得了一定的成果。然而，船舶航跡分布復(fù)雜、交通流特征多種多樣，當(dāng)前對AIS數(shù)據(jù)的挖掘仍然不夠全面;AIS數(shù)據(jù)挖掘結(jié)果的可視化效果仍不夠理想，不能更直觀地體現(xiàn)船舶交通流的航跡特征和宏觀態(tài)勢。本文針對以上問題進(jìn)行研究。

LV[1]設(shè)計(jì)了大型AIS數(shù)據(jù)挖掘平臺，并利用大數(shù)據(jù)對船舶航跡進(jìn)行分析，驗(yàn)證了運(yùn)用大數(shù)據(jù)技術(shù)對AIS數(shù)據(jù)進(jìn)行挖掘的可行性。聚類是數(shù)據(jù)挖掘中必不可少的一環(huán)，魏照坤[2]通過基于軌跡結(jié)構(gòu)距離的聚類方法，實(shí)現(xiàn)了對船舶軌跡的聚類;HAN等[3]利用基于軌跡密度的聚類方法，得到了不同的航跡矢量簇;郭乃琨等[4]討論了數(shù)據(jù)挖掘的關(guān)鍵技術(shù)與基本流程，并表明利用傳統(tǒng)的聚類分析方法無法達(dá)到理想的聚類效果。張樹凱等[5]利用Douglas-Peucker壓縮算法，設(shè)定不同閾值提取關(guān)鍵特征點(diǎn)對AIS航跡數(shù)據(jù)進(jìn)行壓縮，該算法的穩(wěn)定性和處理效率都較高。劉敦偉[6]基于經(jīng)典的Douglas-Peucker壓縮算法，結(jié)合船舶航線設(shè)計(jì)的偏航極限和船舶領(lǐng)域知識壓縮閾值，提出基于速度和航向約束的船舶軌跡數(shù)據(jù)壓縮方法，該方法能夠挖掘曲率和速度變化率較大的點(diǎn)，提高軌跡數(shù)據(jù)的利用率和價(jià)值。高邈等[7-8]利用改進(jìn)的滑動(dòng)窗口（sliding window）算法提取關(guān)鍵特征點(diǎn)，在降低壓縮風(fēng)險(xiǎn)的同時(shí)大幅提高了壓縮效率。劉虎等[9]在軌跡聚類的基礎(chǔ)上，運(yùn)用核密度估計(jì)（kernel density estimation，KDE）推算聚類航跡的概率密度，自動(dòng)識別交通流區(qū)域，進(jìn)行精準(zhǔn)數(shù)據(jù)挖掘。與上述提取船舶交通流的主要特征不同，RONG等[10]使用多種軌跡壓縮和聚類算法，對船舶航行行為的異常特征進(jìn)行數(shù)據(jù)挖掘：在觀察到船舶航行行為發(fā)生重大變化（例如航向變化）的路線上識別相關(guān)航路點(diǎn)，根據(jù)軌跡的航向分布和速度分布，可以概率性地表征沿著特定路線航行的一類船舶的典型行為。LEI[11]將沖突軌跡視為接近碰撞的情況進(jìn)行分析，通過開發(fā)出的CCT Discovery框架，從大量的AIS數(shù)據(jù)中提取沖突軌跡數(shù)據(jù)，用于避碰行為建模和海上交通管理的重點(diǎn)區(qū)域監(jiān)控。ZHOU等[12]從AIS數(shù)據(jù)中挖掘所有的船舶位置、速度、航向等多種行為屬性，對船舶行為進(jìn)行聚類并確定聚類特征，并根據(jù)特征將船舶分類為行為集群，但并未進(jìn)一步對船舶交通流的多種特征進(jìn)行挖掘和分析。當(dāng)前對船舶軌跡的研究中，通過數(shù)據(jù)挖掘得到的船舶交通流特征相對單一，不能充分體現(xiàn)交通流的復(fù)雜特征，而且其可視化效果也有待提高。

針對當(dāng)前研究的不足，本文綜合考慮船位點(diǎn)、船舶轉(zhuǎn)向點(diǎn)和航跡交會點(diǎn)（下文分別簡稱轉(zhuǎn)向點(diǎn)和交會點(diǎn)），結(jié)合船舶運(yùn)動(dòng)特性，運(yùn)用密度聚類算法、Douglas-Peucker壓縮算法和航跡交會算法，提出一種多算法聯(lián)合的船舶交通流框架提取方法。該方法吸取了諸多算法的優(yōu)點(diǎn)，最終提取出實(shí)驗(yàn)水域的船舶交通流框架，并將交通流中的多種重要特征可視化，具有重要的理論意義和應(yīng)用價(jià)值。

1 多算法聯(lián)合的船舶交通流框架模型

1.1 密度聚類算法

聚類指將數(shù)據(jù)對象分成多個(gè)類或簇，使得同一簇中的對象具有較高的相似度，而不同簇中的對象差別較大。傳統(tǒng)的密度聚類算法是在一個(gè)給定的區(qū)域內(nèi)使數(shù)據(jù)點(diǎn)的數(shù)量不小于設(shè)定值，常用的有DBSCAN、OPTICS以及譜聚類等[13]。

本文的密度聚類算法以各數(shù)據(jù)點(diǎn)為中心，計(jì)算其鄰域內(nèi)的點(diǎn)數(shù)，設(shè)定不同閾值控制各點(diǎn)鄰域大小。在各點(diǎn)鄰域所共同構(gòu)成的局部區(qū)域內(nèi)，若某點(diǎn)鄰域內(nèi)包含的點(diǎn)最多，則該點(diǎn)為密度吸引點(diǎn)（以下簡稱密度點(diǎn)），其將吸收鄰域內(nèi)所有數(shù)據(jù)點(diǎn)，完成一次聚類。隨著閾值不斷增大，交通流中各航跡線通過共有密度點(diǎn)聯(lián)系起來，組成該水域交通流的密集點(diǎn)網(wǎng)絡(luò)[14]。

密度聚類流程見圖1。通過預(yù)處理AIS數(shù)據(jù)，獲得各航跡線上數(shù)據(jù)點(diǎn)的坐標(biāo)，

如點(diǎn)Pi。設(shè)兩點(diǎn)之間的距離為d，鄰域閾值為ε，若d≤ε，則這兩點(diǎn)屬于同一類。以Pi為圓心，ε為半徑，統(tǒng)計(jì)該（圓形）鄰域內(nèi)的點(diǎn)，得到包含u個(gè)點(diǎn)的點(diǎn)集A;統(tǒng)計(jì)A中各點(diǎn)（除點(diǎn)Pi外）鄰域內(nèi)的點(diǎn)數(shù)，記最大值為v，v對應(yīng)的點(diǎn)為Qm。若u>v，則說明在點(diǎn)Pi附近，點(diǎn)Pi鄰域內(nèi)的密度最大，點(diǎn)Pi為該區(qū)域的密度點(diǎn)，保存點(diǎn)Pi;若u≤v，則說明在點(diǎn)Pi附近，點(diǎn)Qm鄰域內(nèi)的密度最大，點(diǎn)Qm為該區(qū)域的密度點(diǎn)，則包含點(diǎn)Pi在內(nèi)的Qm鄰域內(nèi)的所有數(shù)據(jù)點(diǎn)都將被聚類到點(diǎn)Qm，保存點(diǎn)Qm。然后依次遍歷所有數(shù)據(jù)點(diǎn)，即完成一次聚類。

以上一次聚類得到的密度點(diǎn)為基礎(chǔ)，增大閾值，再進(jìn)行聚類;隨著迭代次數(shù)的增加，被聚類的數(shù)據(jù)點(diǎn)越來越多，密度點(diǎn)逐漸成為全局密度的局部最大點(diǎn);當(dāng)取到最終閾值時(shí)，密度聚類完成。密度聚類示意圖見圖2。用密度點(diǎn)吸收的點(diǎn)數(shù)表示其權(quán)重，點(diǎn)數(shù)越多，權(quán)重就越大，該點(diǎn)附近的點(diǎn)密度就越大。為直觀顯示密度點(diǎn)權(quán)重大小，權(quán)重越大的密度點(diǎn)在圖中顯示的尺寸越大。

1.2 Douglas-Peucker壓縮算法

1973年，Douglas 等提出一種簡化二維曲線的算法，其核心思想是從構(gòu)成曲線的點(diǎn)集中提取出能反映曲線總體和局部形態(tài)主要特征的另一個(gè)點(diǎn)集。該算法步驟如下：將一段航跡線上首

點(diǎn)P1與尾點(diǎn)P2之間的連線稱為基線，依次計(jì)算這段航跡線上各點(diǎn)到基線的距離，并找出最大距離D對應(yīng)的點(diǎn)P3。設(shè)定閾值δ，若D≤δ，則表示該段航跡線向兩舷偏離的距離小于D，即該段航跡線沒有明顯轉(zhuǎn)折，則用基線代替原航跡線，只保留P1、P2兩點(diǎn)即可;若D>δ，則將最大距離D對應(yīng)的點(diǎn)P3作為分裂點(diǎn)（轉(zhuǎn)向點(diǎn)），并分別與初始點(diǎn)P1、P2連接，得到兩組新的首點(diǎn)、尾點(diǎn)和基線。依次遞歸選取分裂點(diǎn)和分段航跡線，直到整條航跡線上不再出現(xiàn)新的分裂點(diǎn)[5]。

圖3為Douglas-Peucker壓縮示意圖。

設(shè)點(diǎn)P1、P2和P3的坐標(biāo)分別為（x1，y1）、（x2，y2）和（x3，y3），則有D=（y2-y1）x3+（x1-x2）y3+x2y1-x1y2（y2-y1）2+（x2-x1）2

1.3 航跡交會算法

船舶航跡密集交會處通常是海上交通情況比較復(fù)雜的地方，在這一區(qū)域，各船航向、航速往往不同，通航情況復(fù)雜，因此交會點(diǎn)也是船舶交通流的重要特征點(diǎn)之一。

航跡交會算法原理：取某條航跡線上相

鄰兩點(diǎn)Mi和Mi+1，取另一條航跡線上相鄰兩點(diǎn)Nj和Nj+1，連接Mi、Mi+1得線段MiMi+1，連接Nj、Nj+1得線段NjNj+1，分別設(shè)這兩條線段的斜率為k1、k2。若k1、k2都不存在，則兩直線豎直平行;若k1=k2=0，則兩直線水平平行。兩直線平行，不存在交點(diǎn)。若k1≠0或k2≠0，則在二維平面內(nèi)兩直線必相交，此時(shí)先求得兩直線交點(diǎn)E，再判斷該交點(diǎn)是否在線段MiMi+1和NjNj+1上，若在，則點(diǎn)E即為所求的交會點(diǎn)。對于每條航跡線上相鄰兩點(diǎn)之間的線段，均按上述方法判斷其與其余所有航跡線有無交點(diǎn)，逐個(gè)遍歷所有航跡線，即可得到該組AIS數(shù)據(jù)的所有交會點(diǎn)。圖4為交會點(diǎn)提取示意圖。

設(shè)點(diǎn)Mi、Mi+1、Nj、Nj+1和E的坐標(biāo)分別為（x6，y6）、（x7，y7）、（x8，y8）、（x9，y9）和（x10，y10），則相關(guān)公式如下：

k1=y7-y6x7-x6， k2=y9-y8x9-x8

x10=（x7-x6）（x8y9-x9y8）-（x9-x8）（x6y7-x7y6）（y6-y7）（x9-x8）-（y8-y9）（x7-x6）y10=（y8-y9）（x6y7-x7y6）-（y6-y7）（x8y9-x9y8）（y6-y7）（x9-x8）-（y8-y9）（x7-x6）k1≠0， k2≠0

x10=（（x8-x9）y6+x9y8-x8y9）/（y8-y9）

y10=y6k1=0， k2≠0

x10=（（x6-x7）y8+x7y6-x6y7）/（y8-y9）

y10=y8k1≠0， k2=0

x10=x8， y10=y6k1=0， k2不存在

x10=x8y10=（（y7-y6）x8+x7y6-x6y7）/（y7-y6）

k1≠0， k2不存在

x10=x6， y10=y8k1不存在， k2=0

x10=x6y10=（（y9-y8）x6+x9y8-x8y9）/（x9-x8）

k1不存在， k2≠0

1.4 加權(quán)融合算法

通過Douglas-Peucker壓縮算法得到的轉(zhuǎn)向點(diǎn)、通過航跡交會算法得到的交會點(diǎn)和原有的船位點(diǎn)分別為船舶交通流的3種特征點(diǎn)，對這3種特征點(diǎn)分別進(jìn)行密度聚類，得到相應(yīng)的密度點(diǎn)，然后將這3種特征密度點(diǎn)集中顯示。由于轉(zhuǎn)向點(diǎn)和交會點(diǎn)是基于算法從船位點(diǎn)中提取出來的，其數(shù)據(jù)量遠(yuǎn)小于船位點(diǎn)的初始數(shù)據(jù)量，若直接按權(quán)重顯示，則轉(zhuǎn)向點(diǎn)和交會點(diǎn)的聚類密度相較于船位點(diǎn)的聚類密度幾乎可以忽略不計(jì)，這違背了本文的初衷;此外，由于最終密度點(diǎn)的權(quán)重很大，直接顯示可能會使各點(diǎn)難以區(qū)分，影響視覺效果。鑒于以上原因，對不同類型特征點(diǎn)進(jìn)行加權(quán)顯示。具體來說，就是分別成比例地放大或縮小3種特征點(diǎn)的權(quán)重值，放大或縮小比例的設(shè)置需要考慮原始船位點(diǎn)的數(shù)據(jù)量、特征點(diǎn)在交通流框架中的重要程度和最終的可視化效果。例如：10 000個(gè)船位點(diǎn)經(jīng)過Douglas-Peucker壓縮算法得到200個(gè)轉(zhuǎn)向點(diǎn)，其整體權(quán)重值相當(dāng)于縮小為原來的1/50，考慮本文的交通流框架是以船位密度點(diǎn)為主體的，轉(zhuǎn)向點(diǎn)權(quán)重的放大倍數(shù)可先取50的60%～80%，如30，然后統(tǒng)一調(diào)整使可視化效果最佳。這樣充分考慮了3種特征點(diǎn)的影響，顯示了不同類型特征點(diǎn)之間的位置關(guān)系，可更直觀地判斷船舶交通流的整體航跡特征和宏觀態(tài)勢，達(dá)到更好的視覺效果，如圖5所示。

對交通流網(wǎng)絡(luò)中位置相近的3種特征點(diǎn)進(jìn)行加權(quán)融合（見圖6），提取出4種新的融合特征點(diǎn)，即“船位+轉(zhuǎn)向+交會點(diǎn)”、“船位+轉(zhuǎn)向點(diǎn)”、“船位+交會點(diǎn)”和“轉(zhuǎn)向+交會點(diǎn)”。它們能夠表現(xiàn)該點(diǎn)附近的多種航跡特征，與原有的3種特征點(diǎn)一起共同作為該交通流框架的重要節(jié)點(diǎn)。

設(shè)共有ω個(gè)被融合點(diǎn)，融合后點(diǎn)的總權(quán)重為W;被融合點(diǎn)坐標(biāo)為（xτ，yτ），權(quán)重為wτ，τ=1，2，…，ω。第τ個(gè)被融合點(diǎn)的權(quán)重占比rτ=wτ/W，各點(diǎn)加權(quán)可得融合點(diǎn)的坐標(biāo)（X，Y）。

X=ωτ=1（xτrτ）， Y=ωτ=1（yτrτ）

2 實(shí)例驗(yàn)證與分析

選定老鐵山水道附近水域（38.321 7～38.747 1°N，120.431 9～121.431 9°E），從AIS數(shù)據(jù)中提取2017年3月11日至3月14日過往船舶的動(dòng)態(tài)信息，并對其進(jìn)行解碼，共得到126 408個(gè)船位點(diǎn)數(shù)據(jù)。對解碼的AIS信息進(jìn)行預(yù)處理，主要包括數(shù)據(jù)清理和數(shù)據(jù)轉(zhuǎn)換。數(shù)據(jù)清理主要是為了將數(shù)據(jù)挖掘過程中的異常點(diǎn)、錯(cuò)誤信息以及無用信息去除;數(shù)據(jù)轉(zhuǎn)換是為了修正原始數(shù)據(jù)以更有利于數(shù)據(jù)挖掘。對不同航行狀態(tài)船舶的AIS數(shù)據(jù)進(jìn)行時(shí)間等距差分，統(tǒng)一初始時(shí)間和船載信息更新時(shí)間間隔，以及等比例轉(zhuǎn)換各船舶信息的時(shí)間戳和船位，在時(shí)空上保證AIS船位點(diǎn)數(shù)據(jù)的一致性。經(jīng)過數(shù)據(jù)預(yù)處理，將212條航跡線上共計(jì)126 193個(gè)船位點(diǎn)數(shù)據(jù)作為實(shí)驗(yàn)對象，將其經(jīng)緯度坐標(biāo)轉(zhuǎn)換為墨卡托坐標(biāo)，以便在海圖上顯示。整體實(shí)現(xiàn)流程見圖7。

2.1 船位點(diǎn)密度聚類

為使最終聚類得到的船位點(diǎn)坐標(biāo)更加準(zhǔn)確，采用逐漸增大閾值的方法，以上一層的輸出數(shù)據(jù)作為

下一層的輸入數(shù)據(jù)，依次聚類。隨著閾值的不斷增

大，等差增大閾值的聚類效果會逐漸變差，需逐漸增大閾值差：閾值最初取300， 600， …， 1 800 m，每次增加300 m;而后取2 400， 3 000 m，每次增加600 m;最后取4 200， 5 400 m，每次增加1 200 m。聚類過程中，不同閾值下的船位點(diǎn)數(shù)和壓縮率如表1所示，這里的壓縮率是根據(jù)上一層數(shù)據(jù)（而非初始數(shù)據(jù)）計(jì)算得出的。

從表1可以看出，在閾值差相等的情況下，除首次壓縮外，其他各次的壓縮率隨閥值增大逐漸減小，至閾值取1 800 m和3 000 m時(shí)，對上一層的壓縮率已不足20%，因此可增大閾值差以獲得更好的聚類效果。截止到最終閾值5 400 m時(shí)，對初始數(shù)據(jù)的壓縮率已經(jīng)達(dá)到99%以上。

由于密度聚類不限于單條航跡線，聚類后同一船位點(diǎn)可能位于多條航跡線上，壓縮后的船位點(diǎn)數(shù)為各條航跡線上船位點(diǎn)數(shù)之和，因此最終1 229個(gè)船位點(diǎn)會包含許多點(diǎn)的多次計(jì)量，實(shí)際船位點(diǎn)數(shù)遠(yuǎn)小于此。此外，聚類完成后，刪除船位點(diǎn)網(wǎng)絡(luò)中權(quán)重小于600的低密度點(diǎn)，最終得到33個(gè)船位點(diǎn)。圖8為部分不同閾值下船位點(diǎn)密度聚類效果圖，圖8f為在圖8e的基礎(chǔ)上刪掉權(quán)重小于600的船位點(diǎn)所得的最終效果圖。

從圖8可以看出：聚類后的船位點(diǎn)幾乎都在交通流最密集的區(qū)域，而且該船位點(diǎn)網(wǎng)絡(luò)兩頭寬、中間窄，很好地反映了航跡線的實(shí)際分布情況;在老鐵山水道及其進(jìn)出口附近，密度點(diǎn)大且分布較為密集，表示水道附近船位點(diǎn)密度大且較為密集;船位點(diǎn)網(wǎng)絡(luò)并未延伸到右上水域的一些航跡線上，表示右上水域的船位點(diǎn)密度小，這與航跡線在老鐵山水道較為密集而在東北方向較為稀疏的實(shí)際情況相符;在老鐵山水道的相向交通流中，水道右側(cè)密度點(diǎn)大而密集，水道左側(cè)密度點(diǎn)小而稀疏，這與當(dāng)時(shí)老鐵山水道航跡線右側(cè)多、左側(cè)少的實(shí)際情況一致。

2.2 轉(zhuǎn)向點(diǎn)的提取及聚類

為驗(yàn)證Douglas-Peucker壓縮算法的有效性，對212條航跡線上的126 193個(gè)船位點(diǎn)進(jìn)行Douglas-Peucker壓縮，閾值為120 m，壓縮后轉(zhuǎn)向點(diǎn)數(shù)減為1 979（壓縮率達(dá)98.43%）。壓縮后的數(shù)據(jù)量雖然大幅減少，但很好地保留了原始航跡的特征，可以清楚地看出船舶交通流的宏觀態(tài)勢，見圖9。

對壓縮后獲得的轉(zhuǎn)向點(diǎn)進(jìn)行密度聚類，同樣采用閾值逐漸增大的方法。不同閾值下的轉(zhuǎn)向點(diǎn)數(shù)和壓縮率見表2。由表2可知，每經(jīng)過一次聚類，轉(zhuǎn)向點(diǎn)數(shù)就減少一次，閾值取4 200 m和4 800 m時(shí)轉(zhuǎn)向點(diǎn)數(shù)已差別不大。

與船位點(diǎn)密度聚類一樣，表2中所示的轉(zhuǎn)向點(diǎn)數(shù)為各條航跡線上轉(zhuǎn)向點(diǎn)數(shù)之和，存在多條航跡線上的轉(zhuǎn)向點(diǎn)被重復(fù)計(jì)數(shù)問題，閾值取4 800 m時(shí)的實(shí)際轉(zhuǎn)向點(diǎn)數(shù)遠(yuǎn)遠(yuǎn)小于930，刪除權(quán)重小于30的轉(zhuǎn)向點(diǎn)，最終得到的轉(zhuǎn)向點(diǎn)數(shù)為24。圖10為部分不同閾值下的轉(zhuǎn)向點(diǎn)密度聚類效果圖，圖10e為在圖10d的基礎(chǔ)上刪掉權(quán)重小于30的轉(zhuǎn)向點(diǎn)所得的最終效果圖。

從圖10可以看出，聚類后的轉(zhuǎn)向點(diǎn)網(wǎng)絡(luò)與船位點(diǎn)網(wǎng)絡(luò)有很大不同：在航跡線最為密集的老鐵山水道內(nèi)，轉(zhuǎn)向點(diǎn)很少且密度較小;在水道進(jìn)出口附近，有許多密度較大的轉(zhuǎn)向點(diǎn)。實(shí)際航行中，船舶在水道內(nèi)大多定向行駛，航跡偏轉(zhuǎn)很小;而在水道進(jìn)出口附近，船舶進(jìn)出水道需頻繁動(dòng)舵，因此航跡線轉(zhuǎn)折較多，與實(shí)驗(yàn)數(shù)據(jù)相符。在圖10中左上區(qū)域航跡線很多，但大多比較平直或整體彎曲度較低，轉(zhuǎn)向點(diǎn)相對較少，最終導(dǎo)致該水域在轉(zhuǎn)向點(diǎn)網(wǎng)絡(luò)中的轉(zhuǎn)向點(diǎn)少且密度小;圖10e中C1、C2兩點(diǎn)不在航跡線密集的區(qū)域，但其附近航跡線轉(zhuǎn)折頗多，轉(zhuǎn)向點(diǎn)并不少，最終成為轉(zhuǎn)向點(diǎn)網(wǎng)絡(luò)中相對突出、孤立的兩點(diǎn)。

2.3 交會點(diǎn)的提取及聚類

根據(jù)航跡交會算法，對212條航跡線上的126 193個(gè)船位點(diǎn)進(jìn)行編程計(jì)算，最終得到5 200個(gè)交會點(diǎn)，見圖11。

從圖11可以看出，在老鐵山水道及其進(jìn)出口附近交會點(diǎn)密集。圖11中左上區(qū)域（進(jìn)出口鄰近的警戒區(qū)）和右下區(qū)域交會點(diǎn)也很多，與右下區(qū)域相比左上區(qū)域交會點(diǎn)較少且分布比較零散，與航跡線進(jìn)水道時(shí)匯集、出水道后發(fā)散的實(shí)際情況一致。對提取的交會點(diǎn)進(jìn)行密度聚類，閾值逐漸增大，閾值差也逐漸增大（依次取300、600、900、1 200 m）。不同閾值下的交會點(diǎn)數(shù)和壓縮率見表3。

與船位點(diǎn)和轉(zhuǎn)向點(diǎn)不同，交會點(diǎn)是散點(diǎn)，并未引入航跡線中，因此表3中壓縮后的交會點(diǎn)數(shù)和壓縮率均為實(shí)際值。為得到最有代表性的交會點(diǎn)，最終的壓縮率很高。在閾值逐漸增大的過程中，最初采用300 m的閾值差，在閾值取1 800 m與2 100 m時(shí)其整體壓縮率很相近，因此加大閾值差至600 m。閾值越大，數(shù)據(jù)量減少率越低。閾值取3 000 m后改用900 m閾值差，閾值取4 800 m后改用1 200 m閾值差，閾值差改變的區(qū)間內(nèi)往往存在數(shù)據(jù)階躍。

圖12為不同閾值下的交會點(diǎn)密度聚類效果圖，圖12f為在圖12e的基礎(chǔ)上刪掉權(quán)重小于50的交會點(diǎn)所得的最終效果圖。

2.4 加權(quán)融合提取船舶交通流框架

經(jīng)數(shù)據(jù)清洗后共獲得126 193個(gè)船位點(diǎn)數(shù)據(jù)，利用密度聚類算法、Douglas-Peucker壓縮算法和航跡交

會算法等對該AIS數(shù)據(jù)進(jìn)行處理，獲取密度聚類后的3種交通流特征點(diǎn)。關(guān)于特征點(diǎn)聚類過程中最終閾值的選取，主要考慮以下兩個(gè)方面。一是聚類效果：隨著閾值的不斷增大，船位點(diǎn)數(shù)的下降幅度會越來越小，閾值取到4 800 m和6 000 m時(shí)，交通流框架的主要節(jié)點(diǎn)已基本形成，繼續(xù)加大閾值后所聚類的點(diǎn)基本是主框架之外的散點(diǎn)，這些點(diǎn)絕大部分屬于之后會被刪除的低密度點(diǎn)，其對主框架的影響基本可以忽略不計(jì)。例如在對交會點(diǎn)進(jìn)行聚類時(shí)，當(dāng)閾值取6 000 m時(shí)，刪除低密度點(diǎn)后剩余點(diǎn)數(shù)為16，該數(shù)值一直保持不變，直到閾值取8 000 m時(shí)出現(xiàn)階躍。閾值的過大和數(shù)值的階躍，會導(dǎo)致原有的交通流框架發(fā)生嚴(yán)重變形，不符合最初的設(shè)想，因此閾值取到6 000 m已完全符合實(shí)驗(yàn)需要;轉(zhuǎn)向點(diǎn)的情況也與此類似，閾值取到4 800 m即可。二是實(shí)際情況需要：對于特征密度點(diǎn)的聚類，除考慮交通流框架外，還要考慮具體情況。實(shí)驗(yàn)數(shù)據(jù)中兩股反向的交通流在老鐵山水道聚集進(jìn)行分道通航，當(dāng)閾值取到6 000 m以上時(shí)，南下交通流的個(gè)別密度點(diǎn)由于權(quán)重相對較小，會被聚類到北上一側(cè)，這顯然不符合實(shí)際航行情況，必須保證通航分道的兩側(cè)都有對應(yīng)的密度點(diǎn)保留，因此閾值取到5 400 m即可。關(guān)于刪除較小密度點(diǎn)的權(quán)重閾值選擇，以最終保留的特征點(diǎn)不過多為原則：若船位點(diǎn)數(shù)多且權(quán)重大，則權(quán)重閾值選用其最大點(diǎn)權(quán)重的5%左右;若轉(zhuǎn)向點(diǎn)和交會點(diǎn)的數(shù)量和權(quán)重都相對較小，則在選取權(quán)重閾值時(shí)要保留其數(shù)據(jù)總量的30%～40%。具體地，取船位點(diǎn)的最大聚類閾值為5 400 m，聚類完成后刪除權(quán)重600以下的點(diǎn);對船舶軌跡進(jìn)行Douglas-Peucker壓縮，閾值取600 m，得到1 979個(gè)轉(zhuǎn)向點(diǎn)，再經(jīng)過密度聚類，取最大聚類閾值為4 800 m，聚類完成后刪除權(quán)重30以下的點(diǎn);船舶軌跡經(jīng)航跡交會算法提取到5 200個(gè)交會點(diǎn)，再經(jīng)過密度聚類，取最大聚類閾值為6 000 m，聚類完成后刪除權(quán)重50以下的散點(diǎn)。權(quán)重調(diào)整后的結(jié)果見表4和圖13。

在以上實(shí)驗(yàn)數(shù)據(jù)的基礎(chǔ)上，利用加權(quán)融合算法進(jìn)行計(jì)算。首先以閾值4 200 m對船位點(diǎn)進(jìn)行加權(quán)融合，以防后續(xù)出現(xiàn)同一轉(zhuǎn)向點(diǎn)或交會點(diǎn)被融合多次的情況。然后以船位點(diǎn)為基礎(chǔ)，融合其鄰域內(nèi)的轉(zhuǎn)向點(diǎn)和交會點(diǎn)，分別取閾值4 200 m和3 000 m，進(jìn)而得到“船位+轉(zhuǎn)向點(diǎn)”“船位+交會點(diǎn)”“船位+轉(zhuǎn)向+交會點(diǎn)”等3種新的特征點(diǎn)的數(shù)量。再以剩余轉(zhuǎn)向點(diǎn)為基礎(chǔ)，融合其鄰域內(nèi)剩余的交會點(diǎn)，取閾值3 600 m，得到“轉(zhuǎn)向+交會點(diǎn)”的數(shù)量，實(shí)驗(yàn)結(jié)果見表5。

最后以原有的3種特征點(diǎn)和融合后的4種特征點(diǎn)作為交通流的重要節(jié)點(diǎn)，提取該水域的船舶交通流框架，該框架具有混合表現(xiàn)船舶位置、船舶轉(zhuǎn)向、航跡交會3種航跡特征的屬性。圖14為最終提取的老鐵山水道附近水域的交通流框架。

3 結(jié) 論

為提高船舶進(jìn)出交通流密集區(qū)域的安全性，以提取船舶交通流特征為切入點(diǎn)，對監(jiān)控水域的船舶航跡線進(jìn)行數(shù)據(jù)挖掘，利用密度聚類算法、Douglas-Peucker壓縮算法和航跡交會算法，分別提取聚類后的船位點(diǎn)、船舶轉(zhuǎn)向點(diǎn)和航跡交會點(diǎn)等特征點(diǎn)，組成該水域的交通流網(wǎng)絡(luò)。對集成交通流網(wǎng)絡(luò)中的多種特征點(diǎn)進(jìn)行優(yōu)化和加權(quán)融合，提取具有多元特征點(diǎn)的船舶交通流框架，采用老鐵山水道附近水域的AIS數(shù)據(jù)驗(yàn)證了該方法的可行性。該方法能夠彌補(bǔ)以往船舶交通流網(wǎng)絡(luò)特征和可視化效果的不足，有利于增強(qiáng)值班駕駛?cè)藛T對交通流多樣化特征和整體態(tài)勢的了解，提供操縱決策支持，還能為海事管理機(jī)關(guān)的航道建設(shè)和錨地規(guī)劃提供參考。后續(xù)將繼續(xù)挖掘航跡特征和外界環(huán)境信息，使船舶交通流框架的內(nèi)涵更加豐富。

參考文獻(xiàn)：

[1]LV S M. Construction of marine ship automatic identification system data mining platform based on big data[J]. Journal of Intelligent & Fuzzy Systems， 2020， 38（2）： 1249-1255. DOI： 10.3233/JIFS-179487.

[2]魏照坤. 基于AIS的船舶軌跡聚類與應(yīng)用[D]. 大連： 大連海事大學(xué)， 2015.

[3]HAN Peng， YANG Xiaoxia. Big data-driven automatic generation of ship route planning in complex maritime environments[J]. Acta Oceanologica Sinica， 2020， 39（8）： 113-120. DOI： 10.1007/s13131-020-1638-5.

[4]郭乃琨， 馬壯壯， 岳明橋. 船舶軌跡挖掘與可視化技術(shù)分析研究[J]. 電子元器件與信息技術(shù)， 2020， 4（3）： 141-142. DOI： 10.19772/j.cnki.2096-4455.2020.3.057.

[5]張樹凱， 劉正江， 張顯庫， 等. 基于Douglas-Peucker算法的船舶AIS航跡數(shù)據(jù)壓縮[J]. 哈爾濱工程大學(xué)學(xué)報(bào)， 2015， 36（5）： 595-599.DOI： 10.3969/j.issn.1006-7043.201401013.

[6]劉敦偉. 基于AIS數(shù)據(jù)的船舶航線挖掘[D]. 大連： 大連海事大學(xué)， 2017.

[7]高邈， 史國友， 李偉峰. 改進(jìn)的Sliding Window在線船舶AIS軌跡數(shù)據(jù)壓縮算法[J]. 交通運(yùn)輸工程學(xué)報(bào)， 2018， 18（3）： 218-227.

[8]GAO Miao， SHI Guoyou. Ship spatiotemporal key feature point online extraction based on AIS multi-sensor data using an improved sliding window algorithm[J]. Sensors， 2019， 19（12）： 2706. DOI： 10.3390/s19122706.

[9]劉虎， 李偉峰. 基于AIS數(shù)據(jù)的海上交通流區(qū)域自動(dòng)識別[J]. 中國航海， 2016， 39（4）： 87-90， 132.

[10]RONG H， TEIXEIRA A P， SOARES C G. Data mining approach to shipping route characterization and anomaly detection based on AIS data[J]. Ocean Engineering， 2020， 198： 106936. DOI： 10.1016/j.oceaneng.2020.106936.

[11]LEI P R. Mining maritime traffic conflict trajectories from a massive AIS data[J]. Knowledge and Information Systems， 2020， 62（1）： 259-285. DOI： 10.1007/s10115-019-01355-0.

[12]ZHOU Yang， DAAMEN W， VELLINGA T， et al. Ship classification based on ship behavior clustering from AIS data[J]. Ocean Engineering， 2019， 175： 176-187. DOI： 10.1016/j.oceaneng.2019.02.005.

[13]趙梁濱. 船舶軌跡的數(shù)據(jù)挖掘框架及應(yīng)用[D]. 大連： 大連海事大學(xué)， 2016.

[14]周世波， 熊振南. 基于局部密度的成山角船舶交通流特征分析[J]. 大連海事大學(xué)學(xué)報(bào)， 2019， 45（3）： 100-105. DOI： 10.16411/j.cnki.issn1006-7736.2019.03.014.

（編輯 趙勉）