数据挖掘教程：关联规则

关联

报告人：熊赟

内容概要

基本概念

其他

Apriori算法

关联规则分类FP-Growth算法第3章关联

3.1基本概念3.2原理3.3核心算法3.4其他

自然界中某种事物发生时其他事物也会发生的这样一种联系称之为关联。反映事件之间依赖或关联的知识称为关联型知识（又称依赖关系）。(?)定义3.1：关联是两个或多个变量取值之间存在的一类重要的可被发现的某种规律性。关联可分为简单关联、时序关联、因果关联。

基本概念

关联分析目的是寻找给定数据记录集中数据项之间隐藏的关联关系，描述数据之间的密切度。关联分析的结果常有两种：

关联规则和序列模式。关联规则用于寻找在同一个事件中出现的不同项的相关性；序列模式与此类似，但它寻找的是事件之间时间上的相关性。

关联分析

关联规则发现的主要对象是交易型数据库，一个交易一般由交易处理时间，一组顾客购买的物品，有时也有顾客标识号(如信用卡号)组成。定义3.2：关联规则是描述在一个交易中物品之间同时出现的规律的知识模式，更确切的说，关联规则是通过量化的数字描述物品X的出现对物品Y的出现有多大的影响。

关联规则

以零售业为例，体育用品商场通过对销售数据进行关联分析通常可以发现这些数据中常常隐含形式如下的规律——“购买篮球的顾客中有70%的人同时购买篮球运动服，所有交易中有40%的人同时购买篮球和篮球运动服”等等。这些规律即关联规则。

关联规则定义3.3：关联规则挖掘的交易数据集记为D（一般为交易数据库），D＝｛T1，T2，…，Tk，…,Tn｝，Tk（k＝1,2,…，n）称为交易，对应每一个交易有唯一的标识，记作TID。元素im（m＝1,2,…，p）称为项。设I={i1，i2，…，im}是D中全体项组成的集合，且Tk

I。交易号（TID）

项集合（Itemsets）

T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3设X是一个I中项的集合，如果X

Tk，那么称交易Tk包含项集X。若X,Y为项集，X

I,Y

I，并且X

Y=

，则形如X==>Y的表达式称为关联规则。

关联规则形式化定义置信度支持度

关联规则度量规则X

Y在交易数据集D中的置信度是对关联规则准确度的衡量。度量关联规则的强度。即在所有出现了X的活动中出现Y的频率，即规则X

Y的必然性有多大。记为confidence(X

Y)。计算方法：包含X和Y的交易数与包含X的交易数之比：confidence(X

Y)=P(Y∣X)=|{T:X

Y

T，T

D}|/|{T:X

T，T

D}|×100%规则X

Y在交易数据集D中的支持度是对关联规则重要性的衡量，反映关联是否是普遍存在的规律，说明这条规则在所有交易中有多大的代表性。即在所有交易中X与Y同时出现的频率记为：support(X

Y)。计算方法：交易数据集中同时包含X和Y的交易数与所有交易数之比：support(X

Y)=P(X∪Y)=|{T:X

Y

T，T

D}|/|D|×100%（其中|D|是交易数据集D中的所有交易数）最小置信度阈值最小支持度阈值同时满足最小置信度阈值和最小支持度阈值的关联规则为强关联规则，是有意义有价值。

关联规则度量

在给定一个交易数据集D，挖掘关联规则问题就是产生支持度和置信度分别大于用户给定的最小支持度阈值和最小置信度阈值的关联规则。

关联规则度量经常使用的“支持度-可信度”的框架。这样的结构有时会产生一些错误的结果。例：假设体育类用品零售商调查了10000名顾客在购买什么商品，得到的结果是6000名顾客购买篮球，7500名顾客购买足球，4000名顾客购买篮球、足球。设最小支持度为30%，最小置信度为60%，可得到如下的关联规则：篮球足球（支持度＝40%，置信度为66%）

这条规则其实是错误的，因为购买足球的比例是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(X∩Y)期望可信度

Y出现的频率

P(Y)改善度

置信度对期望可信度的比值

P(Y|X)/P(Y)

关联规则度量找出所有具有最小支持度的项集(频繁项集)。用Apriori、FP-Growth等算法来找出频繁项集。使用频繁项集生成期望的关联规则对于每一个频繁项集l，找出其中所有的非空子集；然后，对于每一个这样的子集a，如果support(l)与support(a)的比值大于最小可信度，则存在规则a==>(l-a)。挖掘交易数据库D中所有关联规则的问题可以被划分为两个子问题：找出频繁项集－－Apriori算法

Apriori性质

Apriori算法基本思想交易号项集合T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3表1交易数据库D

例：找出频繁项集－－Apriori算法项集支持度计数｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2项集支持度计数｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2C1L1扫描D，对每个候选计数比较候选支持度计数与最小支持度计数找出频繁1－项集的集合L1找出频繁项集－－Apriori算法例：最小支持度阈值为2项集支持度计数｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2项集｛I1，I2｝｛I1，I3｝｛I1，I4｝｛I1，I5｝｛I2，I3｝｛I2，I4｝｛I2，I5｝｛I3，I4｝｛I3，I5｝｛I4，I5｝L1C2由L1产生候选C2Lk-1用于产生候选Ck

找出频繁项集－－Apriori算法连接&剪枝项集支持度计数｛I1，I2｝4｛I1，I3｝4｛I1，I4｝1｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2｛I3，I4｝0｛I3，I5｝1｛I4，I5｝0项集支持度计数｛I1，I2｝4｛I1，I3｝4｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2C2L2比较候选支持度计数与最小支持度计数扫描D，对每个候选计数项集支持度计数｛I1，I2｝4｛I1，I3｝4｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2L2项集｛I1，I2，I3｝｛I1，I2，I5｝由L2产生候选C3C3连接&剪枝连接：C3＝L2∞L2＝{{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I5}}∞{{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,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}。剪枝后C3＝{{I1,I2,I3},{I1,I2,I5}}。

项集支持度计数｛I1，I2，I3｝2｛I1，I2，I5｝2C3扫描D，对每个候选计数比较候选支持度计数与最小支持度计数项集支持度计数｛I1，I2，I3｝2｛I1，I2，I5｝2L3对每个交易，使用subset函数找出交易中是候选的所有子集，并对每个这样的候选累加计数，所有满足最小支持度的候选形成频繁项集L。

输入：交易数据库D；最小支持度阈值min_sup。输出：D中的频繁项集L。方法：(1)找频繁项集1-项集;(2)apriori_gen(Lk-1,min_sup)函数做两个动作：连接和剪枝。用于在第k-1次遍历中生成的Lk-1生成Ck(3)由Ck生成Lk

Apriori算法详述

子集函数Subset

？子集函数Subset用于确定在一个给定的交易t中包含了哪些Ck中的项。候选集Ck被存放在一棵hash树中，hash树中的结点分为两类：一类包含一个项集列表(叶结点)，另一类包含一张hash表(内部结点)。在内部结点上，hash表中的每一个桶都指向另一个结点。假定hash树的根结点的深度等于1，则一个深度为d的内部结点指向深度为d＋1的结点。项集都存放在叶子结点，当需要添加一个项集c的时候，就从根结点出发直到叶子结点。在一个深度为d的内部结点，对该项集的第d项应用hash函数来确定下一步遍历的分支。所有的结点最初都被创建为叶子结点。当一个叶子结点的项集数目超出某一个阈值时，该结点将会转化为一个内部结点。从根结点开始，子集函数按照如下的方式找出包含在交易t中的所有的候选集。如果在叶子结点，找出该叶子结点中所有包含在交易t中的项集，并且为它们添加一个指向结果集的索引；如果通过散列第i项到达某个内部结点，则散列交易t中第i项后的每一项，并且将这个过程递归地应用于相应的桶。对于根结点，则散列交易t中的每一项。子集函数能够返回所需要的候选集的索引，对于任何交易t中包含的项集c，c的第一个项一定出现在t中。在根结点，通过散列交易t中的每一项，我们能够确定只忽略那些不是从t中的某一项开始的项集。同样的结论也适用于hash树中位于其他层次的结点。由于在每一个项集中的项都经过排序，如果我们通过散列项i到达当前的结点，则以后只需要考虑交易t中出现在项i后的项。

Apriori算法详述（续）1.基于划分的方法2.基于散列的方法3.基于采样的方法4.交易压缩方法

（不包含任何k项集的交易不可能包含k+1项集）

Apriori算法优化D中交易将D划分成n部分找出局部每一部分频繁项集（1次扫描）结合局部频繁项集形成候选项集第1遍在候选项集中找出全局频繁项集（1次扫描）D中频繁项集第2遍基于划分的方法桶地址0123456桶记数2242244桶内容{I1,I4}{I3,I5}{I1,I5}{I1,I5}{I2,I3}{I2,I3}{I2,I3}{I2,I3}{I2,I4}{I2,I4}{I2,I5}{I2,I5}{I1,I2}{I1,I2}{I1,I2}{I1,I2}{I1,I3}{I1,I3}{I1,I3}{I1,I3}基于散列技术压缩候选k－项集Ck使用散列函数h(x,y)=(orderofx)*10+(orderofy))mod7创建散列表候选2项集的散列表步骤：a.

对于每个频繁项集l，找出l的所有非空子集；b.对于l的每个非空子集a，如果

support_count(l)/support_count(a)≥min_conf，则输出规则“a＝>（l－a）”。频繁项集产生强关联规则例：假定数据包含频繁集l＝{I1,I2,I5}，L的非空子集有{I1,I2},{I1,I5},{I2,I5},{I1},{I2},和{I5}。可以由l产生的关联规则：

I1

I2

I5，confidence＝2/4＝50%；

I1

I5

I2，confidence＝2/2＝100%；

I2

I5

I1，confidence＝2/2＝100%；

I1

I2

I5，confidence＝2/6＝33%；

I2

I1

I5，confidence＝2/7＝29%；

I5

I1

I2,confidence＝2/2＝100%；若最小置信度阈值为70%，则只有I1

I5

I2，I2

I5

I1，I5

I1

I2可输出，是强关联规则不需要生成大量候选项集的频繁项集挖掘。算法采用分而治之的策略。频繁模式增长（FP-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-Growth算法例null{}b:1f:3c:1b:1p:1f:1c:1m:1p:1a:1a:2b:1m:1f:2c:2a:3f:4c:3m:2p:21.f,c,a,m,p2.f,c,a,b,m3.f,b4.c,b,p5.f,c,a,m,pFP-Growth算法例生成的FP树

FP-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,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-Growth算法例前缀路径性质为计算路径p上的一个节点ai的频繁模式，只需要计算p中ai的前缀子树，并且前缀子树中的每个节点的频繁数和节点ai相同。

FP-Growth算法详述引理：片段增长假设α是DB中的一个项集，B是α的一个条件模式库，β是B中的一个项集，那么，α∪β在DB中的支持度和β在B中的支持度是相同的。推论：模式增长假设α是DB中的一个频繁项集，B是α的条件模式库，β是B中的一个项集。当且仅当β在B中是频繁时，α∪β在DB中才是频繁的。

FP-Growth算法详述引理单路径FP树的模式生成假设一个FP树T，只有一条路径P，通过列举P的子路径的所有组合，可以得到T的频繁模式全集，它们的支持度等价于子路径中的所有项的最小支持度。

FP-Growth算法详述算法2：在FP树中挖掘频繁模式输入：用DB根据算法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-Growth算法详述1.简单关联规则单维、单层、布尔型关联规则2.量化关联规则3.多维关联规则4.跨层关联规则关联规则分类篮球=>篮球服，只涉及到用户购买的物品性别=“女”=>平均收入=2300，涉及的收入是数值类型性别=“男”=>购买＝“篮球”，涉及两个维

Adidas篮球=>Nike篮球服同层关联规则层间关联规则篮球=>Nike篮球服挖掘量化关联规则数值字段根据数据的分布分成布尔字段每个布尔字段都表示一个数值字段的区间，落在其中则为1，反之为0。这种分法是动态的。得出的规则称布尔量化关联规则。使用预定义的概念分层对量化属性离散化如年龄的概念分层可以分为区间，“20..24”，“25..29”，“35..39”等替换原来的数值。得出的规则也叫做静态量化关联规则。数值字段被分成一些能体现含义的区间，紧扣区间数据的语义。考虑数据点之间的距离因素。得出的规则称基于距离的关联规则。直接用数值字段中的原始数据进行分析根据数据的分布对数值字段的值进行分析，数值属性动态离散化，以满足某种挖掘标准，如最大化所挖掘的规则的置信度。该策略将数值属性的值处理成量，而不是预定义的区间或分类。得出的规则称量化关联规则。

挖掘量化关联规则挖掘量化关联规则体育类商品球类运动服类辅助用品类篮球足球Adidas………Nike………篮球服足球服……