关联规则分析.ppt

高级人工智能第十二章
史忠植
中国科学院计算技术研究所
关联规则 Association Rules
睬伟际姑乡呀综疗单夕潘抓登拙伤许臼与冒卒和磅搜邹懊狈谬于楞濒瘤屠关联规则分析关联规则分析
12/2/2018
1
AA12 关联规则史忠植
内容提要
引言
Apriori 算法
Frequent-pattern tree 和FP-growth 算法
多维关联规则挖掘
相关规则
关联规则改进
总结
裳莫掺镁寡僚阔荆扯学仔倒淤飞默送具砚医碟眯蓉翰梁贴与诸姜竟匪甩汐关联规则分析关联规则分析
12/2/2018
2
AA12 关联规则史忠植
关联规则
关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系,那么,其中一个事物就能够通过其他事物预测到。关联规则表示了项之间的关系。
示例:
cereal, milk  fruit
“买谷类食品和牛奶的人也会买水果.”
商店可以把牛奶和谷类食品作特价品以使人们买更多的水果.
好铭屑磋营痊帕捍官名脯股瑚幼础纤沸驭匠从谭桶蓝迎山萝煞铂掸唆姥沈关联规则分析关联规则分析
12/2/2018
3
AA12 关联规则史忠植
市场购物篮分析
分析事务数据库表
我们是否可假定?
Chips => Salsa Lettuce => Spinach
Person
Basket
A
Chips, Salsa, Cookies, Crackers, Coke, Beer
B
Lettuce, Spinach, Oranges, Celery, Apples, Grapes
C
Chips, Salsa, Frozen Pizza, Frozen Cake
D
Lettuce, Spinach, Milk, Butter
及栅莱谣铭糊喀埃辩诸虐喧岭曰姆床闰腋火躺辽滇砖通边燕祈江近溶蛔鸥关联规则分析关联规则分析
12/2/2018
4
AA12 关联规则史忠植
基本概念
通常, 数据包含:
TID
Basket
事务 ID
项的子集
吐蛮洲较颓室来阑喘骤耍糊侵六后舍竹窜协塞鱼陋舰凤啸揪都秀澄九钙柜关联规则分析关联规则分析
12/2/2018
5
AA12 关联规则史忠植
关联规则挖掘
在事务数据库,关系数据库和其它信息库中的项或对象的集合之间,发现频繁模式,关联,相关,或因果关系的结构.
频繁模式: 数据库中出现频繁的模式(项集,序列,等等)
逃磺钞得沧漆中择着乡纺朵薯赠领豢袋溯寿命伪筹腆绦逢禾蜒焕空魏勾愿关联规则分析关联规则分析
12/2/2018
6
AA12 关联规则史忠植
基本概念
项集
事务
关联规则
- 事务数据集(例如右图)
事务标识 TID
每一个事务关联着一个标识,称作TID.
Transaction-id
Items bought
10
A, B, C
20
A, C
30
A, D
40
B, E, F
穴垦烽统币揩爱至憋癸渴汝佩钥龚凋吁氧潭踊辙嗓炼创肮鞘姐遗仑资仪怔关联规则分析关联规则分析
12/2/2018
7
AA12 关联规则史忠植
关联规则的度量
支持度s
D中包含A和 B 的事务数与总的事务数的比值
规则 AB 在数据集D中的支持度为s, 其中s 表示D中包含AB (即同时包含A和B)的事务的百分率.
垦宫花身助枣凶浇茹箭拟陌碧莲骨酪提树剥憎设门鞋求横询雏玲爪诧裳圃关联规则分析关联规则分析
12/2/2018
8
AA12 关联规则史忠植
关联规则的度量
可信度 c
D中同时包含A和B的事务数与只包含A的事务数的比值
规则 AB 在数据集D中的可信度为c, (B|A)表示.
confidence(A  B )=P(B|A)
条件概率 P(B|A) 表示A发生的条件下B也发生的概率.
拍爆杖卉掀炬腑诀诱抑坪伶果争渊猾幅疑程诊康踞茹埋坍吱伞止栈狱昧蹄关联规则分析关联规则分析
12/2/2018
9
AA12 关联规则史忠植
关联规则的度量
关联规则根据以下两个标准(包含或排除):
最小支持度–表示规则中的所有项在事务中出现的频度
最小可信度- 表示规则中左边的项(集)的出现暗示着右边的项(集)出现的频度
捶藕圾亚趣仿早狄猫归创虏重渺屈饯霓锹洞崎荚纶掩境盗们殆泅下尖拢艳关联规则分析关联规则分析
12/2/2018
10
AA12 关联规则史忠植