版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、,AprioriAlgorithm,小组成员吴国泉、唐思远、赵清伟、张波,2,购物篮分析:引发性例子,Questions关联分析Solutions,1:经常同时购买的商品可以摆近一点,以便进一步刺激这些商品一起销售。2:规划哪些附属商品可以降价销售,以便刺激主体商品的捆绑销售。,哪组商品顾客可能会在一次购物时同时购买?,关联分析的基本概念,关联规则是形如的蕴含式,(支持度)规则在事务集D中成立,支持度S是事务包含的百分比。Support()=P()(置信度)置信度C是D中同时包含A的事务同时也包含B的百分比。Confidence()=P()/P(A)(k项集)包含k个项的项集称为k项集,频繁k
2、项集的集合记作,候选k项集的集合记作。,由频繁项集产生强关联规则,(1)K维数据项集LK是频繁项集的必要条件是它所有K-1维子项集也为频繁项集,记为LK-1(2)如果K维数据项集LK的任意一个K-1维子集LK-1,不是频繁项集,则K维数据项集LK本身也不是最大数据项集。(3)LK是K维频繁项集,如果所有K-1维频繁项集集合LK-1中包含LK的K-1维子项集的个数小于K,则LK不可能是K维最大频繁数据项集。(4)同时满足最小支持度阀值和最小置信度阀值的规则称为强规则。,Apriori算法说明,在Apriori算法中,寻找最大项目集的基本思想是:算法需要对数据集进行多步处理.第一步,简单统计所有含
3、一个元素项目集出现的频率,并找出那些不小于最小支持度的项目集,即一维最大项目集L1.从第二步开始循环处理直到再没有最大项目集生成.循环过程是:第k步中,根据第k-1步生成的(k-1)维最大项目集产生k维侯选项目集CK,然后对数据库进行搜索,得到侯选项目集的项集支持度,与最小支持度比较,从而找到k维频繁项目集LK.,连接步,为找出Lk,通过将Lk-1与自身连接产生候选k项集的集合Ck。设l1和l2是Lk-1中的成员。记lij表示li中的第j项。假设Apriori算法对事务集中的项按字典次序排序,即对于(k-1)项集li,li1li2lik-1。将Lk-1与自身连接,如果(l11=l21)和I1,
4、,I2,I4和I1,I3,I4,和I2,I3,I4.而不会仅仅是I1,I2,I4.和I1,I3,I4。通过I1,I2,I3和I1,I2,I4的组合,就可以得到I1,I2,I3,I4.所以不会遗漏。,Apriori算法的缺陷,(1)在每一步产生侯选项目集时循环产生的组合过多,没有排除不应该参与组合的元素;(2)每次计算项集的支持度时,都对数据库D中的全部记录进行了一遍扫描比较,如果是一个大型的数据库的话,这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求一种能减少这种系统1/O开销的更为快捷的算法。,Apriori算法的优化思路
5、,在逐层搜索循环过程的第k步中,根据k-1步生成的k-1维频繁项目集来产生k维候选项目集,由于在产生k-1维频繁项目集时,我们可以实现对该集中出现元素的个数进行计数处理,因此对某元素而言,若它的计数个数不到k-1的话,可以事先删除该元素,从而排除由该元素将引起的大规格所有组合。这是因为对某一个元素要成为K维项目集的一元素的话,该元素在k-1阶频繁项目集中的计数次数必须达到K-1个,否则不可能生成K维项目集(性质3)。,根据以上思路得到了这个候选项目集后,可以对数据库D的每一个事务进行扫描,若该事务中至少含有候选项目集CK中的一员则保留该项事务,否则把该事物记录与数据库末端没有作删除标记的事务记
6、录对换,并对移到数据库末端的事务记录作删除标一记,整个数据库扫描完毕后为新的事务数据库D中。因此随着K的增大,D中事务记录量大大地减少,对于下一次事务扫描可以大大节约I/0开销。由于顾客一般可能一次只购买几件商品,因此这种虚拟删除的方法可以实现大量的交易记录在以后的挖掘中被剔除出来,在所剩余的不多的记录中再作更高维的数据挖掘是可以大大地节约时间的。,Apriori算法的优化实例,Apriori算法的优化效果,(1)优化算法在考虑组合CK前,对将参与组合的元素进行计数处理,根据计数结果决定排除一些不符合组合条件的元素而降低循环判断的次数。如果对大型的数据库而言,这种时间开销的降低对数据挖掘效率来说是显而易见的,这是Apriori方法中没有涉及的;(2)优化算法对数据库进行扫描后重新生成(删除一些不能支持频繁集的记录,这里所谓的删除实际上是把不符合再次扫描比较条件的记录通过交换记录内容的方式移到数据库的末端,把末端新记录填入该记录的位置。同时对数据库中
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 安全生产月个人总结心得
- 动人的早安问候语
- 2024年抗变态反应药项目合作计划书
- 2024年石油钻井泥浆固控设备项目发展计划
- 2024年PP胶水项目发展计划
- 统编版语文三年级下册第8单元 28 枣核(教案)【绘本课堂】2022
- 航次租船合同(示范文本GF-97-0405)
- 河北省邢台英华教育集团2023-2024学年八年级下学期5月月考生物试题
- 三八节主题活动方案
- 学生自我认知鉴定总结
- 夜市应急方案及措施
- (2024年)《工伤保险培训》ppt课件完整版
- 新教材化学人教版课时作业第七章有机化合物综合素养测评
- 紧急运输应急预案及紧急供货措施
- DB35T 2060-2022 居家社区养老服务第三方评估规范
- 运动损伤预防与处理的新观念与实践
- 智慧课堂在小学语文教学中的运用研究 论文
- 装修施工工艺指导手册之油漆施工
- 一例维持性血液透析患者导管感染的护理查房
- 北师大版四年级数学上册第四单元运算律 大单元作业设计
- 2024年上海申康医疗卫生建设工程公共服务中心招聘笔试冲刺题
评论
0/150
提交评论