下面这份笔记严格以你上传的《Chap4 — Pattern Mining: Advanced Methods》为主线整理。我会把课件里分散的内容重构成“为什么旧方法不够 → 新方法解决什么 → 数学性质为什么允许剪枝 → 后续方法又解决了什么”的演进链，而不是逐页复述。课件中只出现名称、没有进一步展开的内容，我也会明确标出来，不用课外知识偷偷补成“课件内容”。

重要程度统一标记为：

★★★：期末必须掌握，尤其容易出定义题、判断题、计算题、算法比较题。
★★☆：需要理解机制、例子和 Why。
★☆☆：应用、背景、论文名或扩展知识，知道定位即可。

Chapter 4 — Pattern Mining: Advanced Methods

0. 本章到底在解决什么？——从“普通频繁项集”向真实世界推进

上一阶段的 frequent pattern mining 通常隐含了几个非常强的假设：

item 是平坦的，没有层级；
所有 item 使用同一个 min_sup；
数据主要是 categorical / binary；
“频繁”就意味着“有趣”；
把所有 frequent patterns 输出出来是可接受的；
用户没有额外约束；
itemset 没有顺序；
pattern 的结构只是集合，而不是 sequence / graph。

本章就是逐个拆掉这些假设。

整个“进化树”可以记成：

text

Basic Frequent Itemset Mining
│
├── ① Pattern 本身更加复杂
│   ├── Flat items
│   │     ↓
│   ├── Multi-level associations
│   ├── Multi-dimensional associations
│   ├── Quantitative associations
│   ├── Rare patterns
│   └── Negative correlations
│
├── ② 输出太多
│   ├── All frequent patterns
│   │     ↓
│   ├── Closed / Max patterns
│   │     ↓
│   ├── δ-cover compressed patterns
│   └── Redundancy-aware Top-k
│
├── ③ 搜索空间太大，而且用户有需求
│   ├── Mine first → filter later
│   │     ↓
│   └── Constraint-based mining
│         ├── Anti-monotone
│         ├── Monotone
│         ├── Convertible
│         ├── Data anti-monotone
│         ├── Succinct
│         └── Multiple constraints
│
├── ④ 集合没有顺序
│   ├── Itemsets
│   │     ↓
│   └── Sequential patterns
│         ├── GSP
│         ├── SPADE
│         ├── PrefixSpan
│         └── CloSpan
│
├── ⑤ Sequence 仍然不够表达复杂关系
│   ├── Sequences
│   │     ↓
│   └── Graph patterns
│         ├── Apriori-based AGM/FSG
│         ├── gSpan
│         └── CloseGraph
│
└── ⑥ 真正落地
    ├── Graph indexing / similarity search
    ├── Software copy-paste bug detection
    └── Phrase mining / ToPMine

这棵树实际上就是整章最核心的逻辑。

Part I. Mining Various Kinds of Patterns

1. Multi-Level Association Mining

重要度：★★★

1.1 Why：普通 itemset mining 为什么不够？

现实中的 item 往往存在 concept hierarchy：

text

Milk
├── 2% Milk
└── Skim Milk

更具体还可以：

text

Milk
└── 2% Milk
    └── Dairyland 2% Milk

因此：

milk
2% milk
Dairyland 2% milk

不是三个完全独立的 item，而存在 ancestor / descendant 关系。

问题变成：

一个 support threshold 能不能同时适用于所有层级？

课件例子：

如果所有层级统一：

则 Skim Milk 被删除。

但更细粒度的商品本来就天然拥有更低 support。

1.2 Uniform support → Level-reduced support

方法 A：Uniform minimum support

所有层：

例如：

Why it fails

越往 concept hierarchy 下层：

category 越细；
单个 item 占比越低；
support 自然下降。

因此统一阈值容易删除：

稀有但非常合理的细粒度 pattern。

方法 B：Level-reduced minimum support ★★★

令层级为：

课件例子：

于是：

Milk：10% → frequent
2% Milk：6% → frequent
Skim Milk：2% → 也 frequent

核心直觉：

越具体，预期 support 越低，所以 threshold 也应降低。

1.3 Shared multi-level mining ★★☆

如果每层完全独立 mining，计算重复。

课件提出：

Shared multi-level mining

基本思想：

使用最低的 support threshold：

先尽可能保留候选，再根据具体 level 的 threshold 判断。

也就是：

text

最低阈值保证“不漏”
        ↓
共享 candidate/search structure
        ↓
各层再根据自己的 min_sup 判断

2. Multi-Level Association 中的 Redundancy

重要度：★★★

层级结构带来的第二个问题：

descendant rule 很可能只是 ancestor rule 的自然细化，而没有提供新信息。

课件例子：

support = 8%，confidence = 70%。

规则 (2)：

support = 2%，confidence = 72%。

已知：

2% milk 大约占所有 milk 的。

那么从 ancestor rule 预测 descendant rule：

而实际也是 2%。

同时：

所以规则 (2) 没告诉我们什么特别新的事情。

Redundant rule 的直觉定义

一个 descendant rule 如果：

support 接近 ancestor rule 所预测的 expected support；
confidence 与 ancestor rule 类似；

那么该 rule 可以视为 redundant。

课件最后的问题

Rule (1) 是 rule (2) 的 ancestor，应该 prune 哪一个？

答案：

通常 prune descendant rule (2)。

因为 (2) 已可由 (1) + hierarchy 关系大致推出。

保留较一般、能够解释更多情况的 ancestor rule。

3. Customized Minimum Supports

重要度：★★★

这一步实际上是在进一步拆掉：

“同一层所有 item 都应该使用同一个 min_sup”

这一假设。

3.1 Why uniform min_sup fails

例如：

bread
milk

购买频率很高。

但：

diamond
expensive watch

天然非常低频。

如果：

那么 diamond/watch 几乎永远不可能成为 frequent pattern。

但：

low support ≠ unimportant。

3.2 Group-based individualized min-support

课件例子：

即不同 item group 使用不同阈值。

这也是后面 rare pattern mining 的基础。

课件指出：

Existing scalable mining algorithms can be extended to support this setting.

没有进一步给具体新算法。

4. Multi-Dimensional Association Rules

重要度：★★★

前面的购物篮规则实际上几乎都属于一个维度：

都是：

这个 predicate。

4.1 Single-dimensional rule

例如：

只涉及 product / buys dimension。

4.2 Multi-dimensional rule

涉及至少两个 dimensions / predicates。

分两种。

A. Inter-dimension association rule ★★★

没有 repeated predicate：

出现了：

age
occupation
buys

但没有 predicate 重复。

B. Hybrid-dimension association rule ★★★

允许 repeated predicate：

buys 出现了两次。

4.3 Attribute type 决定后续算法

Categorical attributes

例如：

profession
product

值之间没有自然 ordering。

课件指出：

可以使用 data cube 处理 inter-dimensional associations。

Quantitative attributes

例如：

age
salary

具有自然 ordering。

因此不能简单把每个数值当独立类别。

必须考虑：

discretization
clustering
gradient approaches

于是自然进入下一节。

5. Quantitative Association Mining

重要度：★★★

核心问题：

association mining 怎么处理 numerical attributes？

例如：

age = 22
age = 23
age = 24

如果直接作为三个 categorical value，它们之间“距离很近”这一事实完全丢失。

5.1 Static discretization

先人为定义 concept hierarchy。

例如：

再向上概括：

优点

简单；
可解释；
可以复用普通 association mining。

局限

分箱边界是 predefined 的：

不一定符合真实 data distribution。

5.2 Dynamic discretization

根据实际 data distribution 动态决定 intervals。

与 static 的根本差别：

text

Static:
domain knowledge → bins → mining

Dynamic:
data distribution → bins → mining

5.3 Clustering-based association

先做：

one-dimensional clustering

再把 cluster 当作 categorical region 做 association mining。

本质：

5.4 Deviation Analysis

课件开始把关注点从：

“哪些东西经常共同出现？”

转向：

“哪些群体表现得异常不同？”

例如：

而总体：

这不再是普通的 co-occurrence rule，而是 subgroup deviation。

6. Mining Extraordinary Phenomena

重要度：★★★

一个 quantitative rule 可写为：

6.1 LHS 与 RHS 的含义

例如：

LHS：

population 的一个 subset。

RHS：

这个 subset 的 unusual / extraordinary behavior。

6.2 为什么不能只看 mean difference？

如果：

女性平均工资 7
总体 9

并不能自动说明差异可信。

因为可能：

样本数量很小；
sampling variation 很大。

因此课件强调：

Rule 只有通过 statistical test（例如 Z-test），并达到高 confidence 后，才接受。

这里课件只点名了 Z-test，没有给具体 Z statistic 的公式，所以期末按本章课件应记：

text

observed deviation
        ↓
statistical significance test
        ↓
only significant → interesting quantitative rule

不要把“均值不同”直接等价成 interesting rule。

6.3 Subrule

例如 super-rule：

进一步细化：

subrule 是：

super-rule population 的更小 subset，并突出更特殊的 behavior。

6.4 Condition 也可以是 quantitative

例如：

因此：

LHS 并不一定是 categorical predicates。

7. Rare Patterns

重要度：★★★

定义直觉：

support 很低，但仍然 interesting。

例如：

buying Rolex watches。

Rare pattern 的关键不能只是：

然后全部丢掉。

解决思路正是前面的：

individualized / group-based min-support。

所以：

text

Uniform support
      ↓ fails on valuable rare items
Customized support
      ↓
Rare-pattern mining

8. Negative Patterns

重要度：★★★

Rare pattern 与 negative pattern 很容易混。

概念	问题
Rare pattern	单个/组合 pattern 自己出现得少
Negative pattern	两个本来各自常见的 pattern 却很少共同出现

例如：

Ford Expedition：有人买
Ford Fusion：也有人买
但同一个 customer 同时买两辆的概率很低

因此是 negatively correlated。

9. Negative Correlation：第一版定义为什么失败？

这是本节最重要数学点之一。★★★

9.1 Support-based definition

若都频繁，但：

则认为：

negatively correlated。

为什么这个式子合理？

如果 independent：

所以：

意味着 observed co-occurrence 远少于 independence expectation。

它本质上与 lift 的思想有关：

negative correlation 对应：

9.2 Null transaction 问题 ★★★

设：

但：

情况 1：总共 transactions

所以：

于是：

→ negative。

情况 2：增加大量 null transactions

令：

但 A/B/AB 的 count 完全没变。

则：

所以：

反而：

根据旧定义：

不再 negative。

但我们根本没有改变：

A occurrence
B occurrence
A 与 B 的共同 occurrence

只是增加了：

neither A nor B 的 transactions。

因此 correlation classification 居然改变了。

这是不合理的。

9.3 为什么数学上会依赖 null transaction？

写成 count：

而：

两者比值：

注意：

没有消掉。

因此加入 null transactions 改变，就改变指标。

结论 ★★★

Support/lift-based negative correlation definition：

not null-invariant。

10. Kulczynski Measure：Null-Invariant Negative Correlation

重要度：★★★

课件改用：

课件用表示“同时包含 A 与 B 的 pattern”；在概率直觉上就是共同 occurrence。

等价 count 形式：

注意：

完全消失。

因此添加多少 null transactions 都不会变化。

10.1 负相关判定

若：

则 A、B negatively correlated。

其中：

是 negative-pattern threshold。

课件 needle example：

同理：

所以：

无论总 transaction 数是 200 还是，结果都一样。

一个值得你考试时留意的课件细节

课件写：

并写成：

严格数学上：

不是。

因此这里显然是课件阈值符号/数值上的小 typo。

真正要掌握的是：

Kulc 对 null transactions 不敏感。

如果严格使用 <，应令：

或者把判据写成。

Part II. Mining Compressed / Approximate Patterns

11. 为什么需要 compressed patterns？

重要度：★★★

Frequent pattern mining 的另一个严重问题：

pattern explosion。

可能产生大量：

非常相似；
support 接近；
信息高度重复

的 patterns。

12. Closed Pattern vs. Max Pattern 的两种极端

课件例子：

Pattern	Itemset	Support
P1		205227
P2		205211
P3		101758
P4		161563
P5		161576

Closed patterns

该例所有：

都是 closed。

课件评价：

closed pattern emphasizes too much on support。

也就是说，只要 support 有一点差异，可能就保留多个高度相似 pattern。

压缩还不够。

Max pattern

这里最终只剩：

问题：

information loss。

因为最大 pattern 无法恢复很多较小 pattern 的 support 信息。

核心矛盾

text

Closed
压缩太弱
信息较完整
      ↘
       desired balance
      ↗
Max
压缩很强
信息损失严重

课件希望：

作为比较平衡的 representation。

13. Pattern Distance 与 δ-Cover

重要度：★★★

课件定义：

其中：

：两个 patterns；
：支持 pattern 的 transaction 集合；
：该集合大小；
分数部分就是 Jaccard similarity；
是 Jaccard distance。

因此：

若：

说明两者支持 transaction sets 完全相同。

若接近 1：

支持它们的 transactions 几乎不重合。

δ-clustering

给定 representative pattern ，找所有：

能够由表示；
与的 distance 不超过

的 patterns。

即：

构成一个：

-cover / -cluster。

最终：

一个 representative pattern 表示整个 cluster。

δ 的意义

→ 要求更相似

→ clusters 更小

→ representation 更多

→ information loss 较低。

反之：

→ 压缩更强

→ representation 更少

→ approximation 更粗。

这就是本节标题里的 approximate 的主要体现；课件没有另外展开一个独立的“approximate mining algorithm”。

14. Redundancy-Aware Top-k Patterns

重要度：★★☆

单纯 traditional top-k：

只选 significance 最大的 k 个。

问题：

可能前 k 个 pattern 全都来自同一个局部 cluster：

text

很重要
但彼此高度重复

因此真正想要：

课件引入：

MMS — Maximal Marginal Significance

来衡量 pattern set 的 combined significance。

这里课件没有提供 MMS 的明确数学公式，所以期末按课件需要记住其目标，而不是强行背一个本页没有给出的公式：

text

traditional top-k
    → optimize individual significance

redundancy-aware top-k
    → optimize significance + marginal new information

Part III. Constraint-Based Pattern Mining

这是整章算法思想最密集、也最值得考试的部分。

重要度整体：★★★

15. 为什么需要 Constraint-Based Mining？

普通流程：

text

Mine enormous pattern set
        ↓
User filters result

非常浪费。

现实 pattern mining 更像：

user-guided interactive process。

用户会直接告诉系统：

我要什么 data；
哪些 dimensions；
support 多大；
pattern 必须满足什么结构。

因此应该：

Push constraints deeply into mining process.

而不是最后过滤。

16. User-Specified Constraints 的五类

重要度：★★★

1. Knowledge-type constraint

指定 mining task：

classification
association
clustering
outlier detection

2. Data constraint

类似 SQL：

Find products sold together in NY stores this year.

约束：

location
time
subset of database

3. Dimension / level constraint

类似 relational projection。

例如只关心：

region
price
brand
customer category

4. Interestingness constraint

例如：

5. Rule / pattern constraint ★★★

本节重点。

例如：

Small sales $10$)$ triggers big sales $200$)$

接下来的 anti-monotone / monotone / succinct 等全部在解决：

怎么利用 pattern constraint 剪搜索空间？

17. Pattern Anti-Monotonicity

重要度：★★★

这是 Apriori 思想的抽象版本。

17.1 定义

constraint 是 anti-monotone，如果：

若违反，则任何 superset：

也违反。

逻辑写法：

因此：

一旦当前 node 失败，整个 subtree 都可以 prune。

text

S fails
│
├── S+a    prune
├── S+b    prune
└── S+c... prune

这是非常强的 pruning property。

18. Anti-Monotone Examples

18.1

假定 price 均为正：

如果当前：

继续加入正 price item 后：

所以不会恢复。

因此 anti-monotone。

注意 ★★★

课件专门标：

item.price > 0

否则若允许负 price：

加入负值可能把 sum 拉回来。

18.2 Range constraint

定义：

约束：

如果当前 range 已经：

加入更多元素只可能：

保持 max/min；
或把 max 推更高；
或把 min 推更低。

因此：

不会下降。

所以 anti-monotone。

课件：

所以 ab fails，则所有 superset of ab 都 fails。

18.3 非 anti-monotone

如果现在没达到：

后面继续加正 item：

完全可能达到。

所以不能因为当前 fail 就 prune。

19. Support Constraint 为什么是 Anti-Monotone？

重要度：★★★

若：

任何包含的 transaction 必然也包含。

所以：

因此：

如果：

那么：

所以所有 super-pattern 都 infrequent。

这就是：

Apriori property。

极其重要的统一理解

Apriori 并不是一个孤立 trick。

它本质上是：

对 constraint
[ support(S)\ge min_sup ] 使用 anti-monotonicity 进行 pattern-space pruning。

20. Pattern Monotonicity

重要度：★★★

monotone 与 anti-monotone 镜像。

定义

constraint monotone：

若满足，则任何：

都满足。

因此：

当前一旦满足，以后无需再检查这个 constraint。

但：

它通常没有 anti-monotone 那么强的 pruning power。

因为它不能在失败时终止 subtree。

21. Monotone Examples

Example 1

price > 0：

一旦达到，以后只会更大。

Example 2

加入更多 items：

所以一旦 ≤v，以后永远 ≤v。

Example 3

range 加 item 只会不减：

所以一旦满足：

永久满足。

22. Anti-Monotone vs Monotone：必须记的判断原则

aggregate	条件	常见性质
`sum`，值全正		anti-monotone
`sum`，值全正		monotone
`min`		monotone
`min`		anti-monotone
`max`		anti-monotone
`max`		monotone
`range`		anti-monotone
`range`		monotone
`support`		anti-monotone

其中 min/max 的另外两项虽然表中是顺着性质推出来的，本页重点例子是课件出现的那些；考试判断时非常好用。

23. 把 Anti-Monotone Constraint Push 进 Apriori

重要度：★★★

课件例：

并增加：

item price：

因为 price positive，所以：

是 anti-monotone。

例如 singleton：

已经：

不满足 <5。

所以不仅：

可以删，而且：

全不需要生成。

这叫：

constraint pushing / early chopping。

核心不是“最后把不合格 pattern 删除”，而是：

不让这些 pattern 的 descendants 进入 candidate space。

24. Convertible Constraints

这是非常容易出理解题的内容。★★★

有些 constraint 本来：

不是 monotone；
也不是 anti-monotone；

但：

如果给 items 选择正确 processing order，它会变成 monotone / anti-monotone。

这就是：

convertible constraint。

25. avg(S.profit) > 20 为什么可以转换？

课件 item profits：

item	profit
a	40
g	30
h	5
b	0
f	-5
d	-15
c	-20
e	-30

先按 profit descending：

考虑：

其中：

例如：

所以违反：

因为后续允许添加的 item 全部排在 b 后面：

都不可能把 average 拉回 >20。

数学直觉

设当前 prefix：

且：

由于数据 descending：

于是：

所以失败后不会恢复。

于是：

在这个特定 growth order 下，avg > 20 变成 anti-monotone。

26. 为什么 item reordering 不能直接套到 Apriori？

重要度：★★★

这是很容易踩坑的地方。

课件：

而：

但是：

注意：

af fails
gf fails
但 agf succeeds

Apriori candidate generation 要求 size-3 candidate 的所有相关 size-2 subsets surviving。

如果把：

因为 constraint 失败而删掉：

Apriori 不会生成 agf。

但 agf 明明合法。

因此

convertible anti-monotonicity 不是：

对任意 subset lattice 都成立。

而是：

只在指定 ordered pattern-growth / projected-DB expansion 下成立。

这是 p21 和 p22 合起来真正想教的东西。

27. Pattern Space Pruning vs Data Space Pruning

这里开始出现另一条非常重要的分支。★★★

到目前为止：

我们都在删 patterns。

但能不能直接把：

不可能有用的 transactions

也删掉？

这就是 data-space pruning。

28. Data Anti-Monotonicity

重要度：★★★

定义：

在 mining 过程中，如果某条 data entry ：

对当前 pattern ，在 constraint 下不可能产生任何合法 extension，

那么它对：

的 superpatterns

也不会有贡献。

因此可以删掉整个 transaction 。

29. Example：sum(S.Profit) ≥ 25

课件 T30：

profit：

constraint：

即使选最好的 subset：

其余都是 negative。

所以：

T30 中根本不存在一个 subset 能达到 25。

因此 T30 整条 transaction 可以删除。

30. Data anti-monotone 的另外两个例子

Example 2

如果一个 transaction 中每个 item：

则其中任何 subset：

不可能满足。

整条 transaction prune。

Example 3

如果整条 transaction 的 maximum possible range：

其任何 subset 的 range 更不可能 >25。

因此 transaction prune。

31. Pattern Anti-Monotonicity vs Data Anti-Monotonicity

重要度：★★★

	Pattern anti-monotonicity	Data anti-monotonicity
剪什么	candidate patterns	transactions
空间	pattern/search space	data space
判断对象	当前 pattern	当前 data entry
核心逻辑	pattern fails → all descendants fail	transaction 无法再支持合法 extension → transaction 无用
效果	不扩展 subtree	减少后续扫描/投影数据量

一句话：

Pattern anti-monotonicity 是“这条搜索分支没前途”。

Data anti-monotonicity 是“这条数据记录对当前分支没用了”。

32. Data-Space Pruning 必须 Recursive

重要度：★★★

这是课件非常漂亮的一个 cascading pruning 例子。

constraint：

看：

b-projected database。

一开始 T10 中有：

所以似乎仍然可能构成大的 range。

但在 b-projected DB 中：

而：

于是 a 先被频率剪掉。

32.1 删除 a 后发生什么？

T10 剩：

当前 prefix b：

最大：

最小：

所以：

而 constraint 是：

失败。

因此：

T10 现在整个 transaction 可以 prune。

32.2 第二层 cascade

T10 被删掉后：

h 的 support 进一步下降。

于是：

又可以被 min_sup prune。

最终 b-projected DB 被压缩到：

single FP-tree branch cdfg:2

课件总结非常重要：

对 T10 的 data pruning，只有在 a 被 min_sup 先 prune 后才变得有效。

这说明：

text

pattern pruning
      ↓
changes projected data
      ↓
enables data pruning
      ↓
changes supports
      ↓
enables more pattern pruning
      ↓
...

因此应：

recursively interleave pattern-space and data-space pruning。

33. Succinct Constraint

重要度：★★★

定义：

如果 constraint 可以通过直接操作 data 来 enforce，则称 succinct。

换句话说：

不需要先生成大量 candidates 再判断。

33.1 Containing item

想找：

直接：

mine -projected DB。

这是 data-space pruning。

33.2 Without item

想找：

直接：

从 DB 中去掉 i，再 mining。

这是 pattern-space pruning。

33.3

succinct。

因为：

最终 pattern 必须至少包含一个 price ≤ v 的 item。

所以可以直接让满足：

的 items 作为合法 projection / growth anchor。

33.4 非 succinct

无法一开始仅根据 single item 决定。

因为：

会随着 pattern growth 一直累积。

所以：

不能预先通过简单 data manipulation 完全 enforce。

34. Constrained FP-Growth Example

重要度：★★★

课件：

item prices：

所以合法 pattern 必须含：

或：

至少一个。

因此只需要：

1-projected DB
2-projected DB

而不必以：

作为根 prefix 开独立 projected DB。

注意：

这不是说 pattern 中不能出现 3、4、5。

例如 1-projected DB 的 suffix 仍可含：

只是任何合法 pattern 都必须由：

“进入”搜索空间。

这就是 succinct constraint push deep。

35. Constraint 分类总表

重要度：★★★

课件最终将 constraint pruning 分成两大空间。

Pattern-space constraints

Anti-monotonic

fail → terminate subtree。

Monotonic

success → no need to check again。

Convertible

通过 ordering 转成：

monotonic
或 anti-monotonic。

Succinct

通过直接 data manipulation enforce。

Data-space constraints

Data succinct

在 mining 开始就可提前缩小 data space。

Data anti-monotonic

某 transaction 无法支持 constraint：

transaction prune。

36. Multiple Constraints 怎么办？

重要度：★★★

多个 constraints 可能要求不同 item order。

例如：

需要：

profit descending。

而：

要变成合适的 convertible constraint，可能希望：

price ascending。

两套 ordering 冲突。

Solution

选择：

pruning power 更强的 constraint 先执行。

课件假设：

更强。

于是：

全局按 profit descending；
先使用；
生成 projected DB；
对每个 projected DB 再按 price ascending；
使用。

核心思想：

Constraint order 本身也是 query optimization problem。

即：

Part IV. Sequential Pattern Mining

整体重要度：★★★

37. 从 Itemset 到 Sequence：核心变化是什么？

普通 itemset：

没有 order。

sequence：

与：

不同。

一句话：

Sequential = order really matters.

课件例：

不能随便交换。

38. Sequential Pattern vs Time Series

重要度：★★★

Sequential pattern mining：

关心 relative order。

不强调具体发生时间是多少。

例如：

text

Laptop → Camera → Smartphone

重要的是 order。

Time-series analysis：

actual time/timestamp 本身也重要。

这是考试很容易出的概念区别。

39. Sequential Pattern Applications

重要度：★☆☆

课件列：

Customer shopping
Medical treatment
Natural disaster stages
Scientific experiment steps
Stock market movement
DNA / protein sequences

这些例子共同强调：

swapping order changes semantic meaning。

40. Sequence 的形式定义

重要度：★★★

一个 sequence 是：

ordered list of elements。

每个 element：

unordered set of items/events。

例如：

外层：

表示 element 的 order。

括号：

表示：

a 与 b 属于同一个 element。

括号内部无序：

课件因此统一按 alphabetic order 写。

41. Subsequence

课件例：

是：

的 subsequence。

形式上可理解为：

若：

和：

存在：

使：

则：

这里的 formal notation 是把课件的图示关系数学化。

42. Sequential Support

重要度：★★★

support 统计的是：

有多少 sequences 包含这个 subsequence。

不是：

它总共出现多少次。

定义：

或者比例：

课件：

时：

在至少两个 sequences 中出现，所以是 sequential pattern。

43. Sequential Apriori Property

重要度：★★★

仍然成立：

如果 subsequence infrequent：

则任何 supersequence：

都不可能 frequent。

因为：

所以：

这使传统 frequent-pattern 思想可以迁移到 sequences。

44. Sequential Algorithms 的演进树

这是必须形成直觉的一段：

text

GSP
Apriori + candidate generation
        ↓ problem:
many candidates + repeated DB scans

SPADE
vertical SID/EID format
        ↓
support via vertical joins

PrefixSpan
pattern growth + projected DB
        ↓
no candidate generation

Pseudo-projection
        ↓
avoid copying suffixes

CloSpan
        ↓
directly mine closed sequences
        ↓
reduce redundant output/search

45. GSP — Apriori-Based Sequential Pattern Mining

重要度：★★★

GSP = Generalized Sequential Patterns。

基本流程：

找 frequent length-1 sequences；
用它们生成 length-2 candidates；
scan DB count support；
prune；
用 frequent length-2 生成 length-3；
重复。

46. GSP Length-1 Example

初始：

support：

singleton	support
a	3
b	5
c	4
d	3
e	3
f	2
g	1
h	1

于是：

pruned。

frequent singletons：

共：

个。

47. GSP length-2 candidate 数量

重要度：★★★

sequence length 2 有两种形式。

A. 两个 ordered elements

例如：

表示：

注意不是 (ab)。

可以：

所以对于个 frequent items：

种。

B. 同一个 unordered element

例如：

因为：

而且一个 set 里不重复 item，所以数量：

总数

没有 singleton pruning：

所以：

有 pruning：

这是课件明确展示的计算，非常适合计算题。

48. GSP 的完整迭代结果

课件示例：

Scan 1

8 candidates：

→ 6 frequent length-1.

Scan 2

51 candidates：

→ 19 frequent length-2。

其中：

10 candidates 根本没有出现在 DB。

Scan 3

46 candidates：

→ 20 frequent length-3。

其中：

20 candidates 根本不在 DB。

Scan 4

8 candidates：

→ 7 frequent length-4。

Scan 5

1 candidate：

→ 1 frequent length-5。

GSP 最大痛点

从这些数字可以直接看出：

Candidate generation 很浪费。

尤其：

很多 candidate 从未出现；
每层还需要 scan DB。

这正是后续算法演进的原因。

49. SPADE — Vertical Data Format

重要度：★★★

GSP 还是 horizontal sequence DB。

SPADE 改为：

其中：

SID = Sequence ID
EID = Element ID

例如：

text

SID=1:
<a(abc)(ac)d(cf)>

a 出现在：

等等。

49.1 核心思想

sequence pattern support 可以通过：

vertical id-list joins

来计算。

例如要检查：

需要同一 SID 内：

因为 a 必须先于 b。

如果：

则对应：

因此 sequence constraint 转成：

对 SID/EID lists 做 join + ordering comparison。

49.2 相比 GSP

GSP：

text

candidate
   ↓
scan raw DB
   ↓
support

SPADE：

text

vertical ID lists
   ↓
join/intersect
   ↓
support

但它仍然具有：

Apriori-style one-item-at-a-time pattern growth。

50. PrefixSpan：真正摆脱 candidate generation

重要度：★★★

PrefixSpan = Prefix-projected Sequential Pattern Mining。

思想来自 FP-Growth：

不显式生成大批 candidate。

而是：

按 prefix partition search space。

51. Prefix 与 Suffix

课件 sequence：

可能 prefix：

等等。

给定 prefix 后：

只保留可以继续扩展这个 prefix 的 suffix。

52. Projection 例子

对：

prefix：

其 suffix：

prefix：

suffix：

课件中的：

是 placeholder：

表示 prefix 在这个 element 中已经消费了一部分 item，但当前 element 仍然可以继续扩展。

53. PrefixSpan Algorithm

重要度：★★★

Step 1：

找 length-1 frequent sequences：

Step 2：

把整个 pattern space 分为：

-projected DB
-projected DB
…
-projected DB

然后每个 projected DB：

recursive mining。

53.1 a-projected DB

课件得到：

从这里直接找到可扩展的 frequent items。

得到 length-2：

再继续：

aa-projected DB
af-projected DB
...

54. PrefixSpan 的核心优势

课件明确写两点：

1.

No candidate subsequences to be generated.

2.

Projected DBs keep shrinking.

因此从 GSP 到 PrefixSpan 的方法论变化：

text

Breadth-first candidate enumeration
              ↓
Recursive search-space projection

这也是整个 frequent mining 演进里最反复出现的范式变化：

Apriori → Pattern Growth。

55. PrefixSpan 的新瓶颈：Projected DB Construction

重要度：★★★

PrefixSpan 虽然摆脱 candidates，却引入：

大量 recursive projected DBs。

而 suffix 高度重复。

例如：

原始：

a-projection：

ab-projection：

可以看出：

后半段几乎被不停复制。

56. Physical Projection vs Pseudo-Projection

重要度：★★★

Physical projection

真的复制 suffix 数据。

适合：

数据太大，无法整体留在 main memory。

Pseudo-projection

如果 DB 可放入 memory：

不复制 suffix。

只保存：

pointer to original sequence；
suffix offset。

例如：

这样递归 projection 只移动 offset。

作用

显著减少：

memory duplication
copying cost

57. CloSpan：Closed Sequential Patterns

重要度：★★★

PrefixSpan 解决计算问题，却仍可能输出：

非常多 redundant frequent sequences。

于是像 itemset 中 closed pattern 一样，定义 closed sequence。

57.1 定义

sequential pattern 是 closed，如果不存在 superpattern：

满足：

也就是说：

无法在保持同一 support 的情况下继续扩展。

57.2 Example

则：

不是 closed，因为：

是它的 superpattern 且 support 同为 20。

而：

可以是 closed：

因为再扩到 abcde，support 已降为 15。

58. 为什么 mine closed patterns？

两个目的：

reduce redundant patterns；
retain same expressive power。

这是：

lossless compression

的思想。

59. CloSpan Property P

重要度：★★★

课件给出 Property P：

若：

则在课件讨论的 projected-database 条件下：

当两个 projected DB 的 size 相同时，可利用它们的等价关系判断 redundant search。

课件表述为：

并据此采用：

Backward Subpattern Pruning
Backward Superpattern Pruning

来删除重复搜索空间。

直觉：

如果一个更长 pattern 与较短 pattern 对应完全相同的 projected support information，那么从短 pattern 再重新探索一遍 descendants，很可能只是在重复长 pattern 那一支已经能覆盖的搜索。

60. Constraint-Based Sequential Pattern Mining

重要度：★★★

sequence mining 中前面的 constraint ideas 基本都可以迁移。

课件明确列：

Anti-monotonic

例如：

S 违反后，supersequences 也违反。

Monotonic

例如：

一旦 element 数超过 5：

extension 仍然超过 5。

以及：

一旦 pattern 已包含这些 items：

extension 仍包含。

Data anti-monotonic

例如：

某条 input sequence 对当前 pattern 已不存在满足该 threshold 的可能：

可删 data sequence。

Succinct

例如：

可直接操纵 / project 数据。

Convertible

课件列：

核心：

projection 时使用 attribute-value order，而不是原始 sequence temporal order 来辅助 constraint pushing。

61. Timing-Based Constraints

重要度：★★★

sequence 相比 itemset 多了独有 constraints。

61.1 Order constraint

例如：

表示：

algebra / geometry 必须先于 calculus。

课件将违反 order 的 sub-pattern 用 anti-monotonic 思路 prune。

61.2 Min-gap / Max-gap

限制 pattern 相邻/指定 elements 之间的间隔：

例如：

课件归入：

succinct，可在 pattern growth 时直接 enforce。

61.3 Max-span

第一 element 到最后 element 的最大时间差：

一旦 first element 确定：

可以直接控制 extension 是否超过 60 days。

因此 succinct。

61.4 Window size

普通 sequential pattern 的同一 element：

意味着 a,b 同一 event。

加入 window constraint 后：

它们不必 exact same timestamp，只要时间差 ≤ window size。

例如：

会产生不同的 event merging possibilities。

62. Episode Mining

重要度：★★☆

Sequential pattern 之外还有：

episodes / regular expressions。

Serial episode

意思：

total order。

Parallel episode

表示：

A 与 B 之间只有 partial order / 可任意顺序。

Regular expression

课件：

含义：

A/B 可任意 order；
：C 出现任意次数；
(DE)：D、E 在同一 time window；
还可以额外要求：

这说明 sequence mining 最终可以同时组合：

structural constraints
temporal constraints
aggregate constraints。

Part V. Subgraph Pattern Mining

63. 为什么从 Sequence 继续走向 Graph？

重要度：★★★

sequence 只能表达：

但现实关系可能：

一对多；
环；
arbitrary topology。

例如：

molecule
protein interaction network
collaboration network
web graph

都不能压成单一顺序而不丢结构。

所以 pattern representation 再升级：

64. Frequent Subgraph 定义

重要度：★★★

设 labeled graph database：

subgraph 的 supporting graph set：

support：

如果：

则是 frequent subgraph。

课件例中：

对应 3 个 graph 中有 2 个包含该 subgraph。

Alternative setting

除了：

many small graphs

还可以 mining：

one single large graph / network 中的 frequent subgraphs。

65. Graph Mining Applications

重要度：★☆☆

包括：

gene networks
protein interactions
metabolic pathways
chemical compounds
social networks
web communities
cell-phone networks
computer networks
XML / Semantic Web
program execution flow

graph patterns 也可作为：

classification
clustering
compression
comparison
correlation analysis
indexing
similarity search

的 building blocks。

66. Graph Mining 的算法难点

重要度：★★★

课件把设计维度总结得很好：

candidate generation：
- Apriori
- pattern growth
search order：
- BFS
- DFS
duplicate subgraph elimination：
- passive
- active
support calculation：
- store embeddings 等
pattern discovery order：
- path → tree → graph

最大的额外麻烦来自：

graph isomorphism + same graph can be generated in many ways。

这在 itemset/sequence 中没有这么严重。

67. Apriori-Based Graph Mining

重要度：★★★

思想仍然：

从 frequent size-k graphs 生成 size-(k+1) candidates。

流程：

text

candidate generation
        ↓
candidate pruning
        ↓
support counting
        ↓
candidate elimination

Graph Apriori property

核心正确方向是：

如果：

是 frequent graph，则其 subgraphs 都 frequent。

因此：

如果某 subgraph 不 frequent，则包含它的 supergraph 不可能 frequent。

课件措辞上的一个严谨提醒

课件 P55 写：

“A size-k subgraph is frequent iff all its subgraphs are frequent.”

严格来说：

成立。

但反过来：

一般并不保证。

所有 subgraphs frequent 只是：

G 有资格成为 candidate。

仍要做 support counting。

这从同一页后面的：

candidate → support counting → candidate elimination

也能看出来。

期末如果考算法逻辑，记住这个严格版本更安全。

68. AGM vs FSG

重要度：★★☆

两类 graph candidate growth。

AGM

vertex growing：

每次增加一个 vertex。

FSG

edge growing：

每次增加一个 edge。

课件指出：

edge growing 实验上更 efficient。

两者本质仍是：

breadth-first + Apriori joining two size-k graphs。

问题：

一个 size-(k+1) graph 可以从很多不同 size-k graphs join 出来。

因此 duplicate candidates 非常严重。

69. Graph Pattern-Growth

重要度：★★★

为了摆脱 Apriori breadth-first candidate explosion：

depth-first graph growth。

从：

扩成：

马上继续：

新问题

同一个 graph 仍然可以：

经不同 extension orders 被生成很多次。

于是关键问题变成：

如何为 graph growth 定义一个 canonical generation order？

这引出 gSpan。

70. gSpan

重要度：★★★

gSpan 的核心：

Right-most path extension。

而不是任意加边。

70.1 DFS code

通过 depth-first traversal：

把 graph flatten 成 edge sequence。

课件例：

这就是一个 DFS-code-like representation。

70.2 Right-most path

课件定义：

root 到 right-most leaf 的 path。

并在 growth 时只允许：

right-most-path extension。

效果：

大幅减少同一个 graph 被不同 growth paths 重复产生。

70.3 Completeness

限制 extension 不能把合法 graph 漏掉。

课件强调：

enumeration using right-most path extension is complete。

所以同时获得：

reduced duplicates；
complete enumeration。

这就是 gSpan 相比 unrestricted depth-first growth 的核心贡献。

71. 从 gSpan 到 CloseGraph

重要度：★★★

gSpan：

解决 graph search efficiency。

但仍输出：

所有 frequent graphs。

同样有 redundancy explosion。

所以再次引入 closed-pattern 思想。

72. Closed Graph Definition

frequent graph closed：

不存在 supergraph：

同时：

所以：

G 不能在不降低 support 的情况下继续扩展。

Closed graph：

不输出 non-closed graphs；
仍具有 lossless compression 意义。

73. CloseGraph

重要度：★★★

CloseGraph：

extend gSpan to mine closed graph patterns directly。

课件考虑：

且两者 frequent。

如果：

每个包含的数据图也包含（两者支持图集合相同），

那么：

从单独继续 grow 的大部分 children 不可能提供新的 closed pattern。

这里应按 support graph / occurrence set 理解；不必要求每一个具体 embedding 都能扩成同一个。

因此可以 early terminate G branch。

本质和 CloSpan 是同一个思想：

text

same occurrence information
        ↓
short pattern is redundant
        ↓
prune its descendants

只是对象从：

sequence projected DB

变成：

graph embeddings/occurrences。

Part VI. Graph Pattern Applications

74. Application I — Graph Indexing

重要度：★★☆

问题：

给 query graph：

寻找 graph DB 中所有：

的 graphs。

74.1 为什么 path index 不够？

如果只 index：

C
C–C
C–C–C
C–C–C–C

很多不同 graph 都包含这些 paths。

因此 path index 无法有效 prune。

课件例：

path-index 无法排除 graph (a)、(b)，但实际上只有 (c) 包含完整 query Q。

因此：

应 index substructures，而不只是 paths。

75. gIndex

重要度：★★★

但新的问题：

所有 substructures 数量爆炸。

gIndex 的核心：

只 index frequent + discriminative substructures。

75.1 Frequent substructures

不能把所有结构都 index。

课件采用：

size-increasing support threshold。

图中：

直觉：

大结构通常已能被自己的 smaller substructures 很好地索引，因此不需要把所有稀有大 graph pattern 都纳入 index。

75.2 Discriminative substructure

假设已有 selected features：

候选新 structure：

并有：

额外 indexing power 用：

来衡量。

如果：

很小：

意味着：

已知现有 features，并不能很好预测 x。

所以 x 带来：

new discriminative information。

应加入 index。

反之，如果条件概率很高：

x 基本可以由已有 features 推断，加入它价值较低。

76. Substructure Similarity Search

重要度：★★☆

Exact graph containment 不够。

可能要求：

找与 query graph “结构相似”的 graphs。

直接：

text

每个 DB graph
      ↓
compute expensive graph similarity

太慢。

但如果把所有可能相似 subgraphs 全 index：

number explodes。

课件解决：

Keep graph index, but select features in query space。

77. Feature-Based Similarity

把每个 graph 表示成 feature vector：

例如：

表示是否包含 feature 。

graph similarity：

用两个 feature vectors 的 distance 表示。

77.1 Pruning Example

query 有：

个 features。

允许：

最多 missing 2。

因此 candidate graph 至少需要命中：

个。

课件 matrix 中：

：命中 2 → prune
：命中 2 → prune
：命中 2 → prune
：命中 3 → keep
：命中 4 → keep

于是 expensive graph similarity 只需要对：

继续做。

这本质还是：

cheap feature bound → safe pruning → expensive exact/approximate verification。

Part VII. Application Example I — Software Bug Detection

78. Pattern Mining 为什么能找 Bug？

重要度：★★☆

一个很漂亮的思想：

正常代码存在大量重复 programming conventions。

因此频繁 pattern：

很可能代表正常 protocol / idiom。

偏离 frequent pattern 的行为：

可能是 bug。

课件列：

frequent itemsets → programming rules
frequent subsequences → function precedence protocols
itemset/subgraph → neglected conditions
revision-history mining
copy-paste pattern mining

重点展开：

CP-Miner。

79. Copy-Paste Bugs

重要度：★★★

课件数据：

Linux file system：约 12% copy-pasted code
X Window：约 19%

copy-paste 的危险：

programmer 复制后忘记修改某些 identifier。

叫：

forget-to-change bug。

80. CP-Miner Pipeline

text

source code
   ↓
tokenization
   ↓
statement → numeric ID
   ↓
program → long sequence
   ↓
cut into blocks
   ↓
sequence database
   ↓
sequential pattern mining
   ↓
copy-paste segments
   ↓
identifier mapping conflicts
   ↓
bug candidates

81. Building Sequence DB from Code

重要度：★★☆

每条 statement：

tokenize components。

不同：

operators
constants
keywords

→ 不同 token。

但：

same type of identifiers → same token。

因此不同 variable names 不会阻止两段结构等价的代码被识别为 repeated pattern。

接着 hash statement：

于是整个 program：

long integer sequence。

然后按 blocks 切开：

sequence database。

82. Sequence Mining 修改：Max Gap

重要度：★★★

普通 subsequence 允许 pattern elements 相距很远。

但 source-code copy-paste 要求：

duplicated statements 应彼此接近。

因此 CP-Miner：

constrain max gap。

这样不会把文件中远距离、碰巧相同的几行拼成虚假 copy-paste region。

83. Composing Larger Segments

初步挖出的 copy segments 可能是碎片。

所以：

repeatedly combine neighboring copied segments。

形成更大的 copy-paste regions。

84. Forget-to-Change Detection

对两段 copied code 建 identifier mapping。

正常：

text

a1 ↔ b1
a2 ↔ b2
a3 ↔ b3

如果某个 identifier 没跟着其他 identifiers 一起 rename：

conflict。

课件定义：

例子：

1 out of 4：

若：

则 report bug。

为什么不把 ratio=1 也报告？

因为：

全都没改，很可能本来就应该保持一致。

真正可疑的是：

大多数都改了，只有少数漏改。

这就是 pattern-based anomaly detection 的核心。

Part VIII. Application Example II — Phrase Mining

85. 为什么不能只用 Unigram？

重要度：★★☆

单词往往 ambiguous。

例如：

United

可能是：

United States
United Airlines
United Parcel Service

而 phrase：

“United States”

通常是更完整、更 unambiguous 的 semantic unit。

因此目标：

提高处理 unstructured text 的：

semantic quality
efficiency

86. 从 Frequent Pattern Mining 到 Phrase Mining

重要度：★★★

General principle：

利用 information redundancy + data-driven criteria 找 phrase boundaries 和 salience。

三个核心 ideas：

frequent pattern mining + collocation analysis；
phrasal segmentation；
quality phrase assessment。

方法演进

ToPMine

no training data。

SegPhrase

tiny training set。

AutoPhrase

distant supervision，例如 Wikipedia。

可以看成：

text

unsupervised
    ↓
small supervision
    ↓
distant supervision

87. ToPMine

重要度：★★★

ToPMine pipeline：

text

corpus
  ↓
frequent contiguous pattern mining
  ↓
candidate phrases + raw counts
  ↓
agglomerative adjacent-word merging
  ↓
document segmentation
  ↓
rectified phrase frequency
  ↓
phrase ranking
  ↓
bag of phrases
  ↓
PhraseLDA

88. Frequent Contiguous Pattern Mining

和普通 frequent itemset 最大区别：

phrase 必须 contiguous。

例如：

support vector machine

必须三个词连续。

因此 candidate generation：

extract frequent contiguous word patterns。

89. Agglomerative Merging

从 unigram 开始：

text

support | vector | machine

根据 adjacent components 的 significance：

text

support vector | machine
        ↓
support vector machine

逐步 merge。

当 score 低于 threshold：

stop merging。

90. Collocation

重要度：★★★

定义：

word sequence 的 co-occurrence 显著高于随机 expectation。

例如：

made an exception
strong tea

不是简单地“每个词都 frequent”，而是：

它们一起出现得异常多。

课件列出的 statistical measures：

mutual information
t-test
z-test
chi-squared test
likelihood ratio

这些都可以用于：

phrase segmentation / collocation decisions。

91. Phrase Significance Score

重要度：★★★

课件给：

其中：

：左 phrase/unit；
：右 phrase/unit；
：两者 contiguous concatenation；
：该拼接在 corpus 中实际出现频率；
：在 null/background expectation 下的 expected frequency；
：observed occurrence 相对于 expectation 的 significance score。

课件没有进一步给的具体计算公式，所以不应强行加一个未在 slide 里定义的版本。

直觉：

→ 两者共同出现远超 random expectation

→ 更应该 merge。

91.1 Threshold

课件图中示例：

例如：

feature selection

有足够 significance：

→ merge。

但：

selection for

没有：

→ 不 merge。

所以得到：

text

[Markov blanket]
[feature selection]
for
[support vector machines]

92. Raw Frequency vs Rectified Frequency

重要度：★★★

单纯 frequent-pattern counting 有一个严重问题：

如果：

support vector machine

出现一次，那么 raw counting 可能同时给：

support
vector
support vector
vector machine
support vector machine

全部加 count。

这样产生：

nested phrase contamination。

ToPMine 在 segmentation 后重新 count：

rectified frequency。

课件：

Phrase	Raw	Rectified
support vector machine	90	80
vector machine	95	0
support vector	100	5

为什么 vector machine 从 95 变 0？

因为这些 occurrence 主要都属于完整 phrase：

support vector machine。

分词后不应继续把它们算成独立 vector machine phrase。

这是非常关键的 phrase-quality correction。

93. Phrase Ranking

ToPMine 使用课件提到的 KERT criteria：

Popularity
Concordance
Informativeness
Completeness

这里只列名称，没有在本章展开数学公式。

94. PhraseLDA

最终得到：

bag-of-phrases。

输入 PhraseLDA。

它是 LDA extension：

一个 phrase 中的所有 words 被约束共享同一个 latent topic。

这解决普通 LDA 中：

multi-word semantic unit 可能被拆到不同 topics

的问题。

95. ToPMine Experimental Takeaway

课件两组 experiment：

DBLP abstracts

结论：

efficient，而且不用 training data 就能得到 high-quality topics and phrases。

Yelp reviews

结论：

对 social-media-style text 也有效。

没有给需要背的数值结果。

Part IX. 整章方法论演进总表

这是期末之前最值得反复看的表。

问题	旧方法	Why it fails	新方法	How it fixes
Concept hierarchy	uniform support	lower-level support 天生低	level-reduced support	层越低 threshold 越低
不同 item frequency 差异大	one global min_sup	diamond 永远挖不到	individualized support	不同 group 不同 threshold
Numerical data	categorical item mining	丢失 ordering/distance	discretization / clustering	转换为有意义 regions
Rare important patterns	high min_sup	low-frequency patterns 被删	rare mining	group-based low threshold
Negative correlation	support/lift-like criterion	受 null transactions 影响	Kulczynski	抵消，null-invariant
Pattern explosion	all frequent	output enormous	closed/max	compression
Closed / max 不够理想	closed 太冗余，max 信息损失	两个极端	δ-cover / redundancy-aware top-k	significance + representation
Constraints	post filtering	大量无用搜索	constraint pushing	early pruning
Pattern search	generic constraints	不一定可 prune	anti-monotone	fail → prune descendants
Average constraint	neither monotone nor anti	无法直接 prune	convertible	sorting 改变 growth property
Dataset 很大	only pattern pruning	无用 transactions 仍处理	data anti-monotone	prune transactions
Pruning effects interact	one-shot pruning	后续才暴露无用 data	recursive pruning	pattern/data pruning cascade
Sequence	itemsets	无法表示 order	GSP	Apriori on sequences
GSP	candidate generation	candidates 多 + scans 多	SPADE	vertical SID/EID
SPADE/GSP	candidate based	search still expensive	PrefixSpan	prefix projection, no candidates
PrefixSpan	physical projected DB	suffix 重复复制	pseudo-projection	pointer + offset
PrefixSpan output	all sequences	redundancy	CloSpan	mine closed sequences
Graph Apriori	breadth candidate join	duplicates/isomorphism	gSpan	DFS + rightmost extension
gSpan output	all frequent graphs	redundancy	CloseGraph	closed graph pruning
Graph query	path indexing	discrimination weak	gIndex	frequent + discriminative graph features
Text unigram	single words	ambiguity	phrase mining	multi-word semantic units
Raw phrase frequency	nested fragments	false frequency	rectified frequency	segmentation 后重新计数

Part X. 期末最容易混淆的概念

1. Rare vs Negative ★★★

Rare：

Negative：

但：

2. Anti-monotone vs Monotone ★★★

Anti：

fail 永久 fail。

Monotone：

success 永久 success。

3. Pattern anti-monotone vs Data anti-monotone ★★★

Pattern：

prune search nodes。

Data：

prune transactions。

4. Convertible ≠ globally anti-monotone ★★★

它只在：

proper item ordering + corresponding pattern-growth order

下表现出 monotonicity。

所以不能随便拿来做普通 Apriori subset pruning。

5. Succinct vs Anti-monotone ★★★

Anti-monotone：

search 到某个 pattern 后才能发现该 branch 应 prune。

Succinct：

mining 前/过程中可以直接 manipulate data enforcing condition。

6. GSP vs SPADE vs PrefixSpan ★★★

	GSP	SPADE	PrefixSpan
基本范式	Apriori	Vertical Apriori	Pattern growth
Data representation	horizontal sequences	SID/EID vertical	projected DB
Candidate generation	是	是	否
Support	scan DB	ID-list joins	projected DB count
Search	level-wise	vertical joins	recursive projection
主要优势	simple, complete	support count 更有效	无 candidate，DB shrinking

7. PrefixSpan vs CloSpan ★★★

PrefixSpan：

高效挖 all frequent sequential patterns。

CloSpan：

高效挖 closed sequential patterns。

CloSpan 解决的是：

redundancy。

而不是单纯替代 prefix projection。

8. gSpan vs CloseGraph ★★★

gSpan：

efficient frequent graph enumeration。

CloseGraph：

closed frequent graph mining。

关系：

Part XI. 数学公式总表

建议考前至少能凭记忆写出这些。

Support

Rule confidence

本章例子使用 confidence，其基础定义为：

Support-based negative correlation

缺点：

not null-invariant。

Kulczynski

negative：

Pattern distance

δ-cover

Anti-monotonicity

Monotonicity

Range

Average

GSP length-2 candidates

对个 frequent singleton：

即：

例如：

Sequential support

或 proportional version：

Graph supporting set

Graph support

gIndex discriminative power

值足够小：

x adds discrimination。

Graph feature representation

Phrase significance

Part XII. 考前优先级

如果时间非常紧，建议按这个顺序复习。

第一优先级 ★★★

Null-invariance：support-based negative correlation 为什么失败，Kulc 为什么解决；
anti-monotone / monotone 的定义和判断；
convertible constraint，尤其 avg > 20；
为什么 converted constraint 不能直接用普通 Apriori；
pattern vs data anti-monotonicity；
recursive data pruning；
succinct constraints；
Sequence element / subsequence / support；
GSP candidate generation，尤其：
GSP → SPADE → PrefixSpan → CloSpan 的演进；
PrefixSpan projected DB 和 _ placeholder；
physical vs pseudo projection；
graph support；
Apriori graph mining → gSpan → CloseGraph；
gSpan right-most path；
closed sequence / closed graph 的定义。

第二优先级 ★★☆

multi-level support；
ancestor-rule redundancy；
individualized support；
multi-dimensional rule 分类；
quantitative mining；
δ-cover；
timing constraints；
episodes；
graph indexing / gIndex；
CP-Miner；
phrase significance / rectified frequency。

第三优先级 ★☆☆

具体论文作者/年份；
application list；
DBLP/Yelp experiment qualitative conclusion。

最后有一个容易遗漏的点：课件目录 P2 写了 “Mining High-dimensional Data”，但你这份课件后续并没有单独给它技术内容或算法页；因此按这份课件本身，不能再凭空补一个 high-dimensional pattern mining 方法。类似地，MMS 只给名称和目标，没有公式；Z-test 只点名，没有给统计量公式。这几处我没有把课外内容伪装成课件内容。

高密度复习：Pattern Mining 进阶

四条主线

主线	要解决什么	关键词
Rich patterns	单一 minsup/维度不够	multi-level、multiple minsup、quantitative、rare/negative
Compression	频繁模式太多	closed、maximal、-cover、top-
Constraints	尽早剪枝	anti-monotone、monotone、convertible、succinct、data anti-monotone
Ordered / graph data	itemset 不表达顺序/连接	GSP、SPADE、PrefixSpan、CloSpan、gSpan/CloseGraph

Constraint 一张表

类型	性质	正确剪枝方向	例子
Anti-monotone	pattern 不满足所有 supersets 不满足	从小到大尽早剪	、
Monotone	pattern 满足所有 supersets 满足	可利用已满足的扩展
Convertible	排序后转为上述之一	先规定 item order
Succinct	无须搜索即可按属性条件选出	直接过滤	contains item
Data anti-monotone	删除数据后递归影响支持	data-space pruning	需 cascade 更新

不要把 pattern anti-monotonicity（集合扩展的性质）和 data anti-monotonicity（删数据后的递归影响）混为一谈。

Sequential mining

算法	表示 / 搜索	关键优缺点
GSP	Apriori candidates + 多次 scan	易懂，但 candidate 多
SPADE	vertical id-list	用 temporal join 支持深搜
PrefixSpan	prefix-projected DB	不显式 candidate generation；projection 成本是瓶颈
CloSpan	closed sequential pattern	same-support extension 时剪枝

序列的 support 是“包含该 subsequence 的 sequence 数占比”，不是该 subsequence 在单条 sequence 中出现次数。

Graph patterns

frequent graph 的 Apriori 性质只有单向：graph frequent 所有子图 frequent。
gSpan 用 DFS code 的 canonical form 避免同构重复；subgraph isomorphism 是主要计算瓶颈。
CloseGraph 的闭合判断基于 support graph / occurrence set：每个包含的数据图也包含。不要误写成“每一个具体 embedding 都可扩展”。

高频陷阱

multi-level mining 需要按 level 设 minsup；过低会爆炸，过高会漏掉细粒度模式。
negative correlation 必须检查 null transactions；Kulc 是 null-invariant，但阈值比较要注意等号（课件的是笔误）。
closed 与 maximal：closed 保 support，maximal 不保 support。
quantitative association 的 discretization 会改变模式；dynamic / clustering 方法是为降低静态分箱信息损失。

Chapter 4 — Pattern Mining: Advanced Methods ​

0. 本章到底在解决什么？——从“普通频繁项集”向真实世界推进 ​

Part I. Mining Various Kinds of Patterns ​

1. Multi-Level Association Mining ​

1.1 Why：普通 itemset mining 为什么不够？ ​

1.2 Uniform support → Level-reduced support ​

方法 A：Uniform minimum support ​

Why it fails ​

方法 B：Level-reduced minimum support ★★★ ​

1.3 Shared multi-level mining ★★☆ ​

2. Multi-Level Association 中的 Redundancy ​

Redundant rule 的直觉定义 ​

课件最后的问题 ​

3. Customized Minimum Supports ​

3.1 Why uniform min_sup fails ​

3.2 Group-based individualized min-support ​

4. Multi-Dimensional Association Rules ​

4.1 Single-dimensional rule ​

4.2 Multi-dimensional rule ​

A. Inter-dimension association rule ★★★ ​

B. Hybrid-dimension association rule ★★★ ​

4.3 Attribute type 决定后续算法 ​

Categorical attributes ​

Quantitative attributes ​

5. Quantitative Association Mining ​

5.1 Static discretization ​

优点 ​

局限 ​

5.2 Dynamic discretization ​

5.3 Clustering-based association ​

5.4 Deviation Analysis ​

6. Mining Extraordinary Phenomena ​

6.1 LHS 与 RHS 的含义 ​

6.2 为什么不能只看 mean difference？ ​

6.3 Subrule ​

6.4 Condition 也可以是 quantitative ​

7. Rare Patterns ​

8. Negative Patterns ​

9. Negative Correlation：第一版定义为什么失败？ ​

9.1 Support-based definition ​

9.2 Null transaction 问题 ★★★ ​

情况 1：总共 transactions ​

情况 2：增加大量 null transactions ​

9.3 为什么数学上会依赖 null transaction？ ​

结论 ★★★ ​

10. Kulczynski Measure：Null-Invariant Negative Correlation ​

10.1 负相关判定 ​

一个值得你考试时留意的课件细节 ​

Part II. Mining Compressed / Approximate Patterns ​

11. 为什么需要 compressed patterns？ ​

12. Closed Pattern vs. Max Pattern 的两种极端 ​

Closed patterns ​

Max pattern ​

核心矛盾 ​

13. Pattern Distance 与 δ-Cover ​

δ-clustering ​

δ 的意义 ​

14. Redundancy-Aware Top-k Patterns ​

Part III. Constraint-Based Pattern Mining ​

15. 为什么需要 Constraint-Based Mining？ ​

16. User-Specified Constraints 的五类 ​

1. Knowledge-type constraint ​

2. Data constraint ​

3. Dimension / level constraint ​

4. Interestingness constraint ​

5. Rule / pattern constraint ★★★ ​

17. Pattern Anti-Monotonicity ​

17.1 定义 ​

18. Anti-Monotone Examples ​

18.1 ​

注意 ★★★ ​

18.2 Range constraint ​

18.3 非 anti-monotone ​

19. Support Constraint 为什么是 Anti-Monotone？ ​

极其重要的统一理解 ​

20. Pattern Monotonicity ​

定义 ​

21. Monotone Examples ​

Example 1 ​

Example 2 ​

Chapter 4 — Pattern Mining: Advanced Methods

0. 本章到底在解决什么？——从“普通频繁项集”向真实世界推进

Part I. Mining Various Kinds of Patterns

1. Multi-Level Association Mining

1.1 Why：普通 itemset mining 为什么不够？

1.2 Uniform support → Level-reduced support

方法 A：Uniform minimum support

Why it fails

方法 B：Level-reduced minimum support ★★★

1.3 Shared multi-level mining ★★☆

2. Multi-Level Association 中的 Redundancy

Redundant rule 的直觉定义

课件最后的问题

3. Customized Minimum Supports

3.1 Why uniform min_sup fails

3.2 Group-based individualized min-support

4. Multi-Dimensional Association Rules

4.1 Single-dimensional rule

4.2 Multi-dimensional rule

A. Inter-dimension association rule ★★★

B. Hybrid-dimension association rule ★★★

4.3 Attribute type 决定后续算法

Categorical attributes

Quantitative attributes

5. Quantitative Association Mining

5.1 Static discretization

优点

局限

5.2 Dynamic discretization

5.3 Clustering-based association

5.4 Deviation Analysis

6. Mining Extraordinary Phenomena

6.1 LHS 与 RHS 的含义

6.2 为什么不能只看 mean difference？

6.3 Subrule

6.4 Condition 也可以是 quantitative

7. Rare Patterns

8. Negative Patterns

9. Negative Correlation：第一版定义为什么失败？

9.1 Support-based definition

9.2 Null transaction 问题 ★★★

情况 1：总共 transactions

情况 2：增加大量 null transactions

9.3 为什么数学上会依赖 null transaction？

结论 ★★★

10. Kulczynski Measure：Null-Invariant Negative Correlation

10.1 负相关判定

一个值得你考试时留意的课件细节

Part II. Mining Compressed / Approximate Patterns

11. 为什么需要 compressed patterns？

12. Closed Pattern vs. Max Pattern 的两种极端

Closed patterns

Max pattern

核心矛盾

13. Pattern Distance 与 δ-Cover

δ-clustering

δ 的意义

14. Redundancy-Aware Top-k Patterns

Part III. Constraint-Based Pattern Mining

15. 为什么需要 Constraint-Based Mining？

16. User-Specified Constraints 的五类

1. Knowledge-type constraint

2. Data constraint

3. Dimension / level constraint

4. Interestingness constraint

5. Rule / pattern constraint ★★★

17. Pattern Anti-Monotonicity

17.1 定义

18. Anti-Monotone Examples

18.1

注意 ★★★

18.2 Range constraint

18.3 非 anti-monotone

19. Support Constraint 为什么是 Anti-Monotone？

极其重要的统一理解

20. Pattern Monotonicity

定义

21. Monotone Examples

Example 1

Example 2