《数据仓库与数据挖掘原理及应用(第二版) 教学课件 ppt 作者 王丽珍 周丽华 陈红梅 第6章》由会员分享，可在线阅读，更多相关《数据仓库与数据挖掘原理及应用(第二版) 教学课件 ppt 作者 王丽珍 周丽华 陈红梅 第6章（61页珍藏版）》请在金锄头文库上搜索。
1、第六章 关联分析,2,第六章 目录,6.1 问题定义 6.2 Apriori算法 6.3 频繁项集的紧凑表示 6.4 FP-growth算法 6.5 本章小结,3,引例（1）,关联分析的一个典型应用是购物篮分析。所谓购物篮分析就是在某商店的销售事务数据集中分析该商店的“大部分顾客会在一次购物中同时购买什么商品？”，以便对商品促销、布局等提供帮助。 例如，如果某食品商店通过购物篮分析得知“大部分顾客会在一次购物中同时购买面包和牛奶”，那么该食品商店通过降价促销面包有可能同时提高面包和牛奶的销量。 再例如，如果某儿童用品商店通过购物篮分析得知“大部分顾客会在一次购物中同时购买奶粉和尿片”，那么该儿
2、童用品商店通过将奶粉和尿片分别放置在相距较远的地方，中间放置一些其他常用儿童用品，可能诱发顾客在购买奶粉和尿片时一路购买其他商品。,4,引例（2）,在购物篮分析中，我们用关联规则表示“在一次购物中同时购买的商品”的关联关系，用关联规则的支持度与置信度反映该关联规则对“大部分顾客”成立。 例如，在一次购物中同时购买面包和牛奶的关联关系可以用关联规则表示为：bread=milk。如果该关联规则的支持度为5%、置信度为70%，则表示全部顾客中5%同时购买面包和牛奶，购买面包的顾客中70%同时购买牛奶。,5,引例（3）,购物篮分析只是关联分析的一种形式与应用。事实上，关联分析可以分为许多种类。 1）根
3、据分析的模式类型，可以分为项集模式、子序列模式与子结构模式。 2）根据分析的规则类型，可以分为关联规则和相关规则。 3）根据规则的值类型，可以分为布尔关联规则与量化关联规则。 4）根据规则的数据维（或谓词），可以分为单维关联规则与多维关联规则。 5）根据规则的抽象层，可以分为单层关联规则与多层关联规则。,6,6.1 问题定义（1）,设I=i1,i2,im是项集合；T=t1,t2,tn是事务集合，其中 。A=B称为T中的关联规则，其中 。 在事务集合T中，包含 的事务占全部事务的百分比称为T中关联规则A=B的支持度，记为 。 在事务集合T中，包含 的事务占包含A的事务的百分比称为T中关联规则A=
4、B的置信度，记为 。,7,6.1 问题定义（2）,设min_sup是最小支持度阈值；min_conf是最小置信度阈值。如果事务集合T中的关联规则A=B同时满足 support(A=B)min_sup confidence(A=B)min_conf 则A=B称为T中的强关联规则。 关联规则挖掘就是在事务集合中挖掘强关联规则。,8,6.1 问题定义（3）,关联规则挖掘算法主要包括两个步骤： （1）产生频繁项集（支持度测试） 包含k个项的集合称为k-项集，记为Ik。 在事务集合T中，包含某k-项集Ik的事务数称为T中Ik的支持计数（或出现频率），记为sup_count(Ik)。 在事务集合T中，包含
5、某k-项集Ik的事务占全部事务的百分比称为T中Ik的支持度，记为support(Ik)=P(Ik)。 设n是事务集合T中的事务数，即n=|T|。如果T中某k-项集Ik的支持计数满足 sup_count(Ik)nmin_sup 即support(Ik)min_sup 则Ik称为T中的频繁k-项集。所有T中的频繁k-项集集合记为Lk。,9,6.1 问题定义（4）,产生频繁项集就是找出支持度大于等于最小支持度阈值的关联规则。 例如，如果项集a,b,c是频繁3-项集，即support(a,b,c)=P(a,b,c)min_sup，那么， support(a=bc)=support(b=ac)=supp
6、ort(c=ab) = support(ab=c)=support(ac=b)=support(bc=a) = P(a,b,c)min_sup （2）产生强关联规则（置信度测试） 产生强关联规则就是在由频繁项集的项组成的关联规则中，找出置信度大于等于最小置信度阈值的关联规则。 在上述两个步骤中，关键是第一步骤，它的效率影响整个关联规则挖掘算法的效率。因此，关联规则挖掘算法的核心是频繁项集产生方法。,10,6.2 Apriori算法 6.2.1 频繁项集产生（1）,1. Apriori性质 定理6.1 如果一个项集Ii是频繁项集，则它的所有非空子集Ij一定也是频繁项集。该定理也称为Apriori
7、性质。 证明： sup_count(Ij)sup_count(Ii) sup_count(Ii)nmin_sup sup_count(Ij)nmin_sup 证毕。,11,6.2.1 频繁项集产生（2）,根据Apriori性质，Apriori算法的基本思想是： 首先，扫描一次事务集合，找出频繁1-项集集合L1。 基于L1，产生所有可能频繁的2-项集，即候选2-项集集合C2（连接）； 基于L1，优化C2（剪枝）； 基于C2，再扫描一次事务集合，找出频繁2-项集集合L2（支持计数）。 依次类推，直至不能找到频繁项集为止。 最后，在所有频繁项集中产生强关联规则。,12,6.2.1 频繁项集产生（3）
8、,2. 连接：基于频繁k-项集集合Lk，产生所有可能频繁的(k+1)-项集，即候选(k+1)-项集集合Ck+1。 Apriori算法假设项集、事务中的项按字典序排列。 设lu,lvLk。如果(lu1=lv1)(luk-1=lvk-1)(luklvk)，其中lij（i=u或i=v，1jk）表示li的第j项，则lu，lv称为可连接的。 设lu,lvLk且是可连接的。lu,lv的连接运算定义为： =lw= lu1luk lvk。 例如，如果ab,ac,bcL2，那么ab与ac是可连接的，其连接运算结果为abc；ab与bc、ac与bc都不是可连接的。,13,6.2.1 频繁项集产生（4）,根据Apri
9、ori性质，可以证明连接运算是完备的，即 。因此，连接就是仅对频繁k-项集集合Lk中的所有可连接的频繁k-项集进行连接运算，产生候选(k+1)-项集集合Ck+1。这样，可以大量压缩搜索空间。 例如，在包含4个项a,b,c,d的搜索空间中，如果频繁1-项集集合L1=b,c,d,那么候选2-项集集合C2=bc,bd,cd，即如果1-项集a不是频繁项集，那么不用计算包含a的所有2-项集ab、ac、ad的支持度，当然也不用计算包含a的所有3-项集abc、abd、acd和4-项集abcd的支持度，从而压缩了搜索空间，如图6.1 所示。,14,6.2.1 频繁项集产生（5）,图6.1 连接步与剪枝步压缩搜
10、索空间,15,6.2.1 频繁项集产生（6）,3. 剪枝：基于频繁k-项集集合Lk，优化候选(k+1)-项集集合Ck+1。就是对候选(k+1)-项集集合Ck+1中的所有候选(k+1)-项集进行子集测试，优化候选(k+1)-项集集合Ck+1。这样，又可以进一步压缩搜索空间。 例如，如果频繁2-项集集合L2=bc,bd，那么候选3-项集集合C3=bcd，由于候选3-项集bcd的2-项集cd不是频繁项集，所以可以删除，不用计算它的支持度，从而又压缩了搜索空间，如图6.1所示。,16,6.2.1 频繁项集产生（7）,4. 支持计数：基于候选(k+1)-项集集合Ck+1，扫描一次事务集合，找出频繁(k+
11、1)-项集集合Lk+1。 1）Apriori算法按字典序从最左项到最右项依次指定项集的项。 例如，如果事务为abcde，那么3-项集的第一项（最左项）只能是abcde、bcde、cde，前二项只能是abcde、acde、ade、bcde、bde、cde，3-项集只能是abc、abd、abe、acd、ace、ade、bcd、bce、bde、cde，其中， 表示随后可跟的项。,17,6.2.1 频繁项集产生（8）,2）Apriori算法采用Hash树。候选项集按字典序从最左项到最右项依次指定散列的Hash树分枝，最后存放于Hash树的叶节点中。事务项集也按相同的方法散列到Hash树的叶节点，并仅需
12、与叶节点中的候选项集比较，而不需与所有候选项集比较。 例如，如果候选3-项集集合C3=abc,acd,bef,cdf,cef,def，Hash树有三个分枝，事务为abcde，那么Hash树结构、候选项集分布、枚举与散列事务项集及匹配候选项集过程如图6.2所示。,18,6.2.1 频繁项集产生（9）,图6.2 Hash树结构、候选项集分布、枚举与散列事务项集及匹配候选项集过程,19,6.2.1 频繁项集产生（10）,例 6.1 假设事务集合T如表6.1所示，最小支持度阈值min_sup为20%。写出搜索所有频繁项集的过程。 因为：min_sup=20% n=9 n*min_sup =9*20%=
13、1.8 所以：支持计数大于等于1.8的项集是频繁项集。,20,6.2.1 频繁项集产生（10）,21,6.2.1 频繁项集产生（11）,表6.7 频繁3-项集集合L3,22,6.2.2 规则产生（1）,1）对于每个频繁项集l，产生l的所有非空真子集。 2）对于l的每个非空真子集lu，如果l的支持计数除以lu的支持计数大于等于最小置信度阈值min_conf，则输出强关联规则lu=(llu)。其中，因为l是频繁项集，根据Apriori性质，lu与(llu)都是频繁项集，所以，其支持计数在频繁项集产生阶段已经计算，在此不必重复计算。,23,6.2.2 规则产生（2）,例 6.2 假设最小置信度阈值m
14、in_ conf为70%。写出由例6.1中的频繁项集i1i2i5的所有项组成的强关联规则。 因为：频繁项集i1i2i5的支持计数为2，它的所有非空真子集及其支持计数如表6.8所示。 所以：强关联规则有 i5=i1i2 i1i5=i2 i2i5=i1,24,6.2.2 规则产生（3）,定理6.2 对于频繁项集l及其两个非空真子集lu和lv，如果 ，并且规则lu=(llu)不是强关联规则，则规则lv=(llv)也不是强关联规则。 证明： sup_count(lv)sup_count(lu) 证毕。 定理6.2也可以说，如果 ，并且规则lu=(llu)不是强关联规则，则规则lv=(llv)也不是强关
15、联规则。,25,6.2.2 规则产生（4）,Apriori算法对于每个频繁项集，采用逐层搜索策略产生其强关联规则，同时根据定理6.2压缩搜索空间。 对于每个频繁项集，第一层产生后件只有一项的强关联规则，并生成它们的1-后件集合R1； 第二层产生后件有两项的强关联规则，但是根据定理6.2，可以通过R1中的只有一项的后件进行连接运算产生有两项的后件，再通过置信度计算，产生后件有两项的强关联规则，并生成它们的2-后件集合R2； 依次类推，可以产生所有强关联规则；其中，后件连接运算与频繁项集连接运算一样。,26,6.2.2 规则产生（5）,图6.3 压缩强关联规则搜索空间,27,6.2.3 Apriori算法 （1）,1. 算法描述 算法：Apriori算法 输入：事务集合T，最小支持度阈值min_sup，最小置信度阈值min_conf 输出：强关联规则集合SR 变量：频繁k-项集集合Lk，候选k-项集集合Ck，频繁项集集合L，k-后件集合Rk 步骤： /频繁项集产生 （1）for T中的每个事务t （1.1）for t中的每个项i （1.1.1）i.sup_count=i.sup
