搜索
1目录第一章绪论.............................................................................21.1研究背景和意义............................................................21.2本文主要内容................................................................3第二章频繁项集.....................................................................42.1频繁项集概述................................................................42.2频繁项集名词解析........................................................42.3频繁项集分析指标........................................................4第三章A-Priori算法................................................................63.1概述...............................................................................63.2Apriori核心算法过程....................................................7第四章PCY算法......................................................................9第五章A-Priori算法的java实现..........................................10第六章Hadoop核心.............................................................126.1HDFS.............................................................................126.1.1HDFS概述............................................................126.1.2NameNode和SecondNameNode........................136.2MapReduce..................................................................15第七章基于MapReduce的A-Priori算法实现..................172第一章绪论1.1研究背景和意义购物篮模型的最早应用源于真实购物篮的分析，也就是说，超时和连锁商店都会记录每个结账的购物篮的内容、这里的“项”指的是商店出售的不同商店，而“购物篮”指的是单个购物篮中所装的项集，通过发现频繁项集，零售商可以知道哪些商品通常会被顾客购买，那些共同购买的频度远高于各自独立购买所预期的频度的项对或项集。频繁项集分析的应用并不仅限于购物篮数据，同样的模型可以用于挖掘很多其他类型的数据。例如：（1）关联概念这里的项是词，购物篮是文档。文档中的所有词就构成了对应购物篮中的项，如果要寻找多篇文章中共同出现的词汇集合，那么这些集合大都被高频常见词所占据，比如，我们想要寻找猫和狗的网页摘要，但是停用词“and”和“a”却占据了频繁项集中的主要比例，如果忽略所有的停用词，那么我们希望在高频次对中发现某些能够代表联合概念的一部分词对。（2）文档抄袭这里的项是文档，购物篮是句子。一篇文档中，如果包含某个句子，则任务该句子对应的购物篮中包含文档对应的项。本应用中，寻找那些在多个购物篮中共同出现的项对，如果发现这项的项对，也就是两篇文档有很多相同的句子，实际当中，设置一到两个句子相同都是抄袭发生的有力证据。（3）生态标志物这里的项包括两种类型，一种是诸如基金或血3蛋白之类的生物标志物，另一类是痢疾，而购物篮是某个病人的数据集，包括他的基因组合血生化分析数据，以及他的病史信息。频繁项集有某个疾病和一个或多个生物标志物构成，它们组合在一起给出的疾病是一个检测建议。1.2本文主要内容本文对频繁项集的基本概念分析指标进行了解释说明，详细介绍了频繁项集中的A-Priori算法，PCY算法，并通过JAVA对A-Priori算法进行了实现。现在正处于大数据时代，候选项，频繁项等数以百万计，目前的单个计算机来计算频繁项集耗费时间较大，故在文章的最后引入的Hadoop的HDFS和MapReduce技术，对A-Priori进行了分布式的实现，大大的减少的计算时间。4第二章频繁项集2.1频繁项集概述频繁项集最经典和常用的应用就是超市的购物篮分析。每个购物篮里有很多商品，每个商品都是一项元素，每个购物篮都是一个集合，所有购物篮就形成了一个系列集合。分析哪些商品经常一起频繁出现在购物篮内，即找到频繁项集，然后，再分析其他商品与频繁项集的关系，即关联规则。2.2频繁项集名词解析频繁项：在多个集合中，频繁出现的元素/项，就是频繁项频繁项集：有一系列集合，这些集合有些相同的元素，集合中同时出现频率高的元素形成一个子集，满足一定阈值条件，就是频繁项集。极大频繁项集：元素个数最多的频繁项集合，即其任何超集都是非频繁项集。k项集：k项元素组成的一个集合2.3频繁项集分析指标支持度：包含频繁项集F的集合的数目。可信度：频繁项F与某项j的并集（即FU{j}）的支持度与频繁项集F的支持度的比值。5兴趣度：FU{j}可信度与包含{j}的集合比率之间的差值。若兴趣度很高，则频繁项集F会促进j的存在，若兴趣度为负值，且频繁项集会抑制j的存在；若兴趣度为0，则频繁项集对j无太大影响。6第三章A-Priori算法3.1概述目前暂时只集中关注频繁项对的发现。假如我们都有足够的内存用于所有项对计数，那么通过单便扫描读取购物篮文件就很简单。对于每个购物篮，我们使用一个双重循环就可以生成所有的项对，没生成一个相对，就给对应的计数器加一，最后检查所有项对的技术结果并找出那些超过支持度阀值S的项对，这就是频繁项对。然而，当项对的数目太多而无法再内存中对所有的项对技术时，上述的方法就不行了，A-Priori算法被设计成能够减少必须计数的项对数目，代价是要对数据做两便遍而不是一遍扫描。Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。73.2Apriori核心算法过程1．A-priori算法的第一遍扫描第一次扫描中，要建立两张表。如有必要，第一章表要将项的名称转换为1到n之间的整数，另一张表则是一个计数数组，第i个数组元素是上述第i个项的出现次数。这些项的计数值的初始值是0.在读购物篮时，检查购物篮中的每个项并将其名称转换为一个整数，然后，将刚整数作为计数数组的下表找到对应的数组元素，最后对该数组加12．A-Priori算法两遍扫描之间的处理第一遍扫描之后，检查所有项的计数值，以确定哪些项构成单元素频繁项集，对于A-Priori算法的第二遍扫描，只给频繁项重新编号，编号的范围是1到m，此时的表格是一个下表为1到n的数组，8如果第i项不频繁，则对于的第i个数组元素为0.否则为1到m之间的一个唯一整数。3．A-Priori算法的第二遍扫描第二遍扫描中，对两个频繁项组成的所有项对计数。除非一个相对中的两个项都频繁，否则这个项对也不可能是频繁的。第二遍扫描的技术细节包括，对每个购物篮，在频繁项集表中检查哪些项是频繁的，通过一个双重循环生成所有的频繁项对，对每个频繁项对，在存储计数值的数据结构中对应的计数值加1.最后，在第二遍扫描结束时，检查计数值结构以确定哪些项对是频繁项对。9第四章PCY算法第一次扫描结束后，每个桶中都有一个计数值，记录所有哈希到该桶中的项对的数目值和。如果某个桶中的计数值不低于支持度阀值s，那么该桶称为频繁桶，对于哈希到某个频繁桶中的项对，可以假设其为频繁项对，但是如果某个桶中的计数值小于S，那么可以确定哈希到该桶内的项对都是不频繁的，即使它由两个频繁项构成，这个事实对第二遍扫描很有帮助。PCY两次扫描之间，哈希表被概括表示成一个位图，其中每一位表示一个桶。位为1表示对于的桶是频繁的，而0表示不频繁。因此每32位表示的整数替换成1位。如果大部分桶都不频繁，那么可以预期第二遍扫描中所要计算的项对数目会远小于所以频繁项组成的项对数目。所以，在第二遍扫描中，PCY可以在处理某些数据集时避免内存抖动。10第五章A-Priori算法的java实现具体代码见附录下面是一个实例分析以及在JAVA程序中的测试结果加入存在5个购物篮，购物篮的内容如下所示，支持度为3.下面是A-Priori的分析过程下面是对该实例在JAVA中运行结果显示1112第六章Hadoop核心6.1HDFSHadoop分布式文件系统(HDFS)被设计成适合运行在通用硬件(commodityhardware)上的分布式文件系统。6.1.1HDFS概述HDFS:分布式文件系统，海量数据的存储。高容错，可以部署在廉价的机器上，提供高吞吐量的数据访问，适合那些需要处理海量数据集的应用程序。支持以流的形式访问文件系统中的数据。HDFS主要特性：支持超大文件；检测和快速应对硬件故障；流式数据访问；简化的一致性模型；不适用下面特性：低延迟数据访问；大量小文件；多用户写入文件，修改文件；13名字节点是分布式系统的管理者，负责管理文件系统命名空间，集群配置和数据块复制;数据节点是文件存储的基本单元，以数据块的形式保存了HDFS中文件的内容和数据块的数据校验信息;数据块：块的大小代表着系统读写操作的最小单位。对于用户来说是透明的。6.1.2NameNode和SecondNameNodeNameNode是HDFS主从结构中主节点上运行的主要进程，指导主从结构中的从节点，数据节点执行底层的IO任务。NameNode维护这整个文件系统的目录树，文件/目录的元信息和文件的数据块索引，即每个文件的数据块列表。这些信息以两种形式存储在本地文件系统中，一种是命名空间镜像（FileSystemImage文件系统镜像），另一种是命名空间镜像的编辑日志（Editlog）14命名空间镜像保存着某一时刻的目录树，元信息和数据库索引等信息，后续对这些信息的修改，保存在编辑日志中。通过NameNode，客户端可以了解到数据块所在的数据节点信息。这些信息不保存在上面所述的文件系统中，NameNode每次启动，都会动态的重建这些信息，这些信息构成了名字节点的第二类关系。运行时客户端通过名字节点获得上述信息，然后和数据节点进行数据交互，读写文件。名字节点还能够获取HDFS整体运行状态的一些信息，如系统的可用空间，已经使用的空间，各数据节点的当前状态。第二名字节点用于定期合并命名空间镜像和镜像编辑日志。每个集群都有一个第二名字节点，在大规模的部署条件下，一般第二名字节点也独占一台服务器。第二名字节点和名字节点的区别是它不接收和记录HDFS的任何实时变化，只是根据集群配置的时间间隔，不停的获取HDFS某一个时间点的命名空间镜像和镜像的编辑日志，合并成一个新的命名空间镜像，这个新的命名空间镜像就会上传到名字节点，替换原来的命名空间镜像，并情况编辑日志。在数据节点上，HDFS的数据块，以linux文件系统上的普通文件进行保存。客户端进行文件操作