资源描述：
《挖掘大型数据库中的Apriori算法及其改进》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第22卷第1期 中南民族大学学报(自然科学版)Vol.22No.12003年3月 JournalofSouth2CentralUniversityforNationalities(Nat.Sci.Edition)Mar.2003a挖掘大型数据库中的Apriori算法及其改进宋中山(中南民族大学计算机科学学院)摘 要 指出了Apriori算法是一种有效的关联规则挖掘算法,分析和探讨了Apriori算法,并给出了该算法的实现思想,通过实例说明了算法的执
2、行过程,提出了对Apriori算法进行改进的一些方法:散列、事务压缩、划分、选样及动态项集计数.使用这些技术提高了算法的效率.关键词 数据挖掘;关联规则;Apriori算法;频繁项集中图分类号 TP311.13文献标识码 A 文章编号 100523018(2003)0120054204 自1995年第1届知识发现和数据挖掘国际会议当且仅当AAT.则关联规则是形如A]B的蕴涵式,在加拿大召开以来,数据挖掘技术已成为机器学习、数其中AAI,BAI,并且A∩B=5.规则A]B在事[1]据库系统、人工智
3、能等领域内热门研究方向.数据挖务集D中成立,具有支持度s,其中s是D中事务包含掘又称为数据库中的知识发现,从大量的数据库记录A∪B(即A和B二者)的百分比,即概率P(A∪B).中提取关联规则是数据挖掘技术中的一个重要研究如果D中包含A的事务同时也包含B的百分比是c,规课题.则A]B在事务集D中具有置信度c,即条件概率关联规则一个典型的例子就是:“90%的客户在购P(BûA),也即:买面包的同时也会购买牛奶”,其直观意义为顾客在购support(A]B)=P(A∪B),买某些商品的时候有多大的倾向会
4、购买另外一些商confidence(A]B)=P(BûA).品.关联规则挖掘发现大量数据中项集之间有趣的关例如,购买计算机也趋向于同时购买财务管理软件的,联或相关联系.随着大量数据不停地收集和存储,许多可以用以下关联规则表示:业界人士对于从他们的数据库中挖掘关联规则越来越computer]financialmanagementsoftware感兴趣.从大量商务事务记录中发现有趣的关联关系,[support=2%,confidence=60%]可以帮助许多商务决策的制定,如分类设计、交叉购物支持度2
5、%意味分析中的全部事务的2%同时购和贱卖分析.关联规则广泛地应用于商业界、医疗保买计算机和财务管理软件.置信度60%意味购买计算险、金融业、司法部门等,因此对它的研究有着极其重机的顾客60%也购买财务管理软件.要的意义.同时满足最小支持度(minsup)和最小置信度(minconf)的规则称作强规则.关联规则挖掘可定义1 关联规则为:给定一个事务数据库D,寻找出所有满足s>minsup,c>minconf的关联规则A]B.[2]关联规则的概念是由Agrawal首先提出的.关项的集合称为项集(ite
6、mset).包含k个项的项集联规则是表示数据库中一组对象之间某种关联关系的称为k2项集.集合{computer,financialmanage2[3]规则.问题是这样描述的:设I={i1,i2,⋯,im}是项mentsoftware}是一个22项集.项集的出现频率是的集合,任务相关的数据D是数据库事务的集合,其中包含项集的事务数,简称为项集的频率、支持计数或计每个事务T是项的集合,使得TAI.每一个事务有一数.如果项集的出现频率大于或等于minsup与D个标识符,称作TID,设A是一个项集,事务T
7、包含A中事务总数的乘积,称项集满足最小支持度mina收稿日期 2002211224作者简介 宋中山(19632),男,副教授,研究方向:数据库和计算机网络,武汉430074基金项目 国家民委科研基金资助项目(990101)©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.第1期 宋中山:挖掘大型数据库中的Apriori算法及其改进 55sup.如果项集满足最小支持度,则称
8、它为频繁项集.频是也可以不是频繁的,但所有的频繁k2项集都包含在繁k2项集的集合通常记作Lk.Ck中.扫描数据库,确定Ck中每个候选的计数,从而确关联规则的挖掘可以分解为以下2个过程:定Lk(即根据定义,计数值不小于最小支持度计数的所(1)找出所有频繁项集:根据定义,这些项集出现有候选是频繁的,从而属于Lk).然而,Ck可能很大,这的频繁性至少和预定义的最小支持计数一样.样所涉及的计算量就很大.为压缩Ck,可以用性质:任(2)由频繁项集产生强关联规则:根据定义,这些何非频繁的(k-
