Apriori算法及其实现

《数据挖掘》设计论文院（系）理学院专业信息与计算科学指导老师刘建伟班级101001班姓名龙云祥、黄健时间2013年7月4日Apriori算法及其实现内容摘要经典的关联规则数据挖掘算法Apriori算法广泛应用于各种领域，通过对数据的关联性进行了分析和挖掘，挖掘出的这些信息在决策制定过程中具有重要的参考价值。信息技术的不断推广应用，如何充分利用这些数据信息为各个行业决策者提供决策支持成为一个十分迫切的又棘手的问题，人们除了利用现有的关系数据库标准查询语句得到一般的直观的信息以外，必须挖掘其内含的、未知的却又实际存在的数据关系。著名的Apriori算法是一种挖掘关联规则的算法。本文通过对Apriori算法的基本思想，挖掘出内含的数据关系，并实现Apriori算法。关键字：数据挖掘，关联规则，Apriori算法目录1人员分工..................................................................................................................................-1-2数据挖掘定义..........................................................................................................................-1-3关联规则介绍..........................................................................................................................-3-4Apriori算法背景介绍...........................................................................................................-3-5Apriori算法的描述...............................................................................................................-5-5.1Apriori算法的说明...................................................................................................-5-4.2Apriori算法的描述...................................................................................................-6-4.3Apriori算法的举例...................................................................................................-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-1人员分工黄健、龙云祥两人分工明确，对Apriori算法都已熟练掌握。黄健：画出程序流程图，负责实现书上Apriori基本算法。龙云祥：熟悉算法，测试程序，通过查阅资料，做出数据挖掘的流程，并了解Apriori改进的一些算法，主要负责论文。2数据挖掘定义数据挖掘（DataMining）就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。这个定义包括好几层含义：数据源必须是真实的、大量的、含噪声的；发现的是用户感兴趣的知识；发现的知识要可接受、可理解、可运用；并不要求发现放之四海皆准的知识，仅支持特定的发现问题。从广义上理解，数据、信息也是知识的表现形式，但是人们更把概念、规则、模式、规律和约束等看作知识。人们把数据看作是形成知识的源泉，好像从矿石中采矿或淘金一样。原始数据可以是结构化的，如关系数据库中的数据；也可以是半结构化的，如文本、图形和图像数据；甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现的知识可以被用于信息管理，查询优化，决策支持和过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行计算等方面的学者和工程技术人员，投身到数据挖掘这-2-一新兴的研究领域，形成新的技术热点。数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性数据。简而言之，数据挖掘其实是一类深层次的数据分析方法。数据分析本身已经有很多年的历史，只不过在过去数据收集和分析的目的是用于科学研究，另外，由于当时计算能力的限制，对大数据量进行分析的复杂数据分析方法受到很大限制。现在，由于各行业业务自动化的实现，商业领域产生了大量的业务数据，这些数据不再是为了分析的目的而收集的，而是由于纯机会的（Opportunistic）商业运作而产生。分析这些数据也不再是单纯为了研究的需要，更主要是为商业决策提供真正有价值的信息，进而获得利润。但所有企业面临的一个共同问题是：企业数据量非常大，而其中真正有价值的信息却很少，因此从大量的数据中经过深层分析，获得有利于商业运作、提高竞争力的信息，就像从矿石中淘金一样，数据挖掘也因此而得名。因此，数据挖掘可以描述为：按企业既定业务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的先进有效的方法。DM不能告诉你某个模型对你的企业的实际价值DM是一个工具，他只是帮助商业人士更深入、更容易地分析数据，但是无法告诉你某个模型对你的企业的实际价值，DM中得到的模型必须在现实生活中进行验证，DM不会在缺乏指导的情况下自动的发现模型。数据分析者必须知道你所选用的DM工具是如何工作的，采用的算法的原理是什么。DM永远不会替代有经验的商业分析师或管理人员所-3-起的作用，它只是一个强大的工具。3关联规则介绍如果一个事务中含有X，则该事务中很可能含有Y。具体形式为{X}→{Y}，即通常可以描述为:当一个事务中顾客购买了一样东西{钢笔}(这里X=“钢笔”)则很可能他同时还购买了{墨水}(这里Y=墨水)，这就是关联规则。在美国，有一种说法是:“尿不湿”和“啤酒”经常一起被购买。这种说法有其一定的现实意义:1)或许是该年龄段的经常喝啤酒的人刚好家庭开始养育小孩;2)或许是因为啤酒喝多，需要用尿不湿。然而不管怎样，如果没有数据挖掘中的关联规则在这里的应用，你是无论如何想象不出这样有点惊人的“笑话”。4Apriori算法背景介绍关联规则挖掘的一个典型例子是购物篮分析。市场分析员要从大量的数据中发现顾客放入其购物篮中的不同商品之间的关系。如果顾客买牛奶，他也购买面包的可能性有多大？什么商品组或集合顾客多半会在一次购物时同时购买？例如，买牛奶的顾客有80%也同时买面包，或买铁锤的顾客中有70%的人同时也买铁钉，这就是从购物篮数据中提取的关联规则。分析结果可以帮助经理设计不同的商店布局。一种策略是：经常一块购买的商品可以放近一些，以便进一步刺激这些商品一起销售，例如，如果顾客购买计算机又倾向于同时购买财务软件，那么将硬件摆放离软件陈列近一点，可能有助于增加两者的销售。另一种策略是：将硬件和软件放在商店的两端，可能诱发购买这些商品的顾客一路挑选其他商品。关联规则是描述数据库中数据项之间存在的潜在关系的规则,形式为“A1∧A2∧...∧Am=B1∧B2∧...∧Bn”,其Ai(i=1,2,......,m),Bj(j=1,2,......,n)-4-是数据库中的数据项.数据项之间的关联规则即根据一个事务中某些项的出现,可推导出另一些项在同一事务中也出现。挖掘关联规则的问题描述如下:设:I={i1,i2......,im}是所有项目的集合.D是所有事务的集合(即数据库),每个事务T是一些项目