胡瑩瑩，譚光林

（國家無線電監(jiān)測中心，北京 100037）

基于Hadoop的聚類算法在無線電監(jiān)測數(shù)據(jù)分析中的應(yīng)用

胡瑩瑩，譚光林

（國家無線電監(jiān)測中心，北京 100037）

無線電日常監(jiān)測產(chǎn)生了T級別的海量監(jiān)測數(shù)據(jù)，但缺乏有效的數(shù)據(jù)分析軟件。聚類分析是無線電監(jiān)測數(shù)據(jù)分析的一個重要算法，基于Hadoop的K-means算法，使用MapReduce編程框架，將傳統(tǒng)的單機串行聚類算法K-means用分布式、并行的方式實現(xiàn)，使其適用于分布式、海量的無線電監(jiān)測數(shù)據(jù)的分析和計算。本文分析了該算法的時間和空間復(fù)雜度。

無線電監(jiān)測；聚類；K-means算法；Hadoop；MapReduce

1 引言

無線電監(jiān)測是我國各級無線電管理機構(gòu)的重要職責(zé)之一。各地市無線電管理機構(gòu)對無線電頻率進行日常監(jiān)測，掌握信道占用度、頻段利用率及各頻段各業(yè)務(wù)段背景狀況等信息，及時發(fā)現(xiàn)并排除干擾。常年積累的監(jiān)測數(shù)據(jù)和數(shù)據(jù)分析為頻率指配、頻率規(guī)劃、頻率協(xié)調(diào)等工作提供了有效的技術(shù)支持。截至2014年底，我國已經(jīng)建成固定監(jiān)測站1,000多個，這些監(jiān)測站每年執(zhí)行大量的無線電監(jiān)測任務(wù)。隨著無線電通信產(chǎn)業(yè)的快速發(fā)展，無線電電磁環(huán)境日益復(fù)雜，對電磁環(huán)境的不間斷監(jiān)測產(chǎn)生了海量的監(jiān)測數(shù)據(jù)。

2 無線電監(jiān)測數(shù)據(jù)

通常，無線電監(jiān)測分為日常監(jiān)測、專項監(jiān)測和特定信號分析三類，由于專項監(jiān)測和特定信號分析產(chǎn)生的數(shù)據(jù)量相對較小，本文重點分析無線電日常監(jiān)測產(chǎn)生的數(shù)據(jù)。無線電日常監(jiān)測利用固定監(jiān)測站開展全頻段、全方位、全時段的頻譜掃描、信號測量等工作，產(chǎn)生了大量的監(jiān)測數(shù)據(jù)。

日常監(jiān)測時，按照每個接收機3G字節(jié)/天計算，若每個監(jiān)測站有3臺接收機，那么全國1,000個監(jiān)測站，每天至少會產(chǎn)生約9T字節(jié)的無線電監(jiān)測數(shù)據(jù)，全年不間斷的監(jiān)測會產(chǎn)生海量的數(shù)據(jù)。

“十二五”時期，各地市無線電監(jiān)測站購置了大量的監(jiān)測設(shè)備，在硬件上具備了開展日常無線電監(jiān)測的能力，監(jiān)測記錄并存儲每天的監(jiān)測數(shù)據(jù)。但這些海量的監(jiān)測數(shù)據(jù)并不提供有價值的監(jiān)測信息，需要對這些數(shù)據(jù)進行清洗、提純、統(tǒng)計、分析，從而得出有價值的結(jié)論。無線電監(jiān)測站在數(shù)據(jù)處理上的能力相對薄弱，特別是針對海量監(jiān)測數(shù)據(jù)，缺乏有效的分析軟件。因此，如何對海量監(jiān)測數(shù)據(jù)進行深度分析，挖取出蘊含在數(shù)據(jù)中的規(guī)律和信息，有效支撐頻率臺站管理、無線電監(jiān)測與安全保障等工作，是目前大數(shù)據(jù)[1][2]背景下無線電監(jiān)測需要重點研究的方向。

3 Hadoop框架的數(shù)據(jù)分析優(yōu)勢

存儲在多個監(jiān)測站上的無線電監(jiān)測數(shù)據(jù)具有規(guī)模大、分布式存儲的特點，傳統(tǒng)的SPSS、SAS等數(shù)據(jù)分析工具無法在分布式的環(huán)境中進行數(shù)據(jù)統(tǒng)計分析，且無法分析T級別的海量數(shù)據(jù)，因此，需要新的數(shù)據(jù)分析軟件來分析海量的監(jiān)測數(shù)據(jù)。

由Apache基金會開發(fā)的Hadoop[3][4]分布式開發(fā)框架，可以部署在廉價的機器上，提供高吞吐量來訪問應(yīng)用程序的數(shù)據(jù)，可用于分析超大數(shù)據(jù)。無線電監(jiān)測數(shù)據(jù)的規(guī)模已達到T級別，且分布于不同的監(jiān)測站內(nèi)，Hadoop能夠很好地適應(yīng)無線電監(jiān)測數(shù)據(jù)分布式、大規(guī)模的數(shù)據(jù)特點。Hadoop采用HDFS分布式文件系統(tǒng)，可以分析存儲在多個監(jiān)測站文件存儲器上的監(jiān)測數(shù)據(jù)，使用MapReduce編程模型，調(diào)用多臺普通機器上的CPU同時工作，提供強大的計算能力，快速完成海量監(jiān)測數(shù)據(jù)的處理分析，輸出處理結(jié)果。

4 聚類分析算法

聚類分析[5]是數(shù)據(jù)挖掘中的一個重要算法，它被廣泛應(yīng)用于統(tǒng)計、生物、醫(yī)藥、電信等領(lǐng)域，在無線電領(lǐng)域內(nèi)的應(yīng)用也極其廣泛。例如，通過聚類分析算法對監(jiān)測到的電平信號進行分析，為中心頻點的計算提供依據(jù)。隨著無線電行業(yè)的快速發(fā)展，監(jiān)測數(shù)據(jù)規(guī)模越來越大，傳統(tǒng)的聚類分析算法已經(jīng)無法在單機上處理如此規(guī)模的數(shù)據(jù)。

替代方法是使用價格昂貴的超級計算機，或者使用多臺小型機器并行處理數(shù)據(jù)。由于超級計算機價格十分昂貴，無法廣泛用于監(jiān)測站的日常數(shù)據(jù)處理。而在多臺廉價PC上，使用并行算法處理監(jiān)測數(shù)據(jù)，具有部署容易、成本低的優(yōu)點，成為可行的解決方案。本文將介紹基于Hadoop開發(fā)框架，使用MapReduce實現(xiàn)聚類算法K-means，將傳統(tǒng)的單機串行聚類算法K-means用分布式、并行的方式實現(xiàn)，使其適用于分布式、海量的無線電監(jiān)測數(shù)據(jù)的分析和計算。

5 基于Hadoop的K-means算法實現(xiàn)

5.1 傳統(tǒng)K-means算法實現(xiàn)

傳統(tǒng)K-means算法實現(xiàn)的步驟如下：

適當(dāng)選擇c個點作為初始中心

repeat

將每個點指派到最近的中心，形成多個簇

重新計算每個簇的中心

until簇不發(fā)生變化（簇收斂）

傳統(tǒng)的K-means算法[6][7]是經(jīng)典的數(shù)據(jù)挖掘聚類算法，各類文獻中多有介紹，本文不展開闡述。通過該算法，可以找出數(shù)據(jù)中具有某類相同特征的數(shù)據(jù)，如將監(jiān)測數(shù)據(jù)中數(shù)值相近的電平值歸為一個聚類，進而找出中心頻率，為后續(xù)的工作提供基礎(chǔ)數(shù)據(jù)。

5.2 基于Hadoop的K-means算法

（1）Map函數(shù)的設(shè)計

Map函數(shù)的功能是將存儲的無線電監(jiān)測數(shù)據(jù)中的每一條數(shù)據(jù)（每一個電平值）歸入到一個簇中，歸入的原則是找到這條數(shù)據(jù)距離最短的簇的中心。因此，需要計算出每個數(shù)據(jù)離所有簇的中心距離，并進行記錄。

Map函數(shù)的輸入是原始監(jiān)測數(shù)據(jù)文件和初始選定的聚類。Map函數(shù)的具體描述如下：

public void map (Key line, Julei value) {讀取一個電平數(shù)據(jù)；

計算該數(shù)據(jù)到每一個簇的中心距離；比較該數(shù)據(jù)到所有簇的距離；

記錄該數(shù)據(jù)和其距離最近的簇；}

Map函數(shù)輸出當(dāng)前數(shù)值及其距離最短的簇，作為Reduce函數(shù)的輸入。

（2）Reduce函數(shù)的設(shè)計

Reduce函數(shù)的任務(wù)是對Map函數(shù)的輸出結(jié)果進行進一步的加工，將數(shù)值加入到距離最短的簇中，使得簇擁有的成員數(shù)量增加，更新聚類，更新聚類中心。

Reduce函數(shù)的具體描述如下：

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

for（對于value相同的所有數(shù)值）{

將shuzhi加入到聚類value中；

計算更新后的聚類value的中心；

當(dāng)更新后的聚類中心與更新前的聚類中心相同（收斂）時，Reduce函數(shù)處理結(jié)束；}

}

Reduce函數(shù)最后一次的輸出結(jié)果，是基于Hadoop的K-means算法對監(jiān)測數(shù)據(jù)進行聚類分析的最終結(jié)果。

6 時間和空間復(fù)雜度分析

本文研究的基于Hadoop的K-means算法對監(jiān)測數(shù)據(jù)進行聚類分析，所使用的電平值聚類維度是一維，并在此基礎(chǔ)上進行了算法的時間和空間復(fù)雜度分析。

設(shè)待分析的電平值共有n個對象，要劃分成K類，t為算法進行迭代的次數(shù)，那么串行算法的時間復(fù)雜度至少為n×K×t，而K，t均可認為是常量，因此，傳統(tǒng)串行K-means算法的時間復(fù)雜度是O(n)。在基于Hadoop的K-means算法中，電平數(shù)據(jù)被分配到p臺機器上同時處理，假設(shè)每臺機器上運行m個執(zhí)行Map和Reduce函數(shù)的任務(wù)，Map和Reduce函數(shù)一共迭代了k次，則理論上基于Hadoop的K-means算法的時間復(fù)雜度為O(n)/(p×m)×k，k，m均可認為是常量，因此基于Hadoop的K-means算法的時間復(fù)雜度是O(n)/p。當(dāng)p較小時，監(jiān)測數(shù)據(jù)在不同機器上的傳送、算法執(zhí)行過程中機器間的通信等因素將影響基于Hadoop的K-means算法的執(zhí)行時間；但隨著機器臺數(shù)p的顯著增加，基于Hadoop的K-means算法的執(zhí)行時間將與p成反比例關(guān)系，算法運行時間顯著降低。

設(shè)待分析的電平值共有n個對象，要劃分成K類，t為迭代次數(shù)，那么，傳統(tǒng)串行算法的空間復(fù)雜度至少為n+K，傳統(tǒng)串行K-means算法的空間復(fù)雜度是O(n)，算法執(zhí)行所需的空間隨著數(shù)據(jù)規(guī)模的增長而急劇增加，當(dāng)處理海量的無線電監(jiān)測數(shù)據(jù)時，所需的運行空間飛速增加，單臺計算機上存儲空間有限，限制了處理數(shù)據(jù)的規(guī)模，這從理論上解釋了傳統(tǒng)串行算法無法分析海量數(shù)據(jù)的原因?；贖adoop的K-means算法，采用分布式的方式，原始的數(shù)據(jù)文件被分割并送到p臺機器上，在每臺機器上又被切分并送到m個任務(wù)中，每個任務(wù)包含一個Map和一個Reduce函數(shù)，每個任務(wù)執(zhí)行時所需的空間是(n+K)/(m×p)，所有機器上所需的總空間是(n+K)/(m×p)×(m×p)即n+K，基于Hadoop的K-means算法的空間復(fù)雜度是O(n)。由此可見，基于Hadoop的K-means算法的空間復(fù)雜度與傳統(tǒng)串行算法相近，但是由于采用分布式的方式，降低了對每臺機器上的空間要求，使得廉價的機器可以用于處理海量數(shù)據(jù)。

7 結(jié)束語

隨著無線電行業(yè)的飛速發(fā)展，將會產(chǎn)生越來越大規(guī)模的數(shù)據(jù)。傳統(tǒng)的數(shù)據(jù)分析工具已不適應(yīng)這個形勢，基于Hadoop框架來分析海量的無線電數(shù)據(jù)，為無線電數(shù)據(jù)的深度分析指明了新的方向。

[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] 李國杰，程學(xué)旗．大數(shù)據(jù)研究：未來科技及經(jīng)濟社會發(fā)展的重大戰(zhàn)略領(lǐng)域——大數(shù)據(jù)的研究現(xiàn)狀與科學(xué)思考[J]．中國科學(xué)院院刊，2012,27(6):647-657

[3] Tom White．Hadoop權(quán)威指南（第二版）[M]．北京：清華大學(xué)出版社，2011.7

[4] 陸嘉恒．Hadoop實戰(zhàn)（第二版）[M]．北京：機械工業(yè)出版社，2013

[5] 賀玲，吳玲達，蔡益朝．?dāng)?shù)據(jù)挖掘中的聚類算法綜述[J]．計算機應(yīng)用研究，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聚類算法的研究實現(xiàn)[J]．遼寧師專學(xué)報（自然科學(xué)版），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 文獻標(biāo)示碼：A

1672-7274（2015）05-0032-03

胡瑩瑩，女，1988年生，碩士，畢業(yè)于北京航空航天大學(xué)計算機學(xué)院，現(xiàn)任職于國家無線電監(jiān)測中心，從事信息管理工作。譚光林，男，1986年生，碩士，畢業(yè)于北京郵電大學(xué)計算機學(xué)院，現(xiàn)任職于國家無線電監(jiān)測中心，從事信息管理工作。