6_第六讲(关联规则分析)(必威体育精装版修正版）.ppt

3、根据规则集所涉及的抽象层 单层关联规则（关联规则表达时不涉及到概念分层） 多层关联规则（关联规则表达时涉及到概念分层，其内部隐含有概念分层的关系） 4、根据关联挖掘的各种扩充 挖掘最大的频繁模式（该模式的任何真超模式都是非频繁的，意味着这个模式是最大的频繁模式） 挖掘频繁闭项集（一个项集c是频繁闭项集，如果不存在其真超集c`，使得每个包含c的事务也包含c`，意味着c的任何一个真超集都不可能是频繁的，我们就说c是频繁闭项集） * 由事务数据库挖掘单维布尔关联规则 最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘，而且我们的举例尽量不涉及概念分层。 首先挖掘频繁项集，其前提条件是： 最小支持度 50%，且最小置信度 50% 对规则A ? C，其支持度 =50% 置信度分A推导C和由C推导A，以A推导C为例： * Apriori算法（计算大型数据库时挖掘关联规则的常用算法之一） Apriori算法利用频繁项集性质的先验知识（prior knowledge），通过逐层有哪些信誉好的足球投注网站的迭代方法，即将k-项集用于探察(k+1)-项集，来穷尽数据集中的所有频繁项集（通过先验知识挖掘未知知识）。 先找到频繁1-项集集合（即单个项出现的频率）L1,然后用L1找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k-项集，找每个Lk需要一次数据库扫描，过程用到下面性质。 Apriori性质：频繁项集的所有非空子集也必须是频繁的。（ 模式不可能比A更频繁的出现，即A与B的非空交集不可能比A大，只能被包含） Apriori算法是反单调的，即一个集合如果不能通过测试，则该集合的所有超集（注意超集与真超集概念是怎么样的？其定义与子集相对！）也不能通过相同的测试。 * Apriori算法步骤 Apriori算法由连接和剪枝两个步骤组成。 连接：为了找Lk，通过Lk-1与自己连接产生候选k-项集的集合，该候选k项集记为Ck。 Lk-1中的两个元素L1和L2可以执行连接操作 的条件是 Ck是Lk的超集，即它的成员可能不是频繁的，但是所有频繁的k-项集都在Ck中（为什么？）。因此可以通过扫描数据库，通过计算每个k-项集的支持度来得到Lk 。 为了减少计算量，可以使用Apriori性质，即如果一个k-项集的(k-1)-子集不在Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除。 * Apriori算法—示例（如何挖掘满足最小支持度的关联的频繁项集） Database TDB 1st scan C1 L1 L2 C2 C2 2rd scan C3 L3 3rd scan Tid Items 10 A, C, D 20 B, C, E 30 A, B, C, E 40 B, E Itemset sup {A} 2 {B} 3 {C} 3 {D} 1 {E} 3 Itemset sup {A} 2 {B} 3 {C} 3 {E} 3 Itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E} Itemset sup {A, B} 1 {A, C} 2 {A, E} 1 {B, C} 2 {B, E} 3 {C, E} 2 Itemset sup {A, C} 2 {B, C} 2 {B, E} 3 {C, E} 2 Itemset {B, C, E} Itemset sup {B, C, E} 2 注意：我们假设最小支持度是50%，则最小支持计数是2个，则L1时删除D，则任何包含D的超集其出现次数都不可能再超过1次，即Apriori性质所讲的内容。 剪枝结果 连接！ 最终，挖掘出2项集中4个 和3项集中1个频繁项集！ C3 Itemset 不在L2中 {A,B,C} {A,B} {B,C,E} 都在 {A,C,E} {A,E} 连接！ * Apriori算法—示例使用Apiori性质由L2产生C3 1 ．连接：至少有一个元素相同时，才能进行两两连接 C3=L2 L2= {{A,C},{B,C},{B,E}{C,E}} {{A,C},{B,C},{B,E}{C,E}} = {{A,B,C},{A,C,E},{B,C,E}}， 我们认为任何频繁的三项集都包含在此C3中！ 2．使用Apriori性质剪枝：频繁项集的所有子集必须是频繁的，对候选项C3，我们可以删除其子集为非频繁的选项： {A,B,C}的2项子集是{A,B},{A,C},{B,C}，其中{A,B}不是L2的元素，所以删除这个选项； {A,C,E}的2项子集是{A,C},{A,E},