ar(2)（精选）.ppt

数据挖掘: 概念和技术 — Chapter 6 —
©张晓辉
******@
复旦大学(国际)数据库研究中心
2001-11-6
1
数据挖掘:概念和技术
第6章:从大数据库中挖掘关联规则
关联规则挖掘
从交易数据库中挖掘一维的布尔形关联规则
从交易数据库中挖掘多层次关联规则
在交易数据库和数据仓库中挖掘多维关联规则
从关联挖掘到相关性分析
基于约束的关联挖掘
小结
2001-11-6
2
数据挖掘:概念和技术
什么是关联挖掘?
关联规则挖掘:
在交易数据、关系数据或其他信息载体中,查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。
应用:
购物篮分析、交叉销售、产品目录设计、 loss-leader analysis、聚集、分类等。
举例:
规则形式: “Body ® Head [support, confidence]”.
buys(x, “diapers”) ® buys(x, “beers”) [%, 60%]
major(x, “CS”) ^ takes(x, “DB”) ® grade(x, “A”) [1%, 75%]
2001-11-6
3
数据挖掘:概念和技术
关联规则:基本概念
给定: (1)交易数据库(2)每笔交易是:一个项目列表(消费者一次购买活动中购买的商品)
查找: 所有描述一个项目集合与其他项目集合相关性的规则
., 98% of people who purchase tires and auto accessories also get automotive services done
应用
* 护理用品(商店应该怎样提高护理用品的销售?)
家用电器* (其他商品的库存有什么影响?)
在产品直销中使用附加邮寄
Detecting “ping-pong”ing of patients, faulty “collisions”
2001-11-6
4
数据挖掘:概念和技术
规则度量:支持度与可信度
查找所有的规则 X & Y  Z 具有最小支持度和可信度
支持度, s, 一次交易中包含{X 、 Y 、 Z}的可能性
可信度, c, 包含{X 、 Y}的交易中也包含Z的条件概率
设最小支持度为50%, 最小可信度为 50%, 则可得到
A  C (50%, %)
C  A (50%, 100%)
买尿布的客户
二者都买的客户
买啤酒的客户
2001-11-6
5
数据挖掘:概念和技术
关联规则挖掘:路线图
布尔 vs. 定量关联(基于处理数据的类型)
buys(x, “SQLServer”) ^ buys(x, “DMBook”) ® buys(x, “DBMiner”) [%, 60%]
age(x, “30..39”) ^ e(x, “42..48K”) ® buys(x, “PC”) [1%, 75%]
单维 vs. 多维关联(例子同上)
单层 vs. 多层分析
那个品种牌子的啤酒与那个牌子的尿布有关系?
各种扩展
相关性、因果分析
关联并不一定意味着相关或因果
最大模式和闭合相集
添加约束
如, 哪些“小东西”的销售促发了“大家伙”的买卖?
2001-11-6
6
数据挖掘:概念和技术
第6章:从大数据库中挖掘关联规则
关联规则挖掘
从交易数据库中挖掘一维的布尔形关联规则
从交易数据库中挖掘多层次关联规则
在交易数据库和数据仓库中挖掘多维关联规则
从关联挖掘到相关性分析
基于约束的关联挖掘
小结
2001-11-6
7
数据挖掘:概念和技术
关联规则挖掘—一个例子
对于 A  C:
support = support({A 、C}) = 50%
confidence = support({A 、C})/support({A}) = %
Apriori的基本思想:
频繁项集的任何子集也一定是频繁的
最小值尺度 50%
最小可信度 50%
2001-11-6
8
数据挖掘:概念和技术
关键步骤:挖掘频繁集
频繁集:是指满足最小支持度的项目集合
频繁集的子集也一定是频繁的
如, 如果{AB} 是频繁集,则{A} {B} 也一定是频繁集
从1到k(k-频繁集)递归查找频繁集
用得到的频繁集生成关联规则
2001-11-6
9
数据挖掘:概念和技术
Apriori算法
连接: 用 Lk-1自连接得到Ck
修剪: 一个k-项集,如果他的一个k-1项集(他的子集)不是频繁的,那他本身也不可能是频繁的。
伪代码:
Ck: Candidate itemset of size k
Lk : frequent itemse