基于映射和逻辑运算的Apriori算法优化.docx
- 文档编号:17374950
- 上传时间:2023-07-24
- 格式:DOCX
- 页数:24
- 大小:229.58KB
基于映射和逻辑运算的Apriori算法优化.docx
《基于映射和逻辑运算的Apriori算法优化.docx》由会员分享,可在线阅读,更多相关《基于映射和逻辑运算的Apriori算法优化.docx(24页珍藏版)》请在冰点文库上搜索。
基于映射和逻辑运算的Apriori算法优化
目录
摘要II
ABSTRACTIII
第一章绪论1
1.1本文研究背景1
1.2本文的研究目的及工作1
第二章关联规则传统Apriori算法2
2关联规则2
2.1Apriori算法3
2.2Apriori算法PAD4
2.3Apriori算法优点及问题5
第三章改进的Apriori算法6
3.0Apriori算法的强关联规则-以购物篮系统为例6
3.1改进的基于映射和逻辑运算的Apriori算法6
3.2改进Apriori算法示例与分析9
3.3算法分析19
第四章总结与展望22
4.1总结22
4.2展望22
参考文献23
致谢24
摘要
[摘要]关联规则是数据挖掘研究的一个重要分支,其反映了海量数据间的有意义的关联。
而Apriori算法作为最经典的算法之一备受推崇的同时也存在着如下问题:
多次扫描数据库,候选集巨大,时间和空间复杂度过高等。
针对这一问题,本文在分析传统Apriori算法后,提出了基于映射和逻辑运算改进的Apriori算法,该改进算法大大提高了数据挖掘的效率。
[关键词]Apriori关联规则数据挖掘
ABSTRACT
[ABSTRACT]AssociationrulesisanimportantbranchofDatamining,whichreflectsameaningfulassociationinmassdata.TheApriorialgorithmisoneofthemosthighlyregardedclassicalalgorithms,whiletherearealsosomequestionssuchas:
multiplescansofdatabase,colossalcandidatesets,hightimeandspacecomplexity.Tosolvethisproblem,thispaperpresentsanimprovedApriorialgorithmthatisbasedonmappingandlogiccomputingafterintroducingandanalyzingtraditionalApriorialgorithm.ThealgorithmcansignificantlyimproveefficiencyofApriorialgorithm.
[KEYWORDS]AprioriAssociation-rulesData-mining
第一章绪论
1.1本文研究背景
数据挖掘是一种从大量数据中提取出隐含的、未知的、潜在的和有用的信息的过程。
数据挖掘技术和数据库知识发现(KnowledgeDiscoveryinDatabase,KDD)都是近年来随着数据库技术、人工智能技术,以及计算机科学技术的发展而出现的一种全新信息技术。
本文以商场购物篮系统为研究背景,利用Apriori算法挖掘出客户购买商品种类之间的强关联规则,由此来达到了解客户购买习惯,进而使商家可以使销售策略有章可循来达到利润的突破。
1.2本文的研究目的及工作
本文研究工作源于上述背景,对传统的关联规则算法Apriori进行研究分析,在此基础上对传统算法进行优化,同时Code实现改进的Apriori算法,验证其有效性。
本文主要工作:
(1)介绍关联规则以及相关概念。
(2)介绍传统Apriori算法并分析其缺陷。
(3)通过对Apriori算法的性质研究针对其缺陷优化,并给出严格的数学论证。
(4)设计出优化的算法,并编码实现。
(5)对其性能进行算法分析。
第二章关联规则传统Apriori算法
2关联规则
设D是交易(transaction)T的集合,D={t1,t2,t3..tn},这里交易T是项的集合,可以表述为:
T={t1,t2,…,tp}并且T⊆D。
T中的元素ij={j=1,2,…,p}称为项。
对应每一个交易有唯一的标识交易号,记作TID。
设I={i1,i2,…,im}是数据集中所有项的集合,I中的任何子集称为项目集(itemset),记项的个数|X|=K,则称集合X为K-项集。
设tk和X分别为D中的事务和项目集,如果X⊆tk,称事务tk包含项目集X。
项目集X的支持度为support(X),若support(X)不小于用户指定的最小支持度(记作:
minsupport),则称X为频繁项目集,否则称X为非频繁项目集。
设X,Y是数据集D中的项目集。
若X⊆Y,则support(X)>=support(Y);若X⊆Y,如果X是非频繁项目集,则Y也是非频繁项目集;若X⊆Y,如果Y是频繁项目集,则X也是频繁项目集。
一个关联规则是形如X=>Y的蕴涵式,这里X,Y都是项目集,且X与Y包含于同一个事务中,并且X与Y的交集为空,X,Y分别称为关联规则X=>Y的前提和结论。
一般使用支持度(support)和置信度(confidence)两个参数来描述关联规则的属性。
(1)支持度
规则X=>Y在数据库D中的支持度(support)是交易集中同时包含X,Y的事务数与所有事务数之比,记为support(X=>Y)=support(XUY)。
支持度描述了X,Y这两个项集在所有事务中同时出现的概率。
(2)置信度
规则X=>Y在事务集中的置信度(confidence)是指同时包含X,Y的事务数与包含X的事务数之比,它用来衡量关联规则的可信程度。
记为confidence(X=>Y)=support(XUY)/support(X)。
一般情况下,只有关联规则的置信度大于期望可信度,才说明X的出现对Y的出现有促进作用,也说明了它们之间的某种程度的相关性。
给定一个事务集D,挖掘关联规则的问题就是产生支持度和置信度分别大于用户事先给定的最小支持度和最小置信度的关联规则。
关联规则挖掘的任务就是要挖掘出D中所有的强规则X=>Y。
强规则X=>Y对应的项目集(XUY)必定是频繁项目集,频繁项目集(XUY)导出的关联规则X=>Y的置信度可由频繁项目集X和(XUY)的支持度计算。
因此,可以把关联规则挖掘划分为两个子问题:
一个是找出所有的频繁项目集:
即所有支持度不低于给定的最小支持度的项目集。
另一个是由频繁项目集产生强关联规则:
即从第一个子问题得到的频繁项目集中找出置信度不小于用户给定的最小置信度的规则。
其中,第一个子问题是关联规则挖掘算法的核心问题,是衡量关联规则挖掘算法的标准。
2.1Apriori算法
针对核心问题(获得频繁项目集),Apriori算法的描述如下。
输入:
数据库D;
最小支持度阀值min_sup。
输出:
D中的频繁项集
。
方法:
STEP1:
L1={large1-itemsets}//得到频繁一项目集
STEP2:
for(k=2;Lk-1≠Φ;k++)
{
Ck=apriori-gen(Lk-1);//连接由频繁项目集k-1得到候选项目集k
Foralltransactiont∈D
{
Ct=subset(Ck,t)//遍历事务数据库集查看Ck中是否在事务t
Forallcandidatesc∈Ct
{
c.count++;//对遍历后且包含在某一事务t中的Ck计数
//目的:
计算支持度
}
}
Lk={c∈Ct|c.count≥min_sup}
}
2.2Apriori算法PAD
算法示例图2-2:
2.3Apriori算法优点及问题
Apriori算法的优点是结构简单,易于理解,没有复杂的推导。
另外算法应用Apriori性质而设计的连接后剪枝方法在许多情况下大大缩小了需要检查的候选规模,使算法效率大幅度提高。
但Apriori算法依然存在两个主要的问题:
(1)多次扫描数据库。
Apriori算法需要在每进行一次迭代的时候扫描X次数据库,而在实际应用中经常需要挖掘很长的模式,多次扫描数据库带来巨大开销。
(2)可能产生大量候选。
Apriori算法在迭代过程中要在内存中产生、处理和保存候选频繁项集,这个数量有时候是非常巨大的,导致算法在广度和深度上的适应性很差。
即Apriori算法有个严重的缺陷:
因为需要多次扫描数据库和产生大量的频繁项集,使得算法的花费在I/0上的时间很多,从而导致挖掘的效率非常低。
因此,为了提高Apriori算法的有效性,需要对Apriori算法进行改进。
人们对Apriori算法进行了大量的改进,希望能够找出一个高效、可靠的挖掘频繁项集的算法。
因此本文针对购物篮系统对Apriori算法进行了改进,提出一种基于映射和0-1编码逻辑与运算的Apriori改进算法。
第三章改进的Apriori算法
3.0Apriori算法的强关联规则-以购物篮系统为例
WALMART曾将自己的全球销售网络组建一个大型的购物篮系统,通过先进的挖掘技术将数以万计的销售信息汇集到其数据仓库中,其中一个方法就是找出其中的强关联规则,找出顾客的购买习惯,以此调配管理物流.。
其中经典的例子是:
发现尿布和啤酒同时被购买的概率很高,经调查发现在家里带孩子的男士会在买尿布的时候购买啤酒打发无聊的时间,故将两种商品放在一起,提高了销售利润。
因此,找出潜在的强关联规则是发现购物篮系统潜在信息的行之有效的方法,这体现了Apriori算法的优势。
然而,如果数据量大,如何来降低计算量并提高数据分析的效率?
本文针对该问题提出了下列改进:
※通过数据存储方式的改变来减少数据库扫描
※通过Apriori性质分析来缩小候选集
3.1改进的基于映射和逻辑运算的Apriori算法
改进的基于映射和逻辑运算的Apriori是在实现强关联规则的基础上,采用映射集和0-1矩阵的逻辑运算降低数据计算量并提高数据分析的效率。
3.1.1算法简介
Apriori算法需要频繁扫描整个数据库。
与Apriori算法相比,基于映射和逻辑运算的改进算法只需要扫描整个数据库两次。
第一遍:
扫描商品项目映射表(metaData),将产生商品名称与商品代号对应映射。
得到所有项目,用简单的编码减小存储在内存中的存储空间,减少扫描数据库的I/O负载。
第二遍:
对所有项目构建逻辑0-1矩阵,某一条购买事务中存在该项目集则计数为1,否则计数为0;通过矩阵迭代进行逻辑与运算和加入连接前减枝得到所有频繁集。
3.1.2算法伪码
基于映射和逻辑运算的Apriori改进算法的具体描述如下:
输入:
数据库D;最小支持度阀值min_sup
输出:
D的频繁项集L
STEP1:
gotItems();//第一次扫描得到所有项目
SecondScan();//第二次扫描构建0-1矩阵
gotL1();//统计得到L1
gotC2();//逻辑与运算得到候选项目集2
gotL2();//得到L2
STEP2:
for(k=2;Lk-1≠Φ;k++)
{
L_C=CutBefore(Lk);//连接前剪枝
Ck+1=conItems(L_C);//由剪枝后的频繁集连接得到候选项目集//Ck+1
Lk+1=CutAfter(Ck+1);//连接后剪枝
}
3.1.3算法PAD
算法示例图3-1-3:
3.2改进Apriori算法示例与分析
3.2.1数据
※本文以购物篮系统为背景所用数据为随机输入
(数据库D:
顾客购买物品编码表,每一条为1个购买记录,以下共有6条购买记录)
(数据库D:
物品映射编码表,每一条为1种物品映射关系,以下共有6种商品信息)
※解释:
(TID1,AEGKM)某一顾客一次购买了AEGKM(牛奶,花生酱,雪碧,啤酒,大豆)这些商品。
3.2.2第一次扫描数据库映射关系表
※关键伪码示例:
/*
*为构建矩阵与逻辑运算提供简单编码支持
*/
ForeachitemsrsinmetaData2
Begin:
items=newItems();
items.a=rs.getString
(1).trim();
items.b=rs.getString
(2).trim();
list.add(items);
End;
3.2.3第二次扫描数据库购买事务表
※关键伪码示例:
/*
*遍历事务表dataSet2如果该项目元素出现在某一事务中置1否则置0
*/
ForeachitemsrsindataSet2
Begin:
Foreachitemslistiteminlist
Iflistitem∈rs
Thenlistitem+=“1”;
Else
Thenlistitem+=”0”;
End;
※表dataSet2
代码示例:
扫描数据库对于商品A生成向量(111011),因扫描TID1,2,3,5,6均包含A,因此置1,否则为0。
同理,建立如下图矩阵。
3.2.4根据最小支持数计算频繁项目集L1
※支持数:
含有某一项集的TID的个数。
假设最小支持数为2(min_sup=2)
∵Support(B)<2(项目C.D.I.J.N同理)
∴不满足其出现概率的最小值
∴淘汰该项目或项目集
∴得到频繁项目集L1
共9项目集
3.2.5连接得到候选项目集C2并生成L2
※关键伪码示例(连接,即:
逻辑与运算):
/*
*如果对应位同为1置1,否则置0
*/
Stringlogical(Stringa,Stringb)//逻辑与运算
{
N=a.length;
Forallelement1∈aelement2∈b
Ifa和b有N-1项相同进行连接
{
Ifelement1==1&&element2==1
Thenelement=1
Else
Thenelement=0
}
}
※代码解释:
参数a,b即为矩阵的某参与连接的两行,对应的某一位就是该项目是否在某一事务中出现的标志,所以遇到两位都是1的情况下,就将此项置1。
否则,置0。
连接生成C2如下:
共36项目集
连接后剪枝生成L2如下:
∵Support(AF)<2
∴删除AF
(项目AH.AL.AM.AO.EF.EH.EK.EL
EM.EO.FG.FM.GH.GK.GLGM.GO.HL.HM.HO.KL.KO.LM.MO同理删除)
共11个项目集
3.2.6迭代寻找确定所有候选集(连接前剪枝)
※连接前剪枝
※性质1:
I是一个数据集D中的频繁项集-k,那么I的所有k-1子集也一定是频繁项集。
证明:
设I项集的个数为k记为X,I的k-1子集个数记为Y
∵X>Y
∴事务集中包含X的事务数目不大于Y
∴X的支持度肯定不大于Y的支持度
证毕
※推论1:
Xk是数据集D的频繁K项集,则频繁K-1项集中包含Xk的所有k-1项子集
即个数为K。
当P=k-1时,
=K。
※推论2:
如果某个元素在K-频繁项目集中,则该元素在K-1频繁项目集中出现的次数最少为k-1.
证明:
∵(性质一)所有K频繁集的K-1子集一定是频繁集
∴设:
频繁K项集的某一项中的任一元素O在频繁K-1子集中出现的次数为N
N=
=k-1(i=k-1,G=k-2)
∵频繁K项集中含有n项,n>=1
∴当K-频繁集中含有元素O的频繁项x>=1时,则该元素在K-1频繁集中的出现次数M=x·N=x·(k-1)
∴M>=k-1
证毕
◎推论2即为(连接前剪枝):
:
首先统计Lk-1中所有项出现的次数,然后删除Lk-1中包含有出现次数小于(k-1)的项的项集,得到L_C(连接前剪枝后待连接的项目集)。
※关键伪码示例:
/*
*统计Lk频繁项目集中元素出现次数
*/
Foreachitem∈Lk
Begin:
Foreachelement∈item
Switch(element)
Case(A):
A.count++;break;
Case(B):
B.count++;break;
Case(C):
C.count++;break;
Case(D):
D.count++;break;
………
End;
运行结果:
◎对频繁项目集L2进行连接前剪枝
※关键伪码示例:
Foreachelement Begin: ForeachITEM∈Lk Ifpattern(element,ITEM)/*匹配element是否在ITEM中在则删除该项目*/ Delete(ITEM); End; 由于项M在频繁集L2中出现的次数小于2,因此在L2中删除KM生成L_C 共10个项目集 ◎对L_C进行连接,并进行连接后剪枝得到频繁项目集L3 ※连接: (对于项目元素>=2的项目进行两两连接) 步骤: ※连接 ※连接后剪枝: 删除支持数 结果: 共11个项目集 与最小支持数比较: 淘汰AEK.AGK.AFK.AHK.FHL.FHO.FKL.FKO ◎同理,连接前剪枝L3生成L_C 由于频繁项目集L3中所有项的出现次数均小于3,因此均不参与连接,频繁项集搜索结束。 ◎打印出所有候选项目集 3.3算法分析 3.3.1本文示例分析 优化后的算法的优势有两点: ※逻辑与运算的0-1编码矩阵理解简单,计算机实现方便。 ※连接前剪枝 如上例所示,由L2生成L3 如上例所示,由L3生成L4 连接次数比较,如下表所示: 传统Apriori 55+3=58次 改进 Apriori 45+0=45次 对于仅仅有6个事务的示例来说,实际优化效果比为: (58-45)/58=22.4% 显然优化后的算法有优秀的时间效率。 与此同时,实际应用中有上亿条的购买事务,因此利用优化后的算法显然会产生巨大的经济效益。 3.3.2综合分析 ∵随具体数据不同所达到实际效果有偏差 ∴按上文得到的22.4%的优化率作为分析依据 假设如下: ⊙已经得到频繁2项目集,且频繁2项目集的个数是10^6,求由L2生成候选项目集3。 ⊙优化后算法对传统算法的优化率为22.4% 实际效率表格如下: 扫描数据库次数 连接次数 效率分析 改进 Apriori 算法 2 =3*10^11 K=10^6*(1-22.4%)=776000 P=2 1.连接次数 优化后的算法比传统算法在连接次数上减少了2*10^11次,自然节省了这么多次的连接操作时间。 2.扫描数据库次数 传统Apriori算法: 根据项目的多少来决定扫描多少次数据库,因此当项目激增的时候,扫描次数也成指数级增长 改进Apriori算法: 无论多少个项目 都只扫描2次数据库,是个定值 传统 Apriori 算法 10^6 =5*10^11 K=10^6 P=2 第四章总结与展望 4.1总结 本文目的: 通过改进传统算法缩减候选集大小,来达到提高Apriori算法的效率。 方法: 对传统Apriori算法对象进行流程剖析(在扫描数据库,剪枝缩小候选集两方面入手),对前者采用映射数据表和TID表的方式进行两次次扫描,对后者采用0-1编码构成矩阵采用逻辑与运算和加入一次连接前剪枝有效减少候选集。 结果: 采用对照组的形式对比2种算法,在时间和空间复杂度上改进算法要优于传统。 结论: 改进的算法是一种行之有效的关联规则挖掘算法,且易于实现。 由此可见,在最坏的情况下两者在候选集以及I/O操作上没有差别,但是一般情况下该算法可以提高对于关联规则的检索效率。 4.2展望 本文对数据挖掘中的关联规则技术进行了一定的研究,在对传统的Apriori算法分析和研究的基础上,提出了一种关系数据库中关联规则挖掘的优化算法0-1coding-Apriori,并用JAVA实现了该数据挖掘算法,使用0-1coding-Apriori算法对自己随机生成的数据中的关联规则进行挖掘。 由于研究时间和学科知识有限,本文所做的工作尚有欠缺,许多工作需要进一步的研究和探索: ※本文针对的挖掘仅仅是静态数据挖掘,而往往实际应用中都是大量新增数据参与其中的增量动态挖掘,固因此会产生巨大的时间和空间开销。 而增量式关联规则挖掘是解决这一问题的重要研究方向。 在今后的研究过程中可以从这一角度出发,寻找到实现关系数据库中的增量关联规则挖掘的有效方法。 ※不断寻找更为科学便捷的实现算法,设计开发行之有效的数据挖掘系统,使其成为企业科学管理、科学决策的有效方法。 为了实现这一目标,研究和探索还将不断地继续下去。 参考文献 [1]韩秋明·数据挖掘技术应用实例[M]·李微·李华锋·纪希禹·机械工业出版社2009-04出版 [2]邓纳姆·数据挖掘教程[M]·清华大学出版社2005-05出版 [3]潘华·数据仓库与数据挖掘原理工具及应用[M]·项同德·中国电力出版社2007-12出版 [4](美)贝里·数据挖掘—客户关系管理的科学与艺术[M]·中国财经出版社2004-01出版 [5]张喆·数据挖掘及其在客户关系管理中的应用[M]·复旦大学出版社2008-08出版 [6]陈文伟·数据仓库与数据挖掘教程[M]·清华大学出版社2006-08出版 致谢 在这篇论文即将结束时,我要感谢在学习期间关心我的老师和同学,尤其是梁平老师,从论文的选题,研究思路到论文写作,都离不开导师的悉心指导,导师严谨的治学风格,渊博的知识,和无私的奉献精神是我终身的榜样。 导师在繁忙的教学和工作中,经常主动关心指导我的学习,并帮助我查阅资料。 同时,还要感谢老师在开题报告和中期检查时给予的建议和帮助。 感谢所有帮助支持过我的老师和朋友们! 文档来源网络,版权归原作者。 如有侵权,请告知,我看到会立刻处理。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 映射 逻辑运算 Apriori 算法 优化