第二章 关联规则 Association rules

主要内容 1 关联规则概述 2 关联规则有关概念 3 关联规则算法： AIS算法和Apriori 算法

第一部分：关联分析概述 1、关联规则的基本含义 2、关联规则分类 3、应用举例

什么是关联关系 关联关系：两个变量之间存在着一定的联系，比如因果关系或者时序关系。 比如： 购买面包的顾客90%也会购买牛奶； AT&T股票连续上涨两天而DEC股票不跌，则IBM上涨的可能性比较大（75%）； 有太阳的时候基本上是晴天

关联规则的分类 1、根据变量类型：布尔型关联规则和数值型关联规则 布尔型关联规则：变量类型都是离散的 数值型关联规则：存在变量类型是连续的

思考：下面的数据类型是什么？

思考：下面的规则是布尔型还是数值型 1、做地产行业的财富榜排名前10的可能性比较大 2、地产开发商容易身价在300亿以上 3、年龄小于40的难以跻身财富榜前十

2、单层关联规则和多层关联规则 根据抽象层次来判断 尿布啤酒 优乐牌尿布青岛啤酒 {衣服，鞋子} {外套、运动鞋} {夹克、长靴}

3、单维规则与多维规则 单维规则：涉及一个属性 多维规则：涉及多个属性 啤酒尿布 地产开发商容易身价在300亿以上

应用举例（一） 零售业：安排商品布局，提供购买建议 已知：物品A和物品B经常出现在同一笔交易中，你会考虑怎么做？

应用举例（二） 市场营销：分析顾客的购买行为和习惯 年龄大于40岁，在某工业区的投保人有近一半曾经向保险公司索赔 原因是该地区污染比较严重

应用举例（三） 识别欺诈，发现异常事件 保险公司分析客户的保险申请，发现某客户有不寻常的多项保险申请。

应用举例（四） 英特网：提高网络相应速度 发现用户浏览网页时，会按顺序浏览一批网站，这时候在打开第一个网页时，将后面的网页更新缓存中

项集、k阶项集、事务集、支持度、支持数、大项集 第二部分：关联规则的有关概念 交易 商品 A 薯片, 沙司, 曲奇, 饼干, 可乐, 啤酒 B 生菜, 菠菜, 桔子, 芹菜, 苹果, 葡萄 C 薯片,沙司, 披萨, 蛋糕 D 生菜,菠菜, 牛奶, 黄油 项集、k阶项集、事务集、支持度、支持数、大项集

全体数据项集合I {薯片, 沙司, 曲奇, 饼干, 可乐, 啤酒,生菜, 菠菜, 桔子, 芹菜, 苹果, 葡萄,披萨, 蛋糕, 牛奶, 黄油} 项集：I的子集 如：{沙司、曲奇} K阶项集：长度为k的项集 事务集：一笔交易即为一个事务集

项集的支持数 某项集在事务集中出现的次数 项集的支持度 支持数/交易数 大项集 支持数大于最小支持数的项集；或支持度大于最小支持度的项集

思考：填写下面的表格 是否项集 阶数 支持数 支持度 是否大项集 {薯片、啤酒} {生菜、菠菜} {薯片、沙司} {薯片、生菜} {薯片} {生菜} {面包} 备注：假设最小支持数设为2

小结 关联规则 若某项集A是大项集，则认为项集A内的数据项存在关联关系 关联规则算法 寻找到大项集的算法

第三部分：布尔型关联规则挖掘算法 AIS算法 Apriori算法 其它改进算法

关联规则算法引入 穷举法： 由于可以得到全体数据项集合I 求出所有数据项集合I的子集的支持数，则可以得到大项集 假设I的阶数为k，则I的非空子集为2k-1 假设事务数为n，则穷举法的时间复杂度为 n*(2k-1) 穷举法需要花费的时间太多，所有的挖掘算法就是通过减少搜索的内容以所见查询时间

关联规则算法1-AIS算法 地位：第一个关联规则挖掘算法 核心思想：大项集必然是在一笔交易中出现的——减少候选项集 TID 项集 1 ACD 2 BCE 3 ABCE 4 BE 5 BC 项集 支持数 A 2 B 4 C D 1 E 3 项集 支持数 A 2 B 4 C D 1 E 3 大项集 支持数 B 4 C E 3 项集 支持数 AC 2 CD 1 BC 3 CE BE AB AE 项集 支持数 BC 3 BE 项集 支持数 BCE 2 ABC 1 ABE

思考 假设上例中，最小支持数为4，那利用AIS算法的过程？

关联规则算法1-Apriori算法 基于一个推论： 如果一个项集是大项集，那么它的所有子集都是大项集。反之，如果一个项集的某个子集不是大项集，则这个项集也不是大项集。

TID 项集 1 ACD 2 BCE 3 ABCE 4 BE 5 BC 项集 支持数 A 2 B 4 C D 1 E 3 大项集 支持数 B 4 C E 3 项集 支持数 BC 3 BE CE 2 项集 支持数 BC 3 BE 项集 支持数 BCE 2

思考 1、与AIS算法作比较 2、假设上例中，最小支持数为4，那利用Apriori算法的过程？

例题 假设2阶大项集为{AB,AC,AE,BC,BE}，利用Apriori算法的思想，构造3阶候选集 AB+ACABC AB+AEABE AB+BC ABC AB+BE ABE AC+AE ACE AC+BC ABC AC+BE ABCE AE+BC ABCE AE+BE ABE BC+BE BCE 3阶候选集是{ABC,ABE,ACE,BCE}

错了，3阶候选集应该是{ABC,ABE} 为什么？ 问： ABCE 在不在4阶候选集中？

Apriori的算法改进 1、减少扫描事务量：如果某事务不包含k阶大项集，则必然不包含k+1阶大项集 ——AproriTid算法

TID 项集 1 ACD 2 BCE 3 ABCE 4 BE 5 BC 6 F TID 项集 1 ACD 2 BCE 3 ABCE 4 BE 5 BC TID 项集 2 BCE 3 ABCE 4 BE 5 BC 项集 支持数 A 2 B 4 C D 1 E 3 F 项集 支持数 BC 3 BE CE 2 项集 支持数 BCE 2 大项集 支持数 B 4 C E 3 项集 支持数 BC 3 BE

例题 TID 项集 1 ACD 2 BCE 3 ABCE 4 BE 5 BC 6 F 7 GH 8 BCG

2、减少扫描次数，采用分而治之的方法 将一个事务集分解为若干个部分，整体的大项集必然至少是某一个子集的大项集。 假如在所有子集中都是大项集的肯定是大项集

1阶A B C E 2阶AC BC BE CE 3阶BCE 1阶B C E 2阶 BC BE 最小支持数为0.4*3=1.2 TID 项集 1 ACD 2 BCE 3 ABCE 最小支持数为0.4*3=1.2 TID 项集 1 ACD 2 BCE 3 ABCE 4 BE 5 BC 1阶A B C E 2阶AC BC BE CE 3阶BCE TID 项集 4 BE 5 BC 最小支持数为0.4*2=0.8 1阶B C E 2阶 BC BE 最小支持数为2，支持度为0.4

共有的：B、C、E、BC、BE 特有的：A {2}、AC{2}、BCE{2} 都是大项集？

思考 上例中，假如最小支持数是3，结果如何

小结：关联规则算法的手段 1、减少交易集 2、减少候选项集 3、分组

项集的整合

多属性关联规则的挖掘算法

多属性 扩展/最小扩展 B=A1∪A2 ∪A3，C= A1∪A2，A1 B是A1的扩展，B是C的扩展，C是A1的扩展 B是C的最小扩展，C是A1的最小扩展，但B不是A1的最小扩展

支持度 期望支持度 项集{A3 ∪A4，A5，A9 }的支持度？ 规则 A3 ∪A4 {A5,A9}的支持度？ 规则A3 ∪A4 {A5,A9} 是规则A3 {A5,A9}的扩展，则规则A3 {A5,A9}的期望支持度是多少？ 根据期望支持度和实际支持度，判断一个规则是否有用

置信度 期望置信度 规则 A3 ∪A4 {A5UA6,A9}的置信度？ 规则A3 ∪A4 {A5UA6,A9}是规则A3 ∪A4 {A5,A9}的扩展 A3 ∪A4 {A5,A9}的期望置信度

大家思考一下，这张表如何分析