数据挖掘应用- 浙江大学计算机科学与技术学院
179页1、第12讲 数据挖掘应用 Chapter 12 Applications of Data Mining,徐从富(Congfu Xu), PhD, Asso. Professor 浙江大学人工智能研究所 2005年5月17日第一稿 2006年10月30日第二次修改,浙江大学研究生人工智能引论课件,目录,关联规则挖掘 聚类分析 分类与预测 Web挖掘 流数据挖掘 隐私保护数据挖掘,关联规则挖掘,关联规则挖掘简介 关联规则基本模型 关联规则价值衡量与发展,关联规则简介,关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系,那么,其中一个事物就能够通过其他事物预测到。 典型的关联规则发现问题是对超市中的货篮数据(Market Basket)进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。,什么是关联规则挖掘,关联规则挖掘 首先被Agrawal, Imielinski and Swami在1993年的SIGMOD会议上提出 在事务、关系数据库中的项集和对象中发现频繁模式、关联规则、相关性或者因果结构 频繁模式: 数据库中频繁出
2、现的项集 目的: 发现数据中的规律 超市数据中的什么产品会一起购买? 啤酒和尿布 在买了一台PC之后下一步会购买? 哪种DNA对这种药物敏感? 我们如何自动对Web文档进行分类?,频繁模式挖掘的重要性,许多重要数据挖掘任务的基础 关联、相关性、因果性 序列模式、空间模式、时间模式、多维 关联分类、聚类分析 更加广泛的用处 购物篮分析、交叉销售、直销 点击流分析、DNA序列分析等等,关联规则基本模型,关联规则基本模型 Apriori算法,关联规则基本模型,IBM公司Almaden研究中心的R.Agrawal首先提出关联规则模型,并给出求解算法AIS。随后又出现了SETM和Apriori等算法。其中,Apriori是关联规则模型中的经典算法。 给定一组事务 产生所有的关联规则 满足最小支持度和最小可信度,关联规则基本模型(续),设I=i1, i2, im为所有项目的集合,D为事务数据库,事务T是一个项目子集(TI)。每一个事务具有唯一的事务标识TID。设A是一个由项目构成的集合,称为项集。事务T包含项集A,当且仅当AT。如果项集A中包含k个项目,则称其为k项集。项集A在事务数据库D中出现的
3、次数占D中总事务的百分比叫做项集的支持度。如果项集的支持度超过用户给定的最小支持度阈值,就称该项集是频繁项集(或大项集)。,关联规则基本模型(续),关联规则是形如XY的逻辑蕴含式,其中XI,YI,且XY=。如果事务数据库D中有s%的事务包含XY,则称关联规则XY的支持度为s%,实际上,支持度是一个概率值。若项集X的支持度记为support (X),规则的信任度为support (XY)support (X)。这是一个条件概率P (Y | X)。也就是: support (XY)=P (X Y) confidence (XY)=P (Y | X),规则度量:支持度与可信度,查找所有的规则 X & Y Z 具有最小支持度和可信度 支持度, s, 一次交易中包含X 、 Y 、 Z的可能性 可信度, c, 包含X 、 Y的交易中也包含Z的条件概率,设最小支持度为50%, 最小可信度为 50%, 则可得到 A C (50%, 66.6%) C A (50%, 100%),买尿布的客户,二者都买的客户,买啤酒的客户,关联规则基本模型(续),关联规则就是支持度和信任度分别满足用户给定阈值的规则。 发
4、现关联规则需要经历如下两个步骤: 找出所有频繁项集。 由频繁项集生成满足最小信任度阈值的规则。,Let min_support = 50%, min_conf = 50%: A C (50%, 66.7%) C A (50%, 100%),For rule A C: support = support(AC) = 50% confidence = support(AC)/support(A) = 66.6%,Min. support 50% Min. confidence 50%,Apriori算法的步骤,Apriori算法命名源于算法使用了频繁项集性质的先验(Prior)知识。 Apriori算法将发现关联规则的过程分为两个步骤: 通过迭代,检索出事务数据库中的所有频繁项集,即支持度不低于用户设定的阈值的项集; 利用频繁项集构造出满足用户最小信任度的规则。 挖掘或识别出所有频繁项集是该算法的核心,占整个计算量的大部分。,频繁项集,为了避免计算所有项集的支持度(实际上频繁项集只占很少一部分),Apriori算法引入潜在频繁项集的概念。若潜在频繁k项集的集合记为Ck ,频繁k项集的集合记
5、为Lk ,m个项目构成的k项集的集合为 ,则三者之间满足关系Lk Ck 。构成潜在频繁项集所遵循的原则是“频繁项集的子集必为频繁项集”。,关联规则的性质:,性质6.1 频繁项集的子集必为频繁项集。 性质6.2 非频繁项集的超集一定是非频繁的。 Apriori算法运用性质6.1,通过已知的频繁项集构成长度更大的项集,并将其称为潜在频繁项集。潜在频繁k项集的集合Ck 是指由有可能成为频繁k项集的项集组成的集合。以后只需计算潜在频繁项集的支持度,而不必计算所有不同项集的支持度,因此在一定程度上减少了计算量。,Apriori算法,(1) L1=频繁1项集; (2) for(k=2;Lk-1;k+) do begin (3) Ck=apriori_gen(Lk-1); /新的潜在频繁项集 (4) for all transactions tD do begin (5) Ct=subset(Ck,t); /t中包含的潜在频繁项集 (6) for all candidates cCt do (7) c.count+; (8) end; (9) Lk=cCk|c.countminsup (10) en
《数据挖掘应用- 浙江大学计算机科学与技术学院》由会员jiups****uk12分享,可在线阅读,更多相关《数据挖掘应用- 浙江大学计算机科学与技术学院》请在金锄头文库上搜索。
建立安全生产长效机制-共创和谐平安输气管道
土石方爆破工程设计方案
康师傅百货商场制度汇编之退换货管理办法
庙头中学2012年中考百日誓师大会学生代表发言稿
围堰拆除爆破工程
华能洱源马鞍山风电场工程土石方爆破管理制度
国资委:全面开展管理提升活动-为培育世界一流企业奠定坚实基础
《专业技术人员职业发展与规划》电子书
应收票据审计方案
建筑给水排水与采暖工程质量验收用表
广播电视管理条例行政处罚裁量标准
广东电力系统调度运行操作管理规定
建筑给排水工程名词解释
幼儿园小班安全健康活动教案:宝宝误食后的急救
建业集团房屋建筑工程交房标准内容技术交底
建筑心理学论文(1)
康师傅百货商场制度汇编之工服管理程序009
建筑工程专业一级建造师继续教育培训结业报告20
廉洁风险防控回头看工作汇报材料
平台工作人员服务规范
2024-04-08 20页
2024-04-06 36页
2024-02-09 36页
2024-01-31 31页
2024-01-28 18页
2024-01-28 31页
2024-01-28 24页
2024-01-28 27页
2024-01-28 24页
2024-01-28 25页