《《关联规则七章》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《关联规则七章》PPT课件.ppt（35页珍藏版）》请在三一办公上搜索。
1、第7章 关联规则,7.1 关联规则 7.2 关联规则的挖掘方法7.3 算法与讨论7.4 Apriori算法（操作实例）,7.1 关联规则-引言,关联：是两个或多个变量取值之间存在的一类重要的可被发现的某种规律性关联可分为简单关联、时序关联、因果关联关联分析：目的是寻找给定数据记录集中数据项之间隐藏的关联关系，描述数据之间的密切度关联规则：是关联分析的常见结果，用于寻找在同一个事件中出现的不同项的相关性关联规则发现的主要对象是交易型数据库；关联规则是描述在一个交易中物品之间同时出现的规律的知识模式，更确切的说，关联规则是通过量化的数字描述物品A的出现对物品B的出现有多大的影响,7.1 关联规则-
2、例子,购物篮分析引发关联规则挖掘的例子问题：什么商品组或集合顾客多半会在一次购物中同时购买？购物篮分析：设全域为商店出售的商品的集合（即项目全集），一次购物（即事务）所购商品为项目全集的子集。若每种商品用一个布尔变量表示该商品的有无，则每个购物篮可用一个布尔向量表示。通过对布尔向量的分析，得到反映商品频繁关联或同时购买的购买模式，这些模式可用关联规则描述如：computerfinancial_management_software support=2%,confidence=60%support为支持度，confidence为可信度；该规则表示：在所分析的全部事务中，有2的事务同时购买计算机和
3、财务管理软件；在购买计算机的顾客中60也购买财务管理软件,7.1 关联规则-概念-1,关联（Associations）分析的目的是为了挖掘隐藏在数据间的相互关系，即对于给定的一组项目和一个记录集，通过对记录集的分析，得出项目集中的项目之间的相关性项目之间的相关性用关联规则来描述，关联规则反映了一组数据项之间的密切程度或关系形式化定义：令I=i1，i2，,in是项的集合，即项集，包含k个项的项集为k-项集；事务T是I上的一个子集，集合TI，每个事务用唯一的标志TID来标识；D是全体事务的集合关联规则（语法）：是形如AB的蕴含式，其中AI，BI且AB=，A称为规则的条件，B称为规则的结果,7.1
4、关联规则-概念-2,关联规则的支持度和可信度支持度是重要性的度量；可信度是准确度的度量规则 AB具有支持度S，表示S是D中事务包含AUB的百分比，即联合概率P(AUB)，也可以表示为：support(AB)=P(AUB)=(包含A和B的事务数/事务总数)100%规则 AB具有可信度C，表示C是包含A项集的同时也包含B项集，即条件概率P(B|A)，也可以表示为：confidence(AB)P(B|A)=(包含A和B的事务数/包含A的事务数)100,7.1 关联规则-概念-3,阈值：为了在事务数据库中找出有用的关联规则，需要确定两个阈值：最小支持度阈值min_sup和最小可信度阈值min_conf
5、频繁项集：满足最小支持度min_sup的项集频繁项集中，任意子项集中各项出现的联合概率（即项集的支持频度sup(T)）都大于最小支持度min_sup关联规则（语义）：支持度和可信度均不小于给定最小支持度阈值和最小置信度阈值的规则，是有意义有价值的，即：AB，若满足：S(AB)min_sup，且C(AB)min_conf,7.1 关联规则-概念-4,期望可信度：设事务集D中有e%的事务支持项集B，e%称为关联规则AB的期望可信度（与A无关）；描述了在没有任何条件影响时，项集B在所有事务中出现的概率，即P(B)作用度：是可信度与期望可信度的比值；描述项集A的出现对项集B的出现有多大影响，即概率P(
6、B|A)/P(B),7.1 关联规则-概念-小结,表：各参数的含义及计算公式,7.2 关联规则挖掘过程,可以把关联规则挖掘划分为以下两个子问题/子过程：找出所有的频繁项集项集的支持频度vs.最小支持度阈值可以从1到k递推查找k-频繁项集；是过程的核心步骤，关键技术，实现较困难由频繁项集产生关联规则，即找出满足最小支持度和最小可信度的关联规则关联规则的可信度vs.最小可信度阈值相对较容易,7.2 关联规则挖掘过程-简例,已知交易记录数据库D中有9条交易记录（事务）：T1：A，B，ET2：B，DT3：B，CT4：A，B，DT5：A，CT6：B，CT7：A，CT8：A，B，C，ET9：A，B，C设定
7、最小支持度为20%，最小可信度为60%找到所有的频繁项集，有A,B,C、A,B,E及其全部子集；(还有哪些？)产生关联规则，举例有：AEB（?，?）AB（?，?）BEA（?，?）AC（?，?）EAB（?，?）CA（?，?）,7.3 关联规则挖掘分类-1,（1）基于规则中处理的变量的类别布尔型关联规则：规则考虑的关联是项“在”或“不在”，所处理的值是离散的、种类化的如：computerfinancial_management_software min_sup=2%,min_conf=60%数值型关联规则：描述的是量化的项或属性之间的关联如（其中X表示顾客变量，量化属性age和income已经离散
8、化）：age(X,“3039”)income(X,“42K48K”)buys(X,“high_resolution_TV”),7.3 关联规则挖掘分类-2,（2）基于规则中数据的抽象层次单层关联规则：所有的变量的项或属性在同一细节层次如：buys(X,“computer”)buys(X,“printer”)顾客X购买的商品不涉及不同抽象层次（“computer”和“printer”在同一个抽象层）多层关联规则：变量涉及不同抽象层次的项或属性。如：age(X,“3039”)buys(X,“laptop computer”)；age(X,“3039”)buys(X,“computer”)顾客X购买
9、的商品涉及不同抽象层次（“computer”比“laptop computer”抽象层次更高）,7.3 关联规则挖掘分类-3,（3）基于规则中涉及到的数据的维数单维关联规则：关联规则只涉及数据的一个维度，处理单个维中属性间的关系如：coffee sugar，只涉及用户购买的物品，buy属性或维度多维关联规则：关联规则涉及数据的多个维，处理多个维中属性之间的关系如：sex=“f”occupation=“secretary”，涉及到两个维中字段的信息,7.4.1 Apriori算法概述-1,概述：最有影响的，挖掘布尔型关联规则的基本算法；根据有关频繁项集特性的先验（priori）知识而命名；采用层
10、次顺序搜索的循环方法来产生频繁项集，其间利用Apriori性质以帮助有效缩小频繁项集的搜索空间Apriori性质：一个频繁项集的任一子集也应是频繁项集证明：非频繁项集的任意超集(母集)是非频繁项集如：项集A不是频繁项集，P(A)min_sup，则P(AB)P(A)min_sup，所以也不是频繁项集,7.4.1 Apriori算法概述-2,Apriori算法的基本思想：首先，通过扫描数据集，产生一个大的1-候选数据项集，计算每个候选数据项发生的次数（项集的支持频度），然后基于预先给定的最小支持度生成频繁1-项集的集合L1；然后基于L1和数据集中的数据，产生频繁2-项集L2；用同样的方法，直到生成
11、频繁n-项集Ln，其中已不再可能生成满足最小支持度的（n+1）-项集；最后，从大数据项集中导出规则对于每个频繁项集L，产生它的所有非空子集S；检查每一个sS，若L的支持频度sup(L)与s的支持频度sup(s)之间有：sup(L)/sup(s)min_conf成立，则输出关联规则：s L-s,7.4.1 Apriori算法概述-3,关键步骤：由Lk-1找Lk，分两步完成第1步（连接）：为找Lk，通过Lk-1与自己连接产生候选K-项集的集合，将该候选项集的集合记作Ck，它是Lk的超集，可以不是频繁的，但所有的频繁k-项集都包含在其中连接发生在仅有一个不同项的各(k-1)-项集之间设l1和l2是L
12、k-1中的项集，记号lij表示li的第j项。执行连接Lk-1和Lk-1，其中Lk-1的元素是可连接，如果它们前（k-2）个项相同而且第（k-1）项不同（为简单计，设l1k-1l2k-1），即：l11=l21 l12=l22l1k-2=l2k-2 l1k-1l2k-1则Lk-1的元素l1和l2是可连接的，连接产生的结果是项集l11l12l1k-1l2k-1,7.4.1 Apriori算法概述-4,第2步（剪枝）：扫描数据库，确定Ck中每个候选的计数（项集的支持频度），以确定LkCk可能很大，这样所涉及的计算量就很大。为压缩Ck，可以使用Apriori性质：任何非频繁的（k-1）-项集都不可能是频
13、繁k-项集的子集。因此，如果一个候选k-项集的（k-1）-子集不在Lk-1中，则该候选也不可能是频繁的，从而可以由Ck中删除,7.4.2 Apriori算法示例-1,已知交易记录数据库D中有9条交易记录（事务）：T1：A，B，ET2：B，DT3：B，CT4：A，B，DT5：A，CT6：B，CT7：A，CT8：A，B，C，ET9：A，B，C设定最小支持度为20%，最小可信度为60%找到所有的频繁项集，有A,B,C、A,B,E及其全部子集；产生关联规则，举例有：AEB（20%，100%）AB（20%，67%）BEA（20%，100%）AC（20%，67%）EAB（20%，100%）CA（20%，6
14、7%）,7.4.2 Apriori算法示例-2,首先生成频繁1-项集从交易事务数据库中计算各单个项目的支持频度，有：P(A)=6/9，P(B)=7/9，P(C)=6/9，P(D)=2/9，P(E)=6/9，统统不小于最小支持度2/9，所以有L1=A,B,C,D,E然后产生频繁2-项集首先用连接操作对频繁1-项集自身做连接，生成候选2-项集；在连接时用1-频繁项集作剪枝；计算所剪枝后2-项集各项的支持频度；保留支持频度不小于最小支持度的2-项，所以有：频繁2-项集L2=A,B,A,C,A,E,B,C,B,D,B,E同理得到频繁3-项集L3=A,B,C,A,B,E由于找不到满足最小支持度约束的频繁
15、4-项集，所以频繁1-2-3-项集为所有的频繁项集,7.4.2 Apriori算法示例-3,频繁3-项集生成过程：用L2=A,B,A,C,A,E,B,C,B,D,B,E与L2作连接，生成候选3-项集：A,B,C,A,B,E,A,B,D,A,C,E在连接时用1-频繁和2-频繁项集作剪枝：由于A,D不是频繁项集，所以剪去A,B,D；由于C,E不是频繁项集，所以剪去A,C,E计算所剪枝后3-项集各项的支持频度：A,B,C的支持频度为2/9，A,B,E的支持频度为2/9保留支持频度大于最小支持度的3-项，所以有：频繁3-项集L3=A,B,C,A,B,E,7.4.2 Apriori算法示例-4,所有频繁
16、项集为：A,B,C,D,E,A,B,A,C,A,E,B,C,B,D,B,E,A,B,C,A,B,E举例对于L=A,B,E，其所有非空子集为：A,B,E,A,B,A,E,B,E,A,B,E设定最小可信度min_conf=60%，计算举例：对于s=A,B，sup(L)/sup(s)=2/4 60%对于s=A,E，sup(L)/sup(s)=2/2 60%，则有规则AEB 对于s=A，sup(L)/sup(s)=2/6 60%同理，最后得到关联规则有：AEB（20%，100%）BEA（20%，100%）EAB（20%，100%）,7.4.2 Apriori算法示例-5,设有如表8的事务记录，假定mi
17、n_sup=2/9=22%，min_conf=70%，求关联规则举例：I1I5I2（100%）I2I5I1（100%）I5I1I2（100%）,表：事务记录数据,Apriori算法,使用候选项集找频繁项集利用可信度挑选关联规则,Apriori算法（操作实例）,首先，确定最小支持度和最小置信度例如：从数据库D中发现关联规则,假设最小支持度要求为50%，最小置信度要求为80%,Apriori算法,其次，通过扫描数据集，产生一个大的候选数据项集,并计算每个候选数据项发生的次数，然后基于预先给定的最小支持度生成频繁1-项集的集合,Apriori算法,最小支持度为50%(出现2次),Apriori算法,
18、然后基于数据集中的数据，产生频繁2-项集,Apriori算法,然后基于数据集中的数据，产生频繁2-项集,Apriori算法,用同样的方法，直到生成频繁n-项集，其中已不再可能生成满足最小支持度的（n+1）-项集。,Apriori算法,C3,L3,L2,2,3,5,3,2,5,2,2,3,2,1,3,Sup.,Itemset,最后得到的频繁项集是：L1 L2 L3即：1，2，3，5，1,3，2,3，2,5，3,5，2,3,5,Apriori算法,最后导出规则第1步：对于每一个频繁项集I，产生I的所有非空子集。第2步：对于I的每一个非空子集s，如果 则输出关联规则“s(I-s)”,Apriori算法,Apriori算法,Apriori算法,若最小置信度设为80%，则最终所得的规则有：,作 业（讨论）,用matlab实现apriori提示：用矩阵表示事务元素用布尔变量表示-1/0/1函数形式function R=Aprior(D,min_sup,min_conf)分组完成，2周内完成,
