基于层次聚类的航空器群识别方法

王红勇，许 平

（中国民航大学天津市空管运行规划与安全技术重点实验室,天津 300300）

空中交通管理系统最根本的任务是保障空域内航空器的安全，当管制扇区内出现小范围内航空器聚集的情况时，管制员需要付出更多的精力来判断航空器的运行状态，从而避免发生间隔丢失甚至碰撞。面对日益增长的空中交通服务需求，管制员的服务能力与效率正面临巨大的挑战，因此如何描述航空器的聚集情况和运行状况，从而量化不同交通态势给管制员带来的工作负荷显得非常重要。目前，国内外学者主要用空中交通复杂性来刻画不同的空中交通态势。

不同空中交通复杂性直接呈现的结果就是管制员的工作负荷差异，因此有学者将静态扇区空域结构及动态交通流特征作为空中交通复杂性的基本指标来评估管制员的工作负荷[1−3]。扇区空域结构包括扇区的形状、大小等空域因素及扇区的航路数量、长度、走向、交叉点的数量等航路航线因素。交通流特征包括进入或离开扇区的飞机数量、平均通过时间、航空器的冲突数量、爬升航空器比例、下降航空器比例等因素。通过对各种指标的综合量化从而刻画空中交通复杂性。也有一些学者从航空器最基本的内禀性特征（如相对距离及速度）出发，通过量化航空器对的相对运动状态来刻画空中交通复杂性。Delahaye 等[4−6]最早提出内禀性的概念，并且通过动态系统进一步对空中交通复杂性进行计算分析。张进等[7−8]、王红勇等[9]、徐肖豪等[10]在Delahaye 研究的基础上进一步提出运用复杂性学科的思想，提出了综合迫近、几率和连携因素的二维及三维复杂性模型。Hansman 等[11−12]提出空中交通复杂性包括环境复杂性、认知复杂性和感知复杂性。其中，环境复杂性是空域中各种结构静态复杂性的集合，认知复杂性是管制员对静态结构分析处理的难度，感知复杂性则是完成冲突调配等针对认知复杂性的实际操作难度。

以上研究从不同角度对空中交通复杂性进行了分析。John Hansman 为了解决之前的研究只考虑扇区静态结构来衡量复杂性而未考虑管制员认知难度的问题，提出了航空器群的概念。管制员通过对实际的交通流抽象形成认知中的空中交通状况，通过塑造扇区内航空器的预计轨迹和预定航线，形成空域中基础结构限制。管制员通过结构抽象来减少需要评估运行状态的航空器数量，即通过工作思维模型来简化认知的交通流模型，将扇区内大量的航空器分为若干数量较少、运行状态相似的航空器群，从而辅助管制员高效率地分析扇区内航空器的运行状态，降低管制员对交通流结构的认知复杂性。本文在传统k-means 算法基础上，通过改进层次聚类算法实现不同航向航空器群的自动识别，并进一步通过位置内聚度和航向轮廓系数分析航空器群的识别效果，通过与传统k-means 方法作对比，验证本文方法的有效性。

1 轨迹数据预处理

实际的雷达数据为一系列连续、相同时间时隔的点集，表示为：P=(P1,P2,···,Pn)，其中P表示某一架航空器的飞行轨迹，Pi=(xi,yi,zi),其中xi,yi,zi分别为某一时刻该航空器的横、纵、高度坐标。通过对雷达数据的处理，我们可以得到某一时刻的航空器横纵坐标、速度大小和航向。

由于管制员雷达显示屏仅根据航空器的横纵坐标显示相应的位置，不同高度层但水平坐标相近的航空器也会因为雷达标牌重叠等原因增加管制员认知复杂性，因此本文仅考虑航空器横纵坐标作为聚类的位置坐标。为了识别位置相近、速度相似的航空器群，本文将位置、速度信息都作为区分航空器群的要素。

在某一空域内，航空器可视为一个质点。将扇区内的航空器位置、速度的集合表达为下列矩阵：

式中：W为航空器信息的集合；Wn为扇区内第n架航空器的信息；xn、yn为第n架航空器的横、纵位置坐标；vn、θn为第n架航空器的速度大小和航向。

由于每架航空器位置与速度信息的单位不同，需对数据进行标准化处理。

2 航空器群的识别

管制员对交通流的认知抽象先是根据工作模式将扇区内的航空器形成预计航线，再把位置相近、航向相似的航空器归为一个航空器群，从而降低分析交通流特征的认知复杂性。如图1 所示，航空器1、2、3 位置相近，航空器2、3 航向相近，航空器1 与2、3 航向相反。在管制员的认知中，将运行状态相似的2 和3 航空器归为一个航空器群将降低管制员对于交通态势判断的复杂程度。传统以位置进行聚类确定航空器群的方法可能出现将1、2、3 航空器都归为一个航空器群，航空器4、5 归为另一个航空器群。在管制员的实际操作中，该方法识别出航空器群之后还需要管制员再去判断航空器群内各航空器的运行状态，降低管制员认知复杂性的效果不明显。相比之下，识别出群内航空器速度相近、相对距离较短的航空器群在研究管制员认知复杂性中更有优势。

图1 航空器群示意

2.1 聚类算法

本算法步骤如下。

Step1 定义初始航空器群。将扇区内每一架航空器Wn视为一个初始航空器群Gn。

Step2 计算距离。采用欧式空间距离，计算扇区内所有不同航空器i与航空器j之间的距离，公式如下：

计算结果记为距离矩阵D(0)。

Step3 合并航空器群。在距离矩阵D(0)中寻找最小元素，记作：

将GO和GP合并为一个新的航空器群GQ，即GQ={GO，GP}

Step4 重新计算集合间的最小距离。计算新航空器群GQ与合集中其他航空器群GE的距离：

将计算结果对距离矩阵D(0)进行更新，将Gi和Gj所在的行列分别合并到一个新的行列。对于GE，新的与其他航空器群的距离由上式计算结果进行更新，其他行列不变。记新得到的距离矩阵为D(1)。

Step5 循环计算。对距离矩阵D(1)重复步骤（3）和（4），得到新的矩阵D(2)，如此循环，直至所有航空器群合并为一个航空器群为止。

Step6 画谱系图。根据以上5 步的结果画出聚类谱系图。

Step7 确定聚类结果。通过计算畸变程度选取响应的最优聚类群数量确定最终的聚类结果。

2.2 聚类结果确定

采用肘部法则对聚类算法结果的谱系图进行结果分析。

畸变程度定义为某航空器群质心与其他航空器位置距离的平方和。假设将n个航空器划分到K个航空器群中（K≤n−1，即至少有一个航空器群中有两架航空器），用Ck表示第k个航空器群（k=1,2，···，K），且该航空器群质心的位置记为Uk，则第k个航空器群的畸变程度为：

所有航空器群的总畸变程度定义为聚合系数，记作J，表示为

则n个航空器的所有聚合系数为J=(J1,J2,···,Jn)，J1>J2>···>Jn。

定义J(i)=Ji−Ji+1(i=1,2···,n−2)，为聚类结果i的畸变趋势，若J(n)=min{J(i)}，则最优聚类航空器群个数为n。

3 航空器群的评价指标

航空器群作为管制员对交通流特征的认知抽象，识别出的航空器群的合理性、有效性需要一个评价准则。由于划分航空器群的目的是辅助管制员监视相应空域，减少管制员对于扇区运行状态的认知难度，因此航空器群内的航空器运行状态越相似，对管制员的辅助效果越好。为了评价航空器群内航空器的位置、速度指标，采用位置内聚度和速度轮廓系数来评价航空器群的聚类效果。

3.1 位置内聚度

采用位置内聚度来评价航空器群内部航空器之间的位置情况[13]，定义如下：

式中：Ci为第i个航空器群的位置内聚度值；Di为第i个航空器群内所有航空器之间的平均距离；D为扇区内所有航空器之间的平均距离。设duv为航空器u、v之间的距离，ni为第i个航空器群内航空器的数量，n为扇区内航空器的数量，则Di和D计算公式如下：

群内航空器的平均间距相对于扇区中所有航空器的平均间距越小，说明航空器群内的连接越紧密，群的内聚程度就越高，所对应的群结构越佳。

3.2 航向轮廓系数

对于位置相近的航空器群，不同群内的航空器速度差异越大，航空器群的划分效果越好。定义航向的评价指标为航向轮廓系数，记航空器群i的航向轮廓系数为S i，表示为

式中，n为航空器群内航空器的数量。

记标准化后的第n架航空器速度信息为，记航空器i与航空器j之间的速度距离为vdij,采用欧氏距离计算两架航空器之间的速度距离，公式如下：

记航空器u到所在航空器群的其他航空器的速度平均距离为a(u)，公式如下：

航空器群i的速度平均距离为Ai，公式如下：

Ai越小，说明航空器群i内航空器速度值越相似。

记航空器u到其他航空器群的所有航空器的速度平均距离的最小值为b(∑u),公式如下：

式中：Cw为扇区内不包含航空器u的航空器群w；nw为航空器群w内航空器的数量。

航空器群i到其他航空器群的速度平均距离的最小值为Bi，公式如下：

Bi越大，说明航空器群i与其他航空器群的速度差异越大。

记航空器u的航向轮廓系数为S(u)，表示为

S i的值介于[−1,1]之间，越接近于1 说明Bi越大Ai越小，航空器群内速度越相似，航空器群之间速度差异越大；越接近于0 说明航空器群内部和外部之间的速度类似，分界线很不明显；越接近于−1 说明航空器群之间速度越相似，航空器群内速度反而不相似。

4 算例分析

为了验证聚类算法的有效性，选取上海1 号扇区的实际数据进行分析。具体过程为：首先采用本文层次聚类算法对某个时刻的扇区航空器态势进行航空器群划分，根据聚合系数自动选取最优的航空器群数量，并画出相应的谱系图；再选取K-means方法进行对比，设定其聚类数量为本文选取的最优航空器群，并对两种划分方法的位置内聚度、航向轮廓系数进行分析。

4.1 聚类算法

以上海1 号扇区2021 年4 月12 日18:58 雷达数据为例，该扇区内航班的航班号、横纵坐标、速度值、航向如表1 所示。

表1 4 月12 日18:58 雷达数据

根据表中的雷达数据信息，可得到航空器在扇区内的空间分布图，如图2 所示。

图2 航空器雷达位置图

根据本文中的聚类算法对上述时刻的航班信息分析可知，最小畸变趋势值为0.307849，对应最佳航空器群数为4。因此，此时扇区内10 架航空器共被分为4 个航空器群，分别为：CSH9454、CSH9086 和CSC8153 的距离和速度相近，可归为一个航空器群；CQH8931、CSN3374 和DKH1394归为一个航空器群；ANA858 和LKE9731 归为一个航空器群；CSH831 和CSH9313 归为一个航空器群。其中：CSH9454、CSH9086 与CQH8931、CSN3374虽然位置相近，但是航向差异过大，未被归为一个航空器群；DKH1394 与CSC8153 同样由于航向差异过大未被归为一个航空器群。聚类谱系图及航空器群的位置图如图3—4 所示。

图3 谱系图

图4 层次聚类群划分图

将聚类群数量设置为4，采用k-means 算法重新计算，划分结果如图5 所示。

图5 k-means 群划分图

ANA858、LKE9731 与CSH831、CSH9313 分别被归为一个航空器群，计算结果与层次聚类相同。另外两个航空器群的航班不完全相同，航空器群3 和4 中航空器位置相对集中，符合聚集的基本要求，但是航空器群内部航班航向差异过大。由此得到的航空器群只是基于位置映射给管制员的最基本认知，没有进一步缩减交通流的结构，在实际操作中，管制员还需要针对航空器群3 和4 分别判断内部航空器运行状态。相较之下，优化后的层次聚类算法已经自动完成航向的结构缩减，从而降低管制员的认知复杂性。

4.2 指标分析

在完成聚类算法之后，根据所得到的航空器群划分结果，分别计算两种方法中对应的位置内聚度Ci、航空器群i的速度平均距离Ai、航空器群i到其他航空器群的速度平均距离的最小值Bi及航空器群i的航向轮廓系数Si。时刻18：58 及之后以6min为步长共1h 的结果如图6—7 所示。

图6 18：58 指标结果图

由图6 可知，两种方法Ci大致相等。对比群内速度平均距离Ai，航空器群1 和3 的速度平均距离Ai基本相等，航空器群2 和4 的k-means 算法所得的值明显偏大。Ai值越小，说明航空器群内速度越相似，由此可知，层次聚类保持群内速度相似的表现较好。对比群外速度平均距离的最小值Bi，航空器群1 和3 中k-means 所得的值远大于层次聚类，航空器群4 中层次聚类略大于k-means。Bi值越大，说明航空器群间的速度差异越大。而我们注意到，层次聚类所得的航空器群1 和2 的Bi值基本相等，也就是说两群之间的速度几乎没有差异，但是却被分为两个不同的航空器群，说明层次聚类能够很好地区分位置相对较远速度一致的航空器，并分到不同的航空器群中。对比航向轮廓系数S i，观察到层次聚类所得的航空器群S i结果更优。由图7观察1h 的数据可知，对比两种方法的位置内聚度Ci可得到其取值范围基本在[0.6，0.8]之间。位置内聚度Ci越接近1，说明划分的群内航空器的聚集程度越接近于扇区标准水平。两种方法划分的位置内聚度都低于1，说明划分的航空器群基本满足位置相对聚集的要求，具有实际意义。此外，层次聚类的Ci高于k-means。观察S i值层次聚类基本稳定在[0.5,0.8]，而k-means 中的S i值在[−1,1]中无规律跳动。S i值越接近于1，航空器群速度越相似、位置越聚集，群之间差异越明显；S i值越接近于−1，说明划分效果越差。由此可知，层次聚类在航向划分的综合表现中优于k-means，且更加稳定。

图7 1h 指标图

5 结论

针对研究空中交通复杂性中认知复杂性的航空器群识别问题，本文提出了在结构缩减中需要综合考虑位置和航向来模拟管制员对交通流结构的认知抽象，并利用层次聚类算法，通过改进聚类结果的自动选取方式，实现了扇区内航空器群的自动识别。同时，航向因素的加入使得算法能够区分位置相近速度差异明显的航空器，使划分结果更加贴近管制员的认知。此外，还避免了传统划分方法需要人为设定群数量的缺点。从位置内聚度、航向轮廓系数提出了群划分指标用于反映群划分效果。通过对上海扇区实际雷达数据分析，结果表明在识别位置聚集、速度相近的航空器中，本文提出的层次聚类算法相较于传统方法划分效果更优，且算法更加稳定。这对于研究管制员认知复杂性及交通流结构缩减具有十分重要的意义。