网络工程毕业设计论文信息、知识、智能的转换和算法分析.doc

《网络工程毕业设计论文信息、知识、智能的转换和算法分析.doc》由会员分享，可在线阅读，更多相关《网络工程毕业设计论文信息、知识、智能的转换和算法分析.doc（23页珍藏版）》请在三一办公上搜索。

1、 毕 业 论 文（设计）论文（设计）题目：信息、知识、智能的转换和算法分析 系 别： 专 业： 学 号： 姓 名： 指导教师： 毕 业 论 文（设 计） 开 题 报 告系别:计算机与信息科学系 专业:网络工程学 号 姓 名论文（设计）题目信息、知识、智能的转换和算法分析命题来源教师命题 学生自主命题 教师课题选题意义(不少于300字): 随着信息技术的高速发展，数据库应用的规模、范围和深度不断扩大，已经从单台机器发展到网络环境。由于各种新型技术与数据库技术的有机结合，使数据库领域中的新内容、新应用、新技术层出不穷，形成了庞大的数据库体系，如商业条码的推广、企业和政府利用计算机管理事务的能力增强

2、，产生了大规模的数据。而简单数据信息查询只是数据库内容的选择性输出，无论是查询、统计还是报表，其处理方式都是对指定的数据进行简单的数字处理，而不是对这些数据所包含的内在信息进行提取，因此它和人们期望的分析预测、决策支持等高级应用仍有很大的距离，人们希望能够提供更高层次的数据分析功能，自动和智能的将待处理的数据信息转化为有用的知识。数据挖掘之所以吸引专家学者的研究和引起商业厂家的广泛关注，主要在于大型数据系统的广泛使用和把数据转换成有用的知识，推动社会进步，为企业提供能带来商业利润的决策信息使企业在市场竞争中立于不败之地。研究综述(前人的研究现状及进展情况，不少于600字):Shannon信息论

3、和人工智能理论分别于20世纪40年代和50年代相继产生，系统的知识理论却长期无人问津，成为一段理论空白。这种状况在信息论和人工智能理论发展的初期似乎并没有造成明显的问题，但是，随着研究的不断的深入，知识理论的空白就逐渐成为一种制约，信息论和智能理论的发展陷入受限的尴尬境地。20世纪70年代，由于研究和建造专家系统的需要而出现了“知识工程”。然而，知识工程主要关注了知识的表示和知识的演绎推理的问题，至于如何获取专家系统所需要的知识，则几乎完全依靠专家系统设计者的手工操作。因此，知识工程没有能够形成完全的知识理论。与此同时，数据库系统的三个主要模式：层次、网络和关系型数据库的研究和开发取得了重要进

4、展。20世纪80年代，关系型数据库及其相关的数据模型工具、数据索引及数据组织技术得到广泛采用，并形成了整个数据库市场的主导。事务数据库、主动数据库、知识库、办公信息库等技术也得到蓬勃发展。从20世纪80年代中期开始，关系型数据库技术和新型技术的结合成为数据库研究和开发的重要标志。20世纪90年代，数据挖掘与知识发现应运而生。数据挖掘是一个多学科交叉研究领域，它融合了数据库技术、人工智能、机器学习、统计学、知识工程、面向对象方法、信息检索、高性能计算以及数据可视化等最新技术的研究成果。基于统计学、人工智能、面向对象方法等在内的理论与技术成果已经被成功的应用到商业处理和分析中，这些应用从某种程度上

5、为数据挖掘技术提出和发展起到了极大的推动作用。然而，作为人工智能系统研究的三大主流学派，结构主义、功能主义、行为主义方法各自在信息智能决策中取得了不少的进展和成果，但却是计算机科学研究中争议最多而又始终保持强大生命力的研究领域。在这样的背景下，我国著名信息学者、全信息创始人钟义信教授提出智能系统智能生成的共性核心机制：信息-知识-智能的转换。 “信息-知识-智能的转换”的研究方法将能够更好地为智能理论研究服务，在社会走向信息化和智能化的时代将为人类做出更大的贡献。研究的目标和主要内容（不少于400字）本选题将数据挖掘与机器知行学相结合，通过关联规则挖掘算法，从事务数据库中挖掘知识，实现信息、知

6、识、智能的转换。本选题研究内容如下：（1）对信息、知识、智能的转换理论体系结构及数据挖掘原理的应用进行探究。（2）关联规则Apriori算法分析，Apriori算法的内容分析如下：1）关联规则挖掘实现的基本思路：关联规则是用来揭示数据之间未知的相关依赖关系，通过设置支持度和置信度，生成所需要的数据信息。2）Apriori算法的实施思想：掌握Apriori算法运算的基本思想，是实施Apriori算法应用实现的基础。3）Apriori算法性能的分析：了解Apriori算法的优点和不足，为算法的改进优化具有重要意义。4）Apriori挖掘算法的实现：根据关联规则Apriori挖掘算法的描述，用Vis

7、ualC+编译器编写Apriori算法代码，并于一例子中实现。5）对具有语义最小支持度的关联规则挖掘方法的探讨：传统的关联规则挖掘算法大都依赖于一个统一的支持度和置信度阈值设置，在此基础上所挖掘出的结果有很多是没有任何意义或是错误的关联规则。如何引入具有语义最小支持度对算法做相应的改进，是舍弃无效的、虚假的、具有误导性的规则起辅助作用，增强了决策功能。拟采用的研究方法查阅相关资料，借助机器知行学的思想和数据挖掘技术对关联规则Apriori算法进行分析。使用VisualC+编译器编写代码，实现Apriori算法。研究工作的进度安排2010年11月24号11月30号与指导老师沟通交流，完成毕业论文

8、选题；2010年12月1号12月31号 搜集资料，查阅文献，完成开题报告；l2011年1月1号1月31号 完成文献综述，定出算法的需求分析案例；l2011年2月1号2月28号 整理相关资料并完成概要和详细设计；l2011年3月1号4月30号 扼写及整理修改初稿；l2011年5月10号5月31号 总结毕业设计的整个过程，完成毕业设计论文初稿；2011年6月1号6月3号 定稿，打印装订，参加答辩；参考文献目录（作者、书名或论文题目、出版社或刊号、出版年月日或出版期号）1毛国君,段立娟，王实，石云.数据挖掘原理与算法M.北京：清华大学出版社,2007.122何宏.关联规则挖掘算法的研究与实现D. 湖

9、南：湘潭大学，2006：47-503纪希禹,韩秋明,李微,李华锋.数据挖掘技术应用实例M. 北京:机械工业出版社,20094陈竞.基于数据挖掘技术的零售业精确营销应用研究J.中国市场，2010，14:16-185张玲玲，李军，石勇，周琳.基于数据挖掘的智能知识管理模型构架研究J.中国管理科学,2009,17(10):620-6246宫铁峰，髙剑平，韩慧君. 基于全信息的智能决策支持系统研究J.上海海运学院学报，1996，17（2）：84-897张磊,夏士雄,周勇,牛强.具有语义最小支持度的关联规则挖掘方法J.微电子学与计算机,2008,25(9):14-178谢康林,叶瑾,周瑞凌.在数据仓库中

10、进行基于在语义层次的关联规则挖掘J.小型微型计算机系统2003,24(1):58-609 K.P. Soman, Shyam Diwakar, V. Ajay印度.数据挖掘基础教程M.范明,牛常勇译.北京: 机械工业出版社, 200910钟义信. 机器知行学原理：信息、知识、智能的转换与统一理论M.北京:科学出版社,2007指导教师意见 签名： 年 月 日教研室主任意见 签名： 年 月 日目录摘要1关键字1引言11 信息、知识、智能转换的统一理论21.1信息、知识、智能简要概述21.1.1信息的基本概念21.1.2知识的基本概念21.1.3智能的基本概念21.2信息、知识、智能的转换机制22

11、数据挖掘和知识发现32.1数据挖掘和知识发现的概念32.1.1数据挖掘的基本概念32.1.2知识发现的基本概念42.2数据挖掘的分析方法42.3知识发现的过程步骤及技术42.3.1知识发现过程的步骤42.3.2知识发现技术53 数据挖掘算法分析63.1关联规则挖掘算法基本概述63.2 Apriori算法基本原理与优化分析63.2.1 Apriori算法基本原理63.2.2 Apriori算法优化分析83.3 Apriori算法的实现与应用93.3.1 Apriori算法的实现93.3.2 Apriori算法在购物篮中的应用134 具有语义最小支持度的关联规则挖掘方法145 小结15参考文献16

12、Abstract16Key Word17致谢176 信息、知识、智能的转换和算法分析网络工程专业 指导老师： 摘要 21世纪是信息、知识的世纪，信息成为支撑人类社会发展的三大要素之一。而以知识为主题的许多新研究也层出不穷，推动了以网络为基础的信息技术向着更高层次发展。随着经济全球化进程的日益加快，商家间的竞争也日趋激烈，客户演变为商家竞争的核心，一旦无法为客户提供更高价值或更好地的服务，商家的存在价值必定受到质疑，甚至被淘汰。所以，了解顾客是商家必要的生存之道。本文以超市的“购物篮”为例，结合机器知行学原理，采用数据挖掘技术，帮助商家挖掘客户以往的需求趋势、购买行为及偏好，并预测未来，从而给商

13、家带来巨大的利润。关键字信息、知识、智能；数据挖掘；关联规则挖掘算法引言在全球经济一体化趋势下，面临着来自国内外激烈的双重竞争压力，中国零售企业需要通过各种途径全面提升自身，以保持强劲的竞争力。从目前国内零售企业信息化的现状来看，国内零售商普遍专注于操作层面，而在管理决策层的应用普遍很弱，缺乏战略上的信息化规划与应用。零售是生产与消费之间的供求结合，这种供求的结合其实就是信息整合的过程。努力挖掘信息价值，是现阶段零售企业信息化建设的核心，也是企业提升自身竞争力的重要途径。中国零售企业经历了几十年信息化建设，在企业经营管理、流程及效益上都取得一些成绩。但由于对信息化的利用和作用没有完全了解，信息

14、化可以创造更多更大的价值方面，却被零售企业忽略了。直到今天，我国许多零售企业还仅仅是将POS 机作为一般的收款结账设备来使用。随着交易的不断进行, POS 系统和MIS 系统记录积累的大量销售数据、顾客购买历史记录、货物进出与服务记录等信息却成为了庞大却毫无作用的数据累赘。由此可见，中国零售企业缺乏从数据中寻找知识和思想、挖掘财富、发现决策依据，而这些正是数据挖掘对企业的直接贡献，也是企业信息化的重要体现。1 信息、知识、智能转换的统一理论1.1信息、知识、智能简要概述1.1.1信息的基本概念任何一门科学都有自己的基本概念，传统科学的基本概念是物质和能量，信息科学的基本概念是信息。它既是信息科

15、学的出发点，也是它的归宿，而信息科学的出发点是认识信息的本质和它的运动规律，它的归宿则是利用信息来解决各种各样的实际问题，达到各种具体的目的。全信息的主要特色是全面考虑了信息的形式因素、内容因素和价值因素，是在Shannon信息理论基础上发展出来的信息理论。而把仅仅计及其中的形式因素的信息部分称为“语法信息”，把计及其中的含义因素部分称为“语法信息”，把计及其中效用因素的信息部分称为“语用信息”。当机器被设计者赋予特定的“目的性”之后，机器就可以具有很强的感知能力、一定的理解能力、特定的“目的性”，因此，表现外在形式因素的语法信息、表现内在含义因素的语义信息以及表现效用因素的语用信息就变得非常

16、现实了。1.1.2知识的基本概念知识，是信息加工的规律性产物。它是由经验总结升华出来的，属于认识论范畴的概念，它所表述的事物运动的状态和状态变化的规律，任何知识都由相应的形态性知识、内容性知识、效用性知识构成。然而，形态性知识、内容性知识、效用性知识分别与全信息的语法信息、语义信息、语用信息之间有内在的联系。1.1.3智能的基本概念智能，就是在给定问题、问题的环境约束和求解问题的目标的前提下，有效地获得相关信息、把信息提炼成为相应的知识和解决问题的策略、利用策略来解决问题、从而在满足约束条件下成功地达到目的的能力。智能是具体的概念，而不是玄空的概念，它是一种获得信息、处理信息和利用信息生成知识

17、和策略的能力。1.2信息、知识、智能的转换机制一般而言，智能是一种利用知识和信息来解决问题和达到目的的能力。智能生成机制首先将本体论信息转换为认识论信息，从认识论信息中提炼知识。再次将知识转换成智能策略，在生成求解问题的智能策略之后，把智能策略转换为智能行为，使实际问题得到真正的解决。在给定“问题-约束的知识和信息以及预设目标”之后，一般求解智能策略方法原则上是可行的。但是，由于所利用的知识处于不用的生长阶段，这个一般性的原理将会有不同的具体实现方式。如图1-1所示图1-1信息-知识-智能转换：智能生成的共性核心机制2 数据挖掘和知识发现2.1数据挖掘和知识发现的概念2.1.1数据挖掘的基本概

18、念数据挖掘（Data Mining）是一个多科学交叉研究领域，它融合了数据库技术、人工智能、机器学习、统计学、知识工程、面向对象方法、信息检索、高性能计算以及数据可视化等最新技术的研究成果。关于数据挖掘的定义还没有达成一致,当今对数据挖掘有如下几种定义：（1）G.Piatetsky Shapior,W.J.Frawley等定义数据挖掘为从数据库的大量数据中揭示出隐含的、先前未知的、潜在有用的信息的非平凡过程。（2）有人简单认为数据挖掘视是数据库中知识发现过程的一个基本步骤。（3）有人认为数据挖掘是发现数据中隐藏的模式和关系的过程。（4）有人认为数据挖掘就是从大量数据中提取或挖掘知识。（5）Fa

19、yyad等在“知识发现96国际会议”上认为,知识发现是从数据库中发现知识的全部过程,而数据挖掘则是此全部过程种一个特定的关键一步。这种观点将数据挖掘的对象仅仅局限于数据库。（6）数据挖掘广义的定义为在一些事实或观察数据的集合中寻找模式的决策支持的过程。我们可以从上面的定义中看出,数据挖掘是从大量数据中寻找到有价值有意义有趣事先未知的知识，一种透过数理模式来分析企业内储存的大量资料，以找出不同的客户或市场划分，分析出消费者喜好和行为的方法。2.1.2知识发现的基本概念数据库中的知识发现(Knowledge Discovery in Database简称KDD)是在1989年8月美国底特律市召开的

20、第十一届国际联合人工智能学术会议上正是形成。从1995年开始,每年举行一次知识发现国际学术会议,把对数据挖掘和知识发现的研究推向了高潮。知识发现（即KDD）是从数据集中识别出有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程。知识发现将信息变为知识，从数据矿山中找到蕴藏的知识金块，将为知识创新和知识经济的发展作出贡献。2.2数据挖掘的分析方法数据挖掘的分析方法是利用数据来建立一些模仿真实世界的模型，利用这些模型来描述数据中的模式以及关系。提供决策所需要的信息和预测是这些模型的用处。当今先进的数据挖掘工具都提供了许多种可供选择的数据挖掘算法。这是因为每一种算法不可能完成所有不同类型的数

21、据挖掘任务。进行数据挖掘时可以采用不同的算法。数据挖掘技术常见的方法有关联规则、决策树、神经网络、粗糙集方、聚类方法、遗传算法和统计分析方法等。数据挖掘可以建立六种模型：分类（Classification）、回归（Regression）、时间序列（Time Series）、聚类（Clustering）、关联规则（Association）以及顺序规则（Sequence）。分类以及回归主要是用来作预测，而关联规则与顺序规则主要是用来描述行为（例如消费行为）。聚类则是二者都可以用得上的。2.3知识发现的过程步骤及技术2.3.1知识发现过程的步骤知识发现过程有多种描述，然而只是在组织和表达方式上有所不

22、同，在内容上并没有非常本质的区别。图2-1是一个多阶段处理模型，知识发现过程包括以下步骤：（1）问题的理解和定义：数据挖掘人员与领域专家合作，对问题进行深入的分析，以确定可能的解决途径和对学习结果的评测方法。（2）相关数据收集和提取：根据问题的定义收集有关的数据。在数据提取过程中，可以利用数据库的查询功能以加快数据的提取速度。（3）数据预处理：了解数据库中字段的含义及其与其它字段的关系。对提取出的数据进行合法性检查并清理含有错误的数据。主要包括选择相关的属性子集并剔除冗余属性、根据知识发现任务对数据进行采样以减少学习量以及对数据的表述方式进行转换以适于学习算法等。（4）数据挖掘：根据数据和所要

23、解决的问题选择合适的数据挖掘算法，并决定如何在这些数据上使用该算法。根据选定的数据挖掘算法对经过处理后的数据进行模式提取。（5）结果的评价：对学习结果的评价依赖于需要解决的问题。由领域专家对发现的模式的新颖性和有效性进行评价。KDD过程使用数据挖掘算法根据特定的度量方法和阈值从数据库中提取或识别出知识，这个过程包括对数据库的预处理、样本划分和数据变换。图2-1 KDD阶梯处理过程模型2.3.2知识发现技术目前，知识发现技术种类繁多，按挖掘的方法分有数据驱动型、查询驱动型和交互型；按被挖掘对象分有基于关系数据库、多媒体数据库；按知识类型分有关联规则、特征挖掘、分类、聚类、总结知识、趋势分析、偏差

24、分析、文本采掘。知识发现技术可分为两类：基于算法的方法和基于可视化的方法 。大多数基于算法的方法是在人工智能、信息检索、数据库、统计学、模糊集和粗糙集理论等领域中发展来的。典型的基于算法的知识发现技术包括：或然性和最大可能性估计的贝叶斯理论 、衰退分析、最近邻、决策树、K一方法聚类、关联规则挖掘 、Web和搜索引擎、数据仓库和联机分析处理(Online Analytical Processing，OLAP) 、神经网络、遗传算法、模糊分类和聚类、粗糙分类和规则归纳等。3 数据挖掘算法分析3.1关联规则挖掘算法基本概述Agrawal等人于1993年首次提出了关联规则挖掘，最初的动机是针对购物篮分

25、析（Basket Analysis）问题提出的，其目的是为了发现交易数据库中的不同商品之间的相关关系。之后，诸多的研究人员对关联规则的挖掘问题进行大量的研究，用来揭示数据之间未知的相关依赖关系，它是数据挖掘中最为活跃的研究方法之一。一个事务数据库中的关联规则挖掘可以描述如下：设I=,.,是一个项目集合,事务数据库D=,.,是由一系列具有唯一标识TID的事务组成,每个事务 (i=1,2,.,n)都对应I上的一个子集。设I，项目集在数据集D上的支持度（Support） 是包含的事物在D中所占的百分比，即support()=|tD|t|/|D|。对项目集I和事务数据库D，T中所有满足用户指定的最小支

26、持度的项目集，即大于或等于最小支持度的I非空子集，称为频繁项目集或者大项目集。在频繁项目集中挑选出所有不被其它元素包含的频繁项集称为最大频繁项目集或最大项目集。一个定义在I和D上的形如的关联规则通过满足一定的可信度或置信度（Confidence）来给出。可信度是指包含和的事务与包含的事务数之比，即Confidence()=support()/support(),其中,I；=。把D在I上满足最小支持度和最小置信度的关联规则称为强关联规则。通过用户给定的最小支持度，寻找所有频繁项目集，即满足支持度不小于最小支持度的所有项目子集。发现所有的频繁项目集是形成关联规则的基础，在此基础上寻找置信度不小于最

27、小置信度则是生成关联规则。3.2 Apriori算法基本原理与优化分析3.2.1 Apriori算法基本原理Apriori算法是一个基于两阶段频集思想的方法，关联规则挖掘算法的设计可以分解为两个子问题：（1）找到所有支持度大于最小支持度的项集（Itemset），这些项集称为频集（Frequent Itemset)。（2）使用第1步找到的频集产生期望的规则。具体地说，在第一次循环时，经扫描数据库得到1阶频繁集，在之后的第k（k1）次循环中，对第k-1阶频繁项集Lk-1实施Apriro_gen运算生成k阶侯选集Ck。再次扫描数据库，得到Ck的支持度，从而得到Ck中支持度不小于最小支持度的k阶频繁项

28、集Lk。重复以上步骤，直到某一阶的频繁项集为空时算法停止。为生成所有频繁项集，Apriori使用了递推的方法,其核心思想是：（1）L1= find_frequent_1-itemsets(D);（2） for (k=2;Lk-1 ;k+) （3）Ck= apriori_gen(Lk-1,min_sup);（4）for each transaction t D/scan D for counts（5）Ct= subset(Ck,t);/get the subsets of t that are candidates（6）for each candidate c Ct（7）c.count+;（8）

29、（9）Lk=c Ck|c.countmin_sup（10）（11） return L= kLk;如何利用Lk和如何找到Lk是Apriori的关键所在，主要有如下两个步骤：（1）连接步。为找Lk,通过Lk-1与自己连接产生侯选k-项集的集合。该侯选项集的结合记作Ck。（2）剪枝步。Ck是Lk的超集，即它的成员可以是也可以不是频繁的，但所有的频繁k-项集都包含在Ck中。发现频繁集中调用了apriori-gen(Lk-1)，是为了通过(k-1)-频繁项集产生K-候选集。产生候选集可以描述如下：（1）FOR all itemset pLk-1 DO（2） FOR all itemset qLk-1 D

30、O （3）IF p.item1=q.item1,p.item2=q.item2, p.itemk-2=q.itemk-2,p.itemk-1q.itemk-1 THEN BEGI(4) c=pq;(5) IF has_infrequent_subset(c,Lk-1)THEN(6) delete c;(7) ELSE add c to Ck;(8) END(9) Return Ck;根据Agrawal的项目集格空间理论，含有非频繁项子集的元素不可能是频繁项目集，候选集生成算法中调用了has_infrequent_subset(c,Lk-1),是为了判断c是否需要加入到候选集中，以便及时裁减那些

31、含有非频繁项集子集的项集，以提高效率。判断候选集的元素算法描述如下：(1)FOR all (k-1)-subsets of c DO(2) IF SLk-1 THEN Return TRUE;(3)Return FALSE;Apriori算法是通过项集元素数目的不断增长来逐步完成频繁项目集的发现，在得到所有频繁项集后，从给定的频繁项集中生成强关联规则。强关联规则算法可以描述如下：Rule-generate(L,minconf)(1) FOR each frequent itemset lK in L(2) genrules(lk,lk);该算法的核心是genrules递归过程，它实现一个频繁项

32、集中所有强关联规则的生成。3.2.2 Apriori算法优化分析虽然Apriori算法自身已经进行了一定的优化，但是在实际的应用中，还是存在不令人满意的地方，于是人们相继提出了一些优化的方法：（1）基于划分的方法。Savasere等人设计了一个基于划分(partition)的算法，这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。上面所讨论的算法是

33、可以高度并行的，可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后，处理器之间进行通信来产生全局的候选k-项集。通常这里的通信过程是算法执行时间的主要瓶颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶颈。其它的方法还有在多处理器之间共享一个杂凑树来产生频集。（2）基于hash的方法。一个高效地产生频集的基于杂凑(hash)的算法由Park等人提出来。通过实验可以发现寻找频集主要的计算是在生成频繁2-项集Lk上，Park等就是利用了这个性质引入杂凑技术来改进产生频繁2-项集的方法。（3）基于采样的方法。基于前一遍扫描得到的信息，对此仔细地作组合分析，可以得到一个改进

34、的算法，Mannila等人考虑了这一点，他们认为采样是发现规则的一个有效途径。随后又由Toivonen进一步发展了这个思想，先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。Toivonen的算法相当简单并显着地减少了I/O代价，但是一个很大的缺点就是产生的结果不精确，即存在所谓的数据扭曲(data skew)。分布在同一页面上的数据时常是高度相关的，可能不能表示整个数据库中模式的分布，由此而导致的是采样5%的交易数据所花费的代价可能同扫描一遍数据库相近。Lin和Dunham讨论了反扭曲(Anti-skew)算法来挖掘关联规则，他们引入的技

35、术使得扫描数据库的次数少于2 次，算法使用了一个采样处理来收集有关数据的次数来减少扫描遍数。Brin等人提出的算法使用比传统算法少的扫描遍数来发现频集，同时比基于采样的方法使用更少的候选集，这些改进了算法在低层的效率。具体的考虑是，在计算k-项集时，一旦我们认为某个(k+1)-项集可能是频集时，就并行地计算这个(k+1)-项集的支持度，算法需要的总的扫描次数通常少于最大的频集的项数。这里他们也使用了杂凑技术，并提出产生“相关规则”（Correlation Rules）的一个新方法，这是基于他们工作基础上的。（4）减少交易的个数，减少用于未来扫描的事务集的大小。一个基本的原理就是当一个事务不包含

36、长度为k的大项集，则必然不包含长度为k+1的大项集。从而我们就可以将这些事务移去，这样在下一遍的扫描中就可以要进行扫描的事务集的个数。这个就是AprioriTid的基本思想。3.3 Apriori算法的实现与应用3.3.1 Apriori算法的实现根据Apriori算法的思想，用VC+编辑器编写代码的相关步骤如下:（1）对函数进行声明：# include # include # include （2）定义一个无类型有返回值的sum函数；n,m,s为整型变量，分别表示事务数、项数和支持数；d是双精度型；h表示有多少个项，K表示是第几个频繁项集,y表示前有多少项规则，qian存前件，hou存后件，

37、credit存置信度。void sum(int t3020);int get(int t3020,int a10020,int b10020,int k0,int k,int h);int jield(int t3020,int l10020,int k,int h,int qian5010,int hou5010,int y,double credit50);int n,m; double s,d; （3）定义一个不返回任何值得主函数void main()。在函数里，每个行数组中的第一个用来计数，如：t10=3表示第二行有三个元素；cki用于记录一个集中有多少个频繁项集；k1用于记录L1中项

38、数；lk0表示第一项存出现次数，total为频繁项集的总计数。（4）生成频繁项集函数：int get(int t3020,int a10020,int b10020,int k0,int k,int h)/ko表示L中前K-2一共有多少项，表起点；K表示K-1上一次有多少项，H表示L中有几位数有用if (k=0) return(0);int ab10020; int i,j,p,q,m1,x,y,k1,z,z1; y=0; /用于记数产生了多少条项集z=0; /用于记录有用的项集int c100; /计数 int dch100;int biao100;for(i=0;i100;i+)ci=0;

39、 dchi=0; biaoi=0;for(i=k0;ik0+k;i+)for(j=i+1;jk0+k;j+) for(k1=0;k1100;k1+) ck1=0; m1=0;for(p=1;ph;p+)for(q=1;qh;q+)if(aip=ajq)m1+; cq=1;if(m1=h-2) /第一项存出现次数for(x=1;xh;x+)abyx=aix;for(x=1;xh;x+)if(cx=0) abyh=ajx; y+;for(k1=0;k1y;k1+)z1=0;for(i=0;in;i+) z=0;for (j=1;j=h;j+)for(x=1;x=s) dchk1=1; abk10=

40、z1; for(i=0;iy;i+) for(j=i+1;jy;j+) m1=0; for(p=1;p=h;p+) for(q=1;q=h;q+)if(abip=abjq)m1+; if(m1=h) biaoj=1; x=k+k0; z=0;for(i=0;iy;i+) if(dchi=1&biaoi=0) for(j=0;j=h;j+) bxj=abij; z+; x+; return z;（5）对jield函数作出相应的设置，统计n、m的值，推出关联规则。（相应的代码省略）3.3.2 Apriori算法在购物篮中的应用通常，我们将客户一次购买商品的总和称为一个购物篮。在零售行业中，我们可以

41、把关联规则和Apriori算法应用于研究顾客购物篮中，以期发现顾客购物规律。一个购物篮就是一张收款小票，购物小票就是购物篮分析的一个重要依据。一张购物小票包含3个层面的含义：购买商品的客户、购物篮的商品和购物篮的金额。在数据分析行业中，将购物篮的商品相关性分析称为“数据挖掘算法之王”，可见购物篮商品相关分析算法的重要性。对购物篮分析即从购物篮的商品相关度分析入手，表3-1为购物数据内容。表3-1购物内容Class(商品名称)Price(单价/元)Sum(购买总数)面包3.50300果冻2.80600花生酱8.80400牛奶4.00600啤酒4.50500可乐3.00100由于本次挖掘只是针对购

42、物篮的商品相关性进行分析，不进行多层的关联规则挖掘，因此不必进行概念分层及数据离散化处理。随机搜取4个购物篮，5个项数作为采点数据，模拟实验样本数据如表3-2。表3-2 模拟实验样本数据购物篮编号项目集支持度计数代号A1、3、43“1”表示面包，“2”表示果冻，“3”表示花生酱，“4”表示牛奶“5”表示啤酒B2、3、53C1、2、3、54D2、52为了了解商品间的关联关系，顾客买了果冻是否就一定会买啤酒。要求挖掘出支持度大于等于60、置信度大于等于80%的商品间的关联。结果如图3-1所示。图3-1 Apriori算法设计实现结果从图3-1可以看出，在购物数据样本模拟实验中，发现了以下规则：顾客

43、如果购买面包（花生酱、啤酒或果冻、花生酱），那么购买花生酱（果冻或啤酒）的可能性是100%；如果，顾客购买果冻，那么购买啤酒的可能性是100%；反之，如果顾客购买啤酒，那么购买果冻的可能性是100%。由此可以得出：该商城在商品排放策略上应该将啤酒、果冻、花生酱的货架相邻摆设。4 具有语义最小支持度的关联规则挖掘方法传统的关联规则挖掘算法大都依赖于一个统一的支持度和置信度阈值设置，项目的最小支持度是限制关联规则产生的数量的主要因素。可是事件在现实中发生和存在频度上有很大的不一致性，始终保持单一的最小支持度显然是不合理，就此问题，人们采用多个支持度的关联规则方法来解决单一支持度的不可靠问题。然而马占欣等人则提出加入项集之间的“相关度”来对关联规则的挖掘进行约束。以下将语义信息引入关联规则挖掘之中，提出了具有语义最小支持度的关联规则挖掘。设I=,.,