龙源期刊网 http://www.qikan.com.cn
多种关联规则挖掘算法的研究与分析
作者：王金甫
来源：《电脑学习》2011年第01期
摘要： 本文首先介绍关联规则的基本概念，对关联规则算法进行了详细地分析和研究，就目前针对提高该算法效率的各种优
化技术也进行了详细地描述与分析，并说明各改进算法在各商业领域中的应用。 关键词： 数据挖掘； 关联规则； 遗传算法
中图分类号： ＴＰ３１１．１２文献标识码：Ａ 文章编号：１００２－２４２２（２０１１）０１－０００４－０２
Ｒｅｓｅａｒｃｈ ａｎｄ Ａｎａｌｙｓｉｓ ｏｆ Ａ Ｖａｒｉｅｔｙ ｏｆ Ａｓｓｏｃｉａｔｉｏｎ Ｒｕｌｅ Ｍｉｎｉｎｇ Ａｌｇｏｒｉｔｈｍ Ｗａｎｇ Ｊｉｎｆｕ
Ａｂｓｔｒａｃｔ:Ｔｈｅ ｐａｐｅｒ ｆｉｒｓｔ ｉｎｔｒｏｄｕｃｅｓ ｔｈｅ ｂａｓｉｃ ｃｏｎｃｅｐｔｓ ｏｆ ａｓｓｏｃｉａｔｉｏｎ ｒｕｌｅｓ,Ａｓｓｏｃｉａｔｉｏｎ ｒｕｌｅｓ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｄｅｔａｉｌｅｄ ａｎａｌｙｓｉｓ ａ－ ｎｄ ｒｅｓｅａｒｃｈ． Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｉｍｐｒｏｖｉｎｇ ｔｈｅ ｃｕｒｒｅｎｔ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｖａｒｉｏｕｓ ｏｐｔｉｍｉｚａｔｉｏｎ ｔｅｃｈｎｉｑｕｅｓ ｈａｖｅ ａｌｓｏ ｂｅｅｎ ｄｅ－
ｓｃｒｉｂｅｄ ａｎｄ ａｎａｌｙｚｅｄ ｉｎ ｄｅｔａｉｌ,ａｎｄ ｄｅｓｃｒｉｂｅｓ ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｉｎ ａｌｌ ａｒｅａｓ ｏｆ ｂｕｓｉｎｅｓｓ．
Ｋｅｙ ｗｏｒｄｓ:Ｄａｔａ Ｍｉｎｉｎｇ; Ａｓｓｏｃｉａｔｉｏｎ Ｒｕｌｅ;Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ
１ 传统的关联规则挖掘算法 １．１ Ａｐｒｉｏｒｉ算法
龙源期刊网 http://www.qikan.com.cn
Ａｐｒｉｏｒｉ算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。再使用第１步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。
Ａｐｒｉｏｒｉ算法的缺点是扫描事务数据库次数过多、在频繁项长度变大的情况下，运算时间显著增加、不能直接用于关系数据库的关联规则挖掘、不适于海量数据环境下的关联规则挖掘。
１．２ 基于划分的算法
此类算法包括Ａ．Ｓａｖａｓｅｒｅ等人的Ｐａｒｔｉｔｉｏｎ算法[１４?演，Ｓ．Ｂｒｉｎ等人的ＤＩＣ算法[１９?演等。这些算法将整个数据集划分成可以存放在内存中进行处理的数据块，以节省访问外存的Ｉ／Ｏ开销。Ｐａｒｔｉｔｉｏｎ算法只需要对整个数据集进行两次扫描，ＤＩＣ算法在数据块划分恰当时可以通过两次扫描数据集找出所有的频繁项目集。 数据集划分算法的候选项目集的数量一般比Ａｐｒｉｏｒｉ算法的候选项目集的数量大，数据集划分算法是各种并行关联规则挖掘算法和分布式关联规则挖掘算法的基础。该算法是可以高度并行的，可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后，处理器之间进行通信来产生全局的候选ｋ－项集。通常这里的通信过程是算法执行时间的主要瓶颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶颈。 １．３ ＦＰ－树频集算法
频繁项集挖掘算法ＦＰ－ｇｒｏｗｔｈ通过对数据库的两次扫描，将数据信息存到一种压缩的数据结构（ＦＰ－ｔｒｅｅ）里，无须生成候选项目集，显著地缩小了搜索空间，极大地减少了数据模式匹配的开销，有效地避免了产生“知识的组合爆炸”，因此挖掘效率有了很大提高。但是此算法没有充分考虑层次数据的自身特点，在频繁项集查找过程中，仍然包含了大量无用项集的计算。无法根据层次数据的特点来进行关联规则的去冗余，造成了大量的冗余关联规则的产生。
２ 几种关联规则挖掘算法的改进
基于ＦＰ－树频集算法的改进算法，利用层次结构数据的内在特征，采取高效、去冗余的多层关联规则挖掘方法，将是一件非常有意义的工作。采用聚类的方法，对已有的评价关联规则的两个常用客观性指标－支持度和可信度，增加一个相关的业务参数，达到对树的进一步划分，使得频繁项集挖掘时须扫描的数据库变得越来越小，以此提高挖掘效率，以便挖掘出收益较高、值得关注的业务。
龙源期刊网 http://www.qikan.com.cn
基于哈希（ｈａｓｈ）表技术，利用ｈａｓｈ表技术可以帮助有效减少候选ｋ－项集Ｃｋ（ｋ＞１）所占用的空间。例如?押在扫描交易数据库以便从候选１－项集Ｃ１中产生频繁１－项集Ｌ１时，就可以为每个交易记录产生所有的２－项集并将哈希（ｈａｓｈ）到ｈａｓｈ表的不同栏目中，增加相应栏目的技术。如果ｈａｓｈ表中一个存放２－项集的出现频率低于最小支持度，则表示相应２－项集为非频繁项集而被移出候选集。利用ｈａｓｈ表技术可以帮助有效减少需要检查的候选项集数目。
应用遗传算法的思想改进Ａｐｒｉｏｒｉ算法只需扫描一次数据库，通过一次扫描数据库，给定一个映射，把数据库映射成一个矩阵Ｍ，以下所有对数据库Ｄ的扫描均可在Ｍ上运算完成。把求解关联规则最长频繁项集的问题转化到某生物种群对环境的适应性，将优化变量对应生物种群的个体，将所发展的求解优化问题的算法与生物种群的进化过程类比。
改进算法的基本思想:首先要对实际问题进行编码，编码方法可以是二进制编码，也可以是十进制编码。然后，定义遗传算法的适应度函数，根据适应度函数求出频繁１－项集，应用交叉、变异运算对该组项集进行进化，再利用选择运算产生下一代频繁项集，这样经过若干次迭代后，遗传算法满足终止条件，从而得到一组最长频繁项集。 ３ 改进算法分析
３．１ 基于ＦＰ－树频集算法的改进算法
以大型的商业交易为例，每次商业交易都有层次结构树的特征，对整个交易树利用特定的业务参数进行分类，采取自顶向下方式，依次对各层子树进行分类，其中下层分类是在上层分类结果基础上进行的。整个分类过程分为以下几个主要步骤。
步骤１：针对交易树的第ｉ层，考察ｉ－１层的每个分类交易子树如果是第２层，则考察整个交易子树。
步骤２：对于第ｉ－１层中１－项集不是频繁项集的子树，将其从交易数据库中删除且不纳入后续分类。
步骤３：针对第ｉ－１层每棵待分类的每个交易子树，计算所有子树两两之间的业务参数。由于包含这两棵交易子树的２－项集表示的是这两类交易在事务数据库中同时出现的频率，值越大，则这两类交易子树参数相关性程度可能会越高，按每一层上交易子树之间的业务参数相关程度，根据层次连接聚类算法的方法，就可以得到该层上各交易子树之间相互独立的分类，然后依此对上层交易数据库进一步进行划分，使得生成ｋ－项集时须扫描的数据库变得越来越小，以此达到提高生成频繁项集和关联规则的效率。因此该算法适用于大型的金融交易中，比如银行交易，大型企业交易等。
３．２ 应用遗传算法的思想改进Ａｐｒｉｏｒｉ算法