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

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

在信息表中根据等价关系，我们可以用等价类中的一个对象（元组）来代表整个等价类，这实际上是按纵方向约简了信息表中数据。对信息表中的数据按横方向进行约简就是看信息表中有无冗余的属性，即去除这些属性后能保持等价性，使对象分类能力不会下降。

约简后的属性集称为属性约简集，约简集通常不唯一。属性约简的粗糙集理论属性约简概念约简定义约简定义核定义核定义正域定义上面的约简定义没有考虑决策属性，下面研究条件属性C相对决策属性D的约简。正域定义上面的约简定义没有考虑决策属性，下面研究条件属性C相数据仓库与数据挖掘教程(第2版)第八章集合论方法属性约简实例属性约简实例属性约简实例属性约简实例属性约简实例属性约简实例属性约简实例属性约简实例属性约简的粗糙集方法——属性依赖度属性约简的粗糙集方法——属性依赖度属性约简的粗糙集方法——属性重要度属性约简的粗糙集方法——属性重要度属性约简的粗糙集方法——最小属性集概念属性约简的粗糙集方法——最小属性集概念粗糙集方法的规则获取粗糙集方法的规则获取K-均值聚类聚类的问题描述为：

给定数据集合D，把它划分为一组聚类：{C1，C2，……,CK},Ci∈D，使得不同类中的数据尽可能的不相似（或距离较远），而同一类中的数据尽可能的相似（或距离较近）。

即聚类内紧凑，类间独立。K-均值聚类聚类的问题描述为：K-均值聚类算法描述：

1、为中心向量{C1，C2，……,CK}初始化K个种子；2、分组：1）将样本分配给距离其最近的中心向量；2）由这些样本构造不相交的聚类；3、确定中心：用各个聚类的中心向量作为新的中心；4、重复分组和确定中心的步骤，直至算法收敛。K-均值聚类算法描述：关联规则挖掘——基本原理设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两个项集同时发生的事务个数。关联规则挖掘——基本原理设I={i1,i2,…,im}是项（关联规则挖掘——基本原理定义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）的规则称之为关联规则，即成立时，规则称之为关联规则，也可以称为强关联规则。关联规则挖掘——基本原理定义3：规则的可信度。规则AB具有关联规则挖掘过程关联规则的挖掘一般分为两个过程：（1）找出所有的频繁项集：根据定义，这些项集的支持度大于最小支持度的项集，即频繁项集。（2）由频繁项集产生关联规则：根据定义，这些规则必须满足最小支持度和最小可信度。其中，（2）是在（1）的基础上进行的，工作量非常小。挖掘关联规则的总体性能由（1）决定。关联规则挖掘过程关联规则的挖掘一般分为两个过程：关联规则的兴趣度例子：讨论不购买商品与购买商品的关系。设，交易集D，经过对D的分析，得到表格:

37关联规则的兴趣度例子：讨论不购买商品与购买商品的关系。37定义7：兴趣度

公式反映了项集A与项集B的相关程度。若即表示项集A出现和项集B是相互独立的。若表示A出现和B出现是负相关的。若表示A出现和B出现是正相关的。意味着A的出现蕴含B的出现。定义7：兴趣度兴趣度的含义1、一条规则的兴趣度越大于1说明我们对这条规则越感兴趣（即其实际利用价值越大）；2、一条规则的兴趣度越小于1说明我们对这条规则的反面规则越感兴趣（即其反面规则的实际利用价值越大）；3、兴趣度不小于0。兴趣度的含义1、一条规则的兴趣度越大于1说明我们对这条规则越所有可能的关联规则40讨论：I1﹑I2﹑I3﹑I6共4条规则：由于I1,I2<1,在实际中它的价值不大；I3,I6>1,规则才有价值。注：兴趣度也称为作用度（Lift）,表示关联规则A→B的“提升”。如果作用度（兴趣度）不大于1，则此关联规则就没有意义了。所有可能的关联规则40讨论：I1﹑I2﹑I3﹑I6共4条规概括分析可信度是对关联规则地准确度的衡量。支持度是对关联规则重要性的衡量。支持度说明了这条规则在所有事务中有多大的代表性。有些关联规则可信度虽然很高，但支持度却很低，说明该关联规则实用的机会很小，因此也不重要。兴趣度（作用度）描述了项集A对项集B的影响力的大小。兴趣度越大，说明项集B受项集A的影响越大。

概括分析可信度是对关联规则地准确度的衡量。Apriori算法基本思想Apriori是挖掘关联规则的一个重要方法。算法分为两个子问题：1、找到所有支持度大于最小支持度的项集（Itemset），这些项集称为频繁集（FrequentItemset）。2、使用第1步找到的频繁集产生规则。Apriori算法基本思想Apriori是挖掘关联规则的一个Apriori算法基本方法Apriori使用一种称作逐层搜索的迭代方法，“K-项集”用于探索“K+1-项集”。1、首先，找出频繁“1-项集”的集合。该集合记作L1。L1用于找频繁“2-项集”的集合L2，而L2用于找L3；2、如此下去，直到不能找到“K-项集”。找每个LK需要一次数据库扫描。Apriori算法基本方法Apriori使用一种称作逐层搜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-项集的集合，取自所有事务中的单项元素。Apriori性质性质：频繁项集的所有非空子集都必须也是频例：如L1={{A}，{B}}C2={A}{B}={A，B}，且|AB|=2L2={{A，B}，{A，C}}C3={A，B}{A，C}={A，B，C}，且|ABC|=3例：如L1={{A}，{B}}Apriori算法中候选项集与频繁项集的产生实例事务ID事务的项目集T1A,B,ET2B,DT3B,CT4A,B,DT5A,CT6B,CT7A,CT8A,B,C,ET9A,B,C46Apriori算法中候选项集与频繁项集的产生实例事务ID事过程举例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)在算法的第一次迭代，每个项都是候选1-项集的集具体产生过程用图表示具体产生过程用图表示候选集与频繁项集的产生项集支持度计数A,B 4 A,C 4 A,E 2 B,C 4 B,D 2 B,E 2 项集A,B，C A,B，E C3候选集L2频繁2-项集计算支持度项集支持度计数

A,B,C 2 A,B,E 2 项集支持度计数 A,B,C 2 A,B,E 2 C3候选集L3频繁3-项集候选集与频繁项集的产生项集支持度计数A,B 4 项集C3候产生关联规则根据前面提到的可信度的定义，关联规则的产生如下：（1）对于每个频繁项集L，产生L的所有非空子集；（2）对于L的每个非空子集S，如果

则输出规则“S→L－S”。注：L－S表示在项集L中除去S子集的项集。

产生关联规则根据前面提到的可信度的定义，关联规则的产生如下：过程举例在事务数据库中，频繁项集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}，同样可得其它关联规则。过程举例在事务数据库中，频繁项集L={A，B，E}，可以由LApriori算法程序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算法程序1、首先产生频繁1-项集L1，然后是频Apriori够快了吗?—性能瓶颈Apriori算法的核心:用频繁的(k–1)-项集生成候选的频繁k-项集；用数据库扫描和模式匹配计算候选集的支持度；Apriori的瓶颈:候选集生成巨大的候选集:104个频繁1-项集要生成107

个候选2-项集；要找尺寸为100的频繁模式，如

{a1,a2,…,a100},你必须先产生21001030

个候选集；多次扫描数据库：如果最长的模式是n的话，则需要

(n+1)次数据库扫描Apriori够快了吗?—性能瓶颈Apriori算法的挖掘频繁集不用生成候选集1、用Frequent-Patterntree(FP-tree)结构压缩数据库高度浓缩，同时对频繁集的挖掘又完备的；避免代价较高的数据库扫描；2、开发一种高效的基于FP-tree的频繁集挖掘算法采用分而治之的方法学：分解数据挖掘任务为小任务；避免生成关联规则:只使用部分数据库；理论和实验表明该算法优于Apriori算法。挖掘频繁集不用生成候选集1、用Frequent-PatteFP-tree结构的好处1、完备:（1）不会打破交易中的任何模式；（2）包含了序列模式挖掘所需的全部信息；2、紧密（1）去除不相关信息—不包含非频繁项；（2）支持度降序排列:支持度高的项在FP-tree中共享的机会也高；（3）决不会比原数据库大（如果不计算树节点的额外开销)FP-tree结构的好处1、完备:用FP-tree挖掘频繁集1、基本思想(分而治之)用FP-tree递归增长频繁集2、方法对每个项，生成它的条件模式库,然后是它的条件FP-tree；对每个新生成的条件FP-tree，重复这个步骤；直到结果FP-tree为空,或只含维一的一个路径(此路径的每个子路径对应的相集都是频繁集)。用FP-tree挖掘频繁集1、基本思想(分而治之)挖掘FP-tree的主要步骤1、为FP-tree中的每个节点生成条件模式库2、用条件模式库构造对应的条件FP-tree3、递归构造条件FP-trees同时增长其包含的频繁集如果条件FP-tree直包含一个路径，则直接生成所包含的频繁集。挖掘FP-tree的主要步骤1、为FP-tree中的每个节步骤1:从FP-tree到条件模式库（1）从FP-tree的头表开始；（2）按照每个频繁项的连接遍历

FP-tree；（3）列出能够到达此项的所有前缀路径，得到条件模式库；条件模式库item cond.patternbasec f:3a fc:3b fca:1,f:1,c:1m fca:2,fcab:1p fcam:2,cb:1{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表Itemfrequencyheadf 4c 4a 3b 3m 3p 3步骤1:从FP-tree到条件模式库（1）从FP-trFP-tree支持条件模式库构造的属性1、节点裢接任何包含ai,

的可能频繁集，都可以从FP-tree头表中的ai沿着ai的节点链接得到2、前缀路径要计算路径P中包含节点ai的频繁集，只要考察到达ai的路径前缀即可，且其支持度等于节点ai的支持度FP-tree支持条件模式库构造的属性1、节点裢接步骤2:建立条件FP-tree对每个模式库计算库中每个项的支持度用模式库中的频繁项建立FP-treem-条件模式库:fca:2,fcab:1{}f:3c:3a:3m-conditionalFP-tree{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表Itemfrequencyheadf 4c 4a 3b 3m 3p 3步骤2:建立条件FP-tree对每个模式库m-条件模式第3步:递归挖掘条件FP-tree{}f:3c:3a:3m-条件

FP-tree“am”的条件模式库:(fc:3){}f:3c:3am-条件FP-tree“cm”的条件模式:(f:3){}f:3cm-条件FP-tree“cam”条件模式库:(f:3){}f:3cam-条件FP-treeAllfrequentpatternsconcerningmm,fm,cm,am,fcm,fam,cam,fcam第3步:递归挖掘条件FP-tree{}f:3c:3a:3m通过建立条件模式库得到频繁集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条件模式库项通过建立条件模式库得到频繁集EmptyEmptyf{(f:3FP-growth比Apriori快一个数量级原因：不生成候选集，不用候选测试。使用紧缩的数据结构避免重复数据库扫描基本操作是计数和建立FP-tree树FP-growth比Apriori快一个数量级关联规则挖掘：路线图布尔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.多层

分析那个品种牌子的啤酒与那个牌子的尿布有关系?各种扩展相关性、因果分析关联并不一定意味着相关或因果最大模式和闭合相集添加约束如,哪些“小商品”的销售促发了“大商品”的买卖？关联规则挖掘：路线图布尔vs.定量关联(基于处理数事务ID事务的项目集T1A,B,ET2B,DT3B,CT4A,B,DT5A,CT6B,CT7A,CT8A,B,C,ET9A,B,C65事务ID事务的项目集T1A,B,ET2B,DT3B,CT4A事务数据库的FP-树事务数据库的FP-树频繁模式挖掘过程从FP-树中来挖掘频繁模式，先从L表中最后一项开始。E在FP-树有两个分枝，路经为<BAE:1>和<BACE:1>。以E为后缀，它的两个对应前缀路径是（BA:1）和（BAC:1），它们形成E的条件模式基。它的条件FP-树只包含单个路径<B:2,A:2>；不包含C，因为它的支持度计数为1，小于最小支持度计数。该单个路径产生频繁模式的所有组合：{BE:2，AE:2，BAE:2}。频繁模式挖掘过程从FP-树中来挖掘频繁模式，先从L表中最后一对于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}。频繁模式挖掘过程对于D，它的两个前缀形成条件模式基{（BA:1）,（B:1利用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利用FP-树挖掘频繁模式项条件模式基条件FP-树频繁模式EB第八章集合论方法70第八章集合论方法171粗糙集概念2粗糙集概念72粗糙集含义知识的分类观点3粗糙集含义知识的分类观点73粗糙集含义粗糙集是处理不精确、不确定与不完全数据的理论4粗糙集含义粗糙集是处理不精确、不确定与不完全数据的理论粗糙集概述1、粗糙集以等价关系（不可分辨关系）为基础，用于分类问题。2、它用上、下近似两个集合来逼近任意一个集合，该集合的边界线区域被定义为上近似集和下近似集之差集。3、上、下近似集可以通过等价关系给出确定的描述，边界域的含糊元素数目可以被计算出来。粗糙集概述1、粗糙集以等价关系（不可分辨关系）为基础，用于分而模糊集（Fuzzy）是用隶属度来描述集合边界的不确定性，隶属度是认为给定的，不是计算得出了。粗糙集理论用在数据库中的知识发现主要体现在：1、利用等价关系对数据库进行属性约简；2、利用集合的上、下近似关系获取分类规则。而模糊集（Fuzzy）是用隶属度来描述集合边界的基本定义——信息表定义基本定义——信息表定义基本定义——等价关系定义基本定义——等价关系定义基本定义——等价类定义基本定义——等价类定义基本定义——划分的定义基本定义——划分的定义例：例：例：例：集合X的上、下近似关系——下近似定义集合X的上、下近似关系——下近似定义集合X的上、下近似关系——上近似定义集合X的上、下近似关系——上近似定义正域，负域和边界的定义正域，负域和边界的定义用图来说明正域、负域和边界，每一个小长方形表示一个等价类。用图来说明正域、负域和边界，每一个小长方形表示一个等价类。粗糙集定义粗糙集定义例例属性约简的粗糙集理论属性约简概念

在信息表中根据等价关系，我们可以用等价类中的一个对象（元组）来代表整个等价类，这实际上是按纵方向约简了信息表中数据。对信息表中的数据按横方向进行约简就是看信息表中有无冗余的属性，即去除这些属性后能保持等价性，使对象分类能力不会下降。

约简后的属性集称为属性约简集，约简集通常不唯一。属性约简的粗糙集理论属性约简概念约简定义约简定义核定义核定义正域定义上面的约简定义没有考虑决策属性，下面研究条件属性C相对决策属性D的约简。正域定义上面的约简定义没有考虑决策属性，下面研究条件属性C相数据仓库与数据挖掘教程(第2版)第八章集合论方法属性约简实例属性约简实例属性约简实例属性约简实例属性约简实例属性约简实例属性约简实例属性约简实例属性约简的粗糙集方法——属性依赖度属性约简的粗糙集方法——属性依赖度属性约简的粗糙集方法——属性重要度属性约简的粗糙集方法——属性重要度属性约简的粗糙集方法——最小属性集概念属性约简的粗糙集方法——最小属性集概念粗糙集方法的规则获取粗糙集方法的规则获取K-均值聚类聚类的问题描述为：

给定数据集合D，把它划分为一组聚类：{C1，C2，……,CK},Ci∈D，使得不同类中的数据尽可能的不相似（或距离较远），而同一类中的数据尽可能的相似（或距离较近）。

即聚类内紧凑，类间独立。K-均值聚类聚类的问题描述为：K-均值聚类算法描述：

1、为中心向量{C1，C2，……,CK}初始化K个种子；2、分组：1）将样本分配给距离其最近的中心向量；2）由这些样本构造不相交的聚类；3、确定中心：用各个聚类的中心向量作为新的中心；4、重复分组和确定中心的步骤，直至算法收敛。K-均值聚类算法描述：关联规则挖掘——基本原理设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两个项集同时发生的事务个数。关联规则挖掘——基本原理设I={i1,i2,…,im}是项（关联规则挖掘——基本原理定义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）的规则称之为关联规则，即成立时，规则称之为关联规则，也可以称为强关联规则。关联规则挖掘——基本原理定义3：规则的可信度。规则AB具有关联规则挖掘过程关联规则的挖掘一般分为两个过程：（1）找出所有的频繁项集：根据定义，这些项集的支持度大于最小支持度的项集，即频繁项集。（2）由频繁项集产生关联规则：根据定义，这些规则必须满足最小支持度和最小可信度。其中，（2）是在（1）的基础上进行的，工作量非常小。挖掘关联规则的总体性能由（1）决定。关联规则挖掘过程关联规则的挖掘一般分为两个过程：关联规则的兴趣度例子：讨论不购买商品与购买商品的关系。设，交易集D，经过对D的分析，得到表格:

106关联规则的兴趣度例子：讨论不购买商品与购买商品的关系。37定义7：兴趣度

公式反映了项集A与项集B的相关程度。若即表示项集A出现和项集B是相互独立的。若表示A出现和B出现是负相关的。若表示A出现和B出现是正相关的。意味着A的出现蕴含B的出现。定义7：兴趣度兴趣度的含义1、一条规则的兴趣度越大于1说明我们对这条规则越感兴趣（即其实际利用价值越大）；2、一条规则的兴趣度越小于1说明我们对这条规则的反面规则越感兴趣（即其反面规则的实际利用价值越大）；3、兴趣度不小于0。兴趣度的含义1、一条规则的兴趣度越大于1说明我们对这条规则越所有可能的关联规则109讨论：I1﹑I2﹑I3﹑I6共4条规则：由于I1,I2<1,在实际中它的价值不大；I3,I6>1,规则才有价值。注：兴趣度也称为作用度（Lift）,表示关联规则A→B的“提升”。如果作用度（兴趣度）不大于1，则此关联规则就没有意义了。所有可能的关联规则40讨论：I1﹑I2﹑I3﹑I6共4条规概括分析可信度是对关联规则地准确度的衡量。支持度是对关联规则重要性的衡量。支持度说明了这条规则在所有事务中有多大的代表性。有些关联规则可信度虽然很高，但支持度却很低，说明该关联规则实用的机会很小，因此也不重要。兴趣度（作用度）描述了项集A对项集B的影响力的大小。兴趣度越大，说明项集B受项集A的影响越大。

概括分析可信度是对关联规则地准确度的衡量。Apriori算法基本思想Apriori是挖掘关联规则的一个重要方法。算法分为两个子问题：1、找到所有支持度大于最小支持度的项集（Itemset），这些项集称为频繁集（FrequentItemset）。2、使用第1步找到的频繁集产生规则。Apriori算法基本思想Apriori是挖掘关联规则的一个Apriori算法基本方法Apriori使用一种称作逐层搜索的迭代方法，“K-项集”用于探索“K+1-项集”。1、首先，找出频繁“1-项集”的集合。该集合记作L1。L1用于找频繁“2-项集”的集合L2，而L2用于找L3；2、如此下去，直到不能找到“K-项集”。找每个LK需要一次数据库扫描。Apriori算法基本方法Apriori使用一种称作逐层搜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-项集的集合，取自所有事务中的单项元素。Apriori性质性质：频繁项集的所有非空子集都必须也是频例：如L1={{A}，{B}}C2={A}{B}={A，B}，且|AB|=2L2={{A，B}，{A，C}}C3={A，B}{A，C}={A，B，C}，且|ABC|=3例：如L1={{A}，{B}}Apriori算法中候选项集与频繁项集的产生实例事务ID事务的项目集T1A,B,ET2B,DT3B,CT4A,B,DT5A,CT6B,CT7A,CT8A,B,C,ET9A,B,C115Apriori算法中候选项集与频繁项集的产生实例事务ID事过程举例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)在算法的第一次迭代，每个项都是候选1-项集的集具体产生过程用图表示具体产生过程用图表示候选集与频繁项集的产生项集支持度计数A,B 4 A,C 4 A,E 2 B,C 4 B,D 2 B,E 2 项集A,B，C A,B，E C3候选集L2频繁2-项集计算支持度项集支持度计数

A,B,C 2 A,B,E 2 项集支持度计数 A,B,C 2 A,B,E 2 C3候选集L3频繁3-项集候选集与频繁项集的产生项集支持度计数A,B 4 项集C3候产生关联规则根据前面提到的可信度的定义，关联规则的产生如下：（1）对于每个频繁项集L，产生L的所有非空子集；（2）对于L的每个非空子集S，如果

则输出规则“S→L－S”。注：L－S表示在项集L中除去S子集的项集。

产生关联规则根据前面提到的可信度的定义，关联规则的产生如下：过程举例在事务数据库中，频繁项集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}，同样可得其它关联规则。过程举例在事务数据库中，频繁项集L={A，B，E}，可以由LApriori算法程序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算法程序1、首先产生频繁1-项集L1，然后是频Apriori够快了吗?—性能瓶颈Apriori算法的核心:用频繁的(k–1)-项集生成候选的频繁k-项集；用数据库扫描和模式匹配计算候选集的支持度；Apriori的瓶颈:候选集生成巨大的候选集:104个频繁1-项集要生成107

个候选2-项集；要找尺寸为100的频繁模式，如

{a1,a2,…,a100},你必须先产生21001030

个候选集；多次扫描数据库：如果最长的模式是n的话，则需要

(n+1)次数据库扫描Apriori够快了吗?—性能瓶颈Apriori算法的挖掘频繁集不用生成候选集1、用Frequent-Patterntree(FP-tree)结构压缩数据库高度浓缩，同时对频繁集的挖掘又完备的；避免代价较高的数据库扫描；2、开发一种高效的基于FP-tree的频繁集挖掘算法采用分而治之的方法学：分解数据挖掘任务为小任务；避免生成关联规则:只使用部分数据库；理论和实验表明该算法优于Apriori算法。挖掘频繁集不用生成候选集1、用Frequent-PatteFP-tree结构的好处1、完备:（1）不会打破交易中的任何模式；（2）包含了序列模式挖掘所需的全部信息；2、紧密（1）去除不相关信息—不包含非频繁项；（2）支持度降序排列:支持度高的项在FP-tree中共享的机会也高；（3）决不会比原数据库大（如果不计算树节点的额外开销)FP-tree结构的好处1、完备:用FP-tree挖掘频繁集1、基本思想(分而治之)用FP-tree递归增长频繁集2、方法对每个项，生成它的条件模式库,然后是它的条件FP-tree；对每个新生成的条件FP-tree，重复这个步骤；直到结果FP-tree为空,或只含维一的一个路径(此路径的每个子路径对应的相集都是频繁集)。用FP-tree挖掘频繁集1、基本思想(分而治之)挖掘FP-tree的主要步骤1、为FP-tree中的每个节点生成条件模式库2、用条件模式库构造对应的条件FP-tree3、递归构造条件FP-trees同时增长其包含的频繁集如果条件FP-tree直包含一个路径，则直接生成所包含的频繁集。挖掘FP-tree的主要步骤1、为FP-tree中的每个节步骤1:从FP-tree到条件模式库（1）从FP-tree的头表开始；（2）按照每个频繁项的连接遍历

FP-tree；（3）列出能够到达此项的所有前缀路径，得到条件模式库；条件模式库item cond.patternbasec f:3a fc:3b fca:1,f:1,c:1m fca:2,fcab:1p fcam:2,cb:1{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表Itemfrequencyheadf 4c 4a 3b 3m 3p 3步骤1:从FP-tree到条件模式库（1）从FP-trFP-tree支持条件模式库构造的属性1、节点裢接任何包含ai,

的可能频繁集，都可以从FP-tree头表中的ai沿着ai的节点链接得到2、前缀路径要计算路径P中包含节点ai的频繁集，只要考察到达ai的路径前缀即可，且其支持度等于节点ai的支持度FP-tree支持条件模式库构造的属性1、节点裢接步骤2:建立条件FP-tree对每个模式库计算库中每个项的支持度用模式库中的频繁项建立FP-treem-条件模式库:fca:2,fcab:1{}f:3c:3a:3m-co