支持度是概率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给出了所有这些步骤和第二次 迭代的结果