当前位置：文档库 › Apriori算法及其实现

Apriori算法及其实现

《数据挖掘》设计论文

院（系）理学院

专业信息与计算科学

指导老师刘建伟

班级 101001班

姓名龙云祥、黄健

时间 2013年7月4日

Apriori算法及其实现

内容摘要

经典的关联规则数据挖掘算法Apriori 算法广泛应用于各种领域，通过对数据的关联性进行了分析和挖掘，挖掘出的这些信息在决策制定过程中具有重要的参考价值。信息技术的不断推广应用，如何充分利用这些数据信息为各个行业决策者提供决策支持成为一个十分迫切的又棘手的问题，人们除了利用现有的关系数据库标准查询语句得到一般的直观的信息以外，必须挖掘其内含的、未知的却又实际存在的数据关系。著名的Apriori算法是一种挖掘关联规则的算法。

本文通过对Apriori算法的基本思想，挖掘出内含的数据关系，并实现Apriori算法。

关键字：数据挖掘，关联规则，Apriori算法

1 人员分工.................................................................................................................................. - 1 -

2 数据挖掘定义.......................................................................................................................... - 1 -

3 关联规则介绍.......................................................................................................................... - 3 -

4 Apriori算法背景介绍........................................................................................................... - 3 -

5 Apriori算法的描述............................................................................................................... - 5 -

5.1 Apriori算法的说明................................................................................................... - 5 -

4.2 Apriori算法的描述................................................................................................... - 6 -

4.3 Apriori算法的举例................................................................................................... - 6 -

6 设计要求.................................................................................................................................. -

7 -

7 设计原理.................................................................................................................................. - 7 -

8 程序流程图.............................................................................................................................. - 8 -

9 程序运行环境.......................................................................................................................... - 8 -

10 测试数据................................................................................................................................ - 8 -

11 程序运行结果........................................................................................................................ - 9 -

12 参考资料.............................................................................................................................. - 10 -13设计总结............................................................................................................................... - 11 -

13.1黄健总结................................................................................................................... - 11 -

13.2龙云祥总结............................................................................................................... - 11 -14程序源代码见附录1............................................................................................................ - 11 -

1 人员分工

黄健、龙云祥两人分工明确，对Apriori算法都已熟练掌握。

黄健：画出程序流程图，负责实现书上Apriori基本算法。

龙云祥：熟悉算法，测试程序，通过查阅资料，做出数据挖掘的流程，并了解Apriori改进的一些算法，主要负责论文。

2 数据挖掘定义

数据挖掘（Data Mining）就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。这个定义包括好几层含义：数据源必须是真实的、大量的、含噪声的；发现的是用户感兴趣的知识；发现的知识要可接受、可理解、可运用；并不要求发现放之四海皆准的知识，仅支持特定的发现问题。

从广义上理解，数据、信息也是知识的表现形式，但是人们更把概念、规则、模式、规律和约束等看作知识。人们把数据看作是形成知识的源泉，好像从矿石中采矿或淘金一样。原始数据可以是结构化的，如关系数据库中的数据；也可以是半结构化的，如文本、图形和图像数据；甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现的知识可以被用于信息管理，查询优化，决策支持和过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行计算等方面的学者和工程技术人员，投身到数据挖掘这

一新兴的研究领域，形成新的技术热点。

数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性数据。

简而言之，数据挖掘其实是一类深层次的数据分析方法。数据分析本身已经有很多年的历史，只不过在过去数据收集和分析的目的是用于科学研究，另外，由于当时计算能力的限制，对大数据量进行分析的复杂数据分析方法受到很大限制。现在，由于各行业业务自动化的实现，商业领域产生了大量的业务数据，这些数据不再是为了分析的目的而收集的，而是由于纯机会的（Opportunistic）商业运作而产生。分析这些数据也不再是单纯为了研究的需要，更主要是为商业决策提供真正有价值的信息，进而获得利润。但所有企业面临的一个共同问题是：企业数据量非常大，而其中真正有价值的信息却很少，因此从大量的数据中经过深层分析，获得有利于商业运作、提高竞争力的信息，就像从矿石中淘金一样，数据挖掘也因此而得名。

因此，数据挖掘可以描述为：按企业既定业务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的先进有效的方法。

DM 不能告诉你某个模型对你的企业的实际价值DM是一个工具，他只是帮助商业人士更深入、更容易地分析数据，但是无法告诉你某个模型对你的企业的实际价值，DM中得到的模型必须在现实生活中进行验证，DM不会在缺乏指导的情况下自动的发现模型。数据分析者必须知道你所选用的DM工具是如何工作的，采用的算法的原理是什么。DM永远不会替代有经验的商业分析师或管理人员所

起的作用，它只是一个强大的工具。

3 关联规则介绍

如果一个事务中含有X，则该事务中很可能含有Y。具体形式为{X}→{Y}，即通常可以描述为:当一个事务中顾客购买了一样东西{钢笔}(这里X=“钢笔”)则很可能他同时还购买了{墨水}(这里Y= "墨水")，这就是关联规则。在美国，有一种说法是:“尿不湿”和“啤酒”经常一起被购买。这种说法有其一定的现实意义:1)或许是该年龄段的经常喝啤酒的人刚好家庭开始养育小孩;2)或许是因为啤酒喝多，需要用尿不湿。然而不管怎样，如果没有数据挖掘中的关联规则在这里的应用，你是无论如何想象不出这样有点惊人的“笑话”。

4 Apriori算法背景介绍

关联规则挖掘的一个典型例子是购物篮分析。市场分析员要从大量的数据中发现顾客放入其购物篮中的不同商品之间的关系。如果顾客买牛奶，他也购买面包的可能性有多大？什么商品组或集合顾客多半会在一次购物时同时购买？例如，买牛奶的顾客有80%也同时买面包，或买铁锤的顾客中有70%的人同时也买铁钉，这就是从购物篮数据中提取的关联规则。分析结果可以帮助经理设计不同的商店布局。一种策略是：经常一块购买的商品可以放近一些，以便进一步刺激这些商品一起销售，例如，如果顾客购买计算机又倾向于同时购买财务软件，那么将硬件摆放离软件陈列近一点，可能有助于增加两者的销售。另一种策略是：将硬件和软件放在商店的两端，可能诱发购买这些商品的顾客一路挑选其他商品。

关联规则是描述数据库中数据项之间存在的潜在关系的规则,形式为“A1∧A2∧...∧Am=>B1∧B2∧...∧Bn”,其Ai(i=1,2,......,m),Bj(j=1,2,......,n)

是数据库中的数据项.数据项之间的关联规则即根据一个事务中某些项的出现,可推导出另一些项在同一事务中也出现。

挖掘关联规则的问题描述如下:

设: I={i1,i2......,im}是所有项目的集合. D是所有事务的集合(即数据库), 每个事务T是一些项目的集合, T包含在I中, 每个事务可以用唯一的标识符TID来标识. 设X为某些项目的集合,如果X包含在T中, 则称事务T包含X, 关联规则则表示为如下形式 (X包含在T)=>(Y包含在T)的蕴涵式, 这里X 包含在I中, Y包含在I中, 并且X∧Y=Φ. 其意义在于一个事务中某些项的出现,可推导出另一些项在同一事务中也出现 (为简单化,将(X包含在T)=>(Y包含在T)表示为X=>Y, 这里,‘=>’称为‘关联’操作, X称为关联规则的先决条件, Y称为关联规则的结果).

事务集D中的规则X=>Y是由支持度s(support)和置信度c(confidence)约束,置信度表示规则的强度, 支持度表示在规则中出现的频度。数据项集X的支持度s(X)是D中包含X的事务数量与D的总事务数量之比, 但为下文便于叙述, 数据项集X的支持度是用数据库D中包含X的数量来表示;

规则X=>Y的支持度s定义为: 在D中包含X∪Y的事务所占比例为s%, 表示同时包含X和Y的事务数量与D的总事务量之比; 规则X=>Y的置信度c定义为: 在D中,c%的事务包含X的同时也包含Y, 表示D中包含X的事务中有多大可能性包含Y.

最小支持度阈值minsupport表示数据项集在统计意义上的最低主要性. 最小置信度阈值mincontinence表示规则的最低可靠性. 如果数据项集X满足X.support>=minsupport, 则X是大数据项集. 一般由用户给定最小置信度阈值

和最小支持度阈值.置信度和支持度大于相应阈值的规则称为强关联规则, 反之称为弱关联规则. 发现关联规则的任务就是从数据库中发现那些置信度、支持度大小等于给定值的强壮规则.

基于上述概念，我们可以很容易得到一些基本结论:

(1) K维数据项集X K是频繁项集的必要条件是它所有K-1维子项集也为频繁项集，记为X K-1

(2)如果K维数据项集X K的任意一个K-1维子集X K-1，不是频繁项集，则K 维数据项集X K本身也不是最大数据项集。

(3) X K是K维频繁项集，如果所有K-1维频繁项集集合X K-1中包含XK的K-1维子项集的个数小于K，则X K不可能是K维最大频繁数据项集。

证明:

很明显，数据项集X K-1:的K-1维子项集的个数为K-1。如果高频繁数据项集X K-1，中包含X K的K-1.维子项集的个数小于k，则存在X K的K-1维子项集不是频繁数据项集，由结论(2)知K维数据项集本身也不是高频繁数据项集。

5 Apriori算法的描述

5.1 Apriori算法的说明

在Apriori算法中,寻找最大项目集的基本思想是: 算法需要对数据集进行多步处理.第一步,简单统计所有含一个元素项目集出现的频率,并找出那些不小于最小支持度的项目集, 即一维最大项目集. 从第二步开始循环处理直到再没有最大项目集生成. 循环过程是: 第k步中, 根据第k-1步生成的(k-1)维最大项目集产生k维侯选项目集, 然后对数据库进行搜索, 得到侯选项目集的项集支持度, 与最小支持度比较, 从而找到k维最大项目集.

为方便后文叙述，现约定如下:

1.数据库事务中的项目都是以字母顺序排列的,每个项目用来标识, 这里TID表示相应事务的标识符, item则表示项目名称.

2.每个项目集的项目数称为该项目集的size. 当项目集的size=k时, 称该项目集为k-itemset(k维项目集).

下文中遇到的以下符号,分别代表相应的内容

k-itemset k维项目集

Lk 具有最小支持度的最大k-itemset

Ck 侯选的k-itemsets(潜在的最大项目集)

4.2 Apriori算法的描述

Apriori算法的第一步是简单统计所有含一个元素的项集出现的频率,来决定最大的一维项目集。在第k步,分两个阶段,首先用一函数sc_candidate(候选),通过第(k-1)步中生成的最大项目集Lk-1来生成侯选项目集Ck。然后搜索数据库计算侯选项目集Ck的支持度。为了更快速地计算Ck中项目的支持度, 文中使用函数count_support计算支持度。

4.3 Apriori算法的举例

示例说明Apriori算法运作过程

有一数据库D, 其中有四个事务记录, 分别表示为

TID Items

T1I1,I3,I4

T2I2,I3,I5

T3I1,I2,I3,I5

T4I2,I5

在Apriori算法中每一步创建该步的侯选集.统计每个侯选项目集的支持度,

并和预定义的最小支持度比较,来确定该步的最大项目集.

首先统计出一维项目集,即:C1.这里预定义最小支持度minsupport=2,侯选项目集中满足最小支持度要求的项目集组合成最大的1-itemsets.为生成最大的2-itemsets,使用了sc_candidate函数中join步,即: L1joinL1,并通过prune 步删除那些C2的那些子集不在L1中的项目集.生成了侯选项目集C2.搜索D中4个事务,统计C2中每个侯选项目集的支持度.然后和最小支持度比较,生成L2.侯选项目集C3是由L2生成.要求自连接的两个最大2-itemsets中,第一个项目相同,在L2中满足该条件的有{I2,I3},{I2,I5}.这两个集合经过join步后, 产生集合{I2，I3，I5}.在prune步中,测试{I2，I3，I5}的子集{I3，I5},{I2，I3},{I2，I5}是否在L2中,由L2可以知道{I3,I5},{I2,I3},{I2,I5}本身就是最大2-itemsets.即{I2,I3,I5}的子集都是最大项目集.那么{I2,I3,I5}为侯选3-itemset.然后搜索数据库中所有事务记录,生成最大的3-tiemsets L3. 此时, 从L3中不能再生成侯选4-itemset .Apriori算法结束.

6 设计要求

用java代码实现Apriori算法，并对每一步的结果做输出，即每一步产生的频繁项集输出。

7 设计原理

8 程序流程图

9 程序运行环境

Myeclipse、WindowsXP及其以上10 测试数据

TID Items

T100I1,I2,I5

T200I2,I4

T300I2,I3

T400I1,I2,I4

T500 I1,I3

T600 I2,I3

T700 I1,I3

T800 I1,I2,I3,I5

T900 I1,I2,I3

设置min_sup=2，

频繁3项集：

项集支持度计数

{I1,I2,I3}2

{I1,I2,I5}2

设置min_sup=3，

频繁2项集：

项集支持度计数

{I1,I2 }4

{I1,I3 }4

{I2,I3 } 4

11 程序运行结果

12 参考资料

[1]（加）Jiawei Han,Micheline Kamber 著.范明等译.数据挖掘：概念与技术.北京：机械工业出版社，2001.8

[2] 陈京民数据仓库与数据挖掘技术 2002.北京电子工业出版社

[3] 颜雪松、蔡之华一种基于Apriori的高效关联规则挖掘算法的研究计算机工程与应用 2002.10 1002-8331一(2002) 10-0209-03 209-211

[4] 李绪成，王保保挖掘关联规则中Apriori算法的一种改进计算机工程2002.7 第28卷 104-105

[5] 毛秉毅一种新的关联规则发现算法及应用研究计算机应用与工程 2002.22

[6] Peter Cabena, Discovering Data Mining From Concept to Implementation，IBM, 1997

13设计总结

13.1黄健总结

本次实验很好的完成了试验任务，小组成员分工明确，对Appriori算法有了深刻了解，并且很好的锻炼了自己的编码的能力。

13.2龙云祥总结

一周的数据挖掘课程设计，在老师的指导和黄健相互合作下，我学到了不少东西。可将我本周学习的总结分成两部分，其中一部分是理论课程再次巩固的总结，另一部分是实践课程的总结。

Apriori算法在上课期间已经掌握，不过只是停留在表面，这次实践课程我通过网上查阅资料了解了更多相关的算法，也明白了它的优缺点，虽然在编码阶段遇到过一些困难，不过经过询问都一一解决，通过对这门课的实践学习让我意识到理论学习很重要，更重要的是让我看到了将理论与实际相结合，看到了将理论与实际相结合才能更好的发挥理论的作用和产生实际的效果，才更能发挥我们所学的知识的作用，更好的掌握理论知识和提高实践能力。

14程序源代码见附录1