科学网 › 标签 › apriori

标签: apriori

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

数据挖掘领域必须熟悉的十大经典算法其一——Apriori算法: minekirito 2019-1-22 20:49; 国际权威学术组织 IEEE International Conference on Data Mining评出了数据挖掘领域的十大经典算法。在真正进入数据挖掘算法的学习之前，这十个在该领域产生了深远影响的算法应该优先学习一下。注：本文是对《大数据、数据挖掘与智慧运营综述》第一章的重新梳理，并加入了自己的理解。每个算法只是简单介绍，日后会详细研究。 Apriori 算法是最有影响力的挖掘布尔关联规则的算法，就是挖掘数据中潜在的关联关系。例如著名的购物篮问题中顾客在买完尿布之后通常会买啤酒。作为第一个关联规则挖掘算法，它开创性的使用了基于支持度的剪枝技术。该算法的核心是基于两段频集思想的递推算法。（其中有很多数理统计相关的知识）频集是指所有支持度大于最小支持度的项。在频集中，所有置信度大于最小置信度的规则成为强关联规则。首先，先找出所有的频集。然后再由频集找出强规则。大部分的计算都集中在第一步，故对于 Apriori 的效率优化也集中在第一步。产生候选项时，有一个先验原理。如果一个项集是频繁的，则他的子集也是频繁的。相反，如果一个项集是非频繁的，则包含它的所有超集一定是非频繁的。 Apriori 会将所有非频繁的集剪掉近些年对于 Apriori 的优化主要从一下几个方面入手： 1. 减少比较次数。相同项目之间的比较太多，如何避免重复的比较从而提高算法效率？ 2. 减少候选项集数。在寻找频集的过程中，原有的方法先利用已知的（ k-1 ）维的频集来找出候选的 k 维频集又要回去穷举一遍候选项集是不是频集。如果可以减少遍历的次数（利用 hash 函数），或者更直接的生成候选频集那么就可以提高算法的效率。 3. 压缩原始数据库，对数据库的项目进行预修剪，减少时间开销。近两年关于 Apriori 的研究相比其他算法有所减少，希望日后可以看到优秀的新方法。; 个人分类: 数据挖掘算法介绍|2873 次阅读|0 个评论

机器学习之关联分析——Apriori代码一: iggcas010 2018-6-23 21:41; 上次的代码终于调好了，好累啊！接上次博文： \0 http://blog.sciencenet.cn/home.php?do=blogid=1119829mod=spacequickforward=1uid=1966190bsh_bid=2094879447 \0 《机器学习实战》这本书里的代码可以用在python27中，我这python365得不到正确结果。于是本人给代码进行“换血”改成python365可用的程序，费了我好几天时间。附件竟然不支持这种文件上传，好吧，我传到了百度云。 7天内有效，时效过了还想要给我发邮件。邮件地址之前的博文有。链接： https://pan.baidu.com/s/1hC9Ju9NFY1XIHKQT23dPqA 密码：uqp9 网上所见全部是上面那本书中的，甚至一点都不改，有的还抄人家的书发成博文，无耻！！！本人仅仅参考思路，将程序进行了修改。调用方法如下： importmy_apriori2asma data= , , , ] #1包子2油条3豆浆4煎饼5香肠 data2= , , , ] data=data2 min_supp=0.5 C_all,_=ma.ctotal(data,True) #这个函数第二个参数要么是最小支持度，要么是True #最小支持度时计算满足最小支持度的组合，是True时生成所有组合 print('所有的组合情况如下：\\n',C_all) C_length=ma.c_length(C_all) clen=len(C_all ) ##print(C_length==2**clen-1) C,C_supp=ma.ctotal(data,min_supp) print('满足最小支持度的组合如下：\\n',C) 结果为：所有的组合情况如下： , , , , ], , , , , , , , , , ], , , , , , , , , , ], , , , , ], ]] 满足最小支持度的组合如下： , , , ], , , , ], ]] 这种结果与将字符串换成数字是一样的，自己可以试试哈。看到这个结果或许你再也不吃路边摊的早点了，老是包子、油条、豆浆、煎饼、香肠，都想吐了 \0 \0 \0 \0 \0 \0 本人的结果和那本书中结果一致。截图如下：下期预告：发掘关联规则; 2065 次阅读|0 个评论

apriori关联挖掘算法的mapreduce并行化: taiyangqi 2014-10-7 21:00; 关联规则算法用来描述事物之间的联系和挖掘事物之间的相关性，其核心是通过统计数据项获得频繁项集，被广泛应用于分类设计、捆绑式销售、仓储货存配置等领域，涌现出了 Apriori 、 Partition 、 fp-Growth 、 CD 、 DD 、 CaD 等诸多频繁项集挖掘算法，随着大数据时代的到来，传统的挖掘算法无论运算能力还是并行效率都不能满足人们的要求，云计算和并行计算的出现给频繁项集挖掘带来了新的契机。传统的 Apriori 算法过程：采用逐层迭代的方法，从 k 项集推出 k+1 项集。首先发现频繁项集，然后生成关联规则，查找频繁项集会消耗大量计算机资源 D 为数据集，设 L k 是 k 项频繁项集， C k 是 k 项候选集传统 Apriori 算法过程：求频繁 1 项集 L 1 ，以集合 I 作为候选集 C 1 , 扫描数据集 D ，获取候选项集 C 1 的支持度，找出最小支持度 min_sup 的元素作为频繁 1 项集 L 1 ；扫描数据集 D ，获得候选集 C k 的支持度，中出最小支持度 min_sup 的元素作为频繁 k 项集 L k 通过频繁项 k 项集 L k 产生 k+1 项候选集 C k+1 迭代执行步骤（ 2 ）和步骤（ 3 ），知道不能找到 k+1 项候选集传统 Apriori 缺陷：需要多次扫描数据集，每次扫描都会涉及相当规模的逻辑运算 Apriori 的 Mapreduce 并行化随着数据规模的增大，传统并行方案因资源需求过大或因通信消耗过多而变得低效，基于云计算的 MapReduce 编程模型能很好地解决海量信息并行处理的通信问题，同时还具有负载均衡和强大的容错能力。普通 Apriori 的 Mapreduce 并行化思想：首先利用 MapReduce 并行编程模型的键值进行特性对输入的原始数据集进行 Map 分块处理，主进程将这些数据分块分布到 Hadoop 集群中的每台计算机上，然后并行算法对每台计算机上的分块数据进行如下处理：主进程通过分块数据集与原始数据集的对比产生 1 项候选集由 1 项候选集与原始数据集进行对比，可以算出没想事务的支持度，这些支持度与程序中给定的支持度进行对比，得出 1 项频繁项集由 1 项频繁项集产生 2 项频繁项集主次迭代直到产生 k 项候选集， k 项候选集与原始数据集对比，如果存在 k 项候选集，则继续迭代执行，如果不存在，则最终得到 k-1 项候选集由于 MapReduce 的机制，上述过程为每台计算机上的 Map 进程计算出的分块候选集，接下来 MapReduce 编程模型中的 Reduce 进程把每台计算机上的 Map 进程获取的每个分块的 k 项候选集支持数合并获取全局 k 项候选集的支持数，由全集候选集的支持数计算出全集 k 项频繁项集。当一个数据分块的全局 k 项频繁项集计算出以后，每台计算机会启动下一个 Map 进程处理第二个数据分块，这样一次循环，知道架构处理完所有数据分块。基于 Hadoop 平台改进 Apriori 算法有效解决了节点失效和负载均衡问题 Hadoop 集群中，当一台计算机出现故障而停止计算时，这台计算机上的计算任务会被转移到集群中的其他空闲计算机上继续执行未完成的计算任务在 Hadoop 上处理的计算任务无论大小，通过配置文件的修改可以决定每个 Map 数据块的大小，可以做到数据分块数远大于计算节点数，计算资源不会被浪费，做到了负载均衡。 Apriori 算法 MapReduce 并行化改进上述 Apriori 算法的 MapReduce 并行化是在候选项集支持数的统计阶段并行扫描数据库，没遇到一条事务包含候选项集就产生一个 itemset,1 的键 / 值对，在处理海量数据且支持度较低时，算法产生了大量值为 1 的键 / 值对，增加了 mapReduce 系统的负担，影响算法执行效率。改进的 Apriori 算法 MapReduce 化将 Apriori 数据分割的分组思想应用在候选项集的支持数统计阶段，实现候选项集支持数的分组统计。过程如下：采用类似单词计数的过程并行扫描数据库，找出满足最小支持度的 1 －频繁项集 L1 L1 通过自身连接产生 2 －候选项集 C2 ，采用候选项集支持数的分组统计算法统计 C2 的支持数，形成 2 －频繁项集 L2; 相同步骤， L2 产生 L3 ，如此迭代循环，直到没有新的 k －频繁项集产生．步骤 1) 可以定义 Combiner 方法，提升 Job 的速度 ; 步骤 2) 的候选项集支持数的分组统计不适合定义 Combiner 方法，因为无法定义一个与 Map 输出类型一样的 Combiner 函数．候选项集支持数的分组统计步骤如下 : 将原数据库划分为 n 组，使各组数据足够载入内存运行，并分别统计候选项集在各组数据中的支持数，称为候选项集的局部支持数 ; 合并候选项集在各组数据中的支持数，形成最后候选项集的全局支持数．以下是候选项集在各组数据中的支持数统计伪码，其中 count%N 标识事务所分配的组 id 算法：候选项集在各组数据中的支持数统计输入 : 数据库，分组数 N ， k －候选项集输出 : 局部的 k －候选项集支持数 count 0; Map( key1= unused ， value1 = transaction) count ++; output(key2 = count%N ， value2 = transaction) ; Setup( ) candidatesetlist 读取 k －候选项目集 ; Reduce(key2 = id ， iterable( value2) = iterable( transaction) ) transactionListiterable( transaction) ; // 读取被分配到本组的事务 foreachitemsetincandidatesetlist do output(key3 = itemset ， value3 = supp_count_local( itemset) ) ; end 基于候选集产生的关联规则挖掘，在海量数据且支持度较低时，所产生的 ( k － 1) －频繁项目集数是相当大的．因此，有必要实现候选项集生成的 MapReduce 并行策略．由于 k －候选项集是由前 k － 2 项相同的两个 ( k － 1) －频繁项集的连接产生的，根据 MapReduce 模型，可以将 ( k － 1) －频繁项集的前 k － 2 项作为键最后一项作为值，然后再作为 Map 的输出．键相同的就规约到同一个 reduce 中，这样就可以很容易地处理前 k － 2 项相同的两个 ( k － 1) －频繁项集的连接操作．例如假设 Map 的输入是以下 5 个 3 －频繁项集 : ＜ 1 ， 2 ， 3 ＞，＜ 1 ， 2 ， 4 ＞，＜ 1 ， 2 ， 5 ＞，＜ 1 ， 3 ， 4 ＞，＜ 1 ， 3 ， 5 ＞于是 Map 输出为 : ＜＜ 1 ， 2 ＞， 3 ＞，＜＜ 1 ， 2 ＞， 4 ＞，＜＜ 1 ， 2 ＞， 5 ＞，＜＜ 1 ， 3 ＞， 4 ＞，＜＜ 1 ， 3 ＞， 5 ＞ ; MapReduce 系统经过排序分组后，结果为 : ＜＜ 1 ， 2 ＞，［ 3 ， 4 ， 5 ］＞，＜＜ 1 ， 3 ＞，［ 4 ， 5 ］＞ ; 作为 Reduce 的输入，假定 ( k － 1) －频繁项集所产生的 k －候选项集均已满足频繁项目集的性质，则 Reduce 最后的输出为 : ＜ 1 ， 2 ， 3 ， 4 ＞，＜ 1 ， 2 ， 3 ， 5 ＞，＜ 1 ， 2 ， 4 ， 5 ＞，＜ 1 ， 3 ， 4 ， 5 ＞算法：根据（ k-1 ） - 项频繁项集产生 k- 候选项集输入 : ( k － 1) －频繁项集．输出 : k －候选项集． Setup( ) hashtable 读取 ( k － 1) －频繁项目集 ; Map( key1 =frequent( k － 1) _itemset ， value1 = support_count) p = frequent( k － 1) _itemset; output( key2 = (p ［ 0 ］， p ［ 1 ］，， p ［ k － 3 ］ ) ， value2 = p ［ k － 2 ］ ) ; Reduce( key2 = (p ［ 0 ］， p ［ 1 ］，， p ［ k － 3 ］ ) ， iterable( value2) = iterable( value2) ) item ［］ iterable(value2) ; sort( item) ; for i : 0 item ． lengthdo for j : i +1item ． lengthdo itemset = ( p ［ 0 ］， p ［ 1 ］，， p ［ k － 3 ］， item ［ i ］， item ［ j ］ ) ; if all ( k － 1) － subset ofitemset inhashtablethen //itemset 的所有 k － 1 项子集都是频繁集 output( key3 =itemset ， value3 =0) ; end end end 参考文献：博文 http://blog.csdn.net/lizhengnanhua/article/details/9061887 论文：基于迭代式MapReduce的Apriori算法设计与实现章志刚基于MapReduce并行的Apriori算法改进研究黄立勤基于支持度矩阵的关联规则挖掘算法在公安情报分析中的应用李为; 个人分类: 读书笔记|8379 次阅读|0 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: apriori

相关帖子

相关日志

关闭安全验证