数据挖掘中关联规则的频繁项集研究.pdf

孙金鑫

文章编号： 2095-2163（2018）03-0132-04中图分类号： 文献标志码： A

摘要： 关键词： （School of Computer Science and Technology， Donghua University， Shanghai 201620， China）

Abstract： In the last century， the rise of data mining technology helped the researchers to extract valuable information from a large amount of data. Agrawal et al. proposed association rule mining techniques in the 1990s to find relevant information in a large amount of data. After these two decades of development， association rules have become a very important and relatively mature method in data mining. This article outlines the application of association rules in data mining， discusses the existing classical algorithms in association rules， and summarizes the advantages and disadvantages of these algorithms. Based on the above， the paper further optimizes the FP-Growth algorithm.

Key words：

作者简介：

收稿日期： 引言

互联网时代，在查询某个记录时经常使用数据库管理系统，用网络搜索引擎来检索特定的网页。在这个过程中，大量使用了计算机科学技术中的数据结构和逻辑精深的算法来创建索引结构，用以管控信息的组织与查询，而这类方法只能在特定环境之下得以实现。随着社会的不断进步，计算机信息技术的飞速发展，数据量呈现指数级的增长，就使得数据库的规模也处于持续的攀升中。在此基础上，则需要研发更加复杂和更有效率的算法来将这些数据转换成有价值的信息，而这也将耗费数目可观的计算成本。为应对这一需求，数据挖掘技术也得到了迅速发展，目前已广泛地应用于数据分析领域中，其目的是从大量的数据中挖掘隐藏的、潜在的、有价值的模式或规则以对企业工程的决策提供有效依据。从信息技术的角度来看，数据挖掘技术及其相应算法是伴随着数据仓库技术的日趋成熟而逐步完善起来的。正是数据挖掘技术的渗透作用，增强了信息检索系统的能力[1]，具有广阔前景。因而，本文将对这一内容展开深入探索研究。

1数据挖掘简述

数据挖掘（Data Mining，DM），又可称为数据库知识发现（Knowledge Discover in Database，KDD），是一种新型的数据处理技术，综合涵盖了诸如数据库技术、统计学、机器学习、分布式和并行计算等众多学科领域内容[2]。这是从研究数据库的大量的、不完全的、模糊的、随机的、有噪音的（包括错误或偏离期望的异常值）数据中，运算得出人们感兴趣的有用信息及模式。例如预测作用，能够高度自动化分析原有的数据，并发现数据之间的潜在联系，再以此为基础，归纳挖掘得到未来可能会发生的行为。研究者们在知识发现的模式中，透过微观看宏观，会揭示大量数据项集存在的有价值的关联关系。这些知识蕴含着普遍意义上的更高层次的价值。正是数据挖掘的长足发展，使得数据库技术向更高层次推进，即对现实科研产生了价值高端、且意义深远的作用与影响。

2关联规则算法研究

关联规则挖掘研究成为数据挖掘中的一个探讨热点，并已陆续应用于市场营销、事务分析等重要领域[3]。关联规则中的算法研究就是当前的目标核心方向，而且也相继提出了许多高效的关联规则挖掘算法。大量的研究表明，关联规则的主要任务就是找出满足预先指定的频率和精度标准的所有规则，但是由于频繁集数量与变量数、以及数据多少是指数型的关系，这就在无形中增加了研究难度。但是在实际的数据集下，频繁集数量都会较小，这就又显著提升了研究的可行性。关联规则的典型算法主要包括：Apriori算法、AprioriTid算法、DLG算法和FP-Growth算法。下面将逐一阐释论述各算法的研究工作。

2.1Apriori算法

Apriori算法是一种基于关联规则频繁项集的算法，最早提出，同时也占据了标志性地位。后续的众多挖掘算法都是在 Apriori 算法基础上引入改进，并将其作为基准来对比评估算法自身性能。Apriori算法是一种逐层搜索的迭代方法，k项集用于搜索（k+1）项集。首先，通过扫描事务集，找出所有的频繁一项集，该集合记做L1，然后利用L1找频繁二项集的集合 L2，L2用于找L3，如此循环下去，直至不能再找到任何频繁k项集，最后在所有的频繁集中推出强规则。在此算法中常出现频繁项集的概念。项集是项目的集合，包括k个项目的集合记为： k-项集。研究中，包含项集的事务数可称为项集的频率、支持计数或计数。如果项集满足最小支持度，则称为频繁项集。Apriori的算法流程如圖1所示。

但是Apriori算法在执行的过程中，需要对数据库设计部署频繁的扫描，如果设置了最小支持度和置信度之后，所生成的频繁项集最大限度是K，那么就要对数据库展开K次扫描，这样就会增加扫描时间，从而影响工作效率。对于这些问题，迄今已发表了许多优化的方法，诸如：数据库逻辑分割的优化、哈希表技术的优化、基于事务压缩技术的优化和采样技术的优化等。但是如何将这些方法进行有效融合以提高算法效率却仍有待进一步的研究。

2.2AprioriTid算法

AprioriTid是一种宽度优先搜索算法，这是建立在前期研发算法Apriori的基础上，对Apriori算法的改进在于：Apriori算法每次迭代都是扫描原始数据集来计算支持度，而AprioriTid是通过以k阶生成的Tid表来达到这一目的。Tid表没有直接存储事务，存储的是每个事务中包含的k维候选项目集，其作用是用来判断k维候选项目集能否成为k维频繁项目集，如此循环下去。简单说来，AprioriTid算法和Apriori算法的根本性差别就表现在，算法中用于产生候选项目集支持度计数的数据结构不同，从而导致了该算法的性能也得到了显著提升。但是AprioriTid 算法却也暴露出一定程度上的不足之处。当数据量庞大时，此算法也将会带来巨大的时间和空间复杂度。

2.3DLG算法

DLG（Direct Large Itemset Generation） 算法是Yen等人研发提出的基于图的关联规则挖掘算法[4]。该算法的实现步骤是：先扫描数据事务库，生成一阶的频繁项目集和图的位向量，然后再生成二阶频繁项目集并生成关联图，最后通过扩展生成k-1阶频繁项集。该算法的缺点是生成的候选频繁项目集比较大，且会造成计算时间的严重浪费。

2.4FP-Growth算法

FP-Growth算法是一种基于频繁项目集的挖掘算法[5]。算法原理是事务数据库压缩到构建的FP-Tree模式树中。该算法需要对数据事务库进行2次扫描，这也是和Apriori算法呈现重点区别的地方。整个挖掘过程都不会产生候选项目集，都是以FP-Tree的方式在内存中设定表示。也因如此，目前已可见到许多优化的改进算法，相对优化的是文献[6]给出了基于事务项矩阵的FP-Growth改进算法MFP-Growth。这一算法主要是利用矩阵来存储事务库中的事务，过程中只需要扫描一次事务库，再通过构造频繁项集的条件矩阵来实现频繁项集的挖掘。该算法减少了算法的内存空间，从而大幅提高了运行效率。

3FP-Growth算法的优化

3.1优化算法研究

在FP-tree构建生成后，可以着手挖掘FP-tree以找到完整的频繁项集合。算法中，FP-Growth函数的输入数据：在第一次调用时，Tree是指原始的FP-tree，递归调用时便是某个模式的条件FP-tree；在第一次调用函数时，a是null，此后递归调用时，a代表模式的后缀。FP-Growth函数的输出结果：输出所有的模式和支持度。这里，研究将给出FP-Growth算法的执行伪代码可见如下。

输入由表4（见后文）构造的FP-tree表示的数据和后缀模式a。

输出所有的频繁项集

方法调用FP-Growth（FP-tree，null）

FP-Growth（tree，a）{

If tree含单个路径P{

For（路径P中结点的每个组合（记作b））{{

产生模式b∪a，其支持度support=b中结点的最小支持度；

}

}else{

for（每个ai在tree的头部（按照支持度由低到高顺序进行扫描））{

产生一个模式b=ai∪a，其支持度support=ai.support；

构造b的条件模式基，然后构造b的条件FP-tree b；

If（tree b不为空）调用FP-Growth（tree b，b）；

}

}}}

综合上述分析可知，FP-Growth算法是在整个事务数据库基础上构建模式树，占用内存较大，当亟待挖掘的数据量较大、或约束条件严格时，算法运行效率偏低，严重影响了数据挖掘的时效性。为此在延承 FP-Growth 算法长足优势的前提下，本文提出了优化方法。本次设计方法中，首先对事务数据库进行遍历，得到所有事务项中项的支持度计数，根据最小支持度的预设条件可将支持度计数不满足预设条件的项删除，得到频繁 1-项集。依照频繁1-项集中各项支持度计数重新排列事务数据库中的项，并删除支持度不符合条件的事务项；然后，利用频繁1-项集研发构造各项的数据库子集，再对各子集运用FP-Growth 算法进行频繁项集的挖掘，得到各项的频繁项集，最后将所有得到的频繁项集予以合并，即为整个事物数据库的频繁项集。

3.2算法设计实例

假如现有事务数据库，库中事项可见表1。

3.3算法优化设计

输入事务数据库T； 最小支持度阈值min_sup

输出事务数据库 T 的频繁项集

算法优化过程可详述如下：

（1）遍历事务数据库T，找出所有候选1-项集，计算各项的支持度计数，将支持度计数小于预设条件最小支持度的项删除，得到频繁1-项集的集合 H。设 H={J1，J2，…，Jn}。其中， J1是支持度最大的，Jn是支持度最小的。

（2）再次遍历事务数据库 T ，将支持度计数小于最小支持度的项从各事务数据库中删除，对事务数据库中的项按照支持度计数从大到小进行重新排列，得到新的事务数据库为 T'。

（3）遍历事务数据库T'，找出包含项 Ji的所有事务项，将支持度小于该事务项支持度的项删除，得到的事务项集合就是项 Ji的数据库子集 Ti。

（4）再利用FP-Growth 算法对数据库子集Ti进行频繁项集挖掘。

以某年某月的销售数據预处理后1 000条数据为例。假设最小支持度为40%，在相同的硬件和软件环境下，采用FP- Growth算法得到频繁1-项集34项、频繁2-项集26项、频繁3-项集18项、频繁4-项集12项、无频繁5-项集。采用优化FP- Growth算法得到频繁1-项集34项、频繁2-项集26项、频繁3-项集18项、频繁4-项集12项、无频繁5-项集。2种方法得到的频繁项集的内容相同。改变样本数据的数据量，2种算法在时间上的对比结果如图3所示。

进一步研究可知，随着数据库中属性项数和记录数的不断增加，优化FP-Growth算法在时间及空间上运行效果将更加突出，算法优越性也越发明显。

4结束语

本文首先对关联规则挖掘进行了研究，主要包括关联规则挖掘的相关概念定义以及挖掘过程，对现有的数据分析方法给出了技术进展的研究成果综述，而且又着重于对关联规则挖掘的4种经典算法展开了详尽的阐释研究，通过对关联规则现有主流算法的深入探讨剖析，总结出每种算法的优势与劣势，进而设计提出一种FP-Growth的优化方式。

参考文献

[1] 杨泽民. 数据挖掘中关联规则算法的研究 [J]. 軟件，2013，34（11）：71-72.

[2] 段玉琴. 数据挖掘中关联规则算法的研究 [D]. 西安：西安电子科技大学，2011.

[3] 高杰，李绍军，钱峰. 挖掘关联规则中AprioriTid 算法的改进[J]. 计算机工程与应用，2007， 43（7）：188-190，197.

[4] 陈明，史忠植，王文杰. 一种有效的基于图的关联规则挖掘算法[J]. 计算机应用，2006， 26（11）：2654-2656.

[5] HAN Jiawei， PEI Jian， YIN Yiwen. Mining frequent patterns without candidate generation[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data. Dallas， Texas， USA：ACM Press， 2000：1-12.

[6] 段西强，乔赛. 一种基于事务-项矩阵的改进FP-Growth算法[J]. 泰山学院学报，2012， 34（6）：50-52.

[7] 俞燕燕，李绍滋. 基于散列的关联规则AprioriTid改进算法[J]. 计算机工程，2008， 34（5）： 60-62.

[8] 袁玉波，杨传胜，黄廷祝，等. 数据挖掘与最优化技术及其应用 [M]. 北京：科学出版社，2007.

[9] 陈耿，朱玉全，杨鹤标，等. 关联规则挖掘中若干关键技术的研究[J]. 计算机研究与发展，2005， 42（10）：1785-1789.