Apriori资料.pptx

数据挖掘（DM，Data Mining）;数据挖掘的领域;数据挖掘的经典方法;SQL Server 2008中的9种数据挖掘算法;2.1 关联规则挖掘 ;3 ;2.1 关联规则挖掘 ;6 ;TID ;2.基本概念 设I={i1,i2,…,im}是所有项的集合。 任务相关数据D：是事务（或元组）的集合。 事务T：是项的集合，且每个事务具有事务标识符TID。;基本概念;;;支持度和置信度是两个兴趣度度量,分别反映发现规则的统计有效性和可信程度。 支持度小：规则使用面窄 置信度小：规则无意义 ;满足最小支持度阈值和最小置信度阈值的关联规则被认为是有趣的。阈值由用户或专家设定。 强规则：同时满足用户定义的最小支持度阈值（min_sup）和最小置信度阈值 (min_conf)的规则称为强规则。 为方便计，用0% 和100%之间的值表示支持度和置信度。;项集的频率：即包含项集的事务数，也称为项集的支持计数(support_count)。如果项集的出现频率大于或等于min_sup与D中事务总数的乘积，就称该项集满足最小支持度min_sup。 频集（频繁项集）：满足最小支持度的项集称为频集。k-频集通常记作Lk。 ;关联规则挖掘;Apriori算法;1.Apriori算法 Apriori算法是根据有关频繁项集性质的先验知识而命名的。该算法使用一种逐层有哪些信誉好的足球投注网站的迭代方法，利用(k-1)-项集探索 k-项集。 具体做法：首先找出1-频集的集合，记为L1；再用L1找2-频集的集合L2；再用L2找L3…如此下去，直到不能找到k-频集为止。找每个Lk需要一次数据库扫描。 L1→ L2 → L3 → … → Lk;2.2 挖掘单维布尔关联规则 －Apriori算法 ;2.2 挖掘单维布尔关联规则 －Apriori算法 ;设l1和l2是Lk-1中的项集，记号li[j]表示li的第j项。为方便计，假定事务或项集中的项按字典次序排序。执行连接Lk-1　 Lk-1，其中Lk-1的元素是可连接的，如果它们前(k-2 )个项相同。;2.2 挖掘单维布尔关联规则 －Apriori算法 ;以Lk-1作为输入，输出全部k-频集的一个超集。该函数包含两个操作，连接(join) 与修剪(prune)。连接操作将Lk-1中的频集按如下方式进行拼接： insert into Ck select p[1], p[2], …, p[k-1], q[k-1] from Lk-1 p, Lk-1 q where p[1]=q[1],…, p[k-2]=q[k-2], p[k-1] q[k-1]; ;2.2 挖掘单维布尔关联规则 －Apriori算法 ;为了压缩Ck，可利用Apriori性质： 任何非频繁的(k-1)-项集都不可能是频繁 k-项集的子集。因此，若一个候选k-项集的(k-1)-项子集不在Lk-1中，则该候选也不可能是频繁的，从而可以从Ck中删除。 对Ck中任一候选项集c，若c的某个大小为k-1的子集不属于Lk-1，则将其从 Ck中删除。 forall itemsetsc?Ck do forall(k-1)-subsets s of cdo if (s?Lk-1) then delete c from Ck; ;例子 ;发现频繁项集;;;;;;;（6）候选3-项集的集合C3 的产生如下： ?连接：C3=L2 L2 ;?利用Apriori性质剪枝：频繁项集的所有子集必须是频繁的。存在候选项集， 判断其子集是否频繁。 {1,2,3}的2-项子集是{1,2}，{1,3}和{2,3}, 它们都是L2的元素。因此保留{1,2,3}在C3中。 {1,2,5}的2-项子集是{1,2}，{1,5}和{2,5}, 它们都是L2的元素。因此保留{1,2,5}在C3中。 {1,3,5}的2-项子集是{1,3}，{1,5}和{3,5}, {3,5}不是L2的元素，因而不是频繁的，由C3中 删除{1,3,5}。;{2,3,4}的2-项子集是{2,3}，{2,4}和{3,4},其中{3,4}不是L2的元素，因而不是频繁的， 由C3中删除{2,3,4}。 {2,3,5}的2-项子集是{2,3}，{2,5}和{3,5}, 其中{3,5}不是L2的元素，因而不是频繁的， 由C3中删除 {2,3,5}。 {2,4,5}的2-项子集是{2,4}，{2,5}和{4,5}, 其中{4,5}不是L2的元素，因而不是频繁的， 由C3中删除{2,4,5} 。 ;;;例子（设min_sup = 50%） ;例子（设min_sup = 50%） ;改进的Apriori算法;L1= {1-频集}; C1=事务库D;