《Apriori算法实验报告与程序》由会员分享，可在线阅读，更多相关《Apriori算法实验报告与程序（42页珍藏版）》请在金锄头文库上搜索。
1、-Apriori算法实验报告学 号：姓 名：专 业： 计算机应用技术 教 师：计算机学院目 录1 APRIORI实验11.1 实验背景11.1.1 国内外研究概况11.1.2 开展趋势11.2 实验内容与要求11.2.1 实验内容11.2.2 实验要求11.2.3 实验目的22 APRIORI算法分析与实验环境32.1 Apriori算法的描述32.2 Apriori算法的步骤32.3 开发环境32.3.1 软件环境32.3.2 硬件环境42.4 本章小结43 算法的设计53.1 Apriori算法整体框架53.2 主要的数据构造与函数53.2.1 数据构造53.2.2 主要的程序63.2.3
2、 连接与剪枝操作63.3 本章小结64 数据库的设计与数据的来源74.1正确性验证数据74.2 实验数据74.3 本章小结85 实验结果与性能分析95.1 Apriori实验界面95.2 实验的正确性验证95.3 实验性能分析10固定最小支持度改变数据量10固定数据量改变最小支持度11实验结果分析115.4 本章小结126 总结与体会13. z.-1 Apriori实验1.1 实验背景现在, 数据挖掘作为从数据中获取信息的有效方法, 越来越受到人们的重视。关联规则挖掘首先是用来发现购物篮数据事务中各项之间的有趣联系。从那以后, 关联规则就成为数据挖掘的重要研究方向,它是要找出隐藏在数据间的相互
3、关系。目前关联规则挖掘的研究工作主要包括：Apriori算法的扩展、数量关联规则挖掘、关联规则增量式更新、无须生成候选工程集的关联规则挖掘、最大频繁工程集挖掘、约束性关联规则挖掘以及并行及分布关联规则挖掘算法等。关联规则的挖掘问题就是在事务数据库D中找出具有用户给定的满足一定条件的最小支持度Minsup和最小置信度Minconf的关联规则。 国内外研究概况1993年，Agrawal等人首先提出关联规则概念，关联规则挖掘便迅速受到数据挖掘领域专家的广泛关注.迄今关联规则挖掘技术得到了较为深入的开展。Apriori算法是关联规则挖掘经典算法。针对该算法的缺点，许多学者提出了改进算法，主要有基于哈希
4、优化和基于事务压缩等。 开展趋势关联规则挖掘作为数据挖掘的重要研究内容之一, 主要研究事务数据库、关系数据库和其他信息存储中的大量数据项之间隐藏的、有趣的规律。关联规则挖掘最初仅限于事务数据库的布尔型关联规则, 近年来广泛应用于关系数据库, 因此, 积极开展在关系数据库中挖掘关联规则的相关研究具有重要的意义。近年来,已经有很多基于Apriori算法的改进和优化。研究者还对数据挖掘的理论进展了有益的探索，将概念格和粗糙集应用于关联规则挖掘中，获得了显著的效果。到目前为止，关联规则的挖掘已经取得了令人瞩目的成绩，包括：单机环境下的关联规则挖掘算法；多值属性关联规则挖掘；关联规则更新算法；基于约束条
5、件的关联规则挖掘；关联规则并行及分布挖掘算法等。1.2 实验内容与要求1.2.1 实验内容编程实现Apriori算法：要求使用a,b,c,d,e,f,g,h,i,j10个工程随机产生数据记录并存入数据库。从数据库读取记录进展Apriori实验，获得频繁集以及关联规则，实现可视化。并用课堂上PPT的实例测试其正确性。1.2.2 实验要求1、程序构造：包括前台工具和数据库；2、设定工程种类为10个，随机产生事务，生成数据库；3、正确性验证可用课堂上的例子；4、算法效率的研究：在支持度固定数据量不同的时候测量运行时间；在数据量固定，支持度不同的时候测量运行时间；5、注意界面的设计，输入最小支持度和最
6、小可信度，能够输出并显示频繁工程集以及关联规则。1.2.3 实验目的1、加强对Apriori算法的理解；2、锻炼分析问题、解决问题并动手实践的能力。2 Apriori算法分析与实验环境2.1 Apriori算法的描述Apriori算法是一种找频繁工程集的根本算法。其根本原理是逐层搜索的迭代：频繁K项Lk 集用于搜索频繁(K+1)项集Lk+1，如此下去，直到不能找到维度更高的频繁项集为止。这种方法依赖连接和剪枝这两步来实现。算法的第一次遍历仅仅计算每个工程的具体值的数量，以确定大型l项集。随后的遍历，第k次遍历，包括两个阶段。首先，使用在第(k-1)次遍历中找到的大项集Lk-1和产生候选项集Ck
7、。接着扫描数据库，计算Ck中候选的支持度。用Hash树可以有效地确定Ck中包含在一个给定的事务t中的候选。如果*项集满足最小支持度, 则称它为频繁项集。2.2 Apriori算法的步骤步骤如下:1、设定最小支持度s和最小置信度c；2、Apriori算法使用候选项集。首先产生出候选的项的集合,即候选项集,假设候选项集的支持度大于或等于最小支持度,则该候选项集为频繁项集；3、在Apriori算法的过程中,首先从数据库读入所有的事务,每个项都被看作候选1-项集,得出各项的支持度,再使用频繁1-项集集合来产生候选2-项集集合,因为先验原理保证所有非频繁的1-项集的超集都是非频繁的；4、再扫描数据库,得
8、出候选2-项集集合,再找出频繁2-项集,并利用这些频繁2-项集集合来产生候选3-项集；5、重复扫描数据库,与最小支持度比较,产生更高层次的频繁项集,再从该集合里产生下一级候选项集,直到不再产生新的候选项集为止。2.3 开发环境 软件环境 (1)编程软件：Jdk开发包+eclipse集成开发环境Eclipse 是一个开放源代码的、基于Java的可扩展开发平台。就其本身而言，它只是一个框架和一组效劳，用于通过插件组件构建开发环境。幸运的是，Eclipse 附带了一个标准的插件集，包括Java开发工具Java Development Kit，JDK。 (2)数据库软件：SQL Server 2008
9、SQL Server 2008 在Microsoft的数据平台上发布，可以组织管理任何数据。可以将构造化、半构造化和非构造化文档的数据直接存储到数据库中。可以对数据进展查询、搜索、同步、报告和分析之类的操作。数据可以存储在各种设备上，从数据中心最大的效劳器一直到桌面计算机和移动设备，它都可以控制数据而不用管数据存储在哪里。 (3)办公软件：E*cel 2010 E*cel是一款试算表办公软件。它是微软办公套装软件office的重要的组成局部，它是集统计分析、数据处理和辅助决策等功能于一身，现在金融、统计财经、管理等众多领域广泛应用。本实验主要用来为固定数据量改变最小支持数以及固定最小支持数改变
10、数据量两种情况进展时间分析提供可视化图表。 硬件环境装有Windows 7 旗舰版电脑。2.4 本章小结本章的内容主要是为了引出本实验的主要算法以及对算法的实现环境做了介绍。3 算法的设计3.1 Apriori算法整体框架图3.1 Apriori实验流程图3.2 主要的数据构造与函数3.2.1 数据构造class Transaction public int pid;public String itemset;该类表示表中的一条记录。class Daopublic ArrayList Query(String sql)该类用于访问数据库操作。class Kfppublic char kfpst
11、r=new charApriori.ITEMSIZE;public int inde*=-1;public int support=0;public boolean isfp=true;该类代表一个频繁工程。3.2.2 主要的程序Java 中最常用的集合类是 List 和 Map。 List 的具体实现包括 ArrayList 和 Vector，它们是可变大小的列表，比较适合构建、存储和操作任何类型对象的元素列表。 List 适用于按数值索引访问元素的情形。HashMap：Map接口的常用实现类，系统当成一个整体进展处理，系统总是根据Hash算法来计算的存储位置，这样可以保证能快速存、取 Ma
12、p的对。ArrayList alTransactions：保存表中的所有记录ArrayList alKfpsl：临时存储频繁工程的集合，存储连接后的结果ArrayList SureFpset：保存频繁k项集ArrayList SureFpsetPrio：保存频繁k-1项集ArrayList notFpList：保存一定不是频繁工程的集合，用于剪枝HashMap KfpSuppor:频繁工程集及其对应的支持数HashMap guanlianguize:关联规则及其置信度3.2.3 连接与剪枝操作对于连接操作的两个字符串(长度为k)，它们必须有k-1个一样的字符才能做连接操作。 例如:abc和ab
13、d可以连接成abcd，abd和bcd可以连接成abcd，而abc和ade就不可以做连接操作。整个连接过程类似归并排序中的归并操作对于任一频繁工程集的所有非空子集也必须是频繁的，反之，如果*个候选的非空子集不是频繁的，则该候选集肯定不是频繁的，将其剪枝。3.3 本章小结本章主要介绍了算法设计的整体流程并且也对主要程序和操作作了简要的说明。4 数据库的设计与数据的来源本实验的数据均存储于数据库中。数据库yuzm中共产生6张表。表test为测试用表，用于程序的正确性验证。还有5张表存储随机产生的实验数据。其中数据库的构造如以下图所示。图4.1 数据库构造4.1正确性验证数据表test为PPT上的实例
14、，用于正确性验证。数据的item个数为5，其中的九行数据均由SQL语句产生，表的每一行都是一个01的字符串，字符串长度等于商品种类，其中0表示该商品不存在，1表示该商品存在。表的全部数据如图4.2。图4.2 表test4.2 实验数据5张表是通过算法随机产生的具有不同数据量的数据集，假设商品种类为10种，表的每一行都是一个01的字符串，字符串长度等于商品种类，其中0表示该商品不存在，1表示该商品存在。其中表data1共随机产生1万行数据，表data2产生5万行数据，表data3产生25万行数据，表data4产生50万行数据，表data5产生75万行数据。局部数据如图4.3。图4.3 实验用表局部4.3 本章小结本章主要对数据库的设计与数据来源做出了说明。5 实验结果与性能分析5.1 Apriori实验界面其中可信度可自由设置，默认为0.7。而支持度记为最小支持度与数据量的比例。实验数据可以下拉选择6张表中的任意一张。如以下图所示：图5.1实验界面5.2 实验的正确性验证运行程序，我们选择表test，即可进展正确性验证，实验结果如以下图：图5.2正确性验证最终实验结果与ppt的结果相吻合，说明程序编写正确。5.3 实
