基于改进CFSFDP的雷达信号预分选方法

韩佳宝, 崔天舒, 李志豪, 黄永辉, 安军社

(1.中国科学院国家空间科学中心复杂航天系统电子信息技术重点实验室,北京 100000;2.中国科学院大学,北京 100000; 3.清华大学北京信息科学与技术国家研究中心,北京 100000)

0 引言

雷达信号分选技术是电子侦察的重要环节,随着现代战场电磁环境的日益复杂,雷达信号脉冲密度达到数十万甚至数百万每秒[1],传统的一步式分选方法难以处理如此密集的信号,现代雷达信号分选主要分为预分选与主分选两步,其中,预分选主要利用雷达信号的载频(CF)、脉冲宽度(PW)、到达角(DOA)等特征参数对信号进行聚类,以降低信号脉冲的密度,实现初步分选,便于后续主分选等环节的进行。因此,良好的聚类预分选是实现雷达信号准确分选的必要前提。在过去几十年里,关于聚类问题,学者们提出许多经典思路,比如基于密度、基于模型、基于网格、基于层次及基于划分等方法[2]。

K-means[3]是一种经典的基于划分的方法,数据被划分为K个簇并迭代优化,最终形成稳定聚类结果,局限性在于只适用于球形簇,且难以发现信号中的异常值。同时,该方法的准确性受限于簇类别数及初始聚类中心的选取。DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种基于密度连通区域的聚类方法[4],相比于基于距离的方法可以发现任意形状的簇,但需要人为设置簇内邻域半径(Eps)和簇内最小样本数目(MinPts),限制了该方法处理未知雷达数据的性能。近邻传播(Affinity Propagation,AP)[5]聚类是一种基于信息传递的方法,通过节点之间迭代的吸引度与归属度两种消息的传递,判决出各信号样本的聚类中心,其优势在于不需要预先人为设定聚类数目,对信号之间的相似度矩阵的对称性没有要求,因此,针对不同雷达信号数据具有较强的灵活性,但最终聚类效果受限于其中偏向参数的设置,同时难以适应大规模雷达信号数据的处理。

以上典型方法存在各自相应的局限性,不能很好地适应聚类预分选的需求。近年来,关于聚类预分选,不少研究团队在上述方法基础上做出了改进,文献[6]在传统K-means方法基础上联合数据场理论,提出了一种融合算法,首先通过数据场聚类方法得出初始聚类数目和聚类中心,再以此为基础进行K-means聚类,解决了对聚类数目设置的依赖以及对初始聚类中心选取敏感的问题,但该方法相较于K-means计算复杂度大大增加。文献[7]针对DBSCAN方法不能很好处理密度分布不均匀雷达信号的局限性,借助OPTICS方法[8]和网格划分方法提出了一种两级聚类预分选措施,依次处理高密度信号与低密度信号,该方法效果依赖于距离半径、簇内最小样本数目等先验参数的设置。

2014年,RODRIGUEZ等[9]提出一种基于密度和距离的新聚类方法CFSFDP(Clustering by Fast Search and Find of Density Peaks),其具有聚类速度快、适应任意形状分布、经验参数设置少的优点。通过计算每个样本点的局部密度和可达距离,根据两个参数形成的联合信息,判决聚类中心点,并将剩余未判决点按照密度优先原则,以就近原则依次将点分配到高密度点所属簇中。

本文在此方法的基础上,结合现代雷达信号参数的分布特点,做出以下改进:一是利用直方图均衡化思想缓解算法性能对截断距离dc设置敏感的问题;二是改进可达距离计算方法和数据所属簇分配规则,以适应数据密度分布不均衡的情景。

1 CFSFDP方法原理

该方法基于两个假设:1) 簇的中心被拥有更低密度的邻居点包围;2) 每个聚类中心到其他中心的距离较远。在此基础上,该方法关注数据点的两个特征参数:局部密度ρi和当前点与最近的更高密度点的可达距离δi。假设数据点样本集合为X={x1,x2,x3,…,xn},数据点i与j之间的距离dij为两个点之间的欧氏距离,方法具体步骤如下。

1) 计算局部密度。

截断核表示为

(1)

式中,

(2)

为阶跃函数。

高斯核表示为

(3)

式中,dc为截断距离,根据启发式方法进行设置,需要人为设置,一般范围为1%～2%[9]。

2) 计算可达距离。

δi表示数据点i和最近的高密度点之间的距离,表示为

(4)

3) 聚类中心的确定。

根据计算得到的局部密度ρi和可达距离δi形成决策图,人工从其中找到两者都较大的点作为聚类中心。

4) 分配非聚类中心点。

对未分配的点按照局部密度从大到小的顺序,依次将其分配到距离最近的高密度点所属簇中。

2 改进的CFSFDP方法

通过上述对CFSFDP方法的原理说明可以看出,该方法的有效性取决于dc的设置,其直接关系到每个样本点局部密度的计算,最终聚类结果对dc设置较敏感。在原始算法中,dc的选取是基于启发式的,即dc应确保平均每个点的邻居点的数量占到整个数据集样本量的一定比例,这个值一般被设置为1%～2%。针对雷达信号分选所面临的信号参数密度分布不均衡的特点,这种启发式方法显然不是一种科学合理的选择。同时,其中提到的可达距离计算方法、信号类别的分配规则也需要改进,以更好地适应复杂雷达数据的聚类场景,下面将对改进方法展开具体分析与论述。

2.1 直方图均衡化理论

首先,对数据各维度特征进行归一化,计算各数据点之间的距离形成距离矩阵

(5)

根据计算局部密度的方法可以看出,各数据点的相对密度大小只决定于相互之间的距离大小,不受dc的影响,因此可以完成直方图的均衡化[12],即

(6)

式中:k=1,2,…,L-1,L为离散化的灰度级数;ni为灰度为i级的样本点数;n为总样本点数。直方图均衡化后的密度矩阵为Rhisteq。

2.2 改进的可达距离

原始CFSFDP方法仅依靠点与点之间的最近距离信息当作可达距离,忽视了与周围其他点之间的关系,这使得原始方法虽然可以在简单的数据集上获得不错的效果,但不能很好地反映点与点之间的复杂结构关系,因此在处理密度差异较大、参数相互交叠的数据时,性能下降显著。比如,按照原始方法在全局范围内寻找与当前点最近的高密度点,当不同簇的数据密度差异较大时,很有可能面临离真正隶属的簇较远,被划分到其他簇的可能。因此,综合考虑距离与数据结构信息尤为必要。对于数据集X中任意一点i,寻找密度大于i的点j,然后最小化两点之间的距离与到它们各自k最近邻点距离和的乘积作为点的可达距离δi。定义i,j两点到各自k近邻点的距离之和θ(i,j)为

(7)

式中:dij为i,j两点之间的距离;Γ(i)是点i的k最近邻点所构成的集合;p为集合Γ(i)中的点;q为集合Γ(j)中的点。

可达距离δi为

(8)

对于最高密度点,其可达距离为

(9)

当k增加时,点i和j之间的最近邻点数量会增加,点i和j到各自邻居点的距离之和也会增加,即导致θ(i,j)的增加,但影响程度因数据簇密度不同而有差异,对于低密度簇,增加较为明显,而对于高密度簇,增加较少。

假设dij是常数固定值,当点i,j到各自的邻居点距离较远时,会使得δi较大,即在随后的决策图中低密度簇的聚类中心更容易被发现。

假设θ(i,j)是常数固定值,如果点i与j之间的距离较大,那么也会导致δi较大,这满足了原始CFSFDP方法中对于两个聚类中心之间相距较远的假设。反言之,当两个点之间欧氏距离较小时,很难同时成为聚类中心。

通过以上分析可以看出,此处定义的δi不仅考虑到了点之间的距离因素,而且考虑到了点周围邻居点的信息,这对于提高同时含有高低密度簇的数据集中低密度簇的聚类性能有实际意义。因为对于低密度中心点而言,在决策图中虽然密度不占优势,但可达距离较大;反之,高密度点的密度虽然较高,但可达距离较小;如此相互平衡,可以较好地解决原始CFSFDP方法中难以无遗漏发现密度差异较大数据集聚类中心的问题。

在阈值设置过程中,切比雪夫不等式仅基于数据的均值与方差进行计算,适用于任意分布数据,在确定界限时不需要考虑数据的分布情况。通过前面分析可知,相比于非聚类中心,聚类中心的局部密度和可达距离应该明显较大,因此文献[13]提到可以将归一化后密度的上限ρ*设置为

ρ*≥μ(X)+τσ(X)

(10)

式中:μ表示期望;σ表示标准差;τ经过验证选取为2较合适。

(11)

在分别得出局部密度和可达距离的阈值后,应该考虑如何设置最终阈值判决函数,将两个参数信息综合考虑,准确识别出聚类中心所在。如果只是将两个参数进行线性组合构成最终门限函数,那么当某些中心点的其中一个参数超过阈值,另一个没超过阈值;或者两个参数都在阈值附近,但明显大于一般点的参数值。在这些情况下,两个参数线性组合构成的门限函数不能很好判决聚类中心。

(12)

根据判决门限函数,对数据集中的所有数据点进行判断,满足条件的被识别为聚类中心,实现了聚类中心的自动判决,无需人为手动识别。

2.3 改进的分配准则

原始CFSFDP方法直接根据局部密度降序的顺序,将非聚类中心点分配到最近的高密度点所属簇中,这种方法没有考虑到点自身所处的周围邻居点信息,很容易错误地将低密度点划分到不正确的高密度簇中,因为距离最近的点不一定同属一类。同时,这种按照密度降序分配的规则,一旦中间出现错误,很容易造成后续点分配的链式错误。因此,为了更好地结合点自身所具备的密度信息和所处的周围数据结构邻居点信息,文献[15]提出对当前未被分配的点求出其最近的M个高密度点,评价当前点与这M个点的相似性,相似性评价方法是当前点的k邻居点集合与高密度点的k邻居点集合交集的大小,交集越大,说明两者相似性越高,与该高密度点同属一簇的概率也越大。本文认为,这里对于雷达数据密度差异可能较大的情况,会出现当前点与不同簇的高密度点都有交集的情况,此时难以判断最终所属类别。同时,交集大小也是对于两者距离相近程度的一种度量,没有很好地反映周围数据结构信息。因此提出,对于一部分高密度点,按照就近原则进行分配,对于其余所有点,找到当前点的M个高密度近邻点,对其所属类别进行投票,按照少数服从多数原则,进行所属类别的判决。这里既考虑到了距离因素,即相似性程度,又考虑到了周围数据结构信息,对复杂数据分布适应性更好,因此将当前点i所属簇判决为

(13)

式中:φi为i点所属簇;k为近邻点数;nclus为识别出的聚类中心数;mod(·)为查找众数函数,ν(i)为i点的M个近邻高密度点集合。

2.4 改进CFSFDP方法流程

输入:包含特征参数的雷达脉冲序列数据集。

1) 对数据进行归一化预处理;

2) 计算样本数据集中各点之间的距离,形成式(5)距离矩阵;

3) 设置初始截断距离,根据式(3)计算局部密度,并根据式(6)对密度值进行直方图均衡化;

4) 按照局部密度降序排列,根据式(8)、式(9)计算改进的可达距离;

5) 对参数值局部密度、可达距离进行归一化,并根据式(12)自动判决可能存在的聚类中心;

6) 根据改进的分配准则式(13)对非聚类中心点进行分配。

输出:数据集中各点所属簇信息。

3 实验结果及分析

为验证本文所提方法的有效性,通过仿真数据集及UCI标准数据集(Aggregation[16],Jain[17],R15[18])进行实验,验证方法在不同参数分布特点下的性能,并与原始CFSFDP方法及典型的聚类方法(如DBSCAN,K-means,AP,OPTICS)进行比较。

实验1 仿真数据集实验,仿真参数如表1所示。

表1 仿真数据参数

表1中,12部雷达辐射源数据参数之间存在交叠,以模拟真实雷达信号分选过程中面临的实际情况。按照方法流程,对数据归一化后,据式(3)、式(6)计算出数据集直方图均衡化后的局部密度Rhiseq,据式(8)、式(9)计算改进的可达距离δi,二者分别归一化后根据式(12)计算得到门限决策值γ,如图 1所示。

从图1中可以准确识别出12个聚类中心点,最后根据改进的分配准则式(13)对所有点进行所属类别的分配,形成如图2(a)所示的聚类结果,原始CFSFDP方法聚类结果如图2(b)所示。

图1 仿真数据γ值

图2 改进前后聚类结果

从图2结果可以看出,得益于均衡化及改进的分配规则,改进CFSFDP方法对于信号参数距离较近情况下的聚类性能得到了提升。

采用调整兰德系数(ARI)、调整互信息(AMI)和F1-measure值评价算法对仿真数据集的聚类结果进行评价,指标对比如表2所示。其中:ARI及AMI用来衡量真实值与聚类结果之间分布的吻合程度;F1-measure综合考虑召回率与精确率两个指标,更完整地评价算法性能。

表2 仿真数据集聚类结果

通过表2中不同方法对仿真数据集的聚类结果性能指标对比可以看出,本文方法在参数交叠、不同簇相距较近的情况下有较好的性能提升。

实验2 UCI标准数据集实验。

图3展示了6种方法(DBSCAN,K-means,AP,OPTICS,CFSFDP,本文方法)在UCI的3个标准数据集上的实际聚类效果,最终性能评价指标对比如表3所示。

图3 6种方法在3个数据集上的聚类结果

表3 3个数据集聚类指标对比

通过实验结果可以得出:本文方法与K-means方法在R15数据集上性能相当,但对于聚类数目的先验信息错误时K-means性能下降明显;DBSCAN方法在3个数据集上适应性较好,而本文方法性能总体优于DBSCAN方法;本文方法与原始CFSFDP方法在Aggregation及R15类球形分布且点密度均匀数据集上都可以取得较好结果,但在Jain密度不均匀数据集上本文方法性能明显优于原始CFSFDP方法及其他聚类方法。综上可以看出,本文方法相比于原始CFSFDP方法及经典聚类方法有更好的适应性,在参数交叠、密度分布不均匀、任意形状数据集上的聚类性能也得到了提升。

4 结束语

本文重点对应用CFSFDP方法进行雷达信号聚类分选任务面临的问题进行了研究并提出改进方法,针对聚类结果对dc设置敏感的问题采用均衡化思想对局部密度进行处理,可适应不同分布数据聚类需求;针对信号参数交叠、参数密度分布不均衡的复杂场景,提出改进的可达距离计算方式,在考虑密度信息的同时添加数据结构信息,同时改进对非聚类中心点的分配规则,提升应对复杂数据集的分选性能。最后,通过不同分布特点的数据集验证了所提方法的有效性。实验表明,本文的方法可以较好地实现对不同分布特点下数据的自动聚类分选,同时,与原始CFSFDP方法及经典聚类方法对比显示本文所提改进方法具有良好的聚类性能。今后将考虑提取挖掘雷达信号新特征,应用到聚类预分选环节,提升算法性能,为信号主分选及目标识别等任务奠定基础。