1006大设计翻译版

AprioriFP-Growth两大分支。KK个最大结果挖掘。目前来说，在每一领域了其它几个算法，开创性的提出了并行化挖掘前K个结果的大数据频繁模式挖掘算法。化，使算法更好的适应大数据环境。具体的大数据环境采用了Hadoop框架，编码实现按照Hadoop编程实现，可以在Hadoop集群中分布式运行。本算法体现了解决大数据算法可以很好的解决大数据下挖掘K个结果的问题。：数据挖掘，频繁模式，大数据，并行化，优 选题的背景与意 课题来 研究背 国内外研究现 研究目 组织结 相关技术介 MapReduce介 HDFS介 Hadoop作业管 关联规则相关算 Apriori算 其它相关算 大数据平台下的TOP-K算法设 算法简要介 算法关键步骤详 取 分 并行化挖掘频繁闭合模 全局闭合检 大数据平台下TOP-K算法实 全局闭合检 实 环境搭 实验环 实验目 实验过 实验结 结 致 参考文 选题的背景与意3个步骤。数据准备包括了原始数据表述、提取原始数据特性、原始相关技术介HadoopHadoop[1]是一套成分布式系统架构，它以MapReduce计算模型和Hadoop分布式Hadoop平台可以轻松组织计算机资源，从而搭建自己的分布式计算机平高可靠性。Hadoop高扩展性。HadoopMapReduceMapReduce是Hadoop的基本计算模型，为大数据并行化计算提供了一种可能。MapReduceMapReduceMap阶段中，输入按照ReduceReduce2.1Map-Reduce框架示意词出现的次数。一段文章内容为：Ilovetheword,oword,oword。此时Map的任务是读入文章内容然后按照标点符号或者空格将文章分割开，最后输出内容为：<I阶段，Reduce接收到的内容是<I1>,<love1>,<the1>,<word1,1,1>,<o1,1>，具有相同得出每个单词出现的频率，Reduce的输出为<I1>,<love1>,<the1>,<word3>,<o2>。一轮MapReduce作业就成功完成了，每个单词出现的次数就可以统计出来了。经过MapReduce任务分解，本来单词排序的任务需要在单机完成，但分解任务以后，该任务MapKey输出到特定的机器，那么可以将输入内容拆开做Map工作，然后再在不同的特定的机器上进行Reduce任务。HDFSHDFS（Hadoopdistributedfilesystem）Hadoop数据模式为处理超大文件的需求而研发，可以运行在廉价的服务器组成的集群上。HDFS的主要特点如下：处理超大文件。超大文件通常是指数百MB、数百TB甚至更大的文件。流式访同节点。在HDFS中整个数据集比一条数据记录更加高效。可以运行在廉价的硬件集群，而无需非常昂贵的高可用性机器，廉价意味无法高效大量小文件。HDFS中需要有一台机器（NameNode）管理文件系统的元数据，每一个文件的大小、位置和索引都需要在这台机器上注册，如果小文件过多，会对NameNode造成很大的压力。以上介绍了HDFS的优缺点，下面介绍一下HDFS的体系结构。HDFS最基本的单位是块（Bolck，HDFS会为文件系统的所有块进行，这样做的好处是可以迅速定一个文件的备份副本数，很容易通过块来设定。HDFS中有两类节点，NameNode和DataNode，分别承担Worder和Master的任务。NameNode是文件系统的管理者，这个 树以及文件索引。外界读写HDFS都需要先和NameNode进行交互以获得元数据信息，然后通过元数据信息和相关DataNode进行交互，对用户来将需要配置的参数配置好，这些配置参数包括：程序代码、Map接口和Reduce接口配点分为两类：NameNodeDataNode，NameNode担任Master角色，DataNode担任Slave角色。客户端的作业调用submitJob()方法之后，会将该作业交给JobTracker，TaskTracker，TaskTracker取到作业后就会运行这个作业。（HeatBeatHadoopNameNode，集群存在单点故障的风险，HadoopNameNodeNameNode失效，所有的作业将不可恢复，需要重新运行。由于DataNode有很多，每个DataNodeDataNode存在故障，这部分作业可以在其它节点HDFSDataNode需要的文件在其它节点有备份，不会存在文件丢失的问题，所以DataNode失效是可以自动恢复任务的。Apriori[2]k项支持度的项，找1项集的集合。L1，然L1找出频2项集L2，使用L2找出L3，如此递归迭代，直到不能再找到频繁k项集。找出每个频繁项集Kk-1Lk-1k项集的集合，记为Ck。Lk-1的连接方式是Lk-1中的候选项集除最后一项不同外，前剪枝步：Ck是Lk-1的超集，即Ck中的有些项集是不频繁的，但是所有频繁的k项集都包含在Ck中。任何非频繁的k-1项集都不是频繁k项集的子集。所以如k项集的任k-1k-1k项下面举例说明Apriori算法。2.1项集C1。表2.21-候选项集233132.31-23332.42-121232minSupport的{I1,I2}{I1,I5},2-L22.52.52-2232L23-C33-2子集是不是频繁的，这确定3-候选项集的支持度，表2.63-候选项集C3。2.63-2C3中没有小minSupport的候选项集，所以生3-频繁项集L32.73-频繁项集L3。2.73-2Apriori最大的问题就是多次扫描数据库，导致算法效率低下，现在已经有很多Apriori算法的变形，提高了算法效率，其中一些变形如下：k-1候选项Ck-1生成k-1频繁项Lk-1时，扫描数据库的同时生成事务集中所有k-1项集，并且将这些k-1项集散列到不同的桶k项集的事务不可能包含任何频繁k+1项集这种事务在其后的考虑时，可以加上标记或删除，因为产生j（>k）的数据库扫描是事集划为n个非的分区，对每个分区找出局部频繁项集，局部频繁项集可能是也可能不是整个数据库D的频繁项集，但是D的任何频繁项集D的候选项集。Apriori算法解决了关联规则挖掘从无到有的问题，但是通过前面的介绍，无论是基本的Apriori算法还是经过优化的算法都不能解决以下两个问题：产生大量候选集和重复扫描数据库的问题。如果有104个频繁1项集，则Apriori算产生多达107个候选223项集又是一个天文数字，如此多的候选项集是不可接受Tree，该树著，本来在磁盘中的数据可以压缩在内存中，所以加快了搜索速度。这个算法上解Apriori算法带来的两个问题。在介FP-Growth[3]FP-Tree这个基本的数据结构。FP-Tree之前需要先扫描一次数据库，找出所有频繁1-项集，然后按照频繁1-LFP-Tree。首先构建FP-Tree的根节点null标记，然后进行第二次的数据库扫描，逐条读出数据库中的事务，读出的事务先按照L的顺序进行排序，将排好序的事务FP-Tree中，规则如下：顺序遍历排好序的事务集，同时从FP-Tree的根节点，如果此时FP-Tree的节点有孩子FP-Tree的孩否则建立新的FP-Tree节点，将节点FP-Tree中，作为当前遍历节点的孩子，继续遍历当前事务的下一项。下面举例说明。表2.8为原始事务集：2.8f,a,c,d,e,g,i,m,a,b,c,f,l,m,b,f,h,j,b,c,k,s,a,f,c,d,e,l,p,m,{a:3b:3c:4d:2e:2f:4g:1h:1j:1k:1l:1m:3n:1o:2p:3}1{a:3b:3c:4f:4m:3p:3}1{f:4c:4a:3b:3m:3p:3}，以后从事务集中出的事务都按照排序后的1频繁项集的顺序排序，将原始数据集排序后删除不满足的项，得到表9.2所示的结果：2.9f,c,a,m,f,c,a,b,f,c,b,f,c,a,m,将第二条事务FP-Tree中，遍历到f时，发现根节点下有孩子f，然后将f的点，将新建立的节点a中，作为a的孩子。新建节点后，事务中这个节点对应的项以后的项就不需要查找了，直接新建节点即可。b和m后的FP-Tree如图2.4条事务后的FP-Tree如图2.5所示。图 通过两遍扫描原始事务集，建立好这棵FP-Tree之后，就可以在FP-TreeFP-Growth算法进行关联规则挖掘了，FP-Tree的挖掘过程如下：由长度为1的频繁模式开并且递归地在该树上进行挖掘，这是最基本的FP-Growth算法的思想，算法的具体实现在这里就不举例了。FP-growth算法开辟了有效挖掘频繁模式的新途径。然而，它的时间和空间效率还不足够高，仍需进一步改进。FP-growth算法的主要问题是：在挖掘频繁模式时，它需要递归地生成条件FP-树，并且每产生一个频繁模式就要生成一个条件动态地生成和释放数以十万计的条件FP-Tree，将耗费大量时间和空间。此外，FP-Tree和条件FP-Tree需要自顶向下生成，而频繁模式的挖掘需要自底向上处理。由于递归地FP-Tree的结点中就需要的指针，从而需要更大的内存空间来FP-Tree和条件FP-Tree。FP-growth算法首次提出了FP-Tree结构，为很多频繁项集挖掘算法提供了基础。FP-growth算法进行改进，主要考虑改进FP-Tree的结构，以节省时间效率和空FP-Growth挖掘的效率已经非常高，但是FP-Growth挖掘出的频繁模式太多，很多繁项集的基础上人们也对其紧凑形式频繁闭项集进行了研究。Pasquier等人提出了频繁A-Close算法们的闭包——也就是所有的频繁闭合项集也随之确定。A-Close算法能够减少搜索空间，Closet算法数据库，把对事务数据库的挖掘转化为对FP-Tree的挖掘，通过深度优先搜索挖掘频繁闭合模式。在挖掘频繁闭合模式的过程中需要反复递归构造新的条件FP-Tree，占用了后来又有基于Closet算法优化后的Closet+[6][7]算法。D-MINER算法是一种在布尔上下文中的挖掘技术，适用于数据稠密且高度相关的微阵列数据集。一般的闭项集挖掘算法是利用Galois连接特性在较小的维度上计算闭集，在另一个维度上得到闭集。D-MINER算法对于数据稠密且数据维度均较大时的双Top-KFP-growth算法Apriori性质的基础上使用最小支置了一个阈值——边界支持度，减少了FP-Tree生成模式的数目，并对挖掘出的频繁模式按照支持度进行排序，最后输出最频繁的K个模式。大数据平台下Top-k算法设大数据平台，如Apriori、FCP都有在大数据平台下的版本。但是Top-k相关算法目前还算法借鉴了并行化频繁模式挖掘算法PFP[10]（ParallelFrequencyPattern）Closet+算法FP-Tree可以高效地压缩事务集，但当事务集非常巨大的时候，压缩过的事务集也难以存放在内存中；无法在内存中构建FP-Tree，那就意味着所有基于FP-Tree的部分，分别对每一个部分构建FP-Tree，变小的数据集总是可以小到在单机内存中的，然后分别对每个部分FP-Tree进行挖掘，最后将结果整合在一起，形成最终结果。PFP给出了一个在大数据平台下挖掘频繁模式的解决方案，该算法主要分为以下五PFP的原始事务集切割没有分别，只是为了方便并行化计并行化计算支持度：所有基于FP-Tree的算法都必须知道1频繁项集，并且要低来进行，这样可以保证尽可能早的挖掘到支持度最大的K个结果。由于无法PFP中使用的分组方法。对于新的事务集，计1频繁项集，按照支持度排序，将项集中的项分组，标记每个1频繁项集中的项已经确定了组号,1频繁项集为：{f:1c:1a:1b:2K个，说明已经符合要求，立即停止算法并且输出结果，否则算法跳至步骤4，继续进行。Top-kK个频繁闭合模式；也有可能最终无法得到K个频繁闭合模式，这种情况表明原始数据集中就没有K个频繁闭合模式这么多，无论使用何种算法都不可能找到K个频繁闭合模式。同样地使用上文已经使用过的数据，表3.1为原始事务集。3.1f,a,c,d,e,g,i,m,a,b,c,f,l,m,b,f,h,j,b,c,k,s,a,f,c,d,e,l,p,m,设最小支持minSupport=2，最终需要的结果K=51频繁项集：L={f:4c:4a:3b:3m:3p:3d:2e:2}设取样的额度为m=3，即每次从1频繁项集中向后顺延取三个项。第一次取样，相关项集应该为{fca}，但前面讲过，每次取样相关项集中最后一个项一定要取在支持度aab1L发现，ab的支持度是相同abmp添加进这次的相关项集中。此时的相关项集变为{fcabmp}p1频繁项集，发现项p的后一项为项d，项d的支持度低于项p，所以项p处于支持度的T1=fa,cd,e,g,i,m,p}，本次的相关项集为{fcabmp}，本次相关项集的最后pT1与{fcabmp}做交集，取到的结果为{fcamp}，将这条新的事务加入3.2f,c,a,m,f,c,a,b,f,c,b,f,c,a,m,一次取样的剩余集合中顺延取m个，即从剩余的项中取出三个支持度最高的项。由于1频{de}T1={facd,eg,i,m,p}T1与本次相关项集的交集为不为空，此时1频繁项集的第一项f到本次相关项集最后一项e组成的项集为{fcabmpde}T1与该项集的交集为{fcampde}。继续遍历事务集T2={a,b,c,f,l,m,o}T2与本次相关项集的交集为空，所T2，继续遍历。T2T2中如果包含频繁项集，那么就会在上次取样的计算结果中计算出来，这一次取样就没有必要计算了。新生成的事务集如表3.3所示。3.3f,c,a,m,p,d,f,c,a,m,p,d,K个结果，后续的讲解仍回到第一次取样结原始事务集本身就具有独立性那么分组过程会简单许多，比如说包含{fcab}这些项的事务和包含{mpde}这些项的事务是没有重合的，那么事务集本身就具有独立性。这两fmm的事务集都不包含f。groupSum=21频繁项集并且按照支持度排序，由于是第一次取样，所以不需要重新计算1频繁项集，只需要取出全局的1频1频繁项集为f:4c:4a:3b:3m:3p:3}，下面为1频繁项集中的每个项分配组号。本文算法采用的PFP算法的分组策略，保证不同组3.4f1c1a1b2m2p2T1f,c,a,m,p}T1中包含1组的项有{f,c,a}，则向1组发送项集{f,c,a}；T12组的项有{m,p}2组发送{f,ca,m,p}，后面的组要包含前面组的项，项第2组发送项集的时候，要将包含的第1组中的项一并发送出去。继续遍T2fcab,m，T21组发送{f,c,a}2组发送{f,cabm}3.5显3.5SendToGroupSendToGroupf,c,a,m,f,c,f,c,a,m,f,c,a,b,f,c,f,c,a,b,f,ff,c,b,cc,b,f,c,a,m,f,c,f,c,a,m,现很好，而且节约内存。这个算法的原型是Closet+算法，在具体实现的时候对Closet+ FP-Growth算法的挖掘方式基本相同。在这里主要介绍Closet+对应稀疏数据的挖掘方法，原始的Closet+的算法是递归的。第一种剪枝优化项合并：如果包含频繁项集X的每个事务都包含项集Y，但不包含Y的任何真X∪Y形成一个闭频并且不必再搜索X但不Y的XY的Support(X)=Support(Y)XX在集合枚举树中的所有后代都不可能Closet+Closet+算法，并且是同时表3.6所示：3.62f,c,a,m,f,c,a,b,f,c,b,f,c,a,m,需要强调的是本组的事务集需要计算1频繁项集并且排序，称排好序的1频繁项集为fList，本组的fList={f:4c:4a:3b:3m:3p:3}。（Headable，找出这些中包含的所有项，计算出每个项的支持度，汇头表中。头表是由浅层次向次逐层遍历，遍历头表中的项的时候建立项到这些中对应节点（prefix开始遍历，遍历过后生成头表如图3.2所示：生成头表后，开始遍历头表，指针首先指向头表中的f，然后根据f的建立新的的FP-Tree如图3.3所示：整个过程是递归的，继续遍历新头表，此时指针指向新头表中的c，以c为根节点建立新头表，生成新头表后FP-Tree如图3.4所示：的支持度，所以新头表的前缀为{fc:3}。此时指针指向新节点的a，开始递归遍历，这里满足剪枝条件的条件一。aXapp为根节点继续遍历，建立新的头表。但是此时，p节点已经是叶FP-Tree已经遍历到了叶节点，没有新的节点可以遍历，仅就本组取样的相关项最后一项是项p，其支持度为3；但是当前取到的前缀的支持度为2，小于集{fcabmpde:2}，说明这条前缀不是全局闭合的，但是如果不进行下次的取样计算，无法得知该结果是否全局闭合。当前的FP-Tree状态如图3.6所示。算法无法向更次遍历，递归过程需要返回。此时针指向节点p，调整指针使指录，分别为{fcamp:2}和{fcam:3}FP-Tree的状态如3.7所示。c，调整指针，指针指向项a，当前FP-Tree状态如图示。下一个步骤是以a为根节点生成新头表，但是这里满足剪枝规则二。如果项a被遍历，新头表的前缀为{fa:3}，目前的结果集中有{fcamp:2}和{fcam:3}两条记录。根据剪枝条件二,把前X，把结果集中的{fcam:3}Y，XY的真子集，那么向项b，b不可以被剪枝，也不可以合并前缀，继续进行。以项b为根节点所有。有结果，所有结果如表3.7所示。3.72f,c,a,m,2f,c,a,3f,2f4c,2c,3c4b3以发现，结果集中包含了两种不同的结果类型：包含本组分组的项的结果和不包含本组 3.82f,c,a,m,2f,c,a,3f,2c,2c,3b3组的结果集。第一组的结果集如表3.9所示：3.91f,c,3f4c43.102f,c,a,m,2f,c,a,3f,2c,2c,3b3的结果R1包含在了同组的结果R2中，那么R1就不是全局闭合，需要舍弃。当同一组FP-Tree的过程有稍许区别。建立FP-Tree的并。这里去Support=3的结果集举例，结果集中Support=3的结果如表3.11所示：f,c,3f,c,a,3c,3b3开始时结果树为空，第一条结果{fca:3}，结果树如图3.9所示第二条结果{fcam:3}3.10支持度为三的这组全局检查结束，从结果树中可以得到三条结果，分别是{fcam:3}{cp:3}{b:3}，这些结果都是全局闭合的结果，在全局结果检查中删去了结果{fca:3}，这条结果不是全局闭合的。全局检查，最后的工作是统计挖掘了多少个结果。大数据平台Top-k算法实MapReduceMap阶段主要工作就是将排好序的1频繁项集按照规定组数进行分组item分组之后，遍历事务数再赘述。Map阶段处理之后，相同分组的新事务集中在一个Reduce中，不同的Reduce对应不同的分组，每个分组仅仅对应一个Reduce，这样就可以在Reduce中进行频繁项集挖掘，由于Reduce是并行运行，从整体上看，这个工作是并行化运行的。Reduce过程中，主要分为FP-Tree和进Closet+两个阶段，首先介绍建立FP-Tree的过程。建立FP-Tree的伪代码为：transactions:Functionroot:foreachtransactionintransactionreturn7.遍历事务集，将每条事务以root为根节点的FP-Tree中，FP-Tree的伪代FunctionInsertFPtree(root,p #FP-Tree的指foreachitemintransactionifiteminp’sthenmodifyp’schildaddchildforp=p’s11.1itempitem没有找到可以继续合并的路径，需要新建节点，将新建的节点加入p的孩子中，然后p指向新建的节点。InsertFPtree函数负责将一条事务这个FP-Tree中，函数没有返回值。FP-Tree就建立完毕。本文选择具体的挖掘算法nodes:itemnodeFunctionheadTable:新的头表，每个item和其对应的节foreachnodeinnodesp:作为指针遍历节点的ptraversalifpinthenaddpinheadTable’snewadditeminaddpinheadTable’s 15.取得item对应FP-Tree中所对应的所有节点，遍历每个节点的，将中所入头表中新建的item中。CreateHeadTable函数建立头表，如果新建头表有内容，说明可以继续向更如果头表中有可遍历的节点，状态入栈，转入状态0；如果头表中没有可遍历的节点，体流程图如图4.2所示：pointer:stack:用来保存前缀、pointerwhilestate1switchstatecase0ifheadTableisthencheckprefixandoutputendcase1foreachiteminheadTableifneedthenifmergeradditemtopointer=pushstate=endcase2ifstackisnullstate=endpopstate=endendifstateis3endendMapReduce中实现的。当所有组都输出了挖掘的结果之果树就得到了对应的结果。这个MapReduce过程不算复杂，在这里简略说明。Reduce阶段相同支持度的结果已经分在同一key的values中，此时遍values，实HadoopMapReduceYarn的配置问题，程序占用内存稍微增加就会导致内存栈溢出问题。完全分布式的Hadoop环境没有调试成功，本实验在单机Hadoop上硬件环境 将编写Java程序导出，导出格式为可运行Jar程序需5个命令行参数，1为数据输入路径，参2为输出3为最小结果长度4为结果的K值，参数5为取样方案。Hadoopjartime命令检测运行时间，统计运行时间。将统计数据制作成表格。实验要求的结果K为100，结果最小长度为3.方案一：0.250.3750.50.6250.750.8751方案二：0.50.750.8751稀疏度：05方案 方案401时间稀疏度：05方案 方案401时间稀疏度：40%方案 方案5141132101稀疏度：40%方案 方案51411321011111 时间400111400111时间结5.15.20.5%的K0.5%的实验结果中可以看到，当item85%100Hadoop本身的限制，Hadoop读Hadoop读写硬盘的时间。从这个实验中也可以看出取5.340%的时候算法效率最高，算法效果最好。在稀从图5.2的方案一图还可以看出，当数据集性增大时，算法运行时间基本保持致导，毕业设计才没有走很多弯路。参考文[1]..Hadoop实战[M].：机械工业,2011.9:54-67,100-103,118-[2].R.Agrawal,R.Srikant.FastAlgorithmsforMiningAssociationRules.In:Procof1994Int’lConfonveryLargeDataBases.Santiago,Chili:VLDBEndowment,1994.487-[3].HanJ.w.,PeiJ．,andYinY.w..MiningFrequentPatternswithoutCandidateGeneration:AFrequent-patternTreeApproach.DataMiningandKnowledgeDiscovery,