第八章关联规则 本章目标 >解释关联规则技术的建模特性。 分析大型数据库的基本特性。 描述 Apriori算法,并通过示例来解释算法的 所有步骤 >将频繁模式增长方法同Apηor算法进行比较。 >概述从频繁集中产生关联规则的方法
第八章 关联规则 本章目标 ➢ 解释关联规则技术的建模特性。 ➢ 分析大型数据库的基本特性。 ➢ 描述Apriori算法，并通过示例来解释算法的 所有步骤。 ➢ 将频繁模式增长方法同Apriori算法进行比较。 ➢ 概述从频繁集中产生关联规则的方法
第八章关联规则 本章目标 举例说明使用HTs、 LOGSOM和路径遍历 算法来进行Web挖掘的可行性。 >在指定提炼和萃取阶段的基础上定型文本 挖掘的构架
第八章 关联规则 本章目标 ➢ 举例说明使用HITs、LOGSOM和路径遍历 算法来进行Web挖掘的可行性。 ➢ 在指定提炼和萃取阶段的基础上定型文本 挖掘的构架
关联规则是数据挖掘的主要技术之 也是在无指导学习系统中挖掘本地模 式的最普遍形式。 >本章除了重点介绍关联规则挖掘的 Apo技术外,还将讨论一些和Web 挖掘、文本挖掘相关的数据挖掘方法
➢关联规则是数据挖掘的主要技术之一， 也是在无指导学习系统中挖掘本地模 式的最普遍形式。 ➢本章除了重点介绍关联规则挖掘的 Apriori技术外，还将讨论一些和Web 挖掘、文本挖掘相关的数据挖掘方法
8.1购物篮分析 >购物篮是顾客在一次事务中所购买项的集 合,所谓事务是一个明确定义的商业行为。 事务数据库硏究的一个最普通的例子就是 寻找项的集合,或叫做项集。包含个项的 项集被称为ⅰ-项集。包含该项集的事务的百 分数叫做该项集的支持度。支持度超过指 定阈值的项集叫做频繁项集
8.1 购物篮分析 ➢ 购物篮是顾客在一次事务中所购买项的集 合，所谓事务是一个明确定义的商业行为。 ➢ 事务数据库研究的一个最普通的例子就是 寻找项的集合，或叫做项集。包含i个项的 项集被称为i-项集。包含该项集的事务的百 分数叫做该项集的支持度。支持度超过指 定阈值的项集叫做频繁项集
>基本概念 设={i12,m}是项的集合,DB为事务集合, 其中每个事务T是项的集合,且有Tc 个事务有一个标识符,称作TD。设X为 个项集,当且仅当XT即T包含X。关联 规则是形如的→Y式,其中 Xc且X∩Y=则Ⅹ→Y务集DB中 成立,具有支持度s,其中s是DB中事务包含 X和Y两者的百分比。规则 X→Y集 DB中具有置信度c,如果DB中包含X的事务 同时也包含Y的百分比是c
➢ 基本概念： 设I={i1 ,i2 ,…im}是项的集合，DB为事务集合， 其中每个事务T是项的集合，且有 。每一 个事务有一个标识符，称作TID。 设X为一 个项集，当且仅当 时，即T包含X。关联 规则是形如 的蕴涵式，其中 , ,且 。规则 在事务集DB中 成立，具有支持度s，其中s是DB中事务包含 X和Y两者的百分比。规则 在事务集 DB中具有置信度c，如果DB中包含X的事务 同时也包含Y的百分比是c。 XY T I X T X I X I XY = X Y X Y
支持度是概率PXUY >置信度是概率PYX。 >置信度可以表示规则的可信性,支持度表示 模式在规则中出现的频率。具有高置信度和 强支持度的规则被称为强规则。 >挖掘关联规则的问题可以分两个阶段 1.发掘大项集,也就是事务支持度sS大于预 先给定的最小阈值的项的集合。 2.使用大项集来产生数据库中置信度c大于 预先给定的最小阈值的关联规则。 Apio算法是解决这个问题的常用方法
➢ 支持度是概率 。 ➢ 置信度是概率 。 ➢ 置信度可以表示规则的可信性，支持度表示 模式在规则中出现的频率。具有高置信度和 强支持度的规则被称为强规则。 ➢ 挖掘关联规则的问题可以分两个阶段： 1.发掘大项集，也就是事务支持度s大于预 先给定的最小阈值的项的集合。 2.使用大项集来产生数据库中置信度c大于 预先给定的最小阈值的关联规则。 ➢ Apriori算法是解决这个问题的常用方法。 P(X Y) P(Y | X)
82 APRIOR算法 Apor算氵 法利用几 次迭代来i 计算 数据库 中的 频繁项集。第i次迭代计算出所有频繁项集 (包含个元素的项集)。每次迭代有两个步 骤∶产生候选集;计算和选择候选集。 >在第一次迭代中,产生的候选集包含所有1 项集,并计算其支持度s,s大于阈值的1-项 集被选为频繁1-项集。 >第二次迭代时, Apriori算法首先去除非频繁 1-项集,在频繁1-项集的基础上进行产生频 繁2-项集。原理是:如果一个项集是频篆, 那么它的所有子集也是频繁的
8.2 APRIORI算法 ➢ Apriori算法利用几次迭代来计算数据库中的 频繁项集。第i次迭代计算出所有频繁i项集 (包含i个元素的项集)。每一次迭代有两个步 骤：产生候选集；计算和选择候选集。 ➢ 在第一次迭代中，产生的候选集包含所有1- 项集，并计算其支持度s，s大于阈值的1-项 集被选为频繁1-项集。 ➢ 第二次迭代时，Apriori算法首先去除非频繁 1-项集，在频繁1-项集的基础上进行产生频 繁2-项集。原理是：如果一个项集是频繁， 那么它的所有子集也是频繁的
>例如,以表8-1中的数据为例。假设 Smin=50%o 表8-1一个简单事务数据库的模型 数据库DB TID 项 001 ACD BCE ABCE BE
➢ 例如，以表8-1中的数据为例。假设 smin=50%
在第一次迭代的第一步中,所有单项集都 作为候选集,产生一个候选集列表。在下 步中,计算每一项的支持度,然后在smn 的基础上选择频繁项集。图8-1中给出第 次迭代的结果。 1-项集C 1-项集计数S‰ 大1项集L1计数S LAM LAN 50 LAN {C} 75 {D} {B} B 75 E {E} B 75 75 a)生成阶段 bl)计算阶段 b2)选择阶段 图81针对数据库DB的 apriori算法的第一次迭代
➢ 在第一次迭代的第一步中，所有单项集都 作为候选集，产生一个候选集列表。在下 一步中，计算每一项的支持度，然后在smin 的基础上选择频繁项集。图8-1中给出第一 次迭代的结果
在挖掘2项集时,因为2-项集的任何子集都 是频繁项集,所以Apio算法使用L礼1来 产生候选集。*运算通常定义为 L“Lk=ⅨXUY其中×,Y∈L∩Y=k+1} 注∩Y=k+1即×和Y合取容量为k+1 >当k=1时,因此,C2包含在第二次迭代中作 为候选集由运算μ小L1112所产生的2项集 本例中为:43/2=6。用该列表来扫描DB, 计算每一个候选集的s,并与sm比较2项 集L2。图8-2给出了所有这些步骤和第二次 迭代的结果
➢ 在挖掘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给出了所有这些步骤和第二次 迭代的结果