数据挖掘4关联规则

《数据挖掘4关联规则》由会员分享，可在线阅读，更多相关《数据挖掘4关联规则（41页珍藏版）》请在金锄头文库上搜索。

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

2、, subsequences, 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 data What products were often purchased together? Beer and diap

3、ers?! What are the subsequent purchases after buying a PC? What kinds of DNA are sensitive to this new drug? Can we automatically classify web documents? Applications Basket data analysis, cross-marketing, catalog design, sale campaign analysis, Web log (click stream) analysis, and DNA sequence anal

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

5、过量化的数字描述物品甲的出现对物品乙的出现有多大影响。,例如某超级市场的销售系统，记录了5个顾客的购物清单,购买摩托车的人很大可能同时购买头盔,有些数据不像售货数据那样很容易就能看出一个事务是哪些物品的集合，但稍微转换一下思考角度，仍然可以像售货数据一样处理。例如人寿保险，一份保单就是一个事务。保险公司在接受保险前，往往需要记录投保人详尽的信息，有时还要到医院做身体检查。保单上记录有投保人的年龄、性别、健康状况、工作单位、工作地址、工资水平等。这些投保人的个人信息就可以看作事务中的物品。通过分析这些数据，可以得到类似以下这样的关联规则：年龄在40岁以上，工作在A区的投保人当中，有45的人曾经向

6、保险公司索赔过。在这条规则中，“年龄在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：,假设有项集A=I1, I5， 则称事务T1，事务T2支持项集A。,规则表示,由事务与项集表，最

7、终得到的关联规则是如下形式的一种蕴涵式：,R牛奶，面包，黄油，啤酒，酱油，餐巾纸，拖把 A=面包，B黄油 ？ A=面包，B拖把 ？ A=餐巾纸，牛奶，B黄油 ？ ,How to evaluate this rule?,描述关联规则属性的四个参数,(1)可信度（condifence），设W中支持物品集A的事务中，有c的事务同时也支持物品集B，c称为关联规则的可信度。是对关联规则的准确度的衡量。 (2)支持度（support），设W中有s的事务同时支持物品集A和B，s称为关联规则的支持度。是对关联规则重要性（或适用范围）的衡量。支持度说明了这条规则在所有事务中有多大代表性，支持度越大，关联规则越重

8、要，应用越广泛。,(3)期望可信度（expected confidence）,设W中有e的事务支持物品集B，e称为关联规则的期望可信度。描述的是在没有任何条件影响时，物品集B在所有事务中出现的概率。或者说是在没有物品集A的作用下，物品集B本身的支持度。(4)作用度（lift），是可信度与期望可信度的比值。描述的是物品集A的出现对物品集B的出现有多大影响。通 过 可 信 度 对 期 望 可 信 度 的 比 值 反 映 了 在 加 入“ 物 品 集A 出 现” 的 这 个 条 件 后， 物 品 集B 的 出 现 概 率 发 生 了 多 大 的 变 化。作用度越大，说明物品集B受物品集A的影响越大。

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

10、黄油 支持度：0; 可信度：0; 期望可信度：3/5; 作用度：0 规则: A B (0%, 0% ),Chapter 4 Association Rule & Rough Set,4.1 关联规则概述4.2 经典的关联规则挖掘算法4.3 从事物数据库中挖掘多层关联规则,4.2 经典的关联规则挖掘算法,关联规则的挖掘就是在事务数据库D中找出具有用户给定的最小支持度min-sup和最小可信度min-conf的关联规则。,1. 关联规则的挖掘过程: (1) 找出存在于事务数据库中的所有频繁项集。项集X的支持度不小于用户给定的最小支持度，则称x为频繁项集（frequent item set）或大物品

11、集（large item set）。,第二步比较容易，目前大多数研究集中在第一个子问题上。,利用频繁集生成关联规则。对于每个频繁集A，若,2. 关联规则方法的分类,（1）一般处理的是离散化数据，根据离散化结果，可分为根据规则中涉及的数据维数（项数，属性数） 根据规则集所涉及的抽象层,3. 经典的关联规则挖掘算法 （单维、单层、布尔型的关联规则挖掘）,Aprior算法FP_增长树算法,3.1 Aprior算法： 寻找频繁集，用k-1项集（Lk-1）探索k项集（Lk），即频繁集的子集必须是频繁项集，是宽度优先算法。,先找出所有的1项集（含有一个项的项集），记为C1，找出所有的频繁1项集，记为L1。

12、 然后根据频繁1项集确定候选2项集的集合C2 ，从C2中找出所有的频繁2项集，记为L2。 然后再根据频繁2项集确定候选3项集的集合，记为C3，从C3中找出所有的频繁3项集，记为L3。 如此下去直到不再有候选项集。,C1：牛奶，面包，黄油，啤酒，酱油，餐巾纸，拖把,L1：面包，黄油,How to receive Lk from Lk1？,How to receive Lk from Lk1？,Example,Transactional database D,Scan D,C1,L1,Calculate support,Join L1*L 1,Min_sup2,Prune,C2,Scan D,C2

13、,Calculate support,L2,L2*L2,Prune,C3,Prune,C3,C3,Scan D,L3,C4,L3*L3,Prune,Apriori Algorithm Input：DB，min_sup Output：L, frequent itemsets in D and their supports Method：L1=find_frequent_1-itemsets(D);/遍历DB，产生频繁1项集Ck=apriori_gen(Lk-1,min_sup); /产生候选项集For each transaction tD /对所有事物进行操作 Ct=subset(Ck, t)

14、; /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; /剪枝 else add c to Ck; return Ck;,Procedure has_infrequent_subset(c: Lk-1) /use prior knowledgefor each (k-1)-sub

15、set 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）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

16、/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-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）降低需要计算支持度的项目集（常称为候选项集）的数量，使其与频繁项目集的数量接近。候选项目数量的降低可以节省为处理部分候选项目集所需的计算时间和存储空间。,