基于K-means 聚類的通航協(xié)同空域規(guī)劃算法設(shè)計(jì)和實(shí)現(xiàn)

何 聰，王彥成，馮 軍，姜 山，李兆陽

（四川九洲空管科技有限責(zé)任公司，四川 綿陽 621000）

低空協(xié)同空域的合理劃設(shè)是高效通航、安全運(yùn)行運(yùn)營的基礎(chǔ)。當(dāng)前低空協(xié)同空域的規(guī)劃主要由通航企業(yè)主體單位的各自規(guī)模、運(yùn)營范圍和各地區(qū)低空辦專家的經(jīng)驗(yàn)值共同決定，因此劃設(shè)的某些空域存在運(yùn)用頻次低，未覆蓋高頻率使用的空域范圍等問題?？沼蚍诸惒豢茖W(xué)，航路航線劃設(shè)缺乏規(guī)范，低空監(jiān)視、報(bào)告空域數(shù)量少、范圍小，呈“孤島”狀分布，空域使用多偏重于靜態(tài)控制，缺乏靈活性，難以滿足通用航空用戶的需求[1-2]。

目前，大部分地區(qū)的低空中心都建設(shè)了ADSB 地面監(jiān)視站或引入空管局的監(jiān)視數(shù)據(jù)，能夠?qū)崟r(shí)掌握各個(gè)協(xié)同空域以及周邊空域的飛行態(tài)勢，同時(shí)具備歷史數(shù)據(jù)存儲和回放的能力，因此針對歷史ADS-B 數(shù)據(jù)可以進(jìn)行相應(yīng)的數(shù)據(jù)挖掘，得出潛在的運(yùn)行規(guī)律；但目前國內(nèi)外在通航產(chǎn)業(yè)中通過大數(shù)據(jù)處理算法進(jìn)行空域規(guī)劃的研究相對較少，存在很大的提升空間。

綜上所述，本文提出一種通過K-means 聚類的通航協(xié)同空域規(guī)劃算法，通過對歷史ADS-B 監(jiān)視數(shù)據(jù)進(jìn)行特征提取識別、數(shù)據(jù)轉(zhuǎn)換、數(shù)據(jù)聚類、空域生成等處理，生成聚類形成的協(xié)同空域范圍，以期為低空空域規(guī)劃改進(jìn)提供輔助決策建議。

1 飛行軌跡數(shù)據(jù)處理

1.1 飛行軌跡數(shù)據(jù)獲取

本研究中所分析的ADS-B 監(jiān)視數(shù)據(jù)均來源于四川省低空空域協(xié)同運(yùn)行中心飛行態(tài)勢監(jiān)視系統(tǒng)。

中心記錄的歷史報(bào)文包括CAT021 報(bào)文和各個(gè)站點(diǎn)工作的狀態(tài)報(bào)文，需在提取數(shù)據(jù)時(shí)增加數(shù)據(jù)過濾準(zhǔn)則，即濾除狀態(tài)報(bào)文，只對符合標(biāo)準(zhǔn)的CAT021報(bào)文進(jìn)行解析，獲取歷史ADS-B 點(diǎn)跡數(shù)據(jù)。

1.2 飛行軌跡數(shù)據(jù)特征識別與分類

由于研究的空域規(guī)劃范圍主要針對低空通用航空器，因此需對解析后的歷史ADS-B 點(diǎn)跡數(shù)據(jù)進(jìn)行分類和識別，提取出滿足低空通用航空器飛行規(guī)律的點(diǎn)跡數(shù)據(jù)。

低空空域原則上是指全國范圍內(nèi)真高1 000 m（含）以下區(qū)域，山區(qū)和高原地區(qū)可根據(jù)實(shí)際需要[3]而定。2016 年，國務(wù)院辦公廳印發(fā)的《關(guān)于促進(jìn)通航業(yè)發(fā)展的指導(dǎo)意見》，首次從全產(chǎn)業(yè)鏈角度對通航進(jìn)行頂層設(shè)計(jì)，提出擴(kuò)大低空空域真高至3 000 m[4]。因此，本研究需提取出飛行高度在3 000 m 以下的ADS-B 點(diǎn)跡數(shù)據(jù)。

同時(shí)，需對航空器監(jiān)視數(shù)據(jù)的航班號（通航呼號）進(jìn)行區(qū)分，目前國內(nèi)雖沒有制定通用航空器呼號準(zhǔn)則，但行業(yè)中已經(jīng)默認(rèn)通用航空器航班號/呼號以B 開頭。

可以得出歷史通航ADS-B 點(diǎn)跡集合滿足以下公式的過濾準(zhǔn)則：

式中：P為過濾后的ADS-B 點(diǎn)跡集合；h為點(diǎn)跡高度（m）；n為 點(diǎn)跡航班號/呼號；lat為點(diǎn)跡緯度；lon為點(diǎn)跡經(jīng)度；t為目標(biāo)ADS-B 廣播時(shí)間。

1.3 飛行軌跡數(shù)據(jù)清洗與轉(zhuǎn)換

數(shù)據(jù)清洗主要針對重復(fù)的ADS-B 監(jiān)視點(diǎn)跡數(shù)據(jù)，由于低空中心建設(shè)了多個(gè)ADS-B 地面監(jiān)視站，因此會出現(xiàn)多站同時(shí)監(jiān)測到同一飛機(jī)廣播的軌跡數(shù)據(jù)，因此需要聯(lián)合時(shí)間、位置和S 模式地址進(jìn)行去重操作。

研究中需對歷史軌跡點(diǎn)進(jìn)行K-means 聚類，因此需將清洗后的點(diǎn)跡集合轉(zhuǎn)換成可以進(jìn)行聚類的帶時(shí)間、位置屬性的矩陣數(shù)據(jù)，且矩陣中的內(nèi)容轉(zhuǎn)換成全數(shù)字格式，可定義為以下矩陣：

式中：X為轉(zhuǎn)換后的軌跡點(diǎn)矩陣，每一行代表每個(gè)軌跡點(diǎn)的詳細(xì)信息，其定義見表1。

表1 軌跡矩陣行元素定義表

1.4 飛行軌跡數(shù)據(jù)處理流程

綜上所述，飛行軌跡數(shù)據(jù)處理流程主要包括數(shù)據(jù)獲取、特征識別與分類、數(shù)據(jù)清洗、數(shù)據(jù)轉(zhuǎn)換，處理流程如圖1 所示。

圖1 飛行軌跡點(diǎn)數(shù)據(jù)處理流程圖

2 K-means 聚類算法簡介

K-means 算法是一種基于劃分的聚類分析方法，指定輸入?yún)?shù)K，然后將原始數(shù)據(jù)集合分組為K個(gè)類簇[2]。它采用距離作為相似性的評價(jià)指標(biāo)，即認(rèn)為兩個(gè)對象的距離越近，其相似度就越大。該算法認(rèn)為類簇是由距離靠近的對象組成的，因此把得到緊湊且獨(dú)立的簇作為最終目標(biāo)。K-means 聚類算法屬于無監(jiān)督學(xué)習(xí)算法。

K-means 聚類算法是一種迭代求解的聚類分析算法，其步驟是隨機(jī)選取K個(gè)對象作為初始的聚類中心，然后計(jì)算每個(gè)對象與各個(gè)種子聚類中心之間的距離，把每個(gè)對象分配給距離它最近的聚類中心。每分配一個(gè)樣本，聚類的聚類中心會根據(jù)聚類中現(xiàn)有的對象被重新計(jì)算，這個(gè)過程將不斷重復(fù)直到滿足某個(gè)終止條件。聚類計(jì)算的終止條件是沒有（或最小數(shù)目）對象被重新分配給不同的聚類，沒有（或最小數(shù)目）聚類中心再發(fā)生變化，誤差平方和局部最小[5]。

K-means 聚類算法一般采用歐式距離作為相似度指標(biāo)，計(jì)算公式如下：

式中：k代表某一次迭代過程中質(zhì)心的數(shù)量；n代表等待計(jì)算的對象數(shù)量。

3 基于K-means 聚類的空域規(guī)劃算法

3.1 K-means 聚類中心的選擇

聚類中心是一個(gè)簇的中心點(diǎn)，滿足簇中其他對象到該中心點(diǎn)的距離和最小。如果數(shù)據(jù)集中某一數(shù)據(jù)對象所處區(qū)域內(nèi)的數(shù)據(jù)對象越多，區(qū)域內(nèi)的其他對象到該對象的距離越小，說明該對象的數(shù)據(jù)密度越大，能夠較好地反映數(shù)據(jù)分布特征[6]。

距離中心的選擇可按照如下步驟進(jìn)行。

1）距離計(jì)算。設(shè)清洗后的歷史飛行軌跡集合為：P={p1,p2,···,pn}，pi=(xi1,xi2)，點(diǎn)跡樣本pi與pj間的歐式距離計(jì)算公式為

2）計(jì)算集合P中所有對象間的平均距離。P中所有對象間的平均距離AveDis(P)的計(jì)算公式如下

3）計(jì)算每個(gè)點(diǎn)跡對象的密度。對象pi的密度計(jì)算公式為

式中：對于相對距離函數(shù)u(x)滿足，當(dāng)

得到各個(gè)點(diǎn)跡對象的密度集合D={De(x1),De(x2),···,De(xn)}。

4）聚類中心選擇。設(shè)置預(yù)定聚類中心數(shù)為K，將集合D中的元素按照從大到小的順序進(jìn)行排序，依次選擇前K個(gè)對象作為初始聚類中心集。

3.2 聚類個(gè)數(shù)的選擇

聚類個(gè)數(shù)的選擇直接決定聚類簇中對象的分散程度，簇內(nèi)對象分散程度越小，簇間的距離越大，聚類效果越好[7]。按照3.1 的步驟選擇每個(gè)簇的中心，隨機(jī)選擇第j個(gè)簇中數(shù)據(jù)對象間的平均距離作為數(shù)據(jù)對象的分散程度，用dpj,m表示，表示第j個(gè)簇和第m個(gè)簇之間的距離，然后重新設(shè)定聚類個(gè)數(shù)K值，計(jì)算每次得到的聚類中心集合的平均分散程度δ，不斷重復(fù)該項(xiàng)操作，直到 δ的取值最小，則獲得最佳聚類個(gè)數(shù)。平均分散程度計(jì)算公式如下：

3.3 K-means 聚類空域規(guī)劃的實(shí)現(xiàn)

本研究中空域規(guī)劃中的K-means 聚類算法的實(shí)現(xiàn)主要通過Python 的sklearn 中的cluster.Kmeans實(shí)現(xiàn)，主要步驟如下所示。

Step1：載入清洗后的歷史飛行軌跡點(diǎn)集合P={p1,p2,···,pn}，pi=(xi1,xi2)。

Step2：輸入預(yù)設(shè)聚類簇?cái)?shù)量K(聚類后的空域數(shù)量)。

Step3：根據(jù)軌跡點(diǎn)集合和初始簇?cái)?shù)量進(jìn)行聚類自適應(yīng)計(jì)算，得到最佳聚類中心數(shù)K’。

Step4：按照最佳聚類中心數(shù)K’進(jìn)行聚類計(jì)算，得到各個(gè)聚類簇中心點(diǎn)和各個(gè)簇的數(shù)據(jù)。

Step5：對聚類后的各個(gè)簇的數(shù)據(jù)進(jìn)行圖形化繪制，得到聚類后生成的各個(gè)空域信息。

4 仿真實(shí)驗(yàn)結(jié)果分析

4.1 實(shí)驗(yàn)數(shù)據(jù)來源

本研究中的數(shù)據(jù)來源于四川省低空空域協(xié)同運(yùn)行中心（簡稱：四川低空運(yùn)行中心）的真實(shí)歷史監(jiān)視數(shù)據(jù)，選取2020 年9 月4 日到2020 年9 月10 日的歷史數(shù)據(jù)作為挖掘?qū)ο?，原始?shù)據(jù)包括大約570 萬個(gè)歷史監(jiān)視軌跡點(diǎn)。

4.2 實(shí)驗(yàn)結(jié)果分析

將轉(zhuǎn)換后的歷史軌跡點(diǎn)進(jìn)行飛行軌跡點(diǎn)特征識別與清洗后，得到的通航歷史飛行軌跡點(diǎn)的數(shù)量為3 963 980 個(gè)，將得到的通航飛行軌跡點(diǎn)進(jìn)行Kmeans 數(shù)據(jù)挖掘，并進(jìn)行自適應(yīng)K值計(jì)算，得到K值在{5,6,7,8}集合中的聚類情況如圖2 所示，同時(shí)展示了根據(jù)通航歷史飛行軌跡點(diǎn)聚類后形成的空域分布。圖2 中橫坐標(biāo)為緯度，縱坐標(biāo)為經(jīng)度。

圖2 不同K 值的聚類空域分布和聚類情況圖

本研究中的聚類質(zhì)量評判分?jǐn)?shù)采用Calinski-Harabaz 分?jǐn)?shù)，指簇間的協(xié)方差矩陣與簇內(nèi)的協(xié)方差矩陣相除，如果前者越大，后者越小，那么分值越大，分類效果越好。

本次研究中，對于聚類后生成的空域數(shù)據(jù)，在不同K值情況下，得到的空域聚類中心位置均不相同，各個(gè)K值情況下，空域中心位置情況見表2。

表2 不同K 值下的空域規(guī)劃結(jié)果

由表2 可知，在不同K值的情況下，對原始數(shù)據(jù)進(jìn)行K-means 聚類操作，形成的空域劃設(shè)分布情況不同。當(dāng)K值等于8 時(shí)，圖2 中各個(gè)空域分布狀態(tài)較好，按照此結(jié)果進(jìn)行空域規(guī)劃結(jié)果合理、科學(xué)。

4.3 結(jié)果優(yōu)勢對比

四川運(yùn)行中心發(fā)布的協(xié)同空域信息信息如圖3所示。

圖3 四川省運(yùn)行中心協(xié)同空域圖

根據(jù)歷史數(shù)據(jù)聚類后形成的高頻飛行空域信息如圖4 所示。

圖4 協(xié)同空域與聚類空域?qū)Ρ葓D

由圖4 可知，聚類空域更靠近川協(xié)4 號的西南側(cè)。從實(shí)際飛行活動中可以得出聚類空域中存在更多的訓(xùn)練和觀光飛行，包含了廣漢和綿陽飛行學(xué)院的飛行訓(xùn)練航路等；因此，由歷史數(shù)據(jù)聚類形成的空域具備更高頻次的低空飛行活動，可為后續(xù)協(xié)同空域的劃設(shè)提供更有力的數(shù)據(jù)支撐，相對于人為經(jīng)驗(yàn)劃設(shè)的空域具備更高效的利用率。

5 小結(jié)

本文制定和設(shè)計(jì)了歷史飛行軌跡點(diǎn)數(shù)據(jù)處理流程和算法，設(shè)計(jì)了K-means 聚類算法流程，建立了基于歷史飛行軌跡點(diǎn)的通航空域規(guī)劃模型和算法流程，并通過真實(shí)歷史數(shù)據(jù)對建立的模型進(jìn)行算法驗(yàn)證和結(jié)論分析。研究的算法和模型對低空通航空域規(guī)劃能夠提供較優(yōu)的輔助決策，并通過Python 環(huán)境進(jìn)行算法實(shí)現(xiàn)，可為后期工程運(yùn)用奠定基礎(chǔ)。