关联规则挖掘(Association Rule Mining)
- 关联规则挖掘(Association Rule Mining)详解
- 1. 项集 (Itemset) 与 交易数据
- 2. 支持计数 (Support Count, σ) 与支持度 (Support, s)
- 3. 频繁项集 (Frequent Itemset)
- 4. 关联规则 (Association Rule)
- 5. 置信度 (Confidence, c)
- 6. Apriori 算法与计算案例
- 案例2:数据集
- 步骤 1:生成频繁项集
- 计算 1-项集的支持计数
- 计算 2-项集的支持计数
- 计算 3-项集的支持计数
- 步骤 2:生成关联规则
- 规则生成示例
- 最终关联规则
- 7. FP-Growth 算法与计算案例
关联规则挖掘(Association Rule Mining)详解
关联规则挖掘是一种无监督学习方法,旨在从数据中发现项目之间的相关性。关联规则常用于市场篮分析等场景,用来寻找交易中的商品关联,例如“如果顾客买了A,可能还会买B”。下面,我们通过具体的计算案例来阐释关联规则挖掘的各项基本概念。
1. 项集 (Itemset) 与 交易数据
项集 是一组项目的集合,例如 {牛奶, 面包, 尿布}
。在关联规则挖掘中,交易数据通常表示顾客购买的商品清单。我们用以下交易数据来作为示例:
交易 | 项目 |
---|---|
交易 1 | 牛奶, 尿布, 啤酒 |
交易 2 | 牛奶, 面包, 尿布 |
交易 3 | 牛奶, 尿布, 啤酒, 面包 |
交易 4 | 面包, 啤酒 |
交易 5 | 尿布, 啤酒 |
每个交易包含一个或多个项目的组合。关联规则挖掘的目的是找出这些项目组合之间的相关性。
2. 支持计数 (Support Count, σ) 与支持度 (Support, s)
支持计数 是项集在所有交易中出现的次数,用于衡量该项集的普遍性。例如:
- 项集
{牛奶, 尿布}
出现在交易 1、2 和 3 中,因此: σ({牛奶,尿布})=3
支持度 是项集在所有交易中出现的频率,即支持计数除以总交易数,用于衡量项集的流行度。计算公式为:
s = σ ( 项集 ) 总交易数 s= \frac{\sigma(\text{项集})}{\text{总交易数}} s=总交易数σ(项集)
例如,项集 {牛奶, 尿布}
的支持度为:
s ( 牛奶 , 尿布 ) = σ ( { 牛奶 , 尿布 } ) 5 = 3 5 = 0.6 s({牛奶,尿布})= \frac{\sigma(\{牛奶, 尿布\})}{5} = \frac{3}{5} = 0.6 s(牛奶,尿布)=5σ({牛奶,尿布})=53=0.6
这个支持度表示在60%的交易中,顾客同时购买了牛奶和尿布。
3. 频繁项集 (Frequent Itemset)
频繁项集 是支持度达到某一预设阈值的项集。设定一个最低支持度阈值(min_support
)可以过滤掉出现次数较少的项集。假设我们设定 min_support = 0.4
(即项集至少需要出现在 40% 的交易中)。基于这个阈值,我们可以得到:
-
{牛奶, 尿布}
的支持度为 0.6,满足min_support
,因此它是一个频繁项集。 -
{面包, 啤酒}
的支持度为 0.4(2/5),也满足min_support
,因此也是一个频繁项集。
4. 关联规则 (Association Rule)
关联规则 是一种形式为 X→YX的蕴含关系,表示若顾客购买了项集 X,则很可能购买项集 Y。例如,规则 {牛奶, 尿布} → {啤酒}
表示“如果顾客买了牛奶和尿布,那么他们可能还会买啤酒”。
5. 置信度 (Confidence, c)
置信度 用于衡量在包含 X 的交易中,多少比例同时也包含 Y。置信度的计算公式为:
c = σ ( X ∪ Y ) σ ( X ) c= \frac{\sigma(X \cup Y)}{\sigma(X)} c=σ(X)σ(X∪Y)
其中
σ
(
X
∪
Y
)
σ(X∪Y)
σ(X∪Y)表示同时包含 X 和 Y 的交易数。
σ
(
X
)
σ(X)
σ(X) 表示包含 X 的交易数。
以规则 {牛奶, 尿布} → {啤酒}
为例:
- 项集
{牛奶, 尿布, 啤酒}
出现在交易 1 和交易 3 中,所以 σ ( 牛奶 , 尿布 , 啤酒 ) = 2 σ({牛奶,尿布,啤酒})=2 σ(牛奶,尿布,啤酒)=2 - 项集
{牛奶, 尿布}
出现在交易 1、2 和 3 中,所以 σ ( 牛奶 , 尿布 ) = 3 σ({牛奶,尿布})=3 σ(牛奶,尿布)=3
因此,置信度为:
c = σ ( { 牛奶 , 尿布 , 啤酒 } ) σ ( { 牛奶 , 尿布 } ) = 2 3 ≈ 0.67 c = \frac{\sigma(\{牛奶, 尿布, 啤酒\})}{\sigma(\{牛奶, 尿布\})} = \frac{2}{3} \approx 0.67 c=σ({牛奶,尿布})σ({牛奶,尿布,啤酒})=32≈0.67
这个置信度表示,在购买牛奶和尿布的交易中,约 67% 的顾客也购买了啤酒。
6. Apriori 算法与计算案例
Apriori 算法用于高效地生成频繁项集和关联规则。它基于以下原则:
- Apriori 原则:如果一个项集是频繁的,则它的所有子集也必须是频繁的;反之,如果一个项集是不频繁的,那么它的所有超集也不可能是频繁的。这一原则用于减少不必要的项集计算。
Apriori 计算步骤:
- 生成频繁项集:从 1-项集开始逐步生成频繁项集。
- 生成规则:对每个频繁项集生成高置信度的关联规则。
案例: 假设我们设定 min_support = 2
,并使用前面的交易数据。
-
第一步:1-项集:
- 计算每个单项的支持计数:例如,
{牛奶} = 3
,{尿布} = 4
,{啤酒} = 4
,{面包} = 3
。 - 滤除支持度小于
min_support
的项集。
- 计算每个单项的支持计数:例如,
-
第二步:2-项集:
- 对保留的 1-项集进行组合生成 2-项集,并计算支持计数。例如,
{牛奶, 尿布} = 3
,{牛奶, 啤酒} = 2
,{面包, 啤酒} = 2
等。 - 滤除支持度小于
min_support
的项集。
- 对保留的 1-项集进行组合生成 2-项集,并计算支持计数。例如,
案例2:数据集
交易 ID | 项目集 |
---|---|
1 | A, C, D |
2 | B, C, E |
3 | A, B, C, E |
4 | B, E |
步骤 1:生成频繁项集
计算 1-项集的支持计数
计算每个单项的支持计数,要求其支持计数大于或等于 min_support = 2
。
-
{A}
:出现在交易 1 和 3 中,支持计数为 2。 -
{B}
:出现在交易 2、3 和 4 中,支持计数为 3。 -
{C}
:出现在交易 1、2 和 3 中,支持计数为 3。 -
{D}
:出现在交易 1 中,支持计数为 1。 -
{E}
:出现在交易 2、3 和 4 中,支持计数为 3。
频繁 1-项集: 仅保留支持计数大于等于 2 的项集:{A}
, {B}
, {C}
, {E}
。
计算 2-项集的支持计数
接下来,生成所有包含两个元素的组合并计算它们的支持计数。
-
{A, B}
:出现在交易 3 中,支持计数为 1(不满足min_support
)。 -
{A, C}
:出现在交易 1 和 3 中,支持计数为 2。 -
{A, E}
:出现在交易 3 中,支持计数为 1(不满足min_support
)。 -
{B, C}
:出现在交易 2 和 3 中,支持计数为 2。 -
{B, E}
:出现在交易 2、3 和 4 中,支持计数为 3。 -
{C, E}
:出现在交易 2 和 3 中,支持计数为 2。
频繁 2-项集: {A, C}
, {B, C}
, {B, E}
, {C, E}
。
计算 3-项集的支持计数
生成包含三个元素的组合并计算它们的支持计数。
-
{A, B, C}
:出现在交易 3 中,支持计数为 1(不满足min_support
)。 -
{A, B, E}
:出现在交易 3 中,支持计数为 1(不满足min_support
)。 -
{A, C, E}
:出现在交易 3 中,支持计数为 1(不满足min_support
)。 -
{B, C, E}
:出现在交易 2 和 3 中,支持计数为 2。
频繁 3-项集: {B, C, E}
。
步骤 2:生成关联规则
从频繁项集中生成高置信度的关联规则,假设最小置信度为 60%。
规则生成示例
-
从频繁 2-项集
{A, C}
生成规则:- 规则
{A} -> {C}
:置信度 = 支持计数{A, C}
/ 支持计数{A}
= 2 / 2 = 1.0。 - 规则
{C} -> {A}
:置信度 = 支持计数{A, C}
/ 支持计数{C}
= 2 / 3 ≈ 0.67。
规则
{A} -> {C}
和{C} -> {A}
满足最小置信度。 - 规则
-
从频繁 2-项集
{B, C}
生成规则:- 规则
{B} -> {C}
:置信度 = 支持计数{B, C}
/ 支持计数{B}
= 2 / 3 ≈ 0.67。 - 规则
{C} -> {B}
:置信度 = 支持计数{B, C}
/ 支持计数{C}
= 2 / 3 ≈ 0.67。
规则
{B} -> {C}
和{C} -> {B}
满足最小置信度。 - 规则
-
从频繁 2-项集
{B, E}
生成规则:- 规则
{B} -> {E}
:置信度 = 支持计数{B, E}
/ 支持计数{B}
= 3 / 3 = 1.0。 - 规则
{E} -> {B}
:置信度 = 支持计数{B, E}
/ 支持计数{E}
= 3 / 3 = 1.0。
规则
{B} -> {E}
和{E} -> {B}
满足最小置信度。 - 规则
-
从频繁 3-项集
{B, C, E}
生成规则:- 规则
{B, C} -> {E}
:置信度 = 支持计数{B, C, E}
/ 支持计数{B, C}
= 2 / 2 = 1.0。 - 规则
{B, E} -> {C}
:置信度 = 支持计数{B, C, E}
/ 支持计数{B, E}
= 2 / 3 ≈ 0.67。 - 规则
{C, E} -> {B}
:置信度 = 支持计数{B, C, E}
/ 支持计数{C, E}
= 2 / 2 = 1.0。
规则
{B, C} -> {E}
,{B, E} -> {C}
, 和{C, E} -> {B}
满足最小置信度。 - 规则
最终关联规则
以下是满足 min_confidence
的关联规则:
-
{A} -> {C}
,置信度 = 1.0 -
{C} -> {A}
,置信度 ≈ 0.67 -
{B} -> {C}
,置信度 ≈ 0.67 -
{C} -> {B}
,置信度 ≈ 0.67 -
{B} -> {E}
,置信度 = 1.0 -
{E} -> {B}
,置信度 = 1.0 -
{B, C} -> {E}
,置信度 = 1.0 -
{B, E} -> {C}
,置信度 ≈ 0.67 -
{C, E} -> {B}
,置信度 = 1.0
7. FP-Growth 算法与计算案例
FP-Growth 算法是一种改进的频繁项集挖掘方法,能够在无需候选项集的情况下高效地发现频繁项集。FP-Growth 基于一种称为 FP-树 的数据结构。
FP-Growth 计算步骤:
-
构建 FP-树:
- 第一次扫描数据库:统计每个项目的支持度,并按支持度降序排列。
- 第二次扫描数据库:根据降序排列将每个交易中的频繁项组织到 FP-树中。
-
挖掘频繁项集:
- 从 FP-树的底部开始,逐步生成条件模式基,并构建条件 FP-树,直至所有项集挖掘完成。
案例: 假设我们设定 min_support = 2
。
交易 ID | 项目集 |
---|---|
1 | A, C, D |
2 | B, C, E |
3 | A, B, C, E |
4 | B, E |
- 第一步:统计频率并构建项集的支持度降序。
item | 频率 |
---|---|
A | 2 |
B | 3 |
C | 3 |
D | 1 |
E | 3 |
- 第二步:根据降序将交易重新排序,构建 FP-树。例如:
由于D<2所以排序的时候已经删除D了
item | 排序后的item |
---|---|
A, C, D | CA |
B, C, E | CBE (C在B前面,因为上一行先出现的C) |
A, B, C, E | CBEA |
B, E | BE |
figure from usyd
-
挖掘频繁项集:从 FP-树的底部开始构建条件 FP-树,最终得到频繁项集
{尿布, 啤酒}
,{尿布, 牛奶}
, 等
item | condition pattern base |
---|---|
A | C:1, EBC:1 |
E | B:1, BC:2 |
B | C:2, {} |
C | {} |
最后根据条件状态得到所有频繁项集
A: {(C:2)} -> CA
E: BC:2, B:3, C:3 -> BCE, BE, CE
B: C:2 -> CB
所有频繁项集为{A,B,C,E,CA,CB,CE,BE,BCE}