基于改进KNN 检测的ADS-B 轨迹插补研究

靳慧斌，冯朝辉，张召悦，王志森

（中国民航大学a.安全科学与工程学院；b.空中交通管理学院，天津 300300）

广播式自动相关监视（ADS-B，automatic dependent surveillance broadcast）是航空器周期性广播自身位置及相关信息，供空管对其进行监视的一种监视技术[1]。ADS-B 数据传输过程中可能会因为定位设备故障、恶劣天气、飞行姿态变化等因素导致部分报文数据缺失或数据跳点，使地面站接收的ADS-B 轨迹数据出现缺失点、离群点等异常点[2]。异常点的产生不利于系统和相关用户对轨迹位置数据进行应用分析，并有可能产生轨迹点间隙过大、错误位置告警、图形轨迹误判等影响航空安全水平的事件。

为解决数据缺失问题，国内外学者从不同方向展开了研究。鞠时光等[3]从连续性及保形性两方面提出了用λ 参数三次样条函数对等高线轨迹数据进行修补论证，有效地解决了绘制地形图过程中出现的等高线相交或缺失问题，但该方法只适用于线性函数。针对非线性数据插补修复，Zamani[4]采用二次样条函数处理函数边界非线性问题；Farhan 等[5]建立了一种随机多重插补（RMI，random multiple interpolation）方法来克服非线性轨迹不确定性问题。但两种方法对于处理大量数据具有局限性。为解决大数据插补局限性问题，Peeters 等[6]评估了处理丢失数据的不同技术，得到了对于大数据插补问题使用预测均值匹配的多重插补（MI，multiple interpolation）是最佳方法的结论。为提升ADS-B 数据完整性，邹文华等[7]建立了一种引入时间序列的基于贝叶斯常均值模型的数据增广算法，解决ADS-B 轨迹点回跳现象。此外为确保插补数据精度，Sun 等[8]构建了一种使用最小二乘样条逼近（LSB，least square b-spline）的轨迹数据重建算法，能够避免因数据差值而导致插补误差过大问题。

上述研究多侧重从单一角度对数据缺失问题进行插补分析，或以局部数据是否间断为依据进行插补验证，未考虑数据可能存在异常点的问题。针对这一情况，本文采用多约束条件筛选出航空器轨迹缺失点并将其清洗插入，然后利用改进后的K 最近邻（KNN，K-nearest neighbor）方法检测ADS-B 异常点，解决了ADS-B 样本数据量过大带来的聚类点权重分配不平衡而无法有效检测异常点的问题，并对轨迹进行多重回归插补修复，进一步提高轨迹数据完整性，从而保障航空安全监管水平。

1 基于KNN 的轨迹数据异常点检测

1.1 缺失点筛选

为确保经度、纬度和高度使用同一量纲（m），需要利用米勒投影完成经纬度和平面坐标的相互转换[9]。转换过程如图1 所示。

图1 经纬度米勒投影转换Fig.1 Miller projection conversion of longitude and latitude

图1 中：ARP（aerodrome reference point）为机场基准点；L 为地球周长；W 为地球周长的平面展开，并将周长视为X 轴；H 为Y 轴，约等于地球周长一半（L/2）；mill 为米勒投影常数。

ADS-B 地面接收机在同一时间接收不同航空器机载ADS-B OUT 发出的报文信息是有限的[10]，中国民用航空局规定接收机标准是600 架飞机的解码[11]，一台ADS-B OUT 发射全类型报文为4 次/s，则ADS-B地面接收机每秒最少接收2 400 条全类型报文。

假设一台ADS-B OUT 单位时间T 内发射报文次数为C，则每条报文时间间隔

从航路进入终端区的进近航路相对地面高度一般为6 000 m 左右，无线电传播速度为299 792 458 m/s，因此在终端区范围内，因距离而导致的接收延迟问题可以忽略。

一条全类型报文解码平均时间长度为Ta。地面接收机接收报文并完成解码，传入终端显示界面的时间间隔为Tu，则同一航班的两条报文时间间隔应为

一条轨迹点的报文信息包括经度、纬度、高度、地速、航向角、时间，所以设轨迹点P={Plo，Pla，Pal，Psp，Pha，Pt}，轨迹点速度均为瞬时速度，因此将轨迹点之间的时间段位移作为平均速度位移，通过距离和时间差判断是否有缺失点，其判断公式如下

式中：时间差Δt=Pt，i-Pt，i-1；速度差Δv=Psp，i-Psp，i-1；Px为两点之间距离；i 为轨迹点序号。其缺失点判断如图2 所示，其中Pvt为同一架飞机t 时间段内飞行的距离。

图2 缺失点判断示意图Fig.2 Diagram of missing point judgment

当两点之间出现缺失数据，应插入空白轨迹点，其插入轨迹点数目满足

1.2 基于标准欧氏度量的离群点筛选

KNN 算法具有最近邻特性，对于非线性数据筛选可避免偏离数据与正常数据出现较高拟合[12-13]，因此适用于终端区ADS-B 数据检测。

1.2.1 数据处理

在1.1 节中已经完成缺失点的筛选和空白轨迹点插入。但在计算轨迹点相似度时，需要赋予空白轨迹点标签，避免出现因无标签而导致分类错误的问题，通过下三角距离矩阵对空白轨迹点进行赋值，其矩阵如下

式中t 为轨迹点时间，当矩阵中元素Wi，j＜0 时，对应Pt，i为原数据；当Wi，j＞0 时，对应Pt，i=0。因ADS-B 轨迹在界面只显示二维坐标轨迹，所以只需要插补经度和纬度。

1.2.2 距离计算

KNN 距离度量有两种，一种是欧氏度量（Euclidean metric），另一种是曼哈顿度量。欧氏度量用于衡量各点之间的绝对距离。如三维坐标点M1（X1，Y1，Z1）和M2（X2，Y2，Z2），则M1和M2两点之间的距离为

在n 维空间中，两个n 维向量A=（X1，X2，…，Xn）、B=（Y1，Y2，…，Yn）间的欧式度量为

曼哈顿度量是向量之间距离的范数。如向量A=（X1，X2，…，Xn）和B=（Y1，Y2，…，Yn）之间的曼哈顿距离为

选择欧氏度量或曼哈顿度量主要取决数据维度特征[13]。对于高维向量，曼哈顿度量比欧氏度量计算距离的效果更好；对于低维向量，欧氏度量要优于曼哈顿度量。因轨迹点P 经过筛选，只考虑经度、纬度和时间，所以本文选择欧式度量。

欧式度量适用于样本向量的各个分量度量标准统一的情形。ADS-B 轨迹样本各分量权重相同，当时间与经纬度波动范围量纲值差距较大时，可能会引起各个分量分类不平衡问题[14]。因此可以通过标准化欧氏度量（standardized Euclidean metric）解决Pt和Plo、Pla分量差值问题。标准化欧氏度量是针对欧氏度量缺点的一种改进。标准化欧氏度量的思路为：既然数据各维分量的分布不一样，那先将各个分量都“标准化”到均值、方差相等[15]。假设样本集X 的均值为m，标准差为s，X 的“标准化变量”表示为

标准化欧氏度量公式为

由式（10）可以得到不同轨迹点之间标准化欧氏度量为

式中z 为分量度量，因KNN 遵循最近邻原则，为避免同一航班轨迹点之间不同分量差值较大，导致线性方差误差过大，因此需要限制轨迹点方差样本数目i -n1≤i≤i+n2，n1为第i 点前一个不相邻异常点位置，n2为第i 点后一个不相邻异常点位置，将式（11）的变量进行如下改进，即

通过改进后的KNN，检测出缺失点和其他异常点的总集合{O1，O2，…，On}，然后通过程序遍历总集合，将异常点清洗为空白轨迹点，便于后续插补。

2 基于多重插补的ADS-B 轨迹补全

多重回归插补理论定义[16]为：设β 是从所要修复样本数据X 中估计得到的参数向量，β 的先验分布为f（β），使用贝叶斯准则可得到其后验概率分布为

式中Q 是分析样本数据X 得到似然函数。

设Xp为X 中缺失信息的变量。pobs和pmis分别为p中的已存元素和缺失元素，并假设p 中的信息缺失机制为随机丢失（MAR，missing at random）。

缺失数据样本的参数向量期望值β|Xp，pobs为

Bernstein-von Mises 定理[17]将贝叶斯估计与经典的最大似然估计联系起来，总结这种关系如下

根据式（18），在二维多重插补随机修复下（G=1，2），轨迹样本数据的β|Xp，pobs计算公式如下

式（19）可以用于计算轨迹样本的最终方差。通过从轨迹数据集中抽取多个随机样本，可以推断出总体参数的均值和方差的无条件估计[18]。均值和方差-协方差矩阵计算如下

式中：Ex（β|X）为样本数据X 中参数向量的期望；Varx（E（β|X））为Ex（β|X）期望的方差。轨迹缺失数据多重插补的步骤如下：

步骤1从要修复的轨迹数据随机抽取部分样本数据xg，g=1，2，…，G；

步骤2引入误差项e 的方差，计算为

步骤5计算插入缺失值向量，如下

式中Z 为数据插补间可变性系数，在多次插补步骤结束时，可得到G 个完整的数据集。因航空器性能的影响，轨迹数据插补不应以整个轨迹数据方差为系数，为得到更加准确的插补值，采用轨迹分隔和轨迹排序判断对多重插补方法进行改进，其过程如图3 所示。

图3 轨迹修复流程图Fig.3 Flow chart of trajectory repair

因软件界面只显示航空器ADS-B 二维坐标轨迹，所以只需要插补经度和纬度即可。

3 算例分析

3.1 数据处理

本文选择天气状况良好的时间段，排除天气干扰因素，筛选出某机场终端区4 天内轨迹坐标数据，如图4 所示。

图4 终端区不同维度轨迹显示Fig.4 Trajectory display of different dimensions in terminal area

通过匹配机型，从中随机挑选2 个不同机型的航班，其轨迹信息如表1 所示。

表1 样本轨迹信息Tab.1 Information of sample trajectory

样本轨迹数据通过米勒投影转换和缺失点筛选得到结果如表2 所示。

表2 缺失点信息Tab.2 Information of missing points

每条全类型报文平均解码时间Ta=1.12×10-4s，每条全类型报文发射间隔To=0.25 s，数据经过处理传入终端界面时间Tu＜0.1，从表2 可以得到最小间隔Tmin＜Ta+To+Tu均成立，说明缺失点判别模型算法正确。通过距离矩阵对缺失点赋值，便于改进后的KNN算法检测分类。

3.2 算法对比

在轨迹点分类的具体应用中，选择适用的距离计算方法是决定KNN 分类结果质量的关键性因素。常见的空间距离算法有欧氏度量和曼哈顿度量，如1.2节所述。本节将欧氏度量、曼哈顿度量和标准化欧氏度量进行实验对比，通过对比3 种距离算法检测ADS-B 异常轨迹点的结果，验证3 种不同算法检测ADS-B 异常点的准确率。所有样本训练集与测试集比例设置为6 ∶4，每个样本设置不同k 值（样本包括780310、781181），交叉验证采用不同距离算法的KNN检测ADS-B 异常轨迹点，并计算每种算法检测出的异常点数量与每个样本异常点总数之间占比，其结果如图5 所示。

图5 算法结果对比Fig.5 Comparison of algorithm results

从图5 可得标准化欧氏度量的精确度均高于欧氏度量和曼哈顿度量。通过对比不同k 值各算法准确率，当k=2 时为最佳选择。通过同一终端区的不同航班轨迹、不同k 值和不同距离算法的交叉验证，验证了改进后的KNN 算法检测ADS-B 异常点是完全可行的。

3.3 轨迹修复

在进行插补修复前，需要将检测出的异常值的经度和纬度归0，并赋值序号标签，方便插补算法识别需插补位置，以免忽略。完成赋值后，筛选出样本中纬度和经度将其作为修补序列C[X，Y]输入多重插补算法中，其对比结果如图6 所示。

图6 实验结果对比Fig.6 Comparison of experimental results

由图6 可知，ADS-B 轨迹包含线性轨迹与非线性轨迹，经过缺失点筛选和改进后的KNN 检测出异常点，将其清洗后通过多重插补能够有效完善轨迹图像，进一步提高数据的完整性。

4 结语

航空器ADS-B 技术的普及应用，使得ADS-B数据成为当前航空器交通流分析、轨迹监管和空域运行态势分析的重要数据来源之一。然而ADS-B 数据的缺失及异常点的出现给相关系统及用户的应用分析造成一定困难。本文方法不仅可以有效判别是否存在缺失点，而且可以有效检测出除缺失点外的其他异常点，能够有效插补航空器ADS-B 轨迹，提升轨迹图像连续性，降低因异常点或图形问题而造成的不安全事件发生概率。针对ADS-B 数据缺失水平问题，应进一步研究ADS-B 数据质量分析指标体系，并根据用户需求和实际应用场景不断改善和发展ADS-B 技术，提高数据链传输质量和地面站接收能力，从根本上解决数据缺失和异常点出现问题。