当前位置：首页 > news >正文

数据挖掘——关联规则挖掘

news 来源：原创 2025/5/18 6:00:31

数据挖掘——关联数据挖掘

关联数据挖掘
- 关联规则
- 关联规则挖掘问题：
- 具体挖掘过程
- - Apriori
- 产生关联规则

关联数据挖掘

关联分析用于发现隐藏在大型数据集中的令人感兴趣的联系，所发现的模式通常用关联规则或频繁项集的形式表示。

关联规则反映一个事物与其它事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物发生就能够预测与它相关联的其它事物的发生。
在这里插入图片描述
定义：频繁项集

项集（Itemset）

包含0个或多个项的集合
- 例子：{Milk, Bread, Diaper}
k-项集
- 如果一个项集包含k个项

支持度计数（Supportcount）( $\sigma$ )

包含特定项集的事务个数
例如： $\sigma$ ({Milk,Bread,Diaper}) = 2

支持度（Support）

包含项集的事务数与总事务数的比值
例如： s({Milk,Bread, Diaper}) = 2/5

频繁项集（FrequentItemset）

满足最小支持度阈值（minsup ）的所有项集

频繁闭项集

所谓闭项集，就是指一个项集X，它的直接超集的支持度计数都不等于它本身的支持度计数。如果闭项集同时是频繁的，也就是它的支持度大于等于最小支持度阈值，那它就称为闭频繁项集。

最大频繁项集
最大频繁项集是这样的频繁项集，它的直接超集都不是频繁的
在这里插入图片描述

关联规则

关联规则是形如X →Y的蕴含表达式, 其中 X 和 Y 是不相交的项集

例子：{Milk, Diaper} →{Beer}

关联规则的强度

支持度 Support (s)
确定项集的频繁程度
置信度 Confidence （c）
确定Y在包含X的事务中出现的频繁程度

在这里插入图片描述

关联规则挖掘问题：

给定事务的集合 T, 关联规则发现是指找出支持度大于等于minsup并且置信度大于等于minconf的所有规则, minsup和minconf是对应的支持度和置信度阈值

具体挖掘过程

大多数关联规则挖掘算法通常采用的一种策略是，将关联规则挖掘任务分解为如下两个主要的子任务：

频繁项集产生（Frequent Itemset Generation）
- 其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集。
规则的产生（Rule Generation）
- 其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则（strong rule）。

降低产生频繁项集计算复杂度的方法：

减少候选项集的数量
- 先验原理：(Apriori)
减少比较的次数
- 替代将每个候选项集与每个事务相匹配，可以使用更高级的数据结构，或存储候选项集或压缩数据集，来减少比较次数(FPGrowth)

Apriori

先验原理：

如果一个项集是频繁的，则它的所有子集一定也是频繁的
相反，如果一个项集是非频繁的，则它的所有超集也一定是非频繁的

在这里插入图片描述
需要一提的是Apriori中所运用到的项的连接准则：

项的连接准则：去掉尾项之后如果二者一样则可以连接
例如本例中{A,C},{B,C},{B,E},{C,E}四者，只有{B,C},{B,E}，两者去掉尾项后的B是相等的，所以是可以连接的{B,C,E}

Apriori算法特点：

优点

使用先验性质，大大提高了频繁项集逐层产生的效率
简单易理解；数据集要求低

缺点

多次扫描数据库
候选项规模庞大
计算支持度开销大

Apriori算法需要反复的生成候选项，如果项的数目比较大，候选项的数目将达到组合爆炸式的增长

提高Apriori算法性能的方法：
在这里插入图片描述

产生关联规则

任务描述：给定频繁项集Y, 查找Y的所有非空真子集 $\in Y$ ，使得 $\rightarrow Y –X$ 的置信度超过最小置信度阈值minconf

例子：If {A,B,C} is a frequent itemset, 候选规则如下：
$\rightarrow C\\ A\rightarrow BC\\ AC \rightarrow B\\ B \rightarrow AC\\ BC \rightarrow A\\ C \rightarrow AB$
如果 |Y| = k, 那么会有 2k–2 个候选关联规则 (不包括 $Y→\emptyset、 \empty →Y$ ）

如何高效地从频繁项集中产生关联规则?

通常置信度不满足反单调性（anti-monotone property ），例如：
c(ABC →D) 可能大于也可能小于 c(AB →D)
但是，针对同一个频繁项集的关联规则，如果规则的后件满足子集关系，那么这些规则的置信度间满足反单调性
e.g., ${A,B,C,D}\\ c(ABC → D) \geq c(AB → CD) \geq c(A → BCD)$