关联规则挖掘原理简介

关联规则挖掘的实质是在交易数据集中发现超过用户指定的最小支持度阈值和最小置信度阈值的强关联规则。本节介绍关联规则挖掘的一般性原理。

定义3.17（频繁项集，frequent itemset）：项集出现的频率表示包含项集的交易数，如果项集的出现频率大于或等于最小支持度阈值与交易数据集D中交易总数的乘积，即项集满足最小支持度阈值要求，则该项集是频繁项集；其余称为非频繁项集（infrequent itemset） 。

关联规则的挖掘过程一般分为两个主要步骤：

第一步：所有频繁项集的生成；

第二步：由频繁项集到关联规则的生成。

其中第一步“频繁项集的生成”是最关键的。

Apriori算法［1］是较早提出的频繁项集挖掘算法，算法的特点是生成候选项集（candidate itemset），再由候选项集生成频繁项集，但大量候选项集的生成以及多遍数据库扫描，导致算法效率较低。随之出现不少优化方法，如划分、采样、哈希、事务压缩、动态项集计数等，但候选项集的生成仍是该算法本质上难以克服的瓶颈。

FP-Growth算法［2］是一个具有更好性能和伸缩性的频繁项集挖掘算法，其特点是不需要生成大量的候选项集。算法将数据库压缩到一棵频繁模式树中，之后的挖掘就在这棵相对于原始数据库要小很多的树上进行，避免了扫描庞大的数据库，比Apriori算法有明显的性能提升。

第二个步骤相对来说比较简单，假设已完成第一步，找出所有频繁项集，下面看看如何由这些频繁项集生成关联规则。

已经知道，关联规则（XY）置信度计算方法：

confidence（XY） = P（Y|X）= support_count（X∪Y） / support_count（X）

其中support_count （X∪Y）是包含项集X∪Y的交易数，support_count（ X）是包含项集X的交易数。

下面是由频繁项集生成关联规则的步骤：

（1）对于每个频繁项集FI，找出FI的所有非空子集。

（2）对于FI的每个非空子集SFI :

如果support_count（FI ）/support_count（ SFI）≥ min_conf，则输出规则“SFI（FI—SFI）”。

由于规则由频繁项集产生，所以每个规则都自动满足最小支持度阈值。(www.xing528.com)

下面给出一个由频繁项集生成关联规则的例子：

例3.4：将交易数据集转换为具有如表3-2格式的交易数据库D。在表3-2中，项集中的项都是以字典顺序排列的，每一条交易T都具有＜T.id，T.I＞的形式，交易号T.id用于唯一标识一次交易行为，交易号对应的项集T.I表示在这次交易行为中所购买的物品集合。

表3-2　交易数据库D

（续表）

假定经过第一步已找出表3-2中的交易数据库D中包含频繁项集FI=｛I1，I2，I5 ｝ ， FI的非空子集有｛I1， I2｝，｛I1， I5｝，｛I2， I5｝，｛I1｝，｛I2｝，｛I5｝，则可能的关联规则有以下一些：I1∧I2I5， I1∧I5I2， I2∧I5I1， I1I2∧I5 ， I2I1∧I5， I5I1∧I2。

验证各个可能关联规则的置信度值：

confidence（I1∧I2I5）=2/4=50%；

confidence（I1∧I5I2）=2/2=100%；

confidence（I2∧I5I1）=2/2=100%；

confidence（I1I2?I5） =2/6=33%；

confidence（ I2I1?I5）=2/7=29%；

confidence（ I5I1?I2）=2/2=100%。

将每个可能的关联规则的置信度与最小置信度阈值（假设为50%为最小置信度阈值）相比较选择大于置信度阈值的关联规则为真正的满足条件的关联规则。得出结论：满足条件的关联规则为如下四个：

再来讨论如何找到这些频繁项集，针对不同类别的关联规则应用不同的挖掘方法，按具体情况实施。下面分别介绍简单关联规则、量化关联规则、多层关联规则和多维关联规则的挖掘原理。