基于数据挖掘的关联规则挖掘并行算法

龚浩

摘要：数据挖掘是人工智能和数据库领域研究的热点问题。数据挖掘是指从数据库中大量数据中隐藏出来的，揭示出之前未知价值的信息的非正常过程，数据挖掘是一种决策支持过程，主要以人工智能基础、机械学习、模式、统计学、数据库可视化、技术等为高度帮助自动化地挖掘出分析企业资料的归纳推理的潜在模式，减少决策者调整市场战略、风险，是正确的决策。数据挖掘是通过各数据分析，从大量数据中找出其法则的技术，主要有数据准备、法则查找和法则标识三个步骤，数据挖掘将从相关数据源中提取需要的数据，并整合到数据挖掘所用的数据集。寻找法则通过某种方法找出数据集中包含的法则。法则标示是尽可能通过使用者可理解的方式（例如可视化）来找到的法则。数据挖掘的任务是相关分析、分类分析、理想分析、特别集团分析及变迁分析等。

关键词：数据挖掘;关联规则挖掘;并行算法;分析

1 关联规则挖掘并行算法及问题说明

1.1简介

Apriori算法是常用的用于挖掘出数据关联规则的算法，它用来找出数据值中频繁出现的数据集合，找出这些集合的模式有助于我们做一些决策。比如在常关联规则挖掘的目的是找出事物之间的隐藏的关系，比如经典的案例啤酒和尿布的的故事，通过对购物数据进行数据分析和挖掘，得到这样一个结论，男性在买尿布的时候会买几瓶啤酒。这二者并没有什么因果关系，然而通过对海量数据进行关联分析，却能够发现这个有趣且有价值的关联现象，通过对货物的调整，就可以明显的提升了超市啤酒和尿布的销量。

关联规则的挖掘一般分为两步：一是从现有的数据库中找到所有的频繁项集，二是由频繁项集产生强关联规则。Apriori算法是常用的用于挖掘出数据关联规则的算法，它用来找出数据值中频繁出现的数据集合，找出这些集合的模式有助于我们做一些决策。比如在常见的超市购物数据集，或者电商的网购数据集中，如果我们找到了频繁出现的数据集，那么对于超市，我们可以优化产品的位置摆放，对于电商，我们可以优化商品所在的仓库位置，达到节约成本，增加经济效益的目的。

随着互联网时代的深入发展，物联网时代的来临，生活中的数据以指数级增长，当我们对这些数据进行分析时，常用的串行算法无疑会消耗大量的时间，而且很可能得不到较好的结果。因此，并行计算概念的提出让海量数据的处理成为了可能。如何对原有的传统的串行关联规则算法进行并行化，成了我们需要解决的一个重要问题。

1.2相关工作

并行计算经过多年的发展，其相关实际应用也已经在多个领域起到十分重要作用。传统的串联关联规则算法面对日益指数增长的数据，其数据处理也变得十分困难。因为Apriori算法存在着大量的迭代，I/O负载很高，时间效率很低，因此在如今的大数据时代，利用并行化技术加以改进，是很多人研究的方向。

许德心的研究方向，是Apriori算法的改进及其在Spark平台上的并行化方案，并且将并行化的Apriori算法应用于医疗诊断场景中。他首先分析了大数据的相关技术、关联规则算法、Hadoop计算框架、Spark计算框架。然后选择被广泛使用的Apriori算法加以改进，他创新性的引入了兴趣度，排除无价值的强关联规则，提高了准确性，其改进算法在基于Spark平台的分布式并行方案来提高效率。再搭建Spark平台群环境，测试了Apriori算法和他改进的算法在单机环境与集群环境下的实验，比较出了两种算法的差异性，以及改进算法在不同数据量下的处理速度和准确性。最后，将算法应用到医疗辅助场景中。

程阳的研究方向是，基于Hadoop大数据平台对传统的关联规则算法进行并行化。其主要工作是利用Hadoop生态系统对Apriori算法和Fp-Growth算法进行改进，最后实现并行化目标，有效的解决了传统算法中存在的缺陷，提高运行的效率。他先对Hadoop生态进行深入的研究和分析，然后分析了传统算法存在的问题，针对这些问题，在基于Hadoop的生态环境下提出新的改进算法。并对FP-Growth算法提出了两种改进策略——合并剪枝和动态分组策略，设计并实现了算法的并行化。最后在搭建的Hadoop集群环境中进行试验对比，通过实验验证了改进的Apriori算法在处理数据时的高效性，验证了改进的FP-Growth算法在处理海量数据时的独特优势。

王永贵，谢楠，曲海诚三人的研究方向是，针对现有算法存储结构简单，生成大量冗余的候选集，时间和空间复杂度高，挖掘效率不理想的情况，为了进一步提高关联规则算法挖掘频繁集的速度，优化算法的执行性能，提出基于内存结构改进的关联规则挖掘算法。其算法是基于Spark分布式框架，分区并行挖掘出频繁集，提出在挖掘过程中利用布隆过滤器进行项目存储，并对事务集和候选集进行精简化操作，进而达到加快挖掘频繁集的速度，节省计算资源的目的。算法在占用较少内存的条件下，相比于YAFIM和MR-Apriori算法，在挖掘频繁集效率上有明显的提升，不但能较好地提升挖掘速度，降低内存的压力，而且具有很好的可扩展性，使得算法可以應用到更大规模的数据集和集群，从而达到优化算法性能的目的。

王诚，赵申屹的研究方向是，针对传统的基于频繁模式增长的并行关联规则算法，消耗了大量时间和存储空间，且没有充分考虑头表分组过程中组间负载量不同的问题。为了解决在关联规则的实际挖掘过程中，数据集快速增长所造成的增量更新问题，基于并行频繁模式增长PFP-tree算法，基于Spark分布式并行处理框架，提出一种改进的并行关联规则增量更新算法。在增量更新过程中，为了减少挖掘时间和存储空间，利用已有挖掘结果对新增数据集构建频繁模式树。通过改进头表分组策略，实现了并行挖掘节点之间的负载均衡。最后的实验分析表明，相较于传统的关联增量更新算法，该算法是可行的且具备较高的挖掘效率和可扩展性，适用于动态增长的大数据环境。

2总结

当数据集逐渐扩大，并行程序的运行时间增长速度明显小于串行程序，并逐渐接近。

当数据集扩大到一定程度，并行程序的运行效果，会优于串行程序，这充分体现了并行程序的优越性。