海量电磁数据中雷达信号的高效分选方法*
2016-11-16张强王红卫陈游徐源
张强，王红卫，陈游，徐源
（空军工程大学航空航天工程学院，西安710038）
海量电磁数据中雷达信号的高效分选方法*
张强，王红卫，陈游，徐源
（空军工程大学航空航天工程学院，西安710038）
针对海量电磁数据中雷达信号难以进行快速准确分选的问题，提出一种新的聚类分选方法，即改进k-means算法的MapReduce并行化实现方法。通过引入初始聚类中心个数k1、最大聚类中心个数kmax和距离门限rt3个参数，克服了k-means算法需要事先确定k值和易受孤立点影响的局限；基于Hadoop平台实现了对改进k-means算法的MapReduce并行化，克服了k-means算法串行实现时间复杂度高的局限。最后，实验表明改进k-means算法取得了更高的分选准确率，MapReduce并行化后具有良好的加速比和扩展性，能够很好地对海量电磁数据中雷达信号进行高效分选。
海量电磁数据，雷达信号，分选，k-means算法，MapReduce
0 引言
在现代电子战复杂的电磁环境下，存在大量的雷达电磁信号，构成了复杂多变的电子对抗环境［1］。战时，通过电子情报侦察（ELINT）记录下了海量的电磁数据，迫切需要快速准确地分选出各雷达信号。雷达信号分选作为雷达信号识别的基础，直接决定了识别的高效性和准确性，进而影响电子侦察设备性能的发挥，并关系到后续的作战决策。
聚类算法是雷达信号分选的重要方法［2］。但面对海量电磁数据时，传统的聚类算法存在着单位时间内处理量小、处理时间较长、处理能力存在不足的缺陷［3-5］。k-means是经典的划分聚类算法，处理海量数据时存在一定的局限性，但相对其他聚类算法而言，具有高效率和可伸缩的优势，故在研究针对海量数据的高效聚类算法时，通常会首选k-means算法加以改进和优化［6］。k-means算法存在以下局限性：①必须事先人为确定聚类数目k，选择k值是否恰当，直接关系到聚类质量高低；②对孤立点非常敏感，聚类质量易受影响；③串行计算时间复杂度较高，难以满足快速聚类的要求。
为了能够对海量电磁数据进行高效分选，针对k-means算法存在的局限，本文提出了改进k-means算法的MapReduce并行化实现方法。
具体思路是：通过引入初始聚类中心个数k1，最大聚类中心个数kmax和距离门限rt3个参数，提出了改进的k-means算法；基于开源数据处理平台Hadoop，提出了改进k-means算法的MapReduce并行编程实现方法。最后，将所提方法用于大规模雷达信号数据集进行实验，验证了所提方法不仅能够取得更高的分选准确率，而且能够快速地对海量电磁数据中的雷达信号进行分选。
1 Hadoop和M apReduce编程模型
Hadoop是Apache下关于MapReduce等相关技术的开源实现项目，是目前MapReduce众多实现版本的标准［7］，已经被很多的研究机构和企业广泛地使用来构建自己的云计算平台。作为一个分布式的软件计算框架，Hadoop由诸多元素组成，具体如图1所示。Hadoop使用户可以在不了解分布式底层细节的情况下，充分利用集群的威力，开发分布式程序，实现高速运算和存储［8］。Hadoop具有高性能、高扩展性、开源性等优点，同时能够在普通PC机上运行，对硬件要求不高，成本较低。
图1 Hadoop组件结构
MapReduce编程模型是在并行环境下对海量数据进行分布式计算的一种编程模式，具有操作简单，容易实现且扩展性强的优点［9］。MapReduce一般包括Map和Reduce两个过程，并通过一个Job-Tracker和多个TaskTracker节点实现并行计算。Map阶段将用户提交的一个运算任务划分为若干个子任务，通过JobTracker指派多个TaskTracker完成Map计算并生成中间结果；Reduce阶段JobTracker指派多个TaskTracker通过并行的Reduce函数将中间结果进行规约合并，产生最后的输出结果。图2描述了MapReduce的执行流程图。
图2 MapReduce执行流程图
MapReduce分布式计算框架的核心是Map和Reduce函数，由编程人员自行定义实现，以键值对
2 改进k-m eans算法
改进的k-means算法引入了初始聚类中心个数k1、最大聚类中心个数kmax和距离门限rt3个参数。通过k1和kmax确定k值的取值范围，克服了需要预先给出明确k值带来的局限；通过把与各聚类中心距离大于rt的数据（孤立点）作为新的聚类中心，克服了孤立点影响已有聚类的局限。
采用加权欧几里得距离表征数据对象与聚类中心之间的距离，即
其中，x表示数据对象的测量值，u表示聚类中心的参数值，W表示加权矩阵。
改进k-means算法的步骤如下：
步骤1：设定初始聚类中心个数k1（一般取k1=2），最大聚类中心个数kmax（一般取为数据对象总个数），距离门限rt（一般取rt=0.01）；
步骤2：读入全部数据集，并令k=k1，随机选择k个数据为初始聚类中心；
步骤3：采用上述距离计算方法依次计算每个数据对象与各聚类中心之间的距离，取最小距离rmin。若rmin小于距离门限rt，则将当前数据对象归入取最小距离的类中，若rmin大于距离门限rt，则当前数据对象为孤立点，将其作为新的聚类中心，同时k=k+1。若k大于kmax，计算各聚类中心之间的距离，选择距离最小的两个聚类中心进行合并；
步骤4：更新k个聚类中心点；
步骤5：若聚类中心不发生变化，聚类结束，否则继续步骤3和步骤4。
算法串行计算流程如图3所示。
图3 改进k-means算法串行计算流程图
改进k-means算法通过设定k值的取值范围，从而在聚类过程中自动计算出聚类个数k，有效地解决了聚类结果对k值的依赖，并通过设定距离门限，发现孤立点，进而消除了其对聚类结果的影响，但因此带来了比k-means算法更高的串行实现时间复杂度。改进k-means算法串行实现时间复杂度为n×k×t×c，其中：n为数据对象总个数；k为得到的聚类个数；t为算法迭代的次数；c为一次迭代中数据对象完成聚类运算时间复杂度。为了克服算法时间复杂度较高、难以快速聚类的局限，可以对其进行并行处理，即一个数据对象在进行聚类运算的同时，其他数据对象也进行聚类运算。
3 改进k-m eans算法的M apReduce并行化方法
改进k-means算法的MapReduce并行化主要思路是：对其串行实现每1次迭代启动对应的1次MapReduce计算过程，完成数据对象聚类运算以及新的聚类中心的计算。图4描述了改进k-means算法的MapReduce并行化方法。这样算法的实现由1个主机的串行处理转变为多个节点的并行处理，若分散到m个节点，每个节点平均完成p个Map任务，则并行实现时间复杂度为（n×k×t×c）/（m×p），远低于串行实现时间复杂度。
图4 改进k-means算法的MapReduce并行化
3.1Map函数
Map函数的任务是完成每个数据对象的聚类运算。输入数据
3.2Reduce函数
Reduce函数的任务是根据Map函数得到的中间结果重新计算聚类中心，形成新的聚类中心文件供下一轮Job使用。输入数据
4 实验与分析
4.1实验环境
全部实验都是在实验室搭建的Hadoop平台上运行的，其结构如图5所示。平台共有6台机器，CPU型号为Inter（R）Core（TM）i7，8 GB内存。1台机器作为JobTracker服务节点，其他5台机器作为TaskTracker服务节点。每台机器之间用千兆以太网卡，通过交换机连接。Hadoop版本为0.20.2，并基于此配置集群。
图5 Hadoop平台结构示意图
从文献［11］选取用于信号分选的4部3 cm的机载脉冲多普勒雷达仿真数据，如表1所示，其中，PRI为脉冲重复间隔，RF为载频，PW为脉宽，AOA为脉冲到达角。在实验过程中的数据采用二进制序列化存储的方式以行形式进行存储，一方面为了适合MapReduce计算处理模型，另一方面可以提高算法运行的效率。对于等待处理的数据，MapReduce运行环境能够自行完成按行分片。
表1 雷达仿真数据
4.2聚类结果比较实验
采用3种方法对表3的雷达仿真数据进行聚类分选，总的雷达信号个数为1×106，均采用10次Monte-Carlo实验。k-means聚类算法中设定聚类数目为4，改进k-means算法中k1=2，kmax=7，rt=0.01，初始聚类中心随机选择选用分选准确率评价聚类分选结果。分选准确率是衡量雷达信号分选方法优劣的主要指标，其定义为被准确分选的总脉冲数所占脉冲总数的百分比，结果中对10次实验的分选准确率进行平均，选用平均分选准确率进行评价。实验结果如表2所示。
表2 聚类分选结果
由表2可以看出，改进k-means算法聚类分选准确率高于k-means聚类算法，验证了改进k-means算法具有更高的聚类质量，能够更加准确地对雷达信号进行分选。同时由表2可见，改进k-means算法MapReduce并行化相比改进k-means算法，分选准确率几乎一致，说明改进k-means算法通过MapReduce并行编程实现后保持了同等的聚类质量，验证了改进k-means算法基于Hadoop进行MapReduce并行化运算的可行性。
4.3加速比性能实验
加速比指同一个任务串行实现和并行实现消耗时间的比率，通常用来衡量并行系统的性能。故采用加速比验证改进k-means算法的MapReduce并行化能否满足快速聚类的要求。
本文借鉴工程上信噪比计算方法，重新定义加速比计算公式为：
其中，SP为加速比；tk为改进的k-means聚类算法单机串行处理所消耗时间；tm为改进k-means算法的MapReduce并行化处理所消耗时间。当SP<0、SP=0和SP>0时，分别说明改进k-means算法的MapReduce并行化处理消耗时间大于、等于和小于单机串行处理消耗时间。本文加速比计算公式相比传统的计算公式，能够更加方便地对实验结果进行处理和分析。
实验1为了验证同一数据集在不同节点下的加速比，实验采用文件大小为2 008.23 MB，数据个数为5.184 067×106，数据块数为78，占用HDFS空间为14 976 MB的数据集S1，要求生成5个聚类类别。
分别采用1、2、3、4，5个TaskTracker节点（以下统一简称节点）参与计算，考察在逐渐增加节点的情况下，改进k-means算法的MapReduce并行化实现的加速比。采用10次Monte-Carlo实验，k-means聚类算法中设定聚类数目为5；改进k-means算法中k1=2，kmax=8，rt=0.01；初始聚类中心随机选择。实验结果如下页图6所示。
图6 同一数据集在不同节点下的加速比
由图6可见，当节点数为1时，加速比较小，但1个节点下的MapReduce并行化运行时间相比单机串行实现时间还是缩减不少。随着节点的增加，改进k-means算法MapReduce并行化实现加速比显著增加，此时的改进k-means算法MapReduce并行化实现运行时间相比单机串行实现时间明显减小。可见，改进k-means算法MapReduce并行化实现可以快速地处理大规模数据集，增加节点数可以减少处理同一数据集所需的时间，提高了系统对同规模数据集的处理能力。
实验2为了验证不同大小的数据集在同一节点下的加速比，分别选用3个节点和5个节点在大小不同的数据集进行聚类实验。采用10次Monte-Carlo实验，k-means聚类算法中设定聚类数目为5；改进k-means算法中k1=2，kmax=8，rt=0.01；初始聚类中心随机选择。实验结果如图7所示。
图7 不同数据集在同一节点下的加速比
由图7可知，当输入数据量很少时，比如当数据个数为1×105时，SP<0，说明单机串行处理消耗时间小于Hadoop集群上改进k-means算法的MapReduce并行化处理消耗时间，即tk＜tm，这是因为实际计算任务处理时间在总消耗时间中所占的比例较小，而Hadoop集群上Job的启动和交互需要占用较大的时间。当输入数据量增大时，SP逐渐变为正值，并随着输入数据量的增大而不断变大，说明改进k-means算法的MapReduce并行化实现消耗时间开始小于并逐渐远小于单机串行处理消耗时间，当数据个数为2×106时的加速比大于数据个数为1×106，加速效果明显，验证了改进k-means算法的MapReduce并行化能够对不同规模的大数据集进行快速地处理。同时可得，5个节点所得加速比大于3个节点，再次验证了节点数越多，处理大规模数据集的效率越高，具有良好的扩展性。
实验1和实验2验证了改进k-means算法的MapReduce并行化实现具有良好的加速比和扩展性，将其应用于大规模雷达信号数据集，不仅能够取得更高的聚类分选准确率，而且可以更快地进行聚类分选。
5 结论
针对海量电磁数据无法快速进行分选的现状，提出了改进k-means算法的MapReduce并行化实现方法。通过聚类分选实验，验证了改进k-means聚类算法能够取得更高的分选准确率，对其MapReduce并行化后具有良好的加速比和扩展性，可以有效地应用于海量电磁数据中雷达信号的准确快速分选。
［1］王星.航空电子对抗原理［M］.北京：国防工业出版社，2008.
［2］解国良，徐忠伟，王洪迅，等.一种基于相邻脉冲相似性的快速聚类分选方法［J］.火力与指挥控制，2012，37（11），163-165.
［3］DEANJ，GHEMAWAR S.MapReduce：simplifieddataprocessingonlargeclusters［C］//OSDI.［s.n.］，2004：137-150.
［4］EKANAYAKE J，PALLICKARA S.MapReducefor dataintensive scientific analysis［C］//IEEE Science.Piscataway：IEEE，2008：277-284.
［5］ZHOU P，LEI J S，YE W J.Large-scaledatasets clustering basedonMapRedu-ceandhadoop［J］.Journal ofComputational InformationSystems，2011，7（6）：5956-5963.
［6］申彦.大规模数据集高效数据挖掘算法研究［D］.南京：江苏大学，2013.
［7］WHITE T.Hadoop权威指南［M］.周傲英，曾大聆，译.北京：清华大学出版社，2009.
［8］NEWMAN M E J.Fast algorithm for detecting community structure in networks［J］.Phys Rev：E，2004，69（6）：133-137.
［9］章志刚，吉根林.基于迭代式MapReduce的Apriori算法设计与实现［J］.华中科技大学学报（自然科学版），2012，40（1）：9-12.
［10］林文辉.基于Hadoop的海量网络数据处理平台的关键技术研究［D］.北京：北京邮电大学，2014.
［11］国强，王常虹，郭立民，等.分段聚类在雷达信号分选中的应用［J］.北京邮电大学学报，2008，31（2）：132-136.
An Efficient Sorting Method of Radar Signals in the Massive Electromagnetism Data
ZHANG Qiang，WANG Hong-wei，CHENYou，XU Yuan
（School of Aeronautics and Astronautics Engineering，Air Force Engineering University，Xi’an 710038，China）
Aimed at the problem that it’s hard to sort the radar signals in the massive electromagnetism data quickly and accurately，a new clustering algorithm is proposed，that is improved k-means algorithm using MapReduce programming mode.The initial clustering centers numberk1，the maximum clustering centers numberkmaxand the distance threshold rtare introduced by the improved k-means clustering algorithm，to overcome the confines of thek-means clustering algorithm that it needs the pre-determinedkvalue and is prone to be effected by isolated individual data point.Based on the Hadoop platform，Parallel implementation of the improvedk-means clustering algorithm using MapReduce programming mode is realized，to overcome the confines of thek-means algorithm that serial implementation has a high time complexity.Finally，the experimental result validates the improvedk-meansclusteringalgorithmhashighsortingprecision，andshowstheparallel implementation of the improved k-means clustering algorithm using MapReduce programming mode owns good speedup ratio and scalability.It also can sort the radar signals in the massive electromagnetism data efficiently.
massiveelectromagnetismdata，radarsignals，sorting，k-meansalgorithm，MapReduce
TP301.6
A
1002-0640（2016）10-0150-05
2015-08-13
2015-09-25
陕西省自然科学基金（2012JQ8019）；航空科学基金（20145596025）；航空科学基金资助项目（20152096019）
张强（1991-），男，陕西凤翔人，硕士研究生。研究方向：电子对抗理论与技术，数据挖掘技术。
