关联报告人熊赟PPT课件.ppt

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

关关 联联 分分 析析 n关联规则发现的主要对象是交易型数据库，一个交易一般由交易处理时间，一组顾客购买的物品，有时也有顾客标识号(如信用卡号)组成n定义3.2：关联规则关联规则是描述在一个交易中物品之间同时出现的规律的知识模式，更确切的说，关联规则是通过量化的数字描述物品X的出现对物品Y的出现有多大的影响 关关 联联 规规 则则 以零售业为例，体育用品商场通过对销售数据进行关联分析通常可以发现这些数据中常常隐含形式如下的规律——“购买篮球的顾客中有70%的人同时购买篮球运动服，所有交易中有40%的人同时购买篮球和篮球运动服” 等等这些规律即关联规则关联规则 关关 联联 规规 则则n定定义义3.33.3：：关联规则挖掘的交易数据集记为D（一般为交易数据库），D＝｛T1，T2，…，Tk，…,Tn｝，Tk（k＝1,2,…，n）称为交易，对应每一个交易有唯一的标识，记作TIDn元素im（m＝1,2,…，p）称为项设I={i1，i2，…，im}是D中全体项组成的集合，且TkI。

交易号交易号（TID） 项集合项集合（（Itemsets） T100 I1，I2，I5 T200 I2，I4 T300 I2，I3 T400 I1，I2，I4 T500 I1，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(Xconfidence(XY)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(Xsupport(XY)Y)计算方法：交易数据集中同时包含X和Y的交易数与所有交易数之比：support(XY) = P(X∪Y) = |{T: XYT，TD}|/|D|×100%（其中|D|是交易数据集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) 关联规则度量关联规则度量挖掘交易数据库挖掘交易数据库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 例：例：找出频繁项集－－找出频繁项集－－AprioriApriori算法算法项集支持度计数｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2项集支持度计数｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2C1L1扫描D，对每个候选计数比较候选支持度计数与最小支持度计数找出频繁1－项集的集合L1找出频繁项集－－找出频繁项集－－AprioriApriori算法算法例：最小支持度阈值 为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 找出频繁项集－－找出频繁项集－－AprioriApriori算法算法连接连接& &剪枝剪枝项集支持度计数｛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对每个交易，使用对每个交易，使用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算法详述算法详述 子集函数子集函数SubsetSubset ？？•子集函数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后的项 AprioriApriori算法详述（续）算法详述（续）•1. 1. 基于划分的方法基于划分的方法 •2. 2. 基于基于散列散列的方法的方法 •3. 3. 基于采基于采样样的方法的方法 •4. 4. 交易压缩方法交易压缩方法 （不包含任何k项集的交易 不可能包含k+1项集） AprioriApriori算法优化算法优化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)=(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＝>（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-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算法例算法例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-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,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中的支持度和β在B中的支持度是相同的。

推论： 模式增长假设α是DB中的一个频繁项集，B是α的条件模式库，β是B中的一个项集当且仅当β在B中是频繁时，α∪β在DB中才是频繁的  FP-GrowthFP-Growth算法详述算法详述引理 单单路路径径FP树树的的模模式式生生成成假假设设一一个个FP树树T，，只只有有一一条条路路径径P，，通通过过列列举举P的的子子路路径径的的所所有有组组合合，，可可以以得得到到T的的频频繁繁模模式式全全集集，，它它们们的的支支持持度度等等价价于于子子路路径径中中的的所所有有项项的的最最小小支支持持度 FP-GrowthFP-Growth算法详述算法详述算法2：在FP树中挖掘频繁模式输入：用DB根据算法1构造的FP树和最小支持度阈值ξ；输出：所有的频繁模式的集合；方法：调用FP-Growth ( FP-Tree , null )； Procedure FP-Growth ( Tree, α){(1) if (Tree只包含单路径P) then(2) 对路径P中节点的每个组合（记为β）(3) 生成模式β∪α，支持数＝β中所有节点的最小支持度(4) else 对Tree头上的每个ai，do{(5)生成模式β= ai ∪α，支持度＝ai.support；(6)构造β的条件模式库和β的条件FP树Treeβ；(7)   if Treeβ≠φ(8)           then call FP-Growth ( Treeβ , β ) }}FP-GrowthFP-Growth算法详述算法详述w1. 简单关联规则 单维、单层、布尔型关联规则w2. 量化关联规则w3. 多维关联规则w4. 跨层关联规则关联规则分类关联规则分类篮球=>篮球服，只涉及到用户购买的物品性别=“女”=>平均收入=2300，涉及的收入是数值类型性别=“男”=>购买＝“篮球”，涉及两个维 Adidas篮球=> Nike篮球服同层关联规则层间关联规则篮球=> Nike篮球服挖掘量化关联规则挖掘量化关联规则数值字段根据数据的分布分成布尔字段数值字段根据数据的分布分成布尔字段每个布尔字段都表示一个数值字段的区间，落在其中则为1，反之为0。

这种分法是动态的得出的规则称布尔量化关联规则布尔量化关联规则使用预定义的概念分层对量化属性离散化使用预定义的概念分层对量化属性离散化如年龄的概念分层可以分为区间，“20..24”，“25..29”，“35..39”等替换原来的数值得出的规则也叫做静态量化关联规则静态量化关联规则 数值字段被分成一些能体现含义的区间，紧数值字段被分成一些能体现含义的区间，紧扣区间数据的语义扣区间数据的语义考虑数据点之间的距离因素考虑数据点之间的距离因素得出的规则称基于距离的关联规则 直接用数值字段中的原始数据进行分析直接用数值字段中的原始数据进行分析根据数据的分布对数值字段的值进行分析，数值属性动态离散化，以满足某种挖掘标准，如最大化所挖掘的规则的置信度该策略将数值属性的值处理成量，而不是预定义的区间或分类得出的规则称量化关联规则量化关联规则 挖掘量化关联规则挖掘量化关联规则挖掘量化关联规则挖掘量化关联规则体育类商品体育类商品球类球类运动服类运动服类辅助用品类辅助用品类篮球篮球足球足球AdidasAdidas………………NikeNike………………篮球服篮球服足球服足球服…………体育用品的概念分层Adidas篮球=> Nike篮球服篮球=> Nike篮球服挖掘跨层关联规则挖掘跨层关联规则n n同同层层关关联联规规则则即处于同概念层的关联规则，其挖掘是在特定概念层上逐层展开的，需对项的每个层次进行处理，一般采用自顶向下 策略。

对每一层，可以使用类似于单层关联规则挖掘的发现频繁项集的任何算法； 算法有ML-T2、ML-SH、ML-TMAX、 ML-T2+等n n层层间间关关联联规规则则跨越层边界，规则中的项不要求属于同一概念层 算法有：ML-CH等 挖掘跨层关联规则挖掘跨层关联规则层2  最小支持度 ＝ 5%  体育类商品（支持度＝10％）篮球（支持度＝6％）足球（支持度＝4％）层1 最小支持度 ＝ 5%  频繁频繁频繁频繁非频非频繁繁同层关联规则同层关联规则 统一的最小支持度统一的最小支持度体育类商品（支持度＝10％）篮球（支持度＝6％）足球（支持度＝4％）频繁频繁频繁频繁频繁频繁层2  最小支持度 ＝ 3%  层1 最小支持度 ＝ 5%  递减的最小支持度递减的最小支持度——逐层独立逐层独立体育类商品（支持度＝10％）篮球足球非频非频繁繁不考不考察察不考不考察察层2  最小支持度 ＝ 3%  层1 最小支持度 ＝ 12%  递减的最小支持度递减的最小支持度——层交叉单项过滤层交叉单项过滤球类和运动服（支持度＝7％）足球和篮球运动服（支持度＝1％）频繁频繁被考察层2  最小支持度 ＝ 2%  层1 最小支持度 ＝ 5%  一个第i层的k－项集被考察，当且仅当它在第（i-1）层的父节点k－项集是频繁的。

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