基于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 平台的算法主要由这几类算法延伸或演变而来，本文对这些算法进行了概括性的分析和研究。