Apriori算法改进研究.doc

Apriori算法改进研究.docApriori算法改进研究摘要:Apriori算法作为数据挖掘技术中的经典算法,它在事务数量少的数据库中具有较好性能从而得到了人们的广泛应用,但该算法具有的两个固有缺陷,影响了apriori算法在大数据库中挖掘信息的效率。文中对apriori算法的两个固有缺陷进行改进以便提高apriori算法在大数据库中的挖掘效率。关键词:apriori算法;关联规则;数据挖掘;频繁项目集中图分类号:TP311文献标识码:A文章编号:1009-3044(2013)09-2037-03 数据挖掘是近年来非常活跃的一个研究领域,它是在机器学习、统计学、数据库技术、信息科学的理论基础上发展而成。数据挖掘(DM,DataMining)就是从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取隐含在其中的、人们事先不知道的、但又是潜在的有用信息和知识的过程[1],其主要目的是从大量的数据源提取有用的并且用户感兴趣的知识和模式。数据挖掘的一个重要分支就是关联规则挖掘,关联规则反映的是一个事件跟其他事件之间的关联或依赖,是事务内部的规律或模式,体现了现实世界中事物的关联关系,比如人们从超市销售数据中发现购买啤酒的客户很有可能购买尿布,因此超市管理人员根据这种关联关系将啤酒和尿布摆放在相邻的位置以促进商品的销售。关联规则的形式描述为:设I=[[I1,I2,I3,...,In]]是事务数据库D中所有项的集合,D中每个事务T都有唯一的标识符[Tid],[T?I],A、B为项集,关联规则是形如A=>B的蕴涵式,其中[A?I,B?I,并且A?B=?]。关联规则有两个重要的度量标准:支持度(support)和置信度(confidence)。通常人们在挖掘关联规则时会设置最小支持度阈值(min_sup)和最小置信度阈值(min_conf),我们将支持度大于或等于最小支持度阈值的项集称为频繁项集,将同时满足最小支持度阈值和最小置信度阈值的规则称为强关联规则,否则为弱关联规则,强关联规则才是用户感兴趣的关联规则。关联规则的挖掘过程分为两个步骤: 第一步:根据最小支持度阈值从事务数据库中找出所有的频繁项集。第二步:根据最小置信度阈值由频繁项集生成强关联规则。其中,从事务数据库中发现频繁项集是关联规则挖掘的关键步骤,该步骤决定了关联规则挖掘的整体性能。 1apriori算法 apriori算法是针对关联规则挖掘的第一个步骤,也就是从事务数据库中发现所有的频繁项集,apriori算法采用逐层搜索的迭代方法来生成频繁项集[2],首先扫描事务数据库D,根据用户设置的最小支持度找出数据库D中的1-项频繁项集L1,然后由1-项频繁项集L1进行连接操作生成2-项候选项集C2,再次扫描事务数据库从2-项候选项集C2中找出2-项频繁项集L2,然后再由2-项频繁项集L2进行连接生成3-项候选项集C3,再次扫描事务数据库找出3-项候选项集中的3-项频繁项集L3,依次类推,直到没有更大模式的k-项频繁项集或候选项集为空,则apriori算法结束(如图1)。 1)每次由候选项集生成频繁项集时都需要扫描数据库,而数据库一般都存放在外存上,这样就导致该算法在执行过程中需要很大的I/O负载。 2)频繁项集进行自我连接时会产生大量的候选项集,这些候选项集的存放需要很