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

第八章集合论方法12粗糙集概念3粗糙集含义知识的分类观点4粗糙集含义粗糙集是处理不精确、不确定与不完全数据的理论粗糙集概述1、粗糙集以等价关系（不可分辨关系）为基础，用于分类问题。2、它用上、下近似两个集合来逼近任意一个集合，该集合的边界线区域被定义为上近似集和下近似集之差集。3、上、下近似集可以通过等价关系给出确定的描述，边界域的含糊元素数目可以被计算出来。而模糊集（Fuzzy）是用隶属度来描述集合边界的不确定性，隶属度是认为给定的，不是计算得出了。粗糙集理论用在数据库中的知识发现主要体现在：1、利用等价关系对数据库进行属性约简；2、利用集合的上、下近似关系获取分类规则。基本定义——信息表定义基本定义——等价关系定义基本定义——等价类定义基本定义——划分的定义例：例：集合X的上、下近似关系——下近似定义集合X的上、下近似关系——上近似定义正域，负域和边界的定义用图来说明正域、负域和边界，每一个小长方形表示一个等价类。粗糙集定义例属性约简的粗糙集理论属性约简概念在信息表中根据等价关系，我们可以用等价类中的一个对象（元组）来代表整个等价类，这实际上是按纵方向约简了信息表中数据。对信息表中的数据按横方向进行约简就是看信息表中有无冗余的属性，即去除这些属性后能保持等价性，使对象分类能力不会下降。约简后的属性集称为属性约简集，约简集通常不唯一。约简定义核定义正域定义上面的约简定义没有考虑决策属性，下面研究条件属性C相对决策属性D的约简。属性约简实例属性约简实例属性约简实例属性约简实例属性约简的粗糙集方法——属性依赖度属性约简的粗糙集方法——属性重要度属性约简的粗糙集方法——最小属性集概念粗糙集方法的规则获取K-均值聚类聚类的问题描述为：给定数据集合D，把它划分为一组聚类：{C1，C2，……,CK},Ci∈D，使得不同类中的数据尽可能的不相似（或距离较远），而同一类中的数据尽可能的相似（或距离较近）。即聚类内紧凑，类间独立。K-均值聚类算法描述：1、为中心向量{C1，C2，……,CK}初始化K个种子；2、分组：1）将样本分配给距离其最近的中心向量；2）由这些样本构造不相交的聚类；3、确定中心：用各个聚类的中心向量作为新的中心；4、重复分组和确定中心的步骤，直至算法收敛。关联规则挖掘——基本原理设I={i1,i2,…,im}是项（Item）的集合。记D为事务（Transaction）的集合（事务数据库），事务T是项的集合，并且TI。设A是I中一个项集，如果AT，那么称事务T包含A。定义1：关联规则是形如AB的蕴涵式，这里AI，BI，并且AB=。定义2：规则的支持度。规则AB在数据库D中具有支持度S，表示S是D中事务同时包含AB的百分比，它是概率P(AB)，即：其中|D|表示事务数据库D的个数，表示A、B两个项集同时发生的事务个数。|D||AB|P(AB)B)(AS关联规则挖掘——基本原理定义3：规则的可信度。规则AB具有可信度C，表示C是包含A项集的同时也包含B项集，相对于包含A项集的百分比，这是条件概率P(B|A)，即：其中表示数据库中包含项集A的事务个数。定义4：阈值在事务数据库中找出有用的关联规则，需要由用户确定两个阈值：最小支持度（min_sup）和最小可信度（min_conf）。定义5：项的集合称为项集（Itemset），包含k个项的项集称之为k-项集。如果项集满足最小支持度，则它称之为频繁项集（FrequentItemset）。定义6：关联规则同时满足最小支持度（min_sup）和最小可信度（min_conf）的规则称之为关联规则，即成立时，规则称之为关联规则，也可以称为强关联规则。|A||AB|)|()BA(ABPC|A|min_confB)(Amin_supB)(ACS且关联规则挖掘过程关联规则的挖掘一般分为两个过程：（1）找出所有的频繁项集：根据定义，这些项集的支持度大于最小支持度的项集，即频繁项集。（2）由频繁项集产生关联规则：根据定义，这些规则必须满足最小支持度和最小可信度。其中，（2）是在（1）的基础上进行的，工作量非常小。挖掘关联规则的总体性能由（1）决定。关联规则的兴趣度例子：讨论不购买商品与购买商品的关系。设，交易集D，经过对D的分析，得到表格:37定义7：兴趣度公式反映了项集A与项集B的相关程度。若即表示项集A出现和项集B是相互独立的。若表示A出现和B出现是负相关的。若表示A出现和B出现是正相关的。意味着A的出现蕴含B的出现。()()()()PABIABPAPB1)BA(I)()()(BPAPABPI(A)1BI(A)1B兴趣度的含义1、一条规则的兴趣度越大于1说明我们对这条规则越感兴趣（即其实际利用价值越大）；2、一条规则的兴趣度越小于1说明我们对这条规则的反面规则越感兴趣（即其反面规则的实际利用价值越大）；3、兴趣度不小于0。所有可能的关联规则40讨论：I1﹑I2﹑I3﹑I6共4条规则：由于I1,I21,在实际中它的价值不大；I3,I61,规则才有价值。注：兴趣度也称为作用度（Lift）,表示关联规则A→B的“提升”。如果作用度（兴趣度）不大于1，则此关联规则就没有意义了。概括分析可信度是对关联规则地准确度的衡量。支持度是对关联规则重要性的衡量。支持度说明了这条规则在所有事务中有多大的代表性。有些关联规则可信度虽然很高，但支持度却很低，说明该关联规则实用的机会很小，因此也不重要。兴趣度（作用度）描述了项集A对项集B的影响力的大小。兴趣度越大，说明项集B受项集A的影响越大。Apriori算法基本思想Apriori是挖掘关联规则的一个重要方法。算法分为两个子问题：1、找到所有支持度大于最小支持度的项集（Itemset），这些项集称为频繁集（FrequentItemset）。2、使用第1步找到的频繁集产生规则。Apriori算法基本方法Apriori使用一种称作逐层搜索的迭代方法，“K-项集”用于探索“K+1-项集”。1、首先，找出频繁“1-项集”的集合。该集合记作L1。L1用于找频繁“2-项集”的集合L2，而L2用于找L3；2、如此下去，直到不能找到“K-项集”。找每个LK需要一次数据库扫描。Apriori性质性质：频繁项集的所有非空子集都必须也是频繁的。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，YLK，|XY|=K+1}其中C1是1-项集的集合，取自所有事务中的单项元素。例：如L1={{A}，{B}}C2={A}{B}={A，B}，且|AB|=2L2={{A，B}，{A，C}}C3={A，B}{A，C}={A，B，C}，且|ABC|=3Apriori算法中候选项集与频繁项集的产生实例事务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)确定频繁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是最大的频繁项集，即：｛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→L－S”。注：L－S表示在项集L中除去S子集的项集。confmin__SL过程举例在事务数据库中，频繁项集L={A，B，E}，可以由L产生哪些关联规则？L的非空子集S有：{A,B},{A,E},{B,E},{A},{B},{E}。可得到关联规则如下：A∧B→Econf=2/4=50%A∧E→Bconf=2/2=100%B∧E→Aconf=2/2==100%A→B∧Econf=2/6=33%B→A∧Econf=2/7=29%E→A∧Bconf=2/2=100%假设最小可信度为60％，则最终输出的关联规则为：A∧E→B100%B∧E→A100%E→A∧B100%对于频繁项集{A，B，C}，同样可得其它关联规则。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够快了吗?—性能瓶颈Apriori算法的核心:用频繁的(k–1)-项集生成候选的频繁k-项集；用数据库扫描和模式匹配计算候选集的支持度；Apriori的瓶颈:候选集生成巨大的候选集:104个频繁1-项集要生成107个候选2-项集；要找尺寸为100的频繁模式，如{a1,a2,…,a100},你必须先产生21001030个候选集；多次扫描数据库：如果最长的模式是n的话，则需要(n+1)次数据库扫描挖掘频繁集不用生成候选集1、用Frequent-Patterntree(FP-tree)结构压缩数据库高度浓缩，同时对频繁集的挖掘又完备的；避免代价较高的数据库扫描；2、开发一种高效的基于FP-tree的频繁集挖掘算法采用分而治之的方法学：分解数据挖掘任务为小任务；避免生成关联规则:只使用部分数据库；理论和实验表明该算法优于Apriori算法。FP-tree结构的好处1、完备:（1）不会打破交易中的任何模式；（2）包含了序列模式挖掘所需的全部信息；2、紧密（1）去除不相关信息—不包含非频繁项；（2）支持度降序排列:支持度高的项在FP-tree中共享的机会也高；（3）决不会比原数据库大（如果不计算树节点的额外开销)用FP-tree挖掘频繁集1、基本思想(分而治之)用FP-tree递归增长频繁集2、方法对每个项，生成它的条件模式库,然后是它的条件FP-tree；对每个新生成的条件FP-tree，重复这个步骤；直到结果FP-tree为空,或只含维一的一个路径(此路径的每个子