基于并查集的低复杂度模糊聚类信号分选算法

张悦 司伟建

（1.哈尔滨工程大学信息与通信工程学院，哈尔滨 150001；2.哈尔滨工程大学先进船舶通信与信息技术工业和信息化部重点实验室，哈尔滨 150001）

引 言

雷达信号分选是雷达对抗系统的关键处理过程，也是雷达对抗信息处理的核心内容，分选水平是衡量雷达对抗系统和信息处理技术先进程度的重要标志[1].信号分选方法可分为三类：基于脉间参数特征的分选方法、基于脉内细微特征的分选方法、基于波形匹配的分选方法.其中基于脉间参数特征的分选方法又可分为基于雷达脉冲重复间隔(pulse repetition interval，PRI)的分选方法与基于多参数联合的分选方法[2].由于现代电子对抗环境复杂，信号密度越来越大，信号时域交叠严重[3]，这使得传统的基于PRI的信号分选方法已无法适应现代电子对抗环境.同时有学者针对如何提高脉冲丢失，降低信号被正确分选的概率进行研究[4–6].因此发展出了多参数联合的信号分选方法，其中聚类分选方法是一种基于脉冲信号之间相似性的无监督学习方法，由于其无需先验信息，适用于未知信号环境中进行信号分选，成为学者们的研究热点.

众多学者都对聚类分选算法进行了研究.Gao Li-peng等人提出了基于K-Means动态聚类与子线性时间算法相结合的分选算法，通过K-Means对数据动态聚类后，定时对每类数据使用子线性时间算法进行分析得到PRI信息，由PRI信息对各类数据进行进一步分类，完成信号分选.该方法计算量小，具有很好的实时性[7].Cao Sheng等人提出了基于密度的模糊C均值(fuzzy C-means, FCM)多中心重聚类雷达信号分选(density-based FCM multi-center re-clustering,DFCMRC)算法，该算法结合了具有噪声的基于密度的聚类方法(density-based spatial clustering of applications with noise, DBSCAN)和FCM的优点，使用基于密度峰值的快速聚类(clustering by fast search and find of density peaks, CFSFDP)算法产生初始化聚类中心，而不是随机初始化聚类中心.该算法分选结果优于K-Means、FCM等算法[8].Mohaned Giess Shokrallah Ahmed等人提出了一种基于点对称的雷达分选(point symmetry based radar sorting, PSBRS)算法，使用对称测量距离(symmetry measure distance)代替欧氏距离，使得该算法能够处理各种类型的雷达信号，使用交替模糊C均值(alternative FCM, AFCM)初始化距离测量的参考点，降低了噪声和错误分选的影响；同时引入密度滤波，滤除噪声和杂波.该算法对噪声和脉冲丢失不敏感，但需要事先确定信号环境中辐射源数量[9].张怡霄等人提出了一种基于数据场联合PRI变换与聚类的雷达信号分选方法，其结合数据场理论、PRI变换与聚类的优势，综合实现信号分选.该算法不需要人工设置初始条件，可以自动确定聚类数目，同时对噪声、脉冲丢失不敏感，但该算法中使用了PRI变换法，计算量大[10].冯鑫等人提出了基于数据场的多模雷达信号分选算法，基于数据场理论计算数据场势值，选取距最大值最近的样本数据作为初始聚类中心，之后使用传统的K-Means聚类完成分选.该算法能够自动获取合适的初始聚类中心，确定聚类数目，对参数交叠的捷变频信号仍有较好的分选效果，但需要根据经验设置合适的影响因子[11].吴连慧等人提出了基于改进排序点以识别聚类结构(ordering points to identify the clustering structure,OPTICS)的雷达信号预分选方法，利用OPTICS算法的核心距离和可达距离实现不同密度的信号分选，并采用两级处理：第一级处理高密度信号，完成信号稀释；第二级累积并处理低密度信号.与传统的DBSCAN算法相比，该算法可以分选具有不同密度分布的雷达信号[12].袁泽恒等人对支持向量聚类(support vector clustering, SVC)用于信号分选进行了深入研究，提出了改进加权SVC的雷达信号分选新方法，针对参数交叠时分选正确率不高的问题，在SVC和分层互耦分选算法基础上，利用变精度粗糙集对标准化的雷达信号数据进行加权处理，分析分选结果构建了有效性评价模型，获得了最佳的分选参数.该算法在参数严重交叠时，分选正确率显著提高[13].但这些聚类分选算法大都因为逻辑复杂很难实际应用于工程中，或运算量大很难满足工程中对分选实时性的需求.

刘旭波等人提出的改进模糊聚类分选算法[14]，由于算法原理简单，且能够有效完成分选，已广泛应用于工程项目.但在密集信号环境中，消耗硬件资源大，且分选实时性无法保证，即算法复杂度高.本文针对该算法复杂度高的问题进行研究，结合并查集提出基于并查集的低复杂度模糊聚类信号分选算法.首先对复杂信号环境下雷达对抗设备对信号分选实时性的需求进行分析.之后分析原模糊聚类分选算法复杂度高的原因；结合并查集，提出基于并查集的低复杂度模糊聚类信号分选算法，给出该算法的流程；分析改进算法的复杂度，通过仿真实验，对比改进算法与原算法的复杂度.最后将该算法在TMS320C6678开发板上实现，验证了该算法可基本满足实时性的需求.该改进算法基本满足复杂信号环境下雷达对抗设备对分选实时性的需求，具有较大的应用价值.

1 信号环境对分选的实时性需求

以被动雷达寻的器为例，其所面临的信号环境典型参数如下：

1)信号密度为1～2百万脉冲/秒；

2)脉宽(pulse width, PW)范围为0.2～50 μs ；

3)载频(carrier frequency, CF)范围为2～18 GHz；

4)重频范围为500 Hz～100 kHz.

这里取信号密度为1百万脉冲/秒.考虑到被动雷达寻的器天线可对信号进行空域滤波，假设主波束为锥状波束，覆盖± 30°，则主波束对应的立体角为

得到进入被动雷达寻的器的信号密度为

式中， η0为环境中信号密度.

由重频范围可得环境中最大脉冲重复间隔IPR=2ms，为能够积累到一定数目低重频信号，信号序列截取时长T=500ms.同时由于被动雷达寻的器接收机的频域选通作用，目前接收机瞬时带宽可达1 GHz，因此单次分选所需处理的脉冲数为

2 模糊聚类分选算法

2.1 算法原理

模糊聚类算法的输入数据模型：假设有一个数据集合X={x1,x2,···,xn}， 每个数据点有m维参数，即xi={xi1,xi2,···,xim}(i=1,2,···,n).当输入数据为雷达信号脉冲时，n为脉冲个数，X={x1,x2,···,xn}为脉冲串，m为各脉冲的特征参数数量，xi={xi1,xi2,···,xim}中的各特征参数分别对应脉冲描述中的CF、PW、到达方向(direction of arrival, DOA).

模糊聚类算法通过计算两脉冲间相似度(或距离)，将任意两脉冲间的相似度存入相似矩阵R，之后用阈值λ 对相似矩阵进行截取，即将相似度与阈值比较，若相似度高于阈值，则认为两脉冲为同一类.对截取后的相似矩阵进行提取便可得到聚类信息，进而完成分选.阈值的选取对分选效果至关重要，本文所使用的阈值确定方法为贺宏洲等人提出的使用F-统计量确定阈值的方法[15].

模糊聚类分选算法流程主要分为下面4步[14].

1)数据标准化与归一化

①标准差变换

经过标准差变换后，各维参数均值为0，标准差为1，消除了信号各维参数变化范围与量纲不同对信号分选的影响.

②极差变换

式中， max()和 min(分 别为的最大值与最小值.经过极差变换后，信号各维参数位于[ 0,1].

2)建立模糊相似矩阵R

相似矩阵R是n阶方阵，其中各元素是信号序列X={x1,x2,···,xn} 中 两两脉冲之间相似系数rij，rij可通过距离公式得到，这里采用海明距离，也可采用欧式距离等其他距离计算方式.

式中，wk是xi={xi1,xi2,···,xim}的第k个特征的权重系数，且满足.

3)截取相似矩阵R

模糊聚类算法通过设置门限λ 对相似矩阵R进行截取，再根据截取后的相似矩阵R′中各元素的值判断行列坐标对应的两脉冲是否属于同一类.根据式(7)，相似系数rij越接近1，说明数据点xi和xj相似度越高.因此当相似系数rij≥λ时 ，令rij=1，此时可认为数据点xi与xj属于同一类.实际工程中，门限值λ 需根据实际信号环境进行选取.

4)使用追踪法完成聚类信息提取

追踪法具体步骤如下：

①由于截取后矩阵R′具有对称性，因此下三角部分包含了脉冲间的聚类信息，记录该部分中值为1的元素下标，存入数组A[i][2]中.

②令f=1， 将f存入数组B[t]中 ，按行搜索A[i][2].若A[i][2]中 有元素与f相等，且同一行另一个元素在B[t]中 不存在，则将这个元素存入B[t]中.

③令f遍历B[t]，重复步骤②直到没有新元素加入B[t]中.

④将B[t]中 的元素按行存入数组C中，C维数不定.

⑤令f遍历1 →n， 取其中任一个C中不存在的元素，重复步骤②～④，直到所有信号分选完成.

2.2 模糊聚类分选算法存在的问题

实际应用中发现使用模糊聚类分选算法进行分选，在信号数量较大时，占用大量内存，且运行时间较长.内存占用高是由于算法运行时需生成n2大小的浮点型相似矩阵.为定位算法运行时间比重最高的模块，对模糊聚类分选算法中各模块的运行时间进行了实验测试.测试环境：i7-7700K+16GB RAM，Win10+VS2019.

对不同时间长度的信号序列进行分选，统计算法各模块运行时间比重，结果见表1.

表1 模糊聚类分选算法各模块运行时间比重Tab.1 The proportion of running time of each module in fuzzy clustering sorting algorithm

通过分析与测试可以得出，模糊聚类分选算法存在以下问题：

1)生成n2大 小的浮点型相似矩阵，n为信号数量，占用内存空间大；

2)信号数量n较大(信号序列较长)时，追踪法提取聚类信息运行时间巨大且比重最高，高达99%.

加速大概率事件远比优化小概率事件更能提高性能.下一节将介绍并查集这种高效、精妙的数据结构，并将其应用于模糊聚类分选算法中，代替追踪法提取聚类信息，使得模糊聚类分选算法复杂度大大降低.

3 基于并查集的改进模糊聚类分选算法

3.1 并查集

一些应用场景涉及将n个不同的元素划分为一组不相交的集合.如：确定无向图的连通分量、求最小生成树的Kruskal算法以及求最近公共祖先等.这些应用场景都需要对不相交集合进行两种特别的操作：寻找包含给定元素的唯一集合和合并两个集合[16].并查集(union-find set)就是一种用于实现这些操作的高效、精妙的数据结构.

并查集维护了一组不相交的动态集合S={S1,S2,···,Sk}.每个集合可包含一个或多个元素，并使用其中的某一个元素代表该集合.对于每个元素，可以快速找到该元素所在集合的代表，以及快速合并两个元素所在的集合.

并查集中有三个对数据的基本操作：

1)makeset(n)，创建一个并查集，其中包含n个单元素集合；

2)unionset(e1,e2)，对于给定元素e1与e2，若两者不属于同一集合，则将其所在的集合合并；

3)find(e)，对于给定元素e，找到其所属集合，并返回其所在集合的代表元素.

其中unionset(e1,e2)使用find(e)获得e1与e2所在集合的代表元素，通过比较代表元素是否相同判断e1与e2是否属于同一集合.

并查集使用树表示集合，树上的各节点表示集合中的各元素，树根对应的元素即该集合的代表元素，如图1所示.

图1 并查集的表示Fig.1 The representation of union-find set

图1中有两棵树，对应于两个集合，分别是{a,b,c,d} ，代表元素为a； {e,f,g} ，代表元素为e.树中各节点表示集合中的各元素，箭头表示指向父节点的指针(与C/C++语言中的指针概念不同，这里的指针指父节点在数组中的位置序号)，根节点指针指向自身，表示其没有父节点.查找时沿着各节点的父节点不断向上查找，直到找到根节点，即该集合的代表元素.

由此可以使用一个长度为n的整型数组存储各元素，创建并查集时makeset(n)构造出如图2所示的森林，每个元素都是一个集合，其代表元素为自身，各树只有根节点.

图2 并查集构造Fig.2 The construction of union-find set

当进行find(e)操作时，若每次都沿着元素e的父节点向上进行查找，则查找的时间复杂度为树高.为降低时间复杂度，可以使用一种简单高效的策略——路径压缩，即在每次查找过程中，将查找路径上的各节点直接指向根节点，如图3所示.

图3 路径压缩Fig.3 Path compression

最后是归并操作unionset(e1,e2)，合并两个集合时，只需将一棵树的根节点指针指向另一棵树的根节点即可，如图4所示.

图4 集合归并Fig.4 Collections are combined

为降低对合并后集合进行查找时的复杂度，采用启发式策略——按秩归并，即将较矮的树的根节点的指针指向较高的树的根节点，秩即树高.也可以使用树的规模作为秩，即将节点少的树的根节点指针指向节点较多的树的根节点.

关于并查集时间复杂度，有如下引理[16].

令T(M,N)为 交错执行M(≥N)次带路径压缩的查找和N−1次按秩归并的最坏情况时间.则存在正常数k1和k2，使得

式中， α(M,N)与Ackerman函数有关，Ackerman函数表达式为

经数学家证明：

式中， l b∗N为Ackerman反函数，其值为对N求对数直到结果小于等于1的次数.

经过上述分析可知，使用并查集可以在常数时间内完成对集合的查询或合并操作，即对集合进行单次查询或合并操作的时间复杂度为O(1).使用并查集只需长度为n的数组便可表示所有脉冲，n为脉冲数量，则空间复杂度为O(n).

3.2 改进方案

将雷达信号聚类分选问题看作求无向图的连通分量问题.首先将所有数据点看作一幅图中的孤立点，如图5(a)所示，其对应的并查集示意图如图5(b)所示.

若脉冲1与脉冲4为一类，则将图5(a)中对应节点连通，此时对集合1与集合4进行归并，结果如图6所示.

图5 数据集初始化Fig.5 The initialization of data set

图6 脉冲1与脉冲4属于一类时的归并结果Fig.6 The combined result when pulse 1 and pulse 4 belong to one category

假设图5(a)中脉冲1、4、7为一类，脉冲2、3、5、6为一类，重复上述操作，直到对任意两脉冲的归并均已完成即完成分选，分选结果如图7所示.

图7 分选结果Fig.7 The sorting results of pulses

图7为分选结果，可通过如下方式从并查集中查询分选结果并输出：

1)遍历并查集，找到代表元素(指针指向自身)，并对其分配类别号；

2)遍历并查集，各元素的类别号与其所在集合代表元素相同.

经过此步骤得到分类结果，类别1：脉冲1、4、7；类别2：脉冲2、3、5、6.

基于上述思想，使用并查集对模糊聚类分选算法做出如下改进：

1)使用并查集代替追踪法聚类，降低时间复杂度；

2)不生成相似矩阵，直接计算两脉冲间相似度，相似度高于阈值后，对信号集合完成归并操作，降低空间复杂度.

综上，基于并查集的改进模糊聚类分选算法流程如下：

1)数据标准化与归一化；

2)计算两脉冲间相似度；

3)若相似度高于阈值，对信号进行归并；

4)若存在两脉冲没有进行相似度计算，转入步骤2；

5)遍历并查集，找到代表元素(指针指向自身)，并对其分配类别号；

6)遍历并查集，各元素的类别号与其所在集合代表元素相同.

基于并查集改进的模糊聚类分选算法流程图如图8所示.

图8 基于并查集的改进模糊聚类分选算法流程图Fig.8 The flowchart of improved fuzzy clustering sorting algorithm based on union-find set

3.3 算法复杂度对比

由原模糊聚类分选算法(下文称原算法)可知，算法运行时生成大小为n2的浮点型相似矩阵，其空间复杂度为O(n2).其中使用追踪法提取聚类信息算法逻辑过于复杂，无法直接分析其时间复杂度.

基于并查集的改进模糊聚类分选算法(下文称改进算法)运行时，仅需长度为n的整型数组，其空间复杂度为O(n).下面对其时间复杂度进行分析：

1)构造并查集.构造并查集时仅需对数组进行一遍遍历，使其各元素指针指向自身即可，时间复杂度为O(n).

2)并查集聚类.需计算任意两脉冲间相似度，并对相似度高于阈值的两脉冲进行归并，最多需n2/2次归并，时间复杂度为O(n2).

3)聚类结果输出.需遍历两次数组，即需对数组中的各元素进行两次查询，时间复杂度为O(n).

综上，改进算法时间复杂度为O(n2).

下面通过实验验证改进算法相较于原算法复杂度大大降低.测试环境：i7-7700K+16GBRAM，Win10+VS2019.

实验1 算法复杂度对比实验

对常规、参差、抖动、脉间捷变频、脉组捷变频共5种形式，10部雷达，共5 800个脉冲，分别使用原算法与改进算法进行分选.运行时间与内存占用情况见表2.由表2可知，改进算法相较原算法复杂度大大降低.

表2 算法复杂度对比Tab.2 The comparison of algorithm complexity

由于原算法时间复杂度无法直接分析得到，仅一组实验数据无法证明改进算法时间复杂度低于原算法，为此进行了覆盖性实验.

实验2 覆盖性实验

对不同时长的序列(即脉冲数不同)使用两种算法进行分选，分选运行时间见表3.

表3 分选运行时间对比Tab.3 The comparison of sorting time

由表2、表3可知，不同脉冲数量下改进算法时间复杂度均远低于原算法，且改进算法相较原算法空间复杂度大大降低.

3.4 算法分选性能对比

由模糊聚类分选算法原理可知，该算法通过分析截取后的相似矩阵获得脉冲间的聚类信息.截取后的相似矩阵中，属于同一类的两脉冲对应位置处值为1，否则为0.原算法使用的追踪法就是通过不断的遍历该矩阵将属于同一类的脉冲归为一类实现的；而改进算法中使用了并查集，在计算相似度并与阈值比较后，判断两脉冲属于同一类，并将两脉冲所属的集合归并.因为改进算法不需要反复遍历矩阵，所以不需要保存整个矩阵，从而降低了空间复杂度；同时，使用并查集归并两脉冲所属集合可在常数时间内完成，因此降低了时间复杂度.

由上可知，改进算法与原算法本质上是相同的，改进算法仅在提取聚类信息阶段进行了改进，并不会对分选性能造成影响.为验证上述分析，进行实验对比.

实验3 算法改进前后分选结果对比

分别使用原算法与改进算法对同一组数据进行分选，雷达参数见表4，分选结果分别见表5与表6.

表4 雷达信号参数Tab.4 The parameters of radar signal

表5 实验3原算法分选结果Tab.5 The result of the original algorithm for experiment 3

表6 实验3改进算法分选结果Tab.6 The result of the improved algorithm for experiment 3

由表5和6可知，算法改进前后分选结果相同，性能并未因算法改进而下降.

3.5 复杂信号环境分选

为模拟算法在复杂信号环境中的分选性能，加入干扰脉冲，使用改进算法进行分选.

实验4 复杂信号环境分选

在表4所示雷达参数基础上，分别加入表7所示的两个跳频干扰信号，分选结果分别见表8与表9.

表7 两个跳频干扰信号Tab.7 The parameters of 2 frequency-hopping jam signal

表8 实验4原算法分选结果Tab.8 The result of the original algorithm for experiment 4

表9 实验4改进算法分选结果Tab.9 The result of the improved algorithm for experiment 4

由表8与表9可知：在雷达信号参数与干扰信号参数无重叠的情况下能够完成分选，此时干扰信号被作为辐射源分选出来；而在干扰信号参数与雷达信号参数重叠的情况下，算法将两种信号聚为一类(表9中类别9为脉组捷变信号2与跳频干扰信号归并得到)，因此算法的抗参数重叠能力有待提高.

4 算法并行化与DSP实现

4.1 OpenMP并行运行

OpenMP是用于共享内存并行系统的多处理器程序设计的一套指导性编译处理方案.OpenMP API支持C、C++、Fortran语言的多平台共享内存并行编程.

由于循环是程序中运行时间比重最高的部分，也是使用最多的程序执行结构，OpenMP主要对程序中的for循环进行并行化，也可对其他语句进行并行化.改进算法主要由循环构成，基于加速大概率事件的原则，本节使用OpenMP加速算法中的for循环.

OpenMP对可以并行化的循环有如下要求：

1)循环变量是有符号整形数据；

2)循环条件的关系运算必须是<、<=、>、>=中的一种；

3)循环变量的增量为常数；

4)如果关系运算是<、<=，那每次循环变量应该增加，反之应该减小；

5)循环中不能使用break、goto等跳转语句.

改进算法中的循环都满足上述条件，可使用OpenMP使其并行化，在for循环前加入“#pragma omp parallel for”预编译指令即可.而原算法中追踪法部分涉及while循环，且存在大量的break，因此无法使用OpenMP使其并行化.

下面通过实验对比OpenMP开启与否对算法的加速效果.

实验5 OpenMP加速测试

测试环境：i7-7700K+16GBRAM，Win10+VS2019.

对常规、参差、抖动、脉间捷变频、脉组捷变频共5种形式，10部雷达，分别测试OpenMP禁用与启用时改进算法在不同信号数量下的运行时间.测试结果见表10.

表10 OpenMP并行运行时间测试Tab.10 Parallel running time test based on OpenMP

由表10可知，改进算法可使用OpenMP技术并行运行，数据量较大时，使用8个核心并行运行可加速5～6倍.

4.2 算法的DSP实现

在TI公司的TMDSEVM6678LE开发板上实现改进算法，采用优化方式后，对表4所列信号进行分选.

实验6 运行时间测试

使用TMDSEVM6678LE开发板，单核心，核心频率1 GHz，对表4中所列雷达信号进行分选.截取信号时长：100 ms，共5 840个脉冲，800个噪点.分选运行时间1.1 s，分选结果见表11.分选结果中，部分雷达信号分选正确率未达到100%是由于在信号簇附近存在噪点.由表11可知，改进算法在数字信号处理(digital signal processing, DSP)开发板上成功运行，且能在较短时间内完成分选，证明了算法的硬件可实现性.

表11 改进算法分选准确率Tab.11 The accuracy signal sorting of the improved algorithm

由第1节单次分选需完成对1 966个信号的分选及3.3节时间复杂度为O(n2)，可估算单次分选耗时1.1×(1966/5840)2=0.125s，因此改进算法已达到工程应用的实时性要求.

由4.1节中OpenMP并行测试，8核并行运算可加速5～6倍，若在DSP上使用OpenMP技术可使运行时间缩短至原有运行时间的1/6～1/5.尽管TMS320C6678支持OpenMP，但在TMDSEVM6678LE开发板上无法实现裸机OpenMP，因此无法对OpenMP并行进行测试.被动雷达寻的器一般要求500 ms内完成首次分选，若能够实现在DSP上的OpenMP并行运行，则一次可对更多数据点进行分析，即可增大数据积累时长，这将是下一步研究的重点.

5 结 论

模糊聚类算法可有效在复杂信号环境下进行分选，但在信号密度较大的情况下，单次需分选的信号数量大，模糊聚类算法消耗硬件资源大，分选耗时长.本文结合并查集与模糊聚类算法，提出了基于并查集的低复杂度模糊聚类信号分选算法，经过实验与硬件实现，该算法已初步达到工程应用的实时性要求.但目前仍无法在DSP上实现OpenMP并行化，这将是下一步研究的重点；同时如何合理快速地设置阈值与权重、提高算法的抗参数交叠能力等问题也仍需深入研究.