一种空中目标航迹聚类方法研究*

梁复台，李宏权，孟庆文，蔡莉

(1.空军预警学院 预警情报系，湖北 武汉 430019；2.中国人民解放军31121部队，江西 南昌 330000)

0 引言

为挖掘历史航迹价值、揭示空中目标活动规律，可对航迹进行聚类，得出聚类簇中心航迹，然后将中心航迹作为参考与实时空情比对，以帮助雷达操作员准确判定空中目标属性，辅助指挥员及时对空情作出决策。

传统的航迹聚类方法主要有基于航迹点的聚类、基于部分特征相似子航迹的聚类及面向航迹整体的聚类[1]。这些航迹聚类算法的关键点有2处：一是相似度度量模型的构建；二是高效聚类算法的设计[2]。其中，文献[3]提出的航迹点逐点比对的航迹聚类方法，形成了一个航迹聚类框架。文献[4]对文献[3]的算法进行了改进，根据前后附近点最短距离来对航迹相似性度量，然后将聚类结果应用于终端区的进场程序管制。文献[5]提出基于最长公共子序列相似性度量的聚类算法，根据航迹转折点进行聚类，得到的聚类结果用于异常航迹预测。文献[6]采用最小描绘长度(minimun description length,MDL)理论划分得出航迹关键点，对关键点聚类采用改进的模糊k-means算法。文献[7]提出了基于轨迹聚类的轨迹整体运动趋势提取方法，聚类部分采取了分割再聚类的思路实现。

但这些传统方法均存在着较多不足，基于航迹点的聚类运算量大，耗时长，占用大量资源，且对交叉航线航迹点较难处理；基于部分相似子航迹聚类算法复杂；面向航迹整体的聚类不能太多地兼顾航迹细节特征。针这些不足，本文提出一种空中目标航迹聚类算法，首先对空中目标历史航迹进行曲线拟合，将其由点迹映射为曲线，然后对于曲线的特征点及参量运用k-means算法进行聚类，明显克服了上述算法缺陷。

1 航迹特征提取

对于数据挖掘而言，提取有效的特征是前提，如果提取的特征对事物没有好的区分度，方法再好也无济于事。能将事物很好地区分开的属性特征就是有效的特征，其有弱、中、强之分。能否找到强特征，很大程度上决定着数据挖掘的效率高低甚至数据挖掘的成功与否。

数据挖掘输入的是样本属性。传统关于航迹的数据挖掘方法，样本的属性多选择为移动对象航迹的点迹[3-4]，或者基于复杂运算得到的特征点[5-6]，聚类模型往往都是建立于其上，算法运算量大，影响挖掘速度，算法时效性不高。本文通过航迹拟合得到航迹特征点及对应曲线参数，以此来表征目标活动规律的样本属性，带来了一系列的优势。

航迹是由大量点迹组成的，由于目标的运动轨迹是连续变化的，在一段连续的航迹上，点迹变化平缓，航迹曲线光滑，因此可利用曲线对航迹进行拟合。通过拟合曲线参数来代替大量点迹来进行聚类，得到航迹的参数化特征，减少了样本属性数量，使得算法可以适用于大的样本集。同时还使得运算可以分阶段进行，在传输及存储阶段进行拟合运算，在聚类阶段只对拟合参数聚类，优化了存储和运算资源，减小了数据传输压力，提高了运算效率。

1.1 改进的航迹拟合算法

1.1.1 航迹拟合的基本方法

曲线拟合是指选择适当的曲线类型来拟合观测数据，并用拟合的曲线方程分析变量间的关系。常见的拟合函数有：指数函数、对数函数、幂函数，及多项式。对于空中目标航迹的拟合，考虑到多项式简单易用，拟合计算速度快，拟合效果好，而成为空中目标航迹拟合的首选[8]。对大多数空中目标来说，为了得到较好的燃油经济性并追求最大航程，都会尽快爬升到一定高度采取水平匀速巡航(巡航飞行)，尽量避免改变速度和高度，故航迹信息中高度值的变化较小，在一个很长的时间间隔内保留一个高度值即能反应高度的变化[9]。因此，可在经纬度构成的二维平面上采取用三次多项式y=ax3+bx2+cx+d曲线进行拟合[10]，拟合方法采用最小二乘法。目标函数为使航迹拟合值与点航迹实际值离差平方和(或称残差平方和)最小：

(1)

1.1.2 最优拟合区间的选择

由于航迹轨迹复杂，用一条曲线难以描述其全部特征，故自适应的拟合区间选择成为问题的关键[11]，且拟合区间应该精心选择以达最优效果，过长或过短都会弱化重要特征点的区分作用，导致聚类误差加大，况且，过小还影响压缩效果，占用存储空间。拟合前，首先将原始航迹极坐标转换为直角坐标。然后采用回溯法对巡航阶段航迹选择最优拟合区间，回溯法的实现采用迭代逼近的方式：对于一段长度为L的航迹，假如误差小于所设阈值，再向外延伸1/2距离，如果前后误差相等，则终止循环并退出；如果误差大于所设阈值，则从此判断处往回缩减1/2距离，如此循环迭代，直至前后2次误差相等，拟合误差为

(2)

1.1.3 最优拟合区间段航迹拟合

采用上述拟合方法得出整条航迹的全部自适应拟合区间段，航迹段经度值记为序列Xm=(xm1,xm2,xm3,…,xmnm)，航迹段纬度值记为序列Ym=(ym1,ym2,ym3,…,ymnm)，其中，m为段落数，nm为第m段航迹点迹数目。然后对所有拟合区间段航迹附加如下限制条件重新拟合。

为保持航迹的连续性，对于第1段航迹需要添加这样的限制条件，即该段首尾点值与拟合值一致：

(3)

对后面的最优拟合段(m≥2)拟合的过程中不但要考虑各段落之间的连续性，还需保证光滑性，即上一段的航迹末点为下一段的首点。

(4)

通过矩阵运算，将目标函数及其限制条件转化为二次规划问题[12]，通过在Python环境中调用函数计算，得到各段拟合曲线参数。拟合后的航迹信息用航迹拟合特征点与其所对应拟合区间的拟合曲线参数来表示：[(经度，纬度)，(a,b,c,d)]。

1.2 算法仿真实验

按照上节所述思路，用python语言编程实现算法，然后对一条航迹采用该拟合算法进行仿真，得出航迹位置信息拟合前后效果对比示意图。此段航迹共包含373点迹(图1蓝色点迹所示)，航迹地理位置信息变化明显，比较真实地反映了各类空中目标航迹特征，具有一定的代表性。

图1 固定划分航迹拟合图

文献[8]的轨迹拟合算法对航迹段落进行了固定划分，虽然一定程度上解决了拟合效果不好的问题，但在段落划分较少时还是存在着与真实航迹偏差太大的问题，如果划分过密，又达不到压缩数据量的目的。图1中分段数达到35，拟合曲线才较好地吻合原航迹。

图2 自适应的航迹拟合图

对于自适应的航迹拟合方法，在不附加限制条件的情况下，拟合误差σ=0.000 01时，红色圆圈表示拟合特征点，红色曲线为与拟合特征点对应的拟合曲线。从图2可以看出，航迹在自适应拟合段的连接处出现断续，且每段之间连接不光滑，模拟真实航迹存在着一定的失真。

采用本文中所示方法，在拟合误差σ=0.000 01时，自适应航迹段数目为8，原始航迹曲线与拟合后的曲线吻合很好，连续性及光滑性都得到了很好的体现，见图3。很好地保留了航迹信息特征，实现了航迹信息存储与挖掘分析以及可视化各方性能的兼顾。

图3 改进自适应拟合航迹图

2 基于k-means的航迹聚类

聚类是一种无监督学习，将对象划分为不同的簇，同一个簇中的对象“相似”，不同簇之间对象“互异”[13]。聚类方法有基于原型的方法、基于层次的方法、基于密度的方法、基于网格的方法和基于模型的方法。基于原型的聚类方法中，对象的相似性通常通过距离函数来度量，这个特点适用于对于航迹信息的聚类。基于原型的聚类方法常用的有k均值，k-means++是它的改进型，解决了k-means方法因初始中心选择不当导致簇效果不佳或收敛慢的问题[14]。本文采用k-means++算法实现聚类，简记为k-means算法。

2.1 航迹特征点聚类

k-means算法的基本思想是：首先从特征集中随机选择k个特征点作为初始簇中心；然后将n个数据对象划分为k个簇以便使其距离满足：同一簇中的对象相似度较高；不同簇间的对象相似度较小。k-means++在初始点的选择上作了优化。给定样本集D={x1,x2,…,xm}，聚类所得簇C={c1,c2,…,ck}最小化平方误差：

(5)

通常对“相似度度量”都是基于某种形式的距离来定义，距离大小与相似度大小成反比。最常用的距离是闵可夫斯基距离，对于给定样本xi=(xi1，xi2，…，xin)与xj=(xj1，xj2，…，xjn),有

(6)

当p=2时闵可夫斯基距离就是欧式距离,当p=1时为曼哈顿距离[15]。在本文中，采用了欧式距离作为相似度的度量。

对整段航迹通过选取自适应拟合段落，得到各段航迹特征点及拟合曲线系数，建立起关于整段航迹的新的特征集。对某空域中所有航迹拟合时选取统一的误差阈值，得到的新的航迹特征集则能够代表原航迹，解决了传统以所有航迹点作为航迹特征来聚类，所带来的运算量大、准确率不高的问题。对1.1节所述航迹采用自适应航迹拟合算法，将原航迹373点迹压缩为8个特征点，数据量减少了98%,除去拟合环节的开销，在聚类环节，运算量相应减少了98%，这在实时航迹匹配中可以提高运算速度。

k-means算法的缺点是必须事先指定先验的簇数量[16]。对于航迹数据聚类中心数目的确定，可以事先根据拟合特征点的分布，经可视化处理最终确定，也可以通过二分k-means或通过肘部法和轮廓系数图对聚类效果进行评定，帮助选出最优k值。本文采取肘部法评估、可视化辅助的方法选定最优k值。

2.2 航迹曲线系数聚类

对最优航迹拟合段特征点进行聚类，还存在准确率不高的问题，在此基础上，结合航迹最优拟合段曲线系数聚类，可以形成印证互补，提高正确率。

多项式系数决定着多项式曲线的形状，从系数上能够区分拟合曲线所表示的航迹。可对于三次多项式拟合所产生的4个系数，较难在其上确定“序”的关系，属于无序属性，不能直接用闵可夫斯基距离来度量[17]。

对本文中航迹拟合所采取的三次多项式求导可得y′=3ax2+2bx+c，取Δ=4b2-12ac，Δ=0是其是否单调的临界点，再通过a值的大小，完全可以确定目标航迹的运动特征。通过观察三次函数图像(如图4所示)，不难发现a与Δ决定着曲线的形状及性质。a的大小决定函数曲线递增与递减性，Δ的大小决定着函数曲线的单调性。故本文中将系数(a,b,c,d)转化为(a,Δ)2个属性来表述拟合航迹段。

图4 三次函数图像及性质

在实际的聚类操作中，这2类属性具有不同的量纲，这样会影响到航迹聚类的结果，为了消除属性之间的量纲影响，需要进行属性数据归一化处理，以使航迹之间具有可比性。本文采用min-max normalization的归一化方法，特征量化的公式为

(7)

考虑到现实中曲线的递增与递减较明显地表示了航迹的走向，而单调性对航迹的区分没有太大的影响，这里采用加权的闵可夫斯基距离来进行相似度度量：

(8)

根据多次的尝试，式(8)中的权值确定为w1=0.7,w2=0.3较合适。

2.3 实验分析

2.3.1 航迹特征点聚类效果

(1) 误差阈值的影响

模拟某空域一段时间航迹轨迹数据，有3类23条航迹，共4 051点迹，在对其运用自适应拟合方法后，得到航迹特征点集，对其采用k-means方法聚类后效果如下：

误差阈值取0.000 01时，得到共141个航迹拟合特征点，虽然能够很精细地体现航迹特点，但对于航迹聚类来说，聚类的效果不理想，只有一类5条航迹完整地分辨了出来，见图5。误差阈值取0.000 1时，得到共58个航迹拟合特征点，拟合精细度较上次有所降低，聚类的效果有提高，但还是不够完美,将一类折返航迹分成了2类航迹，如图6所示。

误差阈值取0.001时，得到共33个航迹拟合特征点，由图7可以看出，聚类结果将3类航迹完全区分了出来。由此看来，误差阈值的取值与拟合精细度成反比，与聚类效果成正比，在不是航迹重现的场合，可以放宽阈值的设置来达到更好的聚类效果。

(2) 最优簇数目k值的确定

按照肘部法的思路，先用航迹总数作为k值代入聚类，逐次递减，监控在该过程中所有样本点到其所属类簇距离的平方和，在该值明显出现肘部时所对应的k值即为最优簇数。

图5 误差阈值取0.000 01时

图6 误差阈值取0.000 1时

图7 误差阈值取0.001时

由图8可看出，对2.2节所述空域航迹聚类，k值最后确定为3，这个和现实中的航迹类别数目相吻合(参见图7)。

图8 肘部法确定最优簇数目k值

2.3.2 航迹曲线参数聚类效果

对于交叉的航迹，对于航迹点采用聚类方法包括k-means、DBSACND(基于密度的聚类算法)都无能为力。从2.3.1节实验可以看出，在拟合误差阈值取较小时，拟合特征点迹数量较多，存在不同航迹特征点同在一个簇中，但特征点对应的航迹曲线不属于同一类型的情况，即存在航迹交叉现象，此时难以有效区分航迹，聚类效果不好。在对自适应拟合段特征点聚类的同时，结合拟合段曲线参数聚类，可以提高聚类航迹聚类效果。经实验，在结合特征点曲线系数聚类后，对航迹的聚类性能提升明显，误差阈值取0.000 1时，仍然可以实现航迹正确聚类。

3 结束语

针对传统航迹聚类算法计算量大、实时性差等问题，本文首先提出了自适应的航迹拟合算法，从原始航迹中提取少量特征点及对应的拟合曲线，然后采用k-means方法对特征点进行聚类，从而实现了航迹的聚类区分。通过实验仿真可以看到，选取合适的误差阈值可以实现大量航迹的有效聚类，可以将不同运动特征的航迹区分开来。在运用到真实航迹聚类时，为使得算法效果更好，可结合航迹信息所表征的空中目标运动属性，如飞行高度、速度、加速度、爬升率等，以更精准地实现空中目标航迹聚类。