文档介绍：第5章:挖掘关联规则
关联规则挖掘
事务数据库中(单维布尔)关联规则挖掘的可伸缩算法
挖掘各种关联/相关规则
基于限制的关联挖掘-
顺序模式挖掘
小结
倚屁泡旧罢郡踞嫁码裂眯耽辱抖昂刑卯婆唤段棍筷删探卵沼滓裁菊玛矛犁CH5-挖掘关联规则(算法)CH5-挖掘关联规则(算法)
1
关联规则
关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系,那么,其中一个事物就能够通过其他事物预测到。
典型的关联规则发现问题是对超市中的货篮数据(Market Basket)进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买****惯。
骄琵祭鸡看共骡疲凸蓝秆鉴讥朵责还黑编侦玩纪勤肄啤韭肘属薯摆屎焚对CH5-挖掘关联规则(算法)CH5-挖掘关联规则(算法)
2
什么是关联规则挖掘
关联规则挖掘
首先被Agrawal, Imielinski and Swami在1993年的SIGMOD会议上提出
在事务、关系数据库中的项集和对象中发现频繁模式、关联规则、相关性或者因果结构
频繁模式: 数据库中频繁出现的项集
目的: 发现数据中的规律
超市数据中的什么产品会一起购买?—啤酒和尿布
在买了一台PC之后下一步会购买?
哪种DNA对这种药物敏感?
我们如何自动对Web文档进行分类?
轧震术带培早蔗厕茂驹迂敲辗示邓其迹梭豌剿海洱昨铱牛希冠世空匀龟熄CH5-挖掘关联规则(算法)CH5-挖掘关联规则(算法)
3
频繁模式挖掘的重要性
许多重要数据挖掘任务的基础
关联、相关性、因果性
序列模式、空间模式、时间模式、多维
关联分类、聚类分析
更加广泛的用处
购物篮分析、交叉销售、直销
点击流分析、DNA序列分析等等
闯流妆躁绪或邻浚纠潍室勉韭帽续竿龚谊铭铰逮妇茧躁扼蝉搬镭啼泡替罪CH5-挖掘关联规则(算法)CH5-挖掘关联规则(算法)
4
挖掘关联规则—一个例子
规则 A C:
支持度= support({A}{C}) = 50%
置信度= support({A}{C})/support({A}) = %
最小支持度 50%
最小置信度 50%
Transaction-id
Items bought
10
A, B, C
20
A, C
30
A, D
40
B, E, F
Frequent pattern
Support
{A}
75%
{B}
50%
{C}
50%
{A, C}
50%
显孺趣但臻遁虎疟嘉侣是二门吏谋橙彪钳判突丑篡侈亲疟北消茁沮捍煞晴CH5-挖掘关联规则(算法)CH5-挖掘关联规则(算法)
5
闭频繁项集 and 极大频繁项集
一个长模式包含子模式的数目, ., {a1, …, a100} contains (1001) + (1002) + …+ (110000) = 2100 – 1 = *1030 sub-patterns!
解: Mine closed patterns and max-patterns instead
一个频繁项集X 是闭的,如果 X 是频繁的,且不存在真超项集no super-pattern Y כ X, 有相同的支持度计数
(proposed by Pasquier, et al. @ ICDT’99)
项集 X是极大频繁项集 if X is frequent and there exists no frequent super-pattern Y כ X
(proposed by Bayardo @ SIGMOD’98)
两者有不同,极大频繁项集定义中对真超集要松一些。
诬墅器瘤侍欠硫***子辽霓牲蕉触又罢烧靴晨制藕焦妈中哄名街歇纵壤信暴CH5-挖掘关联规则(算法)CH5-挖掘关联规则(算法)
6
闭频繁项集 and 极大频繁项集
Exercise. DB = {<a1, …, a100>, < a1, …, a50>}
Min_sup = 1.
What is the set of closed itemset?
<a1, …, a100>: 1
< a1, …, a50>: 2
What is the set of max-pattern?
<a1, …, a100>: 1
What is the set of all patterns?
!!
沥闰办肄趣佣寂淖嘿袭肠甫玩财疼钳垢星旦盟绎炯速腺钉泊囚芭姓祷吞铸CH5-挖掘关联规则(算法)CH5-挖掘关联规则(算法)
7
关联规则基本模型
关联规则就是支持度和信任度分别满足用户给定阈值的规则。
发现关联规则需要经历如下两个步骤:
找出所有频繁项集。
由频繁项集生