关联分析与频繁模式挖掘.ppt

第十一讲 关联规则,邓志鸿 北京大学信息科学技术学院,2019年7月11日星期四,内容,简介 基本概念 关联分析基本方法 基本内容 频繁模式挖掘 关联规则生成 模式评估,关联规则,1993年SIGMOD大会上Agrawal等人首次提出 关联规则挖掘 (association rule mining) 目的：发现数据中内在的规律性 人们通常会同时购买什么样的商品？ Beer and diapers? 购买微机后，接下来用户通常会有什么购物行为？ 哪种DNA对某个新药敏感？ 应用 Basket data analysis, cross-marketing, catalog design, sale campaign analysis, Web log (click stream) analysis, and DNA sequence analysis. 核心任务 频繁模式 (Frequent pattern) 在数据集（库）中频繁出现的模式（项集 (a set of items)、子序列 (subsequences)、 子结构 (substructures) 等）。,内容,简介 基本概念 频繁模式挖掘基本方法 基本内容 频繁模式挖掘 关联规则生成 模式评估,基本概念,Association Rule Analysis 给定事务集合，根据某些项的出现来预测其它项的出现,Market-Basket transactions,Example of Association Rules,Diaper Beer, Milk, Bread Eggs,Coke, Beer, Bread Milk,隐含着内在关联，而非偶然现象,基本概念,项 (Item) 最小的处理单位 例如：Bread, Milk 事务 (Transaction) 由事务号和项集组成 例如： 事务数据库 由多个事务组成 项集 (Itemset) 一个或多个项 (item) 的集 例如：Milk, Bread, Diaper k-项集 (k-itemset) 包含k个项的集合,基本概念,包含关系 令T为一事务，P为一项集。称T包含P，如果P是T的子集 记T P 或 P T 支持度计数 (Support count) 事务数据库中包含某个项集的事务的个数 例如： (Milk, Bread,Diaper) = 2 支持度 (Support) 事务数据库中包含某个项集的事务占事务总数的比例。 例如： s(Milk, Bread, Diaper) = 2/5 频繁项集 (Frequent Itemset) 令P为任何一个项集，称P为频繁项集，如果P的支持度不小于指定的最小阈值 (minsup threshold),基本概念,Example:,关联规则 (Association Rule) 表达形式：X Y (s, c) 其中， X 和 Y 都是项集，s是规则的支持度，c是置信度 例子： Milk, Diaper Beer (0.4, 0.67) 规则评估度量指标 支持度Support (s) 同时包含X和Y的事务占事务总数的比例 置信度Confidence (c) 在所有包含X的事务中包含Y的事务所占比例,内容,简介 基本概念 关联分析基本方法 基本内容 频繁模式挖掘 关联规则生成 模式评估,关联规则分析内容,给定一个事务数据库TD，关联规则挖掘的目标是要找到所有支持度和置信度都不小于指定阈值的规则。 支持度 minsup threshold 置信度 minconf threshold 穷举法 (Brute-force approach) 列出所有可能的规则 对每条规则计算其支持度和置信度 通过阈值minsup 和 minconf 过滤无效规则,可计算性？,计算复杂性分析,给定 d 个不同项： 项集数目等于2d 所有可能的关联规则总数等于：,如果 d=6 则 R = 602,关联规则分析,Example of Rules: Milk,Diaper Beer (s=0.4, c=0.67) Milk,Beer Diaper (s=0.4, c=1.0) Diaper,Beer Milk (s=0.4, c=0.67) Beer Milk,Diaper (s=0.4, c=0.67) Diaper Milk,Beer (s=0.4, c=0.5) Milk Diaper,Beer (s=0.4, c=0.5),思考 所有规则都对应于把同一项集分成两个部分 Milk, Diaper, Beer 源自同一项集的规则有相同的支持度，但是置信度不同 因此，我们可以分别处理对支持度和置信度的要求 X Y s=s(XY) / |DB|, c= s(XY) / s(X),关联规则分析,分两步执行： 挖掘频繁项集 生成所有支持度 minsup的项集 构造规则 用每个频繁项集生成高置信度的规则 对频繁模式的每次分割（一分为二）就形成一条规则，再判断该规则是否满足最小置信度阈值条件。 但是，挖掘频繁模式仍然是一个“计算昂贵”的工作。,Milk, Diaper, Beer s=0.4,Milk s=0.8,Milk Diaper,Beer s=0.4, c=0.4/0.8=0.5,关联规则分析的核心,内容,简介 基本概念 关联分析基本方法 基本内容 频繁模式挖掘 关联规则生成 模式评估,频繁模式挖掘重要性,发现数据集中的有价值的重要性质 是其它数据挖掘任务的基础 关联分析：Association rules analysis Mining Frequent Itemset 因果分析：causality analysis 序列、结构模式：Sequential, structural (e.g., sub-graph) patterns 时空、多媒体、时间序列、流数据模式分析 分类 聚类 数据仓库 语义数据压缩 推荐系统等其他应用,生成频繁项集,给定d个项，有 2d 个可能的候选项集,生成频繁项集,穷举法 (Brute-force approach) 网格中每个项集都是候选的频繁项集 通过扫描一次数据库，可以得到每个候选项集的支持度 比较每一条事务和每个候选项集 计算复杂度O(NMw) N为事务数目， M = 2d 为候选项集， w为一次比较的计算代价,内容,简介 基本概念 关联分析基本方法 基本内容 频繁模式挖掘 关联规则生成 模式评估,频繁项集挖掘算法,Apriori算法 第一个算法 用了Apriori性质 所有挖掘算法的基础 基于事务列表的算法 Eclat算法 基于节点列表的算法 PPV算法、Prepost算法,Apriori算法,候选生成类型 Apriori性质 反单调性 基本思想 由长度为k的频繁模式生成长度为(k+1)的候选模式 计算长度为(k+1)的候选模式的支持度，从而获得长度为(k+1)的频繁模式,Aprioir算法,Apriori 性质: 如果一个项集是频繁的，那么它的所有子集都是频繁的。 也称为反单调性 Apriori 性质成立的原因如下： 任何一个项集的支持度不可能超过其子集的支持度,Apriori 性质演示,裁减所有超集,Apriori 算法示例,1st scan,C1,L1,L2,C2,C2,2nd scan,C3,L3,3rd scan,Supmin = 2,Apriori 算法（伪码）描述,Ck: Candidate itemset of size k Lk : frequent itemset of size k L1 = frequent items; for (k = 1; Lk !=; k+) do begin Ck+1 = candidates generated from Lk; for each transaction t in database do increment the count of all candidates in Ck+1 that are contained in t Lk+1 = candidates in Ck+1 with support min_support end return k Lk;,Apriori 算法重要细节,如何生成候选项集？ Step 1: 自连接 (self-joining) Lk Step 2: 裁减 (pruning) 如何计算候选项集的支持度？ 例子 L3=abc, abd, acd, ace, bcd Self-joining: L3*L3 由abc 和 abd 生成abcd 由acd 和 ace 生成acde Pruning: 因为ade不在L3中，所以不用处理acde （它不可能是频繁项集） C4=abcd,Apriori 算法生成候选项集,Suppose the items in Lk-1 are listed in an order Step 1: self-joining Lk-1 insert into Ck select p.item1, p.item2, , p.itemk-1, q.itemk-1 from Lk-1 p, Lk-1 q where p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 q.itemk-1 Step 2: pruning For all itemsets c in Ck do For all (k-1)-subsets s of c do if (s is not in Lk-1) then delete c from Ck,Apriori算法在构造候选k-项集的时候利用了频繁k-1项集进行裁减，有效地降低了候选项集的数量。 但是这个方法对生成候选2-项集基本上没有太大作用。 令频繁1-项集个数为n，则候选2-项集个数为n(n-1)/2 基本方法 第一次扫描事务数据库时计算2-项集的支持度，从而直接获得频繁2-项集,Apriori 算法减少候选项集数目,Apriori 算法直接挖掘频繁2-项集,很多实验表明，在Apriori 算法（或基于Apriori 的算法）频繁模式挖掘过程中，频繁2-项集的查找最费时间 频繁1-项集很多，所以候选2-项集就非常多 方法 在扫描事务数据库时，同时计算每个事务所包含2-项集的支持度。 第一次扫描数据库，同时找到频繁1-项集和频繁2-项集,发现频繁2-项集示例,A, C, D A, C, A, D, C, D B, C, E B, C, B, E, C, E ,频繁项集挖掘算法,Apriori算法 第一个算法 用了Apriori性质 所有挖掘算法的基础 基于事务列表的算法 Eclat算法 基于节点列表的算法 PPV算法、Prepost算法,Eclat算法,Apriori算法主要缺点 多次扫描数据库，候选项集支持度计算代价高 垂直数据表示 (vertical data format) Tidset Tidset 令P为一个项集，其Tidset定义如下： Tidset(P)=t.Tid| P t 性质1：P的支持度等于Tidset(P)势（包含元素的个数） 性质2：令Sk = Tidset(P) | P是频繁k-项集，则对任何CCk+1 (候选k+1项集)， Tidset(C)可由Sk中的两个元素Tidset (X) 和Tidset (Y)得到，并且Tidset (C) Tidset (X) Tidset (Y) X C1 C2 Ck-1 Ck Y C1 C2 Ck-1 Ck+1 Eclat算法思想与Apriori基本一致，只不过在获取候选项集的Tidset直接用两个频繁项集的Tidset的交。而候选项集的支持度就直接等于|Tidset|,垂直数据表示,Eclat算法 示例,A,C,D,T,W,AC,AD,AT,AW,CD,CT,CW,DT,DW,TW,ACT,ACW,ATW,CDW,CTW,ACTW,Minsup=3,频繁项集挖掘算法,Apriori算法 第一个算法 用了Apriori性质 所有挖掘算法的基础 基于事务列表的算法 Eclat算法 基于节点列表的算法 PPV算法、Prepost算法,基于节点列表的频繁模式挖掘算法,垂直算法（如Eclat） 简单、易实现 时间效率 对稠密数据而言，较差 对稀疏数据而言，较好 FP-Growth算法 复杂、不易实现 时间效率高 对稠密数据而言，好 对稀疏数据而言，一般 Question 是否可以设计一个算法，同时具有垂直算法简单、易实现，而又具有较高效率的特点。,分析,Eclat 优点 采用垂直数据格式，使得计算项集的支持度变得简单。候选项集的Tidset直接由两个频繁项集的Tidset的交获取。而候选项集的支持度就等于|Tidset|。 问题 Tidset是否足够简洁和压缩。在分布不变的情况下，与数据库的大小呈线性关系。 FP-Growth 优点 采用压缩的FP-tree结构，使得搜索空间极大地缩小 问题 重复递归构造FP-tree费时费力 复杂，对编程技能要求高,分析示例Tidset,Tidset,A: 1,3,B: 2,3,4,C: 1,2,3,D: 5,E: 2,3,4,F: 5,表1,分析示例Tidset,Tidset,A: 1,3,6,8, ,496,498,B: 2,3,4,7,8,9,497,498,499,C: 1,2,3,6,7,8 , 496, 497, 498,D: 5,10,500,F: 5,10,500,表1数据重复100次,表2,E: 2,3,4,7,8,9,497,498,499,分析示例Tidset,显然，对给定的阈值，表1和表2所包含的频繁项集是一样的，且这些频繁项集的支持度是一样的。 但是，如果采用Eclat算法，挖掘表2中频繁项集的时间是挖掘表1中频繁项集的时间的100倍 似乎很不合理,分析示例FP-Tree,表1,C:1,B:3,C:2,E:2,A:1,A:1,E:1,D:1,F:1,B C E A D F,分析示例FP-Tree,表2,C:100,B:300,C:200,E:200,A:100,A:100,E:100,D:100,F:100,B C E A D F,FP-Tree的结构基本上没有变化，只不过每个节点上的计数值增加了100倍,分析发现,C:1,B:3,C:2,E:2,A:1,A:1,E:1,D:1,F:1,B C E A D F,N2,N1,N3,N4,N5,N6,N7,N8,N9,A.support = 2,CA.support = 2,N2.count = 1,N6.count = 1,C.support = 3,N1.count = 1,N4.count = 2,N2.count = 1,N6.count = 1,CA的support等于所有如下节点的count值之和： (1) 该节点的lable为A (2) 该节点的祖先节点中有标签为C的节点,是一个普遍的结论，是节点编码的基础,基于节点列表的算法,每个项或项集都由节点列表表示。 为了有效表达节点之间的包含关系，需要对节点进行编码 杜威编码 前后序编码,CA N2 , N6,杜威编码方法,缺点 编码的大小与树的深度成正比，且与树的宽度有关系。 存储代价高 包含关系的判断与树深度相关，效率不高 能否解决呢？ 可以，采用树的前后序编码,C:100,B:300,C:200,E:200,A:100,A:100,E:100,D:100,F:100,1.1.1,1.1,1.2.1,1.2,1.3,1,1.2.2,1.3.1,,.1,1.2.1是.1的前缀，所以编码为1.2.1的节点是编码为.1的节点的祖先,树的前后序编码,给定一个树，每个节点N对应一个二元组（Npre, Npost）。 Npre代表按前序遍历树（深度优先）时访问到节点N时的编号（序号），Npost代表按后序遍历（深度优先）树时访问到节点N时的编号（序号）。 前后序编码的性质 性质0：X,Y是两个节点，X是Y的祖先节点，当且仅当Xpre Ypost,前后序编码例子,R,A,C,D,F,B,E,R,A,C,D,F,B,E,R,A,C,D,F,B,E,前序次序 先根次序,后序次序 后根次序,RABCDFE,1,1,2,3,4,5,6,7,BAFDECR,1,2,3,4,5,6,7,R,A,C,D,F,B,E,(1,7),(2,2),(3,1),(4,6),(5,5),(6,3),(7,5),基本概念PPC-tree,PPC-tree 类似与FP-tree的一棵前缀树（项按照支持度排序） 每个节点都有一对,C:1,B:3,C:2,E:2,A:1,A:1,E:1,D:1,F:1,(1,10),(2,2),(3,1),(4,7),(5,5),(6,4),(7,3),(8,6),(10,8),(9,9),N2,N1,N3,N4,N5,N6,N7,N8,N9,表1,基本概念PP-code,对PPC-tree 中的每个节点N，称为 节点N的PP-code。 例如： 节点N1 的PP-code 是 节点N2 的PP-code 是,Node-list定义,Node-list：一种节点列表的表示形式 1-itemset (1-项集)的Node-list 给定PPC-tree树， 1-itemset i 的Node-list定义为序列 序列由PPC-tree树中节点标签(label)为i的所有节点的PP-code组成。 PP-code 在序列中的位置按照节点前序序号排列 C的Node-list为, A的Node-list为, ,Node-list定义,约定：所有项的总集I=i1, i2, , iN按照项的支持度降序排列的序列。对任何0 s t N，记is it 。 约定：任何项集中的项按其在I中的序排列 2-itemset (2-项集)的Node-list 给定两个1项集i1 and i2 (i1 i2) ，他们的Node-list分别为 , , , 和, , , 。2项集i1i2的Node-list定义如下 令 是i2的Node-list 中的一个元素，如果存在 i1的Node-list，满足是的祖先，则属于i1i2的Node-list. i1i2的Node-list中的元素按照节点的前序序号排列。,Node-list定义,C的Node-list为, A的Node-list为, 故，CA的Node-list为, ,21，故是的祖先节点，故属于CA的Node-list,53，故是的祖先节点，故属于CA的Node-list,Node-list定义,k-itemset (k-项集)的Node-list 令P = i1 i2i(k-2) ixiy (k 3)是一k-项集，P1 = i1 i2i(k-2)ix的Node-list是 , , , ，P2 = i1 i2i(k-2)iy的Node-list是 , , , ，则P 的Node-list定义如下： 令 是P2的Node-list 中的一个元素，如果存在 P1的Node-list，满足是的祖先，则属于P的Node-list. P的Node-list中的元素按照节点的前序序号排列。,Node-list定义,CA的Node-list为, CE的Node-list为 CEA的Node-list为,63，故是的祖先节点，故属于CEA的N-list,3不是的祖先节点，CE中只有一个元素 ，所以不存在元素是的祖先节点，故不属于CEA的N-list,Node-list现象,C的Node-list为, 1+2=3=C.support E的Node-list为, 2+1=3=E.support A的Node-list为, 1+1=2=A.support CA的Node-list为, 1+1=2=CA.support CE的Node-list为 2=CE.support CEA的Node-list为 1=CEA.support,Node-list的重要性质1,性质1：令k-项集P = i1 i2ik的Node-list为, , , , 有 P.support = z1 + z2 + zm 证明 按照前缀树PPC-tree的构造， P 的Node-list中的节点记录了项集i1 i2ik在数据库中出现的次数。 详细证明见： Zhihong Deng and Zhonghui Wang. A New Fast Vertical Method for Mining Frequent Patterns. International Journal of Computational Intelligence Systems, 3(6): 733 744, 2010. 下载网址：/faculty/system/dengzhihong/dengzhihong.htm,基于Node-list的挖掘算法,Scan transaction database and identify all frequent 1-items.Then, Construct PPC-tree. Based on PPC-tree, construct the N-list of each frequent 1-items Do the almost same procedures as Apriori algorithm Obtain the Node-lists of candidate (k+1)-itemsets by intersecting frequent k-itemsets by the definition of Node-lists. Based on the Node-lists of candidate (k+1)-itemsets, Obtain their supports. Get the frequent (k+1)-itemsets by filtering those candidate (k+1)-itemsets whose support is less than the given support threshold.,基于Node-list的挖掘算法效率,由算法描述可知，由k-项集的Node-list生成(k+1)-项集的Node-list的时间是决定算法效率的关键所。 令P1 = i1 i2i(k-2)ix的Node-list是 , , , ，P2 = i1 i2i(k-2)iy的Node-list是 , , , ，其中ix iy。我们要生成 P = i1 i2i(k-2) ixiy 的Node-list 根据定义，对P2的Node-list中的每一个元素, ，必须检查P1的Node-list中是否存在某个元素，该元素是,的祖先。如果存在，则把加入到P的Node-list中，否则不加入。 一个直观的做法：对P2的Node-list中每个元素，都与P1的Node-list中元素进行祖先后代关系的检查，其算法复杂都为O(m*n) 是否有更为高效的方法呢？ Yes, 有O(m+n)的方法,Node-list的重要性质2,设P为1-项集，令其Node-list为： , , , ， 性质 2 对任何i, j 1, 2, k)，且i j 有 xPi xPj yPi yPj,C的Node-list为, E的Node-list为, A的Node-list为, ,Node-list的重要性质3,性质3： 令P1 = i1 i2i(k-2)ix的Node-list是 , , , ，P2 = i1 i2i(k-2)iy的Node-list是 , , , ，其中ix iy。如果xP1s x P2t ，则对任何 s k m， 1 v t成立x P1k x P2v x P1k xP1s x P2t x P2v 性质3说明不可能的子孙节点。,Node-list的高效生成算法,简记P1的Node-list为p11, p12, , p1m，P2的Node-list为p21, p22, , p2n。其中p1i = , p2j = ，由 P1和P2的生成的k-项集记为P 先看p11 如果对所有的p2i p21, p22, , ,p2v都成立 xP11 xP2i，则由性质0可知， P2中的所有元素都不可能是p11的子孙。另外，由性质2可知xP1k xP11 (1 yP2k ：表明p2k 是p11 的子孙，把p2k插入P的Node-list中。继续比较p11和p2(k+1) 。 yP11 k, yP11 k)。这时，对p11处理结束，转而比较p12和P2 中的元素。 因为对任何sk, p2s 要么是p11的子孙，要么其前序序号xP2s xP11。对第一中情况， p2s 不可能是p12的子孙。否则p11和p12有祖孙关系，因为p11和p12的标签一样，所以根据树的构造算法这是不可能。对第二种情况， xP2s xP11 ，而xP11 xP12 。有xP2s xP12 。故p2s 不可能是p12的子孙。 由上分析， p2s 不可能是p12 的子孙。所以对p12的比较，从p2k开始。对p12的处理同p11 。这样处理的方式避免了p12与P2中已经和p11比较过的元素（ p2k 除外）再进行比较，从而实现线性时间复杂度O(n+m)。,Node-list的高效生成算法示例,(1,25),(2,12),(3,4),(4,2),(6,3),(5,1),(7,8),(11,11),(8,5),(9,7),(10,6),(12,9),(13,10),(14,24),(15,15),(16,13),(17,14),(18,19),(22,23),(19,17),(21,18),(23,21),(25,22),(20,16),(24,20),The node-list of i1i2,The node-list of i1i3,Node-list的高效合并算法示例,i1i2 =, , i1i3 =, , , , 假设i2i3,第1步检测祖孙关系,75, 所以节点(7, 8) 不可能是节点(5, 1)的祖先。 因此第2步就要考察(7, 8)和(8, 5)的关系,i1i2 = , , i1i3 = , , , , ,i1i2i3 =,Node-list的高效合并算法示例,第2步检测祖孙关系,i1i2 = , , i1i3 =, , , , ,7 5。所以节点(7, 8) 是节点(8, 5)的祖先。故把输入到i1i2i3 的Node-list 中。 第三步，检测(7, 8) 与节点(10, 6)的祖孙关系,i1i2i3 =,添加,Node-list的高效合并算法示例,第3步检测祖孙关系,i1i2 = , , i1i3 =, , , , ,7 6。所以节点(7, 8) 是节点(10, 6)的祖先。故把输入到i1i2i3 的Node-list 中。第四步，检测(7, 8) 与节点(18, 19)的祖孙关系。,i1i2i3 =, ,添加,Node-list的高效合并算法示例,第4步检测祖孙关系,i1i2 = , , i1i3 =, , , , ,7 是否与i1i3节点列表中的元素有祖孙关系。,i1i2i3 =, ,Node-list的高效合并算法示例,第5步检测祖孙关系,i1i2 = , , i1i3 =, , , , ,其实不需要检测(15, 15) 与(18, 19)前面节点的祖孙关系。 因为(18, 19)前面节点要么是(7,8)的子孙，要么其前序序号小于7。 如果是(7,8)的子孙，就不可能是(15,15)的子孙（否则(7，8)和(15,15)之间有祖孙关系。这是可能的，因为它们的标签一样）。 如果前序序号小于7，则必然小于(7,8)后续节点的前序序号，故也不可能是(15,15)的子孙。 这就意味着(18, 19)前面的节点不可能是(15, 15) 的子孙。因此第5步直接比较(15, 15) 与(18, 19) 的祖孙关系。 虽然15 是否与i1i3节点列表中的元素有祖孙关系。,i1i2i3 =, ,Node-list的高效合并算法示例,第6步检测祖孙关系,i1i2 = , , i1i3 =, , , , ,与第五步一样，不需要检测(23, 21) 与(18, 19)前面节点的祖孙关系，而是直接比较(23, 21) 与(18, 19)的祖孙关系。 因为23 18 ，所以(23, 21)不是(18, 19)的祖先。第7步要继续检测(23, 21)与(18, 19)后续节点(24, 20)的祖孙关系。,i1i2i3 =, ,Node-list的高效合并算法示例,第7步检测祖孙关系,i1i2 = , , i1i3 =, , , , ,因为23 20，故(23, 21)是 (24, 20)的祖先。把输入到i1i2i3 的Node-list 中。i1i3节点链表没有可处理的节点，整个操作结束，得到了i1i2i3 的Node-list。,i1i2i3 =, , ,添加,PPV 性能比较,在稠密数据库上与FP-growth相当 在稀疏数据库上表现优秀 仍然受制于候选-生成模式的限制,基于节点列表方法N-list,约定：所有项的总集I=i1, i2, , iN按照项的支持度降序排列的序列。对任何0 s t N，记is it 。 约定：任何项集中的项按其在I中的序排列 1-itemset (1-项集)的N-list同其Node-list 2-itemset (2-项集)的N-list定义如下 给定两个1项集i1 and i2 (i1 i2) ，他们的N-list分别为 , , , 和, , , 。2项集i1i2的Node-list定义如下 令 是i2的Node-list 中的一个元素，如果存在 i1的Node-list，满足是的祖先，则属于i1i2的Node-list. i1i2的Node-list中的元素按照节点的前序序号排列。,基于节点列表方法N-list,the N-list of k-itemset Let P = ixiy ik-2 i2 i1 be a itemset (k 3), the N-list of P1 = ixik-2 i2 i1 be , , , , and the N-list of P2 = iy ik-2 i2 i1 be , , , .The N-list of P is a sequence of PP-codes according to pre-order ascending order and generated by intersecting the N-lists of P1 and P2, which follows the rule below: First, for any the N-list of P1 (1pm) and the N-list of P2 (1qn), if is an ancestor of , then is added to the N-list of P.After that, we get an initial N-list of P. Second, we check the initial N-list of P again and merge the nodes with the form of to get a new node .,N-list示例,B的N-list为, A的N-list为, ,C的N-list为, A的N-list为, ,BA的N-list为,CA的N-list为, ,BCA的N-list为,N-list 性质,N-list具有Node-list的所有性质。除此之外， N-list还具有单路径性质(single path property)，从而使得基于N-list的算法PrePost能在局部实现直接挖掘频繁模式而不用生成候选项集，从而有效克服了基于Node-list算法的缺点，极大提升了挖掘速度。 单路径性质(single path property) Let P1 = j1i1i2iv, P2 = j2i1i2iv, , Pn = jni1i2iv, (j1 j2 jn i1 i2 iv) 是n个项集，记Pa Pb = jajbi1i2iv (1 a b n). 如果Pn的N-list 只包含一个PP-code，并且存在集合 S = s1, s2, , st (1 s1 s2 s2 n)满足Pm Pn (m S )的N-list 不为空，则成立： 对任意m S, Pm Pn 的N-list只包含一个PP-code，并且其支持度等于Pn的支持度。 令Nodem代表PPC-tree中对应Pm Pn 的节点，对S中任何sx和sy，如果 sx sy，则Nodesx是Nodesy的祖先。 项集jx1jx2jxk jni1i2iv (1 x1 x2 xk n, 且x1, x2,xk S )的支持度等于Pn的支持度。,N-list 性质,C:1,B:3,C:2,E:2,A:1,A:1,E:1,D:1,F:1,(1,10),(2,2),(3,1),(4,7),(5,5),(6,4),(7,3),(8,6),(10,8),(9,9),N2,N1,N3,N4,N5,N6,N7,N8,N9,EA的N-list为 CA的N-list为 BA的N-list为,BAEA= BEA的N-list为 CAEA= CEA的N-list为,无须通过交BEA和CEA的N-list形成BCEA的N-list来获取BCEA的支持度。利用单路径属性可直接知道BCEA的支持度为1，即EA的支持度。,基于N-list的PrePost 性质,除了采用单链性质进行局部无候选生成直接获取频繁项集的挖掘策略外，PrePost基本上与PPV相同。具体请参见如下文献 Deng ZhiHong, Wang ZhongHui，and Jiang JiaJian. A New Algorithm for Fast Mining Frequent Itemsets Using N-Lists. SCIENCE CHINA Information Sciences 55 (9): 2008-2030, 2012. 下载地址：/faculty/system/dengzhihong/dengzhihong.htm,PrePost 性能比较,在真实稠密数据库（Accidents）和人造稀疏数据库（T25I10D100K ）上均略胜FP-Growth和FP-Growth*(最好的FP-Growth实现，FIMI03冠军),PrePost+,采用了等价提升策略，速度明显提升。细节见课程网站附件,节点列表小节,形式简单、效率高、博采众长 兼具Apriori算法、垂直算法和FP-Growth算法的优点 发展状况 Nodesets： Zhi-Hong Deng, Sheng-Long Lv. Fast mining frequent itemsets using Nodesets. Expert Systems with Applications, 41(10): 4505-4512, 2014 DiffNodesets Zhi-Hong Deng. DiffNodesets: An efficient structure for fast mining frequent itemsets. Applied Soft Computing, 41: 214-223, 2016. 下载地址 /faculty/system/dengzhihong/dengzhihong.htm,内容,简介 基本概念 关联分析基本方法 基本内容 频繁模式挖掘 关联规则生成 模式评估,生成关联规则,给定频繁项集L，找出 L的所有非空子集f， 满足 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, 令|L| = k，则有2k 2 个候选的关联规则 (不考虑 L and L),生成关联规则,如何有效地从频繁项集中生成关联规则？ 一般而言，置信度并不具有反单调性质 (anti-monotone property) 例如：c(ABC D)可能比 c(AB D) 大，也可能比c(AB D) 小 但是，由同一个项集生成的规则（按原顺序）却具有反单调性质 例如：L = A,B,C,D: c(ABC D) c(AB CD) c(A BCD),证明,基于Apriori算法的关联规则生成,Lattice of rules,Pruned Rules,Low Confidence Rule,基于Apriori算法的关联规则生成,通过合并具有共同前缀结论的关联规则生成候选规则 合并(CD=AB,BD=AC) 将生成D = ABC 裁减D=ABC如果其子集 AD=BC置信度小于最小阈值,内容,简介 基本概念 关联分析基本方法 基本内容 频繁模式挖掘 关联规则生成 模式评估,模式评估 (Pattern Evaluation),关联规则算法能产生大量的规则 其中很多是无意义或是冗余的 冗余 例如：A,B,C D 和 A,B D有同样的支持度和置信度 兴趣度 (Interestingness) 反映模式的重要程度，用于裁减模式或对模式排序 支持度和置信度是用到的两个度量,兴趣度的应用,计算兴趣度,给定规则 X Y，计算规则兴趣度的信息可完全由列联表给出 (contingency table),X Y的列联表,用于定义不同的度量 support, confidence, lift, Gini, J-measure, etc.,置信度不足,统计独立性,1000个学生 600个会游泳 (S) 700个会骑自行车 (B) 420个会游泳和骑车 (S,B) P(SB) = 420/1000 = 0.4