关联规则挖掘算法综述

第３３卷第２期　２０１６年２月　计算机应用研究　Ａｐｐｌｉｃａｔｉｏｎ　Ｒｅｓｅａｒｃｈ　ｏｆ　Ｃｏｍｐｕｔｅｒｓ　Ｖｏ１．３３　Ｎｏ．２　Ｆｅｂ．２０１６　

关联规则挖掘综述　

崔妍，包志强　

（西安邮电大学通信与信息工程学院，西安７１００６１）　

摘要：近年来国内外学者对关联规则进行了大量的研究，为深入理解关联规则挖掘技术，掌握其研究现状与　

发展趋势，首先介绍了关联规则相关定义与分类方法；其次从串行和并行两个角度总结了关联规则挖掘的一般　

方法，概述并分析了一些典型的关联规则挖掘模式；最后讨论了关联规则挖掘质量改善问题及领域应用。　

关键词：数据挖掘；关联规则；频繁项集；算法　

中图分类号：ＴＰ３９１　文献标志码：Ａ　文章编号：１００１—３６９５（２０１６）０２－０３３０－０５　

ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１－３６９５．２０１６．０２．００２　

Ｓｕｒｖｅｙ　ｏｆ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅ　ｍｉｎｉｎｇ　

Ｃｕｉ　Ｙａｎ，Ｂａｏ　Ｚｈｉｑｉａｎｇ　（Ｓｃｈｏｏｌ　ｏｆＣｏｍｍｕｎｉｃａｔｉｏｎ＆Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｘｉ’ａｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆＰｏｓｔｓ＆Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｘｉ’ａｎ　７１００６１，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｉｎ　ｒｅｃｅｎｔ　ｙｅａｒｓ，ｒｅｓｅａｒｃｈｅｒｓ　ａｔ　ｈｏｍｅ　ａｎｄ　ａｂｒｏａｄ　ｈａｖｅ　ｄｏｎｅ　ｍｕｃｈ　ｗｏｒｋ　ｏｎ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅｓ．Ｔｏ　ｆｕｒｔｈｅｒ　ｕｎｄｅｒｓｔａｎｄ　ｔｈｅ　ｔｅｃｈｎｏｌｏｇｙ　ｏｆ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅｓ　ａｎｄ　ｉｔｓ　ｃｕｒｒｅｎｔ　ｒｅｓｅａｒｃｈ　ｓｉｔｕａｔｉｏｎ　ａｎｄ　ｄｅｖｅｌｏｐｍｅｎｔ　ｔｒｅｎｄ，ｔｈｉｓ　ｐａｐｅｒ　ｆｉｒｓｔｌｙ　ｉｎｔｒｏｄｕｃｅｄ　ｔｈｅ　ｄｅｆｉｎｉｔｉｏｎ　ｏｆ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅｓ　ａｎｄ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ｍｅｔｈｏｄｓ．Ｓｅｃｏｎｄｌｙ，ｉｔ　ｃｏｎｃｌｕｄｅｄ　ｔｈｅ　ｇｅｎｅｒａｌ　ｍｅｔｈｏｄｓ　ｏｆ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅ　ｍｉｎｉｎｇ　ｆｒｏｍ　ｔｗｏ　ａｎｇｌｅｓ　ｏｆ　ｓｅｒｉａｌ　ａｎｄ　ｐａｒａｌｌｅｌ，ｏｖｅｒｖｉｅｗｅｄ　ａｎｄ　ａｎＭｙｚｅｄ　ｔｈｅ　ｔｙｐｉｃａｌ　ｐａｔｔｅｒｎｓ　ｏｆ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅ　ｍｉｎｉｎｇ．Ｆｉｎａｌｌｙ，ｉｔ　ｄｉｓ—　ｃｕｓｓｅｄ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅ　ｍｉｎｉｎｇ　ｑｕａｌｉｔｙ　ｉｍｐｒｏｖｅｍｅｎｔｓ　ａｎｄ　ｉｔｓ　ｆｉｅｌｄ　ａｐｐｌｉｃａｔｉｏｎ．　Ｋｅｙ　ｗｏｒｄｓ：ｄａｔａ　ｍｉｎｉｎｇ；ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅｓ；￣ｅｑｕｅｎｔ　ｉｔｅｍｓｅｔｓ；ａｌｇｏｒｉｔｈｍ　

关联规则挖掘的相关算法

1.Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。

该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。

可能产生大量的候选集,以及可能需要重复扫描数据库，是Apriori算法的两大缺点。

2.基于划分的算法这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。该算法是可以高度并行的，可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后，处理器之间进行通信来产生全局的候选k-项集。通常这里的通信过程是算法执行时间的主要瓶颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶颈。

3.FP-树频集算法采用分而治之的策略，在经过第一遍扫描之后，把数据库中的频集压缩进一棵频繁模式树（FP-tree），同时依然保留其中的关联信息，随后再将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关，然后再对这些条件库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法,使得一个FP-tree可以放入主存中。实验表明，FP-growth对不同长度的规则都有很好的适应性，同时在效率上较之Apriori算法有巨大的提高。

关联规则挖掘方法

一、前言

关联规则挖掘是数据挖掘中的一个重要领域，它可以帮助我们发现数据中隐藏的规律和关系，从而为商业决策和市场营销提供支持。本文将介绍关联规则挖掘的方法和步骤，包括数据预处理、频繁项集生成、关联规则生成和评估等。

二、数据预处理

在进行关联规则挖掘之前，我们需要对原始数据进行预处理。首先，我们需要去除无用的属性和记录，并对缺失值进行处理。其次，我们需要将离散型数据转换为数值型数据，并对连续型数据进行离散化。最后，我们需要对异常值进行检测和处理。

三、频繁项集生成

频繁项集是指在数据集中经常出现的一组物品集合。频繁项集生成是关联规则挖掘的第一步，其目的是找到所有满足最小支持度阈值的频繁项集。

1. Apriori算法

Apriori算法是最常用的频繁项集生成算法之一。它基于两个重要性质：单调性和自由子集性质。Apriori算法分为两个阶段：候选项集生成和剪枝。

2. FP-growth算法

FP-growth算法是一种基于树结构的频繁项集生成算法。它通过构建一棵FP树来发现频繁项集。FP-growth算法相对于Apriori算法具有更快的速度和更小的空间复杂度。

四、关联规则生成

在找到所有频繁项集之后，我们需要从中挖掘出有意义的关联规则。关联规则是指形如X->Y的规则，其中X和Y都是物品集合，且X∩Y=∅。

1. 关联规则挖掘

关联规则挖掘是指从频繁项集中挖掘出满足最小置信度阈值的关联规则。置信度是指在条件X下出现Y的概率。

2. 关联规则评估

关联规则评估是指对挖掘出来的关联规则进行评估和选择。常用的评价指标包括支持度、置信度、提升度和全置信度等。

五、总结

本文介绍了关联规则挖掘的方法和步骤，包括数据预处理、频繁项集生成、关联规则生成和评估等。在实际应用中，我们需要根据具体情况选择不同的算法和参数，并进行优化和调整。

关联规则挖掘综述

关联规则挖掘是数据挖掘中的一种重要技术，它可以通过分析数据集中的项之间的关系，发现其中的规律和模式。在实际应用中，关联规则挖掘可以帮助企业和组织发现消费者的购买习惯、市场趋势、产品组合等信息，从而更好地制定营销策略和提高销售额。

关联规则挖掘的基本思想是通过计算支持度和置信度来确定项之间的关联程度。支持度指的是在数据集中同时出现两个或多个项的频率，而置信度则是指在出现一个项的情况下，另一个项出现的概率。通过设定支持度和置信度的阈值，可以筛选出具有一定关联程度的项集，从而发现其中的规律和模式。

关联规则挖掘的算法主要包括Apriori算法、FP-Growth算法和Eclat算法等。其中，Apriori算法是最早被提出的关联规则挖掘算法之一，它通过逐层扫描数据集来生成频繁项集。FP-Growth算法则是一种基于树结构的算法，它通过构建FP树来快速发现频繁项集。Eclat算法则是一种基于垂直数据格式的算法，它通过交换和合并项集来发现频繁项集。

除了基本的关联规则挖掘算法外，还有一些扩展算法和改进算法。例如，基于时间序列的关联规则挖掘算法可以用于分析时间序列数据中的项之间的关系；基于多层次关联规则挖掘算法可以用于分析多个层次之间的关系；基于模糊关联规则挖掘算法可以用于处理数据集中存在模糊关系的情况。

关联规则挖掘在实际应用中有着广泛的应用。例如，在零售业中，可以通过关联规则挖掘来发现消费者的购买习惯和偏好，从而制定更加精准的营销策略；在医疗领域中，可以通过关联规则挖掘来发现疾病之间的关联性，从而更好地预防和治疗疾病；在金融领域中，可以通过关联规则挖掘来发现不同金融产品之间的关系，从而更好地进行风险控制和资产配置。

总之，关联规则挖掘是一种重要的数据挖掘技术，它可以帮助企业和组织发现数据集中的规律和模式，从而更好地制定营销策略和提高业务效率。随着数据量的不断增加和数据挖掘技术的不断发展，关联规则挖掘将在更多的领域中得到广泛的应用。