关联规则挖掘综述
摘 要：近年来国内外学者对关联规则进行了大量的
研究。为了更好地了解关联规则的挖掘技术，对研究现状有 更深入的了解，首先本文对数据挖掘技术进行了介绍，接着 介绍了关联数据挖掘的基本原理，最后对经典的挖掘算法进 行分类介绍。
关键词：数据挖掘；关联规则；算法；综述
1. 引言
数据挖掘是从海量的数据里寻找有价值的信息和数据。
数据挖掘中常用的算法 [1] 有：关联规则分析法（解决事件之 间的关联问题） 、决策树分类法（对数据和信息进行归纳和 分类）、遗传算法（基于生物进化论及分子遗传学理论提出 的）、神经网络算法（模拟人的神经元功能）等。
数据挖掘最早使用的方法是关联分析，主要应用于零售
业。其中最有名的是售货篮分析， 帮助售货商制定销售策略。
随着信息时代的到来， 数据挖掘在金融 [2] 、医疗 [3] 、通信 [4]
等方面得到了广泛的应用。
2. 关联规则基本原理
设项的集合 I = { I1 ，I2 ，...，Im }，数据库事务的集合
为 D ，我们用 |D| 表示事务数据库所有事务的个数，其中用 T
表示每个事务，使得 T I。我们用TID作为每个事务的唯一标
识符。用X表示一个项集，满足 X T那么交易T包含X。根
据上述相关描述，给出关联规则的相关定义。 2.1 项集支持度 用 X 表示数据库事务 D 中的项集， 项集 X 的支持度表示
项集X在D中事务数所占的比例，用概率 P (X)表示，那么
Support ( X) =P( X) =COUNT( X) /|D| ( 1)
2.2 关联规则置信度
X丫关联规则的置信度是数据库事务 D中包含X丫的事务
数与包含X的事务数之比，表示方法如下:
confidence( X Y)= support( X Y)/support( X) = P(Y|X)
3. 关联规则算法
3.1 经典的 Apriori 挖掘算法 大多数关联规则的算法是将关联规则挖掘任务分为两
个子任务完成。一是频繁项集的产生，频繁项集的目的是找 到大于等于给定的最小支持度阈值的所有项集，这些项集我 们称之为频繁项集。二是规则的产生，即从频繁项集中找到 置信度比较高的规则，我们称之为强规则。
Apriori 挖掘算法 是众多挖掘关联规则中比较经典的算法，它采用布尔关联规 则，是一种宽度优先算法。
3.2Apriori 算法优化 Apriori 算法的思想是每产生一次候选集就需要扫描一次
数据库，但是当数据库中的数据庞大，无法直接完全放于内
负担。可见当数据信息大的时候，算法效率低下，同时也消 耗的大量的内容。
3.2.1 哈希表技术（散列项集到对应的桶中）
Park等提出了一种基于散列的产生频繁项集的高效算法
DHP算法。即将产生的所有的候选 k-项集（k>1 ）散列到哈
术可以有效减少候选 k-项集（k>1）所占用的空间，进而提
高了 Apriori 算法的效率。
3.2.2 划分技术（为寻找候选项集划分数据）
Savasere等提出了一个基于数据划分的算法，即将数据
库中的记录划分成几个互不相交的块，各块可以高度并行执 行，由最小支持度得到每块中对应的最小支持度。第一次扫 描数据库，得到各块的频繁项集，即局部频繁项集。当算法 进行数据库的第二次扫描时，需得到每个候选项集的支持数， 进而得到全局频繁项集的值。
3.2.3 事务压缩技术 （即压缩未来迭代扫描的事务数据） 该技术用于压缩迭代扫描数据库的大小，即将不包含任
何k-项集的事务肯定不包含任何（k+l）-项集，这种事务在 以后考虑时，可以加上标记或者删除项集，因为产生 j 项集 存中，扫描过程中数据需要不断的换入换出，加重了 I/O 的
希表结构对应的桶中并增加对应的桶计数， 利用哈希表技 （j>k）时不再需要从数据库加上它们进行扫描，如此就可以
减小需要扫描的数据库的规模，从而在一定程度上提高算法 的效率。
3.2.4 连续关联规则算法
C. Hidber提出了一种新型的名为 CARMA（连续关联规则
的算法挖掘算法）算法，该算法用来在线计算大项集。随着
每个项集的支持区间的减少不断产生大项集。他已证明：当
近所有大项集的超集。 CARMA的内存效率比 Apriori是一个
数量级的提高。当支持度阈值比较低时， Apriori 和 DIC 落后
CARMA,此外，CARMA的内存使用效率是两者的六
3.3 基于频繁模式树的算法 FP-growth
由Zaki提出的Eclat算法被认为是产生频繁项集的深度
优先方式的原型。在这以后不同深度优先算法被提出，其中
由韩家炜等提出的FP-growth算法是最著名和最广泛使用的。
法首先两次扫描事务数据库，得到频繁项目集的支持度，然
后将它们降序排序，并且存储到 FP-Tree中。在以后寻找频
繁项目集的过程中，不需要再对事务数据库进行遍历，只需 要在FP-Tree中寻找新的频繁项目集即可。
3.4 并行算法 随着高性能多核处理器的出现，学者们开始借助并行系 相应的支持区间的规模快速减少时， CARMA的项集数迅速接
倍以上。
韩家炜等人提出了基于频繁模式树（ FP-Tree）的算法。该算
作的基础上，Yanbin Ye等实现了并行 Apriori算法，并分析并
行计算的性能， 分割事务数据库的每个分区执行 Apriori 算法。
3.5 其它关联规则算法
Mohammed J. Zaki等提出了 CHARM(闭关联规则挖掘),
它在优势主要体现在挖掘所有频繁闭项集。 Hua-Fu Li等提出
据流挖掘频繁项集)，。Jian Pei等提出了 H-mine频繁模式挖
掘算法。
3.6 关联规则的评估
3.6.1 基于兴趣度约束的关联规则挖掘算法
Silberschatz.A等提出了可执行规则的概念，并统一了关
联规则挖掘过程中主客观评价标准。 Srikant R提出了基于项
Padmanabhan 等提出了一种发现未知模式的置信驱动方法， 在挖掘过程中考虑到与置信评判的结合，从而使挖掘出的关 联规则更加有效。
3.6.2 加权关联规则挖掘算法
Cai等提出了基于K-支持期望的加权关联规则挖掘算法
模型：MINWAL ( 0)模型和 MINWAL (W)模型。张文献等
采用权重集归一化的思想对 Cai给出的算法做了改进。 Wei
Wang 等［5］提出了一个挖掘加权关联规则的方法，其方法不
仅缩短了平均执行时间，但也比已知的方法产生高质量的关 联规则。 统的强大运算能力，将并行算法引入到研究中 。在 Bodon 工
了就是通过整个历史数据流挖掘所有频繁项集的 DSM-F(I 数
目约束的关联规则挖掘的概念和相应的算法描述。 Balaji 4. 小结
数据挖掘是一门新鲜的学科，有着广阔的应用前景，因
而吸引了众多的学者对它进行研究，其中关联规则是其中应 用最早也是很重要的一个领域。关联规则的挖掘受到越来越 多的企业和研究者们的重视，算法模型的建立、算法效率的 提高、算法的扩展应用、挖掘潜在有趣的规则等具有重大的 理论意义和实用价值。
参考文献
[1] 方骏，方云，肖杰 .数据挖掘的工业标准的现状和展望
[J].计算机应用研究，2004, 4: 8-1。
[2] 余波，朱东华，刘卓君 .加权关联规则挖掘算法在电
子商务中的应用[J].计算机工程与应用，2008，44（ 17）: 128-129.
[3] 刘智，伊卫国，鲁明羽，等 .向量法关联规则挖掘在
冠心病诊断中的应用 J].计算机工程，2010，36（6）： 42-44.
[4] 羡晨静，张维石，刘伟光 .关联规则分析在电信交叉
销售中的应用研究 J].计算机工程与设计， 2008，29（ 22）.
[5]张文献，陆建江.加权布尔关联规则的研究 J].计算机
工程， 2003， 29（9）： 55-57.