基于大数据的关联规则挖掘.pdf

《基于大数据的关联规则挖掘.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、大数据环境下的关联规则挖掘赵修湘2014年4月课程目标1mapred计算框架简介2关联规则挖掘简介3大数据环境下关联规则挖掘面临的挑战4大数据关联规则：mapred的解决方案5课程目录1mapred计算框架简介2关联规则挖掘简介3关联规则挖掘面临的挑战4mapred的解决方案一5mapred的解决方案二mapred计算框架简介MapReduce是一个使用简易的计算框架，基于它写出来的应用程序能够运行在由上千个商用机器组成的大型集群上，并以一种可靠容错的方式并行处理上T级别的数据集。一个MapReduce作业（job）通常会把输

2、入的数据集切分为若干独立的数据块，由map任务（task）以完全并行的方式处理它们。框架会对map的输出根据key先进行shuffle分配到reduce所在的服务器，在reduce端会对接收到的数据进行排序，然后把结果输入给reduce任务。通常作业的输入和输出都会被存储在文件系统中。整个框架负责任务的调度和监控，以及重新执行已经失败的任务。mapred计算框架简介课程目录1mapred计算框架简介2关联规则挖掘简介3关联规则挖掘面临的挑战4mapred的解决方案一5mapred的解决方案二关联规则挖掘简介关联规则挖掘发现大量

3、数据中项集之间有趣的关联或相关联系。它在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。关联规则挖掘的一个典型例子是购物篮分析。关联规则研究有助于发现交易数据库中不同商品（项）之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。关联规则挖掘简介支持度:P(A∪B)，即A和B这两个项集在事务集D中同时出现的概率。置信度:P(B｜A)，即在出现项集A的事务集D中，项集B也同时出现的概率。关联规则挖掘简介：Apriori算法Aprio

4、ri算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。关联规则挖掘简介：FPG算法FP-树频集算法。采用分而治之的策略，在经过第一遍扫描之后，把数据库中的频集压缩进一棵频繁模式树（FP-tre

5、e），同时依然保留其中的关联信息，随后再将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关，然后再对这些条件库分别进行挖掘。课程目录1mapred计算框架简介2关联规则挖掘简介3关联规则挖掘面临的挑战4mapred的解决方案一5mapred的解决方案二关联规则挖掘面临的挑战时间挑战：当数据量增长到一定程度时，单机挖掘所需求的时间呈几何级数增长空间挑战：当数据量增长到一定程度时，单机的内存无法全部保存所发现的有效模式课程目录1mapred计算框架简介2关联规则挖掘简介3关联规则挖掘面临的挑战4mapred的解决方案

6、一5mapred的解决方案二mapred的解决方案一：暴力法暴力法的思想是直接利用mapred集群运算的强大计算能力和存储能力暴力求解关联规则问题，mapred流程：map：读取交易日志，对交易日志中的items进行排序，对排序后的items产生所有可能的二项组合，输出combiner：读取本地map的输出，计算key出现的次数，输出reduce：读取combiner的输出，计算key的总次数课程目录1mapred计算框架简介2关联规则挖掘简介3关联规则挖掘面临的挑战4mapred的解决方案一5mapred的解决方案二mapr

7、ed的解决方案二：mapredApriori暴力法还是会遇上时间和空间约束的挑战在暴力法中，map阶段产生的key的个数：210000!C==5000*9999=49995000100002!100002!2100000!C==50000*99999=49999500001000002!1000002!mapred的解决方案二：mapredApriorimapredApriori算法流程：Step1：统计一项频繁集Step2：根据最小支持度过滤后的一项频繁集，统计二项频繁集Step3：根据最小支持度过滤后的二项频繁

8、集，生成三项候选集Step4：根据三项候选集，统计三项频繁集……StepN：直到没有更多的候选集产生mapred的解决方案二：mapredApriori问题：如何存储候选集？在统计频繁集阶段，我们需要知道那些候选集是需要统计的，但是如何有效存储亿级别的候选集？答案：bloom