频繁模式与关联规则挖掘 林琛 博士、副教授.

Presentation on theme: "频繁模式与关联规则挖掘 林琛 博士、副教授."— Presentation transcript:

1 频繁模式与关联规则挖掘 林琛 博士、副教授

2 数据挖掘领域的十大经典算法 Apriori: Rakesh Agrawal and Ramakrishnan Srikant. Fast Algorithms for Mining Association Rules. In VLDB ‘94. #4 （52 votes） FP-Tree: Han, J., Pei, J., and Yin, Y Mining frequent patterns without candidate generation. In SIGMOD '00. 他引超过3000次 GSP: Srikant, R. and Agrawal, R Mining Sequential Patterns: Generalizations and Performance Improvements. In Proceedings of the 5th International Conference on Extending Database Technology, 1996. PrefixSpan: J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal and M-C. Hsu. PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth. In ICDE '01. gSpan: Yan, X. and Han, J gSpan: Graph-Based Substructure Pattern Mining. In ICDM '02.

3 大纲 频繁项集与关联规则 序列模式挖掘（简略） 频繁子图挖掘（简略） 形式定义 Apriori算法 FP-tree算法 关联规则挖掘
关联规则的评估 序列模式挖掘（简略） GSP PrefixSpan 频繁子图挖掘（简略） gSpan

4 Nuts, Coffee, Diaper, Eggs, Milk
频繁项集的形式定义 Tid Items bought 10 Beer, Nuts, Diaper 20 Beer, Coffee, Diaper 30 Beer, Diaper, Eggs 40 Nuts, Eggs, Milk 50 Nuts, Coffee, Diaper, Eggs, Milk 项集: 项目的集合。 k-项集 X = {x1, …, xk} 绝对支持度（支持度计数）: 项集X的出现次数（频率），即包含项集的事务数 相对支持度, s：事务集中包含项集的事务的百分比 频繁项集 ：如果项集X的相对支持度满足某个给定的阈值 频繁k项集 Lk 闭频繁项集X：如果不存在X的真超集Y，具有和X相同的支持度计数 极大频繁项集X：如果X是频繁的，闭的，且不存在频繁项集Y是X的超集 Support({Beer})= 3/60% Support({Nuts})=3/60% Support({Diaper})=4/80% Support({Eggs})=3/60% Support({Beer, Diaper})=3/60% Support({Nuts,Diaper})=2/40% 频繁1项集 不是闭的 闭的， 非极大的 频繁2项集 极大频繁项集 如果min_support=50%

5 Nuts, Coffee, Diaper, Eggs, Milk
关联规则的形式定义 Tid Items bought 10 Beer, Nuts, Diaper 20 Beer, Coffee, Diaper 30 Beer, Diaper, Eggs 40 Nuts, Eggs, Milk 50 Nuts, Coffee, Diaper, Eggs, Milk 关联规则是形如A → B的蕴涵式 A，B是项集 具有支持度s s=P(A B） 具有置信度c c=P(B|A) 强规则：同时满足最小支持度阈值和满足最小置信度阈值 购买diaper: 4/80% 同时购买beer和diaper: 3/60% 购买beer: 3/60% 给定 min_sup = 50%, min_conf = 50% 找出关联强规则 Beer  Diaper (60%, 100%) Diaper  Beer (60%, 75%)

6 关联规则的挖掘过程 找出所有的频繁项集 由频繁项集产生强关联规则 挖掘关联规则的性能由挖掘频繁项集决定 考虑一个简单枚举的算法
或者其他的有价值的关联规则 挖掘关联规则的性能由挖掘频繁项集决定 考虑一个简单枚举的算法 假设样本数（记录数）为N，维度（项目数）为D，每条记录的长度为w 算法复杂度O(2dNw)

7 Apriori算法 Apriori性质 算法伪代码 频繁项集的所有非空子集也必须是频繁的 ABCD ABC ABD ACD BCD AB
Ck: Candidate itemset of size k//候选集 Lk : frequent itemset of size k//频繁项集 L1 = {frequent items}; //由底向上生成候选集 for (k = 1; Lk !=; k++) do //产生步 Ck+1 = apriori_gen //测试步 Lk+1 = count(Ck+1 )>= min_support end return k Lk; ABCD ABC ABD ACD BCD AB AC BC AD BD CD A B C D {} Itemset lattice

8 Apriori算法的产生步 Ck+1 = apriori_gen Ck+1 = join(L1…Lk);//连接步 Ck+1 =pruning(Ck+1 );//剪枝步 Apriori性质

9 Apriori算法的例子 购物篮记录 min_support = 2 L1 C1 扫描计数 C2 连接+剪枝 L2 测试 连接 C2 剪枝
Itemset sup {A} 2 {B} 3 {C} {D} 1 {E} Itemset sup {A} 2 {B} 3 {C} {E} Tid Items 10 A, C, D 20 B, C, E 30 A, B, C, E 40 B, E L1 C1 扫描计数 C2 连接+剪枝 L2 Itemset {A, B, C} {A, C, E} {B, C, A} {B, C, E} {B, E, A} {B, E, C} {C, E, A} {C, E, B} Itemset sup {A, B} 1 {A, C} 2 {A, E} {B, C} {B, E} 3 {C, E} Itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E} Itemset sup {A, C} 2 {B, C} {B, E} 3 {C, E} 测试 连接 C2 剪枝 C3 L3 扫描计数 Itemset {B, C, E} Itemset sup {B, C, E} 2 C3

10 连接步策略 对项编码 Ck+1 = L1×Lk Ck+1 = Lk-1×Lk-1 哪一个策略产生的重复项集多？
Itemset sup {A} 2 {B} 3 {C} {E} Itemset sup {A, C} 2 {B, C} {B, E} 3 {C, E} L2 对项编码 项按字典序存储 项集中的项排序 Ck+1 = L1×Lk 一个频繁k项集和一个不属于频繁k项集的频繁项 且频繁项比频繁k项集中的所有项都大 Ck+1 = Lk-1×Lk-1 一个频繁k项集和一个频繁k项集 且两个频繁k项集的前k-1项相等 哪一个策略产生的重复项集多？ 哪一个策略产生的不必要的候选项集多？ L1 策略2 策略1 Itemset {A, C, E} {B, C, E} Itemset {B, C, E} C3 剪枝 剪枝 Itemset {B, C, E}

11 Apriori算法的测试步 Lk+1 = count(Ck+1 )>= min_support 策略1：比较每个记录与每个候选项集
策略2：枚举每个记录所包含的项集，与每个候选项集比较

12 散列树的数据结构与构造 count(Ck+1 ) construct(HTree); traversal(Htree,T)
struct HashTreeNode  {     bool leaf; //叶节点标志      int level; //该节点层级    itemset* candidate; //指向候选项集       struct node * child[m]; //指向下一层子节点   }  Foreach (l in Ck+1) do //插入 current=root; while(!current.leaf) do k=current.level; n=h(l[k]); current=current.child[n]; end current.candidate.insert(l); if (current.candidate.size>max_leafsize) //分裂 current.leaf=false; current.level=++k; foreach (s in current.candidate) do n=h(s[k]); current.child[n].candidate.insert(s);

13 散列树的构造：例子 C3 哈希函数 max_leafsize=3 3,6,9 1,4,7 2,5,8
{124,125,136,145,159,234,345,356,357,367,368,457,458,567,689} 1 2 2 2 3 4 3 4 5 1 2 4 5 6 7 3 5 6 1 2 5 3 3 5 7 3 6 7 1 3 6 1 2 4 3 4 5 3 6 7 1 3 6 3 5 6 1 4 5 1 2 5 3 5 7 3 6 8 1 4 5 6 8 9 1 5 9 1 2 4 4 5 7 1 2 5 1 5 9 4 5 7 4 5 8

14 基于散列树的支持度计数 1 2 3 5 6 10 2 + 3 5 6 10 t: t’=trim(t):
Input: data set T, k, HashTree for t in T Recursivetraverse (1,HashTree.root,t); end Recursivetraverse (int level, HashTreeNode node, Transaction t) if (node.leaf) compare(t,node.candidate); return; else for (int b=level~w-k+level) do node=node.child[h(t[b])]; t=trim(t); Recursivetraverse(level+1,node,t); Level=1 K-1 W-K+1 t: t’=trim(t):

15 基于散列树的支持度计数：例子 1,4,7 2,5,8 3,6,9 哈希函数 t: 1 2 3 5 6 2 + 3 5 6
2 3 4 5 6 7 1 4 5 1 3 6 1 2 4 4 5 7 1 2 5 4 5 8 1 5 9 3 4 5 3 5 6 3 5 7 6 8 9 3 6 7 3 6 8 比较5个叶子节点中的9个候选项集 而不需要比较总共15个候选项集

16 减少扫描代价的其他方法 数据压缩 抽样 已经得到频繁k项集 测试候选k+1项集 在原始数据的样本上挖掘频繁项集 牺牲精度

17 Apriori算法复杂度分析 影响Apriori算法效率的因素 Apriori算法复杂度 支持度阈值 维度D 样本数N 平均记录长度w
频繁1项集（第一次扫描）O(Nw) 对于每个k 候选项集连接O(| Lk-1 | 2(k-2)) 构造散列树k|Ck| 剪枝O((k-2)(k-1) |Ck|) 测试O(NCwk)

18 FP增长算法 不产生候选 有限的扫描次数 索引全数据集 FP-tree 挖掘频繁项集在索引结构上进行

19 FP树构造 扫描数据集：第一次 扫描数据集：第二次 频繁项支持度计数 频繁项排序 记录改写 构造FP树 构造项头表 每个节点包含 项 计数
指向孩子节点的指针 构造项头表 Input: data set T root=new FPnode; foreach (Transaction t in T) do insert(t[1],t-t[1],root); end insert (item m, itemset ms, FPnode node) branch=node.children.seek(m) if (!branch) count(branch)++; else branch=new Fpnode; count(branch)=1; *itemtable[m].link=&branch; insert (ms[1],ms-ms[1],branch);

20 FP树构造 min_support = 3 {} f:1 c:1 a:1 m:1 p:1 p:1 c:1 b:1 项头表 项 频率 指针
扫描第二遍 构造FP树的根节点 每条记录 增加分支 增加项头表 Tid Items 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 Tid Items 100 f, c, a, m, p 200 f, c, a, b, m 300 f, b 400 c, b, p 500 {} f:1 c:1 a:1 m:1 p:1 扫描第一遍 计算支持度计数 得到频繁1项集 按照支持度递减排序 重写记录，只包含频繁项并排序 p:1 c:1 b:1 2 4 3 项头表 项 频率 指针 f 4 c 4 a 3 b 3 m 3 p 3 □ b:1 3 频繁1项集 sup f 4 c a 3 b m p 3 b:1 m:1 2 2

21 FP树挖掘频繁模式 从频繁1项集（初始后缀模式）开始由底向上 分治地对后缀模式 生成条件FP树 条件模式基 递归挖掘条件FP树
删除不与后缀模式一起出现的分支 删除后缀 更新支持度计数 删除非频繁项 条件模式基 FP树中的与后缀模式一起出现的前缀路径集 递归挖掘条件FP树

22 FP树挖掘频繁模式：例子 b:1 {} f:4 c:3 a:3 m:2 p:2 m:1 p:1 c:1 项头表 项 频率 指针 f 4
项 频率 指针 f 4 c 4 a 3 b 3 m 3 p 3 □ 2，以p为初始后缀模式 生成p的条件FP树 删除不与后缀模式一起出现的分支 删除后缀 更新支持度计数 删除非频繁项 min_support = 3 {} f:2 c:2 a:2 m:2 c:1 b:1 项头表 项 频率 指针 f 2 c 3 a 2 b 1 m 2 □ 条件模式基 p c:3 频繁项集 cp 1，自底向上 包含p 不包含p，含m 不包含p/m，含b 不包含p/m/b，含a 不包含p/m/b/a，含c 只包含f {} c:3

23 FP树挖掘频繁模式：例子（2） b:1 {} f:4 c:3 a:3 m:2 p:2 m:1 p:1 c:1 项头表 项 频率 指针 f 4
生成p的条件FP树 删除不与后缀模式一起出现的分支 删除后缀 更新支持度计数 删除非频繁项 b:1 {} f:4 c:3 a:3 m:2 p:2 m:1 p:1 c:1 项头表 项 频率 指针 f 4 c 4 a 3 b 3 m 3 p 3 □ min_support = 3 {} f:3 c:3 a:3 b:1 项头表 项 频率 指针 f 3 c 3 a 3 b 1 □ {} f:3 c:3 am 条件FP树 1，自底向上 包含p 不包含p，含m 不包含p/m，含b 不包含p/m/b，含a 不包含p/m/b/a，含c 只包含f 条件模式基 m fca:3 分治更长的后缀模式 fm, cm, am, fcm, fam,fcam {} f:3 cm 条件FP树

24 关联规则 枚举的方法 给定频繁项集 L, 非空子集 f  L ，测试f  L – f是否满足置信度 阈值
如果 {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, 对于频繁k项集 |L| = k, 有2k – 2 条候选规则 (即忽略 L   and   L)

25 基于置信度的剪枝 如果形如X->Y-X的规则不满足置信度阈值，那么形如X’->Y-X’的规则也一定不满足置信度阈值，其中X’是X的子集

26 关联规则产生算法 for (k=1~K) do //频繁k项集 for (H1in Lk) do //从1项后件开始 rulegen (H1,Lk); end rulegen (Hm ,L) if (|L|>|Hm|) apriori_gen (Hm+1); foreach (hm+1 in Hm+1) do if (conf>min_conf) output “L-hm+1 hm+1”; else delete hm+1 from Hm+1; end rulegen (Hm+1 ,L);

27 数据挖掘的基本流程 数据获取 数据预处理 数据挖掘 模式评估 用户界面

28 兴趣度度量: 提升度 强关联规则不一定有趣 如果吃麦片占所有学生的75% （> 66.7%）
打篮球 吃麦片 [支持度40%, 置信度66.7%] 是一个误导的强关联规则 如果吃麦片占所有学生的75% （> 66.7%） 打篮球 与吃麦片负相关，即打篮球  不吃麦片 [20%, 33.3%] 扩充关联规则框架：A B [支持度，置信度，相关度] 篮球 非篮球 Sum (row) 麦片 2000 1750 3750 非麦片 1000 250 1250 Sum(col.) 3000 5000 打篮球 吃麦片 [支持度40%, 置信度66.7%，相关度0.89] 打篮球  不吃麦片 [20%, 33.3%，1.33]

29 时间序列数据 股票 时间序列数据集由不同时间重复测量得到的值或事件的序列组成。 序列数据集是由事件序列组成，不一定有具体的时间概念。 GPS
网络点击流

30 序列模式的形式定义 事件=项集 序列=事件的有序列表 子序列和超序列 序列数据集（库）S是序列的集合 序列模式=频繁序列
序列的长度是序列中包含的事件/项个数 L-序列是序列中的项数目为l的序列 子序列和超序列 序列α=<a1a2an>是序列β=<b1b2…bm>的子序列， β 是α的超序列 如果存在整数1≤j1<j2…jn≤m,使得 序列数据集（库）S是序列的集合 序列模式=频繁序列 序列α在序列数据集S中的支持度=序列数据集中包含序列α的记录数 一个序列α是频繁的，如果α的支持度满足最小支持度阈值

31 序列模式的形式定义：例子 序列数据集S 4，找到S中包含的所有频繁2-序列 SID sequence 10
<a(abc)(ac)d(cf)> 20 <(ad)c(bc)(ae)> 30 <(ef)(ab)(df)cb> 40 <eg(af)cbc> <aa>,<ab>,<ac>,<ad>,<af>, <ba>,<bc>,<bd>,<bf>, <ca>,<cb>,<cc>, <db>,<dc>, <ea>,<eb>,<ec>,<ef>, <fb>,<fc>, <(ab)> 1，说明序列10，20，30，40的事件数和项数？ 5/9,4/7,5/8,6/7 2，<a(bc)dc> 是哪个序列的子序列 <a(abc)(ac)d(cf)> 3，给定min_sup = 2, <(ab)c>是序列模式吗？ 是。因为<(ab)c>的支持度为2

32 序列模式挖掘：GSP算法 GSP算法(Generalized Sequential Patterns)
利用了Apriori性质，即任何序列模式的非空子序列也是序列模式 算法框架 扫描第一遍，得到频繁1项，即频繁1-序列 扫描第k遍，得到频繁k-序列 由频繁k-1-序列连接得到候选k-序列 剪枝得到更小的候选k-序列集合 计算支持度计数，得到频繁k-序列 产生 测试

33 候选产生的方法 首先，序列本身有序。事件无序，但按照（字典）序对事件中的项目排序 候选k-序列s由合并两个频繁k-1序列s1和s2
如果s2的最后一项在s2中是一个独立的事件，则作为独立的一个事件加到s的最后 否则，在s中的最后一个事件里加上

34 候选产生的方法：例子 第一个序列去掉第一个项目，第二个序列去掉最后一个项目 子序列 <5 3> = <5 3>
频繁3-序列 <1 5 3> <5 (3 4)> 子序列 <2 3> = <2 3> 频繁3-序列 <1 2 3> <2 3 4> 合并第一个序列与最后一个项目 如果最后一个项目 在第二个序列中 是独立事件 则作为独立事件加入 否则，作为 最后一个事件的一项 加入 候选4-序列 <1 5 (3 4)> 候选4-序列 < > 这个方案是完备的吗？即，这样产生的候选k-序列没有遗漏任何可能的频繁k-序列吗？

35 PrefixSpan算法：形式定义 给定一个序列 α=<a1a2an> β= <b1b2…bm >是α的前缀，如果
m≤n 对于所有的i <m，bi=ai am-bm的所有频繁项按字典序排在bm后 γ= <rmrm+1…rn >是α关于前缀β的后缀 rm=am-bm，如果rm不为空，一般写成(_...) 对于所有的i >m，ri=ai 序列：<a(abc)(ac)d(cf)> 前缀 关于前缀的后缀 <a> <(abc)(ac)d(cf)> <aa> <(_bc)(ac)d(cf)> <ab> <(_c)(ac)d(cf)>

36 PrefixSpan算法思想 分治 扫描数据集，得到频繁1项
以α为前缀的序列模式挖掘问题可以拆分为若干个互不相交的以α β为前缀的序列模式挖掘问题 扫描数据集，得到频繁1项 挖掘以频繁1项为前缀的序列模式 对于每个k前缀 递归的挖掘k+1前缀

37 PrefixSpan算法：例子 min_support =2 挖掘前缀<a>序列模式 挖掘前缀<b>序列模式 …
L1 频率 a 2 b 4 _b c _c 1 d _d e _e f _f SID sequence 10 <a(abc)(ac)d(cf)> 20 <(ad)c(bc)(ae)> 30 <(ef)(ab)(df)cb> 40 <eg(af)cbc> SID sequence 10 <(abc)(ac)d(cf)> 20 <(_d)c(bc)(ae)> 30 <(_b)(df)cb> 40 <(_f)cbc> 扫描 局部 频繁 项 序列数据集S min_support =2 扫描，得到频繁1项集 前缀a的投影数据集 每条记录包含<a> 且是原记录中以<a>的第一次出现 为前缀的子序列 L1 频率 a 4 b c d 2 E 3 f g 1 挖掘前缀<a>序列模式 挖掘前缀<b>序列模式 … 挖掘前缀<f>序列模式 分治 递归挖掘前缀<aa>, <ab>, <(ab)>, <ac>, <ad>, <af>的序列模式

38 频繁子图挖掘的意义: AIDS Compounds are active, inactive or moderately active (CA, CI, CM)

39 频繁子图定义 给定一个图数据集D={G0,G1,…GN} ，其中每个图是标号图，即图中各顶点和边带有标号
图g的支持度计数是 D中包含 g 为子图的图数目 g是频繁[连通] 子图如果图数据集D中包含g作为子图的图数目 support(g)≥minSup 分子结构图，节点V，点的标号N(V)={O,H,S,N…}，边E，边的标号L(E)={-,=…} min_support =2 频繁子图

40 Apriori算法 从只包含1条边的子图开始 for 由{K-1}-边频繁子图生成K-边子图候选集合 剪枝 计算支持度 end
minSup=2 从只包含1条边的子图开始 for 由{K-1}-边频繁子图生成K-边子图候选集合 剪枝 计算支持度 end

41 同构 图G和G’同构 图 G和图 G′同构，如果存在双射f:V↔V’ 子图同构 G的子图和g同构 这两图一样吗？

42 gSpan算法基本思想 不产生候选 分治 递归 模式增长 子图同构检验是算法瓶颈 DFS编码

43 DFS编码 对图进行深度优先遍历 所有节点根据发现时间排序 所有边表示为五元组(i,j,ni,lij,nj)
最后发现的节点叫做最右节点 从第一个节点到最右节点的直线路径叫做最右路径 所有边表示为五元组(i,j,ni,lij,nj) 前向边i<j 后向边i>j 边的排序：e1<e2, iff 同是前向边，且j1<j2 同是后向边，且i1<i2或者i1=i2&& j1<j2 e1是前向边，e2是后向边，且j1<=i2 e1是后向边，e2是前向边，且i1<j2 根据边的次序得到的边序列是图的DFS编码

44 DFS编码：例子 同一个图的不同DFS编码 B:v0,v1,v4 C:v0,v4 D:v0,v1,v2,v3,v4hg

45 确定唯一DFS code 一个图可能有多个DFS code 选择最小的DFS code=唯一编码 因为有label，所以考虑字典序
对于两个序列 序列a,长度为m v.s. 序列b，长度n a≤b 如果b比a长(n≥m)，每个元素相等 如果有某个位置 这个位置之前的 较大点 较小的点 边label 边排序

46 最小DFS编码：例子 同一个图的不同DFS编码 次小 最小 最大 B:v0,v1,v4 C:v0,v4 D:v0,v1,v2,v3,v4hg

47 DFS 编码树 思想：用树结构的增长寻找/计数频繁同构子图 DFS编码增长 树每个节点代表一个DFS编码 一棵树代表了所有可能的频繁子图
最右节点+后向边 最右路径+前向边 考虑字典序

48 DFS编码树的剪枝 Min_support=2 红>绿>蓝

49 gSpan算法