下面这份笔记严格以你上传的《Pattern Mining: Basic Concepts and Methods》课件为主线整理，并按照“为什么旧方法不够 → 新方法解决什么 → 又暴露什么新问题”的方式重构，而不是逐页抄 PPT。课件整体覆盖 Basic Concepts、Frequent Itemset Mining、Pattern Evaluation 三条主线，最终总结也明确包含 Apriori、ECLAT、FP-Growth、closed/max patterns、Lift、、null-invariant measures 等内容。

重要性标记：

★★★★★：核心考点，定义/计算/推导/算法流程都应掌握
★★★★☆：高频理解题、比较题
★★★☆☆：需要知道作用和基本原理
★★☆☆☆：背景/扩展，知道即可

Chapter 3 Pattern Mining: Basic Concepts and Methods

0. 本章到底在解决什么问题？★★★★★

Pattern Mining 的核心问题不是简单地“找出现次数多的东西”，而是：

从巨大的组合搜索空间中，高效地发现具有统计意义的数据模式，并进一步判断这些模式是否真的有意义。

整个章节可以看成三个连续问题。

第一层是：

如何定义：

itemset
frequent itemset
association rule
support / confidence

第二层是：

因为 item 数量增加以后，候选模式数量呈指数爆炸：

于是产生：

第三层是：

于是：

这就是整章最重要的“进化树”。

1. 整章方法论进化树 ★★★★★

text

Massive Dataset
│
├── Pattern Discovery
│     │
│     ├── Frequent itemsets
│     ├── Frequent sequences
│     └── Frequent structures
│
├── 如何定义频繁？
│     │
│     ├── support
│     ├── minsup
│     └── frequent itemset
│
├── 如何表达更有解释性的关系？
│     │
│     └── Association Rules
│            ├── support
│            └── confidence
│
├── Problem 1: Pattern explosion
│     │
│     ├── Closed Pattern → 无损压缩
│     └── Max Pattern    → 有损压缩
│
├── Problem 2: 如何真正搜索？
│     │
│     └── Downward Closure / Apriori Property
│            │
│            ├── Apriori
│            │     ├── candidate generation
│            │     └── candidate pruning
│            │
│            ├── Apriori Improvements
│            │     ├── Partitioning
│            │     └── DHP hashing
│            │
│            ├── ECLAT
│            │     └── Vertical Tid-list intersections
│            │
│            └── FP-Growth
│                  ├── FP-tree
│                  ├── Conditional DB
│                  └── Recursive pattern growth
│
└── Problem 3: Frequent ≠ Interesting
      │
      ├── support-confidence failure
      │
      ├── Lift
      ├── Chi-square
      │
      ├── Problem: null transactions
      │
      ├── Null-invariant measures
      │     ├── AllConf
      │     ├── Jaccard
      │     ├── Cosine
      │     ├── Kulczynski
      │     └── MaxConf
      │
      └── Kulczynski + Imbalance Ratio

这一逻辑比记算法名称重要得多。

Part I. Basic Concepts

2. 什么是 Pattern？★★★★☆

课件定义：

Pattern 是在数据集中经常共同出现，或者具有强相关性的一组 items、subsequences 或 substructures。

因此 pattern 不局限于购物篮：

Frequent itemsets
Frequent sequences
Frequent structures

Pattern discovery：

从 massive datasets 中 uncover patterns。

典型问题：

哪些商品经常一起购买？
买完 iPad 后，用户下一步通常买什么？
哪些结构经常在图中共同出现？
哪些事件经常按某种顺序出现？

3. 为什么 Pattern Mining 重要？★★★☆☆

它不是孤立任务，而是很多 Data Mining 问题的基础：

association analysis
correlation analysis
causality analysis
sequential pattern mining
structural/subgraph pattern mining
classification
clustering

应用：

Market basket analysis
Cross-marketing
Catalog design
Sale campaign analysis
Web log analysis
Biological sequence analysis

数据还可以扩展到：

spatiotemporal
multimedia
time-series
stream data

4. Transactional Database ★★★★☆

典型事务数据库：

TID	Items
1	Beer, Nuts, Diaper
2	Beer, Coffee, Diaper
3	Beer, Diaper, Eggs
4	Nuts, Eggs, Milk
5	Nuts, Coffee, Diaper, Eggs, Milk

每个 transaction：

其中：

：第个 transaction
：所有可能 items 的全集
TID：transaction identifier

5. Itemset 与 -Itemset ★★★★★

设所有 items：

一个 itemset：

若中恰好有个 item：

则称为：

例如：

是 3-itemset。

6. Support：整个章节最基本的量 ★★★★★

6.1 Absolute support

绝对 support：

即：

数据库中包含的 transaction 数量。

例如：

6.2 Relative support

设数据库一共有：

个 transactions。

则：

可以理解成随机抽一个 transaction：

例如：

7. Frequent Itemset ★★★★★

给定 minimum support：

若：

则为 frequent itemset。

如果使用绝对 support threshold ，则等价为：

7.1 课件例子

取：

5 条事务，因此至少需要出现：

即实际上至少 3 次。

Frequent 1-itemsets：

Frequent 2-itemsets：

Frequent 3-itemsets：

为什么没有必要继续考虑 4-itemsets、5-itemsets？

答案在后面的 Apriori property。

8. Frequent Itemset → Association Rule ★★★★★

Itemset：

只能告诉我们：

Beer 和 Diaper 经常一起出现。

Association rule：

增加了一个方向性解释：

在购买 Diaper 的 transactions 中，Beer 出现的概率是多少？

注意：

并不表示因果关系。

它首先只是 conditional association。

9. Association Rule 的 Support 和 Confidence ★★★★★

设：

规则涉及的联合 itemset 是：

9.1 Rule support

即同时含有的 transaction 比例。

例如：

Support 衡量：

这条规则覆盖整个数据库的程度。

9.2 Confidence ★★★★★

定义：

因为：

所以：

例如：

即：

含 Diaper 的 4 条 transaction 中，有 3 条同时含 Beer。

10. Association Rule Mining 的正式问题 ★★★★★

给两个 threshold：

寻找所有：

满足：

以及：

的规则。

10.1 课件例子

唯一 frequent 2-itemset：

于是可生成两条规则：

Beer → Diaper

所以：

Diaper → Beer

因此：

课件黄色问题：

Are these all the rules satisfying the two conditions?

答案：

因为没有其他 frequent 2-itemset 或更大 frequent itemset 能生成非平凡规则。

Part II. Pattern Explosion 与压缩表示

11. 为什么不能直接枚举所有 frequent patterns？★★★★★

课件构造：

并设置绝对 support count 阈值：

由于第二条 transaction 包含全部 100 个 item，所以其任意非空子集至少出现一次。这里的 1 必须理解为出现次数阈值；若把 minsup 定义为 relative support，表示 100%，不能得到下述结论。

因此所有非空 subsets 都 frequent。

总数：

利用二项式定理：

去掉空集：

这是 exponential explosion。

12. Closed Pattern：无损压缩 ★★★★★

问题：

很多不同 itemset 具有完全相同 support，是否有必要全部存储？

答案之一：

定义：

一个 frequent pattern 是 closed，如果不存在：

使：

形式化：

12.1 为什么这是一种 compression？

仍看：

minsup = 1。

虽然有：

个 frequent patterns，但 closed patterns 只有：

原因：

任何只由构成的 pattern，其 support 都是 2。

它们都可以继续扩展到：

而 support 不变。

所以只有最大那个代表这一 entire equivalence class。

12.2 为什么是 lossless？★★★★★

Closed patterns：

例如：

它被：

包含，而：

于是可以恢复：

类似：

只能属于 support 为 1 的 closure：

所以：

更一般地，可理解为：

因此 closed frequent patterns 是：

13. Closed Pattern 的第二个例子 ★★★★☆

Transactions：

minsup：

下面所有 pattern support 都是 2：

前六个都有一个 support 相同的 frequent superset。

因此真正 closed 的是：

而：

由于 minsup=2，不是 frequent pattern。

14. Max Pattern：进一步压缩，但有损 ★★★★★

定义：

一个 pattern 是 maximal frequent pattern，如果：

frequent；
不存在任何 frequent proper superset。

即：

14.1 与 Closed 最大区别

Closed：

不存在 support 相同 的 frequent super-pattern。

Maximal：

不存在 任何 frequent super-pattern。

所以条件更强。

在前面 TDB 中：

是唯一 max-pattern。

14.2 为什么 Max Pattern 是 lossy？

知道：

frequent。

利用 downward closure，可以知道：

一定 frequent。

但是你不知道它的真正 support：

实际上这里是 2，但 maximal pattern representation 无法恢复。

所以：

15. Closed vs Maximal ★★★★★

属性	Closed Pattern	Maximal Pattern
必须 frequent	Yes	Yes
不允许什么 superset	相同 support 的 superset	任意 frequent superset
压缩	Lossless	Lossy
子集是否能判断 frequent	Yes	Yes
子集准确 support	可以恢复	无法恢复
pattern 数	较少	最少
信息量	高	低
典型用途	Analysis / Query	极端压缩

由定义还能直接推出：

原因是：

如果一个 maximal pattern 有 support 相同的 proper superset，那么该 superset 显然也是 frequent，与 maximal 矛盾。

Part III. Efficient Frequent Pattern Mining

16. 最重要的理论：Downward Closure / Apriori Property ★★★★★

这是整个 frequent pattern mining 算法的数学基础。

如果：

那么所有包含的 transaction 必然也包含。

所以：

即 support 关于集合扩张是 monotonic decreasing。

因此：

即：

这就是：

16.1 最重要的逆否命题 ★★★★★

原命题：

其中。

逆否命题：

即：

这就是 pruning。

17. 三条 scalable mining 路线 ★★★★☆

课件总结了三种经典思想：

方法	核心思想	搜索方式
Apriori	level-wise candidate generation	BFS-like
ECLAT	vertical Tid-list intersection	DFS
FP-Growth	conditional pattern growth	Recursive DFS

历史：

Apriori：1994
ECLAT：1997
FP-Growth：2000

其演进本质是：

18. Apriori Algorithm ★★★★★

Apriori 是：

基本流程：

扫描 DB 得到 frequent 1-itemsets：
用生成 candidate：
扫描数据库，计算 support。
得：
重复直到：

19. Apriori Pseudocode ★★★★★

记：

逻辑：

text

k := 1
F1 := frequent 1-itemsets

while Fk != ∅:
    Ck+1 := generate_candidates(Fk)
    count candidates in Ck+1 by scanning TDB
    Fk+1 := candidates satisfying minsup
    k := k + 1

return ⋃k Fk

需要记住：

20. Apriori 完整例题 ★★★★★

数据库：

TID	Items
10	A,C,D
20	B,C,E
30	A,B,C,E
40	B,E

设：

Step 1：

因此：

D 被删除。

Step 2：生成

由：

扫描 DB：

于是：

Step 3：

能通过 Apriori pruning 的候选：

因为其所有 2-subsets：

均 frequent。

支持度：

所以：

之后不能产生。

算法结束。

21. Apriori Candidate Generation ★★★★★

Apriori 的候选生成包含两步：

21.1 Self-join

例如：

根据共同前缀：

21.2 Pruning

检查候选的所有 -subsets 是否都属于。

对于：

其一个 3-subset：

不在：

根据 Apriori property：

因此删掉：

最终：

22. Candidate Generation 的 join 条件 ★★★★☆

假设中 item 按固定顺序排列。

两个：

只有在前：

个 items 相同：

并且：

时才 join：

然后：

若为 true：

否则加入：

23. Apriori 到底哪里慢？★★★★★

Apriori 虽然比 brute force 好很多，但仍然有两个主要瓶颈。

Problem A：Repeated DB scans

每增加一个 level：

都需要重新扫描数据库。

若最长 frequent pattern 很长：

Problem B：Too many candidates

如果大量 item 都 frequent：

仍可能非常大。

因此后续改进主要围绕：

和：

24. Apriori Improvements 概览 ★★★☆☆

课件列出：

减少 transaction DB scans：

Partitioning
Dynamic itemset counting

减少 candidates：

Hashing / DHP
Support lower-bound pruning
Sampling

特殊 data structures：

Tree projection
H-miner
Hypercube decomposition / LCM

课件重点展开：

25. Partitioning：数据库只扫描两次 ★★★★★

核心 theorem：

如果一个 itemset 在整个数据库中 frequent，那么它至少在一个 partition 中 locally frequent。

设：

global minsup ratio：

假设在所有 partitions 都不 frequent：

对于所有。

求和：

因为：

以及：

因此：

所以 globally infrequent。

取逆否命题：

这就是 Partitioning 方法的理论保证。

26. Partitioning 两次扫描 ★★★★★

Scan 1

将数据库 partition：

使每一个：

这样 local mining 可以主要在内存完成。

对每个 partition 找：

所有 local frequent patterns 的 union 组成 global candidates。

Scan 2

重新扫描所有 partitions。

对候选：

重新计算真正 global support。

最终保留满足：

者。

优势：

27. Direct Hashing and Pruning (DHP) ★★★★★

另一个 Apriori bottleneck：

太大。

DHP 使用：

把 itemset hash 到 bucket。

注意：

多个 itemsets 可能 hash 到同一个 bucket：

27.1 核心思想

第一次扫描数据库的时候，本来正在 count 1-itemsets。

同时把 transaction 中所有 2-itemsets hash 到 buckets。

例如一个 bucket：

bucket count：

如果：

那么：

则：

全部不可能 frequent。

27.2 为什么成立？★★★★★

假设被 hash 到 bucket 。

bucket count 是该 bucket 中所有 hashed itemsets 的累计出现量。

因此：

如果：

则必然：

所以：

27.3 一个非常容易考的陷阱

反过来不成立：

不能推出：

因为存在：

多个 itemsets 的 counts 被加在一起。

所以 DHP 是：

而不是直接判 frequent。

28. 从 Apriori 到 ECLAT：为什么要换数据表示？★★★★★

Apriori 的核心问题：

要不断扫描 horizontal transactions 来数 support。

ECLAT 的想法完全不同：

不再重复扫 transaction，而是直接记录每个 item 出现在哪些 TID 中。

这就是：

29. ECLAT ★★★★★

ECLAT：

特点：

vertical format
depth-first search
set intersection

29.1 Horizontal representation

例如：

TID	Items
10	a,c,d,e
20	a,b,e
30	b,c,e

29.2 Vertical representation

变成：

Item	Tid-list
a	10,20
b	20,30
c	10,30
d	10
e	10,20,30

定义：

例如：

30. ECLAT 的 support = set intersection ★★★★★

若：

两个 itemsets，则：

所以：

例如：

则：

所以：

不再重新扫描原始 DB。

31. Tid-list 的结构信息 ★★★★☆

若：

说明：

在 transaction 层面总是共同出现。

课件例子：

如果：

说明：

每一个含的 transaction 一定也含。

例如：

而：

因此：

32. Diffset ★★★★☆

当 Tid-list 很长时，保存完整交集也可能昂贵。

于是可以只存：

例如：

于是：

如果从扩展得到：

这里：

核心思想：

33. Apriori → ECLAT 的本质演进 ★★★★★

	Apriori	ECLAT
Data format	Horizontal	Vertical
Search	Level-wise	Depth-first
Support calculation	Scan transactions	Tid-list intersection
Candidate idea	Explicit generation	Intersection-based extension
主要成本	DB scans	Set intersections
适合思想	广度剪枝	垂直递归

ECLAT 解决的是：

但仍然需要探索大量 itemset combinations。

于是引出：

34. FP-Growth：为什么出现？★★★★★

Apriori 的核心模式：

即使 pruning 很强，在 dense database 中：

仍然可能巨大。

FP-Growth 的目标：

核心思路：

把 transaction DB 压缩成 FP-tree；
针对某个 pattern 构造 conditional database；
recursively grow pattern。

35. FP-Growth Step 1：找 frequent items ★★★★★

课件样例：

原始 transactions：

TID	Transaction
100	f,a,c,d,g,i,m,p
200	a,b,c,f,l,m,o
300	b,f,h,j,o,w
400	b,c,k,s,p
500	a,f,c,e,l,p,m,n

第一次扫描：

其余 item：

删除。

36. F-list ★★★★☆

把 frequent items 按 frequency descending 排列。

课件采用：

注意存在 tie 时：

都为 4，

都为 3。

只要使用固定 consistent ordering 即可。

37. 将 transaction 重排序 ★★★★★

根据 F-list：

TID 100：

删除 infrequent items 后：

重新按照 F-list：

最终：

TID	Ordered frequent itemlist
100	f,c,a,m,p
200	f,c,a,b,m
300	f,b
400	c,b,p
500	f,c,a,m,p

为什么要排序？

因为：

从而让 FP-tree 压缩更有效。

38. FP-tree Construction ★★★★★

每个 ordered transaction 从 root：

开始插入。

如果 prefix 已存在：

不新建节点，只增加 node count。

如果不存在：

创建新 branch。

38.1 最终树结构

最终大致为：

text

{}
├── f:4
│   ├── c:3
│   │   └── a:3
│   │       ├── m:2
│   │       │   └── p:2
│   │       └── b:1
│   │           └── m:1
│   └── b:1
│
└── c:1
    └── b:1
        └── p:1

例如：

意味着有 4 个 frequent transaction paths 从该节点通过。

39. Header Table ★★★★☆

FP-tree 同时维护：

每种 item：

frequency
pointer/node link

将 FP-tree 中相同 item 的多个节点链接起来。

目的：

如果要 mine pattern ：

可以通过 header table 直接找到所有 nodes。

不需要遍历整棵树。

40. FP-Growth 最难点：Conditional Pattern Base ★★★★★

如果我们想找：

只需要关注：

所有通向的 prefix paths。

课件中：

解释：

有一条：

路径对应：

所以 prefix：

另一条：

对应：

因此：

称：

conditional pattern base
conditional database

41. Conditional Databases ★★★★★

课件得到：

这代表：

在“当前 pattern 已经包含某 item”的条件下，还有哪些 prefix items 可以继续生长。

42. Recursively Mine Conditional DB ★★★★★

对于每个 conditional DB：

count frequent single items；
删除 infrequent；
建 conditional FP-tree；
recursively mine。

例如：

其中出现：

达到 minsup：

所以可以得到：

43. 的 conditional database ★★★★★

原始：

统计：

但：

删除后：

形成单一路径：

text

f:3
|
c:3
|
a:3

44. Single-path FP-tree：一个重要 shortcut ★★★★★

若 conditional FP-tree 是单一路径，例如：

则无需继续递归。

路径上所有 items 的非空组合都可直接产生 frequent patterns。

再与 suffix：

拼接。

得到：

二项：

三项：

四项：

所以：

如果路径长度：

个非空组合。

45. FP-Growth 的完整逻辑 ★★★★★

text

DB
 ↓
Find frequent 1-items
 ↓
Sort items by global frequency
 ↓
Construct FP-tree
 ↓
Choose suffix item x
 ↓
Extract x's conditional pattern base
 ↓
Construct conditional FP-tree
 ↓
Recursively grow pattern
 ↓
Empty tree? Stop
Single path? Enumerate combinations

其本质：

46. Apriori vs ECLAT vs FP-Growth ★★★★★

这是非常适合期末大题的比较。

	Apriori	ECLAT	FP-Growth
核心思想	candidate generation	Tid-list intersection	pattern growth
DB representation	horizontal	vertical	FP-tree
Search	BFS / level-wise	DFS	recursive DFS
是否 candidate generation	是	隐式	否
DB scans	多次	转换后少	通常主要两次构树
Support 计算	scan DB	set intersection	tree counts
压缩 DB	否	Tid-list	强
主要问题	candidate explosion	Tid-list/intersection cost	tree/conditional DB complexity

技术进化：

课件 Efficient Pattern Mining Methods 的主线正是 downward closure → Apriori → improvements → vertical format → FP-Growth。

47. 关于 Mining Closed Patterns 的课件范围

这里需要特别说明：

课件 summary 中列出了：

但正文没有继续详细讲 CHARM/CLOSET 等算法流程。

真正讲到的是：

closed pattern 定义
lossless compression
closed vs maximal

最后 recommended readings 才提到：

CHARM
CLOSET+

因此期末复习时，基于本课件本身，你应该重点掌握：

而不是自行扩展 CHARM 算法细节。

Part IV. Pattern Evaluation

48. 为什么“找到 frequent pattern”还不够？★★★★★

Pattern mining 往往产生大量 patterns。

问题：

因此需要：

49. Objective vs Subjective Interestingness ★★★★☆

Objective measures

仅由 data 决定：

support
confidence
correlation
Lift
etc.

Subjective measures

依赖用户。

例如：

Query-based

是否和当前用户问题有关？

Knowledge-based

是否违背已有 knowledge？

Unexpectedness

是否令人意外？

Freshness

是不是新信息？

Timeliness

现在是否有价值？

所以：

50. Support-Confidence Framework 的根本问题 ★★★★★

这是后半章最重要的“Why it fails”。

定义：

数据：

			total
	400	350	750
	200	50	250
total	600	400	1000

51. 看似很强的规则 ★★★★★

规则：

Support：

Confidence：

因此：

看起来 support、confidence 都很不错。

但是：

总体吃 cereal 的概率：

而：

于是：

也就是说：

所以这是一个非常关键的结论：

前半章 support-confidence 主要用于 rule filtering；后半章开始明确区分：

52. 更有信息的规则

对于：

support：

confidence：

所以：

这更准确反映：

不打篮球的人反而更可能吃 cereal。

53. Lift：相对于 baseline 的提升 ★★★★★

为解决 confidence 无视基础概率的问题，引入：

定义：

代入 confidence：

得：

从概率角度：

54. Lift 的解释 ★★★★★

若 independent：

所以：

因此：

55. Lift 例题 ★★★★★

所以：

negative correlated。

同时：

所以：

因此：

positive correlated。

56. Test ★★★★★

另一种 correlation test：

其中：

：Observed frequency
：Expected frequency under independence

57. Expected Count 怎么算？★★★★★

如果 independent：

因此：

整理：

对于：

其他 cells：

58. 计算 ★★★★★

Observed：

Expected：

于是：

结果：

课件通过查 distribution table 得到：

statistically correlated。

严格地说，还须给出自由度和显著性水平再比较临界值；这个 contingency table 的自由度为。本例足够大，结论没有变化。

方向怎么判断？

对关键 cell：

所以实际共同发生少于 independence expectation。

因此：

59. Lift / 又出现了什么问题？★★★★★

到这里似乎解决了：

的缺陷。

但马上出现第二层 failure：

定义：

同时既不包含也不包含的 transaction。

即：

60. Null Transaction 反例 ★★★★★

数据：

			total
	100	1000	1100
	1000	100000	101000
total	1100	101000	102100

关键结构：

但：

直觉上：

当 B 或 C 真正出现时，两者一起出现反而并不常见。

但：

极大。

61. 为什么 Lift 会被骗？★★★★★

因此：

整理：

于是 Lift 竟然说：

62. 为什么也会被骗？★★★★★

独立时：

但 observed：

因此：

导致：

看起来相关性极强。

课件总结：

Too many null transactions may “spoil the soup”.

63. 本质上发生了什么？★★★★★

当：

极大时，数据库总规模巨大。

导致：

和：

都非常小。

于是 independence baseline：

变得极小。

即使：

本身也很小，仍然可能比：

大很多。

于是 Lift 被放大。

因此需要：

64. Null Invariance ★★★★★

定义：

改变 null transactions 的数量，不应改变 measure。

即如果仅增加：

metric：

保持不变。

65. 为什么 Conditional Probabilities 是 Null-Invariant？★★★★★

定义：

和：

写成 counts：

同样：

增加 null transactions 只改变：

不改变：

因此：

这也是后续 measures 的核心。

66. Interestingness Measures 大汇总 ★★★★★

课件给出：

Measure	Formula	Range	Null-invariant?
			No
Lift			No
AllConf			Yes
Jaccard			Yes
Cosine			Yes
Kulczynski			Yes
MaxConf			Yes

这里课件中的延续 itemset convention，表示组合 itemset 的 joint support。

67. 用看这些指标 ★★★★★

设：

那么：

AllConf

因为：

对应较小的条件概率：

MaxConf

Kulczynski

即两个方向 confidence 的 arithmetic mean。

Cosine

而：

所以：

即两个 directional confidence 的 geometric mean。

这是很好的理解方式。

68. 为什么 Null-Invariant 还不够？★★★★★

课件进一步强调：

Not all null-invariant measures are created equal.

也就是说：

关键在于：

和：

可能严重不平衡。

69. D4 / D5 / D6：Kulc 最关键的例子 ★★★★★

三个数据集：

因此：

所以：

对应课件数据：

一侧 non-cooccurrence：

另一侧：

于是两个 directional confidences 约：

与：

但是：

更极端：

一个方向约：

另一个约：

所以：

因此：

Kulc 都是：

但显然三者不一样。

问题变成：

如何描述 directional imbalance？

这就引出 IR。

课件明确指出 Kulc 在 D4-D6 中保持两方向 implication 的平衡，而不同 null-invariant measures 在这些案例上会给出不同判断。

70. Imbalance Ratio (IR) ★★★★★

定义：

其中 denominator：

可以理解为：

transactions 中至少含或的 support。

为了避免课件 itemset/event notation 混淆，可以记：

表示 A、B co-occurrence，则：

课件在这一页用 Kulczynski + IR 对 D4-D6 进行联合解释。

71. IR 的直觉 ★★★★★

如果：

则：

意味着：

如果二者 frequency 差别巨大：

变大，

于是：

即：

72. Kulc + IR 联合解释 ★★★★★

课件数据：

Dataset	Kulc	IR	Interpretation
D4	0.5	0	neutral & balanced
D5	0.5	0.89	neutral but imbalanced
D6	0.5	0.99	neutral but very imbalanced

这非常重要。

Kulc 回答：

IR 回答：

两者是互补的。

73. 为什么 Kulc 比单看 MaxConf 更稳定？★★★★☆

以为例：

可能：

而：

如果用：

则：

看起来“极强关联”。

如果 AllConf：

看起来“几乎无关联”。

两者完全相反。

Kulc：

告诉我们：

平均而言是 neutral，但方向高度不平衡。

再配：

解释就完整了。

74. DBLP Coauthor Example ★★★☆☆

课件把上述思想应用到 DBLP：

哪些 authors 强相关？A 是 advisor 还是 advisee？

DBLP：

computer science publication database
3.8 million author/paper/venue/year entries

课件指出 advisor-advisee 类型关系可能表现为：

Kulc：high
Jaccard：low
Cosine：middle

并建议使用 Kulc 来寻找：

advisor-advisee
close collaborators

这说明 pattern interestingness measure 的选择高度依赖数据结构与业务问题。

75. 最终：到底应该选哪个 Interestingness Measure？★★★★★

课件给出的最终判断流程是：

情况 1：Null transactions 不占主导

可以使用：

情况 2：大量 sparse / null transactions

例如购物篮中：

大多数 basket 既没有 milk，也没有 coffee。

或者 DBLP：

大部分论文既没有 Mike，也没有 Jim。

此时：

课件推荐：

联合评价 pattern。

注意一个微妙点：

Cosine 本身在课件表格里属于 null-invariant measure；但课件最终仍更推荐在 null-heavy / strongly imbalanced 情况下使用 Kulc + IR。原因可以从 D4-D6 看出：

Part V. 三条“方法演进线”务必记住

76. 演进线 1：Pattern 表示的演进 ★★★★★

Frequent itemsets

优点：

完整。

问题：

↓

Closed Patterns

解决：

删除同 support 的冗余 patterns。

特点：

问题：

数量仍可能较多。

↓

Maximal Patterns

进一步删除非最大 frequent patterns。

特点：

代价：

77. 演进线 2：Mining Algorithm 的演进 ★★★★★

Brute Force

问题：

search space。

↓

Downward Closure

关键发现：

↓

Apriori

利用 property 进行：

问题：

many DB scans
candidate explosion

↓

Partitioning / DHP

Partitioning：

DHP：

↓

ECLAT

改变数据表示：

support：

↓

FP-Growth

彻底避免：

通过：

78. 演进线 3：Interestingness 的演进 ★★★★★

Support

问：

Pattern 是否足够普遍？

问题：

没有方向，也没有 conditional relation。

↓

Confidence

问：

问题：

忽略：

baseline。

↓

Lift

比较：

问题：

受 null transactions 强烈影响。

↓

比较 observed 与 independence expectation。

问题同样：

↓

Null-invariant Measures

消除 null transaction 数量影响。

但：

↓

Kulczynski + IR

Kulc：

IR：

形成更加完整的解释。

79. 期末考试最容易混淆的概念 ★★★★★

1. Frequent ≠ Closed ≠ Maximal

2. Closed 不是“没有 frequent superset”

Closed：

Maximal 才是：

3. Confidence 不代表 positive correlation

可能：

但：

则实际降低概率。

4. Lift > 1 不一定在 sparse data 中可靠

大量：

会严重改变 Lift。

5. 只告诉你 deviation 大

方向还需要看：

6. Null invariant 不代表“不受任何数据 imbalance 影响”

D4-D6 就是反例。

因此：

7. DHP 的 hash bucket 只能安全排除

但是：

8. Apriori candidate 生成不是随便 union

必须：

self-join；
检查所有 -subsets；
有一个 infrequent 就 prune。

9. ECLAT 最核心公式

10. FP-Growth 最核心对象

一定区分：

F-list
FP-tree
header table
prefix path
conditional pattern base
conditional FP-tree

80. 算法选择速记表 ★★★★★

目标	关键技术
判断是否 frequent	Support + minsup
找所有 frequent patterns	Apriori / ECLAT / FP-Growth
利用 subset pruning	Apriori property
降低数据库扫描次数	Partitioning
减少 candidates	DHP
用集合交集算 support	ECLAT
避免 candidate generation	FP-Growth
压缩 frequent patterns 且保留 support	Closed patterns
极致压缩，只保留 frequent boundary	Maximal patterns
判断相对独立性	Lift
检验 independence deviation
大量 null transactions	Null-invariant measures
同时考虑双向关系	Kulczynski
判断两个方向是否 imbalance	IR

81. 公式总表：考前必须能默写 ★★★★★

Support count

Relative support

Frequent

Confidence

Apriori monotonicity

Candidate space

ECLAT

Lift

Expected count

Chi-square

AllConf

Jaccard

Cosine

Kulczynski

MaxConf

Imbalance Ratio

82. 最后压缩成一张“考试脑图” ★★★★★

你只要能够从下面这条链完整讲出来，整章结构基本就掌握了：

但：

所以：

同时搜索空间：

太大，因此：

产生：

Apriori 又有：

于是：

再进一步改变 computation：

最终：

但挖完以后又发现：

所以：

又发现：

于是：

最后：

作为课件在大量 sparse/null transaction 场景下推荐的最终判断方案。

这条“问题 → 方法 → 新问题 → 下一代方法”的链，就是本章真正的底层逻辑。

高密度复习：Pattern Mining 基础

核心量与三条判断

量	回答的问题	判读
support	模式常不常见	才 frequent
confidence	出现时多常出现	非对称；不等于相关
lift	是否偏离独立	正相关，负相关，独立
	偏离独立是否显著	同时报与

Apriori / FP-growth / ECLAT 一眼区分

方法	数据表示	核心动作	痛点 / 优势
Apriori	horizontal transactions	join + prune + 多次 scan	candidate explosion
Partition	分块局部频繁再全局验证	local minsup	降低内存/scan 压力
DHP	hash bucket	hash pruning	只能安全剪掉不可能频繁者
ECLAT	vertical TID set	TID intersection	深度优先、对稀疏数据友好
FP-growth	FP-tree	conditional pattern base/tree	不显式生成候选；树压缩失效时不理想

Apriori property：若 itemset frequent，则所有非空子集都 frequent；等价地，任何 infrequent set 的所有 supersets 都 infrequent。它是 pruning 的单向性质，不能反推“子集频繁则超集频繁”。

Closed / maximal / negative correlation

模式	条件	信息损失
Closed	无真超集具有相同 support	可无损恢复 support
Maximal	无频繁真超集	更紧凑，但丢失子集 support
Rare	support 低但有意义	需任务语境，非自动“噪声”

对 sparse/null transaction，support-based negative correlation 会受大量 joint absence 影响；优先理解 null-invariant measures，如 Kulc：

考场算法链

先给频繁项集，再从每个频繁枚举非空真子集，产生。
过滤“规则可靠性”，lift/ 检查“是否仅由 base rate 造成”。
的 expected count 来自边际总数；表。
“minsup=1 导致 ”中的 1 是 absolute count ；relative minsup 表示 100% 支持度，不能混用。

Chapter 3 Pattern Mining: Basic Concepts and Methods ​

0. 本章到底在解决什么问题？★★★★★ ​

1. 整章方法论进化树 ★★★★★ ​

Part I. Basic Concepts ​

2. 什么是 Pattern？★★★★☆ ​

3. 为什么 Pattern Mining 重要？★★★☆☆ ​

4. Transactional Database ★★★★☆ ​

5. Itemset 与 -Itemset ★★★★★ ​

6. Support：整个章节最基本的量 ★★★★★ ​

6.1 Absolute support ​

6.2 Relative support ​

7. Frequent Itemset ★★★★★ ​

7.1 课件例子 ​

8. Frequent Itemset → Association Rule ★★★★★ ​

9. Association Rule 的 Support 和 Confidence ★★★★★ ​

9.1 Rule support ​

9.2 Confidence ★★★★★ ​

10. Association Rule Mining 的正式问题 ★★★★★ ​

10.1 课件例子 ​

Beer → Diaper ​

Diaper → Beer ​

Part II. Pattern Explosion 与压缩表示 ​

11. 为什么不能直接枚举所有 frequent patterns？★★★★★ ​

12. Closed Pattern：无损压缩 ★★★★★ ​

12.1 为什么这是一种 compression？ ​

12.2 为什么是 lossless？★★★★★ ​

13. Closed Pattern 的第二个例子 ★★★★☆ ​

14. Max Pattern：进一步压缩，但有损 ★★★★★ ​

14.1 与 Closed 最大区别 ​

14.2 为什么 Max Pattern 是 lossy？ ​

15. Closed vs Maximal ★★★★★ ​

Part III. Efficient Frequent Pattern Mining ​

16. 最重要的理论：Downward Closure / Apriori Property ★★★★★ ​

16.1 最重要的逆否命题 ★★★★★ ​

17. 三条 scalable mining 路线 ★★★★☆ ​

18. Apriori Algorithm ★★★★★ ​

19. Apriori Pseudocode ★★★★★ ​

20. Apriori 完整例题 ★★★★★ ​

Step 1： ​

Step 2：生成 ​

Step 3： ​

21. Apriori Candidate Generation ★★★★★ ​

21.1 Self-join ​

21.2 Pruning ​

22. Candidate Generation 的 join 条件 ★★★★☆ ​

23. Apriori 到底哪里慢？★★★★★ ​

Problem A：Repeated DB scans ​

Problem B：Too many candidates ​

24. Apriori Improvements 概览 ★★★☆☆ ​

25. Partitioning：数据库只扫描两次 ★★★★★ ​

26. Partitioning 两次扫描 ★★★★★ ​

Scan 1 ​

Scan 2 ​

27. Direct Hashing and Pruning (DHP) ★★★★★ ​

27.1 核心思想 ​

27.2 为什么成立？★★★★★ ​

27.3 一个非常容易考的陷阱 ​

28. 从 Apriori 到 ECLAT：为什么要换数据表示？★★★★★ ​

29. ECLAT ★★★★★ ​

29.1 Horizontal representation ​

29.2 Vertical representation ​

30. ECLAT 的 support = set intersection ★★★★★ ​

31. Tid-list 的结构信息 ★★★★☆ ​

32. Diffset ★★★★☆ ​

33. Apriori → ECLAT 的本质演进 ★★★★★ ​

34. FP-Growth：为什么出现？★★★★★ ​

35. FP-Growth Step 1：找 frequent items ★★★★★ ​

36. F-list ★★★★☆ ​

37. 将 transaction 重排序 ★★★★★ ​

38. FP-tree Construction ★★★★★ ​

38.1 最终树结构 ​

39. Header Table ★★★★☆ ​

40. FP-Growth 最难点：Conditional Pattern Base ★★★★★ ​

41. Conditional Databases ★★★★★ ​

42. Recursively Mine Conditional DB ★★★★★ ​

43. 的 conditional database ★★★★★ ​

44. Single-path FP-tree：一个重要 shortcut ★★★★★ ​

45. FP-Growth 的完整逻辑 ★★★★★ ​

46. Apriori vs ECLAT vs FP-Growth ★★★★★ ​

47. 关于 Mining Closed Patterns 的课件范围 ​

Chapter 3 Pattern Mining: Basic Concepts and Methods

0. 本章到底在解决什么问题？★★★★★

1. 整章方法论进化树 ★★★★★

Part I. Basic Concepts

2. 什么是 Pattern？★★★★☆

3. 为什么 Pattern Mining 重要？★★★☆☆

4. Transactional Database ★★★★☆

5. Itemset 与 -Itemset ★★★★★

6. Support：整个章节最基本的量 ★★★★★

6.1 Absolute support

6.2 Relative support

7. Frequent Itemset ★★★★★

7.1 课件例子

8. Frequent Itemset → Association Rule ★★★★★

9. Association Rule 的 Support 和 Confidence ★★★★★

9.1 Rule support

9.2 Confidence ★★★★★

10. Association Rule Mining 的正式问题 ★★★★★

10.1 课件例子

Beer → Diaper

Diaper → Beer

Part II. Pattern Explosion 与压缩表示

11. 为什么不能直接枚举所有 frequent patterns？★★★★★

12. Closed Pattern：无损压缩 ★★★★★

12.1 为什么这是一种 compression？

12.2 为什么是 lossless？★★★★★

13. Closed Pattern 的第二个例子 ★★★★☆

14. Max Pattern：进一步压缩，但有损 ★★★★★

14.1 与 Closed 最大区别

14.2 为什么 Max Pattern 是 lossy？

15. Closed vs Maximal ★★★★★

Part III. Efficient Frequent Pattern Mining

16. 最重要的理论：Downward Closure / Apriori Property ★★★★★

16.1 最重要的逆否命题 ★★★★★

17. 三条 scalable mining 路线 ★★★★☆

18. Apriori Algorithm ★★★★★

19. Apriori Pseudocode ★★★★★

20. Apriori 完整例题 ★★★★★

Step 1：

Step 2：生成

Step 3：

21. Apriori Candidate Generation ★★★★★

21.1 Self-join

21.2 Pruning

22. Candidate Generation 的 join 条件 ★★★★☆

23. Apriori 到底哪里慢？★★★★★

Problem A：Repeated DB scans

Problem B：Too many candidates

24. Apriori Improvements 概览 ★★★☆☆

25. Partitioning：数据库只扫描两次 ★★★★★

26. Partitioning 两次扫描 ★★★★★

Scan 1

Scan 2

27. Direct Hashing and Pruning (DHP) ★★★★★

27.1 核心思想

27.2 为什么成立？★★★★★

27.3 一个非常容易考的陷阱

28. 从 Apriori 到 ECLAT：为什么要换数据表示？★★★★★

29. ECLAT ★★★★★

29.1 Horizontal representation

29.2 Vertical representation

30. ECLAT 的 support = set intersection ★★★★★

31. Tid-list 的结构信息 ★★★★☆

32. Diffset ★★★★☆

33. Apriori → ECLAT 的本质演进 ★★★★★

34. FP-Growth：为什么出现？★★★★★

35. FP-Growth Step 1：找 frequent items ★★★★★

36. F-list ★★★★☆

37. 将 transaction 重排序 ★★★★★

38. FP-tree Construction ★★★★★

38.1 最终树结构

39. Header Table ★★★★☆

40. FP-Growth 最难点：Conditional Pattern Base ★★★★★

41. Conditional Databases ★★★★★

42. Recursively Mine Conditional DB ★★★★★

43. 的 conditional database ★★★★★

44. Single-path FP-tree：一个重要 shortcut ★★★★★

45. FP-Growth 的完整逻辑 ★★★★★

46. Apriori vs ECLAT vs FP-Growth ★★★★★

47. 关于 Mining Closed Patterns 的课件范围