数据挖掘常用算法概述讲述.ppt

关联分析 关联规则挖掘的提出 关联规则挖掘的典型案例：购物篮问题 在商场中拥有大量的商品（项目），如：牛奶、面包等，客户将所购买的商品放入到自己的购物篮中。 通过发现顾客放入购物篮中的不同商品之间的联系，分析顾客的购买习惯 哪些物品经常被顾客购买？ 同一次购买中，哪些商品经常会被一起购买？ 一般用户的购买过程中是否存在一定的购买时间序列？ 具体应用：利润最大化 商品货架设计：更加适合客户的购物路径 货存安排 ：实现超市的零库存管理 用户分类 ：提供个性化的服务 其他典型应用 相关文献的收集 购物篮 = 文档（Document） 项 目 = 单词（Word） 相关网站的收集 购物篮 = 词句（Sentences） 项 目 =链接文档（Document） 什么是关联规则挖掘? 关联规则挖掘 简单的说，关联规则挖掘发现大量数据中项集之间有趣的关联 在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。 应用 购物篮分析、交叉销售、产品目录设计、 loss-leader analysis、聚集、分类等。 关联规则挖掘形式化定义 给定: 交易数据库 每笔交易是：一个项目列表 (消费者一次购买活动中购买的商品) 查找: 所有描述一个项目集合与其他项目集合相关性的规则 应用 * ? 护理用品 (商店应该怎样提高护理用品的销售？) 家用电器 ? * (其他商品的库存有什么影响?) 在产品直销中使用附加邮寄 其它相关概念 包含k个项目的集合，称为k-项集 项集的出现频率是包含项集的事务个数，称为项集的频率、支持计数或者计数 关联规则的基本形式：前提条件 ? 结论 [支持度, 置信度] buys(x, “diapers”) ? buys(x, “beers”) [0.5%, 60%] major(x, “CS”) ^ takes(x, “DB”) ? grade(x, “A”) [1%, 75%] 关联规则兴趣度的度量值：支持度 推导出的数据间的相关性可称为规则（或模式），对规则兴趣度的描述采用支持度、置信度概念。 支持度（Support）：规则X?Y在交易数据库D中的支持度是交易集中包含X和Y的交易数与所有交易数之比，记为support(X?Y)，即support(X?Y)=|{T:X?Y? T，T?D}|/ |D|，它是概率P（ X?Y ），具体表示为： 关联规则兴趣度的度量值：置信度 置信度（Confidence），规则X?Y在交易集中的置信度是指包含X和Y的交易数与包含X的交易数之比，记为confidence(X?Y)，即confidence(X?Y)=|{T: X?Y?T，T?D}|/|{T:X?T，T?D}|，它是概率P（ X|Y ），具体表示为： 最小支持度和最小置信度 用户（分析员）不关心可信程度太低的规则，因而用户需要输入两个参数：最小支持度和最小置信度。 支持度和置信度举例 零售商场销售分析： 数据项为商品，记录集合为交易记录集合 规则为：“购买商品X的顾客，同时购买商品Y”，即X ? Y； 设最小支持度为0 .3；最小置信度也为0.3。 分析结果： 频繁项集及其基本特征 频繁项集的定义 如果项集满足最小支持度，则称之为频繁项集（高频项集） 频繁项集的基本特征 任何频繁项集的子集均为频繁项集。例如：ABC是频繁项集，则AB、AC、BC均为频繁项集 在数据库表分区的情况下，一个项集是频繁的，则至少在一个分区内是频繁的 关联规则挖掘的种类 布尔 vs. 数值型关联 (基于 处理数据的类型) 性别＝“女” ? 职业＝“ 秘书” [1%, 75%] 布尔型关联规则 性别＝“女” ? 收入 = 2000 [1%, 75%] 数值型关联规则 单维 vs. 多维 关联 age(x, “30..39”) ^ income(x, “42..48K”) ? buys(x, “PC”) [1%, 75%] buys(x, “Book”) ^buys(x, “Pen”) ? buys(x, “Ink”) [1%, 75%] 单层 vs. 多层 分析 那个品种牌子的啤酒与那个牌子的尿布有关系? 各种扩展 相关性、因果分析 关联并不一定意味着相关或因果 最大模式和闭合相集 添加约束 如, 哪些“小东西”的销售促发了“大家伙”的买卖？ 关联规则挖掘的基本过程 找出所有的频繁项集 F，其中对于任何的 Z ? F，在交易集合D中至少 s%的事务包含Z 根据置信度和频繁项集F, 产生关联规则。具体方法如下： conf(X ? Y) = supp(X)/supp(X ? Y) 如果 conf(X ?