第6章-频繁模式挖掘ppt课件.pptx

《第6章-频繁模式挖掘ppt课件.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据挖掘天津大学计算机科学与技术学院喻梅目录CONTENTS1.526.16.26.36.4概述Apriori算法FP-growth算法压缩频繁项集关联模式评估6.5Chapter6.1频繁模式概述46.1频繁模式概述啤酒与尿布在美国，著名的沃尔玛超市发现啤酒与尿布总是共同出现在购物车中，于是沃尔玛超市经过分析发现许多美国年轻的父亲下班之后经常要去购买婴儿的尿布，而在购买尿布的同时，他们往往会顺手购买一些啤酒；因此沃尔玛超市将啤酒与尿布放在相近的位置，方便顾客购买，并明显提高了销售额。购物车分析5面包和牛奶共同出现在购物车中，这代表了什么？买了这么多的鱼子酱

2、，是因为促销吗？购买了油、牛奶、面包、香蕉、洗衣液、还应该有哪些商品？上图能挖掘出哪些有趣的模式？6.1频繁模式概述6Transaction-idItemsbought10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,F项集包含0个或者多个项的集合支持度s事务中同时包含集合A和集合B的百分比置信度c事务中同时包含集合A和集合B的事务数与包含集合A的事务数的百分比事务项集（5项集）6.1频繁模式概述7事务ID事务项10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,F频繁模式支持度满足了最小支持度阈值的项集设最

3、小支持度阈值为30%项集{A,D}的支持度为3/5=60%>30%∴{?,?}是频繁项集。关联规则先验性质如果一个项集是频繁的，那么它的所有非空子集也是频繁的。形如X⇒Y的蕴含式?=>?[支持度=60%，置信度=100%]强关联规则?=>?[支持度=60%，置信度=100%]设最小支持度阈值为30%，最小置信度为70%6.1频繁模式概述Chapter6.2Apriori算法96.2Apriori算法关联规则挖掘的步骤找出所有频繁项集，即大于或等于最小支持度阈值的项集由频繁项集产生强关联规则，这些规则必须大于或等于最小支持度阈值和最小置信度阈值。106.2Ap

4、riori算法Apriori算法是布尔关联规则挖掘频繁项集的原创性算法，算法使用频繁项集性质的先验知识。Apriori算法使用一种称为逐层搜索的迭代方法，其中k项集用于搜索(k+1)项集。首先，通过扫描数据库，累计每个项的个数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记为L1，使用L1找出频繁2项集的集合L2，使用L2找出L3，如此下去，直到不能再找到频繁k项集。找出每一个LK需要一次数据库的完整扫描。11Apriori算法的实现步骤如下：6.2Apriori算法12Apriori算法如下：Apriori算法如下：输入：项集I，事务数据集D，最

5、小支持度计数阈值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-1

6、-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面包、鸡蛋

7、、麦片6牛奶、面包、可乐7牛奶、面包、鸡蛋、麦片8牛奶、面包、可乐9面包、可乐6.2Apriori算法例6.7Apriori算法假设使用表中的事务数据，该数据库具有9个事务，设最小支持度为2，试使用Apriori算法挖掘表6-3的事务数据中的频繁项集。146.2Apriori算法L={{牛奶}：6，{面包}：7，{可乐}：6，{鸡蛋}：2，{麦片}：4，{牛奶，面包}：4，{牛奶，可乐}：4，{牛奶，麦片}：2，{面包，可乐}：4，{面包，鸡蛋}：2，{面包，麦片}：4，{鸡蛋，麦片}：2，{牛奶，面包，可乐}：2，{牛奶，面包，麦片}：2，{面包，鸡蛋，麦

8、片}：2}15关联规则的生成过程包括以下步骤：6.2