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

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

《数据仓库与数据挖掘教程(第2版)第八章集合论方法.pptx》由会员分享，可在线阅读，更多相关《数据仓库与数据挖掘教程(第2版)第八章集合论方法.pptx（69页珍藏版）》请在冰点文库上搜索。

第八章集合论方法,1,2,粗糙集概念,3,粗糙集含义,知识的分类观点,4,粗糙集含义,粗糙集是处理不精确、不确定与不完全数据的理论,粗糙集概述,1、粗糙集以等价关系（不可分辨关系）为基础，用于分类问题。

2、它用上、下近似两个集合来逼近任意一个集合，该集合的边界线区域被定义为上近似集和下近似集之差集。

3、上、下近似集可以通过等价关系给出确定的描述，边界域的含糊元素数目可以被计算出来。

而模糊集（Fuzzy）是用隶属度来描述集合边界的不确定性，隶属度是认为给定的，不是计算得出了。

粗糙集理论用在数据库中的知识发现主要体现在：

1、利用等价关系对数据库进行属性约简；2、利用集合的上、下近似关系获取分类规则。

基本定义信息表定义,基本定义等价关系定义,基本定义等价类定义,基本定义划分的定义,例：

例：

集合X的上、下近似关系下近似定义,集合X的上、下近似关系上近似定义,正域，负域和边界的定义,用图来说明正域、负域和边界，每一个小长方形表示一个等价类。

粗糙集定义,例,属性约简的粗糙集理论,属性约简概念在信息表中根据等价关系，我们可以用等价类中的一个对象（元组）来代表整个等价类，这实际上是按纵方向约简了信息表中数据。

对信息表中的数据按横方向进行约简就是看信息表中有无冗余的属性，即去除这些属性后能保持等价性，使对象分类能力不会下降。

约简后的属性集称为属性约简集，约简集通常不唯一。

约简定义,核定义,正域定义,上面的约简定义没有考虑决策属性，下面研究条件属性C相对决策属性D的约简。

属性约简实例,属性约简实例,属性约简实例,属性约简实例,属性约简的粗糙集方法属性依赖度,属性约简的粗糙集方法属性重要度,属性约简的粗糙集方法最小属性集概念,粗糙集方法的规则获取,K-均值聚类,聚类的问题描述为：

给定数据集合D，把它划分为一组聚类：

C1，C2，,CK,CiD，使得不同类中的数据尽可能的不相似（或距离较远），而同一类中的数据尽可能的相似（或距离较近）。

即聚类内紧凑，类间独立。

K-均值聚类,算法描述：

1、为中心向量C1，C2，,CK初始化K个种子；2、分组：

1）将样本分配给距离其最近的中心向量；2）由这些样本构造不相交的聚类；3、确定中心：

用各个聚类的中心向量作为新的中心；4、重复分组和确定中心的步骤，直至算法收敛。

关联规则挖掘基本原理,设I=i1,i2,im是项（Item）的集合。

记D为事务（Transaction）的集合（事务数据库），事务T是项的集合，并且TI。

设A是I中一个项集，如果AT，那么称事务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）和最小可信度（min_conf）。

定义5：

项的集合称为项集（Itemset），包含k个项的项集称之为k-项集。

如果项集满足最小支持度，则它称之为频繁项集（FrequentItemset）。

定义6：

关联规则同时满足最小支持度（min_sup）和最小可信度（min_conf）的规则称之为关联规则，即成立时，规则称之为关联规则，也可以称为强关联规则。

关联规则挖掘过程,关联规则的挖掘一般分为两个过程：

（1）找出所有的频繁项集：

根据定义，这些项集的支持度大于最小支持度的项集，即频繁项集。

（2）由频繁项集产生关联规则：

根据定义，这些规则必须满足最小支持度和最小可信度。

其中，

（2）是在

（1）的基础上进行的，工作量非常小。

挖掘关联规则的总体性能由

（1）决定。

关联规则的兴趣度,例子：

讨论不购买商品与购买商品的关系。

设，交易集D，经过对D的分析，得到表格:

37,定义7：

兴趣度,公式反映了项集A与项集B的相关程度。

若即表示项集A出现和项集B是相互独立的。

若表示A出现和B出现是负相关的。

若表示A出现和B出现是正相关的。

意味着A的出现蕴含B的出现。

兴趣度的含义,1、一条规则的兴趣度越大于1说明我们对这条规则越感兴趣（即其实际利用价值越大）；2、一条规则的兴趣度越小于1说明我们对这条规则的反面规则越感兴趣（即其反面规则的实际利用价值越大）；3、兴趣度不小于0。

所有可能的关联规则,40,讨论：

I1I2I3I6共4条规则：

由于I1,I21,规则才有价值。

注：

兴趣度也称为作用度（Lift）,表示关联规则AB的“提升”。

如果作用度（兴趣度）不大于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，BC2=AB=A，B，且|AB|=2L2=A，B，A，CC3=A，BA，C=A，B，C，且|ABC|=3,Apriori算法中候选项集与频繁项集的产生实例,46,过程举例,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。

具体产生过程用图表示,候选集与频繁项集的产生,产生关联规则,根据前面提到的可信度的定义，关联规则的产生如下：

（1）对于每个频繁项集L，产生L的所有非空子集；

（2）对于L的每个非空子集S，如果则输出规则“SLS”。

注：

LS表示在项集L中除去S子集的项集。

过程举例,在事务数据库中，频繁项集L=A，B，E，可以由L产生哪些关联规则？

L的非空子集S有：

A,B,A,E,B,E,A,B,E。

可得到关联规则如下：

ABEconf=2/4=50%AEBconf=2/2=100%BEAconf=2/2=100%ABEconf=2/6=33%BAEconf=2/7=29%EABconf=2/2=100%假设最小可信度为60，则最终输出的关联规则为：

AEB100%BEA100%EAB100%对于频繁项集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算法的核心:

用频繁的（k1）-项集生成候选的频繁k-项集；用数据库扫描和模式匹配计算候选集的支持度；Apriori的瓶颈:

候选集生成巨大的候选集:

104个频繁1-项集要生成107个候选2-项集；要找尺寸为100的频繁模式，如a1,a2,a100,你必须先产生21001030个候选集；多次扫描数据库：

如果最长的模式是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为空,或只含维一的一个路径（此路径的每个子路径对应的相集都是频繁集）。

挖掘FP-tree的主要步骤,1、为FP-tree中的每个节点生成条件模式库2、用条件模式库构造对应的条件FP-tree3、递归构造条件FP-trees同时增长其包含的频繁集如果条件FP-tree直包含一个路径，则直接生成所包含的频繁集。

步骤1:

从FP-tree到条件模式库,

（1）从FP-tree的头表开始；

（2）按照每个频繁项的连接遍历FP-tree；（3）列出能够到达此项的所有前缀路径，得到条件模式库；,条件模式库itemcond.patternbasecf:

3afc:

3bfca:

1,f:

1,c:

1mfca:

2,fcab:

1pfcam:

2,cb:

1,FP-tree支持条件模式库构造的属性,1、节点裢接任何包含ai,的可能频繁集，都可以从FP-tree头表中的ai沿着ai的节点链接得到2、前缀路径要计算路径P中包含节点ai的频繁集，只要考察到达ai的路径前缀即可，且其支持度等于节点ai的支持度,步骤2:

建立条件FP-tree,对每个模式库计算库中每个项的支持度用模式库中的频繁项建立FP-tree,m-条件模式库:

fca:

2,fcab:

1,f:

4,c:

1,b:

1,p:

1,b:

1,c:

3,a:

3,b:

1,m:

2,p:

2,m:

1,头表Itemfrequencyheadf4c4a3b3m3p3,第3步:

递归挖掘条件FP-tree,“am”的条件模式库:

（fc:

3）,“cm”的条件模式:

（f:

3）,f:

3,cm-条件FP-tree,“cam”条件模式库:

（f:

3）,f:

3,cam-条件FP-tree,Allfrequentpatternsconcerningmm,fm,cm,am,fcm,fam,cam,fcam,通过建立条件模式库得到频繁集,FP-growth比Apriori快一个数量级原因：

不生成候选集，不用候选测试。

使用紧缩的数据结构避免重复数据库扫描基本操作是计数和建立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.多层分析那个品种牌子的啤酒与那个牌子的尿布有关系?

各种扩展相关性、因果分析关联并不一定意味着相关或因果最大模式和闭合相集添加约束如,哪些“小商品”的销售促发了“大商品”的买卖？

65,事务数据库的FP-树,频繁模式挖掘过程,从FP-树中来挖掘频繁模式，先从L表中最后一项开始。

E在FP-树有两个分枝，路经为和。

以E为后缀，它的两个对应前缀路径是（BA:

1）和（BAC:

1），它们形成E的条件模式基。

它的条件FP-树只包含单个路径；不包含C，因为它的支持度计数为1，小于最小支持度计数。

该单个路径产生频繁模式的所有组合：

BE:

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-树挖掘频繁模式,69,