关联规则七章.ppt

《关联规则七章.ppt》由会员分享，可在线阅读，更多相关《关联规则七章.ppt（35页珍藏版）》请在三一文库上搜索。

1、第7章 关联规则,7.1 关联规则 7.2 关联规则的挖掘方法 7.3 算法与讨论 7.4 Apriori算法（操作实例）,7.1 关联规则-引言,关联：是两个或多个变量取值之间存在的一类重要的可被发现的某种规律性 关联可分为简单关联、时序关联、因果关联 关联分析：目的是寻找给定数据记录集中数据项之间隐藏的关联关系，描述数据之间的密切度 关联规则：是关联分析的常见结果，用于寻找在同一个事件中出现的不同项的相关性 关联规则发现的主要对象是交易型数据库； 关联规则是描述在一个交易中物品之间同时出现的规律的知识模式，更确切的说，关联规则是通过量化的数字描述物品A的出现对物品B的出现有多大的影响,7.

2、1 关联规则-例子,购物篮分析引发关联规则挖掘的例子 问题：什么商品组或集合顾客多半会在一次购物中同时购买？ 购物篮分析：设全域为商店出售的商品的集合（即项目全集），一次购物（即事务）所购商品为项目全集的子集。若每种商品用一个布尔变量表示该商品的有无，则每个购物篮可用一个布尔向量表示。通过对布尔向量的分析，得到反映商品频繁关联或同时购买的购买模式，这些模式可用关联规则描述 如：computerfinancial_management_software support=2%,confidence=60% support为支持度，confidence为可信度； 该规则表示：在所分析的全部事务中，有

3、2的事务同时购买计算机和财务管理软件；在购买计算机的顾客中60也购买财务管理软件,7.1 关联规则-概念-1,关联（Associations）分析的目的是为了挖掘隐藏在数据间的相互关系，即对于给定的一组项目和一个记录集，通过对记录集的分析，得出项目集中的项目之间的相关性 项目之间的相关性用关联规则来描述，关联规则反映了一组数据项之间的密切程度或关系 形式化定义： 令I=i1，i2，,in是项的集合，即项集，包含k个项的项集为k-项集；事务T是I上的一个子集，集合TI，每个事务用唯一的标志TID来标识；D是全体事务的集合 关联规则（语法）：是形如AB的蕴含式，其中AI，BI且AB=，A称为规则的

4、条件，B称为规则的结果,7.1 关联规则-概念-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,阈值：为了在事务数据库中找出有用的关联规则，需要确定两个阈值：

5、最小支持度阈值min_sup和最小可信度阈值min_conf 频繁项集：满足最小支持度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) 作用度： 是可

6、信度与期望可信度的比值； 描述项集A的出现对项集B的出现有多大影响，即概率P(B|A)/P(B),7.1 关联规则-概念-小结,表：各参数的含义及计算公式,7.2 关联规则挖掘过程,可以把关联规则挖掘划分为以下两个子问题/子过程： 找出所有的频繁项集 项集的支持频度vs.最小支持度阈值 可以从1到k递推查找k-频繁项集； 是过程的核心步骤，关键技术，实现较困难 由频繁项集产生关联规则，即找出满足最小支持度和最小可信度的关联规则 关联规则的可信度vs.最小可信度阈值 相对较容易,7.2 关联规则挖掘过程-简例,已知交易记录数据库D中有9条交易记录（事务）： T1：A，B，E T2：B，D T3：

7、B，C T4：A，B，D T5：A，C T6：B，C T7：A，C T8：A，B，C，E T9：A，B，C 设定最小支持度为20%，最小可信度为60% 找到所有的频繁项集，有A,B,C、A,B,E及其全部子集；(还有哪些？) 产生关联规则，举例有： AEB （?， ? ） AB （ ? ， ? ） BEA （ ? ， ? ） AC （ ? ， ? ） EAB （ ? ， ? ） CA （ ? ， ? ）,7.3 关联规则挖掘分类-1,（1）基于规则中处理的变量的类别 布尔型关联规则： 规则考虑的关联是项“在”或“不在”，所处理的值是离散的、种类化的 如：computerfinancial_ma

8、nagement_software min_sup=2%,min_conf=60% 数值型关联规则： 描述的是量化的项或属性之间的关联 如（其中X表示顾客变量，量化属性age和income已经离散化）：age(X,“3039”)income(X,“42K48K”)buys(X,“high_resolution_TV”),7.3 关联规则挖掘分类-2,（2）基于规则中数据的抽象层次 单层关联规则： 所有的变量的项或属性在同一细节层次 如：buys(X, “computer”) buys(X, “printer”) 顾客X购买的商品不涉及不同抽象层次（“computer” 和“printer”在同

9、一个抽象层） 多层关联规则： 变量涉及不同抽象层次的项或属性。 如：age(X,“3039”) buys(X, “laptop computer”)； age(X,“3039”) buys(X, “computer”) 顾客X购买的商品涉及不同抽象层次（“computer” 比“laptop computer”抽象层次更高）,7.3 关联规则挖掘分类-3,（3）基于规则中涉及到的数据的维数 单维关联规则： 关联规则只涉及数据的一个维度，处理单个维中属性间的关系 如： coffee sugar，只涉及用户购买的物品，buy属性或维度 多维关联规则： 关联规则涉及数据的多个维，处理多个维中属性之间

10、的关系 如：sex=“f” occupation=“secretary”，涉及到两个维中字段的信息,7.4.1 Apriori算法概述-1,概述： 最有影响的，挖掘布尔型关联规则的基本算法； 根据有关频繁项集特性的先验（priori）知识而命名； 采用层次顺序搜索的循环方法来产生频繁项集，其间利用Apriori性质以帮助有效缩小频繁项集的搜索空间 Apriori性质：一个频繁项集的任一子集也应是频繁项集 证明：非频繁项集的任意超集(母集)是非频繁项集 如：项集A不是频繁项集，P(A)min_sup，则P(AB) P(A)min_sup，所以也不是频繁项集,7.4.1 Apriori算法概述-2

11、,Apriori算法的基本思想： 首先，通过扫描数据集，产生一个大的1-候选数据项集，计算每个候选数据项发生的次数（项集的支持频度），然后基于预先给定的最小支持度生成频繁1-项集的集合L1； 然后基于L1和数据集中的数据，产生频繁2-项集L2 ； 用同样的方法，直到生成频繁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算

12、法概述-3,关键步骤：由Lk-1找Lk，分两步完成 第1步（连接）：为找Lk，通过Lk-1与自己连接产生候选K-项集的集合，将该候选项集的集合记作Ck ，它是Lk的超集，可以不是频繁的，但所有的频繁k-项集都包含在其中 连接发生在仅有一个不同项的各(k-1)-项集之间 设l1和l2是Lk-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是可连接的，连接

13、产生的结果是项集l11l12l1k-1l2k-1,7.4.1 Apriori算法概述-4,第2步（剪枝）：扫描数据库，确定Ck中每个候选的计数（项集的支持频度），以确定Lk Ck可能很大，这样所涉及的计算量就很大。为压缩Ck，可以使用Apriori性质：任何非频繁的（k-1）-项集都不可能是频繁k-项集的子集。因此，如果一个候选k-项集的（k-1）-子集不在Lk-1中，则该候选也不可能是频繁的，从而可以由Ck中删除,7.4.2 Apriori算法示例-1,已知交易记录数据库D中有9条交易记录（事务）： T1：A，B，E T2：B，D T3：B，C T4：A，B，D T5：A，C T6：B，C

14、T7：A，C T8：A，B，C，E T9：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%，67%）,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,

15、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 由于找不到满足最小支持度约束的频繁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

16、,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,所有频繁项集为： 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_c

17、onf=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的事务记录，假定min_sup=2/9=22%，min_conf=70%，求关联规则 举例： I1I5I2（100%） I2I5I1（100%） I5I1I2（100%）,表：事务记录数据,Apriori算法,使

18、用候选项集找频繁项集 利用可信度挑选关联规则,Apriori算法（操作实例）,首先，确定最小支持度和最小置信度 例如：从数据库D中发现关联规则,假设最小支持度要求为50%，最小置信度要求为80%,Apriori算法,其次，通过扫描数据集，产生一个大的候选数据项集,并计算每个候选数据项发生的次数，然后基于预先给定的最小支持度生成频繁1-项集的集合,Apriori算法,最小支持度为50%(出现2次),Apriori算法,然后基于数据集中的数据，产生频繁2-项集,Apriori算法,然后基于数据集中的数据，产生频繁2-项集,Apriori算法,用同样的方法，直到生成频繁n-项集，其中已不再可能生成满

19、足最小支持度的（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周内完成,