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