关联规则挖掘1：Apriori算法

一、Apriori算法核心原理

1. 基本概念

2. Apriori性质

二、完整案例计算（超市购物数据）

步骤1：按字母序重排每笔交易

步骤2：统计频繁1-项集（min_support=40%）

步骤3：生成候选2-项集

步骤4：生成候选3-项集

步骤5：生成关联规则（min_conf=60%）

（1）从频繁2-项集生成规则

（2）筛选有效规则（Conf≥60%且Lift>1）

（3）最终强关联规则

关键结论

三、Python实现代码

四、算法特性总结

五、面试常见问题

六、例题

题目1

题目2

七、面试题

一、基础概念题

二、流程与实现题

三、优缺点与优化题

四、实战应用题

一、Apriori算法核心原理

1. 基本概念

频繁项集：经常一起出现的物品组合（如{啤酒,尿布}）
支持度(Support)：项集出现的频率

Support(X) = 包含X的交易数 / 总交易数
置信度(Confidence)：规则X→Y的可靠性

Confidence(X→Y) = Support(X∪Y) / Support(X)
提升度(Lift)：X对Y的促进效果

Lift(X→Y) = Support(X∪Y) / (Support(X)*Support(Y))

2. Apriori性质

关键定理：若项集是频繁的，则其所有子集也一定是频繁的

（反之：若子集不频繁，则超集一定不频繁）

二、完整案例计算（超市购物数据）

原始数据（5笔交易）：

商品字母顺序：啤酒(B) < 黄油(H) < 鸡蛋(J) < 面包(M) < 牛奶(N)

交易ID	商品组合
1	牛奶, 面包, 鸡蛋
2	牛奶, 啤酒
3	面包, 黄油
4	牛奶, 面包, 啤酒
5	面包, 黄油

参数设置：最小支持度=40%（至少出现2次），最小置信度=60%

步骤1：按字母序重排每笔交易

交易ID	原始商品组合	排序后商品组合（按B<H<J<M<N）
1	牛奶,面包,鸡蛋	鸡蛋(J), 面包(M), 牛奶(N)
2	牛奶,啤酒	啤酒(B), 牛奶(N)
3	面包,黄油	黄油(H), 面包(M)
4	牛奶,面包,啤酒	啤酒(B), 面包(M), 牛奶(N)
5	面包,黄油	黄油(H), 面包(M)

关键点：字母顺序优先级：B(啤酒) → H(黄油) → J(鸡蛋) → M(面包) → N(牛奶)

步骤2：统计频繁1-项集（min_support=40%）

商品	出现次数	支持度	是否频繁
啤酒	2	2/5=40%	✔
黄油	2	2/5=40%	✔
鸡蛋	1	1/5=20%	✖
面包	4	4/5=80%	✔
牛奶	3	3/5=60%	✔

频繁1-项集：{'啤酒'}, {'黄油'}, {'面包'}, {'牛奶'}

（排除{'鸡蛋'}，因支持度20% < 40%）

步骤3：生成候选2-项集

连接频繁1-项集（按字母序组合）：

候选2-项集	出现交易ID	支持度	是否频繁
{啤酒,黄油}	无	0%	✖
{啤酒,面包}	4	1/5=20%	✖
{啤酒,牛奶}	2,4	2/5=40%	✔
{黄油,面包}	3,5	2/5=40%	✔
{黄油,牛奶}	无	0%	✖
{面包,牛奶}	1,4	2/5=40%	✔

频繁2-项集：{'啤酒', '牛奶'}, {'黄油', '面包'}, {'面包', '牛奶'}

步骤4：生成候选3-项集

尝试连接频繁2-项集（需前k-2=1项相同）：

{'啤酒','牛奶'} + {'面包','牛奶'} → 前1项'啤酒'≠'面包' → 无法连接
其他组合均不满足前1项相同条件

无候选3-项集生成

步骤5：生成关联规则（min_conf=60%）

（1）从频繁2-项集生成规则

{'啤酒', '牛奶'}:
- 规则1：啤酒 → 牛奶
  
  Conf = Support(啤酒,牛奶)/Support(啤酒) = 0.4/0.4 = 100%
  
  Lift = 0.4/(0.4 * 0.6) ≈ 1.67
- 规则2：牛奶 → 啤酒
  
  Conf = 0.4/0.6 ≈ 66.7%
  
  Lift ≈ 1.67
{'黄油', '面包'}:
- 规则3：黄油 → 面包
  
  Conf = 0.4/0.4 = 100%
  
  Lift = 0.4/(0.4 * 0.8) = 1.25
- 规则4：面包 → 黄油
  
  Conf = 0.4/0.8 = 50%
  
  Lift = 1.25
{'面包', '牛奶'}:
- 规则5：面包 → 牛奶
  
  Conf = 0.4/0.8 = 50%
  
  Lift = 0.4/(0.8 * 0.6) ≈ 0.83
- 规则6：牛奶 → 面包
  
  Conf = 0.4/0.6 ≈ 66.7%
  
  Lift ≈ 0.83

（2）筛选有效规则（Conf≥60%且Lift>1）

规则	置信度	提升度	是否有效
啤酒 → 牛奶	100%	1.67	✔
牛奶 → 啤酒	66.7%	1.67	✔
黄油 → 面包	100%	1.25	✔
面包 → 黄油	50%	1.25	✖
面包 → 牛奶	50%	0.83	✖
牛奶 → 面包	66.7%	0.83	✖

（3）最终强关联规则

啤酒 → 牛奶（买啤酒的顾客100%会买牛奶，且概率是普通顾客的1.67倍）
牛奶 → 啤酒（买牛奶的顾客66.7%会买啤酒，概率是普通顾客的1.67倍）
黄油 → 面包（买黄油的顾客100%会买面包，概率是普通顾客的1.25倍）

关键结论

字母序的严格性：确保所有项集按固定顺序处理（如{啤酒,牛奶}不会与{牛奶,啤酒}重复）
商业价值最高的规则：啤酒与牛奶的强双向关联（提升度1.67），可设计组合促销
面包的高频性：因面包本身支持度高（80%），导致与黄油的规则提升度较低（1.25）

三、Python实现代码

import pandas as pd
from mlxtend.frequent_patterns import apriori
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import association_rulesitemSetList = [['牛奶', '面包', '鸡蛋'],['啤酒', '牛奶'],['黄油', '面包'],['啤酒', '面包', '牛奶'],['黄油', '面包']
]#数据预处理——编码
te = TransactionEncoder()
te_array = te.fit(itemSetList).transform(itemSetList)
df = pd.DataFrame(te_array, columns = te.columns_)#挖掘频繁项集（最小支持度为0.5）
frequent_itemsets = apriori(df, min_support = 0.4, use_colnames = True)
print("发现的频繁项集包括：\n")
frequent_itemsets

TransactionEncoder()将购物篮数据转换为机器学习算法可处理的格式
fit()学习数据中所有唯一的商品项
transform()将每个购物篮转换为布尔向量（出现=True，未出现=False）
最终生成的数据框 df如下：

	牛奶	面包	鸡蛋	啤酒	薯片
0	True	True	True	False	False
1	False	True	False	True	True
2	True	True	False	True	True
3	False	False	False	True	True

apriori()函数执行Apriori算法
min_support=0.5表示只保留出现频率≥50%的项集
use_colnames=True使用商品名称而非列索引作为输出

rules = association_rules(frequent_itemsets, metric = 'confidence', min_threshold = 0.6, support_only = False)rules= rules[ rules['lift']>1]
print("生成的强关联规则为：\n")
rules

association_rules()函数从频繁项集中生成关联规则，参数说明：

frequent_itemsets: 之前通过apriori()找到的频繁项集
metric='confidence': 使用置信度作为主要评估指标
min_threshold=0.5: 只保留置信度≥50%的规则
support_only=False: 计算所有指标（不只计算支持度）

rules[rules['lift']>1]只保留提升度(lift)大于1的规则，这表示：

规则前项和后项是正相关的
前项的出现确实会提高后项出现的概率

关键指标解释

antecedents (前项) → consequents (后项)：
- 规则形式：如果买了前项商品，那么也可能买后项商品
support (支持度)：
- 规则在所有交易中出现的频率
- 例如"啤酒→薯片"支持度0.5表示这两个商品一起出现在50%的交易中
confidence (置信度)：
- 当前项出现时，后项也出现的概率
- "啤酒→薯片"置信度0.67表示买了啤酒的顾客中，67%也买了薯片
lift (提升度)：
- 衡量前项对后项的提升效果
- lift>1表示正相关（一起购买的可能性比随机更高）
- lift=1表示独立
- lift<1表示负相关

四、算法特性总结

特性	说明
优点	逻辑简单直观，适合教学
缺点	需多次扫描数据库，效率较低
适用场景	中小规模数据集
改进算法	FP-Growth（只需扫描2次数据库）
商业应用	购物篮分析、交叉销售推荐

五、面试常见问题

为什么Apriori需要多次扫描数据库？

每轮迭代都需要重新计算候选项集的支持度计数。
如何判断一个规则是否有价值？

综合看支持度（覆盖率）、置信度（可靠性）和提升度（相关性）。
提升度=1意味着什么？

表示前项和后项独立出现，没有关联关系。
如何处理数值型数据？

需要先离散化（如将年龄分为"青年/中年/老年"）。

六、例题

题目1

题目问的是："关联规则挖掘方法是一种基于规则的机器学习算法，以下关于关联规则挖掘方法的描述错误的是（）"。

选项解析

选项A：

"生产关联规则一般利用最小支持度从数据库中找到频繁项集"

正确：关联规则挖掘的第一步是通过最小支持度（min_support）筛选出频繁项集（Frequent Itemsets）。
例如，如果{牛奶,面包}在交易数据中出现的频率 ≥ min_support，则它是一个频繁项集。

选项B：

"生成关联规则一般利用最小置信度从频繁项集中找到关联规则"

正确：在得到频繁项集后，通过最小置信度（min_confidence）生成关联规则。
例如，从{牛奶,面包}可能生成规则"牛奶→面包"，其置信度 = P(面包|牛奶) ≥ min_confidence。

选项C：

"关联规则挖掘属于有监督学习算法"

错误（正确答案）：关联规则挖掘是典型的无监督学习方法。
- 原因：它不需要预先标注的标签（如分类问题中的类别），而是直接从数据中探索项之间的关联性。
- 有监督学习需要明确的输入-输出对（如分类、回归），而关联规则仅分析数据内在模式。

选项D：

"如果一个项集是频繁的，那么它的所有子集也一定是频繁的"

正确：这是Apriori算法的核心性质（反单调性）。
- 例如，若{牛奶,面包,啤酒}是频繁的，则{牛奶,面包}、{牛奶}等子集一定也是频繁的（因为子集的支持度 ≥ 父项集的支持度）。

关联规则挖掘的核心概念

频繁项集（Frequent Itemsets）：

通过最小支持度筛选出现频率高的项组合。
例如，{牛奶,面包}在超市交易中经常一起购买。

关联规则（Association Rules）：

形式：X → Y（如"买牛奶的人也会买面包"）。
通过最小置信度筛选可靠的规则。

无监督性：

不需要预先知道"正确答案"，而是自动发现数据中的模式。

题目2

正确答案与解析：C（提升度/Lift）

核心概念解析

支持度（Support）：
- 衡量规则中物品组合出现的频率
- 公式：Support(X→Y)=P(X∪Y)
- 局限性：高支持度可能包含常识性组合（如"面包+牛奶"），无法反映相关性。
置信度（Confidence）：
- 衡量规则可靠性（X出现时Y的概率）
- 公式：Confidence(X→Y)=P(Y∣X)
- 局限性：可能高估单向关联（如"尿布→啤酒"置信度高，但反向不成立）。
提升度（Lift）：
- 关键指标：直接衡量X与Y的相关性强度
- 公式：Lift=P(X)P(Y)P(X∪Y)
- 解释：
  - =1：X与Y独立
  - 1：正相关（值越大关联越强）
  - <1：负相关
- 优势：消除数据倾斜影响，识别真正有意义的规则。
支持度置信度比：
- 非标准指标，实际应用极少。

为什么选C？

题目要求："衡量强度和重要性" → 需同时排除高频但无意义的规则（支持度缺陷）和虚假关联（置信度缺陷）。
提升度唯一能反映：
- 规则是否比随机组合更有价值（如Lift=3表示该规则出现概率是随机预期的3倍）。
经典案例：
- 若"啤酒+尿布"的Lift远高于1，说明组合购买行为非偶然，具有商业价值。

对比总结

指标	作用	适用场景	局限性
支持度	筛选高频组合	商品陈列优化	无法评估相关性
置信度	评估规则可靠性	推荐系统（单向推荐）	可能高估虚假关联
提升度	量化相关性强度	精准营销、交叉销售	计算复杂度稍高

扩展思考

若题目改为"筛选高频项集"，则应选支持度；若问"评估规则可信度"，则选置信度。
Lift是关联规则挖掘中唯一能同时抵抗"高频项干扰"和"数据倾斜误导"的指标。

七、面试题

一、基础概念题

1. 请简要描述 Apriori 算法是什么，以及它解决的是什么问题？

答案：

Apriori 算法是一种经典的用于关联规则学习的算法，主要用于从大规模数据集中发现项（item）之间的有趣关系，即关联规则。

它解决的核心问题是“购物篮分析”，例如“如果顾客购买了商品A，那么他有多大的可能也会购买商品B？”（著名的“啤酒与尿布”案例）。其目标是发现那些频繁一起出现的物品集合（频繁项集），并基于这些项集生成强关联规则。

2. 解释 Apriori 算法中的两个核心概念：支持度（Support）和置信度（Confidence）。

答案：

支持度（Support）： 衡量一个项集（如 {X, Y}）在整个数据集中出现的频率。它的计算公式是：
Support(X) = (包含X的交易数) / (总交易数)
支持度用于筛选“频繁”出现的项集，过滤掉那些偶然出现的组合。
置信度（Confidence）： 衡量在包含项集 X 的交易中，也包含项集 Y 的条件概率。对于规则 X -> Y，其计算公式是：
Confidence(X -> Y) = Support(X ∪ Y) / Support(X)
置信度用于衡量规则的可靠性。置信度越高，说明当X出现时，Y也出现的可能性越大。

3. Apriori 算法的核心思想是什么？请阐述其名字“Apriori”的含义。

答案：
Apriori 算法的核心思想是 “先验知识” 或 “反单调性”（Apriori Principle）。
其具体内容是：如果一个项集是频繁的，那么它的所有子集也一定是频繁的。反之，如果一个项集是非频繁的，那么它的所有超集也一定是非频繁的。

“Apriori”这个名字来源于拉丁语，意为“从先前的”。在算法中，它正是指利用了这个“先验”的性质来剪枝，大大减少需要计算的候选集数量，从而提升算法效率。例如，如果项集 {啤酒} 本身都不频繁，那么我们根本不需要去计算更大的项集 {啤酒，尿布} 的支持度，因为它绝不可能是频繁的。

二、流程与实现题

4. 请描述 Apriori 算法发现频繁项集的主要步骤。

答案：
Apriori 算法采用一种逐层搜索的迭代方法，由k项集探索(k+1)项集。主要步骤如下：

设定最小支持度阈值（min_support）： 由用户指定，用于判断项集是否“频繁”。
扫描数据集，生成候选1项集（C₁），并计算其支持度。
剪枝： 将支持度低于 min_support 的候选集剔除，得到频繁1项集（L₁）。
迭代（k>1）：
a. 连接步（Join）： 将频繁(k-1)项集（Lₖ₋₁）与自身连接，生成候选k项集（Cₖ）。
b. 剪枝步（Prune）： 利用 Apriori 原理，检查候选k项集的所有(k-1)项子集是否都在 Lₖ₋₁ 中。如果不是，则直接删除该候选集（因为其子集不频繁，它本身也不可能是频繁的）。
c. 扫描步（Scan）： 再次扫描数据集，计算修剪后剩下的候选k项集的支持度。
d. 再次剪枝： 剔除支持度低于 min_support 的候选集，得到频繁k项集（Lₖ）。
终止： 重复步骤4，直到不能再生成新的频繁项集为止（即 Cₖ₊₁ 为空）。

5. 在生成了所有频繁项集后，如何从中挖掘关联规则？

答案：
对于每一个频繁项集 L，找出其所有的非空子集。
对于每一个非空子集 S，生成一条规则 S -> (L - S)。
计算这条规则的置信度：
Confidence(S -> (L-S)) = Support(L) / Support(S)
如果该置信度大于或等于用户设定的最小置信度阈值（min_confidence），则保留这条规则，认为是一条强关联规则。

三、优缺点与优化题

6. 谈谈 Apriori 算法的主要优点和缺点。

答案：

优点：
1. 原理简单： 易于理解和实现。
2. 利用先验原理剪枝： 显著减少了需要计算的候选集数量，是它成功的关键。
缺点：
1. 需要多次扫描数据库： 在每一层迭代中都需要扫描一次整个数据集来计算候选集的支持度，当数据集很大时，I/O开销巨大，是性能的主要瓶颈。
2. 可能产生大量的候选集： 尤其是当存在长频繁模式或支持度阈值设置过低时，会产生指数级数量的候选集，导致内存不足。
3. 效率问题： 对于海量数据集，计算效率较低。

7. 针对 Apriori 算法的缺点，有哪些常见的改进或优化方案？

答案：

基于数据划分（Partitioning）： 将数据集划分成多个块，分别挖掘每个块的频繁项集，最后再合并结果。可以减少内存需求。
基于采样（Sampling）： 对原始数据集进行采样，在小样本上挖掘频繁项集，然后用整个数据集验证。牺牲一定精度来换取速度。
使用哈希表（Hashing）： 在生成候选1项集或2项集时，使用哈希技术来更快地计数，减少比较次数。
动态项集计数（DIC）： 在扫描的不同点添加新的候选集，而不是在每次扫描开始时决定，可以更早地剪枝。
采用更先进的算法：
- FP-Growth（频繁模式增长）算法： 这是最著名的改进算法。它只须扫描数据集两次，将数据压缩到一棵FP树中，然后在树上进行挖掘，完全不产生候选集，效率远高于 Apriori。

四、实战应用题

8. 给定一个简单的交易数据集，请手动演示找出频繁项集的过程。
数据集：
T1: {Milk, Bread}
T2: {Milk, Diaper, Beer, Eggs}
T3: {Bread, Diaper, Beer, Cola}
T4: {Bread, Milk, Diaper, Beer}
T5: {Bread, Milk, Diaper, Cola}
设最小支持度 min_support = 3/5 = 0.6

答案：
第一次扫描： 生成候选1项集 C₁ 并计算支持度。

项集	Support
Milk	4
Bread	4
Diaper	4
Beer	3
Eggs	1
Cola	2

剪枝： 剔除支持度 < 3 的项集（Eggs, Cola），得到频繁1项集 L₁。
L₁ = {Milk:4, Bread:4, Diaper:4, Beer:3}

第二次扫描： 由 L₁ 连接生成候选2项集 C₂ = L₁ × L₁。
C₂ = { {Milk, Bread}, {Milk, Diaper}, {Milk, Beer}, {Bread, Diaper}, {Bread, Beer}, {Diaper, Beer} }

扫描计算 C₂ 支持度：

项集	Support
{Milk, Bread}	3 (出现在T1, T4, T5)
{Milk, Diaper}	4 (出现在T2, T4, T5)
{Milk, Beer}	2 (出现在T2, T4)
{Bread, Diaper}	4 (出现在T3, T4, T5)
{Bread, Beer}	2 (出现在T3, T4)
{Diaper, Beer}	3 (出现在T2, T3, T4)

剪枝： 剔除支持度 < 3 的项集（{Milk, Beer}, {Bread, Beer}），得到频繁2项集 L₂。
L₂ = { {Milk, Bread}:3, {Milk, Diaper}:4, {Bread, Diaper}:4, {Diaper, Beer}:3 }

第三次扫描： 由 L₂ 连接生成候选3项集 C₃。
连接：L₂ 中的项集两两连接，要求前(k-2)项相同。
{Milk, Bread} 和 {Milk, Diaper} 可连接为 {Milk, Bread, Diaper}
{Milk, Bread} 和 {Bread, Diaper} 可连接为 {Milk, Bread, Diaper} (同上)
{Milk, Diaper} 和 {Bread, Diaper} 可连接为 {Milk, Bread, Diaper} (同上)
{Milk, Diaper} 和 {Diaper, Beer} 可连接为 {Milk, Diaper, Beer}
... 等等，但需要检查子集是否频繁。
剪枝（Prune Step）： 检查每个候选3项集的所有2项子集是否都在 L₂ 中。

候选 {Milk, Bread, Diaper}：其子集 {Milk, Bread}, {Milk, Diaper}, {Bread, Diaper} 都在 L₂ 中，保留。
候选 {Milk, Diaper, Beer}：其子集 {Milk, Beer} 不在 L₂ 中（因为支持度只有2），因此删除该候选。
其他候选同理判断。最终 C₃ = { {Milk, Bread, Diaper} }

扫描计算 C₃ 支持度：
{Milk, Bread, Diaper} 出现在 T4, T5，支持度为 2。
剪枝： 支持度 2 < 3，因此 L₃ 为空。

算法终止。 所有频繁项集为 L₁ ∪ L₂。