多种关联规则挖掘算法研究与分析.docVIP

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