基于軌跡點聚類的航路發(fā)現(xiàn)方法

劉海楊，孟令航，林仲航，谷源濤

（清華大學(xué)電子工程系，北京 100084）

0 引言

通過對海量歷史軌跡數(shù)據(jù)進行深度挖掘，發(fā)現(xiàn)未掌握的飛行器航路，進而掌握飛行器的運動規(guī)律，是統(tǒng)籌規(guī)劃全局空域交通管制的基礎(chǔ)，同時也是異常軌跡預(yù)警的關(guān)鍵。

學(xué)術(shù)界關(guān)于航路發(fā)現(xiàn)的研究大多是針對浮動車輛的GPS（Global Positioning System）軌跡數(shù)據(jù)，目前，未搜集到航路發(fā)現(xiàn)相關(guān)的研究。

基于浮動車輛GPS 軌跡數(shù)據(jù)的路網(wǎng)提取方法可以分為4類：

1）聚類方法。對軌跡點或線進行聚類，如Edelkamp等［1］、Schroedl等［2］利用K-means算法對軌跡進行聚類，采用樣條曲線擬合道路中心線來提取路網(wǎng)；Worrall 等［3］對軌跡點進行聚類，同時考慮方向角因素，鏈接各個節(jié)點提取路網(wǎng)；米春蕾等［4］、王冬等［5］對數(shù)據(jù)進行網(wǎng)格化后采用聚類方法，通過鏈接骨架節(jié)點或擬合中心線的方式，得到路網(wǎng)幾何數(shù)據(jù)。

2）Delaunay 三角網(wǎng)法。楊偉等［6］、唐爐亮等［7］對軌跡線構(gòu)建約束三角網(wǎng)來提取路網(wǎng)。

3）基于柵格化和核密度估計的圖像處理方法。Shi等［8］、李俊杰等［9］對軌跡數(shù)據(jù)進行柵格化處理；Biagioni 等［10］采用核密度估計將軌跡數(shù)據(jù)轉(zhuǎn)換為圖像，然后采用圖像處理［11］相關(guān)手段提取路網(wǎng)。

4）增量合并方法。Zhang 等［12］、Bruntrup 等［13］、Cao 等［14］主要是根據(jù)已有路網(wǎng)和新的軌跡數(shù)據(jù)對路網(wǎng)進行更新。

飛行器飛行軌跡數(shù)據(jù)與浮動車輛的軌跡數(shù)據(jù)有著明顯差異：浮動車輛均按照現(xiàn)實存在的道路行駛，行駛線路較簡單；而飛行器的航路是抽象的，且飛行軌跡較復(fù)雜，前述基于浮動車輛GPS 軌跡數(shù)據(jù)的路網(wǎng)提取研究成果各有優(yōu)點，但無法充分利用飛行器運動軌跡的特點和解決軌跡采樣率不同、高噪聲的問題，直接應(yīng)用于飛行器航路發(fā)現(xiàn)時性能不佳。存在的主要問題如下：

1）雖然眾多研究成果對“直線”型航路段的提取效果較好，但對于“圓”狀航路結(jié)構(gòu)和多分支的交叉路口結(jié)構(gòu)的提取效果欠佳。“圓”狀航路結(jié)構(gòu)容易提取為“點”結(jié)構(gòu)，多分支結(jié)構(gòu)中的部分夾角較小的分支容易被合并。

2）點、線聚類方法對采樣率和噪聲要求比較嚴格。

3）Delaunay 三角網(wǎng)、柵格化與核密度估計方法提取航路時，道路段呈鋸齒狀。

4）增量合并方法主要用于對航路的更新，而且對噪聲敏感。

因此，本文設(shè)計了一種基于軌跡點聚類的航路發(fā)現(xiàn)方法，旨在解決飛行器軌跡數(shù)據(jù)采樣率不同、高噪聲問題的同時，改善對特殊航路結(jié)構(gòu)的提取效果。

1 技術(shù)路線與主要方法

本文設(shè)計了一種抗噪魯棒、易于實現(xiàn)的基于聚類的航路數(shù)據(jù)提取方法，具體步驟為：

1）對軌跡數(shù)據(jù)進行預(yù)處理，包括離群點剔除和卡爾曼濾波；

2）對預(yù)處理后的軌跡數(shù)據(jù)進行重采樣，使軌跡數(shù)據(jù)的采樣密度基本一致；

3）對軌跡數(shù)據(jù)點進行聚類，得到航路節(jié)點（聚類中心）；

4）對航路節(jié)點進行修正，降低航路節(jié)點的冗余度；

5）根據(jù)軌跡數(shù)據(jù)點的連接關(guān)系，將航路節(jié)點進行連接，形成航路幾何數(shù)據(jù)。

1.1 軌跡預(yù)處理

本文涉及的軌跡數(shù)據(jù)由大量離散軌跡數(shù)據(jù)點組成，并存儲在數(shù)據(jù)庫中。軌跡數(shù)據(jù)點包括軌跡序號、經(jīng)度、緯度、時間4 項有效屬性。由于各種因素的影響，在數(shù)據(jù)庫中存儲的軌跡數(shù)據(jù)存在噪聲和離群點，導(dǎo)致數(shù)據(jù)無法直接使用。針對軌跡數(shù)據(jù)中存在的噪聲和離群點，本文提出了如下解決方案。

1.1.1 離群點剔除

采用一種自適應(yīng)閾值法對離群點進行剔除操作。由經(jīng)度、緯度和時間計算軌跡點的平均速度，采用基于數(shù)理統(tǒng)計中的3σ 原則，對平均速度大于閾值的軌跡點進行剔除。

1）閾值初始化。根據(jù)式（1）計算出整條軌跡各個采樣點的平均速度。由于中值對噪聲不敏感，所以本文以平均速度的中值乘以一個增益系數(shù)η來初始化閾值。

式中：vi是pi點的速度，E0為初始化閾值，(xi，yi)為軌跡中第i個軌跡點pi的坐標，ti為軌跡點pi對應(yīng)的時間。

2）由于當(dāng)前軌跡點的運動狀態(tài)與相鄰軌跡點的運動狀態(tài)有一定的相關(guān)性，本文采用滑窗法對整條軌跡的采樣點進行判斷和剔除。該部分分為兩階段：

①窗未滿時，以初始化閾值為判斷依據(jù)。

式中：pi為軌跡的采樣點，當(dāng)pi=正常點時，pi進入滑窗；否則，將pi從軌跡中刪除。

②窗滿時，根據(jù)3σ 原則，對窗內(nèi)軌跡點的平均速度計算閾值。

式中：E為閾值，meanwin為窗內(nèi)平均速度，varwin為窗內(nèi)速度標準差。

當(dāng)vi>E，pi=離群點，進行剔除；否則，窗體滑動，將窗體中最舊的點移除窗體，令當(dāng)前點進入窗體，直至整條軌跡結(jié)束。

1.1.2 濾噪平滑

采用卡爾曼濾波對軌跡數(shù)據(jù)進行平滑處理，達到消除軌跡數(shù)據(jù)中部分誤差、平滑軌跡的效果。

1.2 基于軌跡點聚類的航路節(jié)點提取

1.2.1 孤立點剔除

Van Winden 等［15］通過統(tǒng)計分析得出結(jié)論：同一道路上的軌跡點到道路中心線的距離近似遵循高斯分布。軌跡預(yù)處理僅降低了軌跡數(shù)據(jù)的噪聲影響，但噪聲仍存在。由于部分軌跡數(shù)據(jù)中會存在孤立點，偏離航空主干道路的情況，為進一步降低對航路節(jié)點提取的影響，本文采用DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法［16］對軌跡數(shù)據(jù)點進行深度去噪處理。該算法不僅能夠?qū)壽E數(shù)據(jù)點進行聚類，且對噪聲不敏感，能處理非凸數(shù)據(jù)，較好地識別孤立點。

定義 孤立點。距離航路中心線較遠且稀疏的點，如圖1 所示。

圖1 孤立點示意圖Fig.1 Schematic diagram of isolated point

設(shè)軌跡{pi，1，pi，2，…，pi，n}，其中pi，j為第i條軌跡的第j個軌跡點，軌跡集合I={T1，T2，…，Tm}，軌跡點集合S={p1，1，p1，2，…，pm，n}。

1）對軌跡點集合S進行DBSCAN 聚類并設(shè)置合適的eps和Minpts，可得到聚類結(jié)果S1，S2，…，Sk，S-1，其中，S-1為孤立點集合，其余聚類結(jié)果視為有效點。

2）將孤立點集合S-1中的軌跡點從軌跡集合I中的軌跡T中剔除。

1.2.2 軌跡重采樣

在歷史軌跡數(shù)據(jù)庫中，軌跡數(shù)據(jù)的采樣時間間隔不統(tǒng)一，且同一軌跡的采樣點的距離間隔也不同，所以本文采用軌跡重采樣的方法，能消除采樣時間間隔不統(tǒng)一造成的軌跡點的空間密度不同帶來的影響，保證各條軌跡數(shù)據(jù)的軌跡點密度基本一致。該步驟的實現(xiàn)是為了1.2.3 節(jié)中的軌跡點聚類做好數(shù)據(jù)基礎(chǔ)。具體算法如下：

1.2.3 軌跡點聚類

對數(shù)據(jù)庫中的歷史數(shù)據(jù)進行處理后得到的每條軌跡大致為等距離采樣點，換言之，所有的軌跡數(shù)據(jù)點的密度較均勻，本文采用mini batchK-means 聚類對所有的軌跡采樣點進行聚類，根據(jù)數(shù)據(jù)規(guī)模和覆蓋面積，設(shè)定合適的聚類中心個數(shù)，經(jīng)過聚類后，聚類中心能夠較好地反映出軌跡的航路結(jié)構(gòu)，得到航路節(jié)點G={C1，C2，…，Cn}。

1.3 對航路節(jié)點修正

對航路節(jié)點進行提取后，由于上述聚類方法選取聚類中心個數(shù)的原因，會存在航路節(jié)點分裂現(xiàn)象，即兩個或多個節(jié)點之間的距離較近，本文采用基于密度的聚類方法，對航路節(jié)點進行合并，得到新的航路節(jié)點集合G′={C′1，C′2，…，C′n′}，并對軌跡數(shù)據(jù)點pi所屬的節(jié)點簇類進行相應(yīng)的修改，如圖2所示。

圖2 航路節(jié)點修正示意圖Fig.2 Schematic diagram of route node amendment

1.4 航路節(jié)點連接

根據(jù)1.3 節(jié)可得到航路節(jié)點，將航路節(jié)點視為聚類中心，那么每條軌跡Ti={pi，1，pi，2，…，pi，n}的軌跡點pi，j(1≤j≤n)都含有各自的所屬類別，本文將軌跡Ti映射到航路節(jié)點集合中，每條軌跡就可由Ti={pi，1，pi，2，…，pi，n}轉(zhuǎn)換為由航路節(jié)點集合中的元素構(gòu)成的序列為Ti={C′k1，C′k2，…，C′kn}，其中：{pi，1，pi，2，…，pi，m}∈C′k1，{pi，m+1，pi，m+2，…，pi，m+l}∈C′ki，{pi，m+l+1，pi，m+l+2，…，pi，n}∈C′kn。

軌跡點pi映射到航路節(jié)點集合的原則：

式中：distance(p，C)為軌跡點p和航路節(jié)點C的歐氏距離。

將所有歷史軌跡映射為航路節(jié)點集合中的元素序列后，遍歷數(shù)據(jù)庫中的所有軌跡，可以得到整個航路節(jié)點的連接關(guān)系，進而得到航路幾何數(shù)據(jù)。

2 實驗與結(jié)果分析

2.1 實驗數(shù)據(jù)集

本文根據(jù)真實軌跡的運動特征和數(shù)據(jù)特點，生成仿真數(shù)據(jù)用于實驗。在生成仿真數(shù)據(jù)時，進行添加噪聲、離群點、軌跡斷裂等處理，使仿真數(shù)據(jù)盡可能逼近真實數(shù)據(jù)。實驗數(shù)據(jù)包括不同噪聲強度的軌跡數(shù)據(jù)，每種噪聲強度下包括4 800條軌跡。實驗數(shù)據(jù)集共有2 296 660 個軌跡數(shù)據(jù)點，每個軌跡點包括經(jīng)度、緯度、時間等屬性。實驗數(shù)據(jù)集如圖3 所示。

圖3 實驗數(shù)據(jù)集Fig.3 Experimental data set

2.2 實驗結(jié)果分析

對實驗數(shù)據(jù)集進行預(yù)處理（如圖4 所示）后，通過對孤立點剔除（如圖5 所示），軌跡重采樣、軌跡點聚類和對航路節(jié)點的修正與連接，得到航路集合數(shù)據(jù)。針對實驗數(shù)據(jù)集，本文設(shè)定聚類中心個數(shù)為300，為了對航路節(jié)點的提取效果進行評價，本文以仿真生成實驗軌跡數(shù)據(jù)使用的航路結(jié)構(gòu)作為參考，將本文的實驗結(jié)果與參考航路進行疊加對比分析。

圖4 軌跡預(yù)處理前后對比Fig.4 Comparison of trajectories before and after preprocessing

圖5 孤立點剔除效果Fig.5 Visualization of isolated point removal

2.2.1 定性評價

圖6（a）為本文方法的疊加分析圖。從整體結(jié)果來看，本文方法提取的航路節(jié)點基本覆蓋了參考航路，并且準確度較高；但對局部結(jié)果觀察發(fā)現(xiàn)，連接航路節(jié)點的過程中，部分航路會出現(xiàn)錯誤連接的情況，這主要是由于軌跡數(shù)據(jù)中存在的噪聲的影響，使得軌跡數(shù)據(jù)點向航路節(jié)點集合中映射出現(xiàn)偏差，導(dǎo)致錯誤連接。

圖6 兩種方法航路發(fā)現(xiàn)結(jié)果對比Fig.6 Comparison of results of two route discovery methods

2.2.2 定量評價

為了定量評價本文方法的實驗結(jié)果，將本文實驗結(jié)果與柵格化方法［8］的實驗結(jié)果分別與參考航路進行匹配，然后引用文獻［12］提出的緩沖區(qū)檢測方法，分別建立10 km、20 km、30 km 的緩沖區(qū)，對兩種方法提取的航路節(jié)點的覆蓋率α和航路長度的覆蓋率β進行性能評價。具體評價函數(shù)如下所示：

式中：pi為航路節(jié)點，N為航路節(jié)點總數(shù)，linei為提取的航路中第i段軌跡段在參考航路緩沖區(qū)的部分，LINEi為提取的航路中第i段軌跡段。

如圖7 和圖8 所示，本文方法提取的航路數(shù)據(jù)在節(jié)點覆蓋率和長度覆蓋率上有較大提高，特別是在10 km 的緩沖區(qū)內(nèi)的實驗結(jié)果。對單一路段的提取，兩種方法的提取效果比較相近，但對于兩條航路夾角較小的交匯路口處，柵格化方法易提取成為一條航路；對“圓”狀航路結(jié)果容易誤提取為點結(jié)構(gòu)。相較于柵格化方法，本文方法能夠在保持提取平滑航路準確率的基礎(chǔ)上，更好地提取“圓”狀航路結(jié)構(gòu)和夾角較小的兩條航路的航路結(jié)構(gòu)，有較好的抗噪性。

圖7 本文方法與柵格化方法的節(jié)點覆蓋率對比Fig.7 Comparison of node coverage between two methods

圖8 本文方法與柵格化方法的長度覆蓋率對比Fig.8 Comparison of length coverage between two methods

2.3 方法驗證

本文方法的有效性已在真實數(shù)據(jù)集上得到驗證，由于真實數(shù)據(jù)不便公開引用，所以本文對22 類民航軌跡數(shù)據(jù)進行航路提取來驗證本文方法的有效性。軌跡數(shù)據(jù)可視化如圖9（a）所示，航路提取結(jié)果如圖9（b）所示。根據(jù)民航數(shù)據(jù)的航路發(fā)現(xiàn)結(jié)果可知，本文方法能夠較好地發(fā)現(xiàn)航路，但存在一定的局限性，當(dāng)某條航路或航路段上的軌跡數(shù)目稀少時，該航路或航路段上的軌跡易被檢測為孤立點進行剔除，因此漏掉部分航路。

圖9 民航軌跡數(shù)據(jù)實驗結(jié)果Fig.9 result of civil aviation data set

3 結(jié)語

為了快速準確地從航空軌跡數(shù)據(jù)中提取航路的幾何數(shù)據(jù)，本文提出了一種基于軌跡點聚類的航路提取方法，利用航空軌跡模擬數(shù)據(jù)進行實驗分析，以模擬數(shù)據(jù)的理想航路為參考數(shù)據(jù)，與柵格化方法進行定性定量分析評價，結(jié)果表明本文方法提取的航路數(shù)據(jù)在節(jié)點覆蓋率和航路長度覆蓋率上都有明顯提高，而且本文方法易于實現(xiàn)，有一定的有效性和可靠性。

本文方法提取的航路節(jié)點，可將軌跡數(shù)據(jù)映射為節(jié)點序列，進而可將軌跡預(yù)測問題轉(zhuǎn)化為序列到序列的序列預(yù)測問題。為提高預(yù)測問題的正確率，需進一步研究和完善：1）軌跡數(shù)據(jù)映射到節(jié)點集合中的更有效的方法；2）各個航空路段的軌跡數(shù)據(jù)的密度相差較懸殊的情況，本文方法還需要進一步改進；3）由于噪聲的影響，連接航路節(jié)點時會有誤連的情況，下一步需對連接節(jié)點的方法進行進一步研究。