Skip to content

下面这份笔记严格以你上传的《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 ★★★★☆ ​

典型事务数据库:

TIDItems
1Beer, Nuts, Diaper
2Beer, Coffee, Diaper
3Beer, Diaper, Eggs
4Nuts, Eggs, Milk
5Nuts, 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,如果:

  1. frequent;
  2. 不存在任何 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 PatternMaximal Pattern
必须 frequentYesYes
不允许什么 superset相同 support 的 superset任意 frequent superset
压缩LosslessLossy
子集是否能判断 frequentYesYes
子集准确 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 路线 ★★★★☆ ​

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

方法核心思想搜索方式
Apriorilevel-wise candidate generationBFS-like
ECLATvertical Tid-list intersectionDFS
FP-Growthconditional pattern growthRecursive DFS

历史:

  • Apriori:1994
  • ECLAT:1997
  • FP-Growth:2000

其演进本质是:


18. Apriori Algorithm ★★★★★ ​

Apriori 是:

基本流程:

  1. 扫描 DB 得到 frequent 1-itemsets:
  2. 用 生成 candidate:
  3. 扫描数据库,计算 support。
  4. 得:
  5. 重复直到:

返回:


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 完整例题 ★★★★★ ​

数据库:

TIDItems
10A,C,D
20B,C,E
30A,B,C,E
40B,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 ​

例如:

TIDItems
10a,c,d,e
20a,b,e
30b,c,e

29.2 Vertical representation ​

变成:

ItemTid-list
a10,20
b20,30
c10,30
d10
e10,20,30

定义:

例如:


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

若:

两个 itemsets,则:

所以:

例如:

则:

所以:

不再重新扫描原始 DB。


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

若:

说明:

在 transaction 层面总是共同出现。

课件例子:

如果:

说明:

每一个含 的 transaction 一定也含 。

例如:

而:

因此:


32. Diffset ★★★★☆ ​

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

于是可以只存:

例如:

于是:

如果 从 扩展得到:

这里:

核心思想:


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

AprioriECLAT
Data formatHorizontalVertical
SearchLevel-wiseDepth-first
Support calculationScan transactionsTid-list intersection
Candidate ideaExplicit generationIntersection-based extension
主要成本DB scansSet intersections
适合思想广度剪枝垂直递归

ECLAT 解决的是:

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

于是引出:


34. FP-Growth:为什么出现?★★★★★ ​

Apriori 的核心模式:

即使 pruning 很强,在 dense database 中:

仍然可能巨大。

FP-Growth 的目标:

核心思路:

  1. 把 transaction DB 压缩成 FP-tree;
  2. 针对某个 pattern 构造 conditional database;
  3. recursively grow pattern。

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

课件样例:

原始 transactions:

TIDTransaction
100f,a,c,d,g,i,m,p
200a,b,c,f,l,m,o
300b,f,h,j,o,w
400b,c,k,s,p
500a,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:

最终:

TIDOrdered frequent itemlist
100f,c,a,m,p
200f,c,a,b,m
300f,b
400c,b,p
500f,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:

  1. count frequent single items;
  2. 删除 infrequent;
  3. 建 conditional FP-tree;
  4. 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 ★★★★★ ​

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

AprioriECLATFP-Growth
核心思想candidate generationTid-list intersectionpattern growth
DB representationhorizontalverticalFP-tree
SearchBFS / level-wiseDFSrecursive DFS
是否 candidate generation是隐式否
DB scans多次转换后少通常主要两次构树
Support 计算scan DBset intersectiontree counts
压缩 DB否Tid-list强
主要问题candidate explosionTid-list/intersection costtree/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
400350750
20050250
total6004001000

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
10010001100
1000100000101000
total1100101000102100

关键结构:

但:

直觉上:

当 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 大汇总 ★★★★★ ​

课件给出:

MeasureFormulaRangeNull-invariant?
No
LiftNo
AllConfYes
JaccardYes
CosineYes
KulczynskiYes
MaxConfYes

这里课件中的 延续 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 联合解释 ★★★★★ ​

课件数据:

DatasetKulcIRInterpretation
D40.50neutral & balanced
D50.50.89neutral but imbalanced
D60.50.99neutral 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 ​

必须:

  1. self-join;
  2. 检查所有 -subsets;
  3. 有一个 infrequent 就 prune。

9. ECLAT 最核心公式 ​


10. FP-Growth 最核心对象 ​

一定区分:

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

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

目标关键技术
判断是否 frequentSupport + minsup
找所有 frequent patternsApriori / ECLAT / FP-Growth
利用 subset pruningApriori property
降低数据库扫描次数Partitioning
减少 candidatesDHP
用集合交集算 supportECLAT
避免 candidate generationFP-Growth
压缩 frequent patterns 且保留 supportClosed patterns
极致压缩,只保留 frequent boundaryMaximal patterns
判断相对独立性Lift
检验 independence deviation
大量 null transactionsNull-invariant measures
同时考虑双向关系Kulczynski
判断两个方向是否 imbalanceIR

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 一眼区分 ​

方法数据表示核心动作痛点 / 优势
Apriorihorizontal transactionsjoin + prune + 多次 scancandidate explosion
Partition分块局部频繁再全局验证local minsup降低内存/scan 压力
DHPhash buckethash pruning只能安全剪掉不可能频繁者
ECLATvertical TID setTID intersection深度优先、对稀疏数据友好
FP-growthFP-treeconditional pattern base/tree不显式生成候选;树压缩失效时不理想

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

Closed / maximal / negative correlation ​

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

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

考场算法链 ​

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

Static academic notes built with VitePress and KaTeX.