文档介绍：第五章关联规则挖掘
东北师大软件学院、理想信息技术研究院
Email:Lixy_2008@
李献业
Data Mining
《数据挖掘》
2
■引言
若两个或多个变量的取值之间存在某种规律性,则称为关联。
关联规则是寻找在同一个事件中出现的不同项的相关性。
比如,在一次购物活动中所购买不同商品的相关性。
关联分析是利用关联规则进行数据挖掘。
关联规则挖掘最初的形式是零售商的购物蓝分析。
购物蓝分析是通过发现顾客放入购物蓝中不同商品间的关联,帮助零售商制定营销策略。
3
■引言
购物篮分析例子:
在购买计算机的顾客中,有30%的人也同时购买了打印机。通过分析,得出计算机和打印机存在关联。
策略一:将计算机和打印机放得近一些,以增加两者的销售。
策略二:将计算机和打印机放在商品两头,以诱发顾客购买更多的商品。
关联分析的目的:挖掘隐藏在数据间的相互关系,自动探测以前未发现的隐藏着的模式。
关联规则的主要应用对象是事物数据库,侧重于确定数据不同项目(商品)之间的联系。典型例子:啤酒和尿布。
4
■引言
关联规则提出后,对它的研究主要集中在五个方面:
(1)关联关系的研究,由于频繁关系在不同数据对象和应用环境中具有不同形式,称这种频繁关系为关联关系。
(2)提高关联规则挖掘的效率,即提高挖掘速度,减少存储空间需求。
(3)如何在稠密集、大量或海量数据集中进行关联规则挖掘。
(4)如何挖掘有价值的关联规则。
(5)如何利用关联规则。
大量的研究集中于关联规则挖掘效率的研究。有代表性的算法有:
Apriori算法、DHP算法、Partition算法、Sear算法、FP-Growth算法、TopDown、FP-Growth、TreeProject等
5
一、关联规则概述

(1)数据项与数据项集
设I={i1,i2,┅im}是m个不同项目的一个集合,每个ik(k=1,2,┅m)称为数据项,数据项的集合I称为数据项集,简称为项集,其元素个数称为数据项集的长度。长度为k的数据项集称为k维数据项集,简称为k-项集。
例如,数据项集I={啤酒、面包、果冻、牛奶、花生酱}
6
一、关联规则概述
(2)事务
事务T是数据项集I的一个子集,即每个事物均有一个唯一的标识符TID与之相联,不同事物的全体构成了全体事物集D(即事物数据库)。
例如,数据项集I ={啤酒、面包、果冻、牛奶、花生酱}的5个事务:
t1={面包、果冻、花生酱}
t2={面包、花生酱}
t3={面包、牛奶、花生酱}
t4={啤酒、面包}
t5={啤酒、牛奶}
7
一、关联规则概述
(3)数据项集的支持度
项目(或项目集)的支持度是指包含该项目(或项目集)的事务占库中所有事务的百分比。下表是所有项目集合的支持度:
集合支持度
集合支持度
啤酒 40
面包 80
果冻 20
牛奶 40
花生酱 60
啤酒、面包 20
啤酒、果冻 0
啤酒、牛奶 20
啤酒、花生酱 0
面包、果冻 20
面包、牛奶 20
面包、花生酱 60
果冻、牛奶 0
果冻、花生酱 20
牛奶、花生酱 20
啤酒、面包、果冻 0
啤酒、面包、牛奶 0
啤酒、面包、花生酱 0
啤酒、果冻、牛奶 0
啤酒、果冻、花生酱 0
啤酒、牛奶、花生酱 0
面包、果冻、牛奶 0
面包、果冻、花生酱 20
面包、牛奶、花生酱 20
果冻、牛奶、花生酱 0
啤酒、面包、果冻、牛奶 0
啤酒、面包、果冻、花生酱 0
啤酒、面包、牛奶、花生酱 0
啤酒、果冻、牛奶、花生酱 0
面包、果冻、牛奶、花生酱 0
啤酒、面包、果冻、牛奶、花生酱 0
8
一、关联规则概述
(4)关联规则
关联规则可以表示为:
它表示如果项目集X在某一事务中出现,则必然导致项目集Y也会在同一事务中出现。X称为规则的先决条件,Y称为规则的结果。
(5)关联规则的支持度
关联规则X=>Y的支持度是数据库中包含X∪Y的事务占库中所有事物数的比值。表明了规则在整个数据库中出现的频率。
9
一、关联规则概述
(6)关联规则的置信度
关联规则X=>Y的置信度是包含X∪Y的事务数与包含X的事物数的比值。
关联规则X=>Y
支持度(%)
置信度(%)
面包=>花生酱
花生酱=>面包
啤酒=>面包
花生酱=>果冻
果冻=>花生酱
果冻=>牛奶
60
60
20
20
20
0
75
100
50

100
0
说明:
①面包=>花生酱的置信度为75%,表明在面包出现时有75%的情况花生酱也出现。
②果冻=>花生酱的置信度为100%,但支持度只有20%表明这条关联规则只存在20%的事务中,但当果冻出现时花生酱总是出现。
10
一、