Apriori算法及其改进算法

Apriori算法及其改进算法 陕西理工学院 学生姓名 丁侃 所在班级专业 01级计算机本科乙班 所在系别 数学与计算机科学系 指导教师姓名 周涛 陕西理工学院数学与计算机科学系制 2005年6月1日 Apriori算法改进及其实现 内容摘要 信息技术的不断推广应用，将企业带入了一个信息爆炸的时代。如何充分利用这些数据信息为企业决策者提供决策支持成为一个十分迫切的又棘手的问题，人们除了利用现有的关系数据库 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 查询语句得到一般的直观的信息以外，必须挖掘其内含的、未知的却又实际存在的数据关系。著名的Apriori算法是一种挖掘关联规则的算法。 本文通过对参与候选集的元素计数的方法来减少产生候选集的组合和减少数据库的扫描次数来达到要求。这有利于提高挖掘的速度和减少数据库的I/O操作时间的开销。 关键字:数据挖掘，关联规则，Apriori算法 Apriori Algorithm And Improved Apriori Algorithm Abstract:An information burst age is coming with the various application of Information technology. How to maximize the information is a very important problem for the decision-maker of the companies. Besides getting the regular information from the Database by SQL-query, people still need to mine the data relation which is unclear but really exists.Association rules is one of the data mining methods, the famous algorithm Apriori is a method, which can be used to solute those problems. This article analyzes and studies the improved algorithm Apriori based on the algorithm of mining association rules Apriori. The main idea is to decrease the number of candidate items and to decrease the times of Database scanning. The solution is available. It upgrades the speed of data mining and decreases computer's I/O operation. It's proved to be more efficient than the traditional Key words: Datamining, association rules, Apriori algorithm, 目录 1 数据挖掘.................................................................................................................................. - 1 - 1.1 技术上的定义及含义 .................................................................................................. - 1 - 1.2 商业角度的定义 .......................................................................................................... - 2 - 1.3 数据挖掘与传统分析方法的区别 .............................................................................. - 2 - 1.4数据挖掘不能干什么 ................................................................................................... - 3 - 2 数据挖掘的几种主要形式: .................................................................................................... - 3 - 2.1:规则挖掘: .................................................................................................................. - 3 - 2.2聚类分析: ................................................................................................................... - 4 - 3 关于关联规则的讨论 .............................................................................................................. - 4 - 3.1购物篮分析 ................................................................................................................... - 4 - 3.2 关联规则基本问题描述 .............................................................................................. - 4 - 3.3 关联规则挖掘举例 ...................................................................................................... - 6 - 3.4 关联规则问题的分解 .................................................................................................. - 8 - 4 Apriori算法的描述 ............................................................................................................... - 8 - 4.1 Apriori算法的说明 ................................................................................................... - 8 - 4.2 Apriori算法的描述 ................................................................................................... - 9 - 4.3 Apriori算法的举例 ................................................................................................. - 11 - 5 一种Apriori的改进算法 .................................................................................................... - 14 - 5.1算法产生的思路 ......................................................................................................... - 14 - 5.2算法的图例说明 ......................................................................................................... - 15 - 5.3本算法的评价: ........................................................................................................... - 15 - 附录1 程序运行图示 ............................................................................................................... - 18 - 附录2 程序代码 ....................................................................................................................... - 20 - 陕西理工学院数学与计算机科学系开放性实验结题 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 1 数据挖掘 1.1 技术上的定义及含义 数据挖掘(Data Mining)就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。这个定义包括好几层含义:数据源必须是真实的、大量的、含噪声的;发现的是用户感兴趣的知识;发现的知识要可接受、可理解、可运用;并不要求发现放之四海皆准的知识，仅支持特定的发现问题。 ----何为知识?从广义上理解，数据、信息也是知识的表现形式，但是人们更把概念、规则、模式、规律和约束等看作知识。人们把数据看作是形成知识的源泉，好像从矿石中采矿或淘金一样。原始数据可以是结构化的，如关系数据库中的数据;也可以是半结构化的，如文本、图形和图像数据;甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的;可以是演绎的，也可以是归纳的。发现的知识可以被用于信息管理，查询优化，决策支持和过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行计算等方面的学者和 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 技术人员，投身到数据挖掘这一新兴的研究领域，形成新的技术热点。 这里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去发现崭新的自然科学定理和纯数学 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 ，更不是什么机器定理证明。实际上，所有发现的知识都是相对的，是有特定前提和约束条件，面向特定领域的，同时还要 - 1 - 陕西理工学院数学与计算机科学系开放性实验结题报告 能够易于被用户理解。最好能用自然语言表达所发现的结果。 1.2 商业角度的定义 数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性数据。 简而言之，数据挖掘其实是一类深层次的数据分析方法。数据分析本身已经有很多年的历史，只不过在过去数据收集和分析的目的是用于科学研究，另外，由于当时计算能力的限制，对大数据量进行分析的复杂数据分析方法受到很大限制。现在，由于各行业业务自动化的实现，商业领域产生了大量的业务数据，这些数据不再是为了分析的目的而收集的，而是由于纯机会的(Opportunistic)商业运作而产生。分析这些数据也不再是单纯为了研究的需要，更主要是为商业决策提供真正有价值的信息，进而获得利润。但所有企业面临的一个共同问题是:企业数据量非常大，而其中真正有价值的信息却很少，因此从大量的数据中经过深层分析，获得有利于商业运作、提高竞争力的信息，就像从矿石中淘金一样，数据挖掘也因此而得名。 因此，数据挖掘可以描述为:按企业既定业务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的先进有效的方法。 1.3 数据挖掘与传统分析方法的区别 数据挖掘与传统的数据分析(如查询、报表、联机应用分析)的本质区别是数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识.数据挖掘所得到的信息应具有先未知,有效和可实用三个特征. - 2 - 陕西理工学院数学与计算机科学系开放性实验结题报告 先前未知的信息是指该信息是预先未曾预料到的,既数据挖掘是要发现那些不能靠直觉发现的信息或知识,甚至是违背直觉的信息或知识,挖掘出的信息越是出乎意料,就可能越有价值.在商业应用中最典型的例子就是一家连锁店通过数据挖掘发现了小孩尿布和啤酒之间有着惊人的联系. 1.4数据挖掘不能干什么 DM 不能告诉你某个模型对你的企业的实际价值DM是一个工具，他只是帮助商业人士更深入、更容易地分析数据，但是无法告诉你某个模型对你的企业的实际价值，DM中得到的模型必须在现实生活中进行验证，DM不会在缺乏指导的情况下自动的发现模型。数据分析者必须知道你所选用的DM工具是如何工作的，采用的算法的原理是什么。DM永远不会替代有经验的商业分析师或管理人员所起的作用，它只是一个强大的工具。 2 数据挖掘的几种主要形式: 2.1:规则挖掘: 如果一个事务中含有X，则该事务中很可能含有Y。具体形式为{X}?{Y}，即通常可以描述为:当一个事务中顾客购买了一样东西{钢笔}(这里X=“钢笔”)则很可能他同时还购买了{墨水}(这里Y= "墨水")，这就是关联规则。在美国，有一种说法是:“尿不湿”和“啤酒”经常一起被购买。这种说法有其一定的现实意义:1)或许是该年龄段的经常喝啤酒的人刚好家庭开始养育小孩;2)或许是因为啤酒喝多，需要用尿不湿。然而不管怎样，如果没有数据挖掘中的关联规则在这里的应用，你是无论如何想象不出这样有点惊人的“笑话”。本文在后面将就该规则作一详细的阐述与讨论。 - 3 - 陕西理工学院数学与计算机科学系开放性实验结题报告 2.2聚类分析: 数据库中的 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 可被化分为一系列有意义的子集，即聚类。聚类增强了人们对客观现实的认识，是概念描述和偏差分析的先决条件。聚类技术主要包括传统的模式识别方法和数学分类学。80年代初，Mchalski提出了概念聚类技术其要点是，在划分对象时不仅考虑对象之间的距离，还要求划分出的类具有某种内涵描述，从而避免了传统技术的某些片面性。 3 关于关联规则的讨论 3.1购物篮分析 关联规则挖掘的一个典型例子是购物篮分析。市场分析员要从大量的数据中发现顾客放入其购物篮中的不同商品之间的关系。如果顾客买牛奶，他也购买面包的可能性有多大, 什么商品组或集合顾客多半会在一次购物时同时购买,例如，买牛奶的顾客有80%也同时买面包，或买铁锤的顾客中有70%的人同时也买铁钉，这就是从购物篮数据中提取的关联规则。分析结果可以帮助经理设计不同的商店布局。一种策略是:经常一块购买的商品可以放近一些，以便进一步刺激这些商品一起销售，例如，如果顾客购买计算机又倾向于同时购买财务软件，那么将硬件摆放离软件陈列近一点，可能有助于增加两者的销售。另一种策略是:将硬件和软件放在商店的两端，可能诱发购买这些商品的顾客一路挑选其他商品。 3.2 关联规则基本问题描述 关联规则是描述数据库中数据项之间存在的潜在关系的规则,形式为“A1?A2?...?Am=>B1?B2?...?Bn”,其中Ai(i=1,2,......,m),Bj(j=1,2,......,n)是数据库中的数据项.数据项之间的 - 4 - 陕西理工学院数学与计算机科学系开放性实验结题报告 关联规则即根据一个事务中某些项的出现,可推导出另一些项在同一事务中也出现. 挖掘关联规则的问题描述如下: 设: 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是大数据项集. 一般由用户给定最小置信度阈值 - 5 - 陕西理工学院数学与计算机科学系开放性实验结题报告 和最小支持度阈值.置信度和支持度大于相应阈值的规则称为强关联规则, 反之称为弱关联规则. 发现关联规则的任务就是从数据库中发现那些置信度、支持度大小等于给定值的强壮规则. 基于上述概念，我们可以很容易得到一些基本结论: (1) K维数据项集X是频繁项集的必要条件是它所有K-1维子项集也为频繁K 项集，记为X K-1 (2)如果K维数据项集X的任意一个K-1维子集X，不是频繁项集，则KKK-1维数据项集X本身也不是最大数据项集。 K (3) X是K维频繁项集，如果所有K-1维频繁项集集合X中包含XK的K-1KK-1维子项集的个数小于K，则X不可能是K维最大频繁数据项集。 K 证明: 很明显，数据项集X:的K-1维子项集的个数为K-1。如果高频繁数据项集K-1 X，中包含X的K-1.维子项集的个数小于k，则存在X的K-1维子项集不是频K-1KK繁数据项集，由结论(2)知K维数据项集本身也不是高频繁数据项集。 3.3 关联规则挖掘举例 一个超级市场的销售系统记录了顾客购物的情况。表3-1中记录了5个顾客的购物单。 记录号 所购物品清单 1 啤酒、尿布，婴儿爽身粉，面包，雨伞 2 尿布，婴儿爽身粉 3 啤酒、尿布，牛奶 4 尿布，啤酒，洗衣粉 5 啤酒，牛奶，可乐饮料 表3-1 - 6 - 陕西理工学院数学与计算机科学系开放性实验结题报告 超市经理想知道商品之间的关联，要求列出那些同时购买的、且支持度?40%(即在5行中至少出现两次)的商品名称。 KDD系统通过特定算法(例如著名的Apriori(验证)算法及或改进算法)多次扫描数据库，依次得出如表2和表3。其中支持度<2/5的项,如单项的{面包}，{雨伞}和 双项中的 {尿布，牛奶}等等已经略去，三项统计为空，其中只有 {啤酒，尿布,牛奶}出现了一次(表3-1中3号记录)，支持度小于40%,略去。 双项统计 支持度 单项统计 支持度 {啤酒，尿布} 3/5 {啤酒} 4/5 {啤酒，牛奶} 2/5 {尿布} 4/5 {尿布，婴儿爽身粉} 2/5 {婴儿爽身粉} 2/5 {牛奶} 2/5 表3-2 表3-3 从单项统计中看出80%的顾客买了啤酒、80%的顾客买了尿布。从双项统计中看出，60%的顾客同时买了啤酒和尿布，40%的顾客买了啤酒和牛奶，40%的顾客买了尿布和爽身粉。还可观察到买了啤酒顾客中又买了尿布的占0.6{啤酒，尿布}/0.8{啤酒}=75% (称为置信度)。于是可得出下列六条规则,其中:s为支持度，c为置信度。 R1:啤酒?尿布,S=60%，C=0.6/0.8=75% R2:尿布?啤酒,S=60%，C=0.6/0.8=75% R3:牛奶?啤酒, S=40%，C=0.4/0.4=100% R4:啤酒?牛奶, S=40%，C=0.4/0.8=50% R5:尿布?爽身粉。S=40%，C=0.4/0.8=50% R6:婴儿爽身粉?尿布。S=40%，C=0.4/0.4=100% - 7 - 陕西理工学院数学与计算机科学系开放性实验结题报告 KDD规则反映了物品之间的表面联系，不一定是现实世界的因果关系。规则是死的，人是活的，运用之妙成乎于人。例如，R6“婴儿爽身粉?尿布”有很高的置信度，是合理可理解的，R3有很高的置信度将提示进一步的调查分析，本例中是因为训练资料太少引起的失真。 3.4 关联规则问题的分解 关联规则挖掘问题可分解为以下两个子问题: 1. 找出事务数据库D中所有大于等于用户指定最小支持度的项目集(itemset). 具有最小支持度的项目集称为最大项目集.项目集的支持度指包含该项目集 的数目. 2. 利用最大项目集生成所需要的关联规则 对每一最大项目集A,找到A的所有非空子集a,如果比率 support(A)/support(a)>=minconfidence,就生成关联规则a=>(A-a).suppor t(A)/support(a) 即规则a=>(A-a)的置信度. 事实上,挖掘关联规则的整个执行过程中第一个子问题是核心问题.当找到所 有的最大项目集后,相应的关联规则将很容易生成.在本文中将对关联规则的 第一个问题进行探讨、研究。 4 Apriori算法的描述 4.1 Apriori算法的说明 在Apriori算法中,寻找最大项目集的基本思想是: 算法需要对数据集进行多步处理.第一步,简单统计所有含一个元素项目集出现的频率,并找出那些不小于最小支持度的项目集, 即一维最大项目集. 从第二步开始循环处理直到再没 - 8 - 陕西理工学院数学与计算机科学系开放性实验结题报告 有最大项目集生成. 循环过程是: 第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计算支持度. Apriori算法描述如下 (1) C1={candidate1-itemsets}; (2) L1={c?C1|c.count?minsupport}; (3) For(k=2,Lk-1?Φ,k++) //直到不能再生成最大项目集为止 - 9 - 陕西理工学院数学与计算机科学系开放性实验结题报告 (4) Ck=sc_candidate(Lk-1); //生成含k个元素的侯选项目集 (5) for all transactions t?D //办理处理 (6) Ct=count_support(Ck,t); //包含在事务t中的侯选项目集 (7) for all candidates c?Ct (8) c.count=c.count+1; (9) next (10) Lk={c?Ck|c.count?minsupport}; (11) next (12) resultset=resultset?Lk 其中, D表示数据库; minsupport表示给定的最小支持度; resultset表示所有最大项目集. Sc_candidate函数 该函数的参数为Lk-1,即: 所有最大k-1维项目集,结果返回含有k个项目的侯选项目集Ck.事实上,Ck是k维最大项目集的超集,通过函数count_support计算项目的支持度,然后生成Lk. 该函数是如何完成这些功能的, 详细说明如下: 首先, 通过对Lk-1自连接操作生成Ck',称join(连接)步, 该步可表述为: insert into Ck selectP.item1,P.item2,......P.itemk-1,Q.itemk-1 from Lk-1P,Lk-1Q whereP.item1=Q.item1,......P.itemk-2=Q.itemk-2,P.itemk-1=minsupport, 若c的子集为c', 则c'.count必然大于等于minsupport. 所以c'也为最大项目集. (2) 在prune步中, 删除Ck'中那些所有k-1维子集不在Lk-1中的项目集, (其中k-1维子集为Ck的所有项目数为k-1的子集). 这里用了(1)中的性质: 最大项目集的子集必为最大项目集. 即若某项目集的(k-1)维子集不是最大项目集(Lk-1中包含所有k-1维最大项目集), 则该项目集不是最大项目集. 所以将删除Ck'中所有不在Lk-1中的k-1维子集. count_support函数 count_support函数为是以t和 Ck 为条件. 来求出t 中所包含的侯选项目集的. 同时计算出所包含的侯选项目集的数目. 4.3 Apriori算法的举例 示例说明Apriori算法运作过程 有一数据库D, 其中有四个事务记录, 分别表示为 - 11 - 陕西理工学院数学与计算机科学系开放性实验结题报告 TID Items T1 I1,I3,I4 T2 I2,I3,I5 T3 I1,I2,I3,I5 T4 I2,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步后, 产生 2，I3，I5}.在prune步中,测试{I2，I3，I5}的子集{I3，I5},{I2，I3},{I2，集合{I 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算法结束. 算法的图例说明 - 12 - 陕西理工学院数学与计算机科学系开放性实验结题报告 从以上的算法执行过程可以看到Apriori算法的缺点: 第一:在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素;第二:每次计算项集的支持度时，都对数据库D中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系 - 13 - 陕西理工学院数学与计算机科学系开放性实验结题报告 统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求一种能减少这种系统1/O开销的更为快捷的算法。 5 一种Apriori的改进算法 5.1算法产生的思路 在Apriori算法中，寻找最大项目集的基本思路是:第一步简单统计所有含一个元素的项目出现的频率，并找出那些大于或等于最小支持度的项目集，产生一维频繁项目集Lt。从第二步开始循环处理直到未能再产生维数更高的频繁项目集。循环过程是:在第k步中，根据k-1步生成的k-1维频繁项目集来产生k维候选项目集，由于在产生k-1维频繁项目集时，我们可以实现对该集中出现元素的个数进行计数处理，因此对某元素而言，若它的计数个数不到k-1的话，可以事先删除该元素，从而排除由该元素将引起的大规格所有组合。这是因为对某一个元素要成为K维项目集的一元素的话，该元素在k-1阶频繁项目集中的计数次数必须达到K-1个，否则不可能生成K维项目集(性质3)。然后再按Apriori算法再检验新的K 维频繁项目集的所有k-1维项目集是否已经包含在已经求出的K-1维频繁项目集。若其中有一个没有包含，则也可删去该组合，这样得到一个真正有用的K维频繁项目集选项目集。得到了这个候选项目集后，可以对数据库D的每一个事务tid进行扫描，若该事务中至少含有候选项目集CK中的一员，则保留该项事务，否则把该事物记录与数据库末端没有作删除标记的事务记录对换，并对移到数据库末端的事务记录作删除标一记，整个数据库扫描完毕后为新 的事务数据库D’ 中。因此随着K 的增大，D’中事务记录量大大地减少，对于下一次事务扫描可以大大节约I/0 开销。由于顾客一般可能一次只购买几件商品，因此这种虚拟删除的方法可以实现大量的交易记录在以后的挖掘中被踢除出来， - 14 - 陕西理工学院数学与计算机科学系开放性实验结题报告 在所剩余的不多的记录中再作更高维的数据挖掘是可以大大地节约时间的。 5.2算法的图例说明 5.3本算法的评价: 通过上述介绍，我们可以看到本算法的思路基本上与Apriori算法保持一致，即它们的共同之处是首先通过扫描数据库D得到那些支持度不小于用户给定的最小支持度minsup的频繁项集L1。然后同样通过多次循环扫描数据库D，分别得到频繁项集L2,L3, . . . ,Lk。但是又有不同之处。第一，改进的算法在 - 15 - 陕西理工学院数学与计算机科学系开放性实验结题报告 考虑组合Ck前，对将参与组合的元素进行计数处理，根据计数结果决定排除一些不符合组合条件的元素，这就降低了组合的可能性，即降低循环判断的次数。如果对大型的数据库而言，这种时间开销的降低对数据挖掘效率来说是显而易见的，这是Apriori方法中没有涉及的;第二，改进的算法对数据库进行了扫描后的重新生成(‘删除’一些不能支持频繁集的记录，这里所谓的删除实际上是把不符合再次扫描比较条件的记录通过交换记录内容的方式移到数据库的末端，把末端新记录填入该记录的位置。同时对数据库中的记录数逻辑地减少。)，虽然会在记录重写中浪费时间和I/O的开销，但是随着循环次数的增加，本算法对以后在‘新生成的数据库’中的扫描比较次数很快减少将逐渐体现出来。从数据挖掘工具的评价标准(1.模式种类的数量，2.解决复杂问题的能力，3.操作性能，4.数据获取能力，5挖掘结果的输出，6.噪声数据的处理及挖掘工具的鲁棒性)来看，本算法可以达到较高的标准;从算法效率的角度来看，本算法的挖掘效率也是较高的。因此本文认为，这种方法在实践应用中也是值得使用的。 - 16 - 陕西理工学院数学与计算机科学系开放性实验结题报告 参考文献 [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 - 17 - 陕西理工学院数学与计算机科学系开放性实验结题报告 附录1 程序运行图示 图1输入数据 图2 设置参数 - 18 - 陕西理工学院数学与计算机科学系开放性实验结题报告 图3 程序运行结果 - 19 - 陕西理工学院数学与计算机科学系开放性实验结题报告 附录2 程序代码 Apriori.cpp // Apriori.cpp : Defines the class behaviors for the application. #include "stdafx.h" #include "Apriori.h" #include "MainFrm.h" #include "AprioriSet.h" #include "AprioriDoc.h" #include "AprioriView.h" #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE[] = __FILE__; #endif ///////////////////////////////////////////////////////////////////////////// // CAprioriApp BEGIN_MESSAGE_MAP(CAprioriApp, CWinApp) //{{AFX_MSG_MAP(CAprioriApp) ON_COMMAND(ID_APP_ABOUT, OnAppAbout) // NOTE - the ClassWizard will add and remove mapping macros here. // DO NOT EDIT what you see in these blocks of generated code! //}}AFX_MSG_MAP // Standard file based document commands ON_COMMAND(ID_FILE_NEW, CWinApp::OnFileNew) ON_COMMAND(ID_FILE_OPEN, CWinApp::OnFileOpen) // Standard print setup command ON_COMMAND(ID_FILE_PRINT_SETUP, CWinApp::OnFilePrintSetup) END_MESSAGE_MAP() ///////////////////////////////////////////////////////////////////////////// // CAprioriApp construction CAprioriApp::CAprioriApp() { // TODO: add construction code here, // Place all significant initialization in InitInstance } - 20 - 陕西理工学院数学与计算机科学系开放性实验结题报告 ///////////////////////////////////////////////////////////////////////////// // The one and only CAprioriApp object CAprioriApp theApp; ///////////////////////////////////////////////////////////////////////////// // CAprioriApp initialization BOOL CAprioriApp::InitInstance() { AfxEnableControlContainer(); // Standard initialization // If you are not using these features and wish to reduce the size // of your final executable, you should remove from the following // the specific initialization routines you do not need. #ifdef _AFXDLL Enable3dControls(); // Call this when using MFC in a shared DLL #else Enable3dControlsStatic(); // Call this when linking to MFC statically #endif // Change the registry key under which our settings are stored. // TODO: You should modify this string to be something appropriate // such as the name of your company or organization. SetRegistryKey(_T("Local AppWizard-Generated Applications")); LoadStdProfileSettings(); // Load standard INI file options (including MRU) // Register the application's document templates. Document templates // serve as the connection between documents, frame windows and views. CSingleDocTemplate* pDocTemplate; pDocTemplate = new CSingleDocTemplate( IDR_MAINFRAME, RUNTIME_CLASS(CAprioriDoc), RUNTIME_CLASS(CMainFrame), // main SDI frame window RUNTIME_CLASS(CAprioriView)); AddDocTemplate(pDocTemplate); // Parse command line for standard shell commands, DDE, file open CCommandLineInfo cmdInfo; ParseCommandLine(cmdInfo); - 21 - 陕西理工学院数学与计算机科学系开放性实验结题报告 // Dispatch commands specified on the command line if (!ProcessShellCommand(cmdInfo)) return FALSE; // The one and only window has been initialized, so show and update it. m_pMainWnd->ShowWindow(SW_SHOW); m_pMainWnd->UpdateWindow(); return TRUE; } ///////////////////////////////////////////////////////////////////////////// // CAboutDlg dialog used for App About class CAboutDlg : public CDialog { public: CAboutDlg(); // Dialog Data //{{AFX_DATA(CAboutDlg) enum { IDD = IDD_ABOUTBOX }; //}}AFX_DATA // ClassWizard generated virtual function overrides //{{AFX_VIRTUAL(CAboutDlg) protected: virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support //}}AFX_VIRTUAL // Implementation protected: //{{AFX_MSG(CAboutDlg) // No message handlers //}}AFX_MSG DECLARE_MESSAGE_MAP() }; CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD) { //{{AFX_DATA_INIT(CAboutDlg) //}}AFX_DATA_INIT - 22 - 陕西理工学院数学与计算机科学系开放性实验结题报告 } void CAboutDlg::DoDataExchange(CDataExchange* pDX) { CDialog::DoDataExchange(pDX); //{{AFX_DATA_MAP(CAboutDlg) //}}AFX_DATA_MAP } BEGIN_MESSAGE_MAP(CAboutDlg, CDialog) //{{AFX_MSG_MAP(CAboutDlg) // No message handlers //}}AFX_MSG_MAP END_MESSAGE_MAP() // App command to run the dialog void CAprioriApp::OnAppAbout() { CAboutDlg aboutDlg; aboutDlg.DoModal(); } ///////////////////////////////////////////////////////////////////////////// // CAprioriApp message handlers - 23 -