基于特征建模的航行規律挖掘方法?

閆婕妤 夏沭濤 董 凱 王子玲

（1.91001部隊 北京 100841）（2.海軍航空大學信息融合研究所 煙臺 264000）

1 引言

當前，我國已具備全球大范圍海域的目標監視能力［1］。海量的目標監視數據具有豐富的研究價值，以目標監視數據中的航跡信息為數據源，利用聚類技術對目標航行規律進行挖掘，對于提升海域的態勢感知能力具有重要意義。海上交通量迅猛增長，從大量的海上交通軌跡數據中挖掘規律對于智能化的處理水平提出了新的要求。通過航跡聚類，提取出海域中船舶的主要航路信息，用于規范船舶的航行，為海事監管以及船舶交通管理系統提供支持［2］。

船只航跡的聚類研究，是通過度量航跡間的相似度，對相似的航跡進行聚類，提取出目標的運動模式規律［3］。針對這一問題，研究者提出了許多解決方案。陳錦陽等［4］以軌跡子段為單位進行相似性匹配，通過改進hausdorff 度量，消除了軌跡子段之間的公共偏差。Xinlong Pan 等［5］提出了一種多維hausdorff度量方式，有效地提升了hausdorff在多維空間上的度量能力。張春瑋等［6］采用動態時間規整算法來計算航跡之間的相似度，實現了非等長航跡相似度的計算。牟軍敏等［7］基于hausdorff 距離設計了一種具有尺度參數的相似性度量參數，構建相似度矩陣并利用譜聚類算法完成航跡聚類。當前的研究都是在對原始航跡進行相似度度量，航跡空間中的樣本點屬于多維矩陣，直接對多維矩陣進行度量本身具有很大的復雜性，這為度量準則的設計增加了困難。度量方式的精細化設計在提高度量精確性的同時，降低了度量的普適性。同時多參數的引進也難以滿足實際工程應用。

完成航跡聚類的關鍵兩步是度量和聚類。度量對象的空間維度直接影響度量方式的設計難度，而度量方式的精確性直接影響到聚類效果。現有研究很少關注度量對象的轉化，度量對象通常為原始的多維航跡序列矩陣。針對現有技術的局限性，本文提出了一種船只航行規律挖掘方法。從度量對象所在空間入手，通過分析不同航行規律的運動特點，首先將航跡轉化到特征空間進行表示，將原始航跡空間的多維航跡矩陣轉化為特征空間中的點，使同一運動模式的航跡在特征空間中表現出強的內聚性，不同模式的航跡表現強的分離性。從而可以通過經典的歐式距離對航跡進行相似度度量，然后采用分級聚類完成模式挖掘。算法更加具有普適性，更能滿足工程實際需求。

2 航跡特征建模

2.1 航跡表示

一條航跡可以表示為

式中Traji表示第i條航跡，Pij為(xij，yij)，代表航跡Traji中的第j個點跡，xij為橫坐標，yij為縱坐標，n代表航跡Traji中包含的航跡點個數。

2.2 特征建模

對航跡進行聚類是將航行規律相似的航跡聚為同簇，相異的航跡聚為不同簇，因此在對航跡的特征進行建模時，應尋找簇內航跡相似并且簇間航跡相異的特征。航跡的相似性表現在兩個方面，一是幾何形狀的相似性，二是絕對位置的相似性。考慮圖1 中的航跡示例，共包含三簇航跡A、B、C，每簇包含兩條航跡。同簇航跡間的幾何形狀相似，而異簇航跡間的幾何形狀具有明顯差異。另一方面，B 簇和C 簇航跡的幾何形狀也相似，但是由于絕對位置具有明顯差異而異簇。

通過以上分析，建模特征需要反映航跡幾何形狀和絕對位置兩方面特點。原始航跡點包括(xij，yij)兩維數據，首先計算出每個航跡段的航向值：

利用航跡的位置坐標來反映航跡的位置特征，利用航向來反映航跡的幾何形狀特征。為準確刻畫特征差異，對航跡的橫坐標和縱坐標分別取五類統計量，分別為最小值、最大值、均值、上四分位數、下四分位數，作為第1到第10個特征量：

式中，表示上四分位數，表示下四分位數。

對航向值也如此操作，創建第11 到第15 個特征量：

為了反映在不同位置處的航向，嘗試將位置信息與航向信息聯系起來，計算每個航跡點處的位置坐標與航向之積：xijyijcij，j?[1，n-1]，同樣對此積取上述五類統計量，創建第16到第20個特征量：

為反映航向的變化特性，計算航向的間隔值：

對間隔值取均值作為第21個特征量：

特征建模完畢后，利用PCA主成分分析法分析各特征量的重要程度，去除重要程度低的特征量。將保留的特征量組成特征向量，利用t分布-隨機近鄰嵌入（t-distributed stochastic neighbour embedding，t-SNE）算法［8］將特征向量降至二維，得到航跡特征向量的二維表示。至此，完成航跡矩陣向特征空間的轉化，原始航跡矩陣轉化為特征空間的點，對于原始航跡的相似度度量轉化為特征空間點的度量，即可采用經典的歐式距離進行度量。

3 聚類算法

聚類算法較為流行的有分層聚類算法［9］、k-means［10］、k-medoids［11］、具有噪聲的基于密度的軌跡聚類（Density-Based Trajectory Clustering of Applications with Noise，DBTCAN）算法［12］、譜聚類算法［13］等。基于參數設置簡單易控制、工程易實現的原則，本文首先選取了分層聚類算法對航跡進行聚類，目的為了檢驗建模特征對于聚類研究的有效性。利用python 環境中的scipy.cluster.hierarchy 模塊即可實現分層聚類，由于本文通過特征建模將航跡矩陣轉化為了特征點，即可通過歐式距離進行相似性度量，因此在模塊參數中設置度量方式為歐式距離，減輕了度量準則設置的復雜性，算法更具普適性。

4 實驗分析

4.1 仿真數據集

采用Piciarelli［14］公開的仿真數據集進行實驗，圖2為兩個數據集，每個數據集包含5個簇，每個簇包含50 條航跡，每條航跡包含16 個航跡點。5 個簇代表5種航行規律。

圖2 數據集

4.2 特征篩選與可視化分析

通過對聚類任務以及航跡特點的分析，設計了共21 個特征量，而不同特征量的貢獻程度不一定相同，可能存在冗余特征量，因此需要對特征量進行篩選。利用PCA 主成分分析法分析各特征量的重要程度，結果如圖3所示，去除排名靠后的4個特征量，分別是第17、7、20、18個特征量，共保留17個特征量。

圖3 特征量貢獻度

利用t 分布-隨機近鄰嵌入（t-distributed stochastic neighbour embedding，t-SNE）算法［8］將特征向量降至二維，得到特征向量的二維表示。繪制散點圖圖4。圖4 中，每種顏色表示同一簇的航跡樣本，可以看到，同簇航跡表現出強內聚性，不同簇航跡表現出強分離性，初步驗證了建模特征的有效性。

圖4 數據集特征可視化

4.3 聚類實驗

對航跡提取特征后，將原始的航跡矩陣轉化為了特征空間中的特征點，采用經典的歐式距離為度量準則，利用分層聚類算法對航跡進行聚類。可以通過設置最大聚類簇數實現不同層級的聚類，圖5為兩個數據集在簇數等級為5 時的聚類效果，每種顏色表示一簇，可見建模特征可以準確體現不同簇航跡間的差異，可以利用歐式距離進行度量實現聚類。在圖6中，簇數等級設置為3，依然可以滿足聚類需求，實現分層聚類效果，簇數等級可根據實際需求進行設定，簇數等級為本實驗參數，參數意義更加接近工程需求層面。

圖5 聚類結果1

圖6 聚類結果2

4.4 對比實驗

本節將所提方法與流行的基于Hausdorff 度量的密度聚類進行對比，選取的指標為輪廓系數與運行時間。輪廓系數是刻畫同簇內聚性和異簇分離性的重要指標，計算公式為

式中，ai和bi的計算公式分別為

ai表示樣本i與同簇其它樣本距離的平均值，bi表示樣本i與異簇樣本距離的最小值。輪廓系數的取值范圍為[]-1，1，越接近于1 表示同簇內聚性和異簇分離性越優。

此外，本節還對比了利用k-means 以及k-medoids聚類算法的聚類表現。表1為實驗結果，在兩個數據集上，本文所提出的特征構建方法以及Hausdorff度量+密度聚類方法的輪廓系數均較為理想，但是本文方法的輪廓系數均超過基于Hausdorff度量的密度聚類，說明本文建模特征在不同的航行規律之間具有更加優異的判別性，能夠將不同簇的航跡更好地區分開，并且將同簇的航跡內聚在一起。運行時間也大幅降低，本實驗中的運行時間都是從輸入原始航跡數據開始到聚類結束的時間，即本文方法的運行時間包括了航跡特征提取降維的過程。由于直接對原始航跡數據進行Hausdorff 度量，遍歷計算多，導致計算量大，因此運行時間較長。而通過特征建模，在特征空間中直接對特征點進行歐式度量，計算量大幅降低，運行時間減少。更加符合工程需求。此外，利用本文的特征構建方法，分層聚類的運行時間最短；k-means 算法以及k-medoids 算法受初始中心點選擇影響較大，會出現陷入局部最優的情況，k-medoids 算法迭代運算次數較多，計算量大，耗時長，綜合來看，分層聚類在本任務中較優異。

表1 算法性能比較

5 結語

本文針對船只航行規律挖掘，提出了一種基于特征距離聚類方法，并且通過仿真數據以及實測數據進行了驗證。在航跡聚類問題中，研究熱點多集中在度量準則和聚類算法的改進上，精細化的設計與多參數的引入，增加了算法的復雜度，降低了度量的普適性。本文從度量對象的轉化方面入手，通過分析船只的航行規律特點，提出了一套特征建模方案，將對原始航跡矩陣的度量轉化為特征空間中特征點的歐式度量，通過轉化操作，使度量對象的同簇樣本更加內聚，異簇樣本更加分離，提高了聚類的魯棒性。采用歐式距離進行度量，更具普適性。