购买

¥ 30.0

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 数据挖掘の基本关联分析

数据挖掘の基本关联分析.ppt

数据挖掘の基本关联分析

烟雨梦兮
2018-10-14 0人阅读 举报 0 0 暂无简介

简介:本文档为《数据挖掘の基本关联分析ppt》,可适用于IT/计算机领域

第章:关联分析基本概念和算法关联分析的预备知识频繁项集产生规则产生关联模式的评估目的:介绍关联分析的基本概念、关联规则挖掘的基本方法以及关联模式评估的度量要求:掌握关联规则挖掘的Apriori算法了解关联规则挖掘的其他方法熟悉关联模式评估的典型度量重点:用于频繁项集产生和规则产生的Apriori算法难点:使用散列树(HashTree)的支持度计算方法(C)VipinKumar,ParallelIssuesinDataMining,VECPAR第章:关联分析基本概念和算法关联分析的预备知识频繁项集的产生频繁项集产生的优化策略计算复杂度的影响因素频繁项集的紧凑表示产生频繁项集的其他方法规则产生关联模式的评估(C)VipinKumar,ParallelIssuesinDataMining,VECPAR关联分析给定一组事务寻找预测“某些项将会随其他项的出现而出现”的规则挖掘关联规则购物篮事务数据库关联规则的例子{Diaper}{Beer},{Milk,Bread}{Eggs,Coke},{Beer,Bread}{Milk},蕴含符号“”表示共现关系而不是因果关系(C)VipinKumar,ParallelIssuesinDataMining,VECPARTIDItemsBread,MilkBread,Diaper,Beer,EggsMilk,Diaper,Beer,CokeBread,Milk,Diaper,BeerBread,Milk,Diaper,Coke定义:频繁项集项集一个或多个项的集合例子:{Milk,Bread,Diaper}k项集包含k个项的项集支持度计数(supportcount)给定项集的出现次数比如({Milk,Bread,Diaper})=支持度(support)覆盖给定项集的事务数占所有事务数的比例比如s({Milk,Bread,Diaper})==频繁项集支持度大于等于给定阈值minsup的项集(C)VipinKumar,ParallelIssuesinDataMining,VECPARTIDItemsBread,MilkBread,Diaper,Beer,EggsMilk,Diaper,Beer,CokeBread,Milk,Diaper,BeerBread,Milk,Diaper,Coke定义:关联规则例子:关联规则形式为XY的蕴含表达式其中X和Y是项集例子:{Milk,Diaper}{Beer}规则评估度量支持度(s)s(XY)=(X∪Y)|T|包含X和Y的事务个数占所有事务个数的比例置信度(c)c(XY)=(X∪Y)(X)在包含X的事务集合中包含Y的事务个数占事务总数的比例(C)VipinKumar,ParallelIssuesinDataMining,VECPARTIDItemsBread,MilkBread,Diaper,Beer,EggsMilk,Diaper,Beer,CokeBread,Milk,Diaper,BeerBread,Milk,Diaper,Coke关联规则挖掘任务给定一个事务集合T关联规则挖掘的目标是寻找所有满足下面条件的规则支持度≥minsup置信度≥minconfBruteforce(蛮力)方法:列出所有可能的关联规则计算每条规则的支持度和置信度删除支持度不足minsup或置信度不足minconf的规则代价极高!因为从包含d个项的数据集提取的可能规则的总数是R=dd比如d=则R=(C)VipinKumar,ParallelIssuesinDataMining,VECPAR挖掘关联规则规则的例子:{Milk,Diaper}{Beer}(s=,c=){Milk,Beer}{Diaper}(s=,c=){Diaper,Beer}{Milk}(s=,c=){Beer}{Milk,Diaper}(s=,c=){Diaper}{Milk,Beer}(s=,c=){Milk}{Diaper,Beer}(s=,c=)观察结果:上面所有的规则都是同一个项集的二分:{Milk,Diaper,Beer}由同一个项集得到的规则具有相同的支持度和不同的置信度因此我们可以将支持度和置信度分开处理(C)VipinKumar,ParallelIssuesinDataMining,VECPARTIDItemsBread,MilkBread,Diaper,Beer,EggsMilk,Diaper,Beer,CokeBread,Milk,Diaper,BeerBread,Milk,Diaper,Coke挖掘关联规则两步方法:频繁项集的产生产生支持度minsup的所有项集规则的产生由每个频繁项集产生置信度minconf的规则其中每个规则都是该频繁项集的二分(C)VipinKumar,ParallelIssuesinDataMining,VECPAR第章:关联分析基本概念和算法关联分析的预备知识频繁项集的产生频繁项集产生的优化策略计算复杂度的影响因素频繁项集的紧凑表示产生频繁项集的其他方法规则产生关联模式的评估(C)VipinKumar,ParallelIssuesinDataMining,VECPAR频繁项集的产生给定d个项一共有d个项集(C)VipinKumar,ParallelIssuesinDataMining,VECPAR频繁项集的产生Bruteforce(蛮力)方法:在项集格中的每个项集都是一个候选频繁项集扫描事务数据库计算每个候选频繁项集的支持度将每个事务与每个候选频繁项集匹配比较次数~O(NMw)=>代价极高因为M=d!!!(C)VipinKumar,ParallelIssuesinDataMining,VECPARN�w�M�ListofCandidates�第章:关联分析基本概念和算法关联分析的预备知识频繁项集的产生频繁项集产生的优化策略计算复杂度的影响因素频繁项集的紧凑表示产生频繁项集的其他方法规则产生关联模式的评估(C)VipinKumar,ParallelIssuesinDataMining,VECPAR频繁项集产生的优化策略减少候选频繁项集的个数(M)完全搜索:M=d使用剪枝计数减少M减少事务的个数(N)当项集的大小增加时减少N在基于垂直数据分布的挖掘算法中使用减少比较的次数(NM)使用高效的数据结构保存候选频繁项集或事务不需要匹配每个候选和每个事务垂直数据分布(C)VipinKumar,ParallelIssuesinDataMining,VECPAR优化策略:减少候选频繁项集的个数先验原理(Aprioriprinciple):如果一个项集是频繁的那么它的所有子集都是频繁的先验原理成立的原因:一个项集的支持度不会超过其任何子集的支持度该性质称作支持度的反单调性质(C)VipinKumar,ParallelIssuesinDataMining,VECPAR先验原理的图示(C)VipinKumar,ParallelIssuesinDataMining,VECPAR先验原理的图示项集项集(不需要生成涉及Coke或Eggs的候选频繁项集)项集最小支持度计数=如果考虑所有项集CCC=使用基于支持度的剪枝=(C)VipinKumar,ParallelIssuesinDataMining,VECPARItemCountBreadCokeMilkBeerDiaperEggsItemsetCount{Bread,Milk}{Bread,Beer}{Bread,Diaper}{Milk,Beer}{Milk,Diaper}{Beer,Diaper}ItemsetCount{Bread,Milk,Diaper}Apriori算法算法流程:设定k=扫描事务数据库一次生成频繁的项集如果存在两个或以上频繁k项集重复下面过程:候选产生由长度为k的频繁项集生成长度为k的候选项集候选前剪枝对每个候选项集若其具有非频繁的长度为k的子集则删除该候选项集支持度计算扫描事务数据库一次统计每个余下的候选项集的支持度候选后剪枝删除非频繁的候选项集仅保留频繁的(k)项集设定k=k(C)VipinKumar,ParallelIssuesinDataMining,VECPARApriori算法的核心步骤候选产生设A={a,a,…,ak}和B={b,b,…,bk}是一对频繁k项集当且仅当ai=bi(i=,,k)并且ak≠bk时合并A和B得到{a,a,…,ak,bk}比如合并{Bread,Milk}和{Bread,Diaper}得到{Bread,Milk,Diaper}但{Milk,Bread}和{Bread,Diaper}不能合并候选前剪枝设A={a,a,…,ak,ak}是一个候选(k)项集检查每个A’是否在第k层频繁项集中出现其中A’由A去掉ai(i=,…,k)得到若某个A’没有出现则A是非频繁的(C)VipinKumar,ParallelIssuesinDataMining,VECPARApriori算法的例子考虑下面的事务数据库最小支持度计数阈值=(C)VipinKumar,ParallelIssuesinDataMining,VECPARApriori算法的例子…(生成频繁项集)(候选产生)(候选后剪枝)(支持度计算)(候选产生和候选前剪枝)(支持度计算)(候选后剪枝)(C)VipinKumar,ParallelIssuesinDataMining,VECPAR优化策略:减少比较次数候选项集的支持度计算:扫描事务数据库决定每个候选项集的支持度为了减少比较次数将候选项集保存在散列(hash)结构中将每个事务与保存在散列结构的候选项集作匹配(C)VipinKumar,ParallelIssuesinDataMining,VECPARN�k�Buckets�HashStructure�生成候选的散列树,,,,,,散列函数假设有个长度为的候选项集:{},{},{},{},{},{},{},{},{},{},{},{},{},{},{}散列树(hashtree)参数:散列函数(hashfunction)叶子大小限制:保存在一个叶子结点的项集个数的上限(如果候选项集的个数超过该限制则分裂叶子结点)叶子大小限制:(C)VipinKumar,ParallelIssuesinDataMining,VECPAR生成候选的散列树,,,,,,散列函数散列树(C)VipinKumar,ParallelIssuesinDataMining,VECPAR生成候选的散列树,,,,,,散列函数散列树(C)VipinKumar,ParallelIssuesinDataMining,VECPAR生成候选的散列树,,,,,,散列函数散列树(C)VipinKumar,ParallelIssuesinDataMining,VECPAR子集操作给定一个事务tt包含哪些长度为的可能子集(C)VipinKumar,ParallelIssuesinDataMining,VECPAR�Transaction,t���������������������������Subsetsofitems�Level�Level�Level���使用散列树的子集操作事务给定一个事务tt包含散列树中哪些子集(C)VipinKumar,ParallelIssuesinDataMining,VECPAR使用散列树的子集操作事务给定一个事务tt包含散列树中哪些子集(C)VipinKumar,ParallelIssuesinDataMining,VECPAR使用散列树的子集操作事务给定一个事务tt包含散列树中哪些子集个候选项集与事务的当前子集比较(C)VipinKumar,ParallelIssuesinDataMining,VECPAR第章:关联分析基本概念和算法关联分析的预备知识频繁项集的产生频繁项集产生的优化策略计算复杂度的影响因素频繁项集的紧凑表示产生频繁项集的其他方法规则产生关联模式的评估(C)VipinKumar,ParallelIssuesinDataMining,VECPAR计算复杂度的影响因素最小支持度阈值的选择低支持度阈值导致更多频繁项集将会增加候选项集的个数和频繁项集的最大长度数据库的维度即项的个数需要更多空间保存每个项的支持度计数如果频繁项集的个数增加则计算量和IO开销也增加数据库的大小由于Apriori多次访问数据库算法的运行时间将随事务个数的增加而增加平均事务长度事务长度随数据库密度的增加而增加可能会增加频繁项集的最大长度和散列树的遍历时间(因为事务的子集个数随着其长度的增加而增加)(C)VipinKumar,ParallelIssuesinDataMining,VECPAR作业将Apriori算法应用于下面的事务数据库最小支持度为画出Apriori算法的运行过程。P:(C)VipinKumar,ParallelIssuesinDataMining,VECPAR第章:关联分析基本概念和算法关联分析的预备知识频繁项集的产生频繁项集产生的优化策略计算复杂度的影响因素频繁项集的紧凑表示产生频繁项集的其他方法规则产生关联模式的评估(C)VipinKumar,ParallelIssuesinDataMining,VECPAR频繁项集的紧凑表示某些项集是冗余的因为它们具有与它们超集相同的支持度频繁项集的个数需要紧凑的表示(C)VipinKumar,ParallelIssuesinDataMining,VECPAR最大频繁项集边界非频繁项集最大频繁项集如果一个频繁项集没有任何频繁的直接超集则该项集称作最大频繁项集(C)VipinKumar,ParallelIssuesinDataMining,VECPAR�AB�AC�AD�AE�BC�BD�BE�CD�CE�DE�ABC�ABD�ABE�ACD�ACE�ADE�BCD�BCE�BDE�CDE�A�B�C�D�E�ABCD�ABCE�ABDE�ACDE�BCDE�ABCDE�频繁闭项集如果一个项集的任何直接超集都不具有和它相同的支持度计数则该项集称为闭项集如果一个闭项集是频繁的则它称为频繁闭项集(C)VipinKumar,ParallelIssuesinDataMining,VECPARSheetTIDItems{A,B}{B,C,D}{A,B,C,D}{A,B,D}{A,B,C,D}SheetSheetSheetItemsetSupport{A}{B}{C}{D}{A,B}{A,C}{A,D}{B,C}{B,D}{C,D}SheetSheetSheetItemsetSupport{A,B,C}{A,B,D}{A,C,D}{B,C,D}{A,B,C,D}SheetSheet最大频繁项集vs频繁闭项集事务ID不被任何事务支持(C)VipinKumar,ParallelIssuesinDataMining,VECPARSheetTIDItemsABCABCDBCEACDEDE最大频繁项集vs频繁闭项集最小支持度计数=#频繁闭项集=#最大频繁项集=频繁闭项集而且是最大的频繁闭项集但不是最大的(C)VipinKumar,ParallelIssuesinDataMining,VECPAR最大频繁项集、频繁闭项集和频繁项集(C)VipinKumar,ParallelIssuesinDataMining,VECPARFrequentItemsets�ClosedFrequentItemsets�MaximalFrequentItemsets�第章:关联分析基本概念和算法关联分析的预备知识频繁项集的产生频繁项集产生的优化策略计算复杂度的影响因素频繁项集的紧凑表示产生频繁项集的其他方法规则产生关联模式的评估(C)VipinKumar,ParallelIssuesinDataMining,VECPAR产生频繁项集的其他方法项集格的遍历一般到特殊vs特殊到一般(C)VipinKumar,ParallelIssuesinDataMining,VECPAR�Frequentitemsetborder��{a,a,,an}�(a)Generaltospecific���{a,a,,an}�Frequentitemsetborder�(b)Specifictogeneral��Frequentitemsetborder��{a,a,,an}�(c)Bidirectional�产生频繁项集的其他方法项集格的遍历等价类(C)VipinKumar,ParallelIssuesinDataMining,VECPAR�AB�AC�AD��BC�BD�AB�CD�AC�AD�ABC�ABD�BC�ACD�BD�CD�BCD�A�B�C�A�B�C�D�D�ABC�ABD�ACD�BCD�ABCD�(a)Prefixtree�(b)Suffixtree�ABCD�产生频繁项集的其他方法项集格的遍历宽度优先vs深度优先(C)VipinKumar,ParallelIssuesinDataMining,VECPAR(a)Breadthfirst�(b)Depthfirst�产生频繁项集的其他方法事务数据库的表示水平数据布局vs垂直数据布局(C)VipinKumar,ParallelIssuesinDataMining,VECPARHorizontalDataLayout�VerticalDataLayout�FP增长算法使用事务数据库的紧凑数据结构-FP树一旦FP树构建完成该算法使用一个递归的分而治之的方法挖掘频繁项集(C)VipinKumar,ParallelIssuesinDataMining,VECPARFP树的构建A:B:A:B:B:C:D:读入TID=后:读入TID=后:事务数据库中已经去掉非频繁的项并且事务中余下的项已按照支持度递减排序(C)VipinKumar,ParallelIssuesinDataMining,VECPARSheetTIDItems{A,B}{B,C,D}{A,C,D,E}{A,D,E}{A,B,C}{A,B,C,D}{B,C}{A,B,C}{A,B,D}{B,C,E}SheetSheetFP树的构建A:B:B:C:D:C:D:C:D:D:E:E:指针用于辅助频繁项集生成D:E:事务数据库头指针表(C)VipinKumar,ParallelIssuesinDataMining,VECPARSheetTIDItems{A,B}{B,C,D}{A,C,D,E}{A,D,E}{A,B,C}{A,B,C,D}{B,C}{A,B,C}{A,B,D}{B,C,E}SheetSheetSheetItemPointerABCDESheetSheetFP增长过程A:B:B:C:D:C:D:C:D:D:从D开始开始直到A逐个处理条件模式库关于D的条件模式库是D的所有前缀路径的集合:P={(A:,B:,C:),(A:,B:),(A:,C:),(A:),(B:,C:)}对P递归应用FP增长过程发现频繁项集(sup>):AD,BD,CD,ACD,BCDD:(C)VipinKumar,ParallelIssuesinDataMining,VECPARECLAT算法使用垂直数据布局:对于每个项保存事务ID列表(TID列表)TID列表(C)VipinKumar,ParallelIssuesinDataMining,VECPARECLAT算法通过计算两个k子集的TID列表的交集决定k项集的TID列表三种遍历方法:自顶向下、自底向上和混合方法优点:计算支持度很快缺点:计算过程产生的TID列表可能占用很大内存(C)VipinKumar,ParallelIssuesinDataMining,VECPARSheetTIDItemsABCDEA,B,EB,C,DC,EA,C,DA,B,C,DA,EA,BA,B,CA,C,DBABSheetSheetSheetTIDItemsABCDEA,B,EB,C,DC,EA,C,DA,B,C,DA,EA,BA,B,CA,C,DBABSheetSheetSheetTIDItemsABCDEA,B,EB,C,DC,EA,C,DA,B,C,DA,EA,BA,B,CA,C,DBABABSheetSheet第章:关联分析基本概念和算法关联分析的预备知识频繁项集的产生频繁项集产生的优化策略计算复杂度的影响因素频繁项集的紧凑表示产生频繁项集的其他方法规则产生关联模式的评估(C)VipinKumar,ParallelIssuesinDataMining,VECPAR规则产生给定一个频繁项集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ABCABCD,ACBD,ADBC,BCAD,BDAC,CDAB,如果|L|=k则有k–个候选的关联规则(忽略L和L)(C)VipinKumar,ParallelIssuesinDataMining,VECPAR规则产生如何从频繁项集高效生成规则一般地说置信度没有反单调性质比如c(ABCD)可以大于或小于c(ABD)但从同一个项集生成的规则的置信度具有反单调性质比如L={A,B,C,D}:c(ABCD)c(ABCD)c(ABCD)针对规则后件的项集置信度是反单调的:如果规则XY-X不满足置信度阈值则形如X’Y-X’的规则也不满足置信度阈值其中X’是X的子集(C)VipinKumar,ParallelIssuesinDataMining,VECPAR规则产生的Apriori算法规则格低置信度规则(C)VipinKumar,ParallelIssuesinDataMining,VECPARABCD=>{}�BC=>AD�BD=>AC�CD=>AB�AD=>BC�AC=>BD�AB=>CD�D=>ABC�C=>ABD�B=>ACD�A=>BCD�ACD=>B�ABD=>C�ABC=>D�BCD=>A�规则产生的Apriori算法候选产生候选规则通过合并两个具有相同规则后件前缀的规则产生比如合并(CD=>AB,BD=>AC)得到候选规则D=>ABC候选前剪枝如果规则D=>ABC的子集AD=>BC不满足置信度阈值则删除该规则置信度计算候选后剪枝(C)VipinKumar,ParallelIssuesinDataMining,VECPAR第章:关联分析基本概念和算法关联分析的预备知识频繁项集的产生频繁项集产生的优化策略计算复杂度的影响因素频繁项集的紧凑表示产生频繁项集的其他方法规则产生关联模式的评估(C)VipinKumar,ParallelIssuesinDataMining,VECPAR关联模式评估关联规则算法倾向于产生大量的规则很多产生的规则是不感兴趣的或冗余的如果{A,B,C}{D}和{A,B}{D}具有相同的支持度和置信度则{A,B,C}{D}是冗余的兴趣度可以用于对产生的规则进行过滤或排序在原来的关联规则定义中支持度和置信度是唯一使用的度量(C)VipinKumar,ParallelIssuesinDataMining,VECPAR兴趣度度量客观度量:基于从数据推导出的统计量来确定模式是否有趣比如个关联度量(支持度、置信度、拉普拉斯、Gini指标、互信息、Jaccard等等)主观度量:根据用户的解释来确定模式是否有趣如果一个模式揭示料想不到的信息那么它是主观有趣的(SilberschatzTuzhilin)如果一个模式是可操作的(actionable)即提供导致有益行动的有用信息那么它是主观有趣的(SilberschatzTuzhilin)(C)VipinKumar,ParallelIssuesinDataMining,VECPAR兴趣度的应用(C)VipinKumar,ParallelIssuesinDataMining,VECPAR计算客观兴趣度给定规则XY计算规则兴趣度的信息可以从以下相依表(contingencetable)中获取规则XY的相依表用于定义不同的度量支持度、置信度、提升度、Gini、J度量等等f:X和Y共现的支持度计数f:X和Y共现的支持度计数f:X和Y共现的支持度计数f:X和Y共现的支持度计数YYXfffXfffoff|T|(C)VipinKumar,ParallelIssuesinDataMining,VECPAR支持度-置信度的局限性支持度的缺点若支持度阈值过高则许多潜在的有意义的模式被删调若支持度阈值过低则计算代价很高而且产生大量的关联模式置信度的缺点关联规则:TeaCoffee置信度=P(Coffee|Tea)=但P(Coffee)=虽然置信度很高但规则是误导的置信度忽略了规则前件和后件的统计独立性CoffeeCoffeeTeaTea(C)VipinKumar,ParallelIssuesinDataMining,VECPAR统计独立性个学生的群体个学生知道如何去游泳(S)个学生知道如何去骑单车(B)个学生知道如何去游泳和骑单车(S,B)P(SB)==P(S)P(B)==P(SB)=P(S)P(B)=>统计独立P(SB)>P(S)P(B)=>正相关P(SB)<P(S)P(B)=>负相关(C)VipinKumar,ParallelIssuesinDataMining,VECPAR基于统计的度量部分考虑统计独立性的度量提升度兴趣因子相关系数余弦(C)VipinKumar,ParallelIssuesinDataMining,VECPAR例子:提升度兴趣因子关联规则:TeaCoffeeConfidence=P(Coffee|Tea)=但P(Coffee)=Lift==(<,说明Coffee和Tea是负相关的)CoffeeCoffeeTeaTea(C)VipinKumar,ParallelIssuesinDataMining,VECPAR上述兴趣度的局限性YYXXYYXXYYXX(C)VipinKumar,ParallelIssuesinDataMining,VECPAR现有文献提供了大量的兴趣度度量当这些度量应用到一组关联模式时是否会产生类似的有序结果?如何通过考察度量的性质了解度量之间的差异?(C)VipinKumar,ParallelIssuesinDataMining,VECPAR客观度量的一致性相依表显示的个关联模式:使用不同的度量对相依表排序的结果:(C)VipinKumar,ParallelIssuesinDataMining,VECPARSheetExampleEEEEEEEEEESheetSheet对称性是否M(A,B)=M(B,A)对称度量:支持度、提升度、集体强度、余弦、Jaccard等等非对称度量:置信度、可信度因子、拉普拉斯、J度量等等(C)VipinKumar,ParallelIssuesinDataMining,VECPAR缩放不变性成绩-性别例子(Mosteller,):关联应该独立于例子中男生和女生的相对人数xxMaleFemaleHighLowMaleFemaleHighLowBBAkkpkkqAkkrkks(C)VipinKumar,ParallelIssuesinDataMining,VECPAR反演性BBApqArsBBAprAqsBBApqArsBBAsqArpBBApqArsBBAsrAqp(C)VipinKumar,ParallelIssuesinDataMining,VECPAR零加性不变度量:支持度、余弦、Jaccard等等变化度量:相关系数、Gini指标、互信息等等(C)VipinKumar,ParallelIssuesinDataMining,VECPAR不同的度量具有不同的性质O:对称性O:缩放不变性O:反演性O:零加性(C)VipinKumar,ParallelIssuesinDataMining,VECPAR(C)VipinKumar,ParallelIssuesinDataMining,VECPAR

VIP尊享8折文档

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/72

数据挖掘の基本关联分析

¥30.0

会员价¥24.0

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利