数据挖掘4关联规则课件

1、数据挖掘发现知识的类型概念描述（广义知识 ）关联知识分类知识预测型知识偏差型知识从数据分析角度出发，数据挖掘可以分为两种类型描述性数据挖掘: 以简洁概述的方式表达数据中的存在的一些有意义的性质预测性数据挖掘: 分析数据，建立一个或一组模型，并试图预测新数据集的行为Chapter 4 Association Rule & Rough Set4.1 关联规则概述4.2 经典的关联规则挖掘算法4.3 从事物数据库中挖掘多层关联规则 What Is Frequent Pattern Analysis?Frequent pattern: a pattern (a set of items, subseq

2、uences, substructures, etc.) that occurs frequently in a data set First proposed by Agrawal, Imielinski, and Swami AIS93 in the context of frequent itemsets and association rule miningMotivation: Finding inherent regularities in dataWhat products were often purchased together? Beer and diapers?!What

3、 are the subsequent purchases after buying a PC?What kinds of DNA are sensitive to this new drug?Can we automatically classify web documents?ApplicationsBasket data analysis, cross-marketing, catalog design, sale campaign analysis, Web log (click stream) analysis, and DNA sequence analysis.关联规则模式是属于

4、描述型模式，发现关联规则的算法属于无监督学习的方法。关联规则的意义和度量 关联规则挖掘的主要对象是事务数据库（transaction DB），针对的应用大多是售货数据，一般情况下，一个事务由如下几个部分组成：事务处理时间，一组顾客购买的物品，物品的数量及金额，顾客的标识号。 在事务数据库中，考察一些涉及到许多物品（项）的事务：事务1中出现了物品甲，事务2中出现了物品乙，事务3中同时出现了物品甲和乙，then，物品甲和物品乙在事务中的出现相互之间是否有一定的规律？ 在数据库知识发现中，关联规则就是描述这种在一个事务中物品之间同时出现的规律的知识模式。更确切的说，关联规则通过量化的数字描述物品甲的

5、出现对物品乙的出现有多大影响。例如某超级市场的销售系统，记录了5个顾客的购物清单 流水号所购物品清单1球鞋、手套、网球拍2摩托车、手套、头盔3球鞋、摩托车 、手套、头盔4头盔5摩托车、头盔购买摩托车的人很大可能同时购买头盔 有些数据不像售货数据那样很容易就能看出一个事务是哪些物品的集合，但稍微转换一下思考角度，仍然可以像售货数据一样处理。 例如人寿保险，一份保单就是一个事务。保险公司在接受保险前，往往需要记录投保人详尽的信息，有时还要到医院做身体检查。保单上记录有投保人的年龄、性别、健康状况、工作单位、工作地址、工资水平等。这些投保人的个人信息就可以看作事务中的物品。通过分析这些数据，可以得到

6、类似以下这样的关联规则： 年龄在40岁以上，工作在A区的投保人当中，有45的人曾经向保险公司索赔过。在这条规则中，“年龄在40岁以上”是物品甲，“工作在A区”是物品乙，“向保险公司索赔过”则是物品丙。 可以看出来，A区可能污染比较严重，环境比较差，导致工作在该区的人健康状况不好，索赔率也相对比较高。 事务与项集设：R=I1，I2，In是一组项集（项目集，属性集，item set）W是一组与R相关的事务集。W中的每个事务T是一组项（属性）。假设有一个项集A，一个事务T，如果 AT，则称事务T支持项集A。例如： R=I1, I2, I3, I4, I5, I6, I7 事务集W：事务T1I1, I

7、2, I5事务T2I1, I5, I7事务T3I2, I4, I6, I7事务T4I3, I7事务T5I5, I6 假设有项集A=I1, I5，则称事务T1，事务T2支持项集A。规则表示由事务与项集表，最终得到的关联规则是如下形式的一种蕴涵式：TIDItem SetT1牛奶，面包，黄油T2牛奶，面包，啤酒T3面包，黄油，啤酒T4黄油，酱油，餐巾纸T5餐巾纸，拖把R牛奶，面包，黄油，啤酒，酱油，餐巾纸，拖把A=面包，B黄油 ？A=面包，B拖把 ？A=餐巾纸，牛奶，B黄油 ？ How to evaluate this rule?描述关联规则属性的四个参数(1)可信度（condifence），设W中

8、支持物品集A的事务中，有c的事务同时也支持物品集B，c称为关联规则的可信度。是对关联规则的准确度的衡量。 (2)支持度（support），设W中有s的事务同时支持物品集A和B，s称为关联规则的支持度。是对关联规则重要性（或适用范围）的衡量。支持度说明了这条规则在所有事务中有多大代表性，支持度越大，关联规则越重要，应用越广泛。 (3)期望可信度（expected confidence）,设W中有e的事务支持物品集B，e称为关联规则的期望可信度。描述的是在没有任何条件影响时，物品集B在所有事务中出现的概率。或者说是在没有物品集A的作用下，物品集B本身的支持度。(4)作用度（lift），是可信度与期

9、望可信度的比值。描述的是物品集A的出现对物品集B的出现有多大影响。通 过 可 信 度 对 期 望 可 信 度 的 比 值 反 映 了 在 加 入“ 物 品 集A 出 现” 的 这 个 条 件 后， 物 品 集B 的 出 现 概 率 发 生 了 多 大 的 变 化。作用度越大，说明物品集B受物品集A的影响越大。 四个参数的计算公式 可信度（condifence） 在物品集A出现的前提下，B出现的概率 P(B|A)支持度（support） 物品集A、B同时出现的概率 P(BA)期望可信度（expected confidence） 物品集B出现的概率 P(B)作用度（lift） 可信度对期望可信度的

10、比值 P(B|A)/P(A)一般情况下，有用的关联规则的作用度都应该大于1，只有关联规则的可信度大于期望可信度，才说明A的出现对B的出现有促进作用，也说明了它们之间有某种程度的相关性。如果作用度不大于1，则此关联规则就没意义了。 BackTIDItem SetT1牛奶，面包，黄油T2牛奶，面包，啤酒T3面包，黄油，啤酒T4黄油，酱油，餐巾纸T5餐巾纸，拖把R牛奶，面包，黄油，啤酒，酱油，餐巾纸，拖把 How to evaluate this rule?A=面包，B黄油 支持度：2/5; 可信度：2/3; 期望可信度：3/5; 作用度：10/9规则: A B (40%, 67% )A=面包，B拖

11、把 支持度：0; 可信度：0; 期望可信度：1/5; 作用度：0规则: A B (0%, 0% )A=餐巾纸，牛奶，B黄油 支持度：0; 可信度：0; 期望可信度：3/5; 作用度：0规则: A B (0%, 0% )Customerbuys diaperCustomerbuys bothCustomerbuys beerChapter 4 Association Rule & Rough Set4.1 关联规则概述4.2 经典的关联规则挖掘算法4.3 从事物数据库中挖掘多层关联规则 4.2 经典的关联规则挖掘算法关联规则的挖掘就是在事务数据库D中找出具有用户给定的最小支持度min-sup和最

12、小可信度min-conf的关联规则。 1. 关联规则的挖掘过程:(1) 找出存在于事务数据库中的所有频繁项集。 项集X的支持度不小于用户给定的最小支持度，则称x为频繁项集（frequent item set）或大物品集（large item set）。第二步比较容易，目前大多数研究集中在第一个子问题上。 利用频繁集生成关联规则。 对于每个频繁集A，若 2. 关联规则方法的分类（1）一般处理的是离散化数据，根据离散化结果，可分为根据规则中涉及的数据维数（项数，属性数） 根据规则集所涉及的抽象层 3. 经典的关联规则挖掘算法 （单维、单层、布尔型的关联规则挖掘） Aprior算法FP_增长树算法3

13、.1 Aprior算法：寻找频繁集，用k-1项集（Lk-1）探索k项集（Lk），即频繁集的子集必须是频繁项集，是宽度优先算法。先找出所有的1项集（含有一个项的项集），记为C1，找出所有的频繁1项集，记为L1。然后根据频繁1项集确定候选2项集的集合C2 ，从C2中找出所有的频繁2项集，记为L2。然后再根据频繁2项集确定候选3项集的集合，记为C3，从C3中找出所有的频繁3项集，记为L3。如此下去直到不再有候选项集。 TIDItem SetT1牛奶，面包，黄油T2牛奶，面包，啤酒T3面包，黄油，啤酒T4黄油，酱油，餐巾纸T5餐巾纸，拖把C1：牛奶，面包，黄油，啤酒，酱油，餐巾纸，拖把L1：面包，黄油

14、How to receive Lk from Lk1？How to receive Lk from Lk1？ExampleTIDItemsT100I1, I2, I5T200I2, I4T300I2, I3T400I1, I2, I4T500I1, I3T600I2, I3T700I1, I3T800I1, I2, I3, I5T900I1, I2, I3Transactional database DItem setSupportI16I27I36I42I52Scan DC1Item setSupport I16I27I36I42I52L1Calculate supportJoinL1*L

15、1Min_sup2PruneItem setI1, I2I1, I3I1, I4I1, I5I2, I3I2, I4I2, I5I3, I4I3, I5I4, I5Item setSupport CountI1, I24I1, I34I1, I41I1, I52I2, I34I2, I42I2, I52I3, I40I3, I51I4, I50C2Scan D C2Item setSupport CountI1, I24I1, I34I1, I52I2, I34I2, I42I2, I52 Calculate supportL2L2*L2PruneItem setI1, I2, I3I1, I

16、2, I5I1, I3, I5I2, I3, I4I2, I3, I5I2, I4, I5Item setI1，I2，I3I1，I2，I5Item setSupportI1，I2，I32I1，I2，I52C3PruneC3Item setSupportI1，I2，I32I1，I2，I52C3Scan DL3ItemsetI1，I2，I3，I5C4L3*L3PruneApriori Algorithm Input：DB，min_supOutput：L, frequent itemsets in D and their supportsMethod： L1=find_frequent_1-item

17、sets(D);/遍历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; /链接步，生成候选项集 (5) if has_infrequent_subset(c, Lk-1) then delete c; /剪枝

18、 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和min_conf）:对于每个频繁项集l ，产生所有非空子集s对于l的每个非空子集，如果 count（l）/count（s

19、）min_conf, 则输出规则 s(l-s) 如：l=I1,I2,I5, 非空子集：I1, I2, I5, I1,I2, I1,I5, I2,I5s=I1,I2, l-s=I5; count(l)/count(s)=2/4s=I1,I5, l-s=I2; count(l)/count(s)=2/2s=I2,I5, l-s=I1; count(l)/count(s)=2/2s=I1, l-s=I2,I5; count(l)/count(s)=2/6s=I2, l-s=I1,I5; count(l)/count(s)=2/7s=I5, l-s=I1,I2; count(l)/count(s)=2

20、/2然后得到如下的规则： 如果min_conf70，则可得到并输出下列的结果（强关联规则）：关联规则挖掘算法主要考虑的问题有以下两个：（1）减少I/O操作。关联规则挖掘的数据集有时可达GB甚至TB数量级，频繁的I/O操作必将影响关联规则的挖掘效率，减少I/O操作的方法主要是减少扫描数据集D的次数。（2）降低需要计算支持度的项目集（常称为候选项集）的数量，使其与频繁项目集的数量接近。候选项目数量的降低可以节省为处理部分候选项目集所需的计算时间和存储空间。 Aprior算法最直观，最易理解，但 需要产生大量的候选项集，工作量很大。 需要重复地扫描数据库，通过模式匹配检查一个很大的候选集合（长模式时

21、尤其如此）。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 transaction database D, min-supOutput: the complete set of frequent patternsMethod:Ste

22、p1.第一次扫描数据库，计数并导出L1的集合，最后使得L1中的每件事务中的项按count的降序排列，记为LItem setSupport I27I16I36I42I52上例的事务数据库得到的LStep2. 构造FP-tree.( 包括Item ID, Support count Node link)Step2.1 创建根节点，记为nullStep2.2 第二次扫描数据库， 对每一个事务中的项按L中的次序重新排列处理 （如右表） 然后对每个事务创建一个分枝（一棵子树）：1）分枝的节点数事务中的项数2）按顺序，最前面一项链接到根节点，后面一项被链接到前面一项，并计数3）对于有共享前缀的，计数加1并

23、在该前缀基础上创建一个新节点TIDItemsT100I2, I1, I5T200I2, I4T300I2, I3T400I2, I1, I4T500I1, I3T600I2, I3T700I1, I3T800I2, I1, I3, I5T900I2, I1, I3 4） 创建项类表，使得每个项通过一个节点链指向它在树中的出现。（如p240的figure6.8） Construct FP-tree from a Transaction Databasef:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequency head f4c4a3b3

24、m3p3min_support = 3TIDItems bought (ordered) frequent items100f, a, c, d, g, i, m, pf, c, a, m, p200a, b, c, f, l, m, of, c, a, b, m300 b, f, h, j, o, wf, b400 b, c, k, s, pc, b, p500 a, f, c, e, l, p, m, nf, c, a, m, pScan DB once, find frequent 1-itemset (single item pattern)Sort frequent items in

25、 frequency descending order, f-listScan DB again, construct FP-treeF-list=f-c-a-b-m-pStep3. 挖掘FP-tree (从FP-tree中寻找频繁项集)从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：（I2：2） I3的条件FP-tree：(I2，I1：2)，(I2：2)，(I1：2) 也有的写为（I2：4，I1：2），（I1：2） I1的条件FP-tree：（I2：4）