文档介绍：第八章关联规则
本章目标
解释关联规则技术的建模特性。
分析大型数据库的基本特性。
描述Apriori算法,并通过示例来解释算法的所有步骤。
将频繁模式增长方法同Apriori算法进行比较。
概述从频繁集中产生关联规则的方法。
第八章关联规则
本章目标
举例说明使用HITs、LOGSOM和路径遍历算法来进行Web挖掘的可行性。
在指定提炼和萃取阶段的基础上定型文本挖掘的构架。
关联规则是数据挖掘的主要技术之一,也是在无指导学习系统中挖掘本地模式的最普遍形式。
本章除了重点介绍关联规则挖掘的Apriori技术外,还将讨论一些和Web挖掘、文本挖掘相关的数据挖掘方法。
购物篮分析
购物篮是顾客在一次事务中所购买项的集合,所谓事务是一个明确定义的商业行为。
事务数据库研究的一个最普通的例子就是寻找项的集合,或叫做项集。包含i个项的项集被称为i-项集。包含该项集的事务的百分数叫做该项集的支持度。支持度超过指定阈值的项集叫做频繁项集。
基本概念:
设I={i1,i2,…im}是项的集合,DB为事务集合,其中每个事务T是项的集合,且有。每一个事务有一个标识符,称作TID。设X为一个项集,当且仅当时,即T包含X。关联规则是形如的蕴涵式,其中,
,且。规则在事务集DB中成立,具有支持度s,其中s是DB中事务包含X和Y两者的百分比。规则在事务集DB中具有置信度c,如果DB中包含X的事务同时也包含Y的百分比是c。
支持度是概率。
置信度是概率。
置信度可以表示规则的可信性,支持度表示模式在规则中出现的频率。具有高置信度和强支持度的规则被称为强规则。
挖掘关联规则的问题可以分两个阶段:
,也就是事务支持度s大于预先给定的最小阈值的项的集合。
。
Apriori算法是解决这个问题的常用方法。
APRIORI算法
Apriori算法利用几次迭代来计算数据库中的频繁项集。第i次迭代计算出所有频繁i项集(包含i个元素的项集)。每一次迭代有两个步骤:产生候选集;计算和选择候选集。
在第一次迭代中,产生的候选集包含所有1-项集,并计算其支持度s,s大于阈值的1-项集被选为频繁1-项集。
第二次迭代时,Apriori算法首先去除非频繁1-项集,在频繁1-项集的基础上进行产生频繁2-项集。原理是:如果一个项集是频繁,那么它的所有子集也是频繁的。
例如,以表8-1中的数据为例。假设smin=50%。
在第一次迭代的第一步中,所有单项集都作为候选集,产生一个候选集列表。在下一步中,计算每一项的支持度,然后在smin的基础上选择频繁项集。图8-1中给出第一次迭代的结果。
在挖掘2-项集时,因为2-项集的任何子集都是频繁项集,所以Apriori算法使用L1*L1来产生候选集。*运算通常定义为:
Lk*Lk={X∪Y 其中X,Y∈Lk,|X∩Y|=k+1}
注:|X∩Y|=k+1即X和Y合取容量为k+1
当k=1时,因此,C2包含在第二次迭代中作为候选集由运算|L1|·|L1-1|/2所产生的2-项集。本例中为:4·3/2=6。用该列表来扫描DB,计算每一个候选集的s,并与smin比较2-项集L2。图8-2给出了所有这些步骤和第二次迭代的结果。