一種基于降維密度聚類的船舶異常軌跡識別方法

李可欣，郭健，王宇君，李宗明，繆坤，陳輝

（1.信息工程大學，鄭州 450001；2.32022 部隊，廣州 510000；3.31682 部隊，蘭州 730000；4.陸軍特種作戰學院，廣西 桂林 541000；5.31438 部隊，沈陽 110031）

隨著經濟全球化程度的不斷加深，各類船舶逐漸實現高速化和大型化，持續增長的海洋運輸需求與日趨飽和的航道容量之間的矛盾日益加劇，影響著海洋航運的安全與效率。為了更好地加強對海洋船舶的監控與管理，為海事監管人員提供更具針對性的解決方案，對大規模軌跡數據中的孤立、偏離、新穎數據點等進行檢測。實現對海上船舶異常軌跡的識別與研究，從而實現對海域的智能高效全監控。在智慧海洋態勢感知與管理方面具有重要的應用價值。

船舶自動識別系統（Automatic Identification System, AIS）包含船舶靜態以及航行運動動態信息，已經成為了海上監控管理的主要數據來源。由于AIS信息最初是為避免碰撞而設計的，缺乏關于數據質量的元數據，如可靠性、確定性等，這使得利用AIS檢測船舶異常成為一項非常困難的任務。AIS 數據包含地理空間特征、時序特征等一般數據所沒有的特定特征，并且缺乏具有代表性的真實數據集，因此如網絡流量[1]、網絡安全[2]等領域的異常檢測方法以及神經網絡[3]、支持向量[4]等有監督模式的識別方法不適用該類數據。上述方法不僅要花費大量的時間對數據進行標記，類別不均衡也易導致檢測結果的準確率降低。

針對AIS 數據特性，近年來關于海上異常檢測的研究方法可以分為基于規則的異常檢測[5]以及基于學習的異常檢測[6]。前者通過明確定義異常行為實現對異常的檢測，具有可解釋性，但需要基于大量歷史數據對規則進行總結，但對一些隱式規則難以發現和描述，實際可用性較低。后者基于歷史數據學習一般模式中隱藏的規則，成為海上異常檢測的主導方法。基于學習的異常檢測方法一般可分為2個階段：學習船舶軌跡的一般模式；檢測偏離模式的偏差。在第1 階段，以聚類分析為代表的無監督模式識別得到了廣泛的應用，如K–Means 算法[7]、DBSCAN 算法[8]、OPTICS 算法[9]、CURD 算法[10]，ST–DBSCAN 算法[11]、ST–OPTICS 算法[12]等。對于密度聚類通常只考慮空間信息這一問題，張春瑋等[13]構建了船舶行為相似度模型，基于DBSCAN 對船舶軌跡行為模式進行識別。王永明[14]綜合 K–means 和DBSCAN 算法對船舶軌跡進行聚類，以發現船舶航行軌跡異常。利用專家調查法和層次分析法對敏感水域的異常行為進行檢測和排序。李楠等[15]通過聚類算法找到類簇中心點，利用軌跡信息和飛行距離構建異常因子，實現航空器異常檢測。杜志強等[16]基于卡爾曼濾波，通過距離計算實現異常判別。孟祥澤等[17]采用ST–DBSCAN 算法從老年人軌跡中提取行為模式鏈，結合空間環境信息構建異常分析模型。馮宏祥等[18]通過船舶軌跡更新距離的均值和標準差，實現對AIS 誤用等多種海上船舶異常的發現與數據處理。上述方法中聚類參數的選擇往往基于經驗，由于缺乏異常數據的標簽，無法對所選參數的優劣進行評估，故難以獲取最優參數。李文杰等[19]根據數據及自身分布特性生成候選集，基于參數尋優策略實現聚類過程的全自動化，但是在密度分布差異大的數據集上聚類效果差。萬佳等[20]基于KANN–DBSCAN 方法，結合去噪衰減和多密度聚類，在實現參數自適應的前提下，提升了方法在密度分布差異大數據集上的聚類效果，但是該方法仍需設置密度閾值，且計算復雜度較高。

針對上述問題，本文提出一種基于降維密度聚類的船舶異常軌跡識別方法，將T–SNE 和自適應密度聚類結合，實現高效可靠的聚類，并根據聚類結果提取中心類簇構建類簇特征向量；最后根據不同距離閾值判別軌跡相似度，實現對異常軌跡的識別。構建海洋船舶軌跡異常模式識別模型，可以為智能海洋交通管理與優化提供科學化的數據支撐。

1 基于降維密度聚類的船舶異常軌跡識別方法

異常是指數據中不符合一般行為規范的模式。具體到海洋交通領域，異常軌跡一般包括：劇烈變速、劇烈轉向、位置漂移等運動學異常以及船舶軌跡偏離一般航線、行駛在禁漁區或禁航區等規則異常。結合軌跡數據特點，設計基于自適應降維密度聚類的船舶異常軌跡識別方法如圖1 所示。首先對AIS 數據進行預處理，通過隨機森林分類器構建最優多維特征組合；然后通過降維密度聚類生成軌跡聚類結果；根據聚類結果計算類簇特征向量，通過計算數據集中點與特征向量的位置距離和速度角度距離，生成判斷相似度檢測軌跡異常的距離閾值；最后結合軌跡段航行距離評估置信度，實現對軌跡異常的檢測。

圖1 基于DR–DBSCAN 的軌跡異常識別分析Fig.1 Analysis of trajectory anomaly identification based on DR-DBSCAN

1.1 AIS 數據預處理

1.1.1 數據清洗

由于軌跡數據本身具有的多源異構性以及數據質量差等特點，需要對原始數據進行處理，軌跡數據處理通常需要解決以下3 個問題：過濾清洗，去除由于采樣頻率、采樣精度、人為失誤等產生的噪聲數據；降低計算量；提高軌跡數據的精度。

對軌跡數據進行缺失值刪除、插值等預處理操作后，對軌跡基礎信息進行分析計算構建多維特征，根據MMSI 號將軌跡點分為完整軌跡段。船舶軌跡的集合M_traj、具體某一艘船舶的完整軌跡M_traji以及船舶軌跡點信息P可表示為：

式中：x、y為軌跡點經緯度信息；d為根據經緯度計算的地理空間距離；t為此段軌跡航行的總時間；v為AIS 報告的船舶速度；C為AIS 報告的船舶航向；H為AIS 報告的船舶艏向；Acal為根據H計算的角度變化；Arep為根據C計算的角度變化量；vrep為根據時間距離計算的航跡平均速度。

1.1.2 多維特征構建

數據集所選取的特征屬性離散性或相異性越高，數據的聚類效果則越好。原始軌跡數據包含經緯度、航行速度、航行方向等信息。為了更充分地挖掘軌跡特征，計算軌跡的航行距離、平均航行速度、加速度、轉向角等特征，避免偏離數據干擾，每個特征指標分別取平均值、最大值、最小值、中值構建軌跡特征數據集。由于特征之間也存在干擾，利用隨機森林分類器對軌跡數據進行分析，對多維特征軌跡進行評估，構建最佳特征組合，避免特征間的相互干擾，提高計算精度和計算效率。

1.1.3 軌跡分段和靜止點提取

停止點一般是船舶的運動狀態或行為模式發生變化的點，可以反映出停泊區、捕魚區、低速作業區等停止區域，具有重要的分析意義。從清洗后的AIS數據中提取同時滿足計算速度和報告速度均為靜止狀態的軌跡點，構建靜止軌跡點，并依據靜止點對完整軌跡段進行劃分。

根據保留的特征屬性信息，軌跡劃分的流程分為2 步：首先計算相鄰軌跡點的距離、轉向角以及速度；然后根據設定的速度閾值和最小軌跡長度，以靜止點以及發生較大轉向的點作為斷點對軌跡段進行劃分，篩除長度不符合要求的軌跡段，根據原始數據計算構造多維特征的時序子軌跡段特征。保留時序位置的子軌跡段集合S_traj_sequence可表示為：

對子軌跡段的多維特征進行處理，將多點二維信息轉化為單點二維信息，子軌跡段特征集合S_traj_features可表示為：

1.2 降維密度聚類

1.2.1 算法原理

由于海上航行相較于陸上交通具有更高的自由度，不同海洋區域船舶航行規律具有較大差別，因此很難提前確定聚類數目。由于AIS 數據本身具有不確定性，報告數據中包含許多錯誤軌跡構成的噪聲點，因此本文基于DBSCAN 算法，同時針對DBSCAN 算法超參數難以確定的問題，提出一種充分利用數據分布特性的基于多維特征降維的聚類方法（Dimensionality Reduction-Density-Based Spatial Clustering of Applications with Noise, DR-DBSCAN）。引入T–SNE 作為數據特征提取模塊，借助多流形聚類[21]的思想，從高維數據中提取和構建更高質量和更具魯棒性的數據特征低維有效表示。該方法的處理流程如圖2 所示。

圖2 DR–DBSCAN 算法流程Fig.2 DR-DBSCAN algorithm flow chart

對于多維特征數據集，常采用維數約減的方法降低特征間的復雜關系，減少噪聲。常用的手段有特征刪除、特征選擇以及特征抽取。前2 種手段往往容易導致信息丟失，PCA 和T–SNE 都屬于特征抽取的方法，在原始特征的基礎上通過空間映射創建新的特征，能更好地挖掘特征間的深層聯系。PCA 是一種線性降維方法，計算復雜度低但是特征表征效果較差；T–SNE 屬于非線性方法，計算復雜度高但對特征映射效果較好。隨機森林是一種由多個決策樹組成的機器學習模型，具有很好的數據集適應能力，對高維數據、離散或連續型數據都能很好的處理，魯棒性強。因此，本文將2 種方法結合，在提高計算效率的同時充分挖掘特征間的相關關系，使得在聚類時能充分利用數據特征間的關系；然后利用隨機森林模型學習聚類標簽，并判斷樣本類型。

在DR–DBSCAN 算法中，具體步驟如下：

1）將輸入的多維特征數據通過局部PCA 方法進行投影，再利用快速T–SNE 模型將PCA 處理后的數據轉化為低維嵌入。

2）計算低維嵌入層數據的平均成對距離作為eps候選集設置的基數構建候選集，并將數據劃分為訓練集和測試集。

3）分別將低維嵌入層數據和訓練集數據代入DBSCAN 模型中進行聚類，提取集群的聚類標簽，去除聚類簇數不符合設置最小聚類簇數的數據。

4）分別用嵌入層及其訓練集的聚類標簽訓練隨機森林分類器。

5）將測試集代入步驟4 中訓練的2 個分類器，經過K 折交叉驗證得到聚類參數最優值，輸出聚類結果。

1.2.2 算法分析及評價

為了更好地驗證所提出算法的性能，綜合考慮內部和外部聚類評估標準構建算法評價體系。外部評價指標是指基于已知標簽或模型，將聚類結果與其進行比較。選取的數據集均為有標簽數據，為了對聚類結果進行準確評價，引入外部聚類指標F1分數、調整蘭德系數（Adjusted Rand index,ARI）、歸一化互信息（Normalized Mutual Information,NMI）作為評價指標，計算公式如下。

F1分數是精確率和召回率的調和平均數，F1越高則模型越穩健，公式見式（7）。

式中：P為精確率；R為召回率。

ARI的取值范圍為[?1,1]，相比蘭德系數具有更高的區分度，值越大則表示聚類結果越吻合，計算式見式（8）。

式中：RI為蘭德系數，取值范圍為[0,1]，表示聚類標簽和真實標簽的比值情況。

NMI值用來衡量2 個數據間的相關性，在聚類中用于度量2 個聚類結果的相近程度，NMI值越大則表示劃分越準確，公式見式（9）。

式中：H(X)、H(Y)分別為聚類標簽和真實標簽的信息熵，即出現的概率；MI(X,Y)為互信息，是聯合分布與乘積分布的相對熵。

內部評價指標是根據數據集的固有特征來對算法結果進行評估。引入聚類性能內部評價指標包含輪廓系數（Silhouette Coefficient，SC）和Davies–Boulding指數（DBI）。輪廓系數結合了凝聚度和分離度，取值為[?1, 1]，其值越大越好，輪廓系數的計算式見式（10）。

式中：為a(i)簇內不相似度；b(i)為簇間不相似度。

DBI指數又稱分類適確性指標，DBI越小說明聚類效果越好，計算式見式（11）。

式中：m(CI)和m(Cj)為樣本間平均距離；d(μi,μj)為簇中心點距離。

1.3 船舶軌跡異常識別

1.3.1 類簇特征向量提取

在利用DR–DBSCAN 算法對軌跡進行聚類后，類簇可以代表船舶的一般運動模式。通過構建類簇特征向量來提取類簇特征，避免使用每個類簇的所有軌跡點進行計算所產生的巨大運算量，導致軌跡數據異常檢測的效率降低。類簇特征向量表達式可表示為式（12）。

提取類簇特征向量表示船舶行為的一般模式，通過計算訓練數據集中軌跡點與類簇特征向量的聚類距離，生成距離閾值，根據特征向量和距離閾值對測試集軌跡點進行異常檢測。最后根據船舶軌跡中異常點的占比來判斷軌跡段是否異常。類簇特征向量提取示意圖如圖3 所示。首先計算類簇平均航向角；然后根據平均航向角以及類簇點的經緯度范圍構建基礎網格；根據不同基礎網格的經緯度跨度，將基礎網格劃分為小網格；計算每個網格中的類簇點的平均速度、平均經緯度、平均距離以及最大轉向角；保存各個網格的特征向量，構建類簇特征向量集合。

圖3 類簇特征向量提取示意圖Fig.3 Feature vector extraction of class cluster

1.3.2 距離判定閾值計算

對于一個待檢測的軌跡數據P，首先根據P點的經緯度坐標，利用半正矢公式計算P與類簇特征向量的地理距離Dp。

式中：R為地球半徑，此處取地球平均半徑R=6 371.393 km。

保留使得所求地理距離最小的類簇特征向量lGVi，根據該特征向量對應的其他特征分量計算該軌跡的相對距離d_l、速度轉角距離d_sa，見式（14）—（15）。

去除噪聲數據和聚類異常數據后，通過計算訓練數據集中軌跡數據與類簇特征向量的距離，生成各個距離閾值，實現對異常軌跡的識別與評估。

2 船舶異常檢測實驗分析

2.1 實驗數據

本實驗選取2019 年1 月1 日的AIS 數據作為訓練集，設置美國西海岸、美國東海岸和墨西哥灣3 個實驗區域進行分析。

由圖4 可以看出，美西和美東均分布有較多較為重要的港口，這2 個區域的客船和貨船占比相對較多，分別為35.45%和28.24%。墨西哥灣北部為佛羅里達半島，人口密度較大，該區域的船舶分布較為密集，且游艇占比較大。特殊船舶包含各種水上或水下作業船舶，如引航、搜救、挖掘、潛水等，墨西哥灣的淺大陸棚區蘊藏大量的石油和天然氣，該區域特殊船舶占比較高。船舶分布與地區地理環境具有很高的相關性，根據某地區的船舶類型分布可以推論該地區的地理環境特征。

圖4 實驗區域船舶類型分布Fig.4 Vessel type distribution in the experimental area

2.2 數據預處理

原始AIS 軌跡數據共7 516 408 條，包含船舶13 115 艘。經過數據清洗和預處理后的AIS 軌跡數據共7 515 892 條，提取靜止點615 977 個。根據設定的速度閾值篩選靜止點以及航向發生重大變化的點作為斷點對軌跡段進行劃分，保留所有軌跡長度在10 以上的軌跡段，得到軌跡段為5 812 條，包含船舶4 740 艘。

為了確保結果的準確性與有效性，使用過濾法結合隨機森林模型對特征進行組合選擇，以得到最佳特征組合。進行了多組對比實驗，每組實驗迭代運行5次以消除隨機性，實驗結果如表1 所示。根據實驗結果最終保留經緯度、報告轉角以及報告速度的最大值、最小值、中位數和均值信息作為最終特征組合。

表1 軌跡特征組合評估Tab.1 Trajectory feature combination evaluation

2.3 聚類分析

由于軌跡數據無標簽，為了驗證聚類方法的精確性和普適性，選取4 個經典的具有不同維度特征的UCI 數據集進行聚類分析，評估DR–DBSCAN 算法解決實際問題的能力。綜合考慮內部和外部聚類評估標準構建算法評價體系，通過屬性數以及類別數的變化，觀察相對變化下算法的聚類性能。數據集在不同算法下的聚類指標對比信息見表2。

從 3 個外部聚類指標F1、ARI和NMI來看，DR–DBSCAN 在4 個數據集上均有較好得分，明顯優于其他幾種算法，但內部聚類指標DBI評估結果相對較差。說明本文算法DR–DBSCAN 能深入挖掘數據內部特征，而不是單純從點跡的空間分布上挖掘信息，因此能在數據分布較為離散的情況下，實現較高的分類準確度。綜合實驗結果分析，本文算法DR–DBSCAN 通過數據集低維嵌入特征層的構建，深入挖掘數據集特征分布特性，能夠得到更符合數據特性的密度閾值。本文算法相較于一般的密度聚類方法，在實現參數自適應的同時能較好地處理多維數據集，在幾個密度分布不均勻的多維數據集上均有較好的表現。

異常檢測的實質就是學習一般行為模式，發現與一般模式相異的數據。DR–DBSCAN 算法能根據數據特征，擬合數據分布特性，構建數據分布一般模式的類簇，從而可以實現異常數據的識別。

在3 個試驗區中，美國西海岸區域包含軌跡數據897 條；墨西哥灣區域包含軌跡2 033 條；美國東海岸區域包含軌跡數據1 027 條。根據隨機森林分類器所構建的軌跡數據特征組合，對3 個實驗區域的軌跡段進行聚類，去除掉無法聚類的噪聲點或異常軌跡，聚類結果與船舶類型分布較為類似。根據每個區域的聚類結果，劃分網格并提取類簇特征向量，計算距離閾值。3 個區域的位置距離閾值分別為美國西海岸2.249 27、墨西哥灣1.805 97、東海岸1.740 78；速度方向距離閾值分別為美國西海岸1.777 7、墨西哥灣1.952 8、東海岸1.705 02。

2.4 異常檢測

根據聚類結果獲取相應區域的距離閾值，將軌跡點超出閾值范圍的視為異常點。對于一條軌跡，當異常點占比超過70%，則該軌跡視為異常軌跡。選取2019 年1 月1 日的AIS 數據進行異常檢測，經過數據劃分后，根據距離閾值判斷異常軌跡點。經過距離計算和異常判定，美國西海岸軌跡數據898 條，檢測出異常軌跡57 條，其中速度或方向異常速度的軌跡19 條，位置異常軌跡38 條；墨西哥灣軌跡數據2 160條，檢測出異常軌跡60 條，其中速度或方向異常速度的軌跡17 條，位置異常軌跡43 條；美國東海岸軌跡數據1 054 條，檢測出異常軌跡45 條，其中速度或方向異常速度的軌跡23 條，位置異常軌跡312 條。

美國西海岸和美國東海岸區域沿岸為主要航道，美西向東為內河流域，向西為大西洋；美東向西為內河流域，向東為太平洋，二者內河與沿岸區域航道明顯，大洋區域軌跡較為離散。墨西哥灣區域內河流域和離港航線分布較為清晰，但在中部區域軌跡分布較為雜亂。異常檢測通過計算距離閾值，將超出閾值范圍的判定為異常。位置異常可以解釋為分布明顯偏離航道的軌跡，或同一艘船舶短時間內位置出現顯著飄移等情況。將行駛方向與一般軌跡不一致或突然發生較大轉向或速度變動的軌跡標記為速度方向異常；將軌跡方向與周圍軌跡相異的視為方向異常；將軌跡發生較大轉向的可視為轉向異常。2 種方向異常都可以由軌跡分布和軌跡形狀進行判斷。

3 結語

本文提出了一種基于降維密度聚類的船舶異常軌跡識別方法。利用隨機森林分類器對軌跡多維特征的重要性進行評估，構建軌跡特征的最優特征組合?；贒R–DBSCAN 聚類算法對歷史AIS 數據進行聚類分析，學習船舶的一般行為模式構建船舶類簇特征向量并計算距離閾值。在保證聚類精度的前提下，有效提高了聚類效率，減少了調參過程中對人工的依賴。采用4 種經典UCI 數據集驗證DR–DBSCAN 算法的精確度和有效性，并使用2019 年1 月1 日的真實航跡數據在3 個不同的實驗區域進行分析，以減少水文地理環境對方法有效性與準確性的干擾。結果表明，該方法能夠有效檢測出船舶的位置異常、速度方向異常，對加強船舶交通行為分析和船舶交通監管具有重要意義。由于硬件設施限制，本文選取數據集時空范圍較小，對多種類型的異常劃分和定義不夠詳細。未來可以進一步修改模型架構在更大區域進行驗證，更為明確地劃分各種類型的異常，并將模型拓展至陸空交通運輸領域，更好地分析判斷不同的軌跡異常行為，為海陸空運輸及交通管理提供數據支撐。