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

胡瑩瑩，譚光林

（國家無線電監(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ù)分析的一個(gè)重要算法，基于Hadoop的K-means算法，使用MapReduce編程框架，將傳統(tǒng)的單機(jī)串行聚類算法K-means用分布式、并行的方式實(shí)現(xiàn)，使其適用于分布式、海量的無線電監(jiān)測數(shù)據(jù)的分析和計(jì)算。本文分析了該算法的時(shí)間和空間復(fù)雜度。

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

1 引言

無線電監(jiān)測是我國各級無線電管理機(jī)構(gòu)的重要職責(zé)之一。各地市無線電管理機(jī)構(gòu)對無線電頻率進(jìn)行日常監(jiān)測，掌握信道占用度、頻段利用率及各頻段各業(yè)務(wù)段背景狀況等信息，及時(shí)發(fā)現(xiàn)并排除干擾。常年積累的監(jiān)測數(shù)據(jù)和數(shù)據(jù)分析為頻率指配、頻率規(guī)劃、頻率協(xié)調(diào)等工作提供了有效的技術(shù)支持。截至2014年底，我國已經(jīng)建成固定監(jiān)測站1,000多個(gè)，這些監(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)測、專項(xiàng)監(jiān)測和特定信號分析三類，由于專項(xiàng)監(jiān)測和特定信號分析產(chǎn)生的數(shù)據(jù)量相對較小，本文重點(diǎn)分析無線電日常監(jiān)測產(chǎn)生的數(shù)據(jù)。無線電日常監(jiān)測利用固定監(jiān)測站開展全頻段、全方位、全時(shí)段的頻譜掃描、信號測量等工作，產(chǎn)生了大量的監(jiān)測數(shù)據(jù)。

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

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

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

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

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

4 聚類分析算法

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

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

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

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

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

適當(dāng)選擇c個(gè)點(diǎn)作為初始中心

repeat

將每個(gè)點(diǎn)指派到最近的中心，形成多個(gè)簇

重新計(jì)算每個(gè)簇的中心

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

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

5.2 基于Hadoop的K-means算法

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

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

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

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

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

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

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

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

Reduce函數(shù)的任務(wù)是對Map函數(shù)的輸出結(jié)果進(jìn)行進(jìn)一步的加工，將數(shù)值加入到距離最短的簇中，使得簇?fù)碛械某蓡T數(shù)量增加，更新聚類，更新聚類中心。

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

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

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

將shuzhi加入到聚類value中；

計(jì)算更新后的聚類value的中心；

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

}

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

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

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

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

設(shè)待分析的電平值共有n個(gè)對象，要?jiǎng)澐殖蒏類，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í)，所需的運(yùn)行空間飛速增加，單臺計(jì)算機(jī)上存儲(chǔ)空間有限，限制了處理數(shù)據(jù)的規(guī)模，這從理論上解釋了傳統(tǒng)串行算法無法分析海量數(shù)據(jù)的原因?；贖adoop的K-means算法，采用分布式的方式，原始的數(shù)據(jù)文件被分割并送到p臺機(jī)器上，在每臺機(jī)器上又被切分并送到m個(gè)任務(wù)中，每個(gè)任務(wù)包含一個(gè)Map和一個(gè)Reduce函數(shù)，每個(gè)任務(wù)執(zhí)行時(shí)所需的空間是(n+K)/(m×p)，所有機(jī)器上所需的總空間是(n+K)/(m×p)×(m×p)即n+K，基于Hadoop的K-means算法的空間復(fù)雜度是O(n)。由此可見，基于Hadoop的K-means算法的空間復(fù)雜度與傳統(tǒng)串行算法相近，但是由于采用分布式的方式，降低了對每臺機(jī)器上的空間要求，使得廉價(jià)的機(jī)器可以用于處理海量數(shù)據(jù)。

7 結(jié)束語

隨著無線電行業(yè)的飛速發(fā)展，將會(huì)產(chǎn)生越來越大規(guī)模的數(shù)據(jù)。傳統(tǒng)的數(shù)據(jù)分析工具已不適應(yīng)這個(gè)形勢，基于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)濟(jì)社會(huì)發(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實(shí)戰(zhàn)（第二版）[M]．北京：機(jī)械工業(yè)出版社，2013

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

1672-7274（2015）05-0032-03

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