关联规则中几种算法的研究

顾　玮

（徐州高等师范学校　徐州　221116）



关联规则中几种算法的研究

顾玮

（徐州高等师范学校徐州221116）

摘要目前，研究人员投入了大量的精力和时间用来研究关联规则挖掘算法，因为算法是关联规则的核心，关联规则中最著名最经典的算法是Apriori算法。随着研究的不断投入，从时间、空间和成本上来考虑，算法的效率在不断的提高，从宽度优先挖掘算法到深度优先挖掘算法，从只挖掘频繁项集到改进的频集算法，关联规则挖掘算法的效率在逐步提高。

关键词数据挖掘关联规则Apriori算法

所谓关联，反映的是一个事件和其他事件之间依赖或关联的知识。在提出了关联规则的挖掘问题之后，对该问题的研究就开始着手，并取得了很大的发展。至目前为止主要的研究方向为：

一、多循环方式挖掘算法

这种算法的核心是“层次算法”。算法的过程如下：先把整个挖掘过程分为若干个层，然后再各个层次进行挖掘，每个层次都挖掘完成后，组合成最后的挖掘结果。典型算法包括Agrawai等人提出的Apriori、AIS算法，Park等人提出的DHP算法，Toivonen提出的FP-growth

二、并行/分布式关联规则挖掘算法

一般在数据挖掘要处理的数据非常巨大的时候采用该算法，随着网络技术飞速发展，数据库的存储模式也逐渐向分布式存储模式发展，因此分布式关联规则算法变得更为重要。其主要算法包括CD、IDD、PDM、FPM和HPA等。

1、增量式更新挖掘算法

这种算法包含两种情况：

（1）数据库中的记录发生变化时，例如进行删除、增加或修改等更新；

（2）在关联规则的度量发生改变时的更新。度量包括支持度、置信度、兴趣度等。例如冯玉才提出的IUAPIUA算法。

2、多层关联规则挖掘算法

这种算法主要是根据概念层的每个抽象层上定义最小支持度闻值的特性，采用多种策略，挖掘多层关联规则。区别于前面基于支持度——可信度的方法。典型的算法包括：Han等提出的ML_T2L1算法，R.Srikant等提出的Cumulate、Stratify算法等等。

3、基于概念格的关联规则的挖掘算法

这种算法在数据挖掘中的应用的非常广泛，当然也取得了非常丰硕的成绩。典型的算法包括：Godin等提出的概念格模型提取蕴含规则的方法；胡可云在Godin算法的基础上，提出了更有效的购物篮分析的关联规则算法等。

4、多值关联规则挖掘算法

将多值属性的值划分为多个区间，每个区间作为一个属性，将类别属性的每一个类别当做一个属性。这种算法是将多值关联规则挖掘问题转化为布尔型关联规则挖掘问题。

5、Apriori算法

关联规则的算法非常多，其中最为经典的算法是Apriori算法，它是挖掘布尔关联规则频繁项目集的算法，这种算法本身有着很多缺陷，因此后来很多学者都对该算法提出了各种改进算法。

Apriori算法是首先寻找给定数据集合中的频繁项集，通过频繁项集生成强关联规则。寻找频繁项集步骤的核心在于，用前一次扫描数据库的结果产生本次扫描候选项目集，这样可以减少候选数据项集的数量，提高搜索的效率。任何频繁项集的所有子集一定是频繁项集是Apriori算法的核心思想。

Apriori算法使用的是一种逐层搜索的迭代方法，即“K-1项集”用于搜索“K项集”；首先找出频繁“1项集”的集合，该集合记作L1。L1用来去寻找频繁“2项集”的集合L2，以此类推，L2又用来寻找频繁“3项集”的集合L3，如此下去，直到不能找到“K项集”。需要注意的是，挖掘每个Lk都需要对整个数据库进行一次扫描。

Apriori算法的描述如下：

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

输出：存在于D中的频繁项集L。

Aprior算法的伪代码如下：

其中，Apriori-gen函数的参数为Lk-1，即所有长度为k-1的频繁项集，结果返回含有k个项目的候选项集Ck。

6、改进的Apriori算法

Apriori算法利用其性质来生成候选项集，大大压缩了频繁集的大小，取得了很好的性能，但还存在以下缺点：

（1）可能产生大量的候选集。迭代过程在内存中产生、处理和保存候选频繁项集，因此会产生非常大的数据，导致算法在广度和深度上的适应性很差。

（2）数据库扫描的次数太多。A每次寻找k频繁项目及时，都需要对数据库进行一次扫描，用来获得候选项目集的支持度，一最大频繁项集的长度为N时，共需要扫描N次数据库，耗费的时间太长，在实际应用中经常需要挖掘很长的模式，多次扫描数据库带来巨大开销。

7、基于划分的Apriori算法

为了提高该算法的挖掘效果，本文提出了一种改进的算法——基于划分的Apriori改进算法。共分为四个主要部分：

第一部分，对数据库进行划分，划分成n个规模大小相当的区段。

第二部分，对这n个区段进行单独计算，产生n个区域性的频繁项目集（潜在的）。

第三部分，根据这些区域性频繁项目集找出整个数据库中真正的频繁项集。

第四部分，在对整个数据库做一次扫描，计算每个候选频繁项目的实际支持度，最后得到所有的频繁项目集。

这种基于划分的Apriori算法在挖掘数据的过程中，只需要扫描两次数据库，在第一次完成数据库扫描时会产生潜在的频繁项集，确保了第二次扫描的实际支持度，而且不会受到数据量增加的影响，它的核心思想是划分多个模块，产生的项目集都是独立的，之后再进行项目集的合并，从而产生面向全局的候选频繁项目集，所以这种基于划分的Apriori算法对数据挖掘的效率有了很大的提高。

8、DHP算法

经典的Apriori算法是一种逐层搜索的迭代方法，要产生频繁项集必须对整个数据库进行一次扫描，结合产生的频繁项集产生下一层候选集。而DHP算法是以Apriori算法为基础，另外加入了哈希表架构，通过利用Hash function过滤非频繁候选集，在对数据库进行扫描，计算出没有过滤的频繁候选集，这样可以减少候选集的数目，更加提高了搜索效率。

9、FP-tree算法

FP-tree算法其实和Apriori算法都是寻找频繁项集的算法，但是FP-tree是不产生候选集而直接生成频繁项集的算法，该算法直接将事务数据库压缩成一棵频繁模式树，通过这棵树可以有效的产生关联规则。其算法思想为：先设定最小支持度的阈值，再利用此阈值进行筛选。假如事务数据库比较庞大，也可以结合基于划分的方法实现。这种算法与Apriori算法相比，只需要对事务数据库进行二次扫描，不会产生大量候选集，在效率上有很大的提高。

随着关联规则挖掘新的算法的提出，问题的定义和问题背景也不相同，关联规则的应用范围，最主要是包括数据库中对数据的判断是不是有价值的，是不是存在可以相互依存的关系。目前的研究主要集中在基本关联规则挖掘、复杂类型关联规则挖掘、针对关联规则评价的研究以及并行挖掘算法和增量挖掘算法等等。

参考文献

［1］陈京民等著.数据仓库与数据挖掘技术［M］.电子工业出版社，2002.8：1-55.

［2］范明，孟小峰.数据挖掘概念与技术［M］.北京：机械工业出版社，2006：26-27，32.

［3］邵峰晶，于忠清.数据挖掘原理与算法［M］.北京：中国水利水电出版社，2003.

［4］曹露燕.叶书建.聚类分析在高校教务系统中的应用研究［J］福建电脑2010（3）.

［5］刘建友.决策树在高校教务管理中的应用［J］中国高新技术企业2008（12）.

［6］陈启买，彭利宁等.基于关联挖掘的课程相关性模式研究［J］华南师范大学学报（自然科学版）2008（1）.

Research on Several Association Rules Algorithm

Gu Wei
（Xuzhou Higher Normal School Xuzhou 221116）

AbstractAt present，the researchers put a lot of effort and time to study the association rule mining algorithm，because the algorithm is the core of association rules，association rules，the most famous classical algorithm is the Apriori algorithm. With the continue to invest in research，from the time，space and cost up to consider，the efficiency of the algorithm in continuous improvement，from the width of the first mining algorithm to the depth first algorithm for mining，from mining frequent item sets to improve the frequency set algorithm，association rules mining algorithm efficiency in the step by step to improve.

keywordsData mining Association rules Apriori algorithm

中图分类号TP311.13

文献标识码A

文章编号160513-7274

作者简介

顾玮，女，1981年生，汉族，徐州高等师范学校教师，硕士研究生，研究数据库，数据挖掘，系统开发。