基于Apriori算法的关联规则挖掘研究与实现

论文总字数：20559字

摘 要

关联规则挖掘是发现已知数据中有趣的关系，属于数据挖掘方法之一。Apriori算法是Agrawal等人提出的经典的简单布尔关联规则挖掘算法。本文针对小型超市部分数据，结合Apriori算法，目的是分析出顾客在购买某些商品的基础上购买另一些商品的倾向，生成的关联规可以用于指导决策。在对Apriori算法进行学习的基础上，用C#语言设计实现，结合SQL数据库，并用图形界面将结果清晰的展现出来。算法实现过程中的设计思路、得到的结果和存在问题在文中给予了说明。另外，本文在功能基本实现的基础上，对数据有序化处理,从而使算法时间性能得到些许改进。

关键词：关联规则，数据挖掘，Apriori算法，频繁集

Abstract：Association rule is one of the key technologies of data mining to find the funny association or relationship from the given dataset.Apriori algorithm is one of the most classic boolean，simple association rule data mining s which presented by Agrawal and etc.The paper is based on the small_and_partial supermarket’s transactions ,combined with Apriori algorithm ,so as to find the possibility of buying A and buying B at the same time .The regulation generated can be used in decision_making. After studied Apriori algorithm’s basic knowledge ,at the same time,designed and realized it in C# language combined with SQL database !Moreover ,the results will be clearly presented in windows .During the design period ,I have learned a lot about the Apriori algorithm ,the detailed design,results,and problems has been already noted in the paper .When simply realized the algorithm,I have made the data sequential trying optimize the algorithm in time_performance .

Key Words：association rule，data minging ,Apriori algorithm ,frequent item sets

目 录

1 绪论 3

1.1 Apriori算法 3

1.2 关联规则 4

1.3 数据挖掘 5

1.4 购物篮分析 5

2 算法设计与实现 5

2.1 算法设计与实现的开发环境 6

2.2 开发工具介绍 6

2.3 C#语言 6

3 关联规则概念详述 7

3.1 关联规则 7

3.2 项集 7

3.3 事务 7

3.4 支持度 7

3.5 置信度 8

3.6 强关联规则 8

4 Apriori算法详述 9

4.1 性质 9

4.2 寻找频繁项集的步骤 9

4.4 生成关联规则的步骤 10

4.5 生成关联规则的伪代码 10

4.6 算法实例描述 11

5 算法的设计与实现详述 12

5.1 算法实现流程图 12

5.2 数据库的设计 13

5.2 主界面的设计 15

5.3 产生频繁集的设计 16

5.5 产生关联规则的设计 18

5.6 Apriori算法的数据测试 21

5.7 算法数据的意义作用 22

5.8 性能分析与优化 23

5.9 算法实现的不足 24

总 结 25

参 考 文 献 26

致 谢 27

1 绪论

在科技迅猛发展的今天，计算机的普及，国家也大力提倡信息化，因此行业信息化的程度也越来越高。社会信息化后，社会的历史是数据的历史，多年的积淀，虽然数据量大，但问题是信息量少。数据挖掘应用而生，即从海量数据提取有用的信息。关联分析就是数据挖掘技术的一部分。关联规则一般用以发现交易数据库中不同商品（项）之间的联系，也叫购物篮分析^[1]。Apriori算法是最经典的简单的布尔关联规则挖掘算法。Apriori算法的扩展性强，不仅用于超市领域，还拓展到金融，电信等多个行业。业界学者对Apriori算法进行了多个方面的改进，改进后的Apriori算法可以处理多种类型数据，拓展挖掘任务，应用于各种各样的应用，其实现的商业价值是巨大的。

1.1 Apriori算法

1.1.1 算法简介

Apriori算法是挖掘产生布尔关联规则频繁项目集的经典算法，它是一种简单的布尔关联规则挖掘算法^[2]。其实现流程如图1.1所示。

图1.1 Apriori算法流程图

Apriori算法使用逐层搜索的迭代方法，在k项集基础上求得k 1项集。第一步扫描交易（事务）记录，找到频繁1项集记做L₁，然后利用L₁ 连接得到2候选集C₂，再剪枝得到频繁2项集的集合L₂，L₂找L₃，如此迭代，直到找不到更高的频繁集为止。最后在频繁集的基础上找出强规则，即产生用户感兴趣的关联规则。

1.1.2 算法的优缺点

根据上述步骤的描述，可知算法思想易于理解，主要用了循环迭代的方法，易于实现。这是其主要优点，但是连接步骤往往是总体性能的瓶颈。连接的条件是两个相同长度的频繁集只有最后一项不同，这样就需要循环逐项集再循环逐项比较之后，才能判断两者是否能连接。算法复杂度是O(N²)。现实情况下，项集的长度往往是很长的，计算两层循环时间耗费是很可观的。剪枝步骤中K候选项集C_k需要循环扫描数据库，计算它出现的频次，这样在数据量庞大的现实情况下，多次扫描数据库也是很耗费时间的。所以现在对算法的改进，性能是一方面

1.1.3 算法的研究的现状概述

现在的Apriori算法不仅仅是单纯用于哪些商品之间可以捆绑销售的的简单问题上了。现实生活中的购物篮信息既包含了交易物品的信息还有会员实体信息等多种影响购物模式的因素，数据结构越来越复杂多样化。近年来围绕关联规则的研究主要集中于两个方面，扩展经典关联规则能够解决问题的范围,改善经典关联规则挖掘算法效率和规则兴趣性^[3]。

1. 由于许多应用问题比超市购物问题更复杂，多种因素都会对关联规则挖掘做出影响。将不同类别层次的属性转换成布尔属性，考虑上时态关系属性使得挖掘出来的关联规则更有意义，这对丰富关联规则的应用领域也是很有意义的。如超大型事务数据库的挖掘，分布式事务数据库的挖掘，多表挖掘以及多层挖掘和空间关联规则挖掘等。

（二）性能优化即压缩连接步骤的比较次数，减少剪枝步骤的重复扫描数据库次数还有减少或不产生候选频繁集。其中比较典型的有以下两个：

（1）FP_Tree算法

剩余内容已隐藏，请支付后下载全文，论文总字数：20559字