数据挖掘CHAPTER6挖掘大型数据库中的关联规则

第六章挖掘大型数据库中的关联规则关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。随着大量数据不停地收集和存储，许多业界人士对于从他们的数据库中挖掘关联规则越来越感兴趣。从大量商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物和贱卖分析。关联规则挖掘的一个典型例子是购物篮分析。该过程通过发现顾客放入其购物篮中不同商品（图6.1）之间联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。例如，在同一次去超级市场，如果顾客购买牛奶，他也购买面包（和什么类型的面包）的可能性有多大？通过帮助零售商有选择地经销和安排货架，这种信息可以引导销售。例如，将牛奶和面包尽可能放近一些，可以进一步刺激一次去商店同时购买这些商品。图6.1购物篮分析数据是事务的或关系的，如何由大量的数据中发现关联规则？什么样的关联规则最有趣？我们如何帮助或指导挖掘过程发现有趣的关联规则？对于关联规则挖掘，什么样的语言结构对于定义关联挖掘查询是有用的？本章我们将深入研究这些问题。6.1关联规则挖掘关联规则挖掘寻找给定数据集中项之间的有趣联系。本节简要介绍关联规则挖掘。6.1.1小节给出一个购物篮分析的例子，这是关联规则挖掘的最初形式。挖掘关联规则的基本概念在6.1.2小节给出。6.1.3小节给出一个路线图，指向可挖掘的各种不同类型关联规则。6.1.1购物篮分析：一个引发关联规则挖掘的例子假定作为AllElectronics的分店经理，你想更加了解你的顾客的购物习惯。例如，你想知道“什么商品组或集合顾客多半会在一次购物时同时购买？”为回答你的问题，你可以在你的商店顾客事务零售数据上运行购物篮分析。分析结果可以用于市场规划、广告策划、分类设计。例如，购物篮分析可以帮助经理设计不同的商店布局。一种策略是：经常一块购买的商品可以放近一些，以便进一步刺激这些商品一起销售。例如，如果顾客购买计算机也倾向于同时购买财务软件，将硬件摆放离软件陈列近一点，可能有助于增加二者的销售。另一种策略是：将硬件和软件放在商店的两端，可能诱发买这些商品的顾客一路挑选其它商品。例如，在决定购买一台很贵的计算机之后，去看软件陈列，购买财务软件，路上可能看到安全系统，可能会决定也买家庭安全系统。购物篮分析也可以帮助零售商规划什么商品降价出售。如果顾客趋向于同时购买计算机和打印机，打印机降价出售可能既促使购买打印机，又促使购买计算机。如果我们想象全域是商店中可利用的商品的集合，则每种商品有一个布尔变量，表示该商品的有无。每个篮子则可用一个布尔向量表示。可以分析布尔向量，得到反映商品频繁关联或同时购买的购买模式。这些模式可以用关联规则的形式表示。例如，购买计算机也趋向于同时购买财务管理软件可以用以下关联规则表示：softwaremanagementfinancialcomputer__[support=2%,confidence=60%](6.1)规则的支持度和置信度是两个规则兴趣度度量，已在前面4.1.4小节介绍。它们分别反映发现规则的有用性和确定性。关联规则(6.1)的支持度2%意味分析事务的2%同时购买计算机和财务管理软件。置信度60%意味购买计算机的顾客60%也购买财务管理软件。关联规则是有趣的，如果它满足最小支持度阈值和最小置信度阈值。这些阈值可以由用户或领域专家设定。6.1.2基本概念设I={i1,i2,...,im}是项的集合。设任务相关的数据D是数据库事务的集合，其中每个事务T是项的集合，使得TI。每一个事务有一个标识符，称作TID。设A是一个项集，事务T包含A当且仅当AT。关联规则是形如AB的蕴涵式，其中AI，BI，并且AB=。规则AB在事务集D中成立，具有支持度s，其中s是D中事务包含AB（即，A和B二者）的百分比。它是概率P(AB)。规则AB在事务集D中具有置信度c，如果D中包含A的事务同时也包含B的百分比是c。这是条件概率P(B|A)。即support(AB)=P(AB)(6.2)confidence(AB)=P(B|A)(6.3)同时满足最小支持度阈值(min_sup)和最小置信度阈值(min_conf)的规则称作强规则。为方便计，我们用0%和100%之间的值，而不是用0到1之间的值表示支持度和置信度。项的集合称为项集1。包含k个项的项集称为k-项集。集合{computer,financial_management_software}是一个2-项集。项集的出现频率是包含项集的事务数，简称为项集的频率、支持计数或计数。项集满足最小支持度min_sup，如果项集的出现频率大于或等于min_sup与D中事务总数的乘积。如果项集满足最小支持度，则称它为频繁项集2。频繁k-项集的集合通常记作Lk。3“如何由大型数据库挖掘关联规则？”关联规则的挖掘是一个两步的过程：1.找出所有频繁项集：根据定义，这些项集出现的频繁性至少和预定义的最小支持计数一样。2.由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和最小置信度。如果愿意，也可以使用附加的兴趣度度量。这两步中，第二步最容易。挖掘关联规则的总体性能由第一步决定。6.1.3关联规则挖掘：一个路线图购物篮分析只是关联规则挖掘的一种形式。事实上，有许多种关联规则。根据下面的标准，关联规则有多种分类方法：根据规则中所处理的值类型：如果规则考虑的关联是项的在与不在，则它是布尔关联规则。例如，上面的规则(6.1)是由购物篮分析得到的布尔关联规则。如果规则描述的是量化的项或属性之间的关联，则它是量化关联规则。在这种规则中，项或属性的量化值划分为区间。下面的规则(6.4)是量化关联规则的一个例子，其中，X是代表顾客的变量。1在数据挖掘研究界，“itemset”比“itemset”更常用。2在早期的工作中，满足最小支持度的项集称为大的。然而，该术语有时易混淆，因为它具有项集中项的个数的内涵，而不是集合出现的频率。因此，我们使用当前术语频繁。3尽管频繁已取代大的，由于历史的原因，频繁k-项集仍记作Lk。)__,()48...42,()39...30,(TVresolutionhighXbuysKKXincomeXage(6.4)注意，量化属性age和income已离散化。根据规则中涉及的数据维：如果关联规则中的项或属性每个只涉及一个维，则它是单维关联规则。注意，(6.1)式可以写作)__,(),(softwaremanagementfinancialXbuyscomputerXbuys(6.5)规则(6.1)是单维关联规则，因为它只涉及一个维buys4。如果规则涉及两个或多个维，如维buys,time_of_transaction和customer_category，则它是多维关联规则。上面的规则(6.4)是一个多维关联规则，因为它涉及三个维age,income和buys。根据规则集所涉及的抽象层：有些挖掘关联规则的方法可以在不同的抽象层发现规则。例如，假定挖掘的关联规则集包含下面规则：age(X,”30...39”)buys(X,”laptopcomputer”)(6.6)age(X,”30...39”)buys(X,”computer”)(6.7)在规则(6.6)和(6.7)中，购买的商品涉及不同的抽象层（即，”computer”在比”laptopcomputer”高的抽象层）。我们称所挖掘的规则集由多层关联规则组成。反之，如果在给定的规则集中，规则不涉及不同抽象层的项或属性，则该集合包含单层关联规则。根据关联挖掘的各种扩充：关联挖掘可以扩充到相关分析，那里，可以识别项是否相关。还可以扩充到挖掘最大模式（即，最大的频繁模式）和频繁闭项集。最大模式是频繁模式p，使得p的任何真超模式5都不是频繁的。频繁闭项集是一个频繁的、闭的项集；其中，项集c是闭的，如果不存在c的真超集c’，使得每个包含c的事务也包含c’。使用最大模式和频繁闭项集可以显著地压缩挖掘所产生的频繁项集数。本章的其余部分，你将学习上述每种关联规则的挖掘方法。6.2由事务数据库挖掘单维布尔关联规则本节，你将学习挖掘最简单形式的关联规则的方法。这种关联规则是单维、单层、布尔关联规则，如6.1.1小节所讨论的购物篮分析中的那些。我们以提供Apriori算法开始（6.2.1小节）。Apriori算法是一种找频繁项集的基本算法。由频繁项集产生强关联规则的过程在6.2.2小节给出。6.2.3小节介绍Apriori算法的一些变形，用于提高效率和可规模性。6.2.4小节提出一些挖掘关联规则方法，不象Apriori，它们不涉及“候选”频繁项集的产生。6.2.5小节介绍如何将Apriori的原则用于提高冰山查询的效率。冰山查询在购物篮分析中是常见的。6.2.1Apriori算法：使用候选项集找频繁项集Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。算法的名字基于这样的事实：算法使用频繁项集性质的先验知识，正如我们将看到的。Apriori使用一种称作逐层搜索的迭代方法，k-项集用于探索(k+1)-项集。首先，找出频繁1-项集的集合。该集合记作L1。L1用于找频繁2-项集的集合L2，而L2用于找L3，如此下去，直到不能找到频繁k-项集。找每个Lk需要一次数据库扫描。为提高频繁项集逐层产生的效率，一种称作Apriori性质的重要性质用于压缩搜索空间。我们先介绍该性质，然后用一个例子解释它的使用。Apriori性质：频繁项集的所有非空子集都必须也是频繁的。Apriori性质基于如下观察：根据定义，如果项集I不满足最小支持度阈值s，则I不是频繁的，即P(I)s。如果项A添加到I，则结果项集（即，IA）不可能比I更频繁出现。因此，IA也不是频繁的，即P(IA)s。4按照多维数据库使用的术语，我们把规则中的每个不同谓词称作维。5q是p的超模式，如果p是q的子模式；即，如果q包含p。该性质属于一种特殊的分类，称作反单调，意指如果一个集合不能通过测试，则它的所有超集也都不能通过相同的测试。称它为反单调的，因为在通不过测试的意义下，该性质是单调的。“如何将Apriori性质用于算法？”为理解这一点，我们必须看看如何用Lk-1找Lk。下面的两步过程由连接和剪枝组成。1.连接步：为找Lk，通过Lk-1与自己连接产生候选k-项集的集合。该候选项集的集合记作Ck。设l1和l2是Lk-1中的项集。记号li[j]表示li的第j项（例如，l1[k-2]表示l1的倒数第3项）。为方便计，假定事务或项集中的项按字典次序排序。执行连接Lk-1Lk-1；其中，Lk-1的元素是可连接的，如果它们前(k-2)个项相同；即，Lk-1的元素l1和l2是可连接的，如果(l1[1]=l2[1])(l1[2]=l2[2])...(l1[k-2]=l2[k-2])(l1[k-1]l2[k-1])。条件(l1[k-1]l2[k-1])是简单地保证不产生重复。连接l1和l2产生的结果项集是l1[1]l1[2]...l1[k-1]l2[k-1]。2.剪枝步：Ck是Lk的超集；即，它的成员可以是，也可以不是频繁的，但所有的频繁k-项集都包含在Ck中。扫描数据库，确定Ck中每个候选的计数，从而确定Lk（即，根据定义，计数值不小于最小支持度计数的所有候选是频繁的，从而属于Lk）。然而，Ck可能很大，这样所涉及的计算量就很大。为压缩Ck，可以用以下办法使用Apriori性质：任何非频繁的(k-1)-项集都不是可能是频繁k-项集的子集。因此，如果一个候选k-项集的(k-1)-子集不在Lk-1中，则该候选也不可能是频繁的，从而可以由Ck中删除。这种子集测试可以使用所有频繁项集的散列树快速完成。例6.1让我们看一个Apriori的具体例子。该例基于图6.2的AllElectronics的事务数据库。数据库中有9个事务，即|D|=9。Apriori假定事务中的项按字典次序存放。我们使用图6.3解