资源描述：
《Apriori算法的分析及应用_刘耀南.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第30卷第3期佛山科学技术学院学报(自然科学版)Vol.30No.32012年5月JournalofFoshanUniversity(NaturalScienceEdition)May2012文章编号:1008-0171(2012)03-0070-05Apriori算法的分析及应用刘耀南(嘉应学院继续教育学院,广东梅州514015)摘要:关联规则是数据挖掘领域中最重要的研究内容,能够在数据库中发现频繁模式和关联知识。对关联规则及其相关挖掘算法Apriori进行了分析,指出了Apriori算法存在的缺点。通过基于预处理的改进Apriori算法在高校教学评价中的应用,说明数据
2、挖掘过程,分析挖掘结果,最后指出了未来的研究方向。关键词:数据挖掘;关联规则;Apriori算法中图分类号:TP301.6文献标志码:A数据挖掘(DataMining)自问世以来就得到了广泛关注和深入研究,它是一门集机器学习、数理统计、人工智能、数据库技术、神经网络等多门学科于一体的交叉性学科,是从现存的大量的数据源中通过加工处理,探寻出有用的、有潜在价值并且是可以被理解的信息或知识的复杂过程,用概念、约束、模式、[1-2]规律、可视化等形式来表示挖掘出的信息,用于决策、过程控制、信息管理、查询处理等。关联规则是数据挖掘问题中最活跃和最重要的研究内容,主要研究从大型数据集
3、中挖掘隐藏的、有趣的、属性间存[3]在的关联和规律。其中Apriori算法是关联规则中最为著名和经典的算法,能够有效挖掘满足用户规定条件的关联知识。1关联规则[4]关联规则是由Agrawal等人在1993年首次提出的,是挖掘数据之间关联知识最常用的方法。关[2]联规则挖掘的经典例子是购物篮数据分析,目的是找出顾客在商场所选购商品之间的关联,如奶酪啤酒[支持度=10%,置信度=80%],表示10%的客户同时购买奶酪和啤酒,而在所有购买奶酪的人中有80%的人也购买了啤酒。关联规则一般可描述为:设I={i1,i2,i3,…,in}是n个不同项的集合,给定一个事务数据库D,T是I
4、中一些项组成的集合,表示D中的一个事务,TI,每个T都有唯一的标识符TID,假设X是一个I中项的集合,如果XT,则称作事务T包含X,如果X中有k个项,则又称X为k-项集。那么一条关联规则表示为:XY,其中XI,YI且X∩Y=H,X是此关联规则的前提,Y是结果,推理通过支持度和置信度来确定。支持度(Support)S表示D中有S%的事务同时包含X和Y,即是事务集中同时包含X和Y的事务数与所有事务数之比,记作Support(XY)=P(X∪Y)。置信度(Confidence)C表示D中有C%的事务同时也包含Y,即包含X和Y的事务数与包含X的事务数之比,记作Confidence
5、(XY)=P(Y/X)=P(X∩Y)/P(X)。可见,支持度表示此规则在所有事务中的代表性,置信度表示规则的强度,关联规则挖掘就是找出收稿日期:2011-11-08基金项目:梅州市与嘉应学院联合自然科学基金重点资助项目(2011KJZ10)作者简介:刘耀南(1980-),男,广东梅州人,嘉应学院讲师。第3期刘耀南:Apriori算法的分析及应用71满足用户给定的最小支持度和最小置信度阈值的有意义的规则,一般分为两步:首先找出所有的频繁项[3]集(满足最小支持度的项集),然后产生有趣的关联规则。2Apriori算法在众多的关联规则算法中,Apriori算法是挖掘布尔关联规则
6、频繁项集的最有影响力的有效算法,[5]它是使用一种称作逐层搜索的迭代方法,k-项集用于探索(k+1)-项集。Apriori算法分两步进行:第1步是生成所有支持度大于minsup(最小支持度阈值)的频繁项集,基本原理是先遍历事务数据库得到频繁1-项集L1,由L1产生长度为2的候选项集合C2,然后求出事务数据库中的每一个事务t在C2中的全部子集Ct,令Ct中的每一个长度为2的候选项集c的计数加1,当扫描事务数据库一遍后,筛选出候选项集合C2中所有计数满足最小支持度的项集组成频繁2-项集L2,如此重复步骤,直到没有频繁k-项集产生,其中候选项集产生的过程被分为连接与剪枝两个部分
7、;第2步是从频繁项集中生成所有满足置信度大于minconf(最小置信度阈值)的关联规则。第2步是比较容易实现的,目前大量的工作是放在第1步即如何生成所有频繁项集。[2]Apriori算法代码解释如下:输入:事务数据库D;minsup。输出:D中所有频繁项集L。方法:(1)C1=init-pass(D)//对事务D进行第1轮搜索(2)L1={f
8、f∈C1,f.count/n≥minsup//n是D中事务的数目(3)for(k=2;Lk-1≠;k++)do//随后的各轮搜索(4)Ck=Candidategen(Lk-1);//产生
