数据管理(挖掘)02-关联规则

1、1第二讲 关联规则23 关联规则挖掘的研究是近几年研究较多的数据挖掘方关联规则挖掘的研究是近几年研究较多的数据挖掘方法，在数据挖掘的各种方法中应用最为广泛。在数据挖掘法，在数据挖掘的各种方法中应用最为广泛。在数据挖掘的知识模式中，关联规则是比较重要的一种。关联规则的的知识模式中，关联规则是比较重要的一种。关联规则的概念是由概念是由Agrawal、Imielinski和和Swami提出，是数据中提出，是数据中一种一种简单但实用简单但实用的规则。关联规则模式属于描述型模式，的规则。关联规则模式属于描述型模式，发现关联规则的算法属于无监督学习的方法发现关联规则的算法属于无监督学习的方法。 关联规则反

2、映了一个事物和其它事物之间的相互依存关联规则反映了一个事物和其它事物之间的相互依存性和关联性。如果两个或多个事物之间存在一定的关联关性和关联性。如果两个或多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其它事物预测到。目系，那么，其中一个事物就能够通过其它事物预测到。目前关联规则主要应用在商业数据库中：商品分类设计、降前关联规则主要应用在商业数据库中：商品分类设计、降价经销分析、生产安排、货架摆放策略等，其中最典型的价经销分析、生产安排、货架摆放策略等，其中最典型的例子就是购物篮例子就是购物篮(market basket)分析。分析。2.1 关联规则介绍关联规则介绍41.购物篮分析

3、购物篮分析 关联规则挖掘的一个典型例子是购物篮分析。市场分析员关联规则挖掘的一个典型例子是购物篮分析。市场分析员要从大量的数据中发现顾客放入其购物篮中的不同商品之间的要从大量的数据中发现顾客放入其购物篮中的不同商品之间的关系。如果顾客买牛奶，他也购买面包的可能性有多大？关系。如果顾客买牛奶，他也购买面包的可能性有多大？ 什么什么商品组或集合顾客多半会在一次购物时同时购买？例如，买牛商品组或集合顾客多半会在一次购物时同时购买？例如，买牛奶的顾客有奶的顾客有80%也同时买面包，或买铁锤的顾客中有也同时买面包，或买铁锤的顾客中有70%的人的人同时也买铁钉，这就是从购物篮数据中提取的关联规则。分析同时

4、也买铁钉，这就是从购物篮数据中提取的关联规则。分析结果可以帮助经理设计不同的商店布局。一种策略是：经常一结果可以帮助经理设计不同的商店布局。一种策略是：经常一块购买的商品可以放近一些，以便进一步刺激这些商品一起销块购买的商品可以放近一些，以便进一步刺激这些商品一起销售，例如，如果顾客购买计算机又倾向于同时购买财务软件，售，例如，如果顾客购买计算机又倾向于同时购买财务软件，那么将硬件摆放离软件陈列近一点，可能有助于增加两者的销那么将硬件摆放离软件陈列近一点，可能有助于增加两者的销售。另一种策略是：将硬件和软件放在商店的两端，可能诱发售。另一种策略是：将硬件和软件放在商店的两端，可能诱发购买这些商

5、品的顾客一路挑选其他商品。购买这些商品的顾客一路挑选其他商品。5设设I=i1,i2,in是项目的集合，其中的元素称为是项目的集合，其中的元素称为项目项目(item)。记记 D 为事物为事物 T (transaction)的集合，这里的集合，这里 T 是是项目的集合，并且项目的集合，并且 。对应每一个事物有一个唯一的标识，如事务号，对应每一个事物有一个唯一的标识，如事务号，记为记为TID。设设X是一个是一个 I 中项目的集合，如果中项目的集合，如果 ，那么，那么称事务称事务T包含包含X。如果项目。如果项目X包含包含k个项目，则称其为个项目，则称其为k项集。项集。IT IT TX 6一个关联规则是

6、形如一个关联规则是形如 的逻辑蕴含式，这里的逻辑蕴含式，这里 ， ，并且，并且 。支持度支持度(support)： 规则规则 在事务集在事务集 D 中的支持度是事务集中中的支持度是事务集中同时包含同时包含 X 和和 Y 的事务数与所有事务数之比。的事务数与所有事务数之比。它反映了规则的可靠程度，记为它反映了规则的可靠程度，记为support( )即即如果项集的支持度超过用户给定的最小支持度阈如果项集的支持度超过用户给定的最小支持度阈值，则称该项集为值，则称该项集为频繁项集频繁项集(或大项集或大项集)。YX IX IY YXYX YX )P()support(YXYX7 置信度置信度(confi

7、dence)规则规则X Y在事务集中的置信度是指同时包含在事务集中的置信度是指同时包含X和和Y的事的事务数与包含务数与包含X的事务数的事务数(不考虑是否包含不考虑是否包含 Y )之比。之比。它反映规则的把握程度，是一个条件概率，即它反映规则的把握程度，是一个条件概率，即support(XY)/support(X), 记为记为confidence(X Y)同时满足最小支持度阈值和最小置信度阈值的规则称为同时满足最小支持度阈值和最小置信度阈值的规则称为强规则强规则。8u 假设项目集合假设项目集合I=A,B,C,D,E，事务数据集，事务数据集D如表所示。如表所示。 请定义请定义AC, C A的关联规

8、则。的关联规则。事务数据集示例事务数据集示例TID项目项目001ACD002BCE003ABCE004B E9u 假设项目集合假设项目集合I=A,B,C,D,E，事务数据集，事务数据集D如表所示。如表所示。 请定义请定义AC, C A的关联规则。的关联规则。解：解： AC的支持度为的支持度为2/4=50%, 置信度为置信度为2/2=100%,记为记为 AC,50%,100% CA的支持度为的支持度为2/4=50%, 置信度为置信度为2/3=66.7%,记为记为 CA,50%,66.7%数据集示例数据集示例101. 一般意义上的关联规则一般意义上的关联规则v基于规则中处理变量的类别基于规则中处理

9、变量的类别 布尔型、数值型布尔型、数值型v基于规则中数据的抽象层次基于规则中数据的抽象层次 单层关联规则、多层关联规则单层关联规则、多层关联规则v基于规则中涉及数据的维数基于规则中涉及数据的维数 单维规则、多维规则单维规则、多维规则11v基于规则中处理变量的类别基于规则中处理变量的类别 布尔型、数值型布尔型、数值型布尔型考虑的是项集的存在与否，而数值型则布尔型考虑的是项集的存在与否，而数值型则是量化的关联。是量化的关联。e.g. 性别性别=“女女” 职业职业=“秘书秘书” 布尔型布尔型 性别性别=“女女” avg(收入收入)=23000 数值型数值型 12v基于规则中数据的抽象层次基于规则中数

10、据的抽象层次 单层关联规则、多层关联规则单层关联规则、多层关联规则在单层关联规则中在单层关联规则中, 所有的变量都没有考虑到现所有的变量都没有考虑到现实的数据是具有多个不同层次的。实的数据是具有多个不同层次的。在多层关联规则中在多层关联规则中,则对数据的多层性进行了充则对数据的多层性进行了充分的考虑。分的考虑。e.g. IBM LaptopHP Laser Printer Laptop Laser Printer 13v基于规则中涉及数据的维数基于规则中涉及数据的维数 单维规则、多维规则单维规则、多维规则在单维的关联规则中，只涉及到数据的一个维在单维的关联规则中，只涉及到数据的一个维 在多维的

11、关联规则中，要处理的数据会设计到多个在多维的关联规则中，要处理的数据会设计到多个维维(属性属性)。e.g. 购买购买(啤酒啤酒) 购买购买(尿布尿布) 性别性别=女女 职业职业=秘书秘书142. 带有时间性的序列关联分析带有时间性的序列关联分析为了发现序列关联规则，首先需要建立一个序为了发现序列关联规则，首先需要建立一个序列数据集，如表列数据集，如表2-2所示。所示。每一行记录与一个特定的对象相关联的一些事每一行记录与一个特定的对象相关联的一些事件在给定时刻的出现。件在给定时刻的出现。将与对象将与对象A有关的所有事件按时间戳增序排序有关的所有事件按时间戳增序排序, 就得到就得到对象对象A的一个

12、序列的一个序列(sequence)。 其中，定义其中，定义 k 序列序列就是包含就是包含k个事件的序列。个事件的序列。表表2-215对象对象时间戳时间戳事件事件A11,2,4A22,3A35B11,2B22,3,4C11,2C22,3,4C32,4,5D12D23,4D34,516设设 D 是包含一个或多个数据序列是包含一个或多个数据序列(data sequence)的数据集。所谓的的数据集。所谓的数据序列数据序列是指与单个是指与单个数据对象相关联的事件的有序列表。例如，表数据对象相关联的事件的有序列表。例如，表2-2显示的数据集包含四个数据序列显示的数据集包含四个数据序列, 对象对象A，B，

13、C，D 各一个。各一个。表表2-217序列序列 s 的的支持度支持度是包含是包含 s 的所有数据序列所占的所有数据序列所占的比例。如果序列的比例。如果序列 s 的支持度大于或等于用户给定的支持度大于或等于用户给定的最小支持度阈值的最小支持度阈值(minsup), 则称则称s是一个是一个频繁序列频繁序列给定序列数据集给定序列数据集 D 和用户指定的最小支持度和用户指定的最小支持度, 发现序列关联的任务就是找出支持度大于或等于最发现序列关联的任务就是找出支持度大于或等于最小支持度的所有序列。小支持度的所有序列。表表2-218Minsup = 50%1, 2s = 75%, 除除 D 以外以外2,

14、3 s = 75%,除除 D 以外以外2, 4 s = 75%,除除 D 以外以外234 s = 50%,除除 A,D以外以外1,22,3 s = 75%,除除 D 以外以外表表2-219对于给定的序列对于给定的序列s, 形如形如st 的表达式就称为的表达式就称为序列关联规则序列关联规则。序列关联规则序列关联规则st 的的置信度置信度是支持序列是支持序列 s 和和t 的的数据序列数与仅支持数据序列数与仅支持 s 的数据序列数之比。的数据序列数之比。例如例如, 1,22,3的置信度为的置信度为: s(1,2 2,3)/s(1,2) = 1。表表2-220根椐我们的约束框架，寻找关联规则的典型数据

15、根椐我们的约束框架，寻找关联规则的典型数据挖掘算法包含以下几部分挖掘算法包含以下几部分:1.任务任务:描述变量之间的关联关系描述变量之间的关联关系;2.结构结构:用概率表示的用概率表示的“关联规则关联规则”;3.评分函数评分函数:支持度和置信度的阈值支持度和置信度的阈值;4.搜索方法搜索方法:系统搜索系统搜索(带修剪的广度优先带修剪的广度优先);5.数据管理技术数据管理技术:多重线性扫描。多重线性扫描。211. 普通的关联规则算法普通的关联规则算法关联规则的最典型算法关联规则的最典型算法Apriori算法算法Apriori算法在关联规则领域具有很大影响力算法在关联规则领域具有很大影响力, 目前

16、目前, 几乎几乎所有高效的发现关联规则的并行数据挖掘算法都是基于所有高效的发现关联规则的并行数据挖掘算法都是基于Apriori算法的。算法的。22在具体实现时在具体实现时, Apriori算法将发现关联规则的过程分为两算法将发现关联规则的过程分为两个步骤个步骤: v第一步通过迭代检索出事务数据库中的所有频繁项集第一步通过迭代检索出事务数据库中的所有频繁项集, 即即支持度不低于用户设定的阈值的项集支持度不低于用户设定的阈值的项集; v第二步利用频繁项集构造出满足最小置信度的规则。第二步利用频繁项集构造出满足最小置信度的规则。其中其中, 挖掘出所有频繁项集是该算法的挖掘出所有频繁项集是该算法的核心

17、核心, 所得的关联所得的关联规则的总体性能主要由该步决定。规则的总体性能主要由该步决定。23L1=large 1-item sets) (Ll是指频繁是指频繁1-项集项集);for (k=2; Lk-1; k+) do begin;Ck = apriori_gen(Lk-1) (将将Lk-1进行连接操作生成候选进行连接操作生成候选 k 项集项集的的 集合集合Ck);for all transactions tD do begin;Ct=subset(Ck, t) (识别包含在事务识别包含在事务 t 中的候选集中的候选集);for all candidates c Ct do;c.count+

18、(支持度计算增值支持度计算增值);end;end;Lk = c Ck | c.count minsup;end;answer=kLk24Ck 中的每个元素需在交易数据库中进行验证来决定其是中的每个元素需在交易数据库中进行验证来决定其是否加入否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库。法要求多次扫描可能很大的交易数据库。大量的候选集、重复扫描数据库大量的候选集、重复扫描数据库, 是是Apriori算法的算法的两大缺两大缺点点。Mannila 等引入的修剪技术：基于这样一个性质等引入的修剪技术：基于这样一个性

19、质一个项集是频集当且仅当它的所有子集都是频集一个项集是频集当且仅当它的所有子集都是频集那么那么, 如果如果Ck中某个候选项集有一个中某个候选项集有一个(k-1)子集不属于子集不属于Lk-1, 则这个项集就被修剪掉不再被考虑则这个项集就被修剪掉不再被考虑, 这个修剪过程可以降低计这个修剪过程可以降低计算所有的候选集支持度的代价。算所有的候选集支持度的代价。25如图事务数据库，假设最小支持度如图事务数据库，假设最小支持度 s=50%, 求此数据求此数据库中的所有频繁项集。库中的所有频繁项集。(即各项集出现的频数要即各项集出现的频数要 2 )26第一步第一步 由数据库求得候选数据项集由数据库求得候选

20、数据项集C127第二步：根据最小支持度为第二步：根据最小支持度为50%，生成频繁，生成频繁1-项集项集L1C1L128第三步：为生成第三步：为生成L2，通过，通过L1与自己连接产生与自己连接产生 候选候选2-项集项集C2，再由最小支持度到频繁，再由最小支持度到频繁2-项集项集L2C2L229第四步：运用第四步：运用Mannila的剪枝策略从的剪枝策略从L2生成生成C3。一个项集是频集当且仅当它的所有子集都是频集一个项集是频集当且仅当它的所有子集都是频集C3剪枝后的剪枝后的C330剪枝后的剪枝后的C3L331e.g. 检验检验 B, C E 是否为强规则是否为强规则s(B,C )=2 s(B,

21、C, E)=2c( B, C E ）= s(B, C, E)/ s(B,C )=2/2=100% L3L2L132e.g. 关于早餐和篮球的关联规则挖掘关于早餐和篮球的关联规则挖掘s(打篮球打篮球)=60% s(吃早餐吃早餐)=75% s(打篮球，吃早餐打篮球，吃早餐)=40% minsup=0.4 minconf=0.6挖掘出规则挖掘出规则“(打篮球打篮球) (吃早餐吃早餐)”s=0.4 confidence=0.66可能的结论：通常打篮球的学生吃早餐可能的结论：通常打篮球的学生吃早餐而实际的情况是：而实际的情况是： s(吃早餐吃早餐)=75%，打篮球的学生吃早餐的，打篮球的学生吃早餐的概率

22、低于此概率，二者是负关联的概率低于此概率，二者是负关联的33为了消除这种规则的误导为了消除这种规则的误导, 需要在关联规则需要在关联规则XY的置信的置信度超过某个特定的度量标准时度超过某个特定的度量标准时, 定义它为有意义的。因此，定义它为有意义的。因此，引入引入Lift 值值(增益增益):Lift(XY) = P(Y|X)/P(Y)=P(XY)/P(X)*P(Y)v Lift =1, 前项和后项经验独立前项和后项经验独立;v Lift 1, 表明前后两项是正相关的表明前后两项是正相关的, 说明说明X与与Y实际同时实际同时 发生的概率大于发生的概率大于X与与Y独立时同时发生的随机概率独立时同时

23、发生的随机概率; v Lift 1, 表明前后两项是负相关的。表明前后两项是负相关的。34e.g. 已知数据库已知数据库D中有中有9个事务，即个事务，即D=9，最小，最小支持度为支持度为2，求所有的频繁项集，并由频繁项集，求所有的频繁项集，并由频繁项集产生关联规则产生关联规则3536373839由频繁项集产生强关联规则 confidence(A B)=P(B|A)=Support_count(AB)Support_count(A)基于找出的频繁项集I=I1,I2,I5可以产生的强关联规则：I2,I1 I5, confidence=2/4=50%I1,I5 I2, confidence=I2,I

24、5 I1, confidence=I1 I2,I5, confidence=I2 I1,I5, confidence=I5 I1,I2, confidence=2/2=100%2/2=100%2/6=33%2/7=29%2/2=100%如果最小置信度如果最小置信度阈值为阈值为70%,则只则只有有2，3和最后一和最后一个规则可以输出个规则可以输出，这些就是产生，这些就是产生的的强规则。强规则。40一种产生序列模式的蛮力方法是枚举所有可能的序列一种产生序列模式的蛮力方法是枚举所有可能的序列, 并并统计它们各自的支持度统计它们各自的支持度, 但是可以想象这个计算量是非常大的但是可以想象这个计算量是非

25、常大的由于先验原理对序列数据成立，即包含由于先验原理对序列数据成立，即包含 k 序列的任何数序列的任何数据序列必然包含该据序列必然包含该 k 序列的所有序列的所有(k-1)子序列，所以可以开发子序列，所以可以开发类类Apriori算法算法来进行序列摸式的发现。来进行序列摸式的发现。但与普通关联规则相比但与普通关联规则相比, 需要注意次序在序列中是重要的需要注意次序在序列中是重要的i1 i2i2 i1对应于不同的序列，必须分别产生。对应于不同的序列，必须分别产生。41k=1Fk=i|iI(i)/Nmin sup(找出所有的频繁找出所有的频繁 1 序列序列)repeatk=k+1Ck=aprior

26、i_gen(Fk-1)(产生候选产生候选 k 序列序列)for 每个数据序列每个数据序列 tT doCt = subsequence( Ck, t) (识别包含在识别包含在 t 中的所有候选中的所有候选)for 每个候选每个候选 k 序列序列 cCt do (c) =(c)+1(支持度计算增值支持度计算增值)endforendforFk=c | cCk(c)/Nmin sup(提取频繁提取频繁 k 序列序列)until Fk = answer = Fk 42序列序列Sl和序列和序列S2合并规则合并规则 合并条件合并条件：仅当从：仅当从S1中去掉第一个中去掉第一个事件事件得到的子序列与从得到的子

27、序列与从 S2中去掉最后一个事件得到的子序列中去掉最后一个事件得到的子序列(事件事件)相同相同, 合并结果合并结果：结果候选是序列：结果候选是序列Sl和序列和序列S2 的的最后一个事件最后一个事件的的 连接连接, 具体连接方法分二种：具体连接方法分二种：(l) 如果如果S2的最后两个的最后两个事件事件属于属于相同的相同的元素元素, 则则S2的最后一个的最后一个 事件在合并后的序列中是事件在合并后的序列中是S1的最后一个元素的一部分。的最后一个元素的一部分。(2)如果如果S2的最后两个事件属于的最后两个事件属于不同的元素不同的元素, 则则S2的最后一个的最后一个 事件在合并后的序列中成为连接到事

28、件在合并后的序列中成为连接到S1的的尾部的单独元素尾部的单独元素。4344123+234 =1234满足条件满足条件 212 5 +2 53 =12 53满足条件满足条件 2153+53, 4 =153 4 满足条件满足条件 1 234+345 =2345满足条件满足条件 22 53+53 4 =2 53 4满足条件满足条件 1序列合并图序列合并图45在找序列模式的过程中，要不断地检测一个给定的大序在找序列模式的过程中，要不断地检测一个给定的大序列集合是否包含于一个数据序列中。为了使这个过程尽量快列集合是否包含于一个数据序列中。为了使这个过程尽量快, 用另一种形式来替换每一个数据序列用另一种形

29、式来替换每一个数据序列:v 在转换完成的数据序列中在转换完成的数据序列中, 每条交易被其所包含的所有频繁每条交易被其所包含的所有频繁序列所取代。如果一条交易不包含任何频繁序列序列所取代。如果一条交易不包含任何频繁序列, 在转换完成在转换完成的序列中它将不被保留。的序列中它将不被保留。v 而如果一个数据序列不包含任何的频繁序列而如果一个数据序列不包含任何的频繁序列, 在转换好的数在转换好的数据库中这个序列也将不复存在。据库中这个序列也将不复存在。v 但是但是,在计算数据序列总数的时候在计算数据序列总数的时候, 它仍将被计算在内。它仍将被计算在内。最终最终, 一个数据序列被一列由频繁序列组成的集合所取代一个数据序列被一列由频繁序列组成的集合所取代46考虑实际需要考虑实际需要, 可以对模式的事件和元素都施加时限约束可以对模式的事件和元素都施加时限约束在不考虑时限约束时在不考虑时限约束时, 会得出一些事件或元素之间时间间会得出一些事件或元素之间时间间隔太长的序列模式隔太长的序列模式, 这种模式对于实际应用是没有意义的。可这种模式对于实际应用是没有意义的。可以施加如下的一些时限约束形式。以施加如下的一些时限约束形式。47v最大跨度最大跨度约束约束最大跨度最大跨度约束指定了约束指定了整个序列整个序列中所允许的事件中所允许的事件最晚和最晚和最早最早发生的发生的最大时间差最大时间差。e.g.