《Apriori算法实验报告及程序》由会员分享，可在线阅读，更多相关《Apriori算法实验报告及程序（21页珍藏版）》请在金锄头文库上搜索。
1、Apr i or i算法实验报告及程序The document was finally revised on 2021Apriori 算法实验报告计算机应用技术学号 姓名 专业 教师计算机学院目录1 Apriori 实验实验背景现在, 数据挖掘作为从数据中获取信息的有效方法 , 越来越受到人们的重视。关 联规则挖掘首先是用来发现购物篮数据事务中各项之间的有趣联系。从那以后 , 关联 规则就成为数据挖掘的重要研究方向,它是要找出隐藏在数据间的相互关系。目前关联 规则挖掘的研究工作主要包括：Apriori算法的扩展、数量关联规则挖掘、关联规则增 量式更新、无须生成候选项目集的关联规则挖掘、最大频繁
2、项目集挖掘、约束性关联 规则挖掘以及并行及分布关联规则挖掘算法等。关联规则的挖掘问题就是在事务数据 库 D 中找出具有用户给定的满足一定条件的最小支持度 Minsup 和最小置信度 Minconf 的关联规则。1.1.1 国内外研究概况1993年，Agrawal等人首先提出关联规则概念，关联规则挖掘便迅速受到数据挖 掘领域专家的广泛关注迄今关联规则挖掘技术得到了较为深入的发展。Apriori算法 是关联规则挖掘经典算法。针对该算法的缺点，许多学者提出了改进算法，主要有基 于哈希优化和基于事务压缩等。1.1.2 发展趋势关联规则挖掘作为数据挖掘的重要研究内容之一 , 主要研究事务数据库、关系数
3、据库和其他信息存储中的大量数据项之间隐藏的、有趣的规律。关联规则挖掘最初仅 限于事务数据库的布尔型关联规则 , 近年来广泛应用于关系数据库 , 因此, 积极开展 在关系数据库中挖掘关联规则的相关研究具有重要的意义。近年来 ,已经有很多基于 Apriori 算法的改进和优化。研究者还对数据挖掘的理论进行了有益的探索，将概念格 和粗糙集应用于关联规则挖掘中，获得了显着的效果。到目前为止，关联规则的挖掘 已经取得了令人瞩目的成绩，包括：单机环境下的关联规则挖掘算法；多值属性关联 规则挖掘；关联规则更新算法；基于约束条件的关联规则挖掘；关联规则并行及分布 挖掘算法等。实验内容与要求实验内容编程实现Ap
4、riori算法：要求使用a,b,c,d,e,F,g,h,i,j10个项目随机产生 数据记录并存入数据库。从数据库读取记录进行 Apriori 实验，获得频繁集以及关联规 则，实现可视化。并用课堂上PPT的实例测试其正确性。实验要求1、程序结构：包括前台工具和数据库；2、设定项目种类为10个，随机产生事务，生成数据库；3、正确性验证（可用课堂上的例子）；4、算法效率的研究：在支持度固定数据量不同的时候测量运行时间；在数据量固定，支持度不同的时候测量运行时间；5、注意界面的设计，输入最小支持度和最小可信度，能够输出并显示频繁项目集 以及关联规则。实验目的1、加强对 Apriori 算法的理解；2、
5、锻炼分析问题、解决问题并动手实践的能力。2 Apriori算法分析与实验环境Apriori 算法的描述Apriori算法是一种找频繁项目集的基本算法。其基本原理是逐层搜索的迭代：频 繁K项Lk集用于搜索频繁(K+1)项集Lk+1，如此下去，直到不能找到维度更高的频繁 项集为止。这种方法依赖连接和剪枝这两步来实现。算法的第一次遍历仅仅计算每个 项目的具体值的数量，以确定大型 l 项集。随后的遍历，第 k 次遍历，包括两个阶 段。首先，使用在第(k-1 )次遍历中找到的大项集Lk-1和产生候选项集Ck。接着扫描 数据库，计算Ck中候选的支持度。用Hash树可以有效地确定Ck中包含在一个给定的 事务
6、t中的候选。如果某项集满足最小支持度，则称它为频繁项集。Apriori 算法的步骤步骤如下:1、设定最小支持度s和最小置信度c；2、Apriori算法使用候选项集。首先产生出候选的项的集合，即候选项集，若候选 项集的支持度大于或等于最小支持度，则该候选项集为频繁项集；3、在Apriori算法的过程中，首先从数据库读入所有的事务,每个项都被看作候选 1-项集，得出各项的支持度，再使用频繁1-项集集合来产生候选2-项集集合，因为先验 原理保证所有非频繁的1-项集的超集都是非频繁的；4、再扫描数据库，得出候选2-项集集合，再找出频繁2-项集，并利用这些频繁2-项 集集合来产生候选3-项集；5、重复扫
7、描数据库，与最小支持度比较，产生更高层次的频繁项集，再从该集合里 产生下一级候选项集，直到不再产生新的候选项集为止。开发环境2.3.1 软件环境(1) 编程软件：Jdk开发包+eclipse集成开发环境Eclipse是一个开放源代码的、基于Java的可扩展开发平台。就其本身而言，它 只是一个框架和一组服务，用于通过插件组件构建开发环境。幸运的是，Eclipse附 带了一个标准的插件集，包括Java开发工具(J ava Development Kit，JDK)。(2) 数据库软件：SQL Server 2008SQL Server 2008在Microsoft的数据平台上发布，可以组织管理任何数
8、据。可 以将结构化、半结构化和非结构化文档的数据直接存储到数据库中。可以对数据进行 查询、搜索、同步、报告和分析之类的操作。数据可以存储在各种设备上，从数据中 心最大的服务器一直到桌面计算机和移动设备，它都可以控制数据而不用管数据存储 在哪里。(3)办公软件：Excel 2010Excel是一款办公软件。它是微软办公套装软件office的重要的组成部分，它是集统计分析、数据处理和辅助决策等功能于一身，现在金融、统计财经、管理等众多 领域广泛应用。本实验主要用来为固定数据量改变最小支持数以及固定最小支持数改 变数据量两种情况进行时间分析提供可视化图表。2.3.2硬件环境装有Windows 7旗舰
9、版电脑。本章小结本章的内容主要是为了引出本实验的主要算法以及对算法的实现环境做了介绍。3 算法的设计Apriori算法整体框架是Apriori 结束图Apriori实验流程图主要的数据结构与函数数据结构class Transactionpublic int pid; public String itemset; 该类表示表中的一条记录。class Daopublic ArrayList Query(String sql)该类用于访问数据库操作。class Kfppublic char kfpstr=new char;public int index=-1;public int support=
10、0;public boolean isfp=true;该类代表一个频繁项目。主要的程序Java 中最常用的集合类是 List 和 Map。 List 的具体实现包括 ArrayList 和 Vector， 它们是可变大小的列表，比较适合构建、存储和操作任何类型对象的元素列表。 List 适用于按数值索引访问元素的情形。HashMap: Map接口的常用实现类，系统 vkey,value当成一个整体进行处理，系统总是根据Hash算法来计算的存储 位置，这样可以保证能快速存、取Map的vkey,value对。ArrayListvTransaction alTransactions:保存表中的所有记
11、录ArrayListvKfp alKfpsl：临时存储频繁项目的集合，存储连接后的结果ArrayListvKfpSureFpset:保存频繁 k 项集ArrayListvKfp SureFpsetPrio：保存频繁 k-1 项集ArrayListvString notFpList：保存一定不是频繁项目的集合，用于剪枝HashMapvString, IntegerKfpSuppor :频繁项目集及其对应的支持数HashMapvString,Double guanlianguize:关联规则及其置信度连接与剪枝操作对于连接操作的两个字符串(长度为k),它们必须有k-1个相同的字符才能做连接 操作。
12、例如:abc和abd可以连接成abcd， abd和bcd可以连接成abcd，而abc和ade就不 可以做连接操作。整个连接过程类似归并排序中的归并操作对于任一频繁项目集的所有非空子集也必须是频繁的，反之，如果某个候选的非 空子集不是频繁的，那么该候选集肯定不是频繁的，将其剪枝。本章小结本章主要介绍了算法设计的整体流程并且也对主要程序和操作作了简要的说明。4数据库的设计与数据的来源本实验的数据均存储于数据库中。数据库yuzm中共产生6张表。表test为测试 用表，用于程序的正确性验证。还有5张表存储随机产生的实验数据。其中数据库的 结构如下图所示。日LJ田口站库春囹 口垂统表国 2 dbo.da
13、tal 旨 dbo.data2 3 dbc.dataS 口 dbo.dsta4 旨 dbo.dsta5() 3 dbo.te5.tEl 口规圍 田口同交词 图数据库结构正确性验证数据表test为PPT上的实例，用于正确性验证。数据的item个数为5，其中的九行数 据均由SQL语句产生，表的每一行都是一个“0”“1”的字符串，字符串长度等于商 品种类，其中“0”表示该商品不存在，“1”表示该商品存在。表的全部数据如图。iditemQ110012 1010301100411010Siaioo6 11007101JQ0S11101g11100707图表test实验数据5张表是通过算法随机产生的具有不
14、同数据量的数据集，假设商品种类为10种，表的每一行都是一个“0”“1 ”的字符串，字符串长度等于商品种类，其中“0”表示该商品不 存在，“1”表示该商品存在。其中表datal共随机产生1万行数据，表data2产生5万 行数据，表data3产生25万行数据，表data4产生50万行数据，表data5产生75万行数据。部分数据如图。iditem13勺0011110011101011110000MlOOILIOOQOO142010100111114300001011001441101110011M51010000000展1001110111147naao 11000oooaiiiin图实验用表（部分
15、）本章小结本章主要对数据库的设计与数据来源做出了说明。5实验结果与性能分析Apriori实验界面其中可信度可自由设置，默认为。而支持度记为最小支持度与数据量的比例。实 验数据可以下拉选择6张表中的任意一张。如下图所示：图实验界面实验的正确性验证运行程序，我们选择表test，即可进行正确性验证，实验结果如下图:图正确性验证最终实验结果与ppt的结果相吻合，表明程序编写正确。实验性能分析为了对本程序的实验进行性能分析，我们分别采用固定数据量改变最小支持数以 及固定最小支持数改变数据量两种情况进行时间分析,其中最小置信度设为不变。固定最小支持度改变数据量设支持度为，最小可信度为。具体实验数据量与执行时间如下：表数据量对性能的影响数据量（万行）1
