数据挖掘4关联规则资料

1、数据挖掘发现知识的类型,概念描述（广义知识 ） 关联知识 分类知识 预测型知识 偏差型知识,从数据分析角度出发，数据挖掘可以分为两种类型 描述性数据挖掘: 以简洁概述的方式表达数据中的存在的一些有意义的性质 预测性数据挖掘: 分析数据，建立一个或一组模型，并试图预测新数据集的行为,Chapter 4 Association Rule 可信度：2/3; 期望可信度：3/5; 作用度：10/9 规则: A B (40%, 67% ) A=面包，B拖把 支持度：0; 可信度：0; 期望可信度：1/5; 作用度：0 规则: A B (0%, 0% ) A=餐巾纸，牛奶，B黄油 支持度：0; 可信度：0

2、; 期望可信度：3/5; 作用度：0 规则: A B (0%, 0% ),Chapter 4 Association Rule /遍历DB，产生频繁1项集 Ck=apriori_gen(Lk-1,min_sup); /产生候选项集 For each transaction tD /对所有事物进行操作 Ct=subset(Ck, t); /t中包含的候选 For each candidate cCt c.count+; /计算每个项集的支持度,Procedure apriori_gen(Lk-1, min_sup)/连接和剪枝 (1) (2) (3) (4) c=l1*l2; /链接步，生成候选

3、项集 (5) if has_infrequent_subset(c, Lk-1) then delete c; /剪枝 else add c to Ck; return Ck;,Procedure has_infrequent_subset(c: Lk-1) /use prior knowledge for each (k-1)-subset s of c return TRUE; Else return FALSE;,找到的所有频繁项集 I1，I2；I1，I3；I1，I5；I2，I3；I2，I4；I2，I5； I1，I2，I3；I1，I2，I5。 从频繁集生成强关联规则（满足min_sup和

4、min_conf）: 对于每个频繁项集l ，产生所有非空子集s 对于l的每个非空子集，如果 count（l）/count（s）min_conf, 则输出规则 s(l-s) 如：l=I1,I2,I5, 非空子集：I1, I2, I5, I1,I2, I1,I5, I2,I5 s=I1,I2, l-s=I5; count(l)/count(s)=2/4 s=I1,I5, l-s=I2; count(l)/count(s)=2/2 s=I2,I5, l-s=I1; count(l)/count(s)=2/2 s=I1, l-s=I2,I5; count(l)/count(s)=2/6 s=I2, l

5、-s=I1,I5; count(l)/count(s)=2/7 s=I5, l-s=I1,I2; count(l)/count(s)=2/2,然后得到如下的规则：,如果min_conf70， 则可得到并输出下列的结果（强关联规则）：,关联规则挖掘算法主要考虑的问题有以下两个： （1）减少I/O操作。关联规则挖掘的数据集有时可达GB甚至TB数量级，频繁的I/O操作必将影响关联规则的挖掘效率，减少I/O操作的方法主要是减少扫描数据集D的次数。 （2）降低需要计算支持度的项目集（常称为候选项集）的数量，使其与频繁项目集的数量接近。候选项目数量的降低可以节省为处理部分候选项目集所需的计算时间和存储空间

6、。,Aprior算法最直观，最易理解，但 需要产生大量的候选项集，工作量很大。 需要重复地扫描数据库，通过模式匹配检查一个很大的候选集合（长模式时尤其如此）。,3.2 FP_tree growth algorithm 不产生候选项集的频繁项集挖掘方法,能提供频繁项集的数据库压缩到频繁模式树（Frequent Pattern Tree）上，分成一组条件数据库，再由这些条件数据库生成频繁项集。 How does FP_tree growth algorithm to find frequent itemsets?,FP-tree growth Algorithm,Input：A transacti

7、on database D, min-sup Output: the complete set of frequent patterns Method: Step1.第一次扫描数据库，计数并导出L1的集合，最后使得L1中的每件事务中的项按count的降序排列，记为L,上例的事务数据库得到的L,Step2. 构造FP-tree.( 包括Item ID, Support count Node link),Step2.1 创建根节点，记为null Step2.2 第二次扫描数据库， 对每一个事务中的项按L中的次序重新排列处理 （如右表） 然后对每个事务创建一个分枝（一棵子树）： 1）分枝的节点数事务

8、中的项数 2）按顺序，最前面一项链接到根节点，后面一项被链接到前面一项，并计数 3）对于有共享前缀的，计数加1并在该前缀基础上创建一个新节点,4） 创建项类表，使得每个项通过一个节点链指向它在树中的出现。（如p240的figure6.8）,Construct FP-tree from a Transaction Database,min_support = 3,TID Items bought (ordered) frequent items 100 f, a, c, d, g, i, m, p f, c, a, m, p 200 a, b, c, f, l, m, o f, c, a, b,

9、 m 300 b, f, h, j, o, w f, b 400 b, c, k, s, p c, b, p 500 a, f, c, e, l, p, m, n f, c, a, m, p,Scan DB once, find frequent 1-itemset (single item pattern) Sort frequent items in frequency descending order, f-list Scan DB again, construct FP-tree,F-list=f-c-a-b-m-p,Step3. 挖掘FP-tree (从FP-tree中寻找频繁项集)

10、,从L的最后端项开始，依次对L中的项做如下操作： （1）寻找该项（记为I）的条件模式基(conditional pattern base)【FP-tree中与后缀模式（I）一起出现的前缀路径集合】，如 I5的条件模式基：（I2，I1：1），（I2，I1，I3：1） I4的条件模式基：（I2，I1：1），（I2：1） I3的条件模式基：（I2，I1：2），（I2：2），（I1：2） I2的条件模式基： I1的条件模式基：（I2：4）,（2）由条件模式基产生满足最小支持度的条件FP-tree(删去一些不满足支持度的项) 如， I5的条件FP-tree：（I2，I1：2） I4的条件FP-tree：

11、（I2：2） I3的条件FP-tree：(I2，I1：2)，(I2：2)，(I1：2) 也有的写为（I2：4，I1：2），（I1：2） I1的条件FP-tree：（I2：4）,（3）由条件FP-tree找频繁模式（frequent patterns）（由条件FP-tree产生的频繁模式被处理项）,如 I5的频繁模式：(I2，I5：2)，(I1，I5：2)，(I2，I1，I5：2) I4的频繁模式：（I2，I4：2） I3的频繁模式：(I2，I1，I3：2)，(I2，I3：4)，(I1，I3：4) I1的频繁模式：(I2，I1：4) Step4.由频繁集产生强关联规则,FP_tree 算法总结,Step1.扫描数据库，计数并导出L1的集合，最后使得L1中的每件事务中的项按count的降序排列，记为L Step2. 构造FP-tree.( 包括Item ID, Support count Node link) Step3. 挖掘FP-tree (从FP-tree中寻找频繁项集) Step4. 由频繁项集产生强关联规则,与经典的关联规则的挖掘相比，目前有如下的发展趋势,从单一概念层次关联规则的发现发展到多概念层次的关联规则的发现。（概念描述里的概念泛化和概念提升，如