针对非合作目标的自适应网格聚类算法

栗大鹏, 梁伟

(1.北京理工大学 机电学院， 北京 100081; 2.北京遥感设备研究所， 北京 100854)

针对非合作目标的自适应网格聚类算法

栗大鹏1,2, 梁伟2

(1.北京理工大学 机电学院， 北京 100081; 2.北京遥感设备研究所， 北京 100854)

武器系统的探测设备通常面对的是非合作目标，观测样本在特征空间中的分布形式难以预期，噪声、不规则的类簇形状以及差异化的类簇密度给聚类分析带来极大挑战。提出了一种自适应的网格聚类算法，该算法包括基于k-近邻方法的空间分辨率自适应网格化处理方法，以及基于自适应分水岭变换的类簇结构检测与划分方法。实现了对噪声以及密度差异极大类簇的自适应处理，同时保留了网格聚类方法对类簇形状不敏感、不需要类个数作为先验参数等优点。通过雷达、电子侦察以及复杂人造数据集的仿真，证明了该算法的有效性。

人工智能； 网格聚类； 可塑性面积单元问题； 分水岭变换

0 引言

聚类分析是一种无监督的模式识别技术，在雷达、引信、电子侦察、激光红外等武器系统的目标探测设备中有广泛的应用。该技术试图解决如下问题[1]：对于包含n个对象的集合，根据相似性将其划分为若干个组，使得同组对象之间的相似性较高，而不同组对象之间的相似性较低。图1仿真了电子侦察系统收集的对象在方位角、俯仰角二维空间上的分布，其中存在4个类簇。

图1 电子侦察仿真数据集Fig.1 ELINT simulation dataset

武器探测系统主要面对非合作目标，目标的信息(如位置、速度、频谱、能量等)通常是不完整的，因此不能实现完全匹配处理，导致目标探测样本在特征空间中的聚合性较差，分布形式难以预期，某些情况下甚至非常不规则，给聚类分析带来诸多困难，包括：

1)类的个数未知。对于武器系统，类的数量(通常对应目标个数)在很多时候是未知的，而一些聚类算法需要类的个数作为先验参数，制约了其在这些场合下的实用性。

2)类的形状不规则。因为接收系统与目标信号形式的非匹配性，观测对象在特征空间中聚集性较差，类簇的形状可能会发生畸变，形成非凸壳类簇，如图1左上的类簇。这些类簇很难确定类中心的位置，从而影响某些聚类算法的效果。

3)类簇间对象密度的差异。对象的相似性通常用特征空间中的距离或密度进行衡量。而在某些情况下不同类簇的对象密度差异较大，如图1所示，右侧两个类簇的类间距离与左下类簇的类内对象间距可以比拟。这种情况下很难确定统一的相似度门限。

4)噪声对象的影响。现代战场上存在大量有意干扰和无意干扰，而且很多情况下信噪比水平是时变的。因此聚类算法需要考虑对噪声对象进行自适应的抑制。

现有的聚类算法一般被分为5类，分别是划分式算法、层次化算法、基于密度的算法、基于网格的算法以及基于模型的算法[1]。从算法的实时性角度来看，划分式算法以及基于网格的算法相对其他算法有明显优势。然而，以K-means、C-means为代表的划分式算法需要类的个数作为先验参数，而且对非凸壳类簇的聚类效果不太理想[2-3]。基于网格的聚类方法首先对特征空间进行网格划分，将其量化为包含不同对象数目的单元格，并定义网格的密度函数，此后的聚类分析只针对单元格进行操作，与对象数量无关，从而能够获得较高的运算效率，很适用于大数据的聚类分析[4]。另外网格类聚类算法还具有不需要预知类个数，对样本输入顺序不敏感，对类的形状不敏感等优点。经典的网格聚类算法包括GDCA[5]、CLIQUE[6]、GGCA[7]、改进的分水岭聚类[8]等。然而，正如文献[7]指出，所有的网格聚类算法都要面对以下两方面的共性问题：1)网格颗粒度的选择问题，即可塑性面积单元问题(MAUP)[9]，当类簇密度差异过大时这一问题尤为突出，即前述第3点困难；2)类的检测与划分的问题，特别是在前述第3点、第4点困难的情况下，如何进行类的检测与划分。如此可见，基于网格的聚类算法用于武器系统非合作目标聚类分析主要需要解决前述第3点、第4点困难。因此，本文提出一种自适应的网格聚类方法，以应对上述挑战。

1 问题描述以及相关的研究

1.1 对MAUP的研究

MAUP最早由Openshawn在1977年提出[9]。在网格聚类算法中，网格密度通常被定义为单元格内包含的对象数量，这样，在不同颗粒度的网格划分下，空间中就会呈现出不同的类簇结构。以图2、图3为例：对同一组数据集，当采用如图2(a)所示的大颗粒度划分时，得到的密度地形图如图2(b)所示，在网格空间中能够正确区分左下角的类，但无法分辨右上角的4个类，出现了空间模糊；而当采用如图3(a)所示的小颗粒度划分时，右上角的4个类能被正确区分，而左下角的类则被过度分割。

图2 大颗粒度网格化效果Fig.2 Gridding effect under gross granularity

图3 小颗粒度网格化效果Fig.3 Gridding effect under fine granularity

一些网格聚类算法对这一问题专门进行了研究。文献[7-8]的方法基于这样一种假设：在最合适的颗粒度下，类簇在地形图上形成局部尖峰，这样在对网格密度进行直方图统计后，将呈现出多峰值的特征。通过遍历不同颗粒度的网格或滤波模板，能够让这种多峰值特征最大化(或密度值统计方差最大化)的即为最佳颗粒度。然而，上述的方法只能适用于不同类簇内的对象密度相差不大的情况，当这个密度差异非常大的时候，是无法获取一个适中的颗粒度兼顾所有类簇的。为此文献[10-12]采用了一种非均匀的网格划分方法：首先采用较粗的颗粒度进行均匀网格化，然后选取那些密度值大于门限t的网格，将其等分成两个网格，这样不断循环，特征空间就被分成大小不同、但密度值均小于t的网格。这种方法能够根据局部密度调整网格尺寸，但非均匀的划分也为后续处理带来了很多困难，另外门限值t的选择显然非常关键，这也涉及到下面要讨论的类的检测与划分问题。

1.2 类簇检测与划分问题的研究

大部分的网格聚类算法都会用到“有效网格”的概念，即那些密度较高，可能存在类簇的网格。通常采用门限比较的方法将高密度的网格与背景网格区分开来，超过门限的网格形成若干个互连区域，然后再将这些区域进一步合并或分割，形成类簇。显然，确定合适的门限是这类算法的关键。然而对于如图4(a)所示的一维网格密度地形图，不同的门限将形成不同的聚类效果，无法用统一的门限检测出所有的类。

图4 不同密度类的检测与划分Fig.4 Detection and partition of clusters with diverse densities

为此，文献[8]采用图像形态学的分水岭变换进行类簇的分割，这种算法起源于地形学的概念：灰度图像被看作地形图，包括山峰和山谷，一滴水从平面上任意一点落下，最终稳定于一个局部最低点。水在各个山谷内累积形成聚水盆，当两个聚水盆将要融合的时候，认为构建分水岭保持其隔离状态，这样直到水漫过最高的山峰，分水岭就形成了对图像的分割。网格化的空间可看作多维图像，网格密度对应灰度值。原始分水岭算法采用自底向上填平峡谷的方式，将其逆转，采用自顶向下削平山峰的方式，即可用于网格聚类。这种方法能够发现并利用局部区域密度的相对差异，找到相对集中的类簇，并在峡谷上形成分水岭，作为类的分割线。其聚类效果如图4(b)所示。

通过上述分析可知，分水岭聚类相较于固定门限方法有明显优势。但是，直接采用原始分水岭方法存在噪声敏感的缺点。受噪声的影响，不仅在背景中会检测出虚假的类，还会造成同属一个类簇区域的过度分割。文献[8]提出的改进分水岭聚类算法采样中值滤波方法，只选取密度大于全局极大值一半的峰值点作为有效类中心，但这种方法损失了对类簇密度差异的适应性，图4中低密度的类簇显然会被漏检。因此，本文提出一种自适应的基于分水岭变换的类簇检测与划分方法，以降低噪声的影响并抑制过度分割效应，进一步提高算法的适应性。

2 算法

2.1 空间分辨率自适应的网格化方法

理想的网格划分应该针对不同密度的类簇采用不同颗粒度的网格，然而悖论是，在未进行聚类分析之前，类簇的分布和密度又是未知的。因此，本文提出了另外一种思路，采用较小颗粒度的网格保证空间分辨力，利用类内对象具有内聚性的特点，用k-近邻方法定义新的密度函数，以适应不同分布密度，下面进行具体讨论。

1) 确定网格尺度。对于N维特征空间，在各个维度上分别进行均匀网格划分，某一维度上划分的颗粒度与该维度上期望得到的分辨率匹配，例如在距离维上需要能够分离两个间隔1 cm以上的类簇，那就可以将距离维的颗粒度定为0.5 cm或1 mm，从而获得足够精细的空间区分度。

2) 定义密度函数。设X={xξ∈RD,ξ=1,…,n}代表D维空间中的对象集，取单元格i的中心点ci，在X中找到K个与中心点最近邻的对象{xi,1,xi,2,…，xi,K}，d(ci,xi,j)代表两个对象之间的距离，则单元格i的密度为

(1)

从(1)式可以看出单元格i的密度与中心点ci的位置、K值以及周围对象分布的疏密程度相关，而与网格划分的颗粒度无关。

(1)式中K值决定密度函数在类簇内的波动率和类簇边缘的衰减率。直观上，K越大，平滑效果越明显，类簇内部密度的起伏越小，有利于抑制类簇内部的过度分割，但同时类簇边缘的密度衰减越缓慢，不利于类簇间的分割；反之亦然。因此需要对这两个指标进行权衡取舍确定最佳的K值。这里以均匀分布的对象集为标准，不失一般性，对象在各维度上的分布间隔均为l，网格在各维度上的尺寸为g，并令g≪l. 定义类簇内的波动率β为类簇区域内网格密度最高值DenInmax与类簇区域内网格密度最低值DenInmin之比。定义类簇边缘处的衰减率α为所有密度值小于0.1DenInmax的网格与类簇内任意对象间的最短距离。β、α与K的关系不容易用解析式表达，本文采用数值仿真的方法计算。以二维空间为例，取欧式距离，在不同K值下的β与α如表1所示。由表1可知，β并非随K值严格单调递减，在K=5时波动率β较小，同时也能兼顾到较好的衰减率α，故而将5设为最佳K值。

表1 指标水平表

采用上述方法对图2和图3中的对象进行网格化处理，网格边长为0.1，K值取5，得到如图5所示的密度地形图。由图5可知，5个密度差异很大的类簇都被凸显出来，并且由于网格颗粒度很小，距离较近的类簇都能被清晰的区分，这样就可以采用较小的网格得到理想的空间分辨率，同时又不会因为网格过小产生过度分割的现象，从而规避了MAUP问题。

图5 自适应网格化方法的效果Fig.5 Griding effect of adaptive gridding method

2.2 基于自适应分水岭变换的类簇检测与划分

原始的分水岭方法能够自动发现相对集中的类簇，对密度差异较大的类簇有很好的适应性，但其缺点在于易受噪声影响，产生过度分割，网格密度的局部不规则性也会加剧这一趋势。故而，成功应用分水岭聚类的关键在于对背景噪声和过度分割效应的抑制，下面详细介绍本文的方法。

2.2.1 自适应背景噪声抑制

背景噪声分布在整个特征空间内，首先估计噪声网格的密度值范围。数据集如图6(a)所示，按2.1节方法生成密度地形图6(b)。统计其密度直方图如图6(c)所示，其横坐标为密度值DH(i)，纵坐标为地形图上落入密度值区间内的像素点数PN(i)，其中i为对横坐标区间量化的序号。密度值区间的划分与噪声网格的密度分布范围、噪声与对象之间密度值的差异等因素相关，同样存在MAUP问题。若间隔较大，噪声与对象之间不容易区分；若间隔较小，落入每个区间的点数较少，出现过度分割。故而，这里采用一维的自适应网格化方法，即采用较小的密度间隔，同时用(1)式对PN(i)进行等价计算。

图6 自适应背景噪声抑制方法Fig.6 Adaptive background noise suppression method

显然，只有当类簇密度大于背景噪声密度的时候，类簇才能被检测出来，因此只考虑类簇密度值大于噪声的情况。故而，认为图6(c)的第1个尖峰属于噪声网格区域，其中峰值点对应的横坐标(网格密度值)为DenNP. 接下来确定噪声网格的密度函数值的分布范围，假设噪声分布区间关于峰值点对称，首先将图6(c)上左起第1个非0网格定为左边界DenNL，则其右边界DenNR为2DenNP-DenNL，认为DenNR就是噪声网格密度函数的最大值，以DenNR作为噪声抑制门限，大部分的噪声网格都将被过滤掉。图6(d)所示为图6(b)的检测结果，红色区域为超过门限的网格，由此可见效果比较理想。

该方法借鉴了恒虚警检测的思想，门限可以根据噪声水平自动调整。

2.2.2 分水岭聚类过度分割抑制

以图7(a)的数据集为例，实施上述噪声门限抑制处理，然后进行分水岭分割，结果如图7(b)所示，可见类簇内部还是存在过度分割，这是局部的地形起伏造成的。常见的方法是加入滤波预处理，以平滑局部尖峰。然而，滤波模板的尺度又直接关系到空间分辨力，使前面阐述的MAUP问题更加复杂化，故而本文不考虑此类方法。在聚类的原始定义中，类是一组内部相似性较高的对象，因此在网格空间中，类簇内部应该具有相近的密度值，类簇之间应存在过渡区域，其密度明显小于与其相邻的类簇，形成峡谷，正确的分水岭应该出现在这些峡谷上。基于这种思想，本文设计一组规则，消除那些多余的分水岭，保留有价值的分水岭。

图7 分水岭聚类的过度分割Fig.7 Over-segmentation of watershed clustering

峡谷所在的低密度区域是一个相对的概念，需要根据其周围类簇的密度自动调整，为了实现这一目的，需要首先确定类簇内部网格密度的波动水平。对象在局部分布的不规则性会导致类簇内部网格密度的波动。对象的分布规律千差万别，根据中心极限定理，假设同一类簇内网格密度值统计规律服从高斯分布。设高斯分布均值为μ，方差为σ2，认为峰值点±2σ内是同属一个类簇的网格密度分布范围，则密度值下限与密度值峰值的比例为

(2)

设DenCpeak为类簇的峰值密度，以该数值乘以RDenC以及2.1节介绍波动率β作为判断类簇边界的门限：

TC=βRDenCDenCpeak=0.143 6DenCpeak.

(3)

在峰值周围密度低于TC的网格被认为属于低密度区域，属类簇范围之外。基于上述准则，设计如下的流程对分水岭变换产生的过度分割区域进行合并：

步骤1在未经过合并处理的分割区域中选择最高峰值所在的区域作为目标区域，将最高峰值设为DenCpeak，并按(3)式计算TC；

步骤2寻找一个与目标区域通过分水岭相连的区域作为备选区域，若二者间公共分水岭上的网格密度高于TC，则消除公共分水岭，将备选区域合并到目标区域内；

步骤3重复步骤2，这样逐步向周围扩大目标区域，直到没有备选区域，或者剩余的分水岭都无法消除；

步骤4返回步骤1寻找下一个目标区域，这样遍历整个特征空间，得到若干目标区域对应不同的类簇所占据的范围。

对图7(b)采用上述方法，效果如图8(a)所示，两个类中的过度分割得到了很好的抑制，得到的聚类结果如图8(b)所示。

图8 过度分割抑制效果Fig.8 Suppression effect of over-segmentation

3 仿真及分析

本文将算法用于武器探测系统仿真数据集以及人造数据集，以进一步验证其在战场仿真场景中及各种极端条件下的聚类效果。由1.2节的分析可知，分水岭聚类相较于其他网格聚类方法在类簇密度差异适应性上有较大优势，因此本文的对比对象为文献[8]的改进分水岭聚类算法。

仿真本文算法的关键参数设置如下：(1)式中的K=5，类簇边界门限采用(3)式中的参数。

3.1 电子侦察数据集

在电子侦察系统中，到达角是主要的辐射源分选依据。建立仿真系统，采用和差比幅测角体制，接收机带内噪声为-20 dB，4个辐射源信号的信噪比分别为10 dB、-15 dB、-10 dB和-10 dB. 在经过一段时间的观测积累后，信号样本到达角在方位角、俯仰角二维空间上的分布如图9所示。

图9 电子侦察数据集Fig.9 ELINT dataset

由于来自不同辐射源的信号能量不同，噪声对其的影响也不尽相同，各辐射源样本的分布呈现不同规律。

文献[8]的改进分水岭聚类算法采用最大化直方图标准差的方法确定最佳颗粒度，但由于其采用统一的网格尺寸，并将网格内对象数量作为密度值，不可避免会在网格化过程中产生MAUP问题。这里人工选定一个适中的网格尺寸，得到的地形图如图10(a)，分水岭划分结果如图10(c)所示，图10中不同颜色的区域对应不同的类簇。可见其中出现了明显的过度分割，并且由于采用了中值滤波处理，密度最低的类簇被漏检了。

采用本文方法的地形图如图10(b)，分水岭划分结果如图10(d)所示，4个类簇的范围被正确划分。需要说明的是由于采用了本文的自适应网格化方法，图10(d)中类簇的范围被扩大，但不影响最终的聚类结果，距离较近的类也被正确分离，如图11所示，可见整体聚类结果比较理想。

3.2 雷达探测数据集

雷达探测数据的特征空间包括方位角、俯仰角、距离、速度4个维度，属于高维数据集。某仿真作战场景中，目标呈编队密集分布，在雷达天线主波束内存在多个目标，并且由于速度、距离接近，一般方法不易分辨。采用聚类分析，记录距离波门内所有时刻样本的上述四维信息，经过100个脉冲的数据积累，形成的数据集如图12(a)所示(这里为了可视化仅绘出三维图形)，其中还存在均匀分布的噪声对象，接收机带内的信噪比为10 dB. 采用本文方法的聚类结果如图12(b)所示，可见整体的聚类结果比较理想。

图12 四维雷达目标数据集聚类效果Fig.12 Clustering effect of the algorithm for 4-D radar target simulation dataset

3.3 Jain数据集

为了更加全面的考验算法性能，采用Jain数据集，这一数据集是由Jain在文献[3]中提出的，其中包含不同形状、密度及大小的类，并散布着均匀分布的噪声。图13左侧的两个类密度差异很大，无法为它们找到相同的距离门限或密度门限作为相似度标准；右上角两个蛇形缠绕的类没有明确的类中心；右下角的类在拓扑结构上完全包围。Jain认为还没有一种聚类算法能够成功识别出图13中所有的类。

图13 Jain数据集Fig.13 Jain dataset

图14 Jain数据集两种分水岭聚类效果比较Fig.14 Compareison of two watershed clustering effects for Jain dataset

虽然Jain对象集是一个人工设计的特例，但是随着战场对抗的不断升级，需要处理的目标模式越来越多、差异也越来越大，难免出现类似Jain对象集里的某种模式。对图13的Jain数据集，首先采用文献[8]的改进分水岭聚类，同样人工选定其最佳颗粒度。得到图14(a)的地形图和14(c)的分水岭划分结果，其效果差强人意。采用本文方法得到的地形图、分水岭划分效果如图14(b)及14(d)所示。最终聚类结果如图15所示。需要说明处理结果存在的两个缺陷：1)由于左上角类簇的密度较低，接近背景噪声的密度，导致部分本来属于类簇内的对象被漏检，该类簇的范围在边缘处出现了断续的现象；2)右下角被3个环形类簇包围的噪声对象因为与外部噪声对象隔离，被识别为3个新类。但整体来看，划分效果比较清晰，各主要类簇均被成功检测出。

图15 自适应网格聚类结果Fig.15 Adaptive grid-based clustering result

4 结论

本文提出了一种应用于武器探测系统对非合作目标处理的自适应网格聚类算法，其核心包括：1)空间分辨率自适应的网格化方法，解决了网格划分的MAUP问题；2)自适应分水岭聚类方法，利用自适应噪声门限以及过度分割抑制处理实现了在噪声环境下不同密度类簇结构的检测与划分。仿真实验表明，该算法达到了预期效果，能够处理空间中分布形式差异极大的类簇，具有一定的噪声抑制能力，并且对类簇分布形式不敏感。其主要缺点在于背景噪声抑制算法的效果在类簇与噪声密度接近的情况下不够理想，导致对类边缘的划分不够精确，有待于进一步研究改进。

References)

[1] 孙吉贵, 刘杰, 赵连宇. 聚类算法研究[J]. 软件学报, 2008, 19(1):48-61.

SUN Ji-gui, LIU Jie, ZHAO Lian-yu. Clustering algorithms research[J]. Journal of Software, 2008, 19(1):48-61. (in Chinese)

[2] Mok P Y, Huang H Q, Kwok Y L, et al. A robust adaptive clustering analysis method for automatic identification of clusters[J]. Pattern Recognition, 2012, 45(8):3017-3033.

[3] Jain A K. Data clustering: 50 years beyond K-means[J]. Pattern Recognition Letters, 2010, 31(8): 651-666.

[4] 伍育红. 聚类算法综述[J]. 计算机科学,2015,42(增刊1):491-499,524.

WU Yu-hong. General overview on clustering algorithms[J]. Computer Science, 2015, 42(S1):491-499,524. (in Chinese)

[5] 陈宁, 陈安, 周龙骧. 基于密度的增量式网格聚类算法[J]. 软件学报, 2002, 13(1):1-7.

CHEN Ning, CHEN An, ZHOU Long-xiang. An incremental grid density-based clustering algorithm[J]. Journal of Software, 2002, 13(1):1-7. (in Chinese)

[6] Agrawal R, Gehrke J, Gunopulos D. Automatic subspace clustering of high dimensional data[J]. Data Mining and Knowledge Discovery, 2005, 11(1): 5-33.

[7] Yue S, Wei M, Wang J S, et al. A general grid-clustering approach[J]. Pattern Recognition Letters, 2008, 29(9):1372-1384.

[8] Lolla S V G, Hoberock L L.Improved unsupervised clustering over watershed-based clustering[C]∥Proceedings of the 9th International Conference on Machine Learning and Applications.Washington DC, US: IEEE, 2010:253-259.

[9] Openshaw S. A geographical solution to scale and aggregation problems in region-building, partition and spatial modeling[J]. Transactions of the Institute of British Geographers, 1977, 2(4):1782-1795.

[10] Dou W, Hu J. A half-split grid clustering algorithm by simulating cell division[C]∥Proceedings of International Joint Conference on Neural Networks. Beijing, China: IEEE, 2014:2183-2189.

[11] Micheal S, Maria P.Fast grid-based clustering method for automatic calculation of optimal parameters of skin color classifier for head tracking[C]∥Proceedings of the 2nd International Conference on Cybernetics. Gdynia, Poland: IEEE, 2015: 119-124.

[12] Schikuta E, Fritz F. An execution framework for grid-clustering methods[J]. Procedia Computer Science, 2016: 80:2322-2326.

AnAdaptiveGrid-basedClusteringAlgorithmforNoncooperativeTargets

LI Da-peng1,2， LIANG Wei2

(1.School of Mechatronical Engineering, Beijing Institute of Technology, Beijing 100081, China; 2.Beijing Institute of Remote Sensing & Equipment, Beijing 100854, China)

The detection equipment of weapon systems is usually used to detect the noncooperative targets, causing the distribution patterns of observed samples to be unpredictable in feature spaces. The irregular cluster shapes, diversified cluster densities and noise bring great challenges to clustering algorithms. A novel adaptive grid-based clustering algorithm, which consists of ak-nearest neighbor method-based gridding method with spatial resolution adaptability, and an adaptive watershed transform-based method for cluster detection and segmentation in the gridded space are presented. The proposed algorithm could process the clusters with noises and significantly diverse densities, meanwhile keeps the advantages of gird-based clustering, including robustness for cluster shape and no need for cluster number as priori parameter. The effectiveness of the algorithm is tested with simulation and artificial datasets.

artificial intelligence; grid-based clustering; modifiable areal unit problem; watershed transform

TP301.6

A

1000-1093(2017)11-2166-10

10.3969/j.issn.1000-1093.2017.11.012

2017-02-16

国防“973”计划项目(613196)

栗大鹏(1982—), 男, 博士研究生。E-mail: li_dapeng@foxmail.com

梁伟(1976—), 男, 研究员。E-mail: lwlevil@163.com