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

数据挖掘领域的十大经典算法 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. 2000. Mining frequent patterns without candidate generation. In SIGMOD '00. 他引超过3000次 GSP: Srikant, R. and Agrawal, R. 1996. 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. 2002. gSpan: Graph-Based Substructure Pattern Mining. In ICDM '02.

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

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%

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%)

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

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

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

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

连接步策略 对项编码 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}

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

散列树的数据结构与构造 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);

散列树的构造：例子 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

基于散列树的支持度计数 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); 1 2 3 5 6 10 Level=1 K-1 W-K+1 2 + 3 5 6 10 t: t’=trim(t):

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

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

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)

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

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);

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

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

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

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树

关联规则 枚举的方法 给定频繁项集 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)

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

关联规则产生算法 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);

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

兴趣度度量: 提升度 强关联规则不一定有趣 如果吃麦片占所有学生的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]

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

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

序列模式的形式定义：例子 序列数据集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

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

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

候选产生的方法：例子 第一个序列去掉第一个项目，第二个序列去掉最后一个项目 子序列 <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-序列 <1 2 3 4> 这个方案是完备的吗？即，这样产生的候选k-序列没有遗漏任何可能的频繁k-序列吗？

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)>

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

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>的序列模式

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

频繁子图定义 给定一个图数据集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 频繁子图

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

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

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

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编码

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

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

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

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

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

gSpan算法