自适应DBSCAN算法在快速落点预报中的应用研究*

陶鹤丹 项树林 吴诗帆

（91550部队 大连 116000）

1 引言

在高空飞行器飞行任务中，落点预报结果是判断实时飞行器飞行态势，实施安控的重要依据，依靠有限的测量数据提高落点预报的精度与可靠性至关重要，这就需要使用高效聚类算法。落点预报往往基于不同设备测量的多组数据，这些数据一般呈散点状态分布，若默认测量设备误差为单纯的机器误差，可以认为任一设备的测量数据均为围绕实际落点产生的随机分布，服从概率统计规律。因此，利用可靠的聚类算法，获取尽可能精确的落点统计信息是可行的。

在现今军内飞行任务中，多采用K-means聚类算法进行落点统计，但K-means聚类算法具有只适用于凸数据集、受异常点影响较大、必须提前确定聚类簇数等局限性［1］，因此，本文提出了使用DBSCAN 算法应用于快速落点预报。DBSCAN 密度聚类算法是经典聚类算法之一，通过判断样本分布的疏密程度区分获取类别簇。与K-means 聚类算法相比，DBSCAN算法有以下几点主要优点：

1）可以对任意形状的稠密数据进行聚类［2］。

2）对样本集的噪声点不敏感，可以主动发现并排除测量数据中的异常点［3］。

3）无需提前确定簇数，对于未知簇数样本亦能聚类［4］。

这些特性都很好地适用于样本集复杂、异常点较多、残骸数目不定的快速落点预报。但是，工程实践表明，DBSCAN算法在应用中存在以下缺点：

1）通过设定的邻域半径（Eps）与邻域内最少样本的数量（minPts）来区分高密度区域与低密度区域［5］，所以，DBSCAN 算法对于全局参数的选取十分敏感。常规DBSCAN 算法选取参数依靠人工干预，在密度分布不均或先验信息少等情况下，很难选取较优的参数组合，很可能出现聚类错误甚至聚类失败的情况［6］，本文旨在解决该问题。

2）样本集较大时，聚类收敛时间长。可以通过KD树等限制样本数量的方法进行优化［7］。

3）聚类间距相差较大、疏密特征不明显时，聚类质量较差。

鉴于此，本文依据实际任务中快速落点预报的算法需求，分别基于样本集自身数据特征与核密度估计，在实测落点数据集中实现并分析了两种自适应合理设定DBSCAN算法全局参数的方法，有效解决了DBSCAN算法人工干预的问题。

2 常规DBSCAN算法原理

DBSCAN 算法的前提为假定样本集的类别可以通过样本分布疏密程度来区分［8］。该算法通过确定邻域半径Eps与最小阈值minPts大小来确定样本集中的核心对象，通过遍历找到所有核心对象的全部密度可达对象，从而得到每一核心对象最大密度相连的样本集合，自动确定最终的类别簇［9］。

算法流程具体如下：

1）首先通过计算样本集D中任意两点的距离，通过距离度量在样本集中找到全部满足预设条件的核心对象xi，即满足xi为圆心以Eps为半径的邻域内包含的样本数目满足N(xi)≤minPts，将xi加入核心对象集合C，初始化聚类簇数k=0，未访问样本集T=D；

2）判断当前核心对象集合C是否为空，若核心对象集合为空则进入步骤6），否则继续步骤3）；

3）在核心对象集合C中，任意选取一核心对象i，初始化当前簇核心对象队列Ck={i}，初始化簇序号k=k+1，初始化当前簇样本集合Wk={i}，更新未访问样本集合T=T-{i}；

4）若当前簇核心对象队列Ck=φ，则认定当前聚类簇Wk生成完毕，更新核心对象集合C=C-Wk，转入步骤2），否则更新核心对象集合后继续步骤5）；

5）在当前簇核心对象队列Ck中取出任一核心对象i'，在邻域半径Eps范围内找出全部的子样本集，将该子样本集与未访问数据求交集，将交集结果Δ 更新至当前簇样本集合，再将其从未访问样本中删除，更新当前簇核心对象队列Ck=Ck∪(Δ ∩C)-i'，转到步骤4）；

6）此时输出的结果W={W1，W2，…，Wk}即为簇划分结果，根据划分的结果，使用K-means 算法得到每簇中心点，即落点预报中统计得到的落点位置。

3 两种自适应DBSCAN算法

3.1 基于样本集数据特征确定全局参数

该种方法依据类中样本的距离计算及统计确定，算法流程如下：

1）首先使用传统DBSCAN 算法对数据集进行简单聚类，得到聚类簇数k与聚类结果{W1，W2，…，Wk}；

2）在类Wi中，计算任意两点之间的距离，得到距离集合Di；

3）统计集合Di中的最大值与最小值，求其差值Δ，将Δ 划分为t个区间；

4）求出每个区间中包含的样本数目，确定包含最多样本数目的区间，将该区间的距离中心值确定为该类的Epsi；

5）确定Epsi后，求出该类中全部样本距离在Epsi范围内的样本数量，对得到的数量矩阵使用K-means聚类，确定中心点设定为该类的minPtsi；

6）判断是否遍历过全部类簇，若否则转至步骤2），若是继续步骤7）；

7）选取各类的minPtsi的最大值作为最终的minPts，即各类对应的参数值为（Epsi，max(minPtsi)），在聚类时首先判断所属一级类簇，自适应调整参数后确定最终类簇。

3.2 基于核密度估计确定全局参数

该种方法依据核心平滑密度估计确定，核密度估计是刻画数据分布特征，有效检测出噪声点的一种非参数方法，原理为假定待聚类样本集中的样本都是独立随机的，且属于某一未知概率密度函数，其分布函数为f(x)，那么，该样本集的核密度估计值为

核函数与光滑参数的选取均会影响核密度估计的精确性，根据大量研究表明，核函数对于精度的影响远没光滑参数的影响大，可以根据实际需求选择核函数，本文选用复杂度较低的高斯核函数。应用于聚类时，样本集即为所有样本之间的距离矩阵，全局参数Eps即为光滑参数值，为使聚类结果最佳，需要将光滑参数值设置在一定范围内，根据文献［10］，最佳的光滑系数如下式所示：

为降低计算复杂度，在样本方差较低时，采用Silverman提出的拇指法则［11］，方差对应的正态密度代替函数f''，使用样本方差代替σ，得到Eps值为

将所有样本半径为Eps的空间内存在的对象数Pi和的平均值定义为minPts，即为

3.3 仿真分析

在飞行测控过程中，为了实时测量信息准确、有效，通常会在航区范围内布设大量的测量设备对飞行目标进行测量，主要包括连续波雷达、脉冲雷达以及GPS 等，根据设备测量体制不同，使用单台设备或几台设备组合形成多种类型的测量方案，可以获得多组落点预报数据。依据装备组合形成的测量方案，可以划分为高精度的交汇测量方案和精度稍差的单站定位测量方案。前者以连续波雷达交汇测量、GPS 为主，后者以脉冲雷达单站定位为主［12］。各种精度类型的测量数据，可以计算形成多组落点预测值，因此，最后参与统计分析的落点预测值是不同组合、不同精度值的混合样本值。

为了验证本文算法，进行仿真试验与对比分析，本文涉及算法均采用Matlab 进行实现，采用数据集均使用某次任务实测单一落点数据，数据均经过脱密清洗处理，该次任务的实际落点坐标为（98.2940，35.3766）。在下文中，基于样本集数据特征确定全局参数的方法简称为方法1，基于核密度估计确定全局参数的方法简称为方法2。

3.3.1 高精度数据集仿真分析

首先针对某高精度跟踪设备的落点测量结果进行仿真聚类，该种数据集特点为数据精度较高，聚集性较强，聚类结果的准确度主要受设备误差及个别异常点影响，仿真得到聚类结果如表1 与图1。

图1 高精度设备测量数据聚类结果

表1 高精度设备测量数据聚类结果

通过表1 可知，由于该数据集聚集程度较高，疏密特征明显，三种方法的聚类计算结果精度均较高，但通过图1（a）～（c）三张图对比可以看出，常规DBSCAN 算法受噪声点影响较大，而两种自适应DBSCAN 算法在仿真中虽采用了不同的参数组合，但是所得聚类结果相近，能够主动发现并排除噪声点，抗干扰能力强，统计落点与实际落点十分接近，精度均较常规DBSCAN算法有所提高。

3.3.2 低精度数据集仿真分析

下面针对某型单站低精度跟踪设备的测量数据进行聚类，该型数据集的特点是数据质量较低，随机误差较大，落点散布分散，聚集性较差，对聚类算法考验较大，但可以尽可能多地保留数据特征。仿真得到聚类结果如表2与图2。

图2 低精度设备测量数据聚类结果

表2 低精度设备测量数据聚类结果

根据表2 可知，低精度数据集对全局参数选择的要求更为苛刻，常规DBSCAN算法依靠人工干预极易导致聚类失败、无法聚类，必须使用算法进行优化。通过图2（a）可以看出，对于数据聚集程度较弱的数据集，使用方法1 确定全局参数进行聚类依旧可以得到较高精度的聚类结果，缩小了由于测量误差导致的对落点计算的影响。而通过图2（b）可以看出，方法2 确定全局参数受数据聚集程度影响较大，会将一些可用数据错误的聚类成了其他类别，导致可用数据缺失，破坏分布的平衡性，导致聚类结果偏差较大。

可以得到结论：

1）数据聚集程度对DBSCAN算法影响较大，数据聚类间距较大会大幅降低DBSCAN算法的准确性。

2）对于该类疏密特征不鲜明的数据集，使用常规DBSCAN 算法极易失败，无法保证工程应用，而两种自适应改进算法均能得到聚类结果。两种方法中，方法2 受数据聚集程度影响更大，容易导致个别样本错误聚类。在工程实践中，对于该类数据集的聚类，建议使用方法1，能得到相对准确的结果。

3.3.3 混合精度数据集仿真分析

在实际的飞行任务中，高精度测量设备测量方式往往以应答为主，测量的准确性与快速性依赖于弹上设备，而低精度测量设备以反射为主，排除了这类依赖造成的风险。为减少风险、提高精度、尽可能获取更加全面的数据特征，往往会使用低精度测量数据作为高精度测量设备数据的补充，得到不同组合、不同精度值的混合样本，不同的测量设备误差混杂会导致数据集复杂度变高，对聚类方法的要求也更高。为检验本文方法在混合数据集中的聚类效果，将两种测量精度差异较大的测量设备对同一飞行目标的测量数据混合，进行极端情况下的检验，仿真结果如表3与图3。

图3 混合精度设备测量数据聚类结果

表3 混合精度设备测量数据聚类结果

根据表3可知，在混合数据集环境下，常规DBSCAN 算法受低精度样本集影响较大，聚类精度较低，而两种自适应确定全局参数的DBSCAN算法仍能取得相对较高的落点计算精度。通过图2（b）与图2（c）可以看出，两种方法的聚类结果均受低精度样本集影响较小，方法1 聚类更为严格，仅选取数据集中最密集部分进行聚类，抛弃的噪声点更多，虽说在本次仿真中取得的聚类结果更为精确，但易产生遗漏数据特征的情形，方法2 聚类相对宽松，虽说在本次试验中聚类精度低于方法1，但是可以尽可能地保留样本集的多种数据特征，在应用环境中，要根据实际情况进行选择。

可以得到结论：

1）在高低精度混合数据集的情况下，两种自适应改进算法均能较大幅度提高常规DBSCAN 算法的聚类精度。

2）在快速落点预报的工程实践中，对于此类高低精度差异较大的混合数据集，为了尽可能地保留低精度测量设备的数据样本特征，降低设备故障等意外因素可能造成的风险，建议使用方法2。

通过多次仿真，可以得到三种方法针对快速落点预报中不同精度类型的数据集中的聚类精度效果对比如表4，在工程应用中，要依据上文的分析结论，根据参试设备的实际精度情况进行选择。

表4 聚类精度效果对比

4 结语

本文针对在快速落点预报应用中K-means 聚类算法局限性较大且常规DBSCAN 算法人工选取参数困难的问题，对提出的两种自适应DBSCAN聚类算法进行了研究分析，并利用实测落点测量数据进行了仿真测试。结果证明，根据测量设备实际精度情况区分高精度、低精度、混合精度选择自适应DBSCAN 算法，可以得到较优的参数组合，在复杂条件下亦能取得较好的聚类效果，统计落点结果较常规DBSCAN 算法精度提升较高，效率较优，有效解决了常规DBSCAN 算法人工干预参数导致聚类质量恶化的问题，且保留了常规DBSCAN算法的特性与优点，适用于快速落点预报。但也存在不足之处，对于疏密程度不明显的数据集的聚类准确率较低，如何解决该问题仍是下一步的研究方向。