数据库课件：第十二讲 关联分析方法 .ppt

1、1第12讲 关联分析方法本讲讲授目标：本讲讲授目标：1. 关联规则挖掘的基本概念关联规则挖掘的基本概念2. 关联规则挖掘的过程关联规则挖掘的过程3. 关联规则挖掘的关联规则挖掘的Apriori算法算法4. 关联规则价值衡量的方法关联规则价值衡量的方法2一. 关联规则挖掘的基本概念关联规则挖掘的基本概念1. 购物篮分析引发关联规则挖掘的例子购物篮分析引发关联规则挖掘的例子 问题：问题：“什么商品组或集合什么商品组或集合, 顾客多半会在一次购顾客多半会在一次购物中同时购买？物中同时购买？”例例购买计算机与购买财务管理软件的关联规则购买计算机与购买财务管理软件的关联规则可表示为：可表示为：compu

2、ter financial_management_software support=2%,confidence=60% support为支持度，为支持度，confidence为置信度。为置信度。该规则表示：在所分析的全部事务中，有该规则表示：在所分析的全部事务中，有2的事的事务同时购买计算机和财务管理软件；在购买计算务同时购买计算机和财务管理软件；在购买计算机的顾客中机的顾客中60也购买财务管理软件。也购买财务管理软件。3关联规则关联规则 关联（关联（Associations）分析的目的是为了）分析的目的是为了挖掘隐藏在数据间的相互关系，即对于给挖掘隐藏在数据间的相互关系，即对于给定的一组项目

3、和一个记录集，通过对记录定的一组项目和一个记录集，通过对记录集的分析，得出项目集中的项目之间的相集的分析，得出项目集中的项目之间的相关性。关性。 项目之间的相关性用关联规则来描述，关项目之间的相关性用关联规则来描述，关联规则反映了一组数据项之间的密切程度联规则反映了一组数据项之间的密切程度或关系。或关系。 4置信度和支持度置信度和支持度 support(XY)(包含包含X和和Y的事务数的事务数 / 事务总数事务总数)100confidence(XY)(包含包含X和和Y的事务数的事务数 / 包含包含X的事务数的事务数)100 置信度和支持度均大于给定阈值（即最小置信度阈置信度和支持度均大于给定阈

4、值（即最小置信度阈值和最小支持度阈值）。即：值和最小支持度阈值）。即：support(XY) min_supconfidence(XY) min_conf 的关联规则称为强规则；否则称为弱规则。的关联规则称为强规则；否则称为弱规则。 数据挖掘主要就是对强规则的挖掘。通过设置最小数据挖掘主要就是对强规则的挖掘。通过设置最小支持度和最小置信度可以了解某些数据之间的关联支持度和最小置信度可以了解某些数据之间的关联程度。程度。5频繁项集频繁项集定义定义在关联规则挖掘算法中，把项目的在关联规则挖掘算法中，把项目的集合称为项集（集合称为项集（itemset），包含有），包含有k个项目个项目的项集称为的项集

5、称为k-项集。包含项集的事务数称为项集。包含项集的事务数称为项集的出现频率，简称为项集的频率或支持项集的出现频率，简称为项集的频率或支持度计数。度计数。 如果项集的出现频率大于或等于最小支持如果项集的出现频率大于或等于最小支持度度S与与D中事务总数的乘积，则称该项集满足中事务总数的乘积，则称该项集满足最小支持度最小支持度S。如果项集满足最小支持度，则。如果项集满足最小支持度，则称该项集为频繁项集（称该项集为频繁项集（frequent itemset ）。）。6强规则强规则 强规则强规则XY对应的项集（对应的项集（XY）必定是频）必定是频繁集。因此，可以把关联规则挖掘划分为繁集。因此，可以把关联

6、规则挖掘划分为以下两个子问题：以下两个子问题： 根据最小支持度找出事务集根据最小支持度找出事务集D中的所有频繁项中的所有频繁项集。集。 核心核心 根据频繁项集和最小置信度产生关联规则。根据频繁项集和最小置信度产生关联规则。 较易较易 7举例 例例 购买商品事务如下表所示，设最小购买商品事务如下表所示，设最小支持度为支持度为50%, 最小可信度为最小可信度为 50%, 则可得则可得到以下关联规则：到以下关联规则： 规则规则1： A C (50%, 66.6%) 规则规则2： C A (50%, 100%)8关联规则挖掘的分类关联规则挖掘的分类 布尔关联规则布尔关联规则 量化关联规则量化关联规则

7、单维规则单维规则 buys(x,“computer”)=buys(x,“management_software”) 多维关联多维关联 age(“30.40”)income(“42000.50000”)=buys(x,“HR_TV”) 单层关联规则单层关联规则 age(“30.40”)=buys(x,“IBM computer”) 多层关联规则多层关联规则 age(“30.40”)=buys(x,“computer”)9二二. . 关联规则挖掘的过程关联规则挖掘的过程定义定义在关联规则挖掘算法中，把项目的在关联规则挖掘算法中，把项目的集合称为项集（集合称为项集（itemset），包含有），包含有

8、k个项个项目的项集称为目的项集称为k-项集。包含项集的事务数项集。包含项集的事务数称为项集的出现频率，简称为项集的频率称为项集的出现频率，简称为项集的频率或支持度计数。如果项集的出现频率大于或支持度计数。如果项集的出现频率大于或等于最小支持度或等于最小支持度S与与D中事务总数的乘积，中事务总数的乘积，则称该项集满足最小支持度则称该项集满足最小支持度S。如果项集满。如果项集满足最小支持度，则称该项集为频繁项集足最小支持度，则称该项集为频繁项集（frequent itemset ）。）。10频繁项集的性质频繁项集的性质 Apriori性质：频繁项集的所有非空子集都性质：频繁项集的所有非空子集都必须

9、是频繁的。必须是频繁的。 Apriori性质基于如下事实：根据定义，如性质基于如下事实：根据定义，如果项集果项集I不满足最小支持度阈值不满足最小支持度阈值min_sup，则则I 不是频繁的，即不是频繁的，即sup（I） min_sup。如果将项如果将项A添加到添加到I， 则结果项集（即则结果项集（即IA）不可能比不可能比I更频繁出现。因此，更频繁出现。因此，IA也不是也不是频繁的，即频繁的，即 sup（IA）= min_conf则输出关联规则则输出关联规则“s (I-s)” ，其中，其中min_conf为为最小置信度阈值。最小置信度阈值。20举例 对数据包含频繁项集对数据包含频繁项集I=I1，

10、I2，I5, 置信度设定为置信度设定为70，第第1步：对于频繁项集步：对于频繁项集I=I1，I2，I5，产生，产生I的所有非空子集的所有非空子集: I1,I2,I1,I5,I2,I5,I1,I2,I5 第第2步：对于步：对于I的每一个非空子集的每一个非空子集s，输出关联规则，输出关联规则“s(I-s)”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/7

11、=100%最小置信度设定为最小置信度设定为70，则只有以下三个关联规则输出：，则只有以下三个关联规则输出：I1I5I2 confidence=2/2=100%I2I5I1 confidence=2/2=100%I5I1I2 confidence=2/7=100%21四. 关联规则价值衡量的方法1.系统客观层面系统客观层面 使用使用“支持度支持度-可信度可信度”的框架，有时会产生一些错误的结果。的框架，有时会产生一些错误的结果。看如下的一个例子：看如下的一个例子： 例例假设一个提供早餐的零售商调查了假设一个提供早餐的零售商调查了400名学生在早晨进名学生在早晨进行什么运动，得到的结果是行什么运动

12、，得到的结果是275名学生打篮球，名学生打篮球，280名学生晨名学生晨跑，跑，180名学生打篮球、晨跑。那么如果设名学生打篮球、晨跑。那么如果设minsup为为40%，minconf为为60%，可以得到如下的关联规则：，可以得到如下的关联规则： 打篮球打篮球 晨跑晨跑 因为它的支持度为因为它的支持度为180/400=45%;信任度为信任度为180/275=65.5%; 显然分别满足最小支持度和最小信任值得要求。显然分别满足最小支持度和最小信任值得要求。 但这条规则，其实是错误的，因为晨跑的学生的比例是但这条规则，其实是错误的，因为晨跑的学生的比例是70%，大于大于65.5%(信任度值信任度值)。说明了打篮球和晨跑之间所存在的关。说明了打篮球和晨跑之间所存在的关系是一种负关联，也就是存在打篮球将会减少晨跑的人数的系是一种负关联，也就是存在打篮球将会减少晨跑的人数的可能。可能。22四. 关联规则价值衡量的方法2. 用户主观层面用户主观层面 一个规则的有用与否最终取决于用户的感一个规则的有用与否最终取决于用户的感觉。只有用户可以决定规则的有效性、可觉。只有用户可以决定规则的有效性、可行性。所以应该将用户的需求和系统更加行性。所以应该将用户的需求和系统更加紧密的结合起来。紧密的结合起来。