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

閆婕妤 夏沭濤 董 凱 王子玲

（1.91001部隊(duì) 北京 100841）（2.海軍航空大學(xué)信息融合研究所 煙臺(tái) 264000）

1 引言

當(dāng)前，我國(guó)已具備全球大范圍海域的目標(biāo)監(jiān)視能力［1］。海量的目標(biāo)監(jiān)視數(shù)據(jù)具有豐富的研究?jī)r(jià)值，以目標(biāo)監(jiān)視數(shù)據(jù)中的航跡信息為數(shù)據(jù)源，利用聚類技術(shù)對(duì)目標(biāo)航行規(guī)律進(jìn)行挖掘，對(duì)于提升海域的態(tài)勢(shì)感知能力具有重要意義。海上交通量迅猛增長(zhǎng)，從大量的海上交通軌跡數(shù)據(jù)中挖掘規(guī)律對(duì)于智能化的處理水平提出了新的要求。通過(guò)航跡聚類，提取出海域中船舶的主要航路信息，用于規(guī)范船舶的航行，為海事監(jiān)管以及船舶交通管理系統(tǒng)提供支持［2］。

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

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

2 航跡特征建模

2.1 航跡表示

一條航跡可以表示為

式中Traji表示第i條航跡，Pij為(xij，yij)，代表航跡Traji中的第j個(gè)點(diǎn)跡，xij為橫坐標(biāo)，yij為縱坐標(biāo)，n代表航跡Traji中包含的航跡點(diǎn)個(gè)數(shù)。

2.2 特征建模

對(duì)航跡進(jìn)行聚類是將航行規(guī)律相似的航跡聚為同簇，相異的航跡聚為不同簇，因此在對(duì)航跡的特征進(jìn)行建模時(shí)，應(yīng)尋找簇內(nèi)航跡相似并且簇間航跡相異的特征。航跡的相似性表現(xiàn)在兩個(gè)方面，一是幾何形狀的相似性，二是絕對(duì)位置的相似性?？紤]圖1 中的航跡示例，共包含三簇航跡A、B、C，每簇包含兩條航跡。同簇航跡間的幾何形狀相似，而異簇航跡間的幾何形狀具有明顯差異。另一方面，B 簇和C 簇航跡的幾何形狀也相似，但是由于絕對(duì)位置具有明顯差異而異簇。

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

利用航跡的位置坐標(biāo)來(lái)反映航跡的位置特征，利用航向來(lái)反映航跡的幾何形狀特征。為準(zhǔn)確刻畫特征差異，對(duì)航跡的橫坐標(biāo)和縱坐標(biāo)分別取五類統(tǒng)計(jì)量，分別為最小值、最大值、均值、上四分位數(shù)、下四分位數(shù)，作為第1到第10個(gè)特征量：

式中，表示上四分位數(shù)，表示下四分位數(shù)。

對(duì)航向值也如此操作，創(chuàng)建第11 到第15 個(gè)特征量：

為了反映在不同位置處的航向，嘗試將位置信息與航向信息聯(lián)系起來(lái)，計(jì)算每個(gè)航跡點(diǎn)處的位置坐標(biāo)與航向之積：xijyijcij，j?[1，n-1]，同樣對(duì)此積取上述五類統(tǒng)計(jì)量，創(chuàng)建第16到第20個(gè)特征量：

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

對(duì)間隔值取均值作為第21個(gè)特征量：

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

3 聚類算法

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

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

4.1 仿真數(shù)據(jù)集

采用Piciarelli［14］公開的仿真數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，圖2為兩個(gè)數(shù)據(jù)集，每個(gè)數(shù)據(jù)集包含5個(gè)簇，每個(gè)簇包含50 條航跡，每條航跡包含16 個(gè)航跡點(diǎn)。5 個(gè)簇代表5種航行規(guī)律。

圖2 數(shù)據(jù)集

4.2 特征篩選與可視化分析

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

圖3 特征量貢獻(xiàn)度

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

圖4 數(shù)據(jù)集特征可視化

4.3 聚類實(shí)驗(yàn)

對(duì)航跡提取特征后，將原始的航跡矩陣轉(zhuǎn)化為了特征空間中的特征點(diǎn)，采用經(jīng)典的歐式距離為度量準(zhǔn)則，利用分層聚類算法對(duì)航跡進(jìn)行聚類?？梢酝ㄟ^(guò)設(shè)置最大聚類簇?cái)?shù)實(shí)現(xiàn)不同層級(jí)的聚類，圖5為兩個(gè)數(shù)據(jù)集在簇?cái)?shù)等級(jí)為5 時(shí)的聚類效果，每種顏色表示一簇，可見(jiàn)建模特征可以準(zhǔn)確體現(xiàn)不同簇航跡間的差異，可以利用歐式距離進(jìn)行度量實(shí)現(xiàn)聚類。在圖6中，簇?cái)?shù)等級(jí)設(shè)置為3，依然可以滿足聚類需求，實(shí)現(xiàn)分層聚類效果，簇?cái)?shù)等級(jí)可根據(jù)實(shí)際需求進(jìn)行設(shè)定，簇?cái)?shù)等級(jí)為本實(shí)驗(yàn)參數(shù)，參數(shù)意義更加接近工程需求層面。

圖5 聚類結(jié)果1

圖6 聚類結(jié)果2

4.4 對(duì)比實(shí)驗(yàn)

本節(jié)將所提方法與流行的基于Hausdorff 度量的密度聚類進(jìn)行對(duì)比，選取的指標(biāo)為輪廓系數(shù)與運(yùn)行時(shí)間。輪廓系數(shù)是刻畫同簇內(nèi)聚性和異簇分離性的重要指標(biāo)，計(jì)算公式為

式中，ai和bi的計(jì)算公式分別為

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

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

表1 算法性能比較

5 結(jié)語(yǔ)

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