第6章-频繁模式挖掘

数据挖掘天津大学计算机科学与技术学院喻梅目录CONTENTS1.526.16.26.36.4概述Apriori算法FP-growth算法压缩频繁项集关联模式评估6.5Chapter6.1频繁模式概述46.1频繁模式概述啤酒与尿布在美国，著名的沃尔玛超市发现啤酒与尿布总是共同出现在购物车中，于是沃尔玛超市经过分析发现许多美国年轻的父亲下班之后经常要去购买婴儿的尿布，而在购买尿布的同时，他们往往会顺手购买一些啤酒；因此沃尔玛超市将啤酒与尿布放在相近的位置，方便顾客购买，并明显提高了销售额。购物车分析5面包和牛奶共同出现在购物车中，这代表了什么？买了这么多的鱼子酱，是因为促销吗？购买了油、牛奶、面包、香蕉、洗衣液、还应该有哪些商品？上图能挖掘出哪些有趣的模式？6.1频繁模式概述6Transaction-idItemsbought10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,F–项集包含0个或者多个项的集合–支持度s事务中同时包含集合A和集合B的百分比–置信度c事务中同时包含集合A和集合B的事务数与包含集合A的事务数的百分比例如：𝑆𝑢𝑝𝑝𝑜𝑟𝑡𝐴=𝐵=𝑃𝐴∪𝑃𝐵=1/5𝑐𝑜𝑛𝑓𝑖𝑑𝑒𝑛𝑐𝑒𝐴=𝐵=𝑃𝐵𝐴=1/3事务项集（5项集）6.1频繁模式概述7事务ID事务项10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,F–频繁模式支持度满足了最小支持度阈值的项集设最小支持度阈值为30%项集{A,D}的支持度为3/5=60%30%∴{𝐴,𝐷}是频繁项集。–关联规则–先验性质如果一个项集是频繁的，那么它的所有非空子集也是频繁的。形如X⇒Y的蕴含式𝐴=𝐷[支持度=60%，置信度=100%]强关联规则𝐴=𝐷[支持度=60%，置信度=100%]设最小支持度阈值为30%，最小置信度为70%6.1频繁模式概述Chapter6.2Apriori算法96.2Apriori算法关联规则挖掘的步骤1.找出所有频繁项集，即大于或等于最小支持度阈值的项集2.由频繁项集产生强关联规则，这些规则必须大于或等于最小支持度阈值和最小置信度阈值。106.2Apriori算法Apriori算法是布尔关联规则挖掘频繁项集的原创性算法，算法使用频繁项集性质的先验知识。•Apriori算法使用一种称为逐层搜索的迭代方法，其中k项集用于搜索(k+1)项集。•首先，通过扫描数据库，累计每个项的个数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记为L1，使用L1找出频繁2项集的集合L2，使用L2找出L3，如此下去，直到不能再找到频繁k项集。找出每一个LK需要一次数据库的完整扫描。11Apriori算法的实现步骤如下：−连接–算法初始设置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.2Apriori算法12Apriori算法如下：Apriori算法如下：输入：项集I，事务数据集D，最小支持度计数阈值Min_sup输出：D中的所有频繁项集的集合L。Apriori算法：(1)求频繁1项集L1首先通过扫描事务数据集D，找出所有1项集并计算其支持度，作为候选1项集C1然后从C1中删除低于最小支持度阈值Min_sup的项集，得到所有频繁1项集的集合L1（2）Fork=2,3,4，…（3）连接：将Lk-1进行自身连接生成候选k项集的集合Ck，连接方法如下：对于任意p,q∈Lk-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）ENDFOR（9）另L=L1∪L2∪…∪Lk，并输出L。6.2Apriori算法测试数据集13TIDItems1面包、可乐、麦片2牛奶、可乐3牛奶、面包、麦片4牛奶、可乐5面包、鸡蛋、麦片6牛奶、面包、可乐7牛奶、面包、鸡蛋、麦片8牛奶、面包、可乐9面包、可乐6.2Apriori算法例6.7Apriori算法假设使用表中的事务数据，该数据库具有9个事务，设最小支持度为2，试使用Apriori算法挖掘表6-3的事务数据中的频繁项集。146.2Apriori算法找到1项候选集的集合C1生成频繁1项集的集合L1项集支持度计数牛奶6面包7可乐6鸡蛋2麦片4C1L1生成2项候选集的集合C2项集支持度计数牛奶，面包4牛奶，可乐4牛奶，鸡蛋1牛奶，麦片2面包，可乐4面包，鸡蛋2面包，麦片4可乐，鸡蛋0可乐，麦片1鸡蛋，麦片2项集支持度计数牛奶，面包4牛奶，可乐4牛奶，麦片2面包，可乐4面包，鸡蛋2面包，麦片4鸡蛋，麦片2生成频繁1项集的集合L2C2L2生成2项候选集的集合C3生成频繁1项集的集合L3C3L3项集支持度计数牛奶6面包7可乐6鸡蛋2麦片4项集支持度计数牛奶，面包，可乐2牛奶，面包，麦片2面包，鸡蛋，麦片2项集支持度计数牛奶，面包，可乐2牛奶，面包，麦片2面包，鸡蛋，麦片2L={{牛奶}：6，{面包}：7，{可乐}：6，{鸡蛋}：2，{麦片}：4，{牛奶，面包}：4，{牛奶，可乐}：4，{牛奶，麦片}：2，{面包，可乐}：4，{面包，鸡蛋}：2，{面包，麦片}：4，{鸡蛋，麦片}：2，{牛奶，面包，可乐}：2，{牛奶，面包，麦片}：2，{面包，鸡蛋，麦片}：2}15关联规则的生成过程包括以下步骤：6.2Apriori算法关联规则的生成过程包括两个步骤：①对于L中的每个频繁项集X，生成X所有的非空真子集Y；②对于X中的每一个非空真子集Y，构造关联规则𝑌⇒(𝑋−𝑌。构造出关联规则后，计算每一个关联规则的置信度，如果大于最小置信度阈值，则该规则为强关联规则。16TIDItems1面包、可乐、麦片2牛奶、可乐3牛奶、面包、麦片4牛奶、可乐5面包、鸡蛋、麦片6牛奶、面包、可乐7牛奶、面包、鸡蛋、麦片8牛奶、面包、可乐9面包、可乐•{牛奶，麦片}⇒{面包}，置信度=2/2=100%•{面包，麦片}⇒{牛奶}，置信度=2/2=100%令最小置信度为70%，则得到的强关联规则有：6.2Apriori算法对于上例6中L中的频繁3项集{牛奶，面包，麦片}，可以推导出非空子集：{{牛奶}，{面包}，{麦片}，{牛奶，面包}，{牛奶，麦片}，{面包，麦片}}。可以构造的关联规则及置信度如下：{牛奶}{面包，麦片}，置信度=2/6=33%{面包}{牛奶，麦片}，置信度=2/7=29%{麦片}{牛奶，面包}，置信度=2/4=50%{牛奶，面包}{麦片}，置信度=2/4=50%{牛奶，麦片}{面包}，置信度=2/2=100%{面包，麦片}{牛奶}，置信度=2/2=100%176.2Apriori算法可以通过枚举频繁项集生成所有的关联规则，并通过计算关联规则的置信度来判断该规则是否为强关联规则。但当一个频繁项集包含的项很多时，就会生成大量的候选关联规则，一个频繁项集X能够生成2|X|-2个（即除去空集及自身之外的子集）候选关联规则。可以逐层生成关联规则，并利用如下关联规则的性质进行剪枝，以减少关联规则生成的计算工作量。关联规则性质：设X为频繁项集，Ø≠Y⊂X且Ø≠Y‘⊂Y。若Y⇒(𝑋−𝑌不是强关联规则，则Y’⇒(𝑋−𝑌′也不是强关联规则。首先产生后件只包含一个项的关联规则，然后两两合并关联规则的后件，生成后件包含两个项的候选关联规则，从这些候选关联规则中再找出强关联规则，以此类推。18TIDItems1面包、可乐、麦片2牛奶、可乐3牛奶、面包、麦片4牛奶、可乐5面包、鸡蛋、麦片6牛奶、面包、可乐7牛奶、面包、鸡蛋、麦片8牛奶、面包、可乐9面包、可乐•{牛奶，麦片}⇒{面包}，置信度=2/2=100%•{面包，麦片}⇒{牛奶}，置信度=2/2=100%令最小置信度为70%，则得到的强关联规则有：6.2Apriori算法对于上例6中L中的频繁3项集{牛奶，面包，麦片}，可以推导出非空子集：{{牛奶}，{面包}，{麦片}，{牛奶，面包}，{牛奶，麦片}，{面包，麦片}}。可以构造的后件只包含一个项的关联规则及置信度如下：{牛奶，面包}{麦片}，置信度=2/4=50%{牛奶，麦片}{面包}，置信度=2/2=100%{面包，麦片}{牛奶}，置信度=2/2=100%由上述两个强关联规则生成后件包含两个项的关联规则及置信度如下：{麦片}⇒{{牛奶，面包}，置信度=2/4=50%不是强关联规则196.2Apriori算法1.频繁项集的性质：①如果X是频繁项集，则它的任何非空子集X‘也是频繁项集。即频繁项集的子集也是频繁项集。②如果X是非频繁项集，则它的所有真超级都是非频繁项集。即非频繁项集的超集也是非频繁项集。2.关联规则的性质：①设X为频繁项集，Ø≠Y⊂X且Ø≠Y‘⊂Y。若Y’⇒(𝑋−𝑌′为强关联规则，则Y⇒(𝑋−Y也是强关联规则。②设X为频繁项集，Ø≠Y⊂X且Ø≠Y‘⊂Y。若Y⇒(𝑋−Y不是强关联规则，则Y’⇒(𝑋−𝑌′也不是强关联规则。关联规则挖掘中重要的基础理论：Chapter6.3FP-growth算法216.3FP-growth算法Apriori算法的优缺点•优点–算法原理简单，抑郁理解。•缺点：–需要多次扫描数据集•如果频繁项集最多包含10个项，需要扫描事务数据集10次，这需要很大的I/O负载–产生大量频繁项集•如数据集有100项，可能产生的候选项个数为1.27*1030226.3FP-growth算法频繁模式增长(frequent-patterngrowthFP-Growth)•将提供频繁项集的数据库压缩到FP-树，但仍保持项集关联信息;•压缩后的数据库分成一组条件数据库，每个数据库关联一个频繁项，并分别挖掘每个条件数据库;{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1HeaderTableItemfrequencyheadf4c4a3b3m3p323FP-growth算法实现步骤①第一次扫描事务数据集D，确定每个1项集的支持度计数，将频繁1项集按照支持度计数降序排序，得到排序后的频繁1项集集合L。②第二次扫描事务数据集D，读出每个事务并构建根结点为null的FP-tree。i.创建FP-tree的根结点，用null标记；ii.将事务数据集D中的每个事务中的集，删除非频繁项，将频繁项按照L中的顺序重新排列事务中项的顺序，并对每个事务创建一个分支；iii.当为一个事务考虑增加分支时，沿共同前缀上的每个结点的计数加1，为跟随前缀后的项创建结点并连接；iv.创建一个项头