第 8 章 集合论方法（二） 关联规则挖掘8.2关联规则挖掘n8.2.1关联规则的挖掘原理n8.2.2Apriori算法基本思想n8.2.3Apriori算法n8.2.4基于Fp-tree的关联规则挖掘算法8.2关联规则挖掘n关联规则（Association Rule）挖掘是发现大 量数据库中项集之间的关联关系n从大量商业事务中发现有趣的关联关系，可以 帮助许多商业决策的制定，如分类设计、交叉 购物等nAgrawal等人于1993年首先提出了挖掘顾客 交易数据库中项集间的关联规则问题 8．2．1关联规则的挖掘原理关联规则是发现交易数据库中不同商品（项 ）之间的联系，这些规则找出顾客购买行为 模式 例1：在购买铁锤的顾客当中，有70％的人同时 购买了铁钉例2：年龄在40 岁以上，工作在A区的 投保人当中，有45％的人曾经向保险公 司索赔过 可以看出来，A区可能污染比较严重， 环境比较差，索赔率也相对比较高 1. 基本原理n设I={i1,i2,…,im}是项（Item）的集合记D为 事务（Transaction）的集合（事务数据库）， 事务T是项的集合，并且TIn设A是I中一个项集，如果AT，那么称事务T 包含A。
n定义1：关联规则是形如AB的蕴涵式，这里 AI，BI，并且AB=n定义2：规则的支持度n规则AB在数据库D中具有支持度S，表 示S是D中事务同时包含AB的百分比，它 是概率P(AB)，即：n n其中|D|表示事务数据库D的个数，表示A 、B两个项集同时发生的事务个数n定义3：规则的可信度n规则AB具有可信度C，表示C是包含 A项集的同时也包含B项集，相对于包 含A项集的百分比，这是条件概率 P(B|A)，即：n n其中 表示数据库中包含项集A的事务 个数 n定义4：阈值n在事务数据库中找出有用的关联规则，需要由 用户确定两个阈值：最小支持度（min_sup） 和最小可信度（min_conf）n定义5：项的集合称为项集（Itemset），包含 k个项的项集称之为k-项集n如果项集满足最小支持度，则它称之为频繁项 集（Frequent Itemset） n定义6：关联规则n同时满足最小支持度（min_sup）和最小 可信度（min_conf）的规则称之为关联 规则，即n成立时，规则称之为关联规则，也可以 称为强关联规则2. 关联规则挖掘过程n关联规则的挖掘一般分为两个过程：n（1）找出所有的频繁项集：找出支持度 大于最小支持度的项集，即频繁项集。
n（2）由频繁项集产生关联规则：根据定 义，这些规则必须满足最小支持度和最 小可信度3. 关联规则的兴趣度n例子：讨论不购买商品与购买商品的关系n设，交易集D，经过对D的分析，得到表格:买咖啡不买咖啡合 计 买牛奶20525 不买牛奶70575 合计9010100n设定minsupp=0.2, minconf=0.6, 得到如下的关联规则：n 买牛奶 → 买咖啡 s=0.2 c=0.8n即80％的人买了牛奶就会买咖啡n同时得到结论：90％的人肯定会买咖啡n规则n 买咖啡 →不买牛奶 s=0.7 c=0.78n支持度和可信度分别为0.7和0.78，更具有商业销售的指导 意义n定义7：兴趣度： n n公式反映了项集A与项集B的相关程度n若 即n表示项集A出现和项集B是相互独立的n若n表示A出现和B出现是负相关的n若n表示A出现和B出现是正相关的意味着A的出 现蕴含B的出现n一条规则的兴趣度越大于1说明我们对这条规 则越感兴趣（即其实际利用价值越大）；n一条规则的兴趣度越小于1说明我们对这条规 则的反面规则越感兴趣（即其反面规则的实际 利用价值越大）；n兴趣度I不小于0。
所有可能的关联规则 Rules SCI1 买牛奶→买 咖啡0.20.80.89 2买咖啡→买 牛奶 0.20.220.89 3买牛奶→不 买咖啡0.050.224不买咖啡→ 买牛奶0.050.525不买牛奶→ 买咖啡0.70.931.0376买咖啡→不 买牛奶0.70.781.0377不买牛奶→不 买咖啡0.050.0670.678不买咖啡→不 买牛奶0.050.20.87n讨论I1﹑I2﹑I3﹑I6共4条规则：n由于I1,I21,规则才有价值n兴趣度也称为作用度（Lift）,表示关联规 则A→B的“提升”如果作用度（兴趣度 ）不大于1，则此关联规则就没有意义了 n概括地说：n可信度是对关联规则地准确度的衡量n支持度是对关联规则重要性的衡量支持度说明了这条 规则在所有事务中有多大的代表性有些关联规则可信 度虽然很高，但支持度却很低，说明该关联规则实用的 机会很小，因此也不重要n兴趣度（作用度）描述了项集A对项集B的影响力的大小 兴趣度（作用度）越大，说明项集B受项集A的影响越 大 8．2．2 Apriori算法基本思想Apriori是挖掘关联规则的一个重要方法。
算法分为两个子问题：n找到所有支持度大于最小支持度的项集（ Itemset），这些项集称为频繁集（ Frequent Itemset）n使用第1步找到的频繁集产生规则 nApriori 使用一种称作逐层搜索的迭代方 法，“K-项集”用于探索“K+1-项集”n首先，找出频繁“1-项集”的集合该集合 记作L1L1用于找频繁“2-项集”的集合L2 ，而L2用于找L3，n如此下去，直到不能找到“K-项集”找每 个LK需要一次数据库扫描1．Apriori 性质n性质：频繁项集的所有非空子集都必须 也是频繁的n如果项集B不满足最小支持度阈值min-sup，则B不是频 繁的，即n P（B）该分枝具有三 个节点，其中B作根节点的子链接，A链接到B ，E链接到A从L表中节点链中，项B，A，E 的指针分别指向树中Ｂ、Ａ、Ｅ节点 n第二个事务“Ｔ２：Ｂ，Ｄ”按Ｌ的次序也是｛ Ｂ，D｝仍以B开头，这样在B节点中产生一个 分枝，该分枝与T1项集存在路径共享前缀B 这样，将节点B的计数增加1，即（B:2），并 创造一个D的新节点（D:1），作为（B:2）的 子链接n第三个事务“T3：B，C”同第二个事务一样处理 ，因为有相同的B为头，在B节点又产生一个分 枝，产生新节点，记为（C:1），节点B的计数 再增加1（为3），即（B:3）。
n第四个事务“T4：A，B，D”，按L的次序 为{B，A，D}在FP-树中B，A，已有节 点，将共享前缀路径，从A节点分枝产生 D的另一新节点，记为（D:1），共享节 点B，A的计数均增加1，即（B:4），（ A:2）此（D:1）节点用指针指向前面 产生的（D:1）节点，在L表中节点链接 中指针指向该（D:1）节点 n第五个事务“T5：A，C”，按L表的次序为{A， C}在FP-树中，由于该事务不含Ｂ节点，不 能共享Ｂ分枝从null节点产生FP-树的第二个 分枝，建新Ａ节点，记为（A:１），由该节点 产生分枝，建新C节点，即为（C:1）由于B 分枝中有（A:2）节点这样，从（A:2）节点 用指针指向此（A:1）节点，B分枝中有（C:1 ）节点，它用指针指向此（C:1）节点n第六个事务“T6：B，C”，同第三个事务 那样，沿FP-树的B-C分枝的节点计数各 增加1，变为（B:5）和（C:2）n第七个事务“T7：A，C”，同第五个事务 ，沿FP-树的A-C分枝的节点计数各增加1 ，变为（A:2）和（C:2）n第八个事务“T8：A，B，C，E”，按L表的 次序为{B，A，C，E}，可沿分枝B-A方 向，在A节点处新建分枝，建C结点，记 （C:1），由该节点再建分枝，建E节点 ，记为（E，1），前面B，Ａ节点计数各 增加１，变为：（B:6），（A:3）。
FP- 树中原E节点（E:1）中的指针指向该（E ，1）节点 n第九个事务“T9：A，B，C”，按L表的次 序为{B A C}，同第八个事务，分枝B-A- C方向，且已有节点，分别对B，A，C三 个节点计数增加1，变为（B:7），（A:4 ），（C:2）n最终的FP-树的表示如图所示事务数据库的FP-树 n从FP-树可以看出，从L表的节点连的指针开始 ，指向B节点，它的计数器为7，n指向A节点，共有两个A节点，累加计数为6；n指向C节点，共有三个C节点，累加计数为6；n指向D节点，共有二个D结点，累加计数为2；n指向E节点，共有二个E节点，累加计数为2 这样， 频繁模式都在FP-树中表现出来 n（2）频繁模式挖掘过程n从FP-树中来挖掘频繁模式，先从L表中最后一 项开始E在FP-树有两个分枝，路经为 和n以E为后缀，它的两个对应前缀路径是（BA:1 ）和（BAC:1），它们形成E的条件模式基它 的条件FP-树只包含单个路径；不包 含C，因为它的支持度计数为1，小于最小支持 度计数n该单个路径产生频繁模式的所有组合：{BE:2 ，AE:2，BAE:2} n对于D， 它的两个前缀形成条件模式基{（ BA:1）,（B:1）}，产生一个单节点的条件 FP- 树（B:2），并导出一个频繁模式{BD:2}。
n对于C，它的条件模式基是{（BA:2）,（B:2） ，（A:2）}，它的条件FP-树有两个分枝（B:4 ，A:2）和（A:2）它的频繁模式集为： {BC:4，AC:4，BAC:2}n对于A，它的条件模式基是{（B:4）}，它的FP -树只包含一个节点（B:4），产生一个频繁模 式{BA:4} 利用FP-树挖掘频繁模式项条件 模 式 基条件 FP- 树频繁模 式EBA:1 ， BA C:1(B:2,A :2)BE:2,AE :2,BA E:2DBA:1, B:1(B:2)BD:2CBA:2, B:2, A:2(B:4,A :2)( A:2 )BC:4,AC :4,BA C:2AB:4(B:4)BA:43. 示例说明n假设有10个事务的数据库D，项目集合 {a,b,c,d,e,f,g,h,i}，最小支持度20% TIDT0T 1T 2T 3T 4T 5T 6T 7T8T 9项集ea,c,g,id,hb,dd,ea,c,e,i a,c,e,f,ia,e,ga,c,e,ic,e,gn使用FP_growth算法，可以得到数据库D的频 繁项目集为n{{e}:7，{a}:5，{c}:5，{i}:4，{d}:3，{g}:3 ，{a,c}:4，{a,e}:4，{a,g}:2，{ a,i }:4， {c,e}:4，{c,g}:2，{c,i}:4，{e,g}:2，{e,i}:3， {a,c,e}:3，{a,c,i}:4，{a,e,i}:3，{c,e,i}:3， {a,c,e,i}:3}。
n其中，b, f, h不是频繁项集结 束。