频繁项集报告.总结

1、目录第一章绪论21.1 研究背景和意义21.2 本文主要内容3第二章频繁项集42.1 频繁项集概述42.2 频繁项集名词解析42.3 频繁项集分析指标4第三章A-Priori 算法63.1 概述63.2 Apriori 核心算法过程7第四章PCY算法9第五章A-Priori 算法的 java 实现10第六章Hadoop 核心126.1 HDFS12概述12和 SecondNameNode136.2 MapReduce15第七章基于 MapReduce的 A-Priori算法实现171第一章 绪论1.1 研究背景和意义购物篮模型的最早应用源于真实购物篮的分析， 也就是说，超时和连锁商店都会记录每

2、个结账的购物篮的内容、这里的“项”指的是商店出售的不同商店，而“购物篮”指的是单个购物篮中所装的项集，通过发现频繁项集， 零售商可以知道哪些商品通常会被顾客购买， 那些共同购买的频度远高于各自独立购买所预期的频度的项对或项集。频繁项集分析的应用并不仅限于购物篮数据， 同样的模型可以用于挖掘很多其他类型的数据。例如：（1） 关联概念 这里的项是词， 购物篮是文档。 文档中的所有词就构成了对应购物篮中的项， 如果要寻找多篇文章中共同出现的词汇集合，那么这些集合大都被高频常见词所占据，比如，我们想要寻找猫和狗的网页摘要，但是停用词“ and”和“a”却占据了频繁项集中的主要比例，如果忽略所有的停用词

3、， 那么我们希望在高频次对中发现某些能够代表联合概念的一部分词对。（2） 文档抄袭 这里的项是文档，购物篮是句子。一篇文档中，如果包含某个句子， 则任务该句子对应的购物篮中包含文档对应的项。本应用中，寻找那些在多个购物篮中共同出现的项对， 如果发现这项的项对，也就是两篇文档有很多相同的句子，实际当中，设置一到两个句子相同都是抄袭发生的有力证据。（3）生态标志物这里的项包括两种类型， 一种是诸如基金或血2蛋白之类的生物标志物， 另一类是痢疾， 而购物篮是某个病人的数据集，包括他的基因组合血生化分析数据，以及他的病史信息。频繁项集有某个疾病和一个或多个生物标志物构成，它们组合在一起给出的疾病是一个

4、检测建议。1.2 本文主要内容本文对频繁项集的基本概念分析指标进行了解释说明，详细介绍了频繁项集中的A-Priori 算法， PCY算法，并通过JAVA对 A-Priori 算法进行了实现。现在正处于大数据时代，候选项，频繁项等数以百万计，目前的单个计算机来计算频繁项集耗费时间较大，故在文章的最后引入的 Hadoop 的 HDFS和 MapReduce 技术，对 A-Priori 进行了分布式的实现，大大的减少的计算时间。3第二章 频繁项集2.1 频繁项集概述频繁项集最经典和常用的应用就是超市的购物篮分析。每个购物篮里有很多商品，每个商品都是一项元素， 每个购物篮都是一个集合，所有购物篮就形成

5、了一个系列集合。分析哪些商品经常一起频繁出现在购物篮内，即找到频繁项集，然后，再分析其他商品与频繁项集的关系，即关联规则。2.2 频繁项集名词解析频繁项：在多个集合中，频繁出现的元素 / 项，就是频繁项频繁项集：有一系列集合，这些集合有些相同的元素，集合中同时出现频率高的元素形成一个子集，满足一定阈值条件， 就是频繁项集。极大频繁项集： 元素个数最多的频繁项集合， 即其任何超集都是非频繁项集。k 项集： k 项元素组成的一个集合2.3 频繁项集分析指标支持度：包含频繁项集F 的集合的数目。可信度：频繁项F 与某项 j 的并集 （即 FU j ）的支持度与频繁项集 F 的支持度的比值。4兴趣度：

6、 FU j可信度与 包含 j 的集合比率之间的差值。若兴趣度很高，则频繁项集 F 会促进 j的存在，若兴趣度为负值，且频繁项集会抑制j的存在；若兴趣度为0，则频繁项集对 j无太大影响。5第三章 A-Priori算法3.1概述目前暂时只集中关注频繁项对的发现。 假如我们都有足够的内存用于所有项对计数， 那么通过单便扫描读取购物篮文件就很简单。 对于每个购物篮， 我们使用一个双重循环就可以生成所有的项对， 没生成一个相对，就给对应的计数器加一， 最后检查所有项对的技术结果并找出那些超过支持度阀值 S的项对，这就是频繁项对。然而，当项对的数目太多而无法再内存中对所有的项对技术时，上述的方法就不行了，

7、 A-Priori 算法被设计成能够减少必须计数的项对数目，代价是要对数据做两便遍而不是一遍扫描。Apriori 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。 该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。63.2 Apriori核心算法过程1A-priori算法的第一遍扫描第一次扫描中， 要建立两张表。如有必要，第一章表要将项的名称转换为 1 到 n 之间的整数，另一张表则是一个计数数组， 第 i 个数组元素是上述第 i 个项的出现次数。这些项的计数值的初始值是 0.在读购物篮时，检

8、查购物篮中的每个项并将其名称转换为一个整数，然后，将刚整数作为计数数组的下表找到对应的数组元素，最后对该数组加 12A-Priori算法两遍扫描之间的处理第一遍扫描之后， 检查所有项的计数值， 以确定哪些项构成单元素频繁项集，对于 A-Priori 算法的第二遍扫描，只给频繁项重新编号，编号的范围是 1 到 m，此时的表格是一个下表为 1 到 n 的数组，7如果第 i 项不频繁，则对于的第i 个数组元素为 0. 否则为 1 到 m之间的一个唯一整数。3A-Priori算法的第二遍扫描第二遍扫描中， 对两个频繁项组成的所有项对计数。 除非一个相对中的两个项都频繁， 否则这个项对也不可能是频繁的。

9、 第二遍扫描的技术细节包括， 对每个购物篮， 在频繁项集表中检查哪些项是频繁的，通过一个双重循环生成所有的频繁项对，对每个频繁项对，在存储计数值的数据结构中对应的计数值加 1.最后，在第二遍扫描结束时， 检查计数值结构以确定哪些项对是频繁项对。8第四章 PCY算法第一次扫描结束后，每个桶中都有一个计数值，记录所有哈希到该桶中的项对的数目值和。 如果某个桶中的计数值不低于支持度阀值 s，那么该桶称为频繁桶，对于哈希到某个频繁桶中的项对，可以假设其为频繁项对，但是如果某个桶中的计数值小于S，那么可以确定哈希到该桶内的项对都是不频繁的， 即使它由两个频繁项构成， 这个事实对第二遍扫描很有帮助。PCY

10、两次扫描之间，哈希表被概括表示成一个位图，其中每一位表示一个桶。位为 1 表示对于的桶是频繁的，而 0 表示不频繁。因此每 32 位表示的整数替换成 1 位。如果大部分桶都不频繁，那么可以预期第二遍扫描中所要计算的项对数目会远小于所以频繁项组成的项对数目。所以，在第二遍扫描中，PCY可以在处理某些数据集时避免内存抖动。9第五章 A-Priori算法的 java 实现具体代码见附录下面是一个实例分析以及在JAVA程序中的测试结果加入存在 5 个购物篮，购物篮的内容如下所示，支持度为3.下面是 A-Priori的分析过程下面是对该实例在JAVA中运行结果显示1011第六章 Hadoop核心6.1

11、HDFSHadoop 分布式文件系统(HDFS)被设计成适合运行在通用硬件(commodity hardware)上的分布式文件系统。概述HDFS:分布式文件系统，海量数据的存储。高容错，可以部署在廉价的机器上， 提供高吞吐量的数据访问， 适合那些需要处理海量数据集的应用程序。支持以流的形式访问文件系统中的数据。HDFS主要特性：支持超大文件；检测和快速应对硬件故障；流式数据访问；简化的一致性模型；不适用下面特性：低延迟数据访问；大量小文件；多用户写入文件，修改文件；12名字节点是分布式系统的管理者，负责管理文件系统命名空间，集群配置和数据块复制; 数据节点是文件存储的基本单元，以数据块的形式

12、保存了 HDFS中文件的内容和数据块的数据校验信息; 数据块：块的大小代表着系统读写操作的最小单位。对于用户来说是透明的。和 SecondNameNodeNameNode是 HDFS主从结构中主节点上运行的主要进程，指导主从结构中的从节点，数据节点执行底层的IO 任务。NameNode维护这整个文件系统的目录树，文件/ 目录的元信息和文件的数据块索引， 即每个文件的数据块列表。 这些信息以两种形式存储在本地文件系统中，一种是命名空间镜像（ File SystemImage 文件系统镜像），另一种是命名空间镜像的编辑日志（Editlog ）13命名空间镜像保存着某一时刻的目录树， 元信息和数据库

13、索引等信息，后续对这些信息的修改，保存在编辑日志中。通过 NameNode，客户端可以了解到数据块所在的数据节点信息。这些信息不保存在上面所述的文件系统中， NameNode每次启动，都会动态的重建这些信息， 这些信息构成了名字节点的第二类关系。 运行时客户端通过名字节点获得上述信息， 然后和数据节点进行数据交互，读写文件。 名字节点还能够获取 HDFS整体运行状态的一些信息，如系统的可用空间， 已经使用的空间，各数据节点的当前状态。第二名字节点用于定期合并命名空间镜像和镜像编辑日志。 每个集群都有一个第二名字节点， 在大规模的部署条件下， 一般第二名字节点也独占一台服务器。第二名字节点和名字

14、节点的区别是它不接收和记录HDFS的任何实时变化，只是根据集群配置的时间间隔，不停的获取HDFS某一个时间点的命名空间镜像和镜像 的编辑日志，合并成一个新的命名空间镜像，这个新的命名空间镜像就会上传到名字节点， 替换原来的命名空间镜像，并情况编辑日志。在数据节点上， HDFS的数据块，以 linux 文件系统上的普通文件进行保存。客户端进行文件操作时， 先由名字节点告知客户端每个数据块驻留在哪个数据节点， 然后客户端直接与数据节点守护进程进行通信，处理与数据块对应的本地文件， 同时数据节点会和其他的数据节点进行通信，复制数据块，保证数据的冗余性。14数据节点作为从节点，会不断地向名字节点报告，

15、初始化时，每个数据节点将当前存储的数据块告知名字节点，后续数据节点工作过程中，数据节点仍然不断的更新名字节点，为之通过本地修改的相关信息，并接受来自名字节点的指令，创建移动或者删除本地磁盘上的数据块。6.2 MapReduceMapReduce是一种分布式计算模型，由Google 提出，主要用于搜索领域，解决海量数据的计算问题.MR 由两个阶段组成：Map 和Reduce，用户只需要实现map() 和 reduce() 两个函数，即可实现分布式计算，非常简单。这两个函数的形参是key 、value 对，表示函数的输入信息。执行步骤：151. map 任务处理1) 读取输入文件内容，解析成 ke

16、y、value 对。对输入文件的每一行，解析成 key、value 对。每一个键值对调用一次 map函数。2) 写自己的逻辑，对输入的 key 、value 处理，转换成新的 key、value输出。3) 对输出的 key、value 进行分区。4) 对不同分区的数据， 按照 key 进行排序、分组。相同 key 的 value 放到一个集合中。5) ( 可选 ) 分组后的数据进行归约。2.reduce 任务处理1) 对多个 map任务的输出， 按照不同的分区， 通过网络 copy 到不同的 reduce 节点。2) 对多个 map任务的输出进行合并、 排序。写 reduce 函数自己的逻辑，

17、对输入的 key、value 处理，转换成新的 key、value 输出。3) 把 reduce 的输出保存到文件中。16第七章基于 MapReduce的 A-Priori算法实现A-Priori算法， 通过对数据库的多趟扫描来发现所有的频繁项集 ,在海量数据的条件下,对数据库的扫描将会耗费大量的时间和内存。本文充分利用云计算提供的分布式并行计算功能,对A-priori算法加以改进 ,得到新的适用于云计算的频繁项集挖掘方法, 该方法使查找 L k 和 L k+ 1 的过程独立 , 能够提高海量数据挖掘的效率。新方法的基本思想如下 :( 1) 把数据库分成规模相当的 M 个数据子集 , 把数据子

18、集发送到 M个站点;( 2) 每个站点扫描它的数据子集 , 产生一个局部的候选 k 项集的集合 , 记作 Cpk , 每个候选项集的支持度计数为 1;( 3)利用 hash 函数把 M 个站点的 Cpk 中相同的项集和它的支持度计数发送到R 个站点 ;( 4) R个站点中的每个站点把相同项集的计数累加起来,产生最后的实际支持度 ,与最小支持度计数min_sup 比较 ,确定局部频繁 k 项集的集合 L( 5)把 R 个站点的输出合并即产生全局频繁k 项集的集合 L k 。17附录一：package com.cars;importpublicclassApriori privatedoublem

19、insup = 3;/最小支持度privatedoubleminconf= 0.2;/最小置信度/ 注意使用 IdentityHashMap ，否则由于关联规则产生存在键值相同的会出现覆盖privateIdentityHashMapruleMap=new IdentityHashMap();privateStringtransSet= "MONKEY","DONKEY","MAKE" ,"MUCKY","COKIE" ; /事务集/ 可以根据需要从构造函数里传入privateintitemCou

20、nts= 0;/候选 1项目集大小 , 即字母的个数privateTreeSetfrequencySet=new TreeSet40;/频繁项集数组，0:代表 1频繁集 .，TreeSet （）使用元素的自然顺序对元素进行排序privateTreeSetmaxFrequency=new TreeSet();/最大频繁集privateTreeSetcandidate=new TreeSet();privateTreeSetcandidateSet =new TreeSet40;/候选集数组 0:代表 1候选集privateintfrequencyIndex;publicApriori() max

21、Frequency=new TreeSet();itemCounts= counts();/初始化 1候选集的大小 6个/初始化其他两个for( inti = 0; i <itemCounts; i+) frequencySeti =new TreeSet();/ 初始化频繁项集数组candidateSeti =new TreeSet();/ 初始化候选集数组candidateSet0 =candidate; / 1候选集/ 主函数入口publicstaticvoidmain(String args) Apriori ap =new Apriori();ap.run();/ 方法运行pu

22、blicvoidrun() intk = 1;/ 求1频繁集，保存到 frequencySet0中item1_gen();do k+;18canditate_gen(k);frequent_gen(k);while(!is_frequent_empty(k);frequencyIndex= k - 1;print_canditate();maxfrequent_gen();print_maxfrequent();ruleGen();rulePrint();/ 记录每个事务中的元素出现次数publicdoublecount_sup(String x) inttemp = 0;for( inti

23、= 0; i <transSet. length; i+) for( intj = 0; j < x.length(); j+) if( transSeti.indexOf(x.charAt(j) = -1)/ 返回指定字符在此字符串中第一次出现处的索引，如果不作为一个字符串，返回-1break ;elseif(j = (x.length() - 1)temp+;returntemp;/ 统计 1候选集的个数 a,b,c,d,e,f,return值为 6publicintcounts() String temp1 =null;chartemp2 ='a'/ 遍历所有

24、事务集 String 加入集合， set 自动去重了for( inti = 0; i <transSet. length; i+) temp1 =transSeti;for( intj = 0; j < temp1.length(); j+) temp2 = temp1.charAt(j);/ 返回位置为 j 的 temp1 的值 a/ 返回 temp2 的字符串表示，并且自动去重candidate.add(String.valueOf(temp2);/treeSet添加会去掉重复的值returncandidate.size();/ 中元素个数不重复，且递增排序/ 求1频繁集pub

25、licvoiditem1_gen() 19String temp1 ="" ;doublem = 0;/ 得到 1频繁集的迭代器，迭代每一个候选项Iterator temp =candidateSet0.iterator();/ 使用方法 iterator()要求容器返回一个Iterator。while(temp.hasNext() / 遍历 temp （1候选集）temp1 = (String) temp.next();m = count_sup(temp1);/ 调用下面的方法，统计1候选集中每个元素个数，计算支持度时，用此m/transSet.length/ 符合条件

26、的加入 1 候选集，即最小支持度大于三的全部加入频繁集if(m >= 3) frequencySet0.add(temp1);/1 频繁集加入频繁项集数组，自动出去重复的集合/ 求 K候选集publicvoidcanditate_gen(intk) String y ="" , z ="" , m ="" ;charc1 ,c2 ;/ 这里减去 2是因为需要对频繁项个数是 k-1 个频繁项的频繁项集进行便利Iterator temp1 =frequencySetk - 2.iterator();/iterator迭代器，用于数组

27、遍历Iterator temp2 =frequencySet0.iterator();/ 遍历频繁项集数组，0:代表 1频繁集TreeSet h =new TreeSet();while(temp1.hasNext() y = (String) temp1.next();/c1 = y.charAt(y.length() - 1);/ 返回指定 y.length() - 1（数组的最后一个）的 char 值while(temp2.hasNext() z = (String) temp2.next();c2 = z.charAt(0);/c2=a,b,c,d,e,f/ 频繁集已经排序，所以不会出

28、现重复的情况if(c1 >= c2)continue;elsem = y + z;/m 为字符串组合 yzh.add(m);/m 加入 TreeSet20temp2 =frequencySet0.iterator();candidateSetk - 1 = h;/ k 候选集 =>k 频繁集publicvoidfrequent_gen(intk) String s1 ="" ;Iterator ix =candidateSetk - 1.iterator();/ 遍历 K候选集 ixwhile(ix.hasNext() s1 = (String) ix.next

29、();/ix中的值 s1if(count_sup(s1) >= (3) /s1项集支持度大于最小支持度frequencySetk - 1.add(s1);/s1加入 K频繁集中/ 判断频繁集为空publicbooleanis_frequent_empty(intk) if( frequencySetk - 1.isEmpty()returntrue ;elsereturnfalse;/ 打印候选集 频繁集publicvoidprint_canditate() for( inti = 0; i <frequencySet0.size(); i+) Iterator ix =candi

30、dateSeti.iterator();Iterator iy =frequencySeti.iterator();System.out .print(" 候选集 " + (i + 1) +":");while(ix.hasNext() System. out .print(String) ix.next() +"t");System.out .print("n" + " 频繁集 "+ (i + 1) +":" );while(iy.hasNext() System. out

31、 .print(String) iy.next() +"t");System.out .println();/ 求关联项集合publicvoidmaxfrequent_gen() 21inti;for(i = 1; i <frequencyIndex; i+) maxFrequency .addAll(frequencySeti);/ 打印频繁项集publicvoidprint_maxfrequent() Iterator iterator =maxFrequency .iterator();System. out .print(" 频繁项集： "

32、 );while(iterator.hasNext() System. out .print(String) iterator.next() +"t");System. out .println();System. out .println();/ 关联规则项集publicvoidruleGen() String s;Iterator iterator =maxFrequency .iterator();while(iterator.hasNext() s = (String) iterator.next();subGen(s);/ 求关联规则publicvoidsubGen(String s) String x ="" , y ="" ;for( inti = 1; i < (1