基于Hadoop 平臺的海量數據挖掘算法的研究分析

羅釗航，車 宇，楊澤威

（中國核動力研究設計院，成都 610005）

近些年我國廣播電視業在積極發展的過程中，也帶動了無線網的建設與發展，特別是在數字化進程下，我國無線微波網也正在加快落實數字化升級，尤其是建設微波中繼通信系統有著建設快、成本低的優勢。因此數字微波電路及其路由設計也需要積極朝著數字化的方向發展，以便可以更好地適應現代化、數字化的廣播電視無線傳輸系統。而通過明確數字微波電路路由設計的注意問題，對保障其設計科學合理性具有積極的幫助作用。

1 Hadoop 相關技術

Hadoop 架構是用于集群分布式計算，是集存儲、處理、計算、分析等為一體的分布式系統并行執行環境。Hadoop 框架以HDFS和Map/Reduce 編程模型為核心。HDFS 負責管理分布式文件存儲系統,Map/Reduce 編程模型為“先分解任務，計算，再匯總結果”的計算框架。Hadoop 平臺的計算和存儲在一個節點，這種搭配模式更能高效快速的使用資源。

2 傳統的數據挖掘算法

本節將主要介紹傳統的數據挖掘算法。

2.1 K-means 聚類算法

聚類算法屬于無監督特性的機器學習領域的算法，最典型的聚類算法為K-means 算法，由于它具有原理簡單和收斂速度快這兩種特性，因而在數據挖掘方面K-means 算法有很大研究和發展。

2.2 改進的PrePost 算法

PrePost 算法雖然常用于數據挖掘，但存在構建結構樹效率低下的問題，為適應基于Hadoop 平臺的大數據挖掘，常對PrePost 算法進行改進，基于B-list 的改進PrePost 算法便是其中一種，它具有良好的用高效的連接和剪枝策略等優勢。

2.3 基于矩陣的Apriori 算法

基于矩陣的Apriori 算法是Apriori 算法的改進型，原理如下：設事務數據庫M，遍歷M 中的每個事務，得到矩陣。算法的描述如下：

輸入：事務數據庫

輸出：頻繁項集

（1）掃描事務數據庫，轉換為矩陣。

（2）計算各項的支持度得到頻繁1-項集。

（3）計算頻繁i-項集中項籍的個數Li。

（4）若Li

（5）連接i-項集，從而得到（i+1）-項集，再對（i+1）-項集剪枝。

（6）計算所有（i+1）-項集的支持度。

（7）計算頻繁（i+1）-項集。

（8）結束。

3 改進型的數據挖掘算法

本節將主要介紹改進型數據挖掘算法。

3.1 基于Hadoop 的K-means 聚類算法改進型

基于Hadoop 的K-means 聚類算法改進型思想如下：

（1）首先分割數據，并對分割后的數據進行計算，Map 階段計算樣本之間的距離，Reduce 階段完成計算并找到初始聚類中心。

（2）進入二次迭代。

（3）二次迭代中使用K-means 聚類算法得到鍵值。

（4）通過Map/Reduce 更新聚類中心。

（5）計算平均誤差準則函數。

（6）若結果不收斂，進行第（2）步；若結果收斂，輸出K個類簇，算法結束。

3.2 基于Hadoop 的數據挖掘算法改進型

基于Hadoop 的數據挖掘算法改進型[1]的核心思想為：通過負載均衡策略使用Hadoop 集群中的HDFS 與Map/Reduce 模型對數據進行計算，得到所有的頻繁模式，再通過kulczynski 度量和不平衡比評估頻繁模式，挖掘數據中的價值。

3.3 基于Hadoop 的Apriori 算法

由于Hadoop 集群的通信會占用部分硬件系統資源，如I/0、內存等，而Apriori 算法可以減少對事務數據庫的掃描，因而將兩者結合起來，可以極大地提高算法的效率。基于Hadoop 的Apriori 算法可以將掃描數據庫次數降為2次，且無大量中間結果集產生。

4 改進型算法分析

4.1 基于Hadoop 的改進型K-means 聚類算法

在算法準確率方面，明顯高于傳統K-means 聚類算法，此算法在準確率上有良好的性能，在集群環境的計算優勢逐漸顯示出來，隨著節點數的增加，數據量越大加速比越大。

4.2 基于Hadoop 的改進型頻繁模式挖掘算法

基于Hadoop 的改進型頻繁模式挖掘算法執行時間是由集群中執行最長時間的節點決定的，因而這個算法的核心使對整個集群做負載均衡。優秀的負載均衡算法能夠使所有節點的耗時接近，節點之間通信數據量小，系統開銷低，從而提高此算法的效率。

4.3 基于Hadoop 的Apriori 算法

基于矩陣的Apriori 算法[2，3]由于減少了對事務數據庫的掃描次數，因而效率高，在同等數據量下，算法耗時短。

5 總結

總的來講，數據挖機算法多種多樣，各有優劣，當前基于Hadoop 平臺的算法主要由這幾類算法延伸或演變而來，本文對這些算法進行了概括性的分析和研究。