数据仓库与数据挖掘教程(第2版)第八章集合论方法37536.pptx

《数据仓库与数据挖掘教程(第2版)第八章集合论方法37536.pptx》由会员分享，可在线阅读，更多相关《数据仓库与数据挖掘教程(第2版)第八章集合论方法37536.pptx（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章 集合论方法12粗糙集概念粗糙集概念3粗糙集含义粗糙集含义知识的分类观点知识的分类观点4粗糙集含义粗糙集含义粗糙集是处理不精确、不确定与不完全数据的理论粗糙集概述粗糙集概述1、粗糙集以等价关系（不可分辨关系）为基础，用于分类问题。2、它用上、下近似两个集合来逼近任意一个集合，该集合的边界线区域被定义为上近似集和下近似集之差集。3、上、下近似集可以通过等价关系给出确定的描述，边界域的含糊元素数目可以被计算出来。而模糊集（Fuzzy）是用隶属度来描述集合边界的不确定性，隶属度是认为给定的，不是计算得出了。粗糙集理论用在数据库中的知识发现主要体现在：1、利用等价关系对数据库进行属性约简；2、利

2、用集合的上、下近似关系获取分类规则。基本定义信息表定义基本定义等价关系定义基本定义等价类定义基本定义划分的定义例：例：集合集合X的上、下近似关系的上、下近似关系下近似定义下近似定义集合集合X的上、下近似关系的上、下近似关系上近似定义上近似定义正域，负域和边界的定义正域，负域和边界的定义用图来说明正域、负域和边界，每一个小长方形表示一个等价类。用图来说明正域、负域和边界，每一个小长方形表示一个等价类。粗糙集定义粗糙集定义例例属性约简的粗糙集理论属性约简的粗糙集理论属性约简概念属性约简概念 在信息表中根据等价关系，我们可以用等价类中的一个对象（元组）来代表整个等价类，这实际上是按纵方向约简了信息表

3、中数据。对信息表中的数据按横方向进行约简就是看信息表中有无冗余的属性，即去除这些属性后能保持等价性，使对象分类能力不会下降。约简后的属性集称为属性约简集，约简集通常不唯一。约简定义约简定义核定义核定义正域定义正域定义上面的约简定义没有考虑决策属性，下面研究条件属性上面的约简定义没有考虑决策属性，下面研究条件属性C相对决策属性相对决策属性D的约简。的约简。属性约简实例属性约简实例属性约简实例属性约简实例属性约简实例属性约简实例属性约简实例属性约简实例属性约简的粗糙集方法属性约简的粗糙集方法属性依赖度属性依赖度属性约简的粗糙集方法属性约简的粗糙集方法属性重要度属性重要度属性约简的粗糙集方法属性约简

4、的粗糙集方法最小属性集概念最小属性集概念粗糙集方法的规则获取粗糙集方法的规则获取K-均值聚类均值聚类聚类的问题描述为：聚类的问题描述为：给定数据集合给定数据集合D D，把它划分为一组聚类：，把它划分为一组聚类：CC1 1，C C2 2，,C CK K,C,Ci i D D，使得不同类中的数据尽可能的不相似（或距离较，使得不同类中的数据尽可能的不相似（或距离较远），而同一类中的数据尽可能的相似（或距离较近）。远），而同一类中的数据尽可能的相似（或距离较近）。即聚类内紧凑，类间独立。即聚类内紧凑，类间独立。K-均值聚类均值聚类算法描述：算法描述：1 1、为中心向量、为中心向量 CC1 1，C C2

5、 2，,C,CK K 初始化初始化K K个种子；个种子；2 2、分组：、分组：1 1）将样本分配给距离其最近的中心向量；）将样本分配给距离其最近的中心向量；2 2）由这些样本构造不相交的聚类；）由这些样本构造不相交的聚类；3 3、确定中心：用各个聚类的中心向量作为新的中心；、确定中心：用各个聚类的中心向量作为新的中心；4 4、重复分组和确定中心的步骤，直至算法收敛。、重复分组和确定中心的步骤，直至算法收敛。关联规则挖掘关联规则挖掘基本原理设I=i1,i2,im是项（Item）的集合。记D为事务（Transaction）的集合（事务数据库），事务T是项的集合，并且TI。设A是I中一个项集，如果A

6、T，那么称事务T包含A。定义1：关联规则是形如AB的蕴涵式，这里AI，BI，并且AB=。定义2：规则的支持度。规则AB在数据库D中具有支持度S，表示S是D中事务同时包含AB的百分比，它是概率P(AB)，即：其中|D|表示事务数据库D的个数，表示A、B两个项集同时发生的事务个数。关联规则挖掘关联规则挖掘基本原理定义3：规则的可信度。规则AB具有可信度C，表示C是包含A项集的同时也包含B项集，相对于包含A项集的百分比，这是条件概率P(B|A)，即：其中 表示数据库中 包含项集A的事务个数。定义4：阈值在事务数据库中找出有用的关联规则，需要由用户确定两个阈值：最小支持度（min_sup）和最小可信度

7、（min_conf）。定义5：项的集合称为项集（Itemset），包含k个项的项集称之为k-项集。如果项集满足最小支持度，则它称之为频繁项集（Frequent Itemset）。定义6：关联规则同时满足最小支持度（min_sup）和最小可信度（min_conf）的规则称之为关联规则，即 成立时，规则称之为关联规则，也可以称为强关联规则。关联规则挖掘过程关联规则的挖掘一般分为两个过程：（1）找出所有的频繁项集：根据定义，这些项集的支持度大于最小支持度的项集，即频繁项集。（2）由频繁项集产生关联规则：根据定义，这些规则必须满足最小支持度和最小可信度。其中，（2）是在（1）的基础上进行的，工作量非常

8、小。挖掘关联规则的总体性能由（1）决定。关联规则的兴趣度例子：讨论不购买商品与购买商品的关系。设，交易集D，经过对D的分析，得到表格:37定义7：兴趣度 公式反映了项集A与项集B的相关程度。若 即表示项集A出现和项集B是相互独立的。若表示A出现和B出现是负相关的。若表示A出现和B出现是正相关的。意味着A的出现蕴含B的出现。兴趣度的含义兴趣度的含义1、一条规则的兴趣度越大于1说明我们对这条规则越感兴趣（即其实际利用价值越大）；2、一条规则的兴趣度越小于1说明我们对这条规则的反面规则越感兴趣（即其反面规则的实际利用价值越大）；3、兴趣度不小于0。所有可能的关联规则 40讨论：讨论：I1I2I3I6

9、共共4条规则：条规则：由于由于I1,I21,规则才有价值。规则才有价值。注：兴趣度也称为作用度（注：兴趣度也称为作用度（Lift）,表示关联规则表示关联规则AB的的“提升提升”。如果作用度（兴趣度）不大于。如果作用度（兴趣度）不大于1，则此关联规则就没有意义了。则此关联规则就没有意义了。概括概括分析分析可信度是对关联规则地准确度的衡量。支持度是对关联规则重要性的衡量。支持度说明了这条规则在所有事务中有多大的代表性。有些关联规则可信度虽然很高，但支持度却很低，说明该关联规则实用的机会很小，因此也不重要。兴趣度（作用度）描述了项集A对项集B的影响力的大小。兴趣度越大，说明项集B受项集A的影响越大。

10、Apriori算法基本思想算法基本思想Apriori是挖掘关挖掘关联规则联规则的一个重要方法。算法分为两个子问题：1、找到所有支持度大于最小支持度的项集（Itemset），这些项集称为频繁集（Frequent Itemset）。2、使用第1步找到的频繁集产生规则。Apriori算法基本方法算法基本方法Apriori 使用一种称作逐层搜索的迭代方法，“K-项集”用于探索“K+1-项集”。1、首先，找出频繁“1-项集”的集合。该集合记作L1。L1用于找频繁“2-项集”的集合L2，而L2用于找L3；2、如此下去，直到不能找到“K-项集”。找每个LK需要一次数据库扫描。Apriori 性质性质：频繁项

11、集的所有非空子集都必须也是频繁的。1、如果项集B不满足最小支持度阈值min-sup，则B不是频繁的，即 P（B）min-sup2、如果项A添加到B，则结果项集（即BA）不可能比B更频繁出现。因此，BA也不是频繁的，即 P（BA）min-sup。“K-项集”产生“K+1-项集”设K-项集LK，K+1项集LK+1，产生LK+1的候选集CK+1，有公式：CK+1=LKLK=XY，其中X，Y LK，|XY|=K+1 其中C1是1-项集的集合，取自所有事务中的单项元素。例：如 L1=A，B C2=AB=A，B，且|AB|=2 L2=A，B，A，C C3=A，BA，C=A，B，C，且|ABC|=3Apri

12、ori 算法中候选项集与频繁项集的产生实例算法中候选项集与频繁项集的产生实例事务ID事务的项目集T1A,B,ET2B,DT3B,CT4A,B,DT5A,CT6B,CT7A,CT8A,B,C,ET9A,B,C46过程举例过程举例1)在算法的第一次迭代，每个项都是候选1-项集的集合C1的成员。算法扫描所有事务，对每个项的出现次数计数；2)假定最小事务支持计数为2。（即min-sup=2/9=22%），可以确定频繁1-项集的集合L1。它由具有最小支持度的候选1-项集组成。3)为发现频繁2-项集的集合L2，算法使用L1*L1来产生候选集C2；4)扫描D中事务，计算C2中每个候选项集的支持度计数；5)确

13、定频繁2-项集的集合L2，它由具有最小支持度的C2中的候选2-项集组成；6)候选3-项集的集合C3的产生，得到候选集：C3=A，B，C，A，B，E，A，C，E，B，C，D，B，C，E，B，D，E，按Apriori 性质，频繁项集的所有子集必须是频繁的。由于A，D，C，D，C，E，D，E不是频繁项集，故C3中后4个候选不可能是频繁的，在C3中删除它们。扫描D中事务，对C3中的候选项集计算支持度计数，7)确定L3，它由具有最小支持度的C3中候选3项集组成；8）按公式产生候选4项集的集合C4，产生结果A,B,C,E,这个项集被剪去，因为它的子集B,C,E不是频繁的。这样L4=。此算法终止。L3是最大

14、的频繁项集，即：A,B,C和A,B,E。具体产生过程用图表示 候选集与频繁项集的产生候选集与频繁项集的产生 项集支持度计数A,B4A,C4A,E2B,C4B,D2B,E2项集A,B，CA,B，EC3候选集L2频繁2-项集计算支持度项集 支持度计数A,B,C2A,B,E2项集 支持度计数A,B,C2A,B,E2C3候选集L3频繁3-项集产生关联规则根据前面提到的可信度的定义，关联规则的产生如下：（1）对于每个频繁项集L，产生L的所有非空子集；（2）对于L的每个非空子集S，如果则输出规则“S LS”。注：LS表示在项集L中除去S子集的项集。过程举例在事务数据库中，频繁项集在事务数据库中，频繁项集L

15、=A，B，E，可以由，可以由L产生哪些关联规则？产生哪些关联规则？L的非空子集的非空子集S有：有：A,B,A,E,B,E,A,B,E。可得到关联规则如下：。可得到关联规则如下：A B E conf=2/4=50%A E B conf=2/2=100%B E A conf=2/2=100%A B E conf=2/6=33%B A E conf=2/7=29%E A B conf=2/2=100%假设最小可信度为假设最小可信度为60，则最终输出的关联规则为：，则最终输出的关联规则为：A E B 100%B E A 100%E A B 100%对于频繁项集对于频繁项集A，B，C，同样可得其它关联规

16、则。，同样可得其它关联规则。Apriori算法程序算法程序1、首先产生频繁1-项集L1，然后是频繁2-项集L2，直到有某个r值使得Lr为空，算法停止。2、在第k次循环中，过程先产生候选k-项集的集合Ck，Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频繁集做一个连接来产生的。Ck中的项集是用来产生频繁集的候选集，最后的频繁集Lk必须是Ck的一个子集。Agrawal等引入了修剪技术来减小候选集Ck的大小。一个项集是频繁集当且仅当它的所有子集都是频繁集。如果Ck中某个候选项集有一个（k-1）-子集不属于Lk-1，则这个项集可以被修剪掉不再被考虑。Apriori 够快了吗够快了吗?性能瓶颈

17、性能瓶颈Apriori算法的核心:用频繁的(k 1)-项集生成候选的频繁 k-项集；用数据库扫描和模式匹配计算候选集的支持度；Apriori 的瓶颈:候选集生成巨大的候选集:104 个频繁1-项集要生成 107 个候选 2-项集；要找尺寸为100的频繁模式，如 a1,a2,a100,你必须先产生2100 1030 个候选集；多次扫描数据库：如果最长的模式是n的话，则需要(n+1)次数据库扫描挖掘频繁集挖掘频繁集 不用生成候选集不用生成候选集1、用Frequent-Pattern tree(FP-tree)结构压缩数据库高度浓缩，同时对频繁集的挖掘又完备的；避免代价较高的数据库扫描；2、开发一种

18、高效的基于FP-tree的频繁集挖掘算法采用分而治之的方法学：分解数据挖掘任务为小任务；避免生成关联规则:只使用部分数据库；理论和实验表明该算法优于Apriori算法。FP-tree 结构的好处结构的好处1、完备:（1）不会打破交易中的任何模式；（2）包含了序列模式挖掘所需的全部信息；2、紧密（1）去除不相关信息不包含非频繁项；（2）支持度降序排列:支持度高的项在FP-tree中共享的机会也高；（3）决不会比原数据库大（如果不计算树节点的额外开销)用用 FP-tree挖掘频繁集挖掘频繁集1、基本思想(分而治之)用FP-tree递归增长频繁集2、方法 对每个项，生成它的条件模式库,然后是它的条件

19、 FP-tree；对每个新生成的条件FP-tree，重复这个步骤；直到结果FP-tree为空,或只含维一的一个路径(此路径的每个子路径对应的相集都是频繁集)。挖掘挖掘 FP-tree的主要步骤的主要步骤1、为FP-tree中的每个节点生成条件模式库2、用条件模式库构造对应的条件FP-tree3、递归构造条件 FP-trees 同时增长其包含的频繁集如果条件FP-tree直包含一个路径，则直接生成所包含的频繁集。步骤步骤1:从从 FP-tree 到条件模式库到条件模式库（1）从FP-tree的头表开始；（2）按照每个频繁项的连接遍历 FP-tree；（3）列出能够到达此项的所有前缀路径，得到条件

20、模式库；条件模式库条件模式库itemcond.pattern basecf:3afc:3bfca:1,f:1,c:1mfca:2,fcab:1pfcam:2,cb:1f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表头表Item frequency head f4c4a3b3m3p3FP-tree支持条件模式库构造的属性支持条件模式库构造的属性1、节点裢接任何包含ai,的可能频繁集，都可以从FP-tree头表中的ai沿着ai 的节点链接得到2、前缀路径要计算路径P 中包含节点ai 的频繁集，只要考察到达ai 的路径前缀即可，且其支持度等于节点ai 的支持度步骤步骤2:建立条

21、件建立条件 FP-tree 对每个模式库计算库中每个项的支持度用模式库中的频繁项建立FP-treem-条件模式库条件模式库:fca:2,fcab:1f:3c:3a:3m-conditional FP-treef:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表头表Item frequency head f4c4a3b3m3p3第第3步步:递归挖掘条件递归挖掘条件FP-treef:3c:3a:3m-条件 FP-tree“am”的条件模式库:(fc:3)f:3c:3am-条件 FP-tree“cm”的条件模式:(f:3)f:3cm-条件 FP-tree“cam”条件模式库:(f:

22、3)f:3cam-条件 FP-treeAll frequent patterns concerning mm,fm,cm,am,fcm,fam,cam,fcam通过建立条件模式库得到频繁集EmptyEmptyf(f:3)|c(f:3)c(f:3,c:3)|a(fc:3)aEmpty(fca:1),(f:1),(c:1)b(f:3,c:3,a:3)|m(fca:2),(fcab:1)m(c:3)|p(fcam:2),(cb:1)p条件FP-tree条件模式库项FP-growth 比比Apriori快一个数量级快一个数量级原因：原因：不生成候选集，不用候选测试。使用紧缩的数据结构避免重复数据库扫描

23、基本操作是计数和建立 FP-tree 树关联规则挖掘：路线图关联规则挖掘：路线图布尔 vs.定量 关联(基于 处理数据的类型处理数据的类型)buys(x,“SQLServer”)buys(x,“DMBook”)buys(x,“DBMiner”)0.2%,60%age(x,“30.39”)income(x,“42.48K”)buys(x,“PC”)1%,75%单维 vs.多维 关联(例子同上)单层单层 vs.多层多层 分析分析那个品种牌子的啤酒与那个牌子的尿布有关系那个品种牌子的啤酒与那个牌子的尿布有关系?各种扩展相关性、因果分析关联并不一定意味着相关或因果关联并不一定意味着相关或因果最大模式和

24、闭合相集最大模式和闭合相集添加约束添加约束 如如,哪些哪些“小商品小商品”的销售促发了的销售促发了“大商品大商品”的买卖？的买卖？事务ID事务的项目集T1A,B,ET2B,DT3B,CT4A,B,DT5A,CT6B,CT7A,CT8A,B,C,ET9A,B,C65事务数据库的FP-树 频繁模式挖掘过程从FP-树中来挖掘频繁模式，先从L表中最后一项开始。E在FP-树有两个分枝，路经为和。以E为后缀，它的两个对应前缀路径是（BA:1）和（BAC:1），它们形成E的条件模式基。它的条件FP-树只包含单个路径；不包含C，因为它的支持度计数为1，小于最小支持度计数。该单个路径产生频繁模式的所有组合：BE

25、:2，AE:2，BAE:2。对于D，它的两个前缀形成条件模式基（BA:1）,（B:1），产生一个单节点的条件 FP-树（B:2），并导出一个频繁模式BD:2。对于C，它的条件模式基是（BA:2）,（B:2），（A:2），它的条件FP-树有两个分枝（B:4，A:2）和（A:2）。它的频繁模式集为：BC:4，AC:4，BAC:2。对于A，它的条件模式基是（B:4），它的FP-树只包含一个节点（B:4），产生一个频繁模式BA:4。频繁模式挖掘过程利用利用FP-树挖掘频繁模式树挖掘频繁模式项条件模式基条件FP-树频繁模式EBA:1，BAC:1(B:2,A:2)BE:2,AE:2,BAE:2DBA:1,B:1(B:2)BD:2CBA:2,B:2,A:2(B:4,A:2)(A:2)BC:4,AC:4,BAC:2AB:4(B:4)BA:469演讲完毕，谢谢观看！