Apriori算法.docx
- 文档编号:2590454
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:23
- 大小:158.39KB
Apriori算法.docx
《Apriori算法.docx》由会员分享,可在线阅读,更多相关《Apriori算法.docx(23页珍藏版)》请在冰点文库上搜索。
Apriori算法
Apriori算法改进及其实现
内容摘要
信息技术的不断推广应用,将企业带入了一个信息爆炸的时代。
如何充分利用这些数据信息为企业决策者提供决策支持成为一个十分迫切的又棘手的问题,人们除了利用现有的关系数据库标准查询语句得到一般的直观的信息以外,必须挖掘其内含的、未知的却又实际存在的数据关系。
著名的Apriori算法是一种挖掘关联规则的算法。
本文通过对参与候选集的元素计数的方法来减少产生候选集的组合和减少数据库的扫描次数来达到要求。
这有利于提高挖掘的速度和减少数据库的I/O操作时间的开销。
关键字:
数据挖掘,关联规则,Apriori算法
AprioriAlgorithmAndImprovedAprioriAlgorithm
Abstract:
AninformationburstageiscomingwiththevariousapplicationofInformationtechnology.Howtomaximizetheinformationisaveryimportantproblemforthedecision-makerofthecompanies.BesidesgettingtheregularinformationfromtheDatabasebySQL-query,peoplestillneedtominethedatarelationwhichisunclearbutreallyexists.Associationrulesisoneofthedataminingmethods,thefamousalgorithmAprioriisamethod,whichcanbeusedtosolutethoseproblems.
ThisarticleanalyzesandstudiestheimprovedalgorithmAprioribasedonthealgorithmofminingassociationrulesApriori.Themainidea
istodecreasethenumberofcandidateitemsandtodecreasethetimesofDatabasescanning.Thesolutionisavailable.Itupgradesthespeedofdatamininganddecreasescomputer'sI/Ooperation.It'sprovedtobe
moreefficientthanthetraditional
Keywords:
Datamining,associationrules,Apriorialgorithm,
目录
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-
4Apriori算法的描述-8-
4.1Apriori算法的说明-8-
4.2Apriori算法的描述-9-
4.3Apriori算法的举例-11-
5一种Apriori的改进算法-14-
5.1算法产生的思路-14-
5.2算法的图例说明-15-
5.3本算法的评价:
-15-
附录1程序运行图示-18-
附录2程序代码-20-
1数据挖掘
1.1技术上的定义及含义
数据挖掘(DataMining)就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中,提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。
与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。
这个定义包括好几层含义:
数据源必须是真实的、大量的、含噪声的;发现的是用户感兴趣的知识;发现的知识要可接受、可理解、可运用;并不要求发现放之四海皆准的知识,仅支持特定的发现问题。
----何为知识?
从广义上理解,数据、信息也是知识的表现形式,但是人们更把概念、规则、模式、规律和约束等看作知识。
人们把数据看作是形成知识的源泉,好像从矿石中采矿或淘金一样。
原始数据可以是结构化的,如关系数据库中的数据;也可以是半结构化的,如文本、图形和图像数据;甚至是分布在网络上的异构型数据。
发现知识的方法可以是数学的,也可以是非数学的;可以是演绎的,也可以是归纳的。
发现的知识可以被用于信息管理,查询优化,决策支持和过程控制等,还可以用于数据自身的维护。
因此,数据挖掘是一门交叉学科,它把人们对数据的应用从低层次的简单查询,提升到从数据中挖掘知识,提供决策支持。
在这种需求牵引下,汇聚了不同领域的研究者,尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行计算等方面的学者和工程技术人员,投身到数据挖掘这一新兴的研究领域,形成新的技术热点。
这里所说的知识发现,不是要求发现放之四海而皆准的真理,也不是要去发现崭新的自然科学定理和纯数学公式,更不是什么机器定理证明。
实际上,所有发现的知识都是相对的,是有特定前提和约束条件,面向特定领域的,同时还要能够易于被用户理解。
最好能用自然语言表达所发现的结果。
1.2商业角度的定义
数据挖掘是一种新的商业信息处理技术,其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理,从中提取辅助商业决策的关键性数据。
简而言之,数据挖掘其实是一类深层次的数据分析方法。
数据分析本身已经有很多年的历史,只不过在过去数据收集和分析的目的是用于科学研究,另外,由于当时计算能力的限制,对大数据量进行分析的复杂数据分析方法受到很大限制。
现在,由于各行业业务自动化的实现,商业领域产生了大量的业务数据,这些数据不再是为了分析的目的而收集的,而是由于纯机会的(Opportunistic)商业运作而产生。
分析这些数据也不再是单纯为了研究的需要,更主要是为商业决策提供真正有价值的信息,进而获得利润。
但所有企业面临的一个共同问题是:
企业数据量非常大,而其中真正有价值的信息却很少,因此从大量的数据中经过深层分析,获得有利于商业运作、提高竞争力的信息,就像从矿石中淘金一样,数据挖掘也因此而得名。
因此,数据挖掘可以描述为:
按企业既定业务目标,对大量的企业数据进行探索和分析,揭示隐藏的、未知的或验证已知的规律性,并进一步将其模型化的先进有效的方法。
1.3数据挖掘与传统分析方法的区别
数据挖掘与传统的数据分析(如查询、报表、联机应用分析)的本质区别是数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识.数据挖掘所得到的信息应具有先未知,有效和可实用三个特征.
先前未知的信息是指该信息是预先未曾预料到的,既数据挖掘是要发现那些不能靠直觉发现的信息或知识,甚至是违背直觉的信息或知识,挖掘出的信息越是出乎意料,就可能越有价值.在商业应用中最典型的例子就是一家连锁店通过数据挖掘发现了小孩尿布和啤酒之间有着惊人的联系.
1.4数据挖掘不能干什么
DM不能告诉你某个模型对你的企业的实际价值DM是一个工具,他只是帮助商业人士更深入、更容易地分析数据,但是无法告诉你某个模型对你的企业的实际价值,DM中得到的模型必须在现实生活中进行验证,DM不会在缺乏指导的情况下自动的发现模型。
数据分析者必须知道你所选用的DM工具是如何工作的,采用的算法的原理是什么。
DM永远不会替代有经验的商业分析师或管理人员所起的作用,它只是一个强大的工具。
2数据挖掘的几种主要形式:
2.1:
规则挖掘:
如果一个事务中含有X,则该事务中很可能含有Y。
具体形式为{X}→{Y},即通常可以描述为:
当一个事务中顾客购买了一样东西{钢笔}(这里X=“钢笔”)则很可能他同时还购买了{墨水}(这里Y="墨水"),这就是关联规则。
在美国,有一种说法是:
“尿不湿”和“啤酒”经常一起被购买。
这种说法有其一定的现实意义:
1)或许是该年龄段的经常喝啤酒的人刚好家庭开始养育小孩;2)或许是因为啤酒喝多,需要用尿不湿。
然而不管怎样,如果没有数据挖掘中的关联规则在这里的应用,你是无论如何想象不出这样有点惊人的“笑话”。
本文在后面将就该规则作一详细的阐述与讨论。
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)是数据库中的数据项.数据项之间的关联规则即根据一个事务中某些项的出现,可推导出另一些项在同一事务中也出现.
挖掘关联规则的问题描述如下:
设:
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是大数据项集.一般由用户给定最小置信度阈值和最小支持度阈值.置信度和支持度大于相应阈值的规则称为强关联规则,反之称为弱关联规则.发现关联规则的任务就是从数据库中发现那些置信度、支持度大小等于给定值的强壮规则.
基于上述概念,我们可以很容易得到一些基本结论:
(1)K维数据项集XK是频繁项集的必要条件是它所有K-1维子项集也为频繁项集,记为XK-1
(2)如果K维数据项集XK的任意一个K-1维子集XK-1,不是频繁项集,则K维数据项集XK本身也不是最大数据项集。
(3)XK是K维频繁项集,如果所有K-1维频繁项集集合XK-1中包含XK的K-1维子项集的个数小于K,则XK不可能是K维最大频繁数据项集。
证明:
很明显,数据项集XK-1:
的K-1维子项集的个数为K-1。
如果高频繁数据项集XK-1,中包含XK的K-1.维子项集的个数小于k,则存在XK的K-1维子项集不是频繁数据项集,由结论
(2)知K维数据项集本身也不是高频繁数据项集。
3.3关联规则挖掘举例
一个超级市场的销售系统记录了顾客购物的情况。
表3-1中记录了5个顾客的购物单。
记录号
所购物品清单
1
啤酒、尿布,婴儿爽身粉,面包,雨伞
2
尿布,婴儿爽身粉
3
啤酒、尿布,牛奶
4
尿布,啤酒,洗衣粉
5
啤酒,牛奶,可乐饮料
表3-1
双项统计
支持度
{啤酒,尿布}
3/5
{啤酒,牛奶}
2/5
{尿布,婴儿爽身粉}
2/5
超市经理想知道商品之间的关联,要求列出那些同时购买的、且支持度≥40%(即在5行中至少出现两次)的商品名称。
KDD系统通过特定算法(例如著名的Apriori(验证)算法及或改进算法)多次扫描数据库,依次得出如表2和表3。
其中支持度<2/5的项,如单项的{面包},{雨伞}和双项中的{尿布,牛奶}等等已经略去,三项统计为空,其中只有{啤酒,尿布,牛奶}出现了一次(表3-1中3号记录),支持度小于40%,略去。
单项统计
支持度
{啤酒}
4/5
{尿布}
4/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%
KDD规则反映了物品之间的表面联系,不一定是现实世界的因果关系。
规则是死的,人是活的,运用之妙成乎于人。
例如,R6“婴儿爽身粉→尿布”有很高的置信度,是合理可理解的,R3有很高的置信度将提示进一步的调查分析,本例中是因为训练资料太少引起的失真。
3.4关联规则问题的分解
关联规则挖掘问题可分解为以下两个子问题:
1.找出事务数据库D中所有大于等于用户指定最小支持度的项目集(itemset).具有最小支持度的项目集称为最大项目集.项目集的支持度指包含该项目集的数目.
2.利用最大项目集生成所需要的关联规则
对每一最大项目集A,找到A的所有非空子集a,如果比率support(A)/support(a)>=minconfidence,就生成关联规则a=>(A-a).support(A)/support(a) 即规则a=>(A-a)的置信度.
事实上,挖掘关联规则的整个执行过程中第一个子问题是核心问题.当找到所有的最大项目集后,相应的关联规则将很容易生成.在本文中将对关联规则的第一个问题进行探讨、研究。
4Apriori算法的描述
4.1Apriori算法的说明
在Apriori算法中,寻找最大项目集的基本思想是:
算法需要对数据集进行多步处理.第一步,简单统计所有含一个元素项目集出现的频率,并找出那些不小于最小支持度的项目集,即一维最大项目集.从第二步开始循环处理直到再没有最大项目集生成.循环过程是:
第k步中,根据第k-1步生成的(k-1)维最大项目集产生k维侯选项目集,然后对数据库进行搜索,得到侯选项目集的项集支持度,与最小支持度比较,从而找到k维最大项目集.
为方便后文叙述,现约定如下:
1.数据库事务中的项目都是以字母顺序排列的,每个项目用
2.每个项目集的项目数称为该项目集的size.当项目集的size=k时,称该项目集为k-itemset(k维项目集).
下文中遇到的以下符号,分别代表相应的内容
k-itemset k维项目集
Lk 具有最小支持度的最大k-itemset
Ck 侯选的k-itemsets(潜在的最大项目集)
4.2Apriori算法的描述
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++) //直到不能再生成最大项目集为止
(4)Ck=sc_candidate(Lk-1); //生成含k个元素的侯选项目集
(5)foralltransactionst∈D//办理处理
(6)Ct=count_support(Ck,t); //包含在事务t中的侯选项目集
(7)forallcandidatesc∈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(连接)步,
该步可表述为:
insertintoCk
selectP.item1,P.item2,......P.itemk-1,Q.itemk-1fromLk-1P,Lk-1Q whereP.item1=Q.item1,......P.itemk-2=Q.itemk-2,P.itemk-1 若用集合表示: Ck'={X∪X'|X,X'∈Lk-1,|X∩X'|=k-2} 然后,是prune(修剪)步,即对任意的c,c∈Ck,删除Ck中所有那些(k-1)维子集不在Lk-1中的项目集,得到侯选项目集Ck.表述为: for all itemset c∈Ck for all (k-1)维子集s of c if (s不属于Lk-1) then delete c from Ck; 用集合表示: Ck=={X∈Ck'|X的所有k-1维子集在Lk-1中} 在此函数中需要说明以下几点: (1)最大项目集的子集必为最大项目集.这是该算法中隐含的最基本的一条性质.因为最大项目集定义为不小于最小支持度(minsupport)的项目集.若最大项目集为c,则即c.count>=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.3Apriori算法的举例 示例说明Apriori算法运作过程 有一数据库D,其中有四个事务记录,分别表示为 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步后,产生集合{I2,I3,I5}.在prune步中,测试{I2,I3,I5}的子集{I3,I5},{I2,I3},{I2,I5}是否在L2中,由L2可以知道{I3,I5},{I2,I3},{I2,I5}本身就是最大2-itemsets.即{I2,I3,I5}的子集都是最大项目集.那么{I2,I3,I5}为侯选3-itemset.然后搜索数据库中所有事务记录,生成最大的3-tiemsetsL3.此时,从L3中不能再生成侯选4-itemset.Apriori算法结束. 算法的图例说明 从以上的算法执行过程可以看到Apriori算法的缺点: 第一: 在每一步产生侯选项目集时循环产生的组合过多,没有排除不应该参与组合的元素;第二: 每次计算项集的支持度时,都对数据库D中的全部记录进行了一遍扫描比较,如果是一个大型的数据库的话,这种扫描比较会大大增加计算机系统的I/O开销。 而这种代价是随着数据库的记录的增加呈现出几何级数的增加。 因此人们开始寻求一种能减少这种系统1/O开销的更
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Apriori 算法