Apriori算法实验报告及程序

Apriori算法实验报告

学 号： 姓 名： 专 业： 计算机应用技术 教 师：

计算机学院

目 录

1 APRIORI实验 .................................................................................................................................................. 1.1 实验背景 ....................................................................................................................................................... 1.1.1 国内外研究概况 ................................................................................................................................... 1.1.2 发展趋势 ............................................................................................................................................... 1.2 实验内容与要求 ........................................................................................................................................... 1.2.1 实验内容 ............................................................................................................................................... 1.2.2 实验要求 ............................................................................................................................................... 1.2.3 实验目的 ............................................................................................................................................. 1 2 APRIORI算法分析与实验环境 ...................................................................................................................... 2.1 APRIORI算法的描述 ...................................................................................................................................... 2.2 APRIORI算法的步骤 .................................................................................................................................... 3 2.3 开发环境 ....................................................................................................................................................... 2.3.1 软件环境 ............................................................................................................................................... 2.3.2 硬件环境 ............................................................................................................................................... 2.4 本章小结 ....................................................................................................................................................... 3 算法的设计 ........................................................................................................................................................ 3.1 APRIORI算法整体框架 .................................................................................................................................. 3.2 主要的数据结构与函数 ............................................................................................................................... 3.2.1 数据结构 ............................................................................................................................................... 3.2.2 主要的程序 ........................................................................................................................................... 3.2.3 连接与剪枝操作 ................................................................................................ 错误！未定义书签。 3.3 本章小结 ....................................................................................................................................................... 4 数据库的设计与数据的来源 ............................................................................................................................. 4.1正确性验证数据 ............................................................................................................................................ 4.2 实验数据 ....................................................................................................................................................... 4.3 本章小结 ....................................................................................................................................................... 5 实验结果与性能分析 ......................................................................................................................................... 5.1 APRIORI实验界面 .......................................................................................................................................... 5.2 实验的正确性验证 ....................................................................................................................................... 5.3 实验性能分析 ............................................................................................................................................... 5.3.1固定最小支持度改变数据量 ................................................................................................................ 5.3.2固定数据量改变最小支持度 ................................................................................................................ 5.3.3实验结果分析 ........................................................................................................................................ 5.4 本章小结 .................................................................................................................... 错误！未定义书签。 6 总结与体会 ........................................................................................................................................................

1 Apriori实验

1.1 实验背景

现在, 数据挖掘作为从数据中获取信息的有效方法, 越来越受到人们的重视。关联规则挖掘首先是用来发现购物篮数据事务中各项之间的有趣联系。从那以后, 关联规则就成为数据挖掘的重要研究方向,它是要找出隐藏在数据间的相互关系。目前关联规则挖掘的研究工作主要包括：Apriori算法的扩展、数量关联规则挖掘、关联规则增量式更新、无须生成候选项目集的关联规则挖掘、最大频繁项目集挖掘、约束性关联规则挖掘以及并行及分布关联规则挖掘算法等。关联规则的挖掘问题就是在事务数据库D中找出具有用户给定的满足一定条件的最小支持度Minsup和最小置信度Minconf的关联规则。

1.1.1 国内外研究概况

1993年，Agrawal等人首先提出关联规则概念，关联规则挖掘便迅速受到数据挖掘领域专家的广泛关注.迄今关联规则挖掘技术得到了较为深入的发展。Apriori算法是关联规则挖掘经典算法。针对该算法的缺点，许多学者提出了改进算法，主要有基于哈希优化和基于事务压缩等。 1.1.2 发展趋势

关联规则挖掘作为数据挖掘的重要研究内容之一, 主要研究事务数据库、关系数据库和其他信息存储中的大量数据项之间隐藏的、有趣的规律。关联规则挖掘最初仅限于事务数据库的布尔型关联规则, 近年来广泛应用于关系数据库, 因此, 积极开展在关系数据库中挖掘关联规则的相关研究具有重要的意义。近年来,已经有很多基于Apriori算法的改进和优化。研究者还对数据挖掘的理论进行了有益的探索，将概念格和粗糙集应用于关联规则挖掘中，获得了显着的效果。到目前为止，关联规则的挖掘已经取得了令人瞩目的成绩，包括：单机环境下的关联规则挖掘算法；多值属性关联规则挖掘；关联规则更新算法；基于约束条件的关联规则挖掘；关联规则并行及分布挖掘算法等。

1.2 实验内容与要求

1.2.1 实验内容

编程实现Apriori算法：要求使用‘a’,‘b’,‘c’,‘d’,‘e’,‘f’,‘g’,‘h’,‘i’,‘j’10个项目随机产生数据记录并存入数据库。从数据库读取记录进行Apriori实验，获得频繁集以及关联规则，实现可视化。并用课堂上PPT的实例测试其正确性。 1.2.2 实验要求

1、程序结构：包括前台工具和数据库；

2、设定项目种类为10个，随机产生事务，生成数据库； 3、正确性验证（可用课堂上的例子）；

4、算法效率的研究：在支持度固定数据量不同的时候测量运行时间；在数据量固定，支持度不同的时候测量运行时间；

5、注意界面的设计，输入最小支持度和最小可信度，能够输出并显示频繁项目集以及关联规则。 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。接着扫描数据库，计算Ck中候选的支持度。用Hash树可以有效地确定Ck中包含在一个给定的事务t中的候选。如果某项集满足最小支持度, 则称它为频繁项集。

2.2 Apriori算法的步骤

步骤如下:

1、设定最小支持度s和最小置信度c； 2、Apriori算法使用候选项集。首先产生出候选的项的集合,即候选项集,若候选项集的支持度大于或等于最小支持度,则该候选项集为频繁项集；

3、在Apriori算法的过程中,首先从数据库读入所有的事务,每个项都被看作候选1-项集,得出各项的支持度,再使用频繁1-项集集合来产生候选2-项集集合,因为先验原理保证所有非频繁的1-项集的超集都是非频繁的；

4、再扫描数据库,得出候选2-项集集合,再找出频繁2-项集,并利用这些频繁2-项集集合来产生候选3-项集；

5、重复扫描数据库,与最小支持度比较,产生更高层次的频繁项集,再从该集合里产生下一级候选项集,直到不再产生新的候选项集为止。

2.3 开发环境

2.3.1 软件环境

(1)编程软件：Jdk开发包+eclipse集成开发环境

Eclipse 是一个开放源代码的、基于Java的可扩展开发平台。就其本身而言，它只是一个框架和一组服务，用于通过插件组件构建开发环境。幸运的是，Eclipse 附带了一个标准的插件集，包括Java开发工具（Java Development Kit，JDK）。 (2)数据库软件：SQL Server 2008

SQL Server 2008 在Microsoft的数据平台上发布，可以组织管理任何数据。可以将结构化、半结构化和非结构化文档的数据直接存储到数据库中。可以对数据进行查询、搜索、同步、报告和分析之类的操作。数据可以存储在各种设备上，从数据中心最大的服务器一直到桌面计算机和移动设备，它都可以控制数据而不用管数据存储在哪里。 (3)办公软件：Excel 2010

Excel是一款试算表办公软件。它是微软办公套装软件office的重要的组成部分，它是集统计分析、数据处理和辅助决策等功能于一身，现在金融、统计财经、管理等众多领域广泛应用。本实验主要用来为固定数据量改变最小支持数以及固定最小支持数改变数据量两种情况进行时间分析提供可视化图表。 2.3.2 硬件环境

装有Windows 7 旗舰版电脑。