改进的云计算环境的下的并行数据挖掘策略

开篇：润墨网以专业的文秘视角，为您筛选了一篇改进的云计算环境的下的并行数据挖掘策略范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

云计算是一种新兴的共享基础架构的方法，它以公开的标准和服务为基础，以互联网为中心，提供安全、快速、便捷的数据存储和网络计算服务。将云计算应用到数据挖掘中，可以为越来越多的海量数据挖掘提供解决方案。云计算面对的是 TB 乃至 PB 级的海量数据，如何从数据中获取有效的信息，这将是决定云计算应用成败的关键之一。除了利用并行计算技术加速数据处理的速度外，还需要新的思路、方法和算法来完成更准确、快捷、强大的数据挖掘。

一、 Apriori 算法描述与问题分析

1.算法描述

Apriori算法是挖掘产生布尔关联规则所需频繁项集的基本算法，也是一个很有影响的关联规则挖掘算法。Apriori算法就是根据有关频繁项集性质的先验知识而命名的。该算法使用一种称作逐层搜索的迭代方法，利用k 项集来产生（k +1）项集。具体包含两个主要的处理步骤，即连接和删除。以用Lk-1来产生Lk为例，挖掘过程如下：

（1）连接步骤：为发现Lk，通过将Lk-1与自身连接产生候选 k 项集的集合Ck 。设I1 和I2为Lk-1中的两个项集，Ii[j]表示Ii中的第j个项。为方便起见，Apriori假定事务或项集中的项按字典次序排序。对于（k +1）项集Ii，意味将项排序，使Ii[1]< Ii[2]

（2）删除步骤：Ck是Lk的一个超集，其中的各项集不一定都是频繁项集，但所有的频繁K项集一定都在Ck中，即有Lk ∈Ck。扫描一遍数据库就可以决定Ck中各候选项集的支持度计数，并由此获得Lk中各个元素（频繁k项集）。所有支持度计数不小于最小支持度计数的候选项集就是属于Lk的频繁项集。然而由于Ck中的候选项集很多，如此操作所涉及的计算量是非常大的。

为提高频繁项集逐层产生的效率。Apriori算法有一个用于缩小频繁项集的搜索空间的性质："频繁项集的所有非空子集也必须是频繁的"。也就是说，若一个候选k项集中任一个子集项集不属于Lk-1，那么该候选k项集也不可能是频繁的，因而也就可以将其从Ck中删去。

Apriori 算法的优点是结构简单，易于理解，没有复杂的推导。另外，算法应用 Apriori性质在许多情况下大大缩小了需要检查的候选规模，使算法效率大幅度提高。

2.存在问题分析

Apriori 算法存在两个主要的问题：

（1）多次扫描数据库

Apriori 算法在每进行一次迭代的时候需要扫描一次数据库，一般当挖掘出的最大频繁项集的长度为N时，需要扫描 N 次数据库。而在实际应用中，经常需要挖掘很长的模式，多次扫描数据库将带来巨大开销。

（2）可能产生大量候选频繁项集

Apriori 算法在迭代过程中要在内存中产生、处理和保存候选频繁项集，这个数量有时候是非常巨大的。例如，如果有104 个频繁 1 项集，则 Apriori 算法要产生接近57个候选 2 项集。另外，为了发现长度为 100 的频繁模式，它必须产生多达2100≈1030个候选，导致算法在广度和深度上的适应性很差。

总之，Apriori 通过对数据库的多趟扫描来发现所有的频繁项集，而对存储海量数据的数据库的多趟扫描将耗费大量时间和内存空间，这将成为 Apriori 算法的瓶颈。为此，近年来有关并行数据挖掘算法的研究不断升温。

二、改进方案

1 第一种改进

具体的改进思路是：

（1）把事务数据库水平均匀的分成规模相当的 n 个数据子集，把数据子集发送到 m 个节点。

（2）每个节点扫描它的数据子集，产生一个局部的候选 k 项集的集合，记作 ，每个候选k 项集的支持度计数为1。

（3）利用分区函数将 m 个节点产生的中间结果Cp 分成r个不同分区，然后连同它们的支持度计数发送到r 个节点。

（4）r 个节点把相同项集的计数累加起来，产生最后的实际支持度，与最小支持度计数min_sup比较，确定局部频繁 k 项集的集合 。

（5）把 r 个节点的输出合并即产生全局频繁 k 项集的集合Lk。

（6）改进的Apriori算法的优势是查找Lk和Lk+1的过程是完全独立的，他们之间没有联系，这是一个循环的过程。k 值从1开始递增，直到找出所有的频繁项集。也可以设定k 的值，只需要查找Lk，或是从L1到Lk之间的所有频繁项集。

将改进的Apriori算法用MapReduce实现的优势是：第一，对事务数据库的扫描次数减少；第二，查找频繁项集的过程可以并行执行，当查找频繁k项集的流程执行的中间结果都被传送到分配了Reduce任务的工作站点时，Master就可以调度分配了Map任务的工作站点开始查找频繁 k +1项集，加快并行处理速度，极大地提高执行效率。

2第二种改进

上述改进算法尽管执行效率比较高，但仍然需要对事务数据库进行多次扫描，生成频繁 1 项集到频繁k 项集需要扫描k 次事务数据库，耗费了大量时间。所以对 Apriori 算法再次改进，改进后的算法只需要扫描事务数据库一遍，就可以产生全部的频繁项集，依然是用在云计算平台上。具体的改进思路如下：

（1）把事务数据库水平均匀的分成规模相当的n个数据子集，把数据子集发送到m个节点。

（2）每个节点扫描它的数据子集，产生一个候选项集（候选1项集到候选k项集）的集合，记作Cp，每个候选项集的支持度计数为1。

（3） r个节点把相同项集的计数累加起来，产生最后的实际支持度，与最小支持度计数min_sup比较，确定局部频繁项集的集合Lp。

（4）把r个节点的输出合并即产生全局频繁项集的集合L。

改进的Apriori算法的优势是只需要扫描一遍事务数据库就能找到所有的频繁项集。

小结：Google 的 MapReduce 库把输入文件平均分成 N 个数据片段，然后均匀的分配给 M个节点，由于云计算环境下的集群系统是异构的，所以这种方法并不能充分地利用集群中的计算资源，本文针对云计算环境的并行计算条件和并行挖掘需求在数据集划分和数据集分配方面做了研究。并且，本文对 Apriori 算法进行了两种改进，使其在云计算环境下能够并行进行海量数据的频繁项集的挖掘。

参考文献：

[1] 王鹏. 云计算的关键技术与应用实例[M]. 北京： 人民邮电出版社，2010.1，74-75.

[2] 刘鹏.云计算[M]. 北京：电子工业出版社 2010.3，149-150.

作者简介：许伟（1979-）男，河南灵宝人，武汉科技大学硕士研究生，河南职业技术学院，讲师，研究方向：数据挖掘，计算机网络与模式识别；于莉莉（1980-），女，河北秦皇岛人，河北师范大学本科，石家庄信息工程职业学院软件工程系教师，讲师。研究方向：软件开发。