第六章 挖掘大型数据库中的关联规则

1、数据挖掘数据挖掘2u概念描述：特征化和比较；u 关联规则；关联规则；u 分类/预测；u 聚类分析；u其他的数据挖掘任务。引引 言言 关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。 从大量商业事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物和促销分析等。2引引 言言 如何从事务DB或关系DB的大量数据中挖掘出关联规则知识？ 什么样的关联规则才是最有意义的？ 如何才能使挖掘过程尽快发现有价值的关联规则知识？ 这是本章要讨论的内容。26.1 关联规则挖掘6.2 由事务数据库挖掘单维布尔关联规则6.3 由事务数据库挖掘多层关联规则6.4 由事务数据库和数据仓库挖

2、掘多维关联规则7u 掌握关联规则挖掘算法-Apriori算法。u 理解多层关联规则挖掘及其方法；u 理解多维关联规则挖掘及其方法。6.1 6.1 关联规则挖掘关联规则挖掘关联规则挖掘关联规则挖掘(Association rule mining)：关联规则挖掘的主要对象是交易型数据库，一个交易一般由交易处理时间，一组顾客购买的物品，有时也有顾客标识号组成。关联规则挖掘用以挖掘一次交易中，物品之间同时出现的规律的知识模式，以反映顾客的购买行为。更确切的说，关联规则是通过量化的数字来描述物品X的出现对物品Y的出现有多大的影响。 以零售业为例，通过对销售数据的关联分析，体育用品商店可以发现隐含在数据中

3、的规律： “购买篮球的顾客中有70%的人同时购买篮球运动服，所有交易中有40%的人同时购买篮球和篮球运动服” 等等。 关联规则挖掘关联规则挖掘 购物篮分析购物篮分析 购物篮分析是关联规则挖掘的最初形式。 如，某商店经理可能更想了解如下的购物习惯： “顾客多半会在购物时同时购买什么商品组或集合？” 为解答这个问题，可以在商店顾客事务零售数据库上进行购物篮分析。 分析的结果可用于市场规划、广告策划和分类设计。45 设商店中所有销售商品为一个集合，每个商品均为一个布尔变量，布尔变量用来表示该商品是否被(一个)顾客购买。则，每个购物篮（事务数据库）可以用一个布尔向量表示。 分析该布尔向量，得到反映商品

4、频繁关联或同时购买的购买模式。 购物篮分析购物篮分析computer = financial _ management _ softwaresupport = 2%, confidence = 60%v 关联规则的支持度(support)2% 表示：全部事务中，有2% 的交易同时购买计算机和财务管理软件。v 关联规则的置信度(confidence)60% 表示：购买计算机的顾客中，有60% 也同时购买了财务管理软件。6 购物篮分析购物篮分析 例如，在购买计算机的同时购买财务管理软件，可用如下关联规则表示：1. 1. 关联规则的基本概念？关联规则的基本概念？关联规则挖掘的基本概念关联规则挖掘的基

5、本概念1）事务数据库：）事务数据库：设I= i1，i2，im 是一个项目集合，事务数据库D= t1，t2，tn 是由一系列具有唯一标识TID的事务组成，每个事务ti（i=1，2，n）都对应I上的一个子集。示例：示例：购物记录v I是全部物品集合，如商场现有的所有商品；v D是购物清单，如顾客的购物清单；v D中的每个元组ti代表一次事务（商业行为），是一次购买物品的集合（I的一个子集）。基本概念基本概念2）支持度）支持度(support)：支持度是模式为真的任务相关的元组（或事务）所占的百分比。对于形如“ ”的关联规则，支持度定义为：其中，A、B是项目的集合。示例：示例：假定任务相关数据由Al

6、lElectronics的计算机部的事务数组成，一个支持度为30%的关联规则：意味着在计算机部的所有顾客中，有30%同时购买了计算机（A）和软件（B）。BA元组总数的元组数和包含）支持度（BABA=) ,() ,(softwareXbuyscomputerXbuys基本概念基本概念3）置信度）置信度(certainty)：每个发现的模式都有一个表示其有效性或值得信赖性的度量。对于形如“ ”的关联规则，其有效性度量为置信度，定义为：其中，A、B是项目的集合。示例：示例：假定任务相关数据由AllElectronics的计算机部购买物品的事务数组成，一个置信度为85%的关联规则：意味着买计算机（A）

7、的顾客中，有85%也同时购买了软件（B）。BA的元组数包含的元组数和包含）置信度（ABABA=) ,() ,(softwareXbuyscomputerXbuys基本概念基本概念4）强关联规则：）强关联规则： 置信度表示规则的可信度；置信度小：规则无意义支持度表示模式在事务数据库中的出现频率；支持度小：规则使用面窄同时满足用户定义的最小置信度和最小支持度阈值的关联规则，称为强关联规则（strong association rule），并被认为是有趣的。2. 2. 关联规则的分类？关联规则的分类？（1 1）基于规则中处理的变量类别）基于规则中处理的变量类别v布尔型布尔型：离散的、可枚举的、种类化

8、的如：性别=“男”= 职业=“网络工程师”v数值型数值型：含有定量的数据项如，性别=“男” = 收入=“3500”关联规则的分类：关联规则的分类：（2 2）基于规则中数据的抽象层次）基于规则中数据的抽象层次u单层关联规则单层关联规则：所有的变量都不考虑层次如：性别=“男”= 职业=“网络工程师”u多层关联规则多层关联规则：考虑变量的不同层次性如，数码相机 = 三星手机，（数码相机是三星数码相机的较高层抽象）再如，数码相机 = 手机（数码相机、手机是三星数码相机和三星手机的较高层抽象）。关联规则的分类：关联规则的分类：u多层关联规则又可以分为：v同层关联规则同层关联规则：如果一个关联规则对应的项

9、目是同一个如果一个关联规则对应的项目是同一个粒度层次，那么它是同层关联规则粒度层次，那么它是同层关联规则 如，数码相机如，数码相机 = = 手机手机。v层间关联规则层间关联规则：如果在不同的粒度层次上考虑问题，那如果在不同的粒度层次上考虑问题，那么得到的是层间关联规则。么得到的是层间关联规则。如，数码相机如，数码相机 = = 三星手机三星手机关联规则的分类：关联规则的分类：（3 3）基于规则中涉及的数据维数）基于规则中涉及的数据维数v单维关联规则单维关联规则：只涉及一个属性（维），处理单个属性（维）中的一些关系如：啤酒 = 尿布，只涉及到用户购买的物品一个维；v多维关联规则多维关联规则：处理多

10、个属性（维）上的关系如，性别“女” = 职业“秘书”，此规则涉及到两个属性（维）的关系。关联规则的分类：关联规则的分类：6.2 6.2 由事务数据库挖掘由事务数据库挖掘单维布尔关联规则单维布尔关联规则关联规则挖掘的两步过程：关联规则挖掘的两步过程：v 1）找出所有的频繁项集：）找出所有的频繁项集：这些项集出现的频繁性要满足最小支持度原则。v2）由频繁项集产生强关联规则：）由频繁项集产生强关联规则：满足最小支持度和最小置信度。v 常用方法： Apriori算法算法频繁项集频繁项集v 项的集合称为项集（itemset），项的项集称为k-项集，如集合computer, software是一个2-项集

11、。v 项集的频率：即包含项集的事务数，也称为项集的支持计数(support_count)。 Min_sup: 设定的支持率阈值 如果项集的出现频率大于或等于min_sup与D中事务总数的乘积，就称该项集满足最小支持度min_sup 。v频繁项集：满足最小支持度的项集，频繁k-项集通常记做：Lk。基本概念基本概念频繁项集：频繁项集：v频繁项集是频繁出现在数据集中的项集；v有助于发现数据中蕴含的内在规律 哪些产品经常被一起购买？-啤酒和尿布？ 买了PC之后接着都会买些什么？ 哪种DNA对这种新药敏感？v能揭示数据集内在的、重要的特性。Apriori 算法算法uApriori 算法原理：v 任何一个

12、频繁项集的子集必定是频繁项集；任何一个频繁项集的子集必定是频繁项集； 如，如果A,B是频繁项集，则A、B都是频繁项集。v 任何非频繁项集的超集都为非频繁项集任何非频繁项集的超集都为非频繁项集如，如果A、B是非频繁项集，则A,B是非频繁项集Apriori算法算法u 算法的关键步骤：v 找出频繁项集：满足最小支持度的项目集；v 方法：使用从1到k的候选集逐层递归的产生频繁项集。u由频繁项集产生关联规则。APRIORI算法过程算法过程p Apriori算法利用逐层迭代来计算数据库中的频繁项集。第i次迭代计算出所有频繁i项集(包含i个元素的项集)。每一次迭代有两个步骤：产生候选集；计算和选择候选集。p

13、 原理是：如果一个项集是频繁的，那么它的所有子集也是频繁的。p 在第一次迭代中，产生的候选集包含所有1-项集，并计算其支持度s，s大于阈值的1-项集被选为频繁1-项集。p 第二次迭代时，Apriori算法首先去除非频繁1-项集，在频繁1-项集的基础上产生候选二项集，继而结合设定的最小支持度阈值，产生频繁2-项集。如，以表6-1中的数据为例。假设smin=50%。APRIORI算法过程算法过程在第一次迭代中，所有单项集都作为候选集，产生一个候选集列表；图5-1给出第一次迭代的结果在下一步中，计算每一项的支持度，然后在smin的基础上选择频繁项集。APRIORI算法过程算法过程图图5-1 Apri

14、ori算法第一次迭代的结果算法第一次迭代的结果p 在挖掘2-项集时，因为2-项集的任何子集都是频繁项集，所以Apriori算法使用L1*L1来产生候选集。*运算通常定义为： Lk*Lk=XY 其中X,YLk,|X Y|=k+1 注: |X Y|=k+1，即X和Y合取容量为k+1p 因此，第二次迭代中的候选集C2由运算|L1|L1-1|/2所产生，其个数为：43/2=6。用该列表来扫描DB，计算每一个候选集的支持度，并与smin进行比较，产生2-项频繁集L2。图5-2给出了所有这些步骤和第二次迭代的结果。APRIORI算法过程算法过程APRIORI算法过程算法过程p 候选集C3 运用L2*L2来

15、产生，运算结果得到A,B,C,A,C,E,B,C,E，但只有B,C,E的所有子集是频繁项集，成为候选的3-项集。然后扫描DB，根据最小支持计数，挖掘出频繁3-项集，见图5-3所示:p 因为本例的L3无法产生候选的4-项集，所以算法停止迭代过程。图图5-3 Apriori算法第三次迭代的结果算法第三次迭代的结果APRIORI算法过程算法过程p 该算法不仅计算所有频繁集的支持度，也计算那些没有被删除的非频繁候选集的支持度。p所有非频繁但被算法计算支持度的候选项集的集合被称为负边界。因此，如果项集是非频繁的，但它的子集都是频繁的，那么它就在负边界之中。APRIORI算法过程算法过程36Apriori

16、算法源代码算法源代码算法：Apriori 使用根据候选生成的逐层迭代找出频繁项集输入：事务数据库D；最小支持度阈值min_sup输出：D中的频繁项集L（1） L1 = large 1-itemsets; /所有1-项目频集（2） FOR （k=2; Lk-1; k+） DO BEGIN（3） Ck=apriori-gen（Lk-1）; / Ck是k-候选集（4） FOR all transactions tD DO BEGIN（5） Ct=subset（Ck，t）; / Ct是所有t包含的候选集元素（6） FOR all candidates c Ct DO（7） c.count+;（8） E

17、ND（9） Lk=cCk |c.countminsup_count（10） END（11） L= Lk; 38示例：示例：对于前面的例子，基于事务数据库D，在假定最小支持度阈值为50%的前提下，我们得到了频繁项集2,3,5。问，由该频繁项集可以产生哪些关联规则？分析：频繁项集L=2,3,5的非空子集有2,3, 2,5, 3,5, 2,3,5。则由这些子集可以产生如下关联规则：由频繁项集产生关联规则由频繁项集产生关联规则%673/2, 325)6(%673/2, 523)5(%673/2, 532)4(%1002/2, 253)3(%673/2, 352)2(%1002/2, 532)1 (=c

18、onfidenceconfidenceconfidenceconfidenceconfidenceconfidence如果限定最小置信度阈值为如果限定最小置信度阈值为80%80%，则只有规则（，则只有规则（1 1），（），（3 3）为强关联规则。）为强关联规则。uApriori作为经典的频繁项目集生成算法，在数据挖掘中具有作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的作用。里程碑的作用。uApriori算法有两个致命的性能瓶颈算法有两个致命的性能瓶颈:1多次扫描事务数据库，需要很大的I/O负载 对每次k循环，侯选集Ck中的每个元素都必须通过扫描数据库来验证其是否加入Lk。假如有一个频繁

19、大项目集包含10个项的话，那么就至少需要扫描事务数据库10遍。2可能产生庞大的侯选集 由Lk-1产生k-侯选集Ck是指数增长的。Apriori算法的性能瓶颈如何提高Apriori算法的效率 一些算法虽然仍然遵循Apriori 属性，但是由于引入了相关技术，在一定程度上改善了Apriori算法适应性和效率。 主要的改进方法有：基于数据分割（基于数据分割（Partition）的方法）的方法：基本原理是“在一个划分中的支持度小于最小支持度的k-项集不可能是全局频繁的”。基于散列（基于散列（Hash）的方法）的方法：基本原理是“在一个hash桶内支持度小于最小支持度的k-项集不可能是全局频繁的”。基于

20、采样的方法基于采样的方法：基本原理是“通过采样技术，评估被采样的子集，并依次来估计k-项集的全局频度”。其他其他：如，动态删除没有用的事务：“不包含任何Lk的事务对未来的扫描结果不会产生影响，因而可以删除”。6.3 6.3 由事务数据库挖掘多层关联规则由事务数据库挖掘多层关联规则多层关联规则：多层关联规则：v 对许多应用，由于多维数据空间数据的稀疏性，在低层或原始层的数据项之间很难找到强关联规则。 如，IBM台式机 = Sony打印机，在两个数据项间可能很难找到强关联规则v 在较高的概念层，则较容易得到强关联规则。这种强关联规则对某些用户可能是普遍意义的，对其他用户则可能是新颖的。 如，台式机

21、 = 打印机，找到强关联规则的可能性就大多了v 因此，数据挖掘系统应当能提供一种能力，在多个抽象层多个抽象层挖掘关联规则，并容易在不同的抽象空间转换。示例示例示例：给定AllElectronics公司分店的计算机部的销售数据，如表6-2所示，对每个事务TID给出了购买的商品。示例示例图图5-4 商品的概念分层商品的概念分层示例示例u 概念分层：定义了低层概念到更一般的高层概念的映射序列。可通过对数据内的低层概念用概念分层中其高层概念进行替换，以实现对数据的概化。u 图5-4中的概念分层有4层，记做0,1,2,3：0层：根节点all（最一般的抽象概念）；1层：computer,software,

22、printer,computer accessory2层：desktop computer, laptop computer,educational software, financial management software3层：IBM desktop computer, Microsoft educational software,示例示例u 表5-2中的项对应图5-4中概念分层的最低层，即第3层，在这种原始层很难找出有趣的购买模式。如，很难找到“IBM desktop computer”和“Sony b/w printer”的强关联规则，因为很少有人同时购买它们，是的IBM deskt

23、op computer, Sony b/w printer不太可能满足最小支持度。u 然而，考虑将“ Sony b/w printer”概化到“b/w printer”，在“IBM desktop computer”和“b/w printer”之间比在“IBM desktop computer”和“Sony b/w printer”间，更可望发现强关联规则。u 类似的，在“computer”和“printer”间，则更容易发现强关联规则。多层关联规则多层关联规则u多层关联规则挖掘的度量方法仍可以沿用“支持度-置信度框架”；u但是，有两种设置支持度的策略设置支持度的策略： 对于所有层使用一致的最

24、小支持度（一致支持度一致支持度）：在每一层挖掘时，使用相同的最小支持度阈值。 在较低层使用递减的最小支持度（递减支持度递减支持度）：每个抽象层有它自己的最小支持度阈值，抽象层越低，对应的阈值越小。一致支持度一致支持度如下图，在挖掘过程中，设置一致的最小支持度阈值5%。发现，层1满足此阈值，在层2中，“2%milk”满足，而“skim milk”则不满足。说明，较低层次抽象的项不大可能像较高层次抽象的项出现得那么频繁。一致支持度一致支持度优势：优势： 使用一致的最小支持度阈值，搜索过程是简单的，且用户只需用指定一个最小支持度阈值。缺陷：缺陷： 如果最小支持度阈值设置太高，可能丢掉出现在较低抽象层

25、中有意义的关联规则； 反之，设置太低，则可能会在较高抽象层产生无兴趣的关联规则解决方法：解决方法： “递减支持度”递减支持度递减支持度如下图，在挖掘过程中，使用递减支持度。层1和层2的阈值分别设定为5%和3%，用这种方法， “Milk”，“2% Milik” 和“Skim Milk”都是频繁的。递减支持度递减支持度 对于具有递减支持度的多层关联规则挖掘，有许多可用的对于具有递减支持度的多层关联规则挖掘，有许多可用的搜索策略：搜索策略： “逐层独立逐层独立” “层交叉单项过滤层交叉单项过滤” “层交叉层交叉k-k-项集过滤项集过滤”1 1）逐层独立）逐层独立逐层独立：逐层独立： 这是完全的宽度搜

26、索，没有频繁项集的背景知识用于剪枝； 频繁项集：如果一个项集是频繁的，那么它的所有子集也是频繁的； 考虑每一个节点，不管它的父节点是否是频繁的。2 2）层交叉单项过滤）层交叉单项过滤层交叉单项过滤：层交叉单项过滤： 一个第i层的项被考察，当且仅当它在第(i-1)层的父节点是频繁的。即，由较一般的关联考察更特定的关联。 如果一个节点是频繁的，它的子女将被考察；否则，它的子孙将被剪枝。如下图所示。3 3）层交叉）层交叉k-k-项集过滤项集过滤层交叉层交叉k-项集过滤：项集过滤： 一个第i层的k-项集被考察，当且仅当它在第(i-1)层的k-项集父节点是频繁的。 如，下图中，2-项集computer,

27、 printer是频繁的，因而节点laptop computer, b/w printer, laptop computer, color printer, desktop computer, b/w printer, desktop computer, color printer被考察。6.4 6.4 由关系数据库和数据仓库挖掘多维关联规则由关系数据库和数据仓库挖掘多维关联规则单维关联规则：单维关联规则：前面所介绍的关联规则都只涉及一个谓词，如buys谓词。如在一个商场的数据库挖掘中，可挖掘出如下关联规则：其中X为代表顾客的一个变量。同样，一个多层次关联规则可为：在上述两个关联规则中仅包含一

28、个特定的谓词：buys，因此被称为单维关联规则，或维内关联规则。6.4 6.4 由关系数据库和数据仓库挖掘多维关联规则由关系数据库和数据仓库挖掘多维关联规则假定不是对事务数据库进行分析，而是对关系数据库或数据仓库中的销售和相关信息进行分析，此时的数据是以多维形式定义存储的。 如，除记录在销售事务中购买的商品外，关系数据库可能还记录着与商品有关的其他属性，如购买数量、价格、销售地址等；还可能有购物顾客的基本信息，如年龄、职业、信誉度、收入、地址等。 若将数据库的每个属性或数据仓库的每个维看作一个谓词，可挖掘得到多维关联规则多维关联规则。6.4 6.4 由关系数据库和数据仓库挖掘多维关联规则由关系数据库和数据仓库挖掘多维关联规则多维关联规则：多维关联规则：包含两个或多个维或谓词的关联规则称为多维关联规则。如上述规则中，包含三个不同的谓词（age, occupation, buys），且每个谓词只出现一次。像这样无重复谓词的多维关联规则称为维间关联规则。而对具有重复谓词的多维关联规则称为混合维关联规则，如：多维关联规则挖掘技术多维关联规则挖掘技术 由于数据库中的属性可以是符号量或数值量：符号属性：仅取有限个无序的值（