关联分析(精品).ppt

《关联分析(精品).ppt》由会员分享，可在线阅读，更多相关《关联分析(精品).ppt（54页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、关 联内容概要基本概念基本概念其他其他Apriori算法算法关联规则分类关联规则分类FP-Growth算法算法第第3 3章章 关关 联联 3.1 基本概念3.2 原 理3.3 核心算法3.4 其 他 w自然界自然界中某种事物发生时其他事物也会发生的这样一种联系称之为关联。w反映事件之间依赖或关联的知识称为关联型知识（又称依赖关系）。(?)w定义3.1：关联关联是两个或多个变变量量取值之间存在的一类重要的可被发现的某种规律性。w关联可分为简单关联、时序关联、因果关联。基基 本本 概概 念念 n关联分析目的是寻找给定数据记录集中数据项之间隐藏的关联关系，描述数据之间的密切度。n关联分析的结果常有两

2、种：关联规则关联规则关联规则关联规则和序列模式序列模式。n关联规则关联规则用于寻找在同一个事件中出现的不同项的相关性；n序列模式序列模式与此类似，但它寻找的是事件之间时间时间上的相关性。关关 联联 分分 析析 n关联规则发现的主要对象是交易型数据库，一个交易一般由交易处理时间，一组顾客购买的物品，有时也有顾客标识号(如信用卡号)组成。n定义3.2：关联规则关联规则是描述在一个交易中物品之间同时出现的规律的知识模式，更确切的说，关联规则是通过量化的数字描述物品X的出现对物品Y的出现有多大的影响。关关 联联 规规 则则 以零售业为例，体育用品商场通过对销售数据进行关联分析通常可以发现这些数据中常常

3、隐含形式如下的规律“购买篮球的顾客中有70%的人同时购买篮球运动服，所有交易中有40%的人同时购买篮球和篮球运动服”等等。这些规律即关联规则关联规则。关关 联联 规规 则则n定定义义3.33.3：关联规则挖掘的交易数据集记为D（一般为交易数据库），DT1，T2，Tk，,Tn，Tk（k1,2,，n）称为交易，对应每一个交易有唯一的标识，记作TID。n元素im（m1,2,，p）称为项。设I=i1，i2，im是D中全体项组成的集合，且TkI。交易号交易号（TID）项集合项集合（Itemsets）T100 I1，I2，I5 T200 I2，I4 T300 I2，I3 T400 I1，I2，I4 T50

4、0 I1，I3 设X是一个I中项的集合，如果XTk，那么称交易Tk包含项集X。若若X,Y为项集，为项集，X I,Y I，并且并且X Y=，则形如则形如X=Y的表达式称的表达式称为为关联规则关联规则。关联规则形式化定义关联规则形式化定义置信度置信度支持度支持度 关联规则度量关联规则度量规则XY在交易数据集D中的置信度置信度是对关联规则准确度的衡量。度量关联规则的强度。即在所有出现了X的活动中出现Y的频率，即规则XY的必然性有多大。记为confidence(Xconfidence(XY)Y)。计算方法：包含X和Y的交易数与包含X的交易数之比：confidence(XY)=P(YX)=|T:XYT，

5、TD|/|T:XT，TD|100%规则XY在交易数据集D中的支持度支持度是对关联规则重要性的衡量，反映关联是否是普遍存在的规律，说明这条规则在所有交易中有多大的代表性。即在所有交易中X与Y同时出现的频率记为：support(Xsupport(XY)Y)。计算方法：交易数据集中同时包含X和Y的交易数与所有交易数之比：support(XY)=P(XY)=|T:XYT，TD|/|D|100%（其中|D|是交易数据集D中的所有交易数）最小置信度阈值最小置信度阈值最小支持度阈值最小支持度阈值同时满足最小置信度阈值和最小支持度阈值的关联规则为强关联规则强关联规则，是有意义有价值。关联规则度量关联规则度量

6、在给定一个交易数据集在给定一个交易数据集D D，挖掘关挖掘关联规则问题就是产生支持度和置信联规则问题就是产生支持度和置信度分别大于用户给定的度分别大于用户给定的最小支持度最小支持度阈值阈值和和最小置信度阈值最小置信度阈值的关联规则。的关联规则。关联规则度量关联规则度量经常使用的“支持度-可信度”的框架。这样的结构有时会产生一些错误的结果。例：假设体育类用品零售商调查了10000名顾客在购买什么商品，得到的结果是6000名顾客购买篮球，7500名顾客购买足球，4000名顾客购买篮球、足球。设最小支持度为30%，最小置信度为60%，可得到如下的关联规则：篮球足球（支持度40%，置信度为66%）这条

7、规则其实是错误的，因为购买足球的比例是75%，甚至大于66%。关联规则度量关联规则度量描述了对于关联规则（X=Y）在没有任何条件影响时，Y在所有交易中出现的频率有多大。即没有X的作用下，Y本身的支持度。期望期望可信度可信度改善度改善度描述X的出现对Y的出现影响多大，是置信度与期望可信度的比值。P(Y|X)/P(Y)关联规则度量关联规则度量兴趣度？兴趣度？(置信度支持度)/Max置信度，支持度一条规则的兴趣度大于0，实际利用价值越大；小于0则实际利用价值越小。名称描述公式置信度X出现的前提下，Y出现的频率P(Y|X)支持度X、Y同时出现的频率 P(XY)期望可信度 Y出现的频率 P(Y)改善度

8、置信度对期望可信度的比值 P(Y|X)/P(Y)关联规则度量关联规则度量挖掘交易数据库挖掘交易数据库D D中所有关联规则中所有关联规则的问题可以被划分为两个子问题：的问题可以被划分为两个子问题：找出频繁项集找出频繁项集AprioriApriori算法算法 n Apriori性质性质n Apriori算法基本思想算法基本思想交易号交易号项集合项集合T100 I1，I2，I5 T200 I2，I4 T300 I2，I3 T400 I1，I2，I4 T500 I1，I3 T600 I2，I3 T700 I1，I3 T800 I1，I2，I3，I5 T900 I1，I2，I3 表1交易数据库D例：例：

9、找出频繁项集找出频繁项集AprioriApriori算法算法项集支持度计数I16I27I36I42I52项集支持度计数I16I27I36I42I52C1L1扫描D，对每个候选计数比较候选支持度计数与最小支持度计数找出频繁1项集的集合L1找出频繁项集找出频繁项集AprioriApriori算法算法例：最小支持度阈值为2项集支持度计数I16I27I36I42I52项集I1，I2I1，I3I1，I4I1，I5I2，I3I2，I4I2，I5I3，I4I3，I5I4，I5L1C2由L1产生候选C2Lk-1用于产生候选Ck找出频繁项集找出频繁项集AprioriApriori算法算法连接连接&剪枝剪枝项集支

10、持度计数I1，I24I1，I34I1，I41I1，I52I2，I34I2，I42I2，I52I3，I40I3，I51I4，I50项集支持度计数I1，I24I1，I34I1，I52I2，I34I2，I42I2，I52C2L2比较候选支持度计数与最小支持度计数扫描D，对每个候选计数项集支持度计数I1，I24I1，I34I1，I52I2，I34I2，I42I2，I52L2项集I1，I2，I3I1，I2，I5由L2产生候选C3C3连接连接&剪枝剪枝连接：C3L2 L2I1,I2,I1,I3,I1,I5,I2,I3,I2,I4,I2,I5 I1,I2,I1,I3,I1,I5,I2,I3,I2,I4,I2

11、,I5=I1,I2,I3,I1,I2,I5,I1,I3,I5,I2,I3,I4,I2,I3,I4,I2,I3,I5,I2,I4,I5剪枝：I1,I2,I3的2-项子集是I1,I2,I1,I3和I2,I3。I1,I2,I3的所有2-项子集都是L2的元素。因此，保留I1,I2,I3在C3中。I2,I3,I5的2-项子集是I2,I3,I2,I5和I3,I5。I3,I5不是L2的元素，因而不是频繁的。因此，由C3中删除I2,I3,I5。剪枝后C3I1,I2,I3,I1,I2,I5。项集支持度计数I1，I2，I32I1，I2，I52C3扫描D，对每个候选计数比较候选支持度计数与最小支持度计数项集支持度计

12、数I1，I2，I32I1，I2，I52L3对对每个交易，使用每个交易，使用subsetsubset函数找出交易函数找出交易中是候选的所有子集，并对每个这样的中是候选的所有子集，并对每个这样的候选累加计数，所有满足最小支持度的候选累加计数，所有满足最小支持度的候选形成频繁项集候选形成频繁项集L L。输入：交易数据库D；最小支持度阈值min_sup。输出：D中的频繁项集L。方法：(1)找频繁项集1-项集;(2)apriori_gen(Lk-1,min_sup)函数做两个动作：连连接接和和剪剪枝枝。用于在第k-1次遍历中生成的Lk-1生成Ck(3)由Ck生成Lk AprioriApriori算法详述

13、算法详述 子集函数子集函数SubsetSubset？子集函数Subset用于确定在一个给定的交易t中包含了哪些Ck中的项。候选集Ck被存放在一棵hash树中，hash树中的结点分为两类：一类包含一个项集列表(叶结点)，另一类包含一张hash表(内部结点)。在内部结点上，hash表中的每一个桶都指向另一个结点。假定hash树的根结点的深度等于1，则一个深度为d的内部结点指向深度为d1的结点。项集都存放在叶子结点，当需要添加一个项集c的时候，就从根结点出发直到叶子结点。在一个深度为d的内部结点，对该项集的第d项应用hash函数来确定下一步遍历的分支。所有的结点最初都被创建为叶子结点。当一个叶子结点

14、的项集数目超出某一个阈值时，该结点将会转化为一个内部结点。从根结点开始，子集函数按照如下的方式找出包含在交易t中的所有的候选集。如果在叶子结点，找出该叶子结点中所有包含在交易t中的项集，并且为它们添加一个指向结果集的索引；如果通过散列第i项到达某个内部结点，则散列交易t中第i项后的每一项，并且将这个过程递归地应用于相应的桶。对于根结点，则散列交易t中的每一项。子集函数能够返回所需要的候选集的索引，对于任何交易t中包含的项集c，c的第一个项一定出现在t中。在根结点，通过散列交易t中的每一项，我们能够确定只忽略那些不是从t中的某一项开始的项集。同样的结论也适用于hash树中位于其他层次的结点。由于

15、在每一个项集中的项都经过排序，如果我们通过散列项i到达当前的结点，则以后只需要考虑交易t中出现在项i后的项。AprioriApriori算法详述（续）算法详述（续）1.1.基于划分的方法基于划分的方法 2.2.基于基于散列散列的方法的方法 3.3.基于采基于采样样的方法的方法 4.4.交易压缩方法交易压缩方法 （不包含任何k项集的交易 不可能包含k+1项集）AprioriApriori算法优化算法优化D中交易将D划分成n部分找出局部每一部分频繁项集（1次扫描）结合局部频繁项集形成候选项集第1遍在候选项集中找出全局频繁项集（1次扫描）D中频繁项集第2遍基于划分的方法桶地址0123456桶记数22

16、42244桶内容I1,I4I3,I5I1,I5I1,I5I2,I3I2,I3I2,I3I2,I3I2,I4I2,I4I2,I5I2,I5I1,I2I1,I2 I1,I2 I1,I2I1,I3I1,I3I1,I3I1,I3基于散列技术压缩候选k项集Ck使用散列函数h(x,y)=(order of x)*10+(order of y)mod 7创建散列表候选2项集的散列表步骤：a.对于每个频繁项集l，找出l的所有非空子集；b.对于l的每个非空子集a，如果 support_count(l)/support_count(a)min_conf，则输出规则“a（la）”。频繁项集产生强关联规则频繁项集产生

17、强关联规则例：假定数据包含频繁集l I1,I2,I5，L的非空子集有I1,I2,I1,I5,I2,I5,I1,I2,和I5。可以由l产生的关联规则：I1I2I5，confidence 2/4 50%；I1I5I2，confidence 2/2 100%；I2I5I1，confidence 2/2 100%；I1I2I5，confidence 2/6 33%；I2I1I5，confidence 2/7 29%；I5I1I2,confidence 2/2 100%；若最小置信度阈值为70%，则只有I1I5I2，I2I5I1，I5I1I2可输出，是强关联规则不需要生成大量候选项集的频繁项集挖掘。算法

18、采用分而治之的策略。频繁模式增长（频繁模式增长（FP-GrowthFP-Growth）算法算法例：最小支持度阈值为3交易编号交易编号所有购物项所有购物项（排序后的）频繁项排序后的）频繁项100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,l,m,of,c,a,b,m300b,f,h,j,of,b400b,c,k,s,pc,b,p500a,f,c,e,l,p,m,nf,c,a,m,pFP-GrowthFP-Growth算法例算法例nullb:1f:3c:1b:1p:1f:1c:1m:1p:1a:1a:2b:1m:1f:2c:2a:3f:4c:3m:2p:21.f,c,a,

19、m,p2.f,c,a,b,m3.f,b4.c,b,p5.f,c,a,m,pFP-GrowthFP-Growth算法例算法例生成的FP树FP-GrowthFP-Growth算法例算法例节点链性质对任意频繁项ai，顺着ai的节点链，从ai的头开始，可以找到包含ai的所有频繁模式。项项条件模式库条件模式库条件条件FP树树p(f:2,c:2,a:2,m:2),(c:1,b:1)(c:3)|pm(f:4,c:3,a:3,m:2),(f:4,c:3,a:3,b:1,m:1)(f:3,c:3,a:3)|mb(f:4,c:3,a:3,b:1),(f:4,b:1),(c:1,b:1)a(f:3,c:3)(f:3

20、,c:3)|ac(f:3)(f:3)|cf包含m的所有频繁模式的集合有：(m:3),(am:3),(cm:3),(fm:3),(cam:3),(fam:3),(fcam:3),(fcm:3)。这表明对一个单独路径的FP树进行挖掘时，可以通过输出该路径上所有项的组合来实现。FP-GrowthFP-Growth算法例算法例前缀路径性质为计算路径p上的一个节点ai的频繁模式，只需要计算p中ai的前缀子树，并且前缀子树中的每个节点的频繁数和节点ai相同。FP-GrowthFP-Growth算法详述算法详述引理：片段增长假设是DB中的一个项集，B是的一个条件模式库，是B中的一个项集，那么，在DB中的支持

21、度和在B中的支持度是相同的。推论：模式增长假设是DB中的一个频繁项集，B是的条件模式库，是B中的一个项集。当且仅当在B中是频繁时，在DB中才是频繁的。FP-GrowthFP-Growth算法详述算法详述引理单单路路径径FP树树的的模模式式生生成成假假设设一一个个FP树树T，只只有有一一条条路路径径P，通通过过列列举举P的的子子路路径径的的所所有有组组合合，可可以以得得到到T的的频频繁繁模模式式全全集集，它它们们的的支支持持度度等等价价于于子子路路径径中中的的所所有有项项的的最最小小支支持持度。度。FP-GrowthFP-Growth算法详述算法详述算法2：在FP树中挖掘频繁模式输入：用DB根据

22、算法1构造的FP树和最小支持度阈值；输出：所有的频繁模式的集合；方法：调用FP-Growth(FP-Tree,null)；ProcedureFP-Growth(Tree,)(1)if(Tree只包含单路径P)then(2)对路径P中节点的每个组合（记为）(3)生成模式，支持数中所有节点的最小支持度(4)else对Tree头上的每个ai，do(5)生成模式=ai，支持度ai.support；(6)构造的条件模式库和的条件FP树Tree；(7)ifTree(8)thencallFP-Growth(Tree,)FP-GrowthFP-Growth算法详述算法详述w1.简单关联规则 单维、单层、布尔型

23、关联规则w2.量化关联规则w3.多维关联规则w4.跨层关联规则关联规则分类关联规则分类篮球=篮球服，只涉及到用户购买的物品性别=“女”=平均收入=2300，涉及的收入是数值类型性别=“男”=购买“篮球”，涉及两个维 Adidas篮球=Nike篮球服同层关联规则层间关联规则篮球=Nike篮球服挖掘量化关联规则挖掘量化关联规则数值字段根据数据的分布分成布尔字段数值字段根据数据的分布分成布尔字段每个布尔字段都表示一个数值字段的区间，落在其中则为1，反之为0。这种分法是动态的。得出的规则称布尔量化关联规则布尔量化关联规则。使用预定义的概念分层对量化属性离散化使用预定义的概念分层对量化属性离散化如年龄的

24、概念分层可以分为区间，“20.24”，“25.29”，“35.39”等替换原来的数值。得出的规则也叫做静态量化关联规则静态量化关联规则。数值字段被分成一些能体现含义的区间，紧数值字段被分成一些能体现含义的区间，紧扣区间数据的语义。扣区间数据的语义。考虑数据点之间的距离因素考虑数据点之间的距离因素。得出的规则称基于距离的关联规则。直接用数值字段中的原始数据进行分析直接用数值字段中的原始数据进行分析根据数据的分布对数值字段的值进行分析，数值属性动态离散化，以满足某种挖掘标准，如最大化所挖掘的规则的置信度。该策略将数值属性的值处理成量，而不是预定义的区间或分类。得出的规则称量化关联规则量化关联规则。

25、挖掘量化关联规则挖掘量化关联规则挖掘量化关联规则挖掘量化关联规则体育类商品体育类商品球类球类运动服类运动服类辅助用品类辅助用品类篮球篮球足球足球AdidasAdidasNikeNike篮球服篮球服足球服足球服体育用品的概念分层Adidas篮球=Nike篮球服篮球=Nike篮球服挖掘跨层关联规则挖掘跨层关联规则n n同同层层关关联联规规则则即处于同概念层的关联规则，其挖掘是在特定概念层上逐层展开的，需对项的每个层次进行处理，一般采用自顶向下 策略。对每一层，可以使用类似于单层关联规则挖掘的发现频繁项集的任何算法；算法有ML-T2、ML-SH、ML-TMAX、ML-T2+等n n层层间间关关联联规

26、规则则跨越层边界，规则中的项不要求属于同一概念层。算法有：ML-CH等。挖掘跨层关联规则挖掘跨层关联规则层2最小支持度5%体育类商品（支持度10）篮球（支持度6）足球（支持度4）层1最小支持度5%频繁频繁频繁频繁非频非频繁繁同层关联规则同层关联规则 统一的最小支持度统一的最小支持度体育类商品（支持度10）篮球（支持度6）足球（支持度4）频繁频繁频繁频繁频繁频繁层2最小支持度3%层1最小支持度5%递减的最小支持度递减的最小支持度逐层独立逐层独立体育类商品（支持度10）篮球足球非频非频繁繁不考不考察察不考不考察察层2最小支持度3%层1最小支持度12%递减的最小支持度递减的最小支持度层交叉单项过滤层

27、交叉单项过滤球类和运动服（支持度7）足球和篮球运动服（支持度1）频繁频繁被考察层2最小支持度2%层1最小支持度5%一个第i层的k项集被考察，当且仅当它在第（i-1）层的父节点k项集是频繁的。足球和足球运动服（支持度2）篮球和篮球运动服（支持度3）篮球和足球运动服（支持度1）递减的最小支持度递减的最小支持度层交叉层交叉k-k-项过滤项过滤被考察删除删除n单维关联规则（维内关联规则）n维间关联规则（多维关联规则）n混合维关联规则（某些谓词重复出现）挖掘多维关联规则挖掘多维关联规则单维关联规则搜索频繁项集搜索频繁谓词集对Apriori算法稍加修改找出所有的频繁谓词而不是频繁项集。策略：频繁谓词的每个子集也必须是频繁的（类似Apriori性质）数据立方体适合挖掘多维关联规则n-维立方体的单元用于存放对应n-谓词集的计数或支持度。