文档介绍：目录
第一章绪论 1
1
2
第二章频繁项集 3
3
3
4
第三章 A-Priori算法 5
概述 5
Apriori核心算法过程 6
第四章 PCY算法 8
第五章 A-Priori算法的java实现 9
第六章 Hadoop核心 11
HDFS 11
HDFS概述 11
NameNode和SecondNameNode 12
MapReduce 14
第七章基于MapReduce的A-Priori算法实现 16
第一章绪论
购物篮模型的最早应用源于真实购物篮的分析,也就是说,超时和连锁商店都会记录每个结账的购物篮的内容、这里的“项”指的是商店出售的不同商店,而“购物篮”指的是单个购物篮中所装的项集,通过发现频繁项集,零售商可以知道哪些商品通常会被顾客购买,那些共同购买的频度远高于各自独立购买所预期的频度的项对或项集。
频繁项集分析的应用并不仅限于购物篮数据,同样的模型可以用于挖掘很多其他类型的数据。例如:
(1) 关联概念这里的项是词,购物篮是文档。文档中的所有词就构成了对应购物篮中的项,如果要寻找多篇文章中共同出现的词汇集合,那么这些集合大都被高频常见词所占据,比如,我们想要寻找猫和狗的网页摘要,但是停用词“and”和“a”却占据了频繁项集中的主要比例,如果忽略所有的停用词,那么我们希望在高频次对中发现某些能够代表联合概念的一部分词对。
(2) 文档抄袭这里的项是文档,购物篮是句子。一篇文档中,如果包含某个句子,则任务该句子对应的购物篮中包含文档对应的项。本应用中,寻找那些在多个购物篮中共同出现的项对,如果发现这项的项对,也就是两篇文档有很多相同的句子,实际当中,设置一到两个句子相同都是抄袭发生的有力证据。
(3) 生态标志物这里的项包括两种类型,一种是诸如基金或血蛋白之类的生物标志物,另一类是痢疾,而购物篮是某个病人的数据集,包括他的基因组合血生化分析数据,以及他的病史信息。频繁项集有某个疾病和一个或多个生物标志物构成,它们组合在一起给出的疾病是一个检测建议。
本文对频繁项集的基本概念分析指标进行了解释说明,详细介绍了频繁项集中的A-Priori算法,PCY算法,并通过JAVA对A-Priori算法进行了实现。现在正处于大数据时代,候选项,频繁项等数以百万计,目前的单个计算机来计算频繁项集耗费时间较大,故在文章的最后引入的Hadoop的HDFS和MapReduce技术,对A-Priori进行了分布式的实现,大大的减少的计算时间。
第二章频繁项集
频繁项集最经典和常用的应用就是超市的购物篮分析。每个购物篮里有很多商品,每个商品都是一项元素,每个购物篮都是一个集合,所有购物篮就形成了一个系列集合。
分析哪些商品经常一起频繁出现在购物篮内,即找到频繁项集,然后,再分析其他商品与频繁项集的关系,即关联规则。
频繁项:在多个集合中,频繁出现的元素/项,就是频繁项
频繁项集:有一系列集合,这些集合有些相同的元素,集合中同时出现频率高的元素形成一个子集,满足一定阈值条件,就是频繁项集。
极大频繁项集:元素个数最多的频繁项集合,即其任何超集都是非频繁项集。
k项集:k项元素组成的一个集合
支持度:包含频繁项集F的集合的数目。
可信度:频繁项F与某项j的并集(即F U { j })的支持度与频繁项集F的支持度的比值。
兴趣度:F U { j } 可信度与包含{ j }的集合比率之间的差值。若兴趣度很高,则频繁项集F会促进 j 的存在, 若兴趣度为负值,且频繁项集会抑制 j 的存在;若兴趣度为0,则频繁项集对 j 无太大影响。
第三章 A-Priori算法
概述
目前暂时只集中关注频繁项对的发现。假如我们都有足够的内存用于所有项对计数,那么通过单便扫描读取购物篮文件就很简单。对于每个购物篮,我们使用一个双重循环就可以生成所有的项对,没生成一个相对,就给对应的计数器加一,最后检查所有项对的技术结果并找出那些超过支持度阀值S的项对,这就是频繁项对。
然而,当项对的数目太多而无法再内存中对所有的项对技术时,上述的方法就不行了,A-Priori算法被设计成能够减少必须计数的项对数目,代价是要对数据做两便遍而不是一遍扫描。
Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。