一種顧及時(shí)間特征的船舶軌跡DBSCAN聚類算法

郭乃琨，陳明劍，陳 銳

(1.信息工程大學(xué) 地理空間信息學(xué)院,河南 鄭州 450001;2.92493部隊(duì),遼寧 葫蘆島 125001)

近年來，全球衛(wèi)星導(dǎo)航系統(tǒng)(Global Navigation Satellite System，GNSS)、北斗衛(wèi)星導(dǎo)航系統(tǒng)(BeiDou Navigation Satellite System，BDS)等衛(wèi)星導(dǎo)航定位系統(tǒng)迅速發(fā)展，已經(jīng)成為國防軍事、國民經(jīng)濟(jì)發(fā)展中必不可少的基礎(chǔ)設(shè)施[1]。

隨著世界海洋經(jīng)濟(jì)的迅速發(fā)展，各國海洋貿(mào)易中的船舶數(shù)量隨之劇增，船舶自動識別系統(tǒng)(Auto Identification System，AIS)已被世界各國廣泛采用。全球船舶軌跡數(shù)量龐大、內(nèi)容豐富，除了與常見的陸上軌跡一樣具有海量性、動態(tài)性、時(shí)序性特征外，還具有一系列的獨(dú)特性，陸上軌跡主要反映對象在陸地上的時(shí)空變化規(guī)律與行為模式，而船舶軌跡主要反映對象在海上的相應(yīng)規(guī)律與模式；船舶軌跡在形成過程中，更多地受到水系的固有約束，并且其數(shù)據(jù)相比陸上軌跡具有更多的字段，屬性維度更高。因此，運(yùn)用簡單、常規(guī)的數(shù)據(jù)分析方法很難從船舶軌跡中分析出全面、有價(jià)值的隱含信息。

聚類分析是眾多數(shù)據(jù)分析與挖掘方法中應(yīng)用最廣泛的方法，通過衡量研究對象之間的相似度(距離度量)，將相似度高的對象劃分為同類。按照聚類的目標(biāo)、處理的數(shù)據(jù)以及具體應(yīng)用領(lǐng)域的不同，聚類分析可分為基于劃分的聚類、基于層次的聚類、基于密度的聚類、基于網(wǎng)格的聚類和基于模型的聚類。其中，基于密度的聚類是近年來在交通流挖掘、商業(yè)中心選址、圖像分割與識別等諸多領(lǐng)域得到廣泛應(yīng)用的經(jīng)典聚類算法，其中又以基于密度的對噪聲魯棒的空間聚類算法(Density-Based Spatial Clustering of Application with Noise，DBSCAN)最為常用。DBSCAN算法相比其他算法無需指定簇的個(gè)數(shù)，可以對任意形狀的數(shù)據(jù)集進(jìn)行聚類，常用于離群點(diǎn)監(jiān)測。但經(jīng)典的DBSCAN算法僅適用于空間聚類，對于具有時(shí)間、航速等多維、動態(tài)信息的船舶AIS軌跡而言不再適用。本文提出一種顧及時(shí)間特征的船舶軌跡DBSCAN聚類算法，在經(jīng)典DBSCAN的基礎(chǔ)上，通過定義船舶軌跡間的時(shí)間距離來衡量其時(shí)間相似度，進(jìn)而定義時(shí)空距離來衡量時(shí)空相似度，實(shí)現(xiàn)船舶軌跡的時(shí)空聚類。

1 相關(guān)工作

1.1 經(jīng)典DBSCAN算法

DBSCAN是一種典型的基于密度的聚類算法，最初主要用于點(diǎn)或可視為點(diǎn)對象的聚類，通過將簇定義為密度相連的點(diǎn)的最大集合，可以有效找到樣本點(diǎn)的全部密集區(qū)域，這些密集區(qū)域即被視為聚類簇[2]。DBSCAN算法的聚類過程如圖1所示。

圖1 經(jīng)典DBSCAN算法流程

目前的相關(guān)研究主要圍繞對經(jīng)典DBSCAN算法的聚類效果改進(jìn)而展開。許虎寅等[3]在DBSCAN算法的基礎(chǔ)上，提出一種改進(jìn)的基于密度的聚類算法，有效減少核心點(diǎn)鄰域的重疊區(qū)域的查詢時(shí)間和次數(shù)；王光等[4]提出一種改進(jìn)的自適應(yīng)參數(shù)DBSCAN算法，對MinPts和Eps參數(shù)基于核密度估計(jì)進(jìn)行確定，基于4種經(jīng)典數(shù)據(jù)集的對比實(shí)驗(yàn)證明該算法在參數(shù)選擇自動化和準(zhǔn)確率方面的優(yōu)勢；李建伏等[5]基于馬爾科夫鏈蒙特卡洛方法MCMC對DBSCAN方法進(jìn)行改進(jìn)，提出一種基于MCMC的DBSCAN算法DBSCAN++，并且與經(jīng)典DBSCAN算法和OPTICS算法進(jìn)行對比分析實(shí)驗(yàn)，結(jié)果表明DBSCAN++算法聚類的高效性與準(zhǔn)確性。

1.2 船舶軌跡聚類算法

船舶軌跡聚類的目的是采用相關(guān)的聚類算法對軌跡數(shù)據(jù)進(jìn)行聚類，找出具有相似船舶運(yùn)動演化方式的軌跡簇[6-8]，揭示船舶軌跡間潛在的關(guān)系，分析船舶交通流特征或個(gè)體船舶的行為。通過對船舶軌跡數(shù)據(jù)進(jìn)行處理和聚類分析，可以對船舶的運(yùn)動規(guī)律進(jìn)行量化，并進(jìn)一步探測船舶的異常行為，從而有效提升海上交通態(tài)勢感知能力，為海事安全監(jiān)控與預(yù)測提供決策支持。船舶軌跡數(shù)據(jù)一般是指基于AIS的軌跡數(shù)據(jù)[9]，主要是從AIS基站獲得，因此當(dāng)前大部分的船舶軌跡聚類研究均為針對船舶AIS數(shù)據(jù)的聚類分析，其分析流程如圖2所示。

圖2 船舶AIS軌跡聚類流程

船舶 AIS軌跡數(shù)據(jù)采集的過程中，需要對船舶 AIS軌跡數(shù)據(jù)進(jìn)行預(yù)處理，以提高數(shù)據(jù)質(zhì)量，常見的預(yù)處理過程包括數(shù)據(jù)編碼與清洗、缺失數(shù)據(jù)處理、降維處理、數(shù)據(jù)壓縮等內(nèi)容：船舶軌跡聚類方面，Huttenlocher等人[10]證明利用Hausdorff距離比其他度量兩個(gè)點(diǎn)之間距離的相關(guān)算法具有更強(qiáng)的魯棒性；Zheng等[11]將K-Means聚類算法用于船舶軌跡的聚類，用歐式距離計(jì)算船舶軌跡相似度，利用開源數(shù)據(jù)挖掘工具WEKA對長江某航段船舶到達(dá)時(shí)間、船舶噸位、船舶類型等屬性分別進(jìn)行聚類，獲得有價(jià)值的交通特性信息[12]；Vries等人[13]將船舶軌跡看作時(shí)間序列，采用態(tài)時(shí)間規(guī)整(Dynamic Time Warping，DTW)和ED來計(jì)算軌跡的相似度；Pallotta等人[14-15]對DBSCAN算法進(jìn)行改進(jìn)，采用增量DBSCAN算法對船舶AIS軌跡數(shù)據(jù)中的轉(zhuǎn)向點(diǎn)聚類，在此基礎(chǔ)上分析船舶的交通流模式。Liu等人[16]在考慮船舶軌跡數(shù)據(jù)中非空間屬性(如船速、航向等)基礎(chǔ)上，對DBSCAN算法進(jìn)行改進(jìn)，在輸入?yún)?shù)中新增船舶最大的船速變化量(MaxSpd)和最大的航向變化量(MaxDir)兩個(gè)變量。

1.3 相關(guān)研究分析

傳統(tǒng)的軌跡聚類方法主要面向居民日常出行、活動和旅游等現(xiàn)實(shí)場景，如常見的出租車軌跡聚類、熱點(diǎn)區(qū)域分析、居民出行模式挖掘、載客路徑挖掘、重要興趣點(diǎn)識別等，面對復(fù)雜問題時(shí)需要設(shè)置的條件和參數(shù)較多，并且大部分方法的可移植性較差，很難被應(yīng)用到新的數(shù)據(jù)集上。上述船舶軌跡聚類的相關(guān)研究中，基于距離的聚類方法對船舶軌跡進(jìn)行聚類具有算法簡單、實(shí)現(xiàn)容易的優(yōu)點(diǎn)，但由于基于距離的軌跡相似度度量方法本身的不足，仍然存在容易丟失軌跡局部特征信息等不足；與基于距離的船舶軌跡聚類方法相比，采用經(jīng)典DBSCAN等基于密度的聚類算法對船舶軌跡進(jìn)行聚類，其優(yōu)勢主要表現(xiàn)在能發(fā)現(xiàn)任意形狀的船舶軌跡簇，且對異常的船舶軌跡魯棒性較強(qiáng)，軌跡聚集的結(jié)構(gòu)與樣本軌跡的遍歷順序也無關(guān)。但DBSCAN算法主要適用于空間聚類，即通過定義空間距離對象的空間相似度進(jìn)行衡量，對于具有典型的多維、時(shí)變和空間動態(tài)特征的船舶軌跡很難達(dá)到理想的聚類分析效果。

2 顧及時(shí)間特征的船舶軌跡DBSCAN聚類算法

2.1 算法概述

鑒于經(jīng)典DBSCAN算法主要適用于空間聚類，對具有時(shí)變動態(tài)信息的船舶軌跡聚類適用性差的現(xiàn)狀，本文提出一種顧及時(shí)間特征的船舶軌跡DBSCAN聚類算法。該算法在經(jīng)典DBSCAN空間聚類算法的基礎(chǔ)上，首先對船舶軌跡數(shù)據(jù)進(jìn)行數(shù)據(jù)編碼與清洗、缺失數(shù)據(jù)處理、數(shù)據(jù)壓縮等一系列預(yù)處理，在此基礎(chǔ)上提出了基于OD(Origin-Destination)點(diǎn) 、SP(Stay-Point)點(diǎn)以及TF(Trajectory-Feature)點(diǎn)的軌跡特征點(diǎn)提取方法，以此生成船舶AIS軌跡的子軌跡；然后提出船舶子軌跡段之間的時(shí)間距離度量方法，并通過設(shè)置權(quán)重調(diào)整時(shí)空特征敏感度，最后使用DBSCAN算法對時(shí)空鄰域密度進(jìn)行聚類分析，進(jìn)而挖掘船舶軌跡的典型時(shí)空運(yùn)動模式。相比于空間聚類，顧及時(shí)間特征的船舶軌跡DBSCAN聚類算法可以同時(shí)兼顧船舶軌跡的空間與時(shí)間特征，得到的聚類可以更加細(xì)化，移動通道更準(zhǔn)確，有利于對船舶的移動規(guī)律做更進(jìn)一步的分析，進(jìn)而為合理規(guī)劃航路及海事監(jiān)管中的熱點(diǎn)航道提取和異常事件預(yù)防提供有效的決策手段和參考信息。

2.2 算法流程

本文提出的顧及時(shí)間特征的船舶軌跡DBSCAN聚類算法流程如圖3所示。

圖3 顧及時(shí)間特征的船舶AIS軌跡聚類流程

2.2.1 船舶軌跡數(shù)據(jù)預(yù)處理

首先是數(shù)據(jù)準(zhǔn)備工作，將采集到的船舶軌跡數(shù)據(jù)，利用空間關(guān)系型數(shù)據(jù)庫(如PostgreSQL)進(jìn)行存儲，數(shù)據(jù)庫表的內(nèi)容主要包括MMSI碼、船舶位置、航向、航速、船舶大小、UTC時(shí)間等。由于船舶AIS設(shè)備以“明碼”和“暗碼” 兩種壓縮編碼的形式傳輸數(shù)據(jù)，運(yùn)用AIS數(shù)據(jù)解析程序從原始數(shù)據(jù)中提取所需內(nèi)容并導(dǎo)入數(shù)據(jù)庫。

然后是軌跡數(shù)據(jù)預(yù)處理工作，船舶軌跡原始數(shù)據(jù)通常存在噪聲和偏差的問題。為了保證后續(xù)軌跡特征點(diǎn)選取的精度和速度，需要對船舶軌跡數(shù)據(jù)進(jìn)行預(yù)處理：刪除MMSI碼錯(cuò)誤的數(shù)據(jù)；刪除船舶位置的經(jīng)緯度出現(xiàn)負(fù)值或是經(jīng)度大于180°、緯度大于90°的數(shù)據(jù)；刪除航速為負(fù)值或大于60 kn的數(shù)據(jù)；刪除超過研究水域范圍的數(shù)據(jù)等。

2.2.2 特征點(diǎn)提取

將每條船舶軌跡按照OD點(diǎn) 、SP點(diǎn)和TF點(diǎn)的判定條件進(jìn)行軌跡特征點(diǎn)的提取，將提取出的三類軌跡特征點(diǎn)組成代表該條軌跡運(yùn)動規(guī)律的特征點(diǎn)集合。將集合中的相鄰特征點(diǎn)按時(shí)間先后順序排列依此連接生成該條軌跡的子軌跡。最終由這些特征點(diǎn)集合生成所有船舶軌跡的子軌跡集合。其中，通過如下方法對OD點(diǎn)、SP點(diǎn)和TF點(diǎn)進(jìn)行篩選和提取。

首先，將每條船舶軌跡的起點(diǎn)和終點(diǎn)選取為該條船舶軌跡的OD點(diǎn)。然后通過設(shè)置時(shí)間閾值和速度閾值，如果相鄰軌跡點(diǎn)之間時(shí)間差大于特定的時(shí)間閾值，而兩個(gè)軌跡點(diǎn)的速度值都小于設(shè)定的速度閾值，則將兩個(gè)相鄰的軌跡點(diǎn)識別為該條船舶軌跡的停泊點(diǎn)，記為SP點(diǎn)。最后利用曲線邊緣檢測法對每條船舶軌跡的所有軌跡點(diǎn)進(jìn)行識別，將符合判定條件的軌跡點(diǎn)選取為軌跡特征點(diǎn)，記為TF點(diǎn)，曲線邊緣檢測法的過程如下：

1)假設(shè)給定一條船舶運(yùn)行軌跡，其中的P1(x1,y1)，P2(x2,y2)，P3(x3,y4)(x1

T12(x,y)=(y2-y1)(x-x1)+

(y-y1)(x2-x1).

2)計(jì)算軌跡點(diǎn)P3(x3,y3)關(guān)于正向直線方程T12的值，若T12(x3,y3)<0，則稱軌跡點(diǎn)P3(x3,y3)是關(guān)于正向直線的內(nèi)點(diǎn)；若T12(x3,y3)>0，則稱軌跡點(diǎn)P3(x3,y3)是關(guān)于正向直線外點(diǎn)。

3)連接軌跡點(diǎn)P2(x2,y2)和P3(x3,y3)構(gòu)成一條關(guān)于軌跡的正向直線T23，對應(yīng)的正向直線方程為：

T23(x,y)=(y3-y2)(x-x2)+

(y-y2)(x3-x2).

4)計(jì)算軌跡點(diǎn)P4(x4,y4)關(guān)于正向直線方程T23的值，并根據(jù)上述方法判斷軌跡點(diǎn)P4(x4,y4)為內(nèi)點(diǎn)或外點(diǎn)。

5)若T12(x3,y3)·T23(x4,y4)<0，說明軌跡在P3(x3,y3)處方向有所改變，則軌跡點(diǎn)P3(x3,y3)是特征點(diǎn)，即為TF點(diǎn)，否則P3(x3,y3)不是TF點(diǎn)。

6)依次循環(huán)判斷，直到最后一個(gè)軌跡點(diǎn)，即可識別出船舶運(yùn)行軌跡的所有TF點(diǎn)。

2.2.3 子軌跡段劃分

根據(jù)上述提取出的三類軌跡特征點(diǎn)(OD點(diǎn)、SP點(diǎn)和TF點(diǎn))組成該船舶運(yùn)行軌跡的特征點(diǎn)集合，將特征點(diǎn)集合中的相鄰特征點(diǎn)按時(shí)間先后順序排列，依次連接生成該條軌跡的子軌跡，其中相鄰兩個(gè)特征點(diǎn)的線段稱為子軌跡段，如圖4所示。

圖4 子軌跡段劃分流程

2.2.4 時(shí)空距離定義與計(jì)算

這一步主要計(jì)算任意兩子軌跡段之間的空間距離和時(shí)間距離，對得到的空間距離和時(shí)間距離進(jìn)行加權(quán)求和得到融合后的時(shí)空距離。

1)空間距離定義與計(jì)算。本文中兩子軌跡段之間的空間距離是根據(jù)船舶位置信息計(jì)算得到的，包括平行距離、垂直距離和角度距離3個(gè)方面。設(shè)兩條子軌跡段Li和Lj，記為Li(si,ei)和Lj(sj,ej)，其中si，ei和sj，ej分別為子軌跡段Li和子軌跡段Lj的起點(diǎn)和終點(diǎn)的位置信息，由子軌跡段Lj向Li垂直投影，如圖4所示，其中，Ps和Pe為Lj在Li上的垂直投影點(diǎn)。則子軌跡段Li和Lj之間的垂直距離為：

子軌跡段Li和Lj之間的平行距離為:

d‖(Li,Lj)=MIN(l‖1,l‖2)；

角度距離為:

dθ(Li,Lj)=

綜上，得到子軌跡段Li和子軌跡段Lj之間的空間距離為:

DS=d⊥(Li,Lj)+d‖(Li,Lj)+dθ(Li,Lj).

Δtij=max(tie,tje)-min(tis,tjs).

則子軌跡段Li和Lj之間的時(shí)間距離DT為

其中，兩子軌跡段之間的時(shí)間距離由時(shí)間跨度、時(shí)間差和航速的速度均值共同決定。為了更簡單地計(jì)算時(shí)間距離，上述中的速度均值也可以采用子軌跡段中的任一點(diǎn)的速度，這是由于在短時(shí)間內(nèi)，子軌跡段內(nèi)的船舶航速基本不會變化。

使用均值絕對偏差對空間距離Ds標(biāo)準(zhǔn)化為:

其中，Dsn服從高斯分布；同理可按照上述過程得到時(shí)間距離的標(biāo)準(zhǔn)化值Dtn，則時(shí)空距離的算式為：

DST=ωs×Dsn+ωt×Dtn.

其中，Dsn為將空間距離通過Z-Score分?jǐn)?shù)方法進(jìn)行標(biāo)準(zhǔn)化處理得到，Dtn為將時(shí)間距離DT通過Z-Score分?jǐn)?shù)方法進(jìn)行標(biāo)準(zhǔn)化處理得到，ws為空間距離的權(quán)重系數(shù)，wt為時(shí)間距離的權(quán)重系數(shù)，兩者表征空間距離和時(shí)間距離的敏感度，可根據(jù)實(shí)際情況進(jìn)行設(shè)定，且滿足ωs+ωt=1。

5)船舶軌跡聚類。這一步主要根據(jù)獲取的時(shí)空距離，通過DBSCAN算法對各子軌跡段進(jìn)行聚類。聚類時(shí)，從任一子軌跡段出發(fā)，計(jì)算與其他所有子軌跡線段間的時(shí)空距離，根據(jù)獲取的各子軌跡段間的時(shí)空距離，給定ε-鄰域范圍和最小線段參數(shù)(MinLns)，統(tǒng)計(jì)滿足ε-鄰域范圍的線段個(gè)數(shù)，并與最小線段參數(shù)(MinLns)進(jìn)行比較，當(dāng)ε-鄰域范圍內(nèi)的線段數(shù)目大于給定的最小線段參數(shù)(MinLns)時(shí)，該子軌跡段即為核心軌跡，形成一個(gè)聚類，其鄰域內(nèi)的直接密度可達(dá)線段也將聚類到該類中，再對剩余的其他子軌跡段按照同樣的方式依次進(jìn)行聚類擴(kuò)展，得到最終的聚類結(jié)果；而其中未被聚成一類的子軌跡段則是孤立軌跡，不作處理。其中，關(guān)于DBSCAN的各項(xiàng)參數(shù)表示或計(jì)算如下：ε-鄰域范圍Nε(Li)為子軌跡段Li在線段集D(Li∈D)內(nèi)所有與其時(shí)空距離不超過ε的軌跡集合，即表示為Nε(Li)={Li∈D|Ddist(Li,Lj)≤ε}；子軌跡段Li的線段集為D(Li∈D)，給定鄰域范圍ε和最小線段參數(shù)MinLns，若滿足|Nε(Li)|≥MinLns，則認(rèn)為Li為核心軌跡；子軌跡段Li的線段集為D(Li∈D)，給定參數(shù)鄰域范圍ε和最小線段參數(shù)MinLns，若Li為核心軌跡且Lj在Li的ε鄰域范圍內(nèi)，則稱Lj從Li直接密度可達(dá)；子軌跡段Li的線段集為D(Li∈D)，給定參數(shù)鄰域范圍ε和最小線段參數(shù)MinLns，若存在從Li到Lk直接密度可達(dá)，從Lk到Lj直接密度可達(dá)，則從Li到Lj密度可達(dá)；子軌跡段Li的線段集為D(Li∈D)，給定參數(shù)鄰域范圍和最小線段參數(shù)MinLns，若存在Li和Lj均由Lk密度可達(dá)，則Li和Lj密度相連。

6)時(shí)間和空間距離權(quán)重系數(shù)確定。在上述流程中，時(shí)間距離和空間距離的權(quán)重系數(shù)需要確定。為了得到最佳的聚類效果，本文確定的原則是，基于戴維森堡丁(Davies Bouldin Index，DBI)指數(shù)[17]來量化不同權(quán)重系數(shù)下的聚類質(zhì)量，而DBI指數(shù)與時(shí)空距離權(quán)重系數(shù)之間存在一一對應(yīng)關(guān)系，含義是度量每個(gè)簇類最大相似度的均值，能夠較好的體現(xiàn)不同權(quán)重系數(shù)取值的聚類質(zhì)量。DBI的值最小是0，不同權(quán)重系數(shù)下求得的DBI指數(shù)越小，聚類效果越好，同時(shí)也證明權(quán)重系數(shù)更優(yōu)。DBI指數(shù)又稱分類適確性指標(biāo)，是一種評估聚類算法優(yōu)劣的指標(biāo)，其計(jì)算方法為：首先假設(shè)實(shí)驗(yàn)數(shù)據(jù)有m個(gè)時(shí)間序列，這些時(shí)間序列聚類為n個(gè)簇，m個(gè)時(shí)間序列設(shè)為輸入矩陣X，n個(gè)簇類設(shè)為N作為參數(shù)傳入算法，則DBI指數(shù)的算式為：

其中，各項(xiàng)參數(shù)的計(jì)算公式如下：

其中Xj代表簇類i中第j個(gè)數(shù)據(jù)點(diǎn)，也就是一個(gè)樣本點(diǎn)；Ai是簇類的質(zhì)心；Ti是簇類中數(shù)據(jù)的個(gè)數(shù)。

2)距離值Mi,j定義為簇類i與簇類j的距離，算式為:

其中,ak,i代表簇類質(zhì)心點(diǎn)的第k個(gè)值；Mi,j就是簇類i與簇類j質(zhì)心的距離，即ak,i表示第i類的中心點(diǎn)的第k個(gè)屬性的值，Mi,j則就是第i類與第j類中心的距離。

3)相似度值Ri,j用于衡量第i類與第j類的相似度，算式為:

4)在上述基礎(chǔ)上，做一個(gè)基于簇類數(shù)n的n2的嵌套循環(huán)，對每一個(gè)簇類i計(jì)算Ri,j的最大值，記為Di=max(Ri,j)，即簇類和其他類的最大的相似度值。然后對所有類的最大相似度取平均值就得到了DBI指數(shù)，算式為:

通過以上步驟，就能夠直觀地分析出不同權(quán)重下聚類結(jié)果質(zhì)量的高低，從而確定聚類質(zhì)量最優(yōu)的權(quán)重系數(shù)，進(jìn)而準(zhǔn)確地對船舶運(yùn)行的子軌跡進(jìn)行聚類。

3 實(shí)驗(yàn)驗(yàn)證

3.1 實(shí)驗(yàn)環(huán)境

測試服務(wù)器為Thinkpad T440，AMD雙核CPU，4 GB內(nèi)存，256 G固態(tài)硬盤容量；操作系統(tǒng)采用Windows 10 64位旗艦版，實(shí)驗(yàn)程序運(yùn)行環(huán)境為Pycharm 2018.1，程序語言及其版本為Python 3.6.2。

3.2 實(shí)驗(yàn)流程與結(jié)果

為對本文所提算法的有效性進(jìn)行驗(yàn)證，選取東海某海域(113°45′37″E～130°23′43″E，17°47′29″N～38°52′59″N)2016年2月9日到2016年3月6日真實(shí)船舶AIS軌跡數(shù)據(jù)進(jìn)行測試，其中每條軌跡由相互緊鄰的樣本點(diǎn)連接而成。原始數(shù)據(jù)共計(jì)320 001個(gè)采樣點(diǎn)，按照船舶MMSI標(biāo)識整理后共得到260條軌跡；由于部分軌跡中的船舶點(diǎn)位過少，生成的軌跡無法代表其航行軌跡，因此對這部分無效軌跡進(jìn)行剔除，得到249條有效軌跡。

由于從上述初步得到的每條軌跡中提取關(guān)鍵點(diǎn)需要迭代的次數(shù)較多、工作量較大，需要對每條船舶軌跡進(jìn)行壓縮。數(shù)據(jù)壓縮有多種方法，在GIS領(lǐng)域常見的矢量數(shù)據(jù)壓縮方法有道格拉斯-普克法(Douglas-Peucker Algorithm)、垂距法、光欄法等，其中道格拉斯-普克法較為經(jīng)典且使用較廣。對于一條曲線軌跡，道格拉斯-普克法通過循環(huán)連接首尾兩點(diǎn)，并計(jì)算中間各點(diǎn)到上述連線的距離，將最大距離值dmax與限差D進(jìn)行比較，若dmax

圖5 船舶AIS軌跡數(shù)據(jù)壓縮前后對比

在上述數(shù)據(jù)壓縮的基礎(chǔ)上，接下來對實(shí)驗(yàn)船舶軌跡進(jìn)行特征點(diǎn)提取。首先，通過對實(shí)驗(yàn)數(shù)據(jù)的分析，將SP點(diǎn)的提取采取的時(shí)間閾值為8 min，航速閾值為0.8 kn。然后，通過對每條軌跡的OD點(diǎn)、SP點(diǎn)和TF點(diǎn)進(jìn)行提取，從而得到能夠代表每條船舶軌跡的特征點(diǎn)集合，以此形成子軌跡集合。眾多子軌跡在某些子段處會出現(xiàn)重疊，因此按照上文的子軌跡段劃分方法對249條軌跡進(jìn)行劃分，共得到2 396條子軌跡。然后利用本文提出的顧及時(shí)間特征的船舶軌跡DBSCAN算法對子軌跡段實(shí)施聚類，在確定時(shí)間距離和空間距離各自的權(quán)重系數(shù)時(shí)，利用DBI指數(shù)來進(jìn)行判定，部分試驗(yàn)結(jié)果如表1所示。

由表1可知，當(dāng)空間距離權(quán)重ωs=0.56、時(shí)間距離權(quán)重ωT=0.44時(shí)，DBI的值最小，聚類效果最佳。因此，最終時(shí)空距離計(jì)算中的空間距離權(quán)重系數(shù)確定為0.56，時(shí)間距離權(quán)重確定為0.44。在此基礎(chǔ)上，利用本文的算法對上述所有的船舶子軌跡段進(jìn)行聚類，最后對相似的子軌跡進(jìn)行融合形成。實(shí)驗(yàn)過程中發(fā)現(xiàn)該算法對聚類參數(shù)ε和MinLns較為敏感，因此通過反復(fù)試驗(yàn)，最終確定ε=0.003 nmile,MinLns=3時(shí)，聚類效果較為理想。結(jié)果如圖6所示。

表1 基于不同時(shí)、空距離權(quán)重取值的部分DBI指數(shù)計(jì)算結(jié)果

圖6 船舶AIS軌跡數(shù)據(jù)聚類前后對比

此外，為了驗(yàn)證本文算法的優(yōu)劣，將其與經(jīng)典的DBSCAN空間聚類算法的效果進(jìn)行對比。在選用相同的數(shù)據(jù)集的基礎(chǔ)上，兩者在耗時(shí)、準(zhǔn)確度、分類數(shù)等方面的對比如表2所示。

表2 本文算法與經(jīng)典DBSCAN算法的優(yōu)劣對比

3.3 實(shí)驗(yàn)分析

由圖6可知，在實(shí)驗(yàn)船舶軌跡數(shù)據(jù)集上，通過本文的聚類算法，成功將軌跡數(shù)據(jù)集分成4個(gè)有效類簇(每個(gè)類簇以一種顏色表示)，即本文算法成功地從原始軌跡中提取出4條典型軌跡，這4條軌跡可以形象地反映出該船舶在1個(gè)月時(shí)間內(nèi)的空間位置變化規(guī)律和航行模式。由表2可知，本文提出的顧及時(shí)間特征的船舶軌跡聚類算法在耗時(shí)上略遜于經(jīng)典DBSCAN算法，這是由于本文算法除了要計(jì)算空間距離外，還需要計(jì)算兩子軌跡之間的時(shí)間距離，然后計(jì)算時(shí)空距離，其中涉及的相似性度量相對復(fù)雜，因此使得算法的復(fù)雜度升高。但由于本文算法同時(shí)兼顧時(shí)空距離，更易于發(fā)現(xiàn)經(jīng)典DBSCAN算法無法發(fā)現(xiàn)的隱蔽群，使得算法的準(zhǔn)確率和聚類數(shù)目有較大提升。

此外，考慮本文算法隨著船舶軌跡數(shù)據(jù)集增長時(shí)的效能變化，分別在前文數(shù)據(jù)集27 d，45 d，60 d數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)流程與上述流程保持一致，統(tǒng)計(jì)不同數(shù)據(jù)集上的原始軌跡數(shù)、劃分子軌跡數(shù)和耗時(shí)如表3所示。

表3 基于不同規(guī)模數(shù)據(jù)集的本文算法性能對比

由表3可知，隨著數(shù)據(jù)集的增大，本文算法的耗時(shí)呈現(xiàn)急劇上升的趨勢，因此在后續(xù)研究中，需要關(guān)注如何優(yōu)化算法的過程與結(jié)構(gòu)，從而有效降低聚類的時(shí)間消耗。

4 結(jié)束語

作為時(shí)空大數(shù)據(jù)范疇中對地理信息環(huán)境中社會感知數(shù)據(jù)的重要表現(xiàn)形式，軌跡數(shù)據(jù)能夠有效表征時(shí)空對象的移動規(guī)律，具有重要的應(yīng)用價(jià)值。船舶軌跡數(shù)據(jù)具有多維、動態(tài)特征，能夠表征船舶的時(shí)空移動狀態(tài)，為預(yù)測船舶的出行規(guī)律和行為模式提供信息支撐。本文在現(xiàn)有經(jīng)典DBSCAN聚類算法的基礎(chǔ)上，設(shè)計(jì)并實(shí)現(xiàn)一種顧及時(shí)間特征的船舶軌跡DBSCAN聚類算法，通過引入時(shí)間相似性度量方法，對船舶軌跡數(shù)據(jù)進(jìn)行分段并計(jì)算其時(shí)空距離，實(shí)現(xiàn)對船舶軌跡的時(shí)空聚類。最后進(jìn)行實(shí)驗(yàn)驗(yàn)證，通過與經(jīng)典DBSCAN算法進(jìn)行效能對比，結(jié)果證實(shí)本文算法的有效性。不足之處在于隨著船舶軌跡數(shù)據(jù)規(guī)模的擴(kuò)大，算法的耗時(shí)會急劇增長，因此如何對該算法進(jìn)行優(yōu)化，有效降低算法的聚類開銷，是后期的研究方向。