第五章关联规则挖掘

《第五章关联规则挖掘》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章关联规则挖掘DataMining《数据挖掘》■引言若两个或多个变量的取值之间存在某种规律性，则称为关联。关联规则是寻找在同一个事件中出现的不同项的相关性。比如，在一次购物活动中所购买不同商品的相关性。关联分析是利用关联规则进行数据挖掘。关联规则挖掘最初的形式是零售商的购物蓝分析。购物蓝分析是通过发现顾客放入购物蓝中不同商品间的关联，帮助零售商制定营销策略。2■引言购物篮分析例子：在购买计算机的顾客中，有30%的人也同时购买了打印机。通过分析，得出计算机和打印机存在关联。策略一：将计算机和打印机放得近一些，以增加两者的销售。策略二：将计算

2、机和打印机放在商品两头，以诱发顾客购买更多的商品。关联分析的目的：挖掘隐藏在数据间的相互关系，自动探测以前未发现的隐藏着的模式。关联规则的主要应用对象是事物数据库，侧重于确定数据不同项目（商品）之间的联系。典型例子：啤酒和尿布。3■引言关联规则提出后，对它的研究主要集中在五个方面：（1）关联关系的研究，由于频繁关系在不同数据对象和应用环境中具有不同形式，称这种频繁关系为关联关系。（2）提高关联规则挖掘的效率，即提高挖掘速度，减少存储空间需求。（3）如何在稠密集、大量或海量数据集中进行关联规则挖掘。（4）如何挖掘有价值的关联规则。（5）如何利用

3、关联规则。大量的研究集中于关联规则挖掘效率的研究。有代表性的算法有：Apriori算法、DHP算法、Partition算法、Sear算法、FP-Growth算法、TopDown、FP-Growth、TreeProject等4一、关联规则概述1.关联规则挖掘的基本概念（1）数据项与数据项集设I=｛i1，i2，┅im｝是m个不同项目的一个集合，每个ik（k=1，2，┅m）称为数据项，数据项的集合I称为数据项集，简称为项集，其元素个数称为数据项集的长度。长度为k的数据项集称为k维数据项集，简称为k-项集。例如，数据项集I=｛啤酒、面包、果冻、牛奶、

4、花生酱｝5一、关联规则概述（2）事务事务T是数据项集I的一个子集，即每个事物均有一个唯一的标识符TID与之相联，不同事物的全体构成了全体事物集D（即事物数据库）。例如，数据项集I=｛啤酒、面包、果冻、牛奶、花生酱｝的5个事务：t1=｛面包、果冻、花生酱｝t2=｛面包、花生酱｝t3=｛面包、牛奶、花生酱｝t4=｛啤酒、面包｝t5=｛啤酒、牛奶｝6一、关联规则概述（3）数据项集的支持度项目（或项目集）的支持度是指包含该项目（或项目集）的事务占库中所有事务的百分比。下表是所有项目集合的支持度：集合支持度集合支持度啤酒40面包80果冻20牛奶40花生

5、酱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啤酒、面包、果冻、牛奶、花生酱07一、关联规则概述（4）关联规则关联规则可以

6、表示为：它表示如果项目集X在某一事务中出现，则必然导致项目集Y也会在同一事务中出现。X称为规则的先决条件，Y称为规则的结果。（5）关联规则的支持度关联规则X=>Y的支持度是数据库中包含X∪Y的事务占库中所有事物数的比值。表明了规则在整个数据库中出现的频率。8一、关联规则概述（6）关联规则的置信度关联规则X=>Y的置信度是包含X∪Y的事务数与包含X的事物数的比值。关联规则X=>Y支持度（%）置信度（%）面包=>花生酱花生酱=>面包啤酒=>面包花生酱=>果冻果冻=>花生酱果冻=>牛奶60602020200751005033.31000说明：①面包

7、=>花生酱的置信度为75%，表明在面包出现时有75%的情况花生酱也出现。②果冻=>花生酱的置信度为100%，但支持度只有20%表明这条关联规则只存在20%的事务中，但当果冻出现时花生酱总是出现。9一、关联规则概述2、关联规则挖掘问题关联规则的挖掘就是发现具有用户指定的具有最小支持度和最小置信度的关联规则。置信度太低，说明规则的可信程度差；支持度太低，则说明规则不具有一般性。数据挖掘的目的在于找出那些可信的并且具有代表性的规则。（1）关联规则挖掘问题的形式描述如下：给定事务的集合T，关联规则发现是指支持度大于等于minsup并且置信度大于等于m

8、inconf的所有规则，其中minsup和minconf是对应的支持度和置信度阈值。10一、关联规则概述（2）关联规则挖掘算法通常采用的策略将关联规则挖掘任务分解为