3) 剪枝：
1) 因为ade不在L3中，删除acde
4) C4={abcd}
降低复杂度的方法
备选项集的计算过程
扫描数据库并计算每个备选项集的支持度 减少统计的次数，可以利用哈希桶来统计
Transactions
TID Items
1 Bread, Milk
2 Bread, Diaper, Beer, Eggs
读取第一项后:
null A:1
B:1
读取第二项后: null
A:1
B:1
B:1
C:1
D:1
FP生长算法
TID Items
1
{A,B}
2 {B,C,D}
3 {A,C,D,E}
4 {A,D,E}
5 {A,B,C}
6 {A,B,C,D}
7
{B,C}
8 {A,B,C}
9 {A,B,D}
10 {B,C,E}
Item
Count (1-项集)
Bread
4
Coke
2
Milk
4
Beer
3
Diaper
4
Eggs
1
Itemset
{Bread,Milk} {Bread,Beer} {Bread,DiMilk,Diaper}
支持度阙值 = 3
{Beer,Diaper}
Count
3 2 3 2 3 3
234 567
345
12 5 45 8
15 9
356 357 689
367 368
哈希桶
哈希函数
备选项哈希桶
1,4,7 2,5,8
2, 5, 8的 哈希值
3,6,9
145 124 457
13 6
234 567
345
12 5 45 8
15 9
356 357 689
367 368
哈希桶
哈希函数
备选项哈希桶
如果{A, B, C, D}是频繁项集，备选规则有： ABC D, ABD C, ACD B, BCD A,
A BCD,B ACD, C ABD, D ABC AB CD,AC BD, AD BC, BC AD, BD AC, CD AB,
如果L的项个数为K，那么可能有2k – 2 个关联规则 (忽 略L 与 L)
普遍到特殊 VS 特殊到普遍
Frequent
itemset
border null
null
..
..
..
..
Frequent itemset null border
.. ..
{a1,a2,...,an}
(a) General-to-specific
{a1,a2,...,an}
Frequent itemset border
(2-项集) (3-项集)
如果考虑所有的项集计算次数, 6C1 + 6C2 + 6C3 = 41
修剪项集后计算次数, 6 + 6 + 1 = 13
Itemset
Count
{Bread,Milk,Diaper}
3
Apriori算法
令k = 1
产生长度为1的频繁项集
循环直到没有新的频繁项集产生
频繁项集
影响复杂度的因素
最小支持度阈值的选择
降低最小支持度阈值导致更多频繁项集 增加备选项次数和频繁项集的长度
数据集的维数（属性数目）
需要更多的空间来存储每个项的支持计数 如果频繁项的数量也随之增加，计算和I/ O的成本也可能增加
数据库的大小
由于循环多遍，数据多少可能会增加算法的运行时间
N3
4
Milk, Diaper, Beer, Coke Bread, Milk, Diaper, Beer
5 Bread, Milk, Diaper, Coke
Hash Structure
k
Buckets
哈希桶
假设有15个备选3-项集
{1 4 5}, {1 2 4}, {4 5 7}, {1 2 5}, {4 5 8}, {1 5 9}, {1 3 6}, {2 3 4}, {5 6 7}, {3 4 5}, {3 5 6}, {3 5 7}, {6 8 9}, {3 6 7}, {3 6 8}
关联分析
规则评估标准
TID Items
1
Bread, Milk
支持度
一个项集出现的频率。
置信度
一个项集在另一个项集中出现的频率。
2
Bread, Diaper, Beer, Eggs
3
Milk, Diaper, Beer, Coke
4
Bread, Milk, Diaper, Beer
支持度的评估满足
X ,Y : ( X Y ) s( X ) s(Y )
降低复杂度的方法
null
A
B
C
D
E
不频繁的项集
AB
AC
AD
AE
BC
BD
BE
CD
CE
DE
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE
修剪超集
ABCD
ABCE
ABDE
ACDE
BCDE
ABCDE
Apriori范例
5
Bread, Milk, Diaper, Coke
范例：
{Milk, Diaper} Beer
s (Milk, Diaper,Beer) 2 0.4
|T|
5
c (Milk, Diaper,Beer) 2 0.67 (Milk, Diaper) 3
关联分析目的
支持度计算()
一个项集出现的个数。如({Milk, Bread,Diaper}) = 2
支持度
一个项集出现的频率。如s({Milk, Bread,Diaper}) = 2/5
频繁项集
满足最小支持度阙值的所有项集。
关联规则
项集之间形如X->Y的蕴涵表达式。如{Milk, Diaper} {Beer}
当计算3-项集支持度时
Hash function
1,4,7
3,6,9
2,5,8
145
124 457
125 458
234 567 136345
159
356 357 689
367 368
哈希桶
哈希函数
备选项哈希桶
1,4,7 2,5,8
1, 4, 7的 哈希值
3,6,9
145 124 457
13 6
12 3 5 6 13 5 6 15 6
235 6 25 6
3 56 35 6
123 125 126
Level 3
135 136
156
235 236
Subsets of 3 items
256
356
哈希桶实现的子集
1 2 3 5 6 交易
哈希函数
1+ 2356
2+ 356
1,4,7
3,6,9
3+ 56
规则产生
如果从频繁项集中产生规则
null
A:7
B:1
B:5
C:1 D:1
C:1
C:3
D:1 D:1
D:1
频繁项集：AB, ABC
D:1
FP生长算法
TID Items
1
{A,B}
2 {B,C,D}
3 {A,C,D,E}
4 {A,D,E}
5 {A,B,C}
6 {A,B,C,D}
7
{B,C}
8 {A,B,C}
9 {A,B,D}
10 {B,C,E}
2,5,8
145
234 567
136
345
124 125 159 457 458
356 357 689
367 368
哈希桶实现的子集
1 2 3 5 6 交易
哈希函数
12+ 356 13+ 56 15+ 6
1+ 2356
2+ 356
1,4,7
3,6,9
3+ 56
2,5,8
234 567
145
136
124 125 159 457 458
玩转大数据 – 深入浅出数据挖掘技术 关联分析
关联规则挖掘
给定一批交易，根据项目的出现频率找出相互之间的关联 规则
购物车记录
TID Items
1
Bread, Milk
2
Bread, Diaper, Beer, Eggs
3
Milk, Diaper, Beer, Coke
4
Bread, Milk, Diaper, Beer
从长度k中的频繁项集中产生长度为k + 1的备选项集
清除备选项集中对应子集为不频繁的备选项集
计算所有备选项集的支持度
排除不频繁的备选项集
1) 例如，备选3-项集是 L3={abc, abd, acd, ace, bcd} 2) 合并备选项集L3*L3
a. 从abc和abd中提取abcd b. 从acd和ace中提取acde
AB
A
AC
AD
B
C
D
AE
BC
BD
BE
E
CD
CE
DE