基于Hadoop的聚類算法在無線電監測數據分析中的應用

胡瑩瑩，譚光林

（國家無線電監測中心，北京 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年生，碩士，畢業于北京郵電大學計算機學院，現任職于國家無線電監測中心，從事信息管理工作。