基于动态时间规整下密度聚类的轨迹识别研究

吴 达，吕 锐，杨 宇，邓建军，张保山，2

（1.空军工程大学防空反导学院，西安 710051；2.解放军92095 部队，福建 台州 318050）

0 引言

随着航空发动机、气动外形设计、飞行控制系统、机载武器系统、空战指挥系统等不断更新换代，战斗机的机动动作也越来越复杂多样，而目前的目标轨迹生成系统多是根据经验人为设定的［1-2］，难以保证与真实战场的贴近性、真实性和准确性，在难以获得飞行训练手册和作战中，对战斗机的操纵要求以及飞行员的飞行习惯的情况下，通过演习、模拟训练等飞行记录数据获得的机动动作更加可靠。现今关于机动识别的算法多是运用SVM［3-4］、神经网络［5-7］、动态贝叶斯网络［8-9］、HMM［10-11］等算法构建分类器，进行机动类型的分类，或者通过构建机动动作库［12-13］，通过模板匹配［14-16］的方法进行识别，上述方法得到的结果并不能运用于目标轨迹生成，因为上述方法仅仅得到机动动作的类型，而没有考虑机动过程中特征参数峰值的差异导致的分类。对于构建分类器的方法来说，需要一部分有参数峰值标签的数据。对于构建机动动作库进行模板匹配的方法来说，需要不断更新新的机动动作和相关经验知识。

张夏阳［17］考虑对飞行数据进行聚类获得了11种机动动作类型，方法中用一组均值与方差构成的特征向量表示每个机动片段，仅仅考虑了空间维度的变化，对时间维度上的变化考虑较少。姚佩阳［14］考虑用DTW 距离将样本与模板轨迹进行匹配，DTW 距离充分考虑了时间维度，但是两条轨迹进行规整的过程需要较大的计算量，直接对每两条轨迹计算DTW 距离而后进行聚类的效率是极低的。不妨利用DBSCAN 算法对所有的轨迹点进行预分类，使得被聚为一类可能性较低的机动片段之间不必再进行DTW 距离计算，再利用DBSCAN 改进DTW聚类方法，对可能分为一类的轨迹进行计算，确定其所属分类。

1 特征及机动片段提取

从演习训练数据可以得到北天东坐标系航迹的三维坐标数据，以雷达站位坐标原点O，基本面为原点所在地的大地水平面，3 个坐标轴X 轴指向北极，Z 轴与地表垂直指向空中，Y 轴指向北方，与X、Z 构成右手系。

定义1：一个完整的机动过程是从航迹倾角变化率，航迹偏角变化率和切向加速度由恒定为0 到不为0 的时间结点开始，到不为0 到恒定为0 的时间结点为止。

定义2：机动过程中飞行参数的峰值不同，也被划分为不同的机动类别。

定义3：机动过程中航迹倾角、航迹偏角、速度改变的累计大小不看作机动类别的区分标准。

为了便于进行聚类分析，排除无关因素，不妨采用航迹倾角变化率、航迹偏角变化率和切向加速度（以上这3 种飞行参数统称为特征参数）作为特征。

1.1 航迹偏角变化率的获取方法

1.2 航迹倾角变化率的获取方法

1.3 切向加速度的获取方法

图1 轨迹点特征参数空间分布图

2 基于DBSCAN 改进DTW 机动轨迹分析

2.1 基于DBSCAN 轨迹预分类

DBSCAN 中邻域半径和邻域中核心点的最小数量MinPts 是其关键参数，关于DBSCAN 的具体定义可以参考文献［18］。

在使用DBSCAN 方法进行轨迹预聚类时，需要进行以下适用性改进：在飞行过程中，进行协调转弯、抬头机动、切向加速等机动时，会导致发动机需要提供的功率增大［19］。但是发动机的最大输出功率是有限的，一种特征参数的增加会使另外两种特征参数最大值减小，产生负相关性，采用加权的欧式距离或对特征参数进行归一化都不是最适用的。而马氏距离既独立于测量尺度，又考虑到各种特性之间的联系。对于一个均值为μ，协方差矩阵为S 的多变量向量，两点间的马氏距离表示为

其中，X 是由所有轨迹点的特征向量构成的矩阵。

n 为最大机动片段数量，mi是第i 个机动片段的最大轨迹点数量。

设定作为核心点邻点的限制条件，使同一机动片段的点无效，可以避免相同机动片段间较小距离的轨迹点聚为一个点簇。

2.2 构建基于DBSCAN 改进DTW 机动轨迹识别模型

动态时间规整（DTW）是通过计算T 与R 之间的累积最小欧式距离。当两条轨迹长度相等时，可以通过直接计算T 和R 的距离，距离越小，两个序列相似度越高。当两条轨迹长度不相等时，DTW 采用动态规划（Dynamic Programming，DP）方法来识别。关于DTW 的详细说明可参考文献［20］。

早已有相关学者采用DTW 方法对航迹进行聚类或者分类的研究［15］，但很少见到从航迹特征的角度对DTW 方法进行分析：

在战斗机机动动作中往往存在类似于如下模式的机动过程：以协调转弯为例，战斗机往往先是逐渐增加坡度，进入一个较为稳定的转弯状态，此状态下θ 会基本保持不变，累计转弯角度Δθ 会逐渐增大，然后再逐渐减小坡度改出机动状态，由定义3 可知，Δθ 的大小不会影响机动类别的划分，而DTW 方法会自动对θ 值相同的点进行合理对应，使得DTW 距离不会因Δθ 的大小而产生明显变化。

再者由于记录的轨迹点之间的时间差不是均等的，且飞行员使用操纵杆的习惯不同，使得拥有相同变化趋势的轨迹拥有不同的记录点数量，DTW 方法会自动对变化过程中的处于相似进度的记录点进行匹配，来减小记录点数量不同所带来的影响。

3 实验分析

实验1 DBSCAN 改进DTW 聚类算法

实验1 的数据由专家根据相关经验知识，在目标轨迹生成软件上，根据想定参数绘制的10 条完整航迹。包含机动动作详细情况如下表1 所示。

表1 机动动作设置表

图2 是其中一条完整的航迹。

图2 航迹效果图

表2 DBSCAN 改进DTW 算法分类结果表

其轨迹分类结果如图3 所示，不同类别的机动片段放于不同区域内，不同机动片段用不同颜色表示，其中，错误划分片段由红色曲线标出，虚假片段由绿色曲线标出。

图3 DBSCAN 改进DTW 算法分类结果轨迹图

实验结果验证了DBSCAN 改进DTW 聚类算法对于第1 节所定义的分类规则的适用性，即飞行参数φ、θ、vt的起始值，飞行参数φ、θ、vt的累计变化值以及轨迹段的疏密程度，不会影响DBSCAN 改进DTW 聚类算法对机动类别的划分，同时，实验结果中出现的误识别，也体现出DBSCAN 改进DTW 聚类算法对于特征参数峰值的不敏感性。

实验2 DBSCAN 预分类的DBSCAN 改进DTW聚类算法

实验2 的数据与实验1 中相同。

表3 DBSCAN 预分类的DBSCAN改进DTW 算法分类结果表

其轨迹分类图如图4，不同类别的机动轨迹段放于不同区域内，不同机动轨迹段用不同颜色表示，其中，虚假片段轨迹已由绿色曲线标出。

图4 DBSCAN 预分类的DBSCAN 改进DTW 算法分类结果轨迹图

实验2 的总运行时间相比于实验1 减少了16.41 %。主要是由于DBSCAN 预分类限制了DBSCAN 改进DTW 聚类算法进行运算的最大规模，虽然DBSCAN 预分类本身也会加大计算时间的开销，但相较于由此带来的计算时间复杂度的减小是十分值得的。

实验3 数据结构对分类结果的影响

实验3 中的数据来自模拟训练的记录数据。每条航迹中机动片段的机动类型已由记录数据给出。

表4 数据结构参数设置表

实验结果如图5 所示，从图中曲线的趋势可以看出，无论是机动轨迹段的总数x，还是机动轨迹段的平均长度n 的增加，都会使DBSCAN 预分类的DBSCAN 改进DTW 聚类算法在时间复杂度上的优化效果更为明显。同时对比图5（a）和图5（b）也可以发现，x 增加带来的效果更为明显。图5（c）说明数据总量的增加也会使错误率f（错误划分的机动轨迹段数量占总机动轨迹段数量的比率）增加，但也是在可以接受的范围内。

图5 数据结构的影响

实验4 聚类参数对分类结果的影响

表5 数据结构参数设置表

实验结果见图6，图6（a）中两种算法在运行时间上的差值随着c 的增加，有增大的趋势，说明用于预分类记录点的数量比例越少，算法优化的效果越明显。而在c=0.10 时，算法的运行时间均有较大增加，对照图6（b）中c=0.10 时，错误率明显增加，而正确率（正确划分的轨迹段的数量与总共轨迹段数量的比率）没有明显变化，可知由于数据误差波动的存在，使得虚假机动轨迹段大量增加。而当c=0.30，时算法运行时间有较大减少的异常现象，对照图6（b）可知，此时由于门限值选取过大，使得部分机动轨迹段被忽略。

图6（c）中两种算法运行时间上的差值随着d的增加，呈现先保持稳定，后减小的趋势。随着d 的增加保持稳定说明，DBSCAN 预分类的能力是有限的，需要DBSCAN 改进DTW 聚类算法进行再分类。而当d 继续增加时，预分类产生的类别数量逐渐减少，再分类承担的任务增加，使得算法整体的效率降低。在d=0.010 时，同样出现两种算法的运行时间有较大减小的异常现象，对照图6（d）可知，由于半径参数选取过小，很多机动轨迹段被误识别为噪声点。在图6（d）中随着d 不断增加，正确率有先缓慢增加，后基本稳定不变的趋势。可见，在d 值的一定范围内，d 越大，越能减少机动轨迹段被误识别为噪声点的现象。

图6 聚类参数的影响

4 结论

通过实验验证了DBSCAN 改进DTW 聚类算法对机动轨迹聚类的有效性，并且验证了DTW 距离度量方法，可以有效屏蔽与预设分类方法无关的影响因素，提高了类别划分的准确性。通过实验研究发现，相较于DBSCAN 改进DTW 聚类算法，DBSCAN 预分类的DBSCAN 改进DTW 聚类算法，不仅节省了计算时间上的支出，还可以得到更为精确的类别划分效果。当数据规模逐渐增大时，DBSCAN预分类的DBSCAN 改进DTW 聚类算法起到的优化效果更为明显。当其参数取到c=0.20，d=0.020 时，既可以保证较高的正确率，也可以保证算法较高运行效率，此时，DBSCAN 预分类的作用发挥到最大。同时要注意，若参数选取不当，会造成机动轨迹段的大量丢失或大量虚假片段出现的问题。