最新 数据挖掘方法关联规则 ppt课件教案讲义（附代码数据）图文

数据仓库与数据挖掘（国院）,挖掘频繁模式 关联和相关性：基本概念和方法,目录,2,【原创】定制代写开发 r/python/spss/matlab/WEKA/sas/sql/C+/stata/eviews 数 据挖掘和统计分析可视化调研报告程序等服务（附代码数据）,咨询邮箱： 有问题到淘宝找“大数据部落”就可以了,3,6.1基本概念,频繁模式（Frequent pattern）: 是频繁出现在数据集中的模式（如项集、序列(序列模式)或子结构）。 First proposed by Agrawal, Imielinski, and Swami AIS93 in the context of frequent itemsets and association rule mining 驱动力: 发现数据中潜藏的规律 什么商品经常会被客户一起购买? Beer and diapers?!(啤酒+尿布) 购买商品是否有一般序列模式，如买了 PC，下一步还会买什么? DNA种类与新药品成分之间有什么关联关系? Web文档是否能自动分类，与类别之间存在怎样的关联关系? 应用 购物篮分析(推荐系统), Web 日志(点击流) 分析, DNA序列分析,4,6.1.1购物篮分析：一个经典例子,挖掘顾客放入“购物篮”中的商品间的关联，分析购买习惯 可以将全域看成商品的集合，每种商品对应一个布尔向量，表示该商品是否购买 每个购物篮可用一个布尔向量表示 挖掘频繁关联的购买模式，以关联规则的形式表示 computerantivirus_softwaresupport=2%;confidence=60% 规则兴趣度度量：满足最小支持度（min_sup）、最小置信度(min_conf)要求,则称强关联规则 （相对）支持度（Support）：2%显示两者被同时购买的概率 置信度（Confidence）60%意味着购买计算机的顾客中60 %的可能性会买杀毒软件，是条件概率值 阈值可由用户或领域专家设定,5,2. 数据格式,事务数据格式 事务处理数据对于每个交易或项目具有一个单独的记录 表格格式 篮子 数据或 真值表 数据 课堂示例数据文件：weather_original.csv,5,6,6.1.2基本概念频繁项集,项集: 项的集合 k-项集 X = x1, , xk 频度, 或者支持度计数、或计数: 包含项集的事务数，也称绝对支持度 项集是频繁的，需满足支持度大于等于最小支持度阈值（min_sup ） 关联规则：形如A=B的蕴含式 满足条件，A、B都不为空，且交集为空，具有支持度s,为包含(AB)的百分比,7,6.1.2基本概念关联规则,Find all the rules X Y with minimum support and confidence support, s, probability that a transaction contains X Y support(X=Y)=P(XY) confidence, c, conditional probability that a transaction having X also contains Y confidence(X=Y)=P(Y/X)=support(XY)/support(X) Let minsup = 50%, minconf = 50% Freq. Pat.: Beer:3, Nuts:3, Diaper:4, Eggs:3, Beer, Diaper:3,Customer buys diaper,Customer buys both,Customer buys beer,Nuts, Eggs, Milk,40,Nuts, Coffee, Diaper, Eggs, Milk,50,Beer, Diaper, Eggs,30,Beer, Coffee, Diaper,20,Beer, Nuts, Diaper,10,Items bought,Tid,Association rules: (many more!) Beer Diaper (60%, 100%) Diaper Beer (60%, 75%),8,挖掘关联规则的问题可以归纳为挖掘频繁项集 一般包含两步： 找出所有的频繁项集：根据定义，需满足最小支持计数 由频繁项集产生强关联规则：满足最小支持度的基础上、最小置信度 算法挑战 会产生大量频繁项集：项集是频繁的则它的子集也一定频繁 如，一个集合包含不同项集数是巨量的, 存储和计算是一个巨大挑战，e.g., a1, , a100 包含C1001 + C1002 + + C110000 = 2100 1 = 1.27*1030 子模式，需判断是否频繁 为优化算法，引入闭频繁项集、极大频繁项集,6.1.2基本概念关联规则,9,6.1.2基本概念闭频繁项集与极大频繁项集,闭频繁项集X（Closed frequent itemset）：如果 X 是频繁的，并且 不存在超项集Y, 即Y X，Y至少有一个元素不属于X, 使得X 、Y的支持度相同。(proposed by Pasquier, et al. ICDT99) 极大频繁项集（Maximal frequent itemset /Max- itemset ）： 如果X是频繁的，且不存在频繁超项集Y，使得Y X (proposed by Bayardo SIGMOD98) C是数据集D中满足最小支持度计数阈值的闭频繁项集集合 M是D中满足最小支持度计数阈值的极大频繁项集的集合 C可以导出频繁项集的完整集合 M只存储了极大频繁项集的支持度信息,10,示例：DB = a1, , a100, a1, , a50 ，仅含两个事务 Min_sup = 1. 闭频繁项集? C=a1, , a100: 1； a1, , a50: 2 极大频繁项集? M=a1, , a100: 1 所有频繁项集? C可推导出（1）a2,a45:2 (2) a8,a55:1 从M也可推导出前两个子集是频繁的，单不能确定它们的支持度计数,6.1.2基本概念闭频繁项集与极大频繁项集,目录,11,12,6.2频繁项集挖掘方法,Apriori: 通过限制候选产生发现频繁项集* 由频繁项集产生关联规则* 提高Apriori算法的效率* 挖掘频繁项集的模式增长方法* 使用垂直数据格式挖掘频繁项集* 挖掘闭模式和极大模式,13,Apriori (Agrawal & SrikantVLDB94)：逐层搜索的迭代方法，其中k项集用于探索k+1项集 首先，扫描数据库，累计每个项的计数，收集满足最小支持度的项，找出频繁1项集的集合，记为L1 然后对频繁1项集进行组合作为候选2项集,并扫描找出频繁2项集L2 依次类推,直到找到Lk 此算法为了提高效率，引用一个先验性质 频繁项集的所有非空子集也一定是频繁的 If beer, diaper, nuts is frequent, so is beer, diaper i.e., every transaction having beer, diaper, nuts also contains beer, diaper,6.2.1Apriori: 通过限制候选产生发现频繁项集,14,6.2.1Apriori: 通过限制候选产生发现频繁项集,如何使用Lk-1找出Lk,其中k2 连接步：通过将Lk-1 与自身连接产生候选k项集的集合Ck 剪枝步:Ck是Lk超集，也就是说， Ck的成员可以是也可以不是频繁的，但是所有的频繁k项集都包含在Ck中。 扫描数据库，确定Ck中每个候选的计数，从而确定Lk， Ck可能很大，根据先验性质，如果某个候选集的k-1子集不是频繁的，则可判定其不是频繁的，即可删除,Example of Candidate-generation L3=abc, abd, acd, ace, bcd Self-joining: L3*L3 abcd from abc and abd acde from acd and ace Pruning: acde is removed because ade is not in L3 C4 = abcd,15,Apriori 算法示例,Database TDB,1st scan,C1,L1,L2,C2,C2,2nd scan,C3,L3,3rd scan,Supmin = 2,16,Apriori 算法伪代码,Pseudo-code: 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 min_support end return k Lk;,17,如何产生候选集,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 forall itemsets c in Ck do forall (k-1)-subsets s of c do if (s is not in Lk-1) then delete c from Ck,18,6.2频繁项集挖掘方法,Apriori: 通过限制候选产生发现频繁项集* 由频繁项集产生关联规则* 提高Apriori算法的效率* 挖掘频繁项集的模式增长方法* 使用垂直数据格式挖掘频繁项集* 挖掘闭模式和极大模式,19,6.2.2 由频繁项集产生关联规则,一旦确定频繁项集，则可产生强关联规则： confidence(A=B)=P(B/A) =support_count(AB)/support-count(A) support_count( AB)表示包含AB的事务数， support_count(A)表示包含A的事务数 关联规则产生步骤 对于每个频繁项集l, 产生l的所有非空子集 对于l的每个非空子集s，如果support_count(l)/support-count(s)大于等于最小置信度阈值， 则输出规则“s=(l-s)”,20,Apriori 算法示例,Database TDB,L3,Supmin = 2,关联规则,B,C=E, confidence=2/2=100% B,E=C, confidence=2/3=66.7% C,E=B, confidence=2/2=100% B=C,E, confidence=2/3=66.7% C=B,E, confidence=2/3=66.7% E=B,C, confidence=2/3=66.7%,如果最小置信度阈值为70%,21,6.2频繁项集挖掘方法,Apriori: 通过限制候选产生发现频繁项集* 由频繁项集产生关联规则* 提高Apriori算法的效率* 挖掘频繁项集的模式增长方法* 使用垂直数据格式挖掘频繁项集* 挖掘闭模式和极大模式,22,6.2.3提高Apriori算法的效率,算法变形提高算法执行效率 基于散列的技术：散列项集到对应的桶中，并对桶中项集进行计数 划分：为找候选集划分数据，只需要两次数据库扫描 抽样：对给定数据的一个子集上挖掘 动态项集计数：在扫描的不同点添加候选项集 事务压缩：压缩进一步迭代扫描的事务数，不包含任何频繁k项集的事务不可能包含任何频繁（k+1）项集，可做相应标记或删除 ,23,6.2.3提高Apriori算法的效率-散列,A k-itemset whose corresponding hashing bucket count is below the threshold cannot be frequent Candidates: a, b, c, d, e Hash entries ab, ad, ae bd, be, de Frequent 1-itemset: a, b, d, e ab is not a candidate 2-itemset if the sum of count of ab, ad, ae is below support threshold,Hash Table,6.2.3提高Apriori算法的效率-划分,划分技术，只需两次数据库扫描 Scan 1: 算法把D中的事务划分成n个非重叠的分区，对于每个分区找出局部频繁项集 Scan 2:评估每个候选的实际支持度，确定全局频繁项集 局部频繁不一定全局频繁，但D中全局频繁项集必然至少出现在一个分区中，因此各个分区局部频繁项集组成D的全局候选项集 每个分区大小需要能够一次装载到内存中，以提高扫描性能,DB1,DB2,DBk,+,= DB,+,+,sup1(i) DB1,sup2(i) DB2,supk(i) DBk,sup(i) DB,sup(i) ：支持度计数 ：相对支持度,25,6.2.3提高Apriori算法的效率,抽样 选取给定数据库D中的随机样本S,在S中搜索频繁项集 牺牲了精度换取了性能 样本大小最好一次能装载到内存，保障数据扫描性能 对精度要求高的，可再次扫描D寻找缺失的频繁项集 动态项集计数 将数据库划分为用开始标记标记的块，可以在任何开始点添加新的候选集 不像Apriori算法仅在每次完整的数据库扫描后确定新的的候选 使用迄今为止的计数作为实际计数的下界，如果迄今为止的计数满足最小支持度，则该项集添加到频繁项集的集合中，并且可以用来产生更长的候选,26,6.2.3提高Apriori算法的效率 DIC: Reduce Number of Scans,ABCD,ABC,ABD,ACD,BCD,AB,AC,BC,AD,BD,CD,A,B,C,D,Itemset lattice,Once both A and D are determined frequent, the counting of AD begins Once all length-2 subsets of BCD are determined frequent, the counting of BCD begins,Transactions,1-itemsets,2-itemsets,Apriori,1-itemsets,2-items,3-items,DIC,S. Brin R. Motwani, J. Ullman, and S. Tsur. Dynamic itemset counting and implication rules for market basket data. In SIGMOD97,27,6.2频繁项集挖掘方法,Apriori: 通过限制候选产生发现频繁项集* 由频繁项集产生关联规则* 产生Apriori算法的效率* 挖掘频繁项集的模式增长方法* 使用垂直数据格式挖掘频繁项集* 挖掘闭模式和极大模式,28,6.2.4挖掘频繁项集的模式增长算法,频繁模式增长算法（ Frequent Pattern Growth, FPGrowth 算法） 深度优先（Depth-first ）搜索 发现频繁模式但不用产生候选集 将发现频繁模式的问题转换成在较小的条件数据库中递归地搜索一些较短模式，然后连接后缀形成最终频繁项集 主要思想： 首先将频繁项集数据库压缩到一棵频繁模式树（构造FP树） 然后将压缩后的数据库,为每个频繁项，划分构建条件模式库与条件 FP-tree 对每个新产生的条件 FP-tree，重复这个过程 直到FP-tree 为空,或者单一路径， 可以产生出所有频繁模式组合 性能研究表明，对于挖掘长/短频繁模式都是有效的 还有很多进一步优化的算法,29,构建FP-tree示例,min_support = 3,TID Items bought (ordered) frequent items 100 f, a, c, d, g, i, m, p f, c, a, m, p 200 a, b, c, f, l, m, o f, c, a, b, m 300 b, f, h, j, o, w f, b 400 b, c, k, s, p c, b, p 500 a, f, c, e, l, p, m, n f, c, a, m, p,Scan DB once, find frequent 1-itemset (single item pattern) Sort frequent items in frequency descending order, f-list Scan DB again, construct FP-tree,F-list = f-c-a-b-m-p,30,频繁模式挖掘分区,Frequent patterns can be partitioned into subsets according to f-list F-list = f-c-a-b-m-p Patterns containing p Patterns having m but no p Patterns having c but no a nor b, m, p Pattern f Completeness and non-redundency,31,条件模式库构建,Starting at the frequent item header table in the FP-tree Traverse the FP-tree by following the link of each frequent item p Accumulate all of transformed prefix paths of item p to form ps conditional pattern base,Conditional pattern bases item cond. pattern base c f:3 a fc:3 b fca:1, f:1, c:1 m fca:2, fcab:1 p fcam:2, cb:1,32,条件FP树,For each pattern-base Accumulate the count for each item in the base Construct the FP-tree for the frequent items of the pattern base,m-conditional pattern base: fca:2, fcab:1,All frequent patterns relate to m m, fm, cm, am, fcm, fam, cam, fcam,f:4,c:1,b:1,p:1,b:1,c:3,a:3,b:1,m:2,p:2,m:1,Header Table Item frequency head f 4 c 4 a 3 b 3 m 3 p 3,33,递归: 挖掘每个条件FP树,Cond. pattern base of “am”: (fc:3),Cond. pattern base of “cm”: (f:3),f:3,cm-conditional FP-tree,Cond. pattern base of “cam”: (f:3),f:3,cam-conditional FP-tree,34,特例: 单一前缀路径 FP-tree,Suppose a (conditional) FP-tree T has a shared single prefix-path P Mining can be decomposed into two parts Reduction of the single prefix path into one node Concatenation of the mining results of the two parts,+,FPGrowth 算法综合示例,i2:7,i1:2,i4:1,i4:1,i3:2,i1:4,i5:1,i5:1,i3:2,Header Table Item frequency head i2 7 i1 6 i3 6 i4 2 i5 2,i3:2,36,6.2频繁项集挖掘方法,Apriori: 通过限制候选产生发现频繁项集* 由频繁项集产生关联规则* 产生Apriori算法的效率* 挖掘频繁项集的模式增长方法* 使用垂直数据格式挖掘频繁项集* 挖掘闭模式和极大模式,37,6.2.5使用垂直数据格式挖掘频繁项集,Apriori算法、FP-growth算法都从TID项集格式（即TID：itemset）水平数据格式挖掘 垂直数据格式：项-TID集格式itemID:TID_set,item是项的名称，TID-set是包含item的事务标识符集合,水平数据,垂直数据,38,6.2.5使用垂直数据格式挖掘频繁项集,频繁2项集,频繁3项集,基于求事务集的交集，来挖掘频繁模式，假设最小支持度计数为2 可通过存储差集来进一步优化算法,39,6.2频繁项集挖掘方法,Apriori: 通过限制候选产生发现频繁项集* 由频繁项集产生关联规则* 产生Apriori算法的效率* 挖掘频繁项集的模式增长方法* 使用垂直数据格式挖掘频繁项集* 挖掘闭模式和极大模式,6.2.6挖掘闭模式和极大模式,闭频繁项集可以推出频繁项集的集合及其支持度 如何挖掘闭频繁项集？推荐方法是直接搜索闭频繁项集，挖掘过程中，一旦识别闭项集就尽快对搜索空间进行剪枝 剪枝策略 项合并：如果频繁项集X的每个事务都包含项集Y,但不包含Y的任何真超集，则XY形成一个闭频繁项集，并且不必再搜索包含X但不包含Y的任何项集 子项集剪枝：如果频繁项集X是一个已经发现的闭频繁项集Y的真子集，并且support(X)=support(Y),则X和Y在集合枚举树中的所有后代都不可能是闭频繁项集,6.2.6挖掘闭模式和极大模式,剪枝策略 项跳过：在深度优先挖掘闭项集时，每一层都有一个与头表和投影数据相关的前缀项集X,如果一个局部频繁项p在不同层的多个头表中都具有相同的支持度，则可以将p从高层头表中剪裁掉。 频繁项集导出后，进行闭包检查：超集、子集检查 可构造压缩的类似FP树的模式树，用于子集检查 闭模式挖掘方法可扩展应用到极大模式挖掘中,42,Visualization of Association Rules: Plane Graph,43,Visualization of Association Rules: Rule Graph,目录,44,6.3.1强规则不一定是有趣的,一个误导的“强”关联规则 例：设game表示包含计算机游戏的事务，而video表示包含录像的事务，在所分析的10000个事务中，数据显示6000个顾客事务包含计算机游戏，7500个事务包含录像，而4000个事务两者都包含。如果设置最小支持度30%，最小置信度60%，则发现关联规则： buys(X,“computer games”=buys(X,”videos”) support=4000/10000=40%, confidence=4000/6000=66% 误导，数据中购买录像的比例是75%，比66%还高 为什么？因为两者存在负相关性 支持度-置信度度量不足以过