基于K-means 聚类的通航协同空域规划算法设计和实现

何 聪，王彦成，冯 军，姜 山，李兆阳

（四川九洲空管科技有限责任公司，四川 绵阳 621000）

低空协同空域的合理划设是高效通航、安全运行运营的基础。当前低空协同空域的规划主要由通航企业主体单位的各自规模、运营范围和各地区低空办专家的经验值共同决定，因此划设的某些空域存在运用频次低，未覆盖高频率使用的空域范围等问题。空域分类不科学，航路航线划设缺乏规范，低空监视、报告空域数量少、范围小，呈“孤岛”状分布，空域使用多偏重于静态控制，缺乏灵活性，难以满足通用航空用户的需求[1-2]。

目前，大部分地区的低空中心都建设了ADSB 地面监视站或引入空管局的监视数据，能够实时掌握各个协同空域以及周边空域的飞行态势，同时具备历史数据存储和回放的能力，因此针对历史ADS-B 数据可以进行相应的数据挖掘，得出潜在的运行规律；但目前国内外在通航产业中通过大数据处理算法进行空域规划的研究相对较少，存在很大的提升空间。

综上所述，本文提出一种通过K-means 聚类的通航协同空域规划算法，通过对历史ADS-B 监视数据进行特征提取识别、数据转换、数据聚类、空域生成等处理，生成聚类形成的协同空域范围，以期为低空空域规划改进提供辅助决策建议。

1 飞行轨迹数据处理

1.1 飞行轨迹数据获取

本研究中所分析的ADS-B 监视数据均来源于四川省低空空域协同运行中心飞行态势监视系统。

中心记录的历史报文包括CAT021 报文和各个站点工作的状态报文，需在提取数据时增加数据过滤准则，即滤除状态报文，只对符合标准的CAT021报文进行解析，获取历史ADS-B 点迹数据。

1.2 飞行轨迹数据特征识别与分类

由于研究的空域规划范围主要针对低空通用航空器，因此需对解析后的历史ADS-B 点迹数据进行分类和识别，提取出满足低空通用航空器飞行规律的点迹数据。

低空空域原则上是指全国范围内真高1 000 m（含）以下区域，山区和高原地区可根据实际需要[3]而定。2016 年，国务院办公厅印发的《关于促进通航业发展的指导意见》，首次从全产业链角度对通航进行顶层设计，提出扩大低空空域真高至3 000 m[4]。因此，本研究需提取出飞行高度在3 000 m 以下的ADS-B 点迹数据。

同时，需对航空器监视数据的航班号（通航呼号）进行区分，目前国内虽没有制定通用航空器呼号准则，但行业中已经默认通用航空器航班号/呼号以B 开头。

可以得出历史通航ADS-B 点迹集合满足以下公式的过滤准则：

式中：P为过滤后的ADS-B 点迹集合；h为点迹高度（m）；n为 点迹航班号/呼号；lat为点迹纬度；lon为点迹经度；t为目标ADS-B 广播时间。

1.3 飞行轨迹数据清洗与转换

数据清洗主要针对重复的ADS-B 监视点迹数据，由于低空中心建设了多个ADS-B 地面监视站，因此会出现多站同时监测到同一飞机广播的轨迹数据，因此需要联合时间、位置和S 模式地址进行去重操作。

研究中需对历史轨迹点进行K-means 聚类，因此需将清洗后的点迹集合转换成可以进行聚类的带时间、位置属性的矩阵数据，且矩阵中的内容转换成全数字格式，可定义为以下矩阵：

式中：X为转换后的轨迹点矩阵，每一行代表每个轨迹点的详细信息，其定义见表1。

表1 轨迹矩阵行元素定义表

1.4 飞行轨迹数据处理流程

综上所述，飞行轨迹数据处理流程主要包括数据获取、特征识别与分类、数据清洗、数据转换，处理流程如图1 所示。

图1 飞行轨迹点数据处理流程图

2 K-means 聚类算法简介

K-means 算法是一种基于划分的聚类分析方法，指定输入参数K，然后将原始数据集合分组为K个类簇[2]。它采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为类簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。K-means 聚类算法属于无监督学习算法。

K-means 聚类算法是一种迭代求解的聚类分析算法，其步骤是随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。每分配一个样本，聚类的聚类中心会根据聚类中现有的对象被重新计算，这个过程将不断重复直到满足某个终止条件。聚类计算的终止条件是没有（或最小数目）对象被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小[5]。

K-means 聚类算法一般采用欧式距离作为相似度指标，计算公式如下：

式中：k代表某一次迭代过程中质心的数量；n代表等待计算的对象数量。

3 基于K-means 聚类的空域规划算法

3.1 K-means 聚类中心的选择

聚类中心是一个簇的中心点，满足簇中其他对象到该中心点的距离和最小。如果数据集中某一数据对象所处区域内的数据对象越多，区域内的其他对象到该对象的距离越小，说明该对象的数据密度越大，能够较好地反映数据分布特征[6]。

距离中心的选择可按照如下步骤进行。

1）距离计算。设清洗后的历史飞行轨迹集合为：P={p1,p2,···,pn}，pi=(xi1,xi2)，点迹样本pi与pj间的欧式距离计算公式为

2）计算集合P中所有对象间的平均距离。P中所有对象间的平均距离AveDis(P)的计算公式如下

3）计算每个点迹对象的密度。对象pi的密度计算公式为

式中：对于相对距离函数u(x)满足，当

得到各个点迹对象的密度集合D={De(x1),De(x2),···,De(xn)}。

4）聚类中心选择。设置预定聚类中心数为K，将集合D中的元素按照从大到小的顺序进行排序，依次选择前K个对象作为初始聚类中心集。

3.2 聚类个数的选择

聚类个数的选择直接决定聚类簇中对象的分散程度，簇内对象分散程度越小，簇间的距离越大，聚类效果越好[7]。按照3.1 的步骤选择每个簇的中心，随机选择第j个簇中数据对象间的平均距离作为数据对象的分散程度，用dpj,m表示，表示第j个簇和第m个簇之间的距离，然后重新设定聚类个数K值，计算每次得到的聚类中心集合的平均分散程度δ，不断重复该项操作，直到 δ的取值最小，则获得最佳聚类个数。平均分散程度计算公式如下：

3.3 K-means 聚类空域规划的实现

本研究中空域规划中的K-means 聚类算法的实现主要通过Python 的sklearn 中的cluster.Kmeans实现，主要步骤如下所示。

Step1：载入清洗后的历史飞行轨迹点集合P={p1,p2,···,pn}，pi=(xi1,xi2)。

Step2：输入预设聚类簇数量K(聚类后的空域数量)。

Step3：根据轨迹点集合和初始簇数量进行聚类自适应计算，得到最佳聚类中心数K’。

Step4：按照最佳聚类中心数K’进行聚类计算，得到各个聚类簇中心点和各个簇的数据。

Step5：对聚类后的各个簇的数据进行图形化绘制，得到聚类后生成的各个空域信息。

4 仿真实验结果分析

4.1 实验数据来源

本研究中的数据来源于四川省低空空域协同运行中心（简称：四川低空运行中心）的真实历史监视数据，选取2020 年9 月4 日到2020 年9 月10 日的历史数据作为挖掘对象，原始数据包括大约570 万个历史监视轨迹点。

4.2 实验结果分析

将转换后的历史轨迹点进行飞行轨迹点特征识别与清洗后，得到的通航历史飞行轨迹点的数量为3 963 980 个，将得到的通航飞行轨迹点进行Kmeans 数据挖掘，并进行自适应K值计算，得到K值在{5,6,7,8}集合中的聚类情况如图2 所示，同时展示了根据通航历史飞行轨迹点聚类后形成的空域分布。图2 中横坐标为纬度，纵坐标为经度。

图2 不同K 值的聚类空域分布和聚类情况图

本研究中的聚类质量评判分数采用Calinski-Harabaz 分数，指簇间的协方差矩阵与簇内的协方差矩阵相除，如果前者越大，后者越小，那么分值越大，分类效果越好。

本次研究中，对于聚类后生成的空域数据，在不同K值情况下，得到的空域聚类中心位置均不相同，各个K值情况下，空域中心位置情况见表2。

表2 不同K 值下的空域规划结果

由表2 可知，在不同K值的情况下，对原始数据进行K-means 聚类操作，形成的空域划设分布情况不同。当K值等于8 时，图2 中各个空域分布状态较好，按照此结果进行空域规划结果合理、科学。

4.3 结果优势对比

四川运行中心发布的协同空域信息信息如图3所示。

图3 四川省运行中心协同空域图

根据历史数据聚类后形成的高频飞行空域信息如图4 所示。

图4 协同空域与聚类空域对比图

由图4 可知，聚类空域更靠近川协4 号的西南侧。从实际飞行活动中可以得出聚类空域中存在更多的训练和观光飞行，包含了广汉和绵阳飞行学院的飞行训练航路等；因此，由历史数据聚类形成的空域具备更高频次的低空飞行活动，可为后续协同空域的划设提供更有力的数据支撑，相对于人为经验划设的空域具备更高效的利用率。

5 小结

本文制定和设计了历史飞行轨迹点数据处理流程和算法，设计了K-means 聚类算法流程，建立了基于历史飞行轨迹点的通航空域规划模型和算法流程，并通过真实历史数据对建立的模型进行算法验证和结论分析。研究的算法和模型对低空通航空域规划能够提供较优的辅助决策，并通过Python 环境进行算法实现，可为后期工程运用奠定基础。