关联规则挖掘
基本知识
- 关联规则挖掘定义
给定事务的集合 T, 关联规则发现是指找出支持度大于等于 min_sup并且置信度大于等于min_conf的所有规则,min_sup和min_conf是对应的支持度和置信度阈值 - 关联规则挖掘目的
在事务、关系数据库中的项集和对象中发现频繁模式、关联规则、相关性或者因果结构 - 频繁模式:数据库中频繁出现的项集
- 项集(Itemset)
k-项集:包含k个项的集合 - 频繁项集(Frequent Itemset)
满足最小支持度阈值(min_sup)的所有项集 - 支持度计数(Support count)
包含特定项集的事务个数 - 支持度(Support)
包含项集的事务数与总事务数的比值
- 项集(Itemset)
- 关联规则(Association Rule)
关联规则是形如X→ Y 的蕴含表达式,其中X 和Y 是不相交的项集- 关联规则的提取
将一个项集X 划分成两个非空的子集X 和Y−X ,使得X→(Y−X) 满足置信度阈值
- 关联规则的提取
- 支持度 :确定项集的频繁程度
support(X→Y)=P(X∪Y) - 置信度:确定Y在包含X的事务中出现的频繁程度
Confidence(X→Y)=P(Y∣X)=support(X∪Y)support(X)
频繁项集产生(Frequent Itemset Generation)
- Brute-force 方法(蛮力方法)
- 把格结构中每个项集作为候选项集
- 将每个候选项集和每个事务进行比较,确定每个候选项集的支持度计数
- 把所有的k-项集都看作可能的候选,然后使用候选剪枝除去不必要的候选
- 候选产生相当简单的,但候选剪枝的开销极大,时间复杂度高
-
Apriori算法
降低产生频繁项集计算复杂度,先验原理- 如果一个项集是频繁的,则它的所有子集一定也是频繁的(连接时减少)
- 如果一个项集是非频繁的,则它的所有超集也一定是非频繁的(剪纸原则)
- 基于支持度的剪枝(support-based pruning)
由长度为k的频繁项集产生长度为 (k+1) 的候选项集,连接,剪枝 - 支持度度量的反单调性(anti-monotone)
一个项集的支持度决不会超过它的子集的支持度
- 极大频繁项集
- 如果
X 是频繁的,且不存在超项集Y 使得Y⊃X 并且Y 是频繁的,则X 是极大频繁项集 - 有效地提供了频繁项集的紧凑表示,即所有的频繁项集是极大频繁项集的子集,但它不包含子集的支持度信息
- 如果
- 提高Apriori算法的方法
- 散列项集计数(Hash-based itemset counting)
压缩候选k项集 - 事务压缩(Transaction reduction)
不包含任何频繁k项集的事务不可能包含任何频k+1项集。因此这些事务在其后的考虑中,可以加上标记或删除 - 划分(Partitioning)
项集在DB中是频繁的,它必须至少在DB的一个划分中是频繁的(分治的思想) - 采样(Sampling)
选取原数据库的一个样本,使用Apriori 算法在样本中挖掘频繁模式(牺牲一些精度换取有效性)
- 散列项集计数(Hash-based itemset counting)
-
FP增长算法(Frequent-Pattern Growth)
使用一种称作FP树的紧凑数据结构组织数据,并直接从该结构中提取频繁项集- 支持度排序:扫描一次数据集,将频繁项按照支持度的递减排序
- 构建FP树:再次扫描数据集,读入事务,每个事务都映射到FP树的一条路径,并不断更新支持度计数
-
例子1
例子2
条件模式基
一个“子数据库”,由FP树中与该后缀模式一起出现的前缀路径集组成-
将条件模式基看作为事务数据库,构造条件FP树
-
挖掘频繁项集
-
如果条件FP树为单个路径,则产生该路径下所有模式的组合
-
如果条件FP树为多路径,则针对树的头表中的每一个项, 产生对应模式获取频繁模式
-
如果条件FP树为单个路径,则产生该路径下所有模式的组合
- 优缺点
对长和短的模式都是有效且可伸缩的,效率比Apriori算法快了一个数量级;但对内存要求较大, 算法实现相对复杂
关联模式的评估(Pattern Evaluation)
关联分析算法往往产生大量的规则,而其中很大一部分可能是不感兴趣的。建立一组广泛接受的评价关联模式质量的标准是非常重要的。
- 通过统计论据
- 通过主观论据
置信度度量忽略了规则后件中出现的项集的支持度,高置信度的规则有时存在误导- 提升度(lift)
规则置信度和规则后件中项集的支持度之间的比率 - 兴趣因子(interest factor)
- 提升度(lift)