第6章频繁模式挖掘ppt课件.pptx
,数据挖掘,2,Chapter 6.1,频繁模式概述,4,6.1 频繁模式概述,啤酒与尿布,在美国，著名的沃尔玛超市发现啤酒与尿布总是共同出现在购物车中，于是沃尔玛超市经过分析发现许多美国年轻的父亲下班之后经常要去购买婴儿的尿布，而在购买尿布的同时，他们往往会顺手购买一些啤酒；因此沃尔玛超市将啤酒与尿布放在相近的位置，方便顾客购买，并明显提高了销售额。,购物车分析,5,面包和牛奶共同出现在购物车中，这代表了什么？,买了这么多的鱼子酱，是因为促销吗？,购买了油、牛奶、面包、香蕉、洗衣液、还应该有哪些商品？,上图能挖掘出哪些有趣的模式？,6.1 频繁模式概述,6,项集,包含0个或者多个项的集合,支持度s,事务中同时包含集合A和集合B的百分比,置信度c,事务中同时包含集合A和集合B的事务数与包含集合A的事务数的百分比,例如： = = =1/5 = = =1/3,事务,项集（5项集）,6.1 频繁模式概述,7,频繁模式,支持度满足了最小支持度阈值的项集设最小支持度阈值为30%项集A,D的支持度为3/5=60%30%,是频繁项集。,关联规则,先验性质,如果一个项集是频繁的，那么它的所有非空子集也是频繁的。,形如XY的蕴含式=支持度=60%，置信度=100%,强关联规则,=支持度=60%，置信度=100%,设最小支持度阈值为30%，最小置信度为70%,6.1 频繁模式概述,Chapter 6.2,Apriori算法,9,6.2 Apriori算法,关联规则挖掘的步骤,找出所有频繁项集，即大于或等于最小支持度阈值的项集由频繁项集产生强关联规则，这些规则必须大于或等于最小支持度阈值和最小置信度阈值。,10,6.2 Apriori算法,Apriori算法,是布尔关联规则挖掘频繁项集的原创性算法，算法使用频繁项集性质的先验知识。,Apriori算法使用一种称为逐层搜索的迭代方法，其中k项集用于搜索(k+1)项集。首先，通过扫描数据库，累计每个项的个数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记为L1，使用L1找出频繁2项集的集合L2，使用L2找出L3，如此下去，直到不能再找到频繁k项集。找出每一个LK需要一次数据库的完整扫描。,11,Apriori算法的实现步骤如下：,连接算法初始设置k=1，使用连接运算从数据库中找到所有的k项候选集的集合 ，然后k增加1，直到k等于频繁项集的极大长度或频繁项集为空。构造k项候选集的集合 （k不等于1）时，每次连接步都使用前一次迭代中的所有频繁k-1项集的集合 1 的相互连接来构造频繁k项候选集的集合 = 1 1 ，其中 1 的元素是可连接的，如果它们前k-2个项是相同的，即两个可连接的元素只有最后一项不同，这样可简单地确保不产生重复。剪枝按照先验原理对得到的k项候选集的集合 进行剪枝，以减小因 较大而产生较大的计算量。先验性质指出如果某一k-1项集的支持度小于最小支持度阈值，那么它的所有真超项集的支持度都小于最小支持度阈值，所以该k-1项集和它的所有真超项集都不是频繁项集，从而可以在 中剪掉该k-1项集的真超k项集，在以后的迭代步骤中不予考虑。然后可以根据最小支持度阈值，在剪枝后的k项候选集的集合 中剪掉支持度小于最小支持度阈值的k项集，生成频繁k项集的集合 。,6.2 Apriori算法,12,Apriori算法如下：,Apriori算法如下：输入：项集I，事务数据集D，最小支持度计数阈值Min_sup输出：D中的所有频繁项集的集合L。Apriori算法：(1)求频繁1项集L1首先通过扫描事务数据集D，找出所有1项集并计算其支持度，作为候选1项集C1然后从C1中删除低于最小支持度阈值Min_sup的项集，得到所有频繁1项集的集合L1（2）For k=2,3,4，（3）连接：将Lk-1进行自身连接生成候选k项集的集合Ck，连接方法如下：对于任意p,qLk-1，若按字典序有p=p1,p2,pk-2,pk-1, q=p1,p2,pk-2,qk-1,且满足pk-1qk-1,则把p和q连接成k项集p1,p2,pk-2,pk-1,qk-1作为候选k项集Ck中的元素。（4）剪枝：删除Ck中的非频繁k项集，即当Ck中一个候选k项集的某个k-1项子集不是Lk-1中的元素时，则将它从Ck中删除。（5）计算支持数：通过扫描事务数据集D，计算Ck中每个k项集的支持数。（6）求Lk：删除Ck中低于最小支持度阈值Min_sup的k项集，得到所有频繁k项集的集合Lk。（7）若Lk=，则转第（9）步（8）END FOR（9）另L=L1L2Lk，并输出L。,6.2 Apriori算法,测试数据集,13,6.2 Apriori算法,例6.7 Apriori算法假设使用表中的事务数据，该数据库具有9个事务，设最小支持度为2，试使用Apriori算法挖掘表6-3的事务数据中的频繁项集。,14,6.2 Apriori算法,L=牛奶：6，面包：7，可乐：6，鸡蛋：2，麦片：4，牛奶，面包：4，牛奶，可乐：4，牛奶，麦片：2，面包，可乐：4，面包，鸡蛋：2，面包，麦片：4，鸡蛋，麦片：2，牛奶，面包，可乐：2，牛奶，面包，麦片：2，面包，鸡蛋，麦片：2,15,关联规则的生成过程包括以下步骤：,6.2 Apriori算法,关联规则的生成过程包括两个步骤：对于L中的每个频繁项集X，生成X所有的非空真子集Y；对于X中的每一个非空真子集Y，构造关联规则 ( 。构造出关联规则后，计算每一个关联规则的置信度，如果大于最小置信度阈值，则该规则为强关联规则。,16,牛奶，麦片 面包，置信度=2/2=100%面包，麦片 牛奶，置信度=2/2=100%,令最小置信度为70%，则得到的强关联规则有：,6.2 Apriori算法,对于上例6中L中的频繁3项集牛奶，面包，麦片，可以推导出非空子集：牛奶，面包，麦片，牛奶，面包，牛奶，麦片，面包，麦片。可以构造的关联规则及置信度如下：牛奶 面包，麦片，置信度=2/6=33%面包 牛奶，麦片，置信度=2/7=29%麦片 牛奶，面包，置信度=2/4=50%牛奶，面包 麦片，置信度=2/4=50%牛奶，麦片 面包，置信度=2/2=100%面包，麦片 牛奶，置信度=2/2=100%,17,6.2 Apriori算法,可以通过枚举频繁项集生成所有的关联规则，并通过计算关联规则的置信度来判断该规则是否为强关联规则。但当一个频繁项集包含的项很多时，就会生成大量的候选关联规则，一个频繁项集X能够生成2|X|-2个（即除去空集及自身之外的子集）候选关联规则。可以逐层生成关联规则，并利用如下关联规则的性质进行剪枝，以减少关联规则生成的计算工作量。关联规则性质：设X为频繁项集，YX且YY。若Y ()不是强关联规则，则Y ( )也不是强关联规则。首先产生后件只包含一个项的关联规则，然后两两合并关联规则的后件，生成后件包含两个项的候选关联规则，从这些候选关联规则中再找出强关联规则，以此类推。,18,牛奶，麦片 面包，置信度=2/2=100%面包，麦片 牛奶，置信度=2/2=100%,令最小置信度为70%，则得到的强关联规则有：,6.2 Apriori算法,对于上例6中L中的频繁3项集牛奶，面包，麦片，可以推导出非空子集：牛奶，面包，麦片，牛奶，面包，牛奶，麦片，面包，麦片。可以构造的后件只包含一个项的关联规则及置信度如下：牛奶，面包 麦片，置信度=2/4=50%牛奶，麦片 面包，置信度=2/2=100%面包，麦片 牛奶，置信度=2/2=100%,由上述两个强关联规则生成后件包含两个项的关联规则及置信度如下：麦片 牛奶，面包，置信度=2/4=50%不是强关联规则,19,6.2 Apriori算法,频繁项集的性质：如果X是频繁项集，则它的任何非空子集X也是频繁项集。即频繁项集的子集也是频繁项集。如果X是非频繁项集，则它的所有真超级都是非频繁项集。即非频繁项集的超集也是非频繁项集。2. 关联规则的性质：设X为频繁项集，YX且YY。若Y ( )为强关联规则，则Y (Y)也是强关联规则。设X为频繁项集，YX且YY。若Y (Y)不是强关联规则，则Y ( )也不是强关联规则。,关联规则挖掘中重要的基础理论：,Chapter 6.3,FP-growth算法,21,6.3 FP-growth算法,Apriori算法的优缺点,优点算法原理简单，抑郁理解。缺点：需要多次扫描数据集如果频繁项集最多包含10个项，需要扫描事务数据集10次，这需要很大的I/O负载产生大量频繁项集如数据集有100项，可能产生的候选项个数为1.27*1030,22,6.3 FP-growth算法,频繁模式增长(frequent-pattern growth FP-Growth),将提供频繁项集的数据库压缩到FP-树，但仍保持项集关联信息;压缩后的数据库分成一组条件数据库，每个数据库关联一个频繁项，并分别挖掘每个条件数据库;,23,FP-growth算法实现步骤,第一次扫描事务数据集D，确定每个1项集的支持度计数，将频繁1项集按照支持度计数降序排序，得到排序后的频繁1项集集合L。第二次扫描事务数据集D，读出每个事务并构建根结点为null的FP-tree。i. 创建FP-tree的根结点，用null标记；ii. 将事务数据集D中的每个事务中的集，删除非频繁项，将频繁项按照L中的顺序重新排列事务中项的顺序，并对每个事务创建一个分支；iii. 当为一个事务考虑增加分支时，沿共同前缀上的每个结点的计数加1，为跟随前缀后的项创建结点并连接；iv. 创建一个项头表，以方便遍历，每个项通过一个结点链指向它在树中的出现。从1项集的频繁项集中支持度最低的项开始，从项头表的结点链头指针，沿循每个频繁项的链接来遍历FP-tree，找出该频繁项的所有前缀路径，构造该频繁项的条件模式基，并计算这些条件模式基中每一项的支持度；通过条件模式基构造条件FP-tree，删除其中支持度低于最小支持度阈值的部分，满足最小支持度阈值的部分则是频繁项集；递归地挖掘每个条件FP-tree，直到找到FP-tree为空或者FP-tree只有一条路径，该路径上的所有项的组合都是频繁项集。,6.3 FP-growth算法,测试数据集,24,6.3 FP-growth算法,例6.8 FP-growth算法该数据集具有9个事务，设最小支持度为2，频繁项集的极大长度为3。试使用FP-growth算法挖掘表6-2的事务数据中的频繁项集。,25,6.3 FP-growth算法,图6-11 FP-tree,26,对于项集鸡蛋，开始向上找出所有前缀路径，找出其中的频繁模式：面包，鸡蛋：2麦片，鸡蛋：2面包，麦片，鸡蛋：2,6.3 FP-growth算法,图6-12 鸡蛋的条件FP-tree,27,对于项集麦片，开始向上找出所有前缀路径，找出其中的频繁模式：面包，麦片：4牛奶，麦片：2面包，牛奶，麦片：2,6.3 FP-growth算法,28,对于项集可乐，开始向上找出所有前缀路径，找出其中的频繁模式：面包，可乐：4牛奶，可乐：4面包，牛奶，可乐：2,6.3 FP-growth算法,29,对于项集牛奶，开始向上找出所有前缀路径，找出其中的频繁模式：面包，牛奶：4,6.3 FP-growth算法,30,6.3 FP-growth算法,图6-12 鸡蛋的条件FP-tree,表6-5 FP-tree 挖掘过程,31,性能研究表明FP-树比Apriori算法快一个数量级,原因减少没有候选集的产生，没有候选测试使用简洁的数据结构除去了重复的数据库扫描,6.3 FP-growth算法,Chapter 6.4,压缩频繁项集,在实际应用中，当最小支持度阈值较低或者数据规模较大时，使用频繁模式挖掘事务数据可能产生过多的频繁项集；而闭频繁模式、极大模式等模式可以显著减少频繁模式挖掘所产生的频繁项集数量。,33,6.4 压缩频繁项集,如果 ，且Y中至少有一项不在X中，那么Y是X的真超项集。如果在数据集中不存在频繁项集X的真超项集Y，使得X、Y的支持度相等，那么称项集X是这个数据集的闭频繁项集。,34,6.4 压缩频繁项集,1. 挖掘闭模式,35,6.4 压缩频繁项集,2. 剪枝的策略,项合并如果包含频繁项集X的每个事务都包含项集Y，但不包含Y的任何真超集，则XY形成一个闭频繁项集，并且不必搜索包含X但不包含Y的任何项集。子项集剪枝如果频繁项集X是一个已经发现的闭频繁项集Y的真子集，并且两者的支持度计数相等，则X和Y的所有后代都不可能是闭频繁项集，因此可以剪枝。,36,测试数据集,测试数据集,6.4 压缩频繁项集,表6-1 项集事务,37,最小支持度为2，可以得到d、e、ac、de、abc、acd、ace这些频繁项集的支持度都大于等于2，并且他们都不存在等于他们支持度的真超集，所以他们是闭频繁项集。,6.4 压缩频繁项集,38,3. 极大频繁项集：,如果在数据集中不存在频繁项集X的真超项集Y，使得X属于 Y并且Y也是频繁项集，那么称项集X是这个数据集的极大频繁项集。可以推导出极大频繁项集是闭频繁项集，而闭频繁项集不一定是极大频繁项集。,6.4 压缩频繁项集,39,假设最小支持度为2，从图中可知闭频繁项集d、e、ac、de、abc、acd、ace，根据定义de、abc、acd、ace则是极大频繁项集。,6.4 压缩频繁项集,Chapter 6.5,关联模式评估,强关联规则（支持度-置信度框架）不一定是有趣的测试数据集 最小支持度阈值为0.3，最小置信度阈值为0.6。,41,6.5 关联模式评估,表6-5 1000个人的手机偏爱,1. 支持度-置信度框架,2. 相关性分析 提升度令A和B表示不同的项集， ( 表示项集*在总体数据集中的出现概率。根据统计学定义，如果项集A和项集B的 ()=()( ，那么项集A和项集B是相互独立的，否则两者是相互依赖的。项集A和项集B的提升度定义如式(6-3)所示。如果A和B的提升度的值等于1，说明A和B相互独立；若是A和B的提升度的值大于1，说明A和B正相关；如果A和B的提升度的值小于1，说明A和B负相关。Lift(苹果手机 , 小米手机)=0.4/(0.75*0.6)=0.89,42,6.5 关联模式评估,2. 相关性分析杠杆度杠杆度和提升度的含义相近，其定义如式（6-4）所示。 A, = () （6-4）如果A和B的杠杆度的值等于0，则说明A和B相互独立；如果A和B的杠杆度的值大于0，说明A和B正相关，并且杠杆度越大，说明A和B的关系越密切；如果A和B的杠杆度的值小于0，说明A和B负相关。苹果手机、小米手机 的杠杆度为 苹果手机,小米手机 =0.40.60.75=0.05苹果手机和小米手机是负相关的。,43,6.5 关联模式评估,2. 相关性分析 皮尔森相关系数 皮尔森相关系数能够反映两个变量的相似程度，皮尔森相关系数值越大表明两个变量的相关性越强。对于二元变量，皮尔森相关系数定义如式(6-4)所示。苹果手机和小米手机的皮尔森相关系数为,44,6.5 关联模式评估,(苹果手机,小米手机)= （0.40.050.350.2） 0.60.40.750.25 =0.2357,2. 相关性分析关 IS度量 IS度量通常用于处理非对称二元变量，IS度量定义如式(6-5)所示。 IS度量的数值越大则说明A和B之间的关联越强。 苹果手机和小米手机的IS度量为(苹果手机,小米手机)= 0.4 0.60.75 =0.5963,45,6.5 关联模式评估,2. 相关性分析 确信度 确信度能够度量一个规则的强度，同时衡量A和B之间的独立性。确信度定义如式(6-6)所示。确信度越大，A和B关系越紧密。苹果手机和小米手机的确信度为(苹果手机,小米手机)= 0.60.25 0.2 =0.33541 ，说明苹果手机和小米手机的关系不紧密。,46,6.5 关联模式评估,(,)= ()( ( ,3. 模式评估度量 不包含任何考察项集的事务被称作零事务。提升度、皮尔森相关系数和卡方系数等度量在很大程度上受零事务的影响，因此它们识别关联模式关联关系的能力较差。 全置信度 全置信度反映了规则和规则的最小置信度。全置信度定义如式(6-7)所示。 _(,)= ( max(),() =min(|),(|) (6-7)对于项集A和B，全置信度越大，说明规则和规则的最小置信度越大，那么A和B关系越紧密，反之A和B关系越疏远。苹果手机和小米手机的全置信度为_ 苹果手机 , 小米手机 = 0.4 max0.6,0.75 =0.5333,47,6.5 关联模式评估,3. 模式评估度量极大置信度极大置信度则反映了规则和规则的最大置信度。极大置信度定义如式(6-8)所示。 max_(,)=max(|),(|) (6-8)对于项集A和B，极大置信度越大，A和B关系越紧密。苹果手机和小米手机的极大置信度为 max_( 苹果手机 , 小米手机 )=max（ 0.4 0.6 , 0.4 0.75 ）=0.667说明两者可能关系一般。,48,6.5 关联模式评估,3. 模式评估度量Kulczynski度量Kulczynski度量表示在项集A存在的情况下项集B也存在的条件概率和在项集B存在的情况下项集A也存在的条件概率之和的平均值。Kulczynski度量定义如式(6-9)所示。 (,)= 1 2 (|)+(|) (6-9)对于项集A和B，Kulczynski度量越大，说明平均可信程度越大，那么A和B关系越紧密。苹果手机和小米手机的Kulczynski度量为 ( 苹果手机 , 小米手机 )= 1 2 （ 0.4 0.6 + 0.4 0.75 ）=0.6说明两者关系一般。,49,6.5 关联模式评估,
