胡莹莹，谭光林

（国家无线电监测中心，北京 100037）

基于Hadoop的聚类算法在无线电监测数据分析中的应用

胡莹莹，谭光林

（国家无线电监测中心，北京 100037）

无线电日常监测产生了T级别的海量监测数据，但缺乏有效的数据分析软件。聚类分析是无线电监测数据分析的一个重要算法，基于Hadoop的K-means算法，使用MapReduce编程框架，将传统的单机串行聚类算法K-means用分布式、并行的方式实现，使其适用于分布式、海量的无线电监测数据的分析和计算。本文分析了该算法的时间和空间复杂度。

无线电监测；聚类；K-means算法；Hadoop；MapReduce

1 引言

无线电监测是我国各级无线电管理机构的重要职责之一。各地市无线电管理机构对无线电频率进行日常监测，掌握信道占用度、频段利用率及各频段各业务段背景状况等信息，及时发现并排除干扰。常年积累的监测数据和数据分析为频率指配、频率规划、频率协调等工作提供了有效的技术支持。截至2014年底，我国已经建成固定监测站1,000多个，这些监测站每年执行大量的无线电监测任务。随着无线电通信产业的快速发展，无线电电磁环境日益复杂，对电磁环境的不间断监测产生了海量的监测数据。

2 无线电监测数据

通常，无线电监测分为日常监测、专项监测和特定信号分析三类，由于专项监测和特定信号分析产生的数据量相对较小，本文重点分析无线电日常监测产生的数据。无线电日常监测利用固定监测站开展全频段、全方位、全时段的频谱扫描、信号测量等工作，产生了大量的监测数据。

日常监测时，按照每个接收机3G字节/天计算，若每个监测站有3台接收机，那么全国1,000个监测站，每天至少会产生约9T字节的无线电监测数据，全年不间断的监测会产生海量的数据。

“十二五”时期，各地市无线电监测站购置了大量的监测设备，在硬件上具备了开展日常无线电监测的能力，监测记录并存储每天的监测数据。但这些海量的监测数据并不提供有价值的监测信息，需要对这些数据进行清洗、提纯、统计、分析，从而得出有价值的结论。无线电监测站在数据处理上的能力相对薄弱，特别是针对海量监测数据，缺乏有效的分析软件。因此，如何对海量监测数据进行深度分析，挖取出蕴含在数据中的规律和信息，有效支撑频率台站管理、无线电监测与安全保障等工作，是目前大数据[1][2]背景下无线电监测需要重点研究的方向。

3 Hadoop框架的数据分析优势

存储在多个监测站上的无线电监测数据具有规模大、分布式存储的特点，传统的SPSS、SAS等数据分析工具无法在分布式的环境中进行数据统计分析，且无法分析T级别的海量数据，因此，需要新的数据分析软件来分析海量的监测数据。

由Apache基金会开发的Hadoop[3][4]分布式开发框架，可以部署在廉价的机器上，提供高吞吐量来访问应用程序的数据，可用于分析超大数据。无线电监测数据的规模已达到T级别，且分布于不同的监测站内，Hadoop能够很好地适应无线电监测数据分布式、大规模的数据特点。Hadoop采用HDFS分布式文件系统，可以分析存储在多个监测站文件存储器上的监测数据，使用MapReduce编程模型，调用多台普通机器上的CPU同时工作，提供强大的计算能力，快速完成海量监测数据的处理分析，输出处理结果。

4 聚类分析算法

聚类分析[5]是数据挖掘中的一个重要算法，它被广泛应用于统计、生物、医药、电信等领域，在无线电领域内的应用也极其广泛。例如，通过聚类分析算法对监测到的电平信号进行分析，为中心频点的计算提供依据。随着无线电行业的快速发展，监测数据规模越来越大，传统的聚类分析算法已经无法在单机上处理如此规模的数据。

替代方法是使用价格昂贵的超级计算机，或者使用多台小型机器并行处理数据。由于超级计算机价格十分昂贵，无法广泛用于监测站的日常数据处理。而在多台廉价PC上，使用并行算法处理监测数据，具有部署容易、成本低的优点，成为可行的解决方案。本文将介绍基于Hadoop开发框架，使用MapReduce实现聚类算法K-means，将传统的单机串行聚类算法K-means用分布式、并行的方式实现，使其适用于分布式、海量的无线电监测数据的分析和计算。

5 基于Hadoop的K-means算法实现

5.1 传统K-means算法实现

传统K-means算法实现的步骤如下：

适当选择c个点作为初始中心

repeat

将每个点指派到最近的中心，形成多个簇

重新计算每个簇的中心

until簇不发生变化（簇收敛）

传统的K-means算法[6][7]是经典的数据挖掘聚类算法，各类文献中多有介绍，本文不展开阐述。通过该算法，可以找出数据中具有某类相同特征的数据，如将监测数据中数值相近的电平值归为一个聚类，进而找出中心频率，为后续的工作提供基础数据。

5.2 基于Hadoop的K-means算法

（1）Map函数的设计

Map函数的功能是将存储的无线电监测数据中的每一条数据（每一个电平值）归入到一个簇中，归入的原则是找到这条数据距离最短的簇的中心。因此，需要计算出每个数据离所有簇的中心距离，并进行记录。

Map函数的输入是原始监测数据文件和初始选定的聚类。Map函数的具体描述如下：

public void map (Key line, Julei value) {读取一个电平数据；

计算该数据到每一个簇的中心距离；比较该数据到所有簇的距离；

记录该数据和其距离最近的簇；}

Map函数输出当前数值及其距离最短的簇，作为Reduce函数的输入。

（2）Reduce函数的设计

Reduce函数的任务是对Map函数的输出结果进行进一步的加工，将数值加入到距离最短的簇中，使得簇拥有的成员数量增加，更新聚类，更新聚类中心。

Reduce函数的具体描述如下：

public void reduce(Julei value, Iteratable〈shuzhi〉) {

for（对于value相同的所有数值）{

将shuzhi加入到聚类value中；

计算更新后的聚类value的中心；

当更新后的聚类中心与更新前的聚类中心相同（收敛）时，Reduce函数处理结束；}

}

Reduce函数最后一次的输出结果，是基于Hadoop的K-means算法对监测数据进行聚类分析的最终结果。

6 时间和空间复杂度分析

本文研究的基于Hadoop的K-means算法对监测数据进行聚类分析，所使用的电平值聚类维度是一维，并在此基础上进行了算法的时间和空间复杂度分析。

设待分析的电平值共有n个对象，要划分成K类，t为算法进行迭代的次数，那么串行算法的时间复杂度至少为n×K×t，而K，t均可认为是常量，因此，传统串行K-means算法的时间复杂度是O(n)。在基于Hadoop的K-means算法中，电平数据被分配到p台机器上同时处理，假设每台机器上运行m个执行Map和Reduce函数的任务，Map和Reduce函数一共迭代了k次，则理论上基于Hadoop的K-means算法的时间复杂度为O(n)/(p×m)×k，k，m均可认为是常量，因此基于Hadoop的K-means算法的时间复杂度是O(n)/p。当p较小时，监测数据在不同机器上的传送、算法执行过程中机器间的通信等因素将影响基于Hadoop的K-means算法的执行时间；但随着机器台数p的显著增加，基于Hadoop的K-means算法的执行时间将与p成反比例关系，算法运行时间显著降低。

设待分析的电平值共有n个对象，要划分成K类，t为迭代次数，那么，传统串行算法的空间复杂度至少为n+K，传统串行K-means算法的空间复杂度是O(n)，算法执行所需的空间随着数据规模的增长而急剧增加，当处理海量的无线电监测数据时，所需的运行空间飞速增加，单台计算机上存储空间有限，限制了处理数据的规模，这从理论上解释了传统串行算法无法分析海量数据的原因。基于Hadoop的K-means算法，采用分布式的方式，原始的数据文件被分割并送到p台机器上，在每台机器上又被切分并送到m个任务中，每个任务包含一个Map和一个Reduce函数，每个任务执行时所需的空间是(n+K)/(m×p)，所有机器上所需的总空间是(n+K)/(m×p)×(m×p)即n+K，基于Hadoop的K-means算法的空间复杂度是O(n)。由此可见，基于Hadoop的K-means算法的空间复杂度与传统串行算法相近，但是由于采用分布式的方式，降低了对每台机器上的空间要求，使得廉价的机器可以用于处理海量数据。

7 结束语

随着无线电行业的飞速发展，将会产生越来越大规模的数据。传统的数据分析工具已不适应这个形势，基于Hadoop框架来分析海量的无线电数据，为无线电数据的深度分析指明了新的方向。

[1] Big data: The Next Frontier for Innovation, Competition, and Productivity[EB]. http: //www.mckinsey.com/insights/mgi/research/ technology_and_innovation/big_data_the_next_frontier_for_innovation, 2013.1.24

[2] 李国杰，程学旗．大数据研究：未来科技及经济社会发展的重大战略领域——大数据的研究现状与科学思考[J]．中国科学院院刊，2012,27(6):647-657

[3] Tom White．Hadoop权威指南（第二版）[M]．北京：清华大学出版社，2011.7

[4] 陆嘉恒．Hadoop实战（第二版）[M]．北京：机械工业出版社，2013

[5] 贺玲，吴玲达，蔡益朝．数据挖掘中的聚类算法综述[J]．计算机应用研究，2007(01)

[6] PierreHansen, EricNgai, BernardK.Cheung, NenadMladenovic. Analysis of Global k-Means, an Incremental Heuristic for Minimum Sum-of-Squares Clustering[J]. Journal of Classification, 2005 (2)

[7] 孙凤菊．K-means聚类算法的研究实现[J]．辽宁师专学报（自然科学版），2012(01)

Application of Cluster Algorithm based on Hadoop in Analysis of Radio Monitoring Data

Hu Yingying, Tan Guanglin

(The State Radio Monitoring Center, Beijing,100037)

Daily radio monitoring produces T-level data , while lacking of effective data analysis software. Cluster algorithm is very important in analysis of monitoring data .we realize the traditional K-means algorithm in the way of distributed, parallel manner based on Hadoop, with MapReduce programming framework, making it ideal for distributed, vast quantities of radio monitoring data analysis and calculations. This paper also analyzes the time and space complexity of algorithms.

radio monitoring; cluster; K-means algorithm; Hadoop; MapReduce

10.3969/J.ISSN.1672-7274.2015.05.009

TP399 文献标示码：A

1672-7274（2015）05-0032-03

胡莹莹，女，1988年生，硕士，毕业于北京航空航天大学计算机学院，现任职于国家无线电监测中心，从事信息管理工作。谭光林，男，1986年生，硕士，毕业于北京邮电大学计算机学院，现任职于国家无线电监测中心，从事信息管理工作。