基于Hadoop 平臺(tái)的海量數(shù)據(jù)挖掘算法的研究分析

羅釗航，車 宇，楊澤威

（中國核動(dòng)力研究設(shè)計(jì)院，成都 610005）

近些年我國廣播電視業(yè)在積極發(fā)展的過程中，也帶動(dòng)了無線網(wǎng)的建設(shè)與發(fā)展，特別是在數(shù)字化進(jìn)程下，我國無線微波網(wǎng)也正在加快落實(shí)數(shù)字化升級(jí)，尤其是建設(shè)微波中繼通信系統(tǒng)有著建設(shè)快、成本低的優(yōu)勢(shì)。因此數(shù)字微波電路及其路由設(shè)計(jì)也需要積極朝著數(shù)字化的方向發(fā)展，以便可以更好地適應(yīng)現(xiàn)代化、數(shù)字化的廣播電視無線傳輸系統(tǒng)。而通過明確數(shù)字微波電路路由設(shè)計(jì)的注意問題，對(duì)保障其設(shè)計(jì)科學(xué)合理性具有積極的幫助作用。

1 Hadoop 相關(guān)技術(shù)

Hadoop 架構(gòu)是用于集群分布式計(jì)算，是集存儲(chǔ)、處理、計(jì)算、分析等為一體的分布式系統(tǒng)并行執(zhí)行環(huán)境。Hadoop 框架以HDFS和Map/Reduce 編程模型為核心。HDFS 負(fù)責(zé)管理分布式文件存儲(chǔ)系統(tǒng),Map/Reduce 編程模型為“先分解任務(wù)，計(jì)算，再匯總結(jié)果”的計(jì)算框架。Hadoop 平臺(tái)的計(jì)算和存儲(chǔ)在一個(gè)節(jié)點(diǎn)，這種搭配模式更能高效快速的使用資源。

2 傳統(tǒng)的數(shù)據(jù)挖掘算法

本節(jié)將主要介紹傳統(tǒng)的數(shù)據(jù)挖掘算法。

2.1 K-means 聚類算法

聚類算法屬于無監(jiān)督特性的機(jī)器學(xué)習(xí)領(lǐng)域的算法，最典型的聚類算法為K-means 算法，由于它具有原理簡(jiǎn)單和收斂速度快這兩種特性，因而在數(shù)據(jù)挖掘方面K-means 算法有很大研究和發(fā)展。

2.2 改進(jìn)的PrePost 算法

PrePost 算法雖然常用于數(shù)據(jù)挖掘，但存在構(gòu)建結(jié)構(gòu)樹效率低下的問題，為適應(yīng)基于Hadoop 平臺(tái)的大數(shù)據(jù)挖掘，常對(duì)PrePost 算法進(jìn)行改進(jìn)，基于B-list 的改進(jìn)PrePost 算法便是其中一種，它具有良好的用高效的連接和剪枝策略等優(yōu)勢(shì)。

2.3 基于矩陣的Apriori 算法

基于矩陣的Apriori 算法是Apriori 算法的改進(jìn)型，原理如下：設(shè)事務(wù)數(shù)據(jù)庫M，遍歷M 中的每個(gè)事務(wù)，得到矩陣。算法的描述如下：

輸入：事務(wù)數(shù)據(jù)庫

輸出：頻繁項(xiàng)集

（1）掃描事務(wù)數(shù)據(jù)庫，轉(zhuǎn)換為矩陣。

（2）計(jì)算各項(xiàng)的支持度得到頻繁1-項(xiàng)集。

（3）計(jì)算頻繁i-項(xiàng)集中項(xiàng)籍的個(gè)數(shù)Li。

（4）若Li

（5）連接i-項(xiàng)集，從而得到（i+1）-項(xiàng)集，再對(duì)（i+1）-項(xiàng)集剪枝。

（6）計(jì)算所有（i+1）-項(xiàng)集的支持度。

（7）計(jì)算頻繁（i+1）-項(xiàng)集。

（8）結(jié)束。

3 改進(jìn)型的數(shù)據(jù)挖掘算法

本節(jié)將主要介紹改進(jìn)型數(shù)據(jù)挖掘算法。

3.1 基于Hadoop 的K-means 聚類算法改進(jìn)型

基于Hadoop 的K-means 聚類算法改進(jìn)型思想如下：

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

（2）進(jìn)入二次迭代。

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

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

（5）計(jì)算平均誤差準(zhǔn)則函數(shù)。

（6）若結(jié)果不收斂，進(jìn)行第（2）步；若結(jié)果收斂，輸出K個(gè)類簇，算法結(jié)束。

3.2 基于Hadoop 的數(shù)據(jù)挖掘算法改進(jìn)型

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

3.3 基于Hadoop 的Apriori 算法

由于Hadoop 集群的通信會(huì)占用部分硬件系統(tǒng)資源，如I/0、內(nèi)存等，而Apriori 算法可以減少對(duì)事務(wù)數(shù)據(jù)庫的掃描，因而將兩者結(jié)合起來，可以極大地提高算法的效率。基于Hadoop 的Apriori 算法可以將掃描數(shù)據(jù)庫次數(shù)降為2次，且無大量中間結(jié)果集產(chǎn)生。

4 改進(jìn)型算法分析

4.1 基于Hadoop 的改進(jìn)型K-means 聚類算法

在算法準(zhǔn)確率方面，明顯高于傳統(tǒng)K-means 聚類算法，此算法在準(zhǔn)確率上有良好的性能，在集群環(huán)境的計(jì)算優(yōu)勢(shì)逐漸顯示出來，隨著節(jié)點(diǎn)數(shù)的增加，數(shù)據(jù)量越大加速比越大。

4.2 基于Hadoop 的改進(jìn)型頻繁模式挖掘算法

基于Hadoop 的改進(jìn)型頻繁模式挖掘算法執(zhí)行時(shí)間是由集群中執(zhí)行最長(zhǎng)時(shí)間的節(jié)點(diǎn)決定的，因而這個(gè)算法的核心使對(duì)整個(gè)集群做負(fù)載均衡。優(yōu)秀的負(fù)載均衡算法能夠使所有節(jié)點(diǎn)的耗時(shí)接近，節(jié)點(diǎn)之間通信數(shù)據(jù)量小，系統(tǒng)開銷低，從而提高此算法的效率。

4.3 基于Hadoop 的Apriori 算法

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

5 總結(jié)

總的來講，數(shù)據(jù)挖機(jī)算法多種多樣，各有優(yōu)劣，當(dāng)前基于Hadoop 平臺(tái)的算法主要由這幾類算法延伸或演變而來，本文對(duì)這些算法進(jìn)行了概括性的分析和研究。