高级人工智能十二章培训资料

《高级人工智能十二章培训资料》由会员分享，可在线阅读，更多相关《高级人工智能十二章培训资料（141页珍藏版）》请在金锄头文库上搜索。

1、高级人工智能第十二章,史忠植 中国科学院计算技术研究所,关联规则 Association Rules,2020/7/8,史忠植 关联规则,2,内容提要,引言 Apriori 算法 FP-growth 算法 并行关联规则挖掘 多维关联规则挖掘 相关规则 关联规则改进,2020/7/8,史忠植 关联规则,3,关联规则,关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到。关联规则表示了项之间的关系。 示例: cereal, milk fruit “买谷类食品和牛奶的人也会买水果.” 商店可以把牛奶和谷类食品作

2、特价品以使人们买更多的水果.,2020/7/8,史忠植 关联规则,4,市场购物篮分析,分析事务数据库表 我们是否可假定? Chips = Salsa Lettuce = Spinach,2020/7/8,史忠植 关联规则,6,关联规则挖掘,在事务数据库,关系数据库和其它信息库中的项或对象的集合之间,发现频繁模式,关联,相关,或因果关系的结构. 频繁模式: 数据库中出现频繁的模式(项集,序列,等等),2020/7/8,史忠植 关联规则,7,基本概念,项集 事务 关联规则 - 事务数据集 (例如右图) 事务标识 TID 每一个事务关联着一个标识,称作TID.,2020/7/8,史忠植 关联规则,8

3、,关联规则的度量,支持度s D中包含A和 B 的事务数与总的事务数的比值 规则 AB 在数据集D中的支持度为s, 其中s 表示D中包含AB (即同时包含A和B)的事务的百分率.,2020/7/8,史忠植 关联规则,9,关联规则的度量,可信度 c D中同时包含A和B的事务数与只包含A的事务数的比值,规则 AB 在数据集D中的可信度为c, 其中c表示D中包含A的事务中也包含B的百分率.即可用条件概率P(B|A)表示. confidence(A B )=P(B|A) 条件概率 P(B|A) 表示A发生的条件下B也发生的概率.,2020/7/8,史忠植 关联规则,10,关联规则的度量,关联规则根据以下

4、两个标准(包含或排除): 最小支持度 表示规则中的所有项在事务中出现的频度 最小可信度 - 表示规则中左边的项(集)的出现暗示着右边的项(集)出现的频度,2020/7/8,史忠植 关联规则,11,市场购物篮分析,I是什么? 事务ID B的T是什么? s(Chips=Salsa) 是什么? c(Chips=Salsa)是什么?,2020/7/8,史忠植 关联规则,12,频繁项集,项集 任意项的集合 k-项集 包含k个项的项集 频繁 (或大)项集 满足最小支持度的项集 若I包含m个项,那么可以产生多少个项集?,2020/7/8,史忠植 关联规则,13,强关联规则,给定一个项集,容易生成关联规则.

5、项集: Chips, Salsa, Beer Beer, Chips = Salsa Beer, Salsa = Chips Chips, Salsa = Beer 强规则是有趣的 强规则通常定义为那些满足最小支持度和最小可信度的规则.,2020/7/8,史忠植 关联规则,14,关联规则挖掘,两个基本步骤 找出所有的频繁项集 满足最小支持度 找出所有的强关联规则 由频繁项集生成关联规则 保留满足最小可信度的规则,2020/7/8,史忠植 关联规则,15,内容提要,引言 Apriori 算法 FP-growth 算法 并行关联规则挖掘 多维关联规则挖掘 相关规则 关联规则改进 总结,2020/7

6、/8,史忠植 关联规则,16,Apriori算法,IBM公司Almaden研究中心的R.Agrawal 等人在1993年提出的AIS和SETM。 在1994年提出Apriori和AprioriTid。Apriori和AprioriTid算法利用前次过程中的数据项目集来生成新的候选数据项目集，减少了中间不必要的数据项目集的生成，提高了效率,2020/7/8,史忠植 关联规则,17,生成频繁项集,Nave algorithm n - |D| for each subset s of I do l - 0 for each transaction T in D do if s is a subset

7、 of T then l - l + 1 if minimum support = l/n then add s to frequent subsets,2020/7/8,史忠植 关联规则,18,生成频繁项集,nave algorithm的分析 I 的子集: O(2m) 为每一个子集扫描n个事务 测试s为T的子集: O(2mn) 随着项的个数呈指数级增长! 我们能否做的更好?,2020/7/8,史忠植 关联规则,19,Apriori 性质,定理(Apriori 性质): 若A是一个频繁项集,则A的每一个子集都是一个频繁项集. 证明:设n为事务数.假设A是l个事务的子集,若 A A , 则A 为

8、l (l l )个事务的子集.因此, l/n s(最小支持度), l/n s也成立.,2020/7/8,史忠植 关联规则,20,Apriori 算法,Apriori算法是一种经典的生成布尔型关联规则的频繁项集挖掘算法.算法名字是缘于算法使用了频繁项集的性质这一先验知识. 思想: Apriori 使用了一种称作level-wise搜索的迭代方法,其中k-项集被用作寻找(k+1)-项集. 首先,找出频繁1-项集,以L1表示.L1用来寻找L2,即频繁2-项集的集合.L2用来寻找L3,以此类推,直至没有新的频繁k-项集被发现.每个Lk都要求对数据库作一次完全扫描.,2020/7/8,史忠植 关联规则,

9、21,生成频繁项集,中心思想: 由频繁(k-1)-项集构建候选k-项集 方法 找到所有的频繁1-项集 扩展频繁(k-1)-项集得到候选k-项集 剪除不满足最小支持度的候选项集,2020/7/8,史忠植 关联规则,22,Apriori: 一种候选项集生成-测试方法,Apriori 剪枝原理: 若任一项集是不频繁的,则其超集不应该被生成/测试! 方法: 由频繁k-项集生成候选(k+1)-项集,并且 在DB中测试候选项集 性能研究显示了Apriori算法是有效的和可伸缩(scalablility)的.,2020/7/8,史忠植 关联规则,23,The Apriori 算法一个示例,Database

10、TDB,1st scan,C1,L1,L2,C2,C2,2nd scan,C3,L3,3rd scan,2020/7/8,史忠植 关联规则,24,Apriori 算法,Algorithm: Apriori 输入: Database, D, of transactions; minimum support threshold,min_sup. 输出: L, freuqent itemsets in D. 过程: Ck: Candidate itemset of size k Lk : frequent itemset of size k L1 = find_frequent_1_itemsets

11、(D); for (k = 2; Lk+1 !=; k+) do begin Ck = apriori_gen(Lk-1 ,min_sup); for each transaction t in database D do/scan D for counts Ct =subset(Ck ,t);/ get the subsets of t that are candidates For each candidate c Ct c.count+; Lk = candidates in Ck with min_support end return L=k Lk;,2020/7/8,史忠植 关联规则

12、,25,Apriori 算法,Procedure apriori_gen(Lk-1: frequent (k-1)-itemsets; min_sup:minimum support threshold ) for each itemset l1 Lk-1 for each itemset l2Lk-1 if(l11=l21) (l12=l22) (l1k-1=l2k-1) Then c=join(l1,l2)/join step: generate candidates if has_infrequent_subset(c, Lk-1 ) then delete c;/prune step:

13、 remove unfruitful candidate else add c to Ck return Ck,2020/7/8,史忠植 关联规则,26,Apriori 算法,Join is generate candidates set of itemsets Ck from 2 itemsets in Lk-1 Procedure join(p,q) insert into Ck select p.item1, p.item2,., p.itemk-1, q.itemk-1 from Lk-1 p, Lk-1 q where p.item1=q.item1, ., p.itemk-2=q.

14、itemk-2, p.itemk-1 = q.itemk-1,2020/7/8,史忠植 关联规则,27,Apriori 算法,Procedure has_infrequent_subset(c:candidate k-itemset;Lk-1: frequent (k-1)-itemsets;)/use prior knowledge for each (k-1)-subset s of c if s Lk-1 then return TRUE; return FALSE.,2020/7/8,史忠植 关联规则,28,Apriori 算法,如何生成候选项集? 步骤 1: 自连接 Lk 步骤 2:

15、 剪枝 如何计算候选项集的支持度? 候选项庥生成的示例 L3= abc, abd, acd, ace, bcd 自连接: L3*L3 由abc 和abd 连接得到abcd 由acd 和ace 连接得到acde 剪枝: 因为ade 不在L3中acde 被剪除 C4=abcd,2020/7/8,史忠植 关联规则,29,如何生成候选项集?,假定Lk-1中的项以一定顺序排列 步骤 1: 自连接 Lk-1 insert into Ck select p.item1, p.item2, , p.itemk-1, q.itemk-1 from Lk-1 p, Lk-1 q where p.item1=q.i

16、tem1, , p.itemk-2=q.itemk-2, p.itemk-1 q.itemk-1 步骤 2: 剪枝 forall itemsets c in Ck do forall (k-1)-subsets s of c do if (s is not in Lk-1) then delete c from Ck,2020/7/8,史忠植 关联规则,30,如何计算候选项集的支持度?,为何候选项集的支持度的计算是一个问题? 候选项集的总数可能是巨大的 一个事务可能包含多个候选项集 方法: 候选项集被存储在一个哈希树 哈希树的叶子结点包含一个项集和计数的列表 内部结点 包含一个哈希表 子集函数: 找出包含在一个事务中的所有候选项集,2020/7/8,史忠植 关联规则,31,频繁模式挖掘的挑战,挑战 多次扫描事务数据库 巨大数量的候选项集 繁重的计算候选项集的支持度工作 改进 Apriori: 大体的思路 减少事务数据库的扫描次数 缩减候选项集的数量 使候选