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

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

关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。随着大量数据不停地收集和存储，许多业界人士对于从他们的数据库中挖掘关联规则越来越感兴趣。从大量商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物和贱卖分析。

关联规则挖掘的一个典型例子是购物篮分析。该过程通过发现顾客放入其购物篮中不同商品（图6.1）之间联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。例如，在同一次去超级市场，如果顾客购买牛奶，他也购买面包（和什么类型的面包）的可能性有多大？通过帮助零售商有选择地经销和安排货架，这种信息可以引导销售。例如，将牛奶和面包尽可能放近一些，可以进一步刺激一次去商店同时购买这些商品。

图6.1 购物篮分析

数据是事务的或关系的，如何由大量的数据中发现关联规则？什么样的关联规则最有趣？我们如何帮助或指导挖掘过程发现有趣的关联规则？对于关联规则挖掘，什么样的语言结构对于定义关联挖掘查询是有用的？本章我们将深入研究这些问题。

6.1 关联规则挖掘

关联规则挖掘寻找给定数据集中项之间的有趣联系。本节简要介绍关联规则挖掘。6.1.1小节给出一个购物篮分析的例子，这是关联规则挖掘的最初形式。挖掘关联规则的基本概念在6.1.2小节给出。6.1.3小节给出一个路线图，指向可挖掘的各种不同类型关联规则。 6.1.1 购物篮分析：一个引发关联规则挖掘的例子

假定作为AllElectronics的分店经理，你想更加了解你的顾客的购物习惯。例如，你想知道“什么商品组或集合顾客多半会在一次购物时同时购买？”为回答你的问题，你可以在你的商店顾客事务零售数据上运行购物篮分析。分析结果可以用于市场规划、广告策划、分类设计。例如，购物篮分析可以帮助经理设计不同的商店布局。一种策略是：经常一块购买的商品可以放近一些，以便进一步刺激这些商品一起销售。例如，如果顾客购买计算机也倾向于同时购买财务软件，将硬件摆放离软件陈列近一点，可能有助于增加二者的销售。另一种策略是：将硬件和软件

放在商店的两端，可能诱发买这些商品的顾客一路挑选其它商品。例如，在决定购买一台很贵的计算机之后，去看软件陈列，购买财务软件，路上可能看到安全系统，可能会决定也买家庭安全系统。购物篮分析也可以帮助零售商规划什么商品降价出售。如果顾客趋向于同时购买计算机和打印机，打印机降价出售可能既促使购买打印机，又促使购买计算机。

如果我们想象全域是商店中可利用的商品的集合，则每种商品有一个布尔变量，表示该商品的有无。每个篮子则可用一个布尔向量表示。可以分析布尔向量，得到反映商品频繁关联或同时购买的购买模式。这些模式可以用关联规则的形式表示。例如，购买计算机也趋向于同时购买财务管理软件可以用以下关联规则表示：

computer?financial_management_software

[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是代表顾客的变量。

12

在数据挖掘研究界，“itemset”比“item set”更常用。

在早期的工作中，满足最小支持度的项集称为大的。然而，该术语有时易混淆，因为它具有项集中项的个数的内涵，而不是集合出现的频率。因此，我们使用当前术语频繁。 3

尽管频繁已取代大的，由于历史的原因，频繁k-项集仍记作Lk。

age(X,\30...39\)?income(X,\42K...48K\)?buys(X,\high_resolution_TV\) (6.4)

注意，量化属性age 和income已离散化。

? 根据规则中涉及的数据维：如果关联规则中的项或属性每个只涉及一个维，则它是单维关联规

则。注意，(6.1)式可以写作

buys(X,\computer\)?buys(X,\financial_management_software\) (6.5)

规则(6.1)是单维关联规则，因为它只涉及一个维buys4。如果规则涉及两个或多个维，如维

buys, time_of_transaction和customer_category，则它是多维关联规则。上面的规则(6.4)是一个多维关联规则，因为它涉及三个维age, income和buys。

? 根据规则集所涉及的抽象层：有些挖掘关联规则的方法可以在不同的抽象层发现规则。例如，

假定挖掘的关联规则集包含下面规则：

age(X,”30...39”) ? buys(X,”laptop computer”) (6.6)

age(X,”30...39”) ? buys(X,” computer”) (6.7)

在规则(6.6)和(6.7)中，购买的商品涉及不同的抽象层（即，”computer”在比”laptop computer”高的抽象层）。我们称所挖掘的规则集由多层关联规则组成。反之，如果在给定的规则集中，规则不涉及不同抽象层的项或属性，则该集合包含单层关联规则。

? 根据关联挖掘的各种扩充：关联挖掘可以扩充到相关分析，那里，可以识别项是否相关。还可

以扩充到挖掘最大模式（即，最大的频繁模式）和频繁闭项集。最大模式是频繁模式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.1 Apriori算法：使用候选项集找频繁项集

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。 45

按照多维数据库使用的术语，我们把规则中的每个不同谓词称作维。 q是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 - 1Lk - 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解释Apriori算法发现D中的频繁项集。

AllElectronics数据库 TID List of item_ID’s T100 I1,I2,I5 T200 I2,I4 T300 I2,I3 T400 I1,I2,I4 T500 I1,I3 T600 I2,I3 T700 I1,I3 T800 I1,I2,I3,I5 T900 I1,I2,I3 图6.2 AllElectronics某分店的事务数据

1. 在算法的第一次迭代，每个项都是候选1-项集的集合C1的成员。算法简单地扫描所有的事

务，对每个项的出现次数计数。 2. 假定最小事务支持计数为2（即，min_sup = 2/9 = 22%）。可以确定频繁1-项集的集合L1。它

由具有最小支持度的候选1-项集组成。 3. 为发现频繁2-项集的集合L2，算法使用L1L1产生候选2-项集的集合C2 。C2由(1)个2-项

26

|L|集组成。

4. 下一步，扫描D中事务，计算C2中每个候选项集的支持计数，如图6.3的第二行的中间表所

示。 5. 确定频繁2-项集的集合L2，它由具有最小支持度的C2中的候选2-项集组成。

6

L1L1等价于L1? L1，因为LkLk的定义要求两个连接的项集共享k-1=0个项。

图6.3 候选项集和频繁项集的产生，最小支持计数为2

1．连接：C3= L2L2={{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I5}}{{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I5}} =

{{I1,I2,I3},{I1,I2,I5},{I1,I3,I5},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}}

2．使用Apriori性质剪枝：频繁项集的所有子集必须是频繁的。存在候选项集，其子集不是频繁的吗？ ? {I1,I2,I3}的2-项子集是{I1,I2}，{I1,I3}和{I2,I3}。{I1,I2,I3}的所有2-项子集都是L2的元素。因此，保留{I1,I2,I3}在C3中。 ? {I1,I2,I5}的2-项子集是{I1,I2}，{I1,I5}和{I2,I5}。{I1,I2,I5}的所有2-项子集都是L2的元素。因此，保留{I1,I2,I5}在C3中。 ? {I1,I3,I5}的2-项子集是{I1,I3}，{I1,I5}和{I3,I5}。{I3,I5}不是L2的元素，因而不是频繁的。这样，由C3中删除{I1,I3,I5}。 ? {I2,I3,I4}的2-项子集是{I2,I3}，{I2,I4}和{I3,I4}。{I3,I4}不是L2的元素，因而不是频繁的。这样，由C3中删除{I2,I3,I4}。 ? {I2,I3,I5}的2-项子集是{I2,I3}，{I2,I5}和{I3,I5}。{I3,I5}不是L2的元素，因而不是频繁的。这样，由C3中删除{I2,I3,I5}。 ? {I2,I4,I5}的2-项子集是{I2,I4}，{I2,I5}和{I4,I5}。{I4,I5}不是L2的元素，因而不是频繁的。这样，由C3中删除{I2,I3,I5}。 3．这样，剪枝后C3 = {{I1,I2,I3},{I1,I2,I5}}。

图6.4 使用Apriori性质，由L2产生候选3-项集C3

6. 候选3-项集的集合C3的产生详细地列在图6.4中。首先，令C3 = L2L2 = {{I1,I2,I3},

{I1,I2,I5}, {I1,I3,I5}, {I2,I3,I4}, {I2,I3,I5}, {I2,I4,I5}}。根据Apriori性质，频繁项集的所有子集必须是频繁的，我们可以确定后4个候选不可能是频繁的。因此，我们把它们由C3删除，这

样，在此后扫描D确定L3时就不必再求它们的计数值。注意，Apriori算法使用逐层搜索技术，给定k-项集，我们只需要检查它们的(k-1)-子集是否频繁。

7. 扫描D中事务，以确定L3，它由具有最小支持度的C3中的候选3-项集组成（图6.3）。 8. 算法使用L3L3产生候选4-项集的集合C4。尽管连接产生结果{{I1,I2,I3,I5}}，这个项集被剪

去，因为它的子集{I1,I3,I5}不是频繁的。这样，C4 = ?，因此算法终止，找出了所有的频繁项集。? 图6.5给出Apriori算法和它的相关过程的伪代码。Apriori的第1步找出频繁1-项集的集合L1。在2-10步，Lk - 1用于产生候选C k，以找出L k。Apriori_gen过程产生候选，然后使用Apriori性质删除那些具有非频繁子集的候选（步骤3）。该过程在下面描述。一旦产生了所有的候选，就扫描数据库（步骤4）。对于每个事务，使用subset函数找出事务中是候选的所有子集（步骤5），并对每个这样的候选累加计数（步骤6和7）。最后，所有满足最小支持度的候选形成频繁项集L。然后，调用一个过程，由频繁项集产生关联规则。该过程在6.2.2小节介绍。 算法6.2.1 (Apriori) 使用逐层迭代找出频繁项集 输入：事务数据库D；最小支持度阈值。 输出：D中的频繁项集L。

方法：

1) L1 = find_frequent_1_itemsets(D); 2) for (k = 2; Lk-1 ? ?; k++) {

3) Ck = aproiri_gen(Lk-1,min_sup);

4) for each transaction t?D{ //scan D for count 5) Ct = subset(Ck,t); //get subsets of t that are candidates 6) for each candidate c?Ct 7) c.count++; 8) }

9) Lk={c?Ck | c.count ? min_sup} 10) }

11) return L = ?kLk；

procedure apriori_gen(Lk-1: frequent (k-1)-itemset; min_sup: support) 1) for each itemset l1?Lk-1 2) for each itemset l2?Lk-1 3) if (l1[1]=l2[1])?...?(l1[k-2]=l2[k-2])?(l1[k-1]

procedure has_infrequent_subset(c:candidate k-itemset; L k-1:frequent (k-1)-itemset) // use priori knowledge

1) for each (k-1)-subset s of c 2) if c?Lk-1 then 3) return TRUE; 4) return FALSE;

图6.5 对于布尔关联规则发现频繁项集的Apriori算法

如上所述，Apriori_gen做两个动作：连接和剪枝。在连接部分，Lk - 1与L k - 1连接产生可能的候选（步骤1-4）。剪枝部分（步骤5-7）使用Apriori性质删除具有非频繁子集的候选。非频繁子集的测试在过程has_infrequent_subset中。 6.2.2 由频繁项集产生关联规则

一旦由数据库D中的事务找出频繁项集，由它们产生强关联规则是直接了当的（强关联规则满足最小支持度和最小置信度）。对于置信度，可以用下式，其中条件概率用项集支持度计数表示。

support_count(A?B)confidence(A?B)?P(A|B)? (6.8)

support_count(A)其中，support_count(A?B)是包含项集A?B的事务数，support_count(A)是包含项集A的事务数。根据该式，关联规则可以产生如下：

? 对于每个频繁项集l，产生l的所有非空子集。 ? 对于l的每个非空子集s，如果

support_count(l)?min_conf，则输出规则“s ? (l-s)”。其

support_count(s)中，min_conf是最小置信度阈值。

由于规则由频繁项集产生，每个规则都自动满足最小支持度。频繁项集连同它们的支持度预先存放在hash表中，使得它们可以快速被访问。

例6.2 让我们试一个例子，它基于图6.2中 AllElectronics事务数据库。假定数据包含频繁项集l = {I1, I2, I5}，可以由l产生哪些关联规则？l的非空子集有{I1,I2}, {I1,I5}, {I2,I5}, {I1}, {I2}和{I5}。结果关联规则如下，每个都列出置信度。

I1?I2 ? I5, I1?I5 ? I2, I2?I5 ? I1, I1 ? I2?I5, I2 ? I1?I5, I5 ? I1?I2,

confidence = 2/4 = 50% confidence = 2/2 = 100% confidence = 2/2 = 100% confidence = 2/6 = 33% confidence = 2/7 = 29% confidence = 2/2 = 100%

如果最小置信度阈值为70%，则只有2、3和最后一个规则可以输出，因为只有这些是强的。? 6.2.3 提高Apriori的有效性

“怎样能够提高Apriori的有效性？”已经提出了许多Apriori算法的变形，旨在提高原算法的效率。其中一些变形列举如下。

图6.6 候选2-项集的散列表H2：该散列表在由C1确定L1时通过扫描图5.2的事

务数据库产生。如果最小支持度为3，在桶0, 1，3和4中的项集不可能是频繁的，因而它们不包含在C2中

基于散列的技术（散列项集计数）：一种基于散列的技术可以用于压缩候选k-项集Ck (k >1)。例如，当扫描数据库中每个事务，由C1中的候选1-项集产生频繁1-项集L1时，我们可以对每个事务产生所有的2-项集，将它们散列（即，映射）到散列表结构的不同桶中，并增加对应的桶计数

（图6.6）。在散列表中对应的桶计数低于支持度阈值的2-项集不可能是频繁2-项集，因而应当由候选项集中删除。这种基于散列的技术可以大大压缩要考察的k-项集（特别是当k = 2时）。 事务压缩（压缩进一步迭代扫描的事务数）：不包含任何k-项集的事务不可能包含任何(k+1)-项集。这样，这种事务在其后的考虑时，可以加上标记或删除，因为为产生j-项集(j > k)，扫描数据库时不再需要它们。

划分（为找候选项集划分数据）：可以使用划分技术，它只需要两次数据库扫描，以挖掘频繁项集（图6.7）。它包含两遍。在第I遍，算法将D中的事务划分成n个非重叠的部分。如果D中事务的最小支持度阈值为min_sup，则每个部分的最小支持度计数为min_sup?该部分中事务数。对每一部分，找出该部分内的频繁项集。这些称作局部频繁项集。该过程使用一种特殊的数据结构，对于每个项集，记录包含项集中项的事务的TID。这使得对于k = 1,2,..，找出所有的局部频繁k-项集只需要扫描一次数据库。

局部频繁项集可能不是整个数据库D的频繁项集。D的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。这样，所有的局部频繁项集作为D的候选项集。所有部分的频繁项集的集合形成D的全局候选项集。在第II遍，第二次扫描D，评估每个候选的实际支持度，以确定全局频繁项集。每一部分的大小和划分的数目这样确定，使得每一部分能够放入内存，这样每遍只需要读一次。

图6.7 通过划分挖掘

选样（在给定数据的一个子集挖掘）：选样方法的基本思想是：选取给定数据库D的随机样本S，然后，在S而不是在D中搜索频繁项集。用这种方法，我们牺牲了一些精度换取了有效性。样本S的大小这样选取，使得可以在内存搜索S中频繁项集；这样，总共只需要扫描一次S中的事务。由于我们搜索S 中而不是D中的频繁项集，我们可能丢失一些全局频繁项集。为减少这种可能性，我们使用比最小支持度低的支持度阈值来找出局部于S的频繁项集（记作LS）。然后，数据库的其余部分用于计算LS中每个项集的实际频繁度。有一种机制可以用来确定是否所有的频繁项集都包含在LS中。如果LS实际包含了D中的所有频繁项集，只需要扫描一次D。否则，可以做第二次扫描，以找出在第一次扫描时遗漏的频繁项集。当效率最为重要时，如计算密集的应用必须在不同的数据上运行时，选样方法特别合适。

动态项集计数（在扫描的不同点添加候选项集）：动态项集计数技术将数据库划分为标记开始点的块。不象Apriori仅在每次完整的数据库扫描之前确定新的候选，在这种变形中，可以在任何开始点添加新的候选项集。该技术动态地评估已被计数的所有项集的支持度，如果一个项集的所有子集已被确定为频繁的，则添加它作为新的候选。结果算法需要的数据库扫描比Apriori少。 其它变形涉及多层和多维关联规则挖掘，在本章的其余部分讨论。涉及空间数据、时间序列数据和多媒体数据的关联挖掘在第9章讨论。 6.2.4 不产生候选挖掘频繁项集

正如我们已经看到的，在许多情况下，Apriori的候选产生-检查方法大幅度压缩了候选项集的大小，并导致很好的性能。然而，它有两种开销可能并非微不足道的。

?

它可能需要产生大量候选项集。例如，如果有104个频繁1-项集，则Apriori算法需要产生多达107个候选2-项集，累计并检查它们的频繁性。此外，为发现长度为100的频繁模式，如{a1 ,..., a100}，它必须产生多达2100 ? 1030个候选。

它可能需要重复地扫描数据库，通过模式匹配检查一个很大的候选集合。对于挖掘长模式尤其如此。

?

“可以设计一种方法，挖掘全部频繁项集，而不产生候选吗？”一种有趣的方法称作频繁模式增长，或简单地，FP-增长，它采取如下分治策略：将提供频繁项集的数据库压缩到一棵频繁模式树（或FP-树），但仍保留项集关联信息；然后，将这种压缩后的数据库分成一组条件数据库（一种特殊类型的投影数据库），每个关联一个频繁项，并分别挖掘每个数据库。让我们看一个例子。

例6.3 使用频繁模式增长方法，我们重新考察例6.1中图6.2事务数据库D的挖掘。

数据库的第一次扫描与Apriori相同，它导出频繁项（1-项集）的集合，并得到它们的支持度计数（频繁性）。设最小支持度计数为2。频繁项的集合按支持度计数的递减序排序。结果集或表记作L。这样，我们有L = [I2:7, I1:6, I3:6, I4:2, I5:2]。

然后，FP-树构造如下：首先，创建树的根结点，用“null”标记。二次扫描数据库D。每个事务中的项按L中的次序处理（即，根据递减支持度计数排序）并对每个事务创建一个分枝。例如，第一个事务“T100: I1, I2, I5”按L的次序包含三个项{ I2, I1, I5}，导致构造树的第一个分枝<(I2:1), (I1:1), (I5:1)>。该分枝具有三个结点，其中，I2作为根的子女链接，I1链接到I2，I5链接到I1。第二个事务T200按L的次序包含项I2和I4，它导致一个分枝，其中，I2链接到根，I4链接到I2。然而，该分枝应当与T100已存在的路径共享前缀。这样，我们将结点I2的计数增加1，并创建一个新结点(I4:1)，它作为(I2:2)的子女链接。一般地，当为一个事务考虑增加分枝时，沿共同前缀上的每个结点的计数增加1，为随在前缀之后的项创建结点并链接。

为方便树遍历，创建一个项头表，使得每个项通过一个结点链指向它在树中的出现。扫描所有的事务之后得到的树展示在图6.8中，附上相关的结点链。这样，数据库频繁模式的挖掘问题就转换成挖掘FP-树问题。

图6.8 存放压缩的频繁模式信息的FP-树

FP-树挖掘处理如下。由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基（一个“子数据库”， 由FP-树中与后缀模式一起出现的前缀路径集组成）。然后，构造它的（条件）FP-树，并递归地在该树上进行挖掘。模式增长通过后缀模式与由条件FP-树产生的频繁模式连接实现。

FP-树的挖掘总结在表6.1中，细节如下。让我们首先考虑I5，它是L中的最后一个项，而不是第一个。其原因随着我们解释FP-树挖掘过程就会清楚。I5出现在图6.8 的FP-树的两个分枝。（I5的出现容易通过沿它的结点链找到。）这些路径由分枝<(I2 I1 I5:1)>和<(I2 I1 I3 I5:1)>形成。这样，考虑I5为后缀，它的两个对应前缀路径是<(I2 I1:1)>和<(I2 I1 I3:1)>，它们形成I5的条件模式基。它的条件FP-树只包含单个路径<(I2:2 I1:2)>；不包含I3，因为它的支持度计数为1，小于最小支持度计数。该单个路径产生频繁模式的所有组合：I2 I5:2, I1 I5:2, I2 I1 I5:2。

表6.1 通过创建条件（子）模式基挖掘FP-树 item I5 I4 I3 I1

条件模式基

{(I2 I1:1), (I2 I1 I3:1)) {(I2 I1:1), (I2:1)}

{(I2 I1:2), (I2:2), (I1:2)} {(I2:4)}

条件FP-树

,

产生的频繁模式

I2 I5:2, I1 I5:2, I2 I1 I5:2 I2 I4:2

I2 I3:4, I1 I3:4, I2 I1 I3:2 I2 I1:4

对于I4，它的两个前缀形成条件模式基{(I2 I1:1), (I2:1)，产生一个单结点的条件FP-树，并导出一个频繁模式I2 I4:2。注意，尽管I5跟在第一个分枝中的I4之后，也没有必要在此分析中包含I5，因为涉及I5的频繁模式在I5的考察时已经分析过。这就是我们为什么由后面，而不是由前面开始处理的原因。

与以上分析类似，I3的条件模式基是{(I2 I1:2), (I2:2), (I1:2)}。它的条件FP-树有两个分枝和，如图6.9所示，它产生模式集：{I2 I3:4, I1 I3:2, I2 I1 I3:2}。最后，I1的条件模式基是{(I2,4)}，它的FP-树只包含一个结点，产生一个频繁模式I2 I1:4。挖掘过程总结在图6.10。?

图6.9 具有条件结点I3的条件FP-树

算法：FP-增长。使用FP-树，通过模式段增长，挖掘频繁模式。 输入：事务数据库D；最小支持度阈值min_sup。 输出：频繁模式的完全集。 方法：

1．按以下步骤构造FP-树：

(a) 扫描事务数据库D一次。收集频繁项的集合F和它们的支持度。对F按支持度

降序排序，结果为频繁项表L。

(b) 创建FP-树的根结点，以“null”标记它。对于D中每个事务Trans，执行：

选择Trans中的频繁项，并按L中的次序排序。设排序后的频繁项表为[p | P]，其中，p是第一个元素，而P是剩余元素的表。调用insert_tree([p | P], T)。该过程执行情况如下。如果T有子女N使得N.item-name = p.item-name，则N的计数增加1；否则创建一个新结点N，将其计数设置为1，链接到它的父结点T，并且通过结点链结构将其链接到具有相同item-name的结点。如果P非空，递归地调用insert_tree(P, N)。 2．FP-树的挖掘通过调用FP_growth(FP_tree, null)实现。该过程实现如下： procedure FP_growth(Tree, ?) (1) if Tree 含单个路径P then

(2) for 路径P中结点的每个组合（记作?） (3) 产生模式? ? ?，其支持度support = ?中结点的最小支持度； (4) else for each a i 在Tree的头部 {

(5) 产生一个模式? = a i ? ?，其支持度support = a i .support； (6) 构造?的条件模式基，然后构造?的条件FP-树Tree?； (7) if Tree? ? ? then (8) 调用 FP_growth (Tree?, ?)；}

图6.10 不产生候选，发现频繁项集的FP-增长算法

FP-增长方法将发现长频繁模式的问题转换成递归地发现一些短模式，然后与后缀连接。它使用最不频繁的项作后缀，提供了好的选择性。该方法大大降低了搜索开销。

当数据库很大时，构造基于内存的FP-树是不现实的。一种有趣的替换是首先将数据库划分成投影数据库的集合，然后在每个投影数据库上构造FP-树并挖掘它。该过程可以递归地用于投影数据库，如果它的FP-树还不能放进内存。

对FP-树方法的性能研究表明：对于挖掘长的和短的频繁模式，它都是有效的和可规模化的，并且大约比Apriori算法快一个数量级。它也比树-投影算法快。树-投影算法递归地将数据库投影为投影数据库树。 6.2.5 冰山查询

Apriori算法可以用来提高回答冰山查询的效率。冰山查询在数据挖掘中经常用，特别是对购物篮分析。冰山查询在一个属性或属性集上计算一个聚集函数，以找出大于某个指定阈值的聚集值。给定关系R，它具有属性a_1, a_2, ... , a_n和b，一个聚集函数agg_f，冰山查询形如

select R.a_1, R.a_2, ... ,R.a_n, agg_f(R.b) from relation R

group by R.a_1, R.a_2, ..., R.a_n having agg_f(R.b) >= threshold

给定大量输入数据元组，满足having子句中的阈值的输出元组数量相对很少。输出结果看作“冰山顶”，而“冰山”是输入数据集。

例6.4 一个冰山查询：假定给定销售数据，你想产生这样的一个顾客-商品对的列表，这些顾客购买商品的数量达到3件或更多。这可以用下面的冰山查询表示

P.cust_ID, P.Item_ID,SUM(P.qty) select

Purchases P from

group by P.cust_ID, Pitem_ID having SUM(P.qty) >=3 ? “如何回答例6.4的查询？”你可能会问。一个常用的策略是使用散列或排序，对所有顾客-商品分组，计算聚集函数SUM的值，然后删除被给定的顾客购买的商品数量少于3的那些。相对于处理的元组总数，满足该条件的元组多半很少，为改进性能留下了空间。我们可以使用Apriori性质的变形，裁减需要考虑的顾客-商品对。即，不是考查每个顾客购买的每种商品的数量，我们可以

?

产生cust_list，一个总共购买3件或更多商品的顾客表。例如 select from group by having

P.cust_ID Purchases P P.cust_ID

SUM(P.qty) >= 3

?

产生item_list，被顾客购买的、数量为3或更多的商品表。例如 select from group by having

P. item_ID Purchases P P.item_ID

SUM(P.qty) >= 3

由先验知识，我们可以删除许多被散列/排序方法产生的顾客-商品对：仅对cust_list中的顾客和在item_list中的商品产生候选顾客-商品对。对每个这样的对，维持一个计数。尽管该方法通过预先裁减许多对或分组提高了性能，所产生的顾客-商品对数量可能依然很大，不能放进内存。可以将散列和选样策略集成到该过程，帮助提高该查询回答技术的总体性能。

6.3 由事务数据库挖掘多层关联规则

本节，你将学习挖掘多层关联规则的方法。多层关联规则是这样一些规则，它们涉及多个抽象层中的项。本节还讨论检查冗余多层规则的方法。 6.3.1 多层关联规则

对于许多应用，由于多维数据空间数据的稀疏性，在低层或原始层的数据项之间很难找出强关联规则。在较高的概念层发现的强关联规则可能提供普遍意义的知识。然而，对一个用户代表普遍意义的知识，对另一个用户可能是新颖的。这样，数据挖掘系统应当提供一种能力，在多个抽象层挖掘关联规则，并容易在不同的抽象空间转换。

让我们考察下面的例子。 例6.5 假定给定表6.2事务数据的任务相关数据集，它是AllElectronics分店的计算机部的销售数据，对每个事务TID给出了购买的商品。商品的概念分层在图6.11给出。概念分层定义了由低层概念到高层更一般的概念的映射序列。可以通过将数据内的低层概念用概念分层中的其高层概念（祖先）替换，对数据进行泛化7。图6.11的概念分层有4层，记作0, 1, 2和3层。为方便计，概念分层中的层自顶向下编号，根结点all（最一般的抽象概念）为第0层。因此，第1层包括computer, software, printer和computer accessory，第2层包括desktop computer, laptop computer, education software, financial management software, ...，而第3层包括IBM desktop computer,..., Microsoft education software，等等。第3层是该分层结构的最特定的抽象层。概念分层可以由熟悉数据的用户指定，也可以在数据中蕴涵存在。

表6.2 任务相关数据D TID T1 T2 T3 T4 T5 ... 购买的商品 IBM desktop computer, Sony b/w printer Microsoft educationsoftware, Microsoft finacial management software Logitech mouse computer accessory, Ergo-way wrist pad computer accessory IBM desktop computer, Microsoft finacial management software IBM desktop computer .....

图6.11 AllElectronics计算机商品的概念分层

表6.2中的项在图6.11概念分层的最低层。在这种原始层很难找出有趣的购买模式。例如，如果“IBM desktop computer”和“Sony b/w (黑白) printer”每个都在很少一部分事务中出现，则可能很难找到涉及它们的强关联规则。很少人同时购买它们，使得“{ IBM desktop computer, Sony b/w printer }”不太可能满足最小支持度。然而，考虑将“Sony b/w printer”泛化到“b/w printer”。在“IBM desktop computer”和“b/w printer”之间比在“IBM desktop computer”和“Sony b/w printer” 可望更容易发现强关联。类似地，许多人同时购买“computer”和“printer”，而不是同时购买特定的“IBM desktop computer”和“Sony b/w printer”。换句话说，包含更一般项的项集，如“{ IBM desktop computer, b/w printer }”和“{ computer, printer }”，比仅包含原始层数据 7

概念分层已在第2、4章详细介绍。为了使得本书的没章尽可能自包含，我们在此再次给出它的定义。泛化在第5章已介绍。

的项集，如“{ IBM desktop computer, Sony b/w printer }”，更可能满足最小支持度。因此，在多个概念层的项之间找有趣的关联比仅在原始层数据之间更容易找。?

由具有概念分层的关联规则挖掘产生的规则称为多层关联规则，因为它们考虑多个概念层。 6.3.2 挖掘多层关联规则的方法

“我们如何使用概念分层有效地挖掘多层关联规则？”让我们看一些基于支持度-置信度框架的方法。一般地，可以采用自顶向下策略，由概念层1开始向下，到较低的更特定的概念层，在每个概念层累加计数计算频繁项集，直到不能再找到频繁项集。即，一旦找出概念层1的所有频繁项集，就开始在第2层找频繁项集，如此下去。对于每一层，可以使用发现频繁项集的任何算法，如Apriori或它的变形。这种方法有许多变形，介绍如下，并用图6.12到图6.16解释。图中矩形指出项或项集已被考察，而粗边框的矩形指出已考察的项或项集是频繁的。

?

对于所有层使用一致的支持度（称作一致支持度）：在每一层挖掘时，使用相同的最小支持度阈值。例如，在图6.12中，整个使用最小支持度阈值5%（例如，对于由“computer”到“laptop computer”）。“ computer”和“laptop computer”都是频繁的，但“desktop computer”不是。

图6.12 具有一致支持度的多层挖掘

使用一致的最小支持度阈值时，搜索过程是简单的，并且用户也只需要指定一个最小支持度阈值。根据祖先是其后代的超集的知识，可以采用优化策略：搜索时避免考察这样的项集，它包含其祖先不具有最小支持度的项。

然而，一致支持度方法有一些困难。较低层次抽象的项不大可能象较高层次抽象的项出现得那么频繁。如果最小支持度阈值设置太高，可能丢掉出现在较低抽象层中有意义的关联规则。如果阈值设置太低，可能会产生出现在较高抽象层的无兴趣的关联规则。这导致了下面的方法。

?

在较低层使用递减的支持度（称作递减支持度）：每个抽象层有它自己的最小支持度阈值。抽象层越低，对应的阈值越小。例如，在图6.13，层1和层2的最小支持度阈值分别为5%和3%。用这种方法，“computer”、“laptop computer”和“desktop computer”都是频繁的。

图6.13 具有递减支持度的多层挖掘

对于具有递减支持度的多层关联规则挖掘，有许多可用的搜索策略，包括：

?

逐层独立：这是完全的宽度搜索，没有频繁项集的背景知识用于剪枝。考察每一个结点，不管它的父结点是否是频繁的。

层交叉用单项过滤：一个第i层的项被考察，当且仅当它在第(i-1)层的父结点是频繁的。换一句话说，我们由较一般的关联考察更特定的关联。如果一个结点是频繁的，它的子女将被考

?

察；否则，它的子孙将由搜索中剪枝。例如，在图6.14中，“computer”的后代结点（即，“laptop computer”和“desktop computer”）将不被考察，因为“computer”不是频繁的。

图6.14 具有递减支持度的多层挖掘，使用层交叉用单项过滤

?

层交叉用k-项集过滤：一个第i层的k-项集被考察，当且仅当它在第(i-1)层的对应父结点k-项集是频繁的。例如，在图6.15中，2-项集“{computer, printer}”是频繁的，因而结点“{laptop computer, b/w printer}”、“ {laptop computer, color printer}”、“ {desktop computer, b/w printer}”和“{desktop computer, color printer}”被考察。

图6.15 具有递减支持度的多层挖掘，使用层交叉用k-项集过滤，其中k=2

“如何比较这些方法？”逐层独立策略的条件很松，可能导致在低层考察大量非频繁的项，找出一些不太重要的关联。例如，如果“computer furniture”很少购买，考察特定的“computer chair”是否与“laptop computer”关联没什么意思。然而，如果“computer accessories”经常出售，考察“laptop”与“mouse”之间是否存在关联购买模式可能是有意义的。

层交叉用k-项集过滤策略允许系统仅考察频繁k-项集的子女。这一限制可能太强，通常没有多少k-项集组合后仍是频繁的（特别是当k > 2时）。因此，有些有价值的模式可能被该方法过滤掉。

层交叉用单项过滤策略是上两个极端的折衷。然而，这种方法也可能丢失低层项之间的关联；根据递减的最小支持度，这些项是频繁的，但它们的祖先不满足最小支持度（由于每层的支持度阈值可能不同）。例如，如果根据第i层的最小支持度阈值，“color monitor”在第i层是频繁的，但是它在(i-1)层的父结点“monitor”，根据第(i-1)层的最小支持度阈值，不是频繁的，则频繁的关联“desktop computer ? color monitor”将丢失。

层交叉单项过滤策略有一个修改版本，称作受控的层交叉单项过滤策略。可以设置一个称作层传递阈值的阈值，用于向较低层“传递”相对频繁的项（称作子频繁项）。换句话说，如果满足层传递阈值，则该方法允许考查不满足最小支持度阈值项的子女。每个概念层可以有它自己的层传递阈值。通常，对于一个给定层，层传递阈值设置为下一层的最小支持度阈值和给定层的最小支持度阈值之间的一个值。用户可以在较高层选择“下滑”或降低层传递阈值，使得子频繁项的后代在较低层被考察。降低层传递阈值到最低层的最小支持度阈值将使得项的所有后代被考察。例如，在图6.16中，设置层1的层传递阈值(level_passage_sup)为8%，使得第2层的“laptop computer”和“desktop computer”被考察，并发现是频繁的，尽管它们的父结点“computer”不是频繁的。通过增加这种机制，用户对进一步控制多概念层上的挖掘过程有了更多的灵活性，同时减少无意义关联的考察和产生。

图6.16 多层挖掘，受控的层交叉单项过滤

迄今为止，我们的讨论集中在发现这样的频繁项集，它的所有项都属于同一概念层。这可能导致形如“computer ? printer”（其中，”computer”和”printer”都在概念层1）和“desktop computer ? b/w printer”（其中，”desktop computer”和”b/w printer”都在给定概念层的第2层）的规则。假定我们想要发现跨越概念层边界的规则，如“computer ? b/w printer”，规则中的项不要求属于同一概念层。这些规则称作交叉层关联规则。

“如何挖掘交叉层关联规则？”如果挖掘由层i到层j的关联，其中层j比层i更特定（即，在较低的抽象层），则应当使用层j的最小支持度阈值，使得层j的项可以包含在分析中。 6.3.3 检查冗余的多层关联规则

概念分层在数据挖掘中是有用的，因为它们允许不同的抽象层的知识发现，如多层关联规则。然而，当挖掘多层关联规则时，由于项之间的“祖先”关系，有些发现的规则将是冗余的。例如，考虑下面的规则，其中，根据图6.11的概念分层，”desktop computer”是”IBM desktop computer”的祖先。

desktop computer ? b/w printer, [support=8%, confidence=70%] (6.9) IBM desktop computer ? b/w printer, [support=2%, confidence=72%] (6.10)

“如果挖掘出规则6.9和6.10，那么后一个规则是有用的吗？”你可能怀疑“它真的提供新颖的信息吗？”如果后一个具有较小一般性的规则不提供新的信息，应当删除它。让我们看看如何来确定。规则R1是规则R2的祖先，如果将R2中的项用它在概念分层中的祖先替换，能够得到R1。例如，规则(6.9)是规则(6.10)的祖先，因为” desktop computer”是”IBM desktop computer”的祖先。根据这个定义，一个规则被认为是冗余的，如果根据规则的祖先，它的支持度和置信度都接近于“期望”值。作为解释，假定规则(6.9)具有70%置信度，8%支持度，并且大约四分之一的”desktop computer”销售是”IBM desktop computer”。可以期望规则(6.10)具有大约70%的置信度（由于所有的”IBM desktop computer”样本也是” desktop computer”样本）和2%（即，8%?1/4）的支持度。如果确实是这种情况，规则(6.10)不是有趣的，因为它不提供附加的信息，并且它的一般性不如规则(6.9)。

6.4 由数据库和数据仓库挖掘多维关联规则

本节，你将学习挖掘多维关联规则的方法。多维关联规则是涉及多个属性或谓词的规则（例如，关于顾客的buys和顾客的age的规则）。这些方法可以根据他们对量化属性的处理组织。 6.4.1 多维关联规则

到本章这里，我们研究了蕴涵单个谓词，即谓词buys的关联规则。例如，在挖掘AllElectronics数据库时，我们可能发现布尔关联规则“IBM desktop computer ? Sony b/w printer”，它也可以写成

buys(X,”IBM desktop computer”) ? buys(X,”Sony b/w printer”) (6.11)

其中，X是变量，代表在AllElectronics购物的顾客。沿用多维数据库使用的术语，我们把每个不同的谓词称作维。这样，我们称规则(6.11)为单维或维内关联规则，因为它们包含单个不同谓词

（即，buys）的多次出现（即，谓词在规则中出现多次）。正如我们在本章的前几节看到的，这种规则通常由事务数据挖掘。

然而，假定不是使用事务数据库，销售和相关数据存放在关系数据库或数据仓库中。根据定义，这种存储是多维的。例如，除记录购买的商品之外，关系数据库可能记录与商品有关的其它属性，如购买数量，或价格，或销售分店的地址。另外，关于购物顾客的信息，如顾客的年龄、职业、信誉度、收入和地址等也可能存储。将数据库的每个属性或数据仓库的每个维看作一个谓词，这样就能挖掘多维关联规则，如

age(X,\20...29\)?occupation(X,\student\)?buys(X,\laptop\) (6.12)

涉及两个或多个维或谓词的关联规则称为多维关联规则。规则(6.12)包含三个谓词（age, occupation和buys），每个在规则中仅出现一次。因此，我们称它具有不重复谓词。具有不重复谓词的关联规则称作维间关联规则。我们也对挖掘具有重复谓词的关联规则感兴趣。这种规则包含某些谓词的多次出现，称作混合维关联规则。这种规则的一个例子是规则(6.13)，其中谓词buys是重复的。

age(X, “20...29”) ? buys(X, “laptop”) ? buys(X, “b/w printer”) (6.13)

注意，数据库属性可能是分类的或量化的。分类属性具有有限个不同值，值之间无序（例如，occupation, brand, color）。分类属性也称标称属性，因为它们的值是“事物的名字”。量化属性是数值的，并在值之间具有一个蕴涵的序（例如，age, income, price）。挖掘多维关联规则的技术可以根据量化属性的处理分为三类。

第一种方法，使用预定义的概念分层对量化属性离散化。这种离散化在挖掘之前进行。例如，income的概念分层可以用于以区间值，如“0...20K”、“21...30K”、“31...40K”等，替换属性的原来的数值值。这里，离散化是静态的、预确定的。离散化的数值属性具有区间值，可以象分类属性一样处理（每个区间看作一类）。我们称这种方法为使用量化属性的静态离散化挖掘多维关联规则。

第二种方法，根据数据的分布，将量化属性离散化到“箱”。这些箱可能在挖掘过程中进一步组合。离散化的过程是动态的，以满足某种挖掘标准，如最大化所挖掘的规则的置信度。由于该策略将数值属性的值处理成量，而不是预定义的区间或分类，由这种方法挖掘的关联规则称为量化关联规则。

第三种方法，量化属性离散化，以紧扣区间数据的语义。这种动态离散化过程考虑数据点之间的距离。因此，这种量化关联规则称作基于距离的关联规则。

让我们逐个研究这些挖掘多维关联规则方法。为简明起见，我们将讨论限于维间关联规则。注意，不是搜索频繁项集（象单维关联规则挖掘那样），在多维关联规则挖掘中，我们搜索频繁谓词集。k-谓词集是包含k个合取谓词的集合。例如，规则(6.12)中的谓词集{age, occupation, buys}是3-谓词集。类似于项集使用的记号，我们用Lk表示频繁k-谓词集的集合。 6.4.2 使用量化属性的静态离散化挖掘多维关联规则

在这种情况下，量化属性使用预定义的概念分层，在挖掘之前离散化，数值属性的值用区间替代，如果期望的话，分类属性可以泛化到较高的概念层。如果任务相关的结果数据存放在关系表中，则Apriori算法只需要稍加修改就可以找出所有的频繁谓词，而不是频繁项集（即，通过搜索所有的相关属性，而不是仅搜索一个属性，如buys）。找出所有的频繁k-谓词将需要k或k+1次表扫描。其它策略，如散列、划分和选样可以用来改进性能。

替换地，变换后的任务相关的数据可以存放在数据方中。数据方很适合挖掘多维关联规则，由于根据定义，它们是多维的。数据方和它们的计算已在第2章详细讨论。回顾一下，数据方由方体的格组成，方体是多维数据结构。这种结构可以存放任务相关的数据，以及聚集、分组信息。图6.17给出了一个方体的格，定义维age, income和buys的数据方。n-维方体的单元用于存放对应n-谓词集的计数或支持度。基本方体按age, income和buys聚集了任务相关的数据；2-D方体(age, income)按age和income聚集；0-D（顶点）方体包含任务相关数据中事务的总数，等等。

图6.17 方体的格，形成3-D数据方。每个方体代表一个不同

分组。基本方体包含三个谓词age, income和buys

由于数据仓库和OLAP技术的日益增长的使用，包含用户感兴趣的维的数据方可能已经存在，并完全物化。“如果是这种情况，我们如何去找频繁谓词集？”可以使用一种类似于Apriori所用的策略，基于先验知识：频繁谓词集的每个子集也必须是频繁的。这个性质可以用于减少产生的谓词集候选数量。

在没有挖掘任务相关数据方存在时，必须创建。第2章介绍了数据方快速、有效计算的算法。这些算法可以修改，在数据方构造时搜索频繁项集。 6.4.3 挖掘量化关联规则

量化关联规则是多维关联规则，其中数值属性动态离散化，以满足某种挖掘标准，如最大化挖掘规则的置信度或紧凑性。在本小节，我们将特别关注如何挖掘左部有两个量化属性，右部有一个分类属性的量化关联规则，例如

Aquan1?Aquan2?Acat 其中，Aquan1和Aquan2是在量化属性的区间（其中，区间动态地确定）上测试，Acat测试任务相关数据的分类属性。这种规则称作2-维量化关联规则，因为它们包含两个量化维。例如，假定我们关心象age和income这样的量化属性对和这样的顾客喜欢什么类型的电视机之间的关联关系。这种2-D量化关联规则的一个例子是

age(X,”30...39”) ? income(X ,”42K...48K”) ? buys(X,”high resolution TV”) (6.15)

“如何找出这种规则？”让我们看看系统ARCS（Association Rule Clustering System，关联规则聚类系统）使用的方法，其思想源于图形处理。本质上，该方法将量化属性对映射到满足给定分类属性条件的2-D栅格上。然后，搜索栅格点的聚类，由此产生关联规则。下面是ARCS涉及的步骤：

分箱。量化属性可能具有很宽的取值范围，定义它们的域。如果我们以age和income为轴，每个age的可能值在一个轴上赋予一个唯一的位置；类似地，每个income的可能值在另一个轴上赋予一个唯一的位置；想想2-D栅格会有多么大！为了使得栅格压缩到可管理的尺寸，我们将量化属性的范围划分为区间。这些区间是动态的，在挖掘期间它们可能进一步合并。这种划分过程称作分箱；即，区间被看作“箱”。三种常用的分箱策略是：

? 等宽分箱：每个箱的区间长度相同，

? 等深分箱：每个箱赋予大致相同个数的元组，和

? 基于同质的分箱：箱的大小这样确定，使得每个箱中的元组一致分布。

在ARCS中，使用等宽分箱，每个量化属性的箱尺寸由用户输入。对于涉及两个量化属性的每种可能的箱组合，创建一个2-D数组。每个数组单元存放规则右部分类属性每个可能类的对应的计数分布。通过创建这种数据结构，任务相关的数据只需要扫描一次。基于相同的两个量化属性，同样的2-D数组可以用于产生分类属性的任何值的规则。分箱在第3章也进行了讨论。

找频繁谓词集。一旦包含每个分类计数分布的2-D数组设置好，就可以扫描它，以找出也满足最小置信度的频繁谓词集（满足最小支持度）。然后，使用类似于6.2.2小节介绍的规则产生算法，由这些谓词集产生关联规则。

关联规则聚类。将上一步得到的强关联规则映射到2-D栅格上。图6.18显示给定量化属性age和income，预测规则右端条件buys(X,”high resolution TV”)的2-D量化关联规则。四个“?”对应于规则

age(X,34) ? income(X,”31K...40K”) ? buys(X,”high resolution TV”) (6.15) age(X,35) ? income(X,”31K...40K”) ? buys(X,”high resolution TV”) (6.16) age(X,34) ? income(X,”41K...50K”) ? buys(X,”high resolution TV”) (6.17) age(X,35) ? income(X,”41K...50K”) ? buys(X,”high resolution TV”) (6.18)

“我们能找到一个更简单的规则替换上面四个规则吗？”注意，这些规则都相当“接近”，在栅格中形成聚类。的确，这些规则可以组合或“聚”在一起，形成下面的规则(6.19)，它更简单，将上面四个规则汇总在一起，并取代它们。

age(X,”34...35”) ? income(X,”31K...50K”) ? buys(X,”high resolution TV”) (6.20)

ARCS使用聚类算法做这件事。该算法扫描栅格，搜索规则的矩形聚类。用这种方法，出现在规则聚类中的量化属性的箱可能进一步合并，从而对量化属性动态地离散化。

图6.18 表示购买高分辨TV的顾客元组的2-D栅格

这里介绍的基于栅格的技术假定初始关联规则可以聚集到矩形区域。在进行聚集前，可以使用平滑技术，帮助消除数据中噪音和局外者。矩形聚类可能过分简化数据。已经提出了一些替换技术，基于其它形状的区域，看来能够更适合数据，但需要更大的计算量。

已经提出了一种非基于栅格的技术，发现更一般的关联规则，其中任意个数的量化属性和分类属性可以出现在规则的两端。在这种技术下，量化属性使用等深分箱动态划分，划分根据部分完全性度量组合，该度量量化由于划分而导致的信息丢失。关于这些ARCS替代方法的引文，参见文献注释。

6.4.4 挖掘基于距离的关联规则

前一小节我们介绍了量化关联规则，其量化属性开始用分箱的方法离散化，然后将结果区间组合。然而，这种方法可能不能紧扣区间数据的语义，因为它未考虑数据点之间或区间之间的相对距离。

例如，考虑表6.3中属性price的数据，根据等宽和等深分箱与基于距离的划分对比。基于距离的划分看来最直观，因为它将接近的值分在同一区间内（例如，[20, 22]）。相比之下，等深划分将很远的值放在一组（例如，[22, 50]）。等宽划分可能将很近的值分开，并创建没有数据的区间。显然，基于距离的划分既考虑稠密性或区间内的点数，又考虑一个区间内点的“接近性”，这帮助产生更有意义的离散化。每个量化属性的区间可以通过聚集该属性的值建立。

关联规则的一个缺点是它们不允许近似的属性值。考虑关联规则

item_type(X,”electronic”) ? manufacture(X,”foreign”) ? price(X,$200) (6.20)

在现实中，更可能的是国外的电子产品的价格大约$200，而不是恰好$200。使得关联规则可以表达这种接近性是有用的。注意，支持度和置信度度量不考虑属性值的接近性。这导致基于距离的关联规则挖掘。这种规则紧扣区间数据的语义，并允许数据值的近似。一个两遍算法可以用于

挖掘基于距离的关联规则。第一遍使用聚类找出区间或聚类。第二遍搜索频繁地一起出现的聚类组得到基于距离的关联规则。

表6.3 分箱方法，如等宽和等深，不能总是紧扣区间数据的语义

price($) 7 20 22 50 51 53 等宽 （宽度$10） 等深 （深度2） 基于距离 [7,7] [20,22] [50,53] [0,10] [11,20] [21,30] [31,40] [41,50] [51,60] [7,20] [22,50] [51,53] “如何在第一遍形成聚类？”这里，我们给出如何形成聚类的直观介绍。感兴趣的读者可以阅读第8章，以及本章文献注释中给出的关于基于距离的关联规则的引文。设S[X]是N个元组t1, t2 ,..., tN投影到属性集X的集合。定义一个直径度量，评估元组的接近性。S[X]的直径是投影到X的元组两两距离的平均值。距离度量可以使用诸如欧几里德距离或曼哈坦距离8。S[X]的直径越小，其元组投影到X上时越接近。因此，直径度量评估聚类的稠密性。聚类CX是定义在属性集X上的元组的集合；其中，元组满足稠密度阈值和频繁度阈值。频繁度阈值限定聚类中元组的最少个数。聚类方法，如第8章介绍的那些，可以修改，用于该挖掘过程的第一遍。

第二遍，将聚类组合，形成基于距离的关联规则。考虑一个简单的形如CX ? CY的基于距离的关联规则。假定X是属性集{age}，而Y是属性集{income}。我们想确保age的聚类CX和income的聚类CY之间的蕴涵是强的。这意味当age聚类的元组投影到属性income上时，它们对应的值落在income聚类CY之内，或接近它。聚类CX投影到属性集Y上记作CX[Y]。这样，CX[Y]和CY[Y]之间的距离必须很小。该距离度量CX和CY之间的关联程度。CX[Y]和CY[Y]之间的距离越小，CX和CY之间的关联程度越强。关联程度度量可以使用标准统计度量定义，如平均内聚类距离，质心曼哈坦距离。其中，聚类的质心代表聚类的“平均”元组。

一般地，可以组合聚类，找出如下形式的基于距离的关联规则

CX1CX2...CXx?CYCY2...CYy

1其中，Xi和Yj是两两不相交的属性集，并满足以下三个条件：（1）规则前件的每个聚类与后件的每个聚类是强关联的；（2）前件中的聚类一起出现；（3）后件中的聚类一起出现。关联程度取代了非基于距离的关联规则框架下的置信度，而稠密度阈值取代了支持度。

6.5 由关联挖掘到相关分析

“挖掘了关联规则之后，数据挖掘系统如何指出哪些规则是用户感兴趣的？”大部分关联规则挖掘算法使用支持度-置信度框架。尽管使用最小支持度和置信度阈值排除了一些无兴趣的规则的探查，仍然会产生一些对用户来说不感兴趣的规则。本节，我们首先看看即便是强关联规则为何也可能是无兴趣的并可能误导；然后，讨论基于统计独立性和相关分析的其它度量。 6.5.1 强关联规则不一定是有趣的：一个例子

“在数据挖掘中，所有的强关联规则（即，满足最小支持度和最小置信度阈值）都有兴趣，值得向用户提供吗？”并不一定。规则是否有兴趣可能用主观或客观的标准来衡量。最终，只有用户能够确定规则是否是有趣的，并且这种判断是主观的，因不同用户而异。然而，根据数据“支持”的统计，客观兴趣度度量可以用于清除无兴趣的规则，而不向用户提供。

“我们如何识别哪些强关联规则是真正有兴趣的？”让我们考查下面的例子。 8

两个元组t1=(x11,x12,...,x1m)和t2=(x21,x22,...,x2m)之间的欧几里德距离和曼哈坦距离分别是

Euclidean_d(t1,t2)??m(x1ii?1?x2i)和Manhattan_d (t1,t2)??|x1i?x2i|。

i?12m例6.6 假定我们对分析AllElectronics的事务感兴趣，涉及计算机游戏和录像。设事件game表示包含计算机游戏的事务，而video表示包含录像的事务。在所分析的10,000个事务中，数据显示6000个顾客事务包含计算机游戏，7500个事务包含录像，而4000个事务包含计算机游戏和录像。假定发现关联规则的数据挖掘程序在该数据上运行，使用最小支持度30%，最小置信度60%。将发现下面的关联规则

buys(X,\computergames\)?buys(X,\videos\)4,00010,000

4,0006,000[support = 40%,confidence = 66%] (6.21)

规则(6.21)是强关联规则，因而向用户报告，因为其支持度为

?40%，置信度为

?

66%，分别满足最小支持度和最小置信度阈值。然而，规则(6.21)是误导，因为购买录像的可能性是75%，比66%还大。事实上，计算机游戏和录像是负相关的，买一种实际上减少了买另一种的可能性。不完全理解这种现象，可能根据导出的规则作出不明智的决定。? 上面的例子也表明规则A ? B的置信度有一定的欺骗性，它只是给定A，B的条件概率的估计。它并不度量A和B之间蕴涵的实际强度。因此，寻求支持度-置信度框架的替代，对挖掘有趣的数据联系可能是有用的。 6.5.2 由关联分析到相关分析

使用支持度-置信度框架的关联规则挖掘对于许多应用是有用的。然而，支持度-置信度框架可能误导，当A的出现事实上并不蕴涵B的出现时，识别出A ? B是有趣的。本小节，我们考虑一种替代框架，根据相关性挖掘数据项之间有趣的联系。

项集A的出现独立于项集B的出现，如果P(A ? B) = P(A)P(B)；否则，项集A和B是依赖的和相关的。这个定义容易推广到多于两个项集。A和B的出现之间的相关性通过计算下式度量

P(A?B) (6.22)

P(A)P(B)如果(6.22)式的值小于1，则A的出现和B的出现是负相关的。如果结果值大于1，则A和B是正相关的，意味每一个的出现都蕴涵另一个的出现。如果结果值等于1，则A和B是独立的，它们之间没有相关性。

让我们回头看例6.6计算机游戏和录像。

例6.7 为了帮助过滤掉形如A ? B的误导的“强”关联，我们需要研究两个项集A和B怎样才是相关的。设game表示例6.6中不包含计算机游戏的事务，video表示不包含录像的事务。事务可以汇总在相依表中。例6.6的数据的相依表如表6.4所示。由该表可以看出，购买计算机游戏的概率P({game}) = 0.60，购买录像的概率P({video}) = 0.75，而购买二者的概率P({game, video}) = 0.40。根据(6.22)式，P({game, video}) / (P({game}) ? P({video})) =0.40 / (0.75?0.60) = 0.89。由于该值明显比1小，{game}和{video}之间存在负相关。分子是顾客购买二者的可能性，而分母是如果两个购买是完全独立的可能性。这种负相关不能被支持度-置信度框架识别。?

表6.4 汇总关于购买计算机游戏和录像事务的2 ? 2相依表

video

game 4,000 2,000

6,000

game

3,500 500 4,000

?row 7,500 2,500 10,000

video

?col

这激发了识别相关性规则或相关规则的挖掘。相关规则形如{i1, i2, ..., im}，其中，项{i1, i2 ,..., im}的出现是相关的。给定由(6.22)式确定的相关值，?2统计可以确定相关是否是统计意义上的相关。?2统计也可以确定负蕴涵。

相关性的一个优点是它是向上封闭的。这意味，如果项集S是相关的（即，S中的项是相关的），则S的超集也是相关的。换句话说，添加项到相关集合中，不影响已存在的相关性。?2统计在每个有意义的层也是向上封闭的。

在搜索相关集，形成相关规则时，可以使用相关性和?2的向上封闭性。由空集开始，考察项集空间（或项集的格），一次添加一个项，寻找最小相关项集——相关的项集，其子集都不相关。这些项集形成格的边界。由于封闭性，边界以下的项集都不是相关的。由于最小相关项集的所有超集都是相关的，我们可以停止向上搜索。在项集空间进行这种一系列“行走”的算法称作随机行走算法。这种算法可以与支持度测试结合，以进行进一步的剪枝。随机行走算法容易使用数据方实现。将这里介绍的过程用于超大规模数据库是一个尚待解决的问题。另一个限制是，当相依表数据稀疏时，?2统计不够精确，并且对于大于2 ? 2相依表可能误导。替代支持度-置信度框架评估关联规则兴趣度的提议在文献注释中给出。

6.6 基于限制的关联挖掘

对于给定的任务相关的数据集，数据挖掘过程可能发现数以千计的规则，其中许多用户并不感兴趣。在基于限制的挖掘中，挖掘在用户提供的各种限制的指导下进行。这些限制包括

? ? ? ? ?

知识类型限制：指定要挖掘的知识类型，如关联规则。 数据限制：指定任务相关的数据集。

维/层限制：指定所用的维或概念分层结构的层。

兴趣度限制：指定规则兴趣度阈值或统计度量，如支持度和置信度。

规则限制：指定要挖掘的规则形式。这种限制可以用元规则（规则模板）表示，如可以出现在规则前件或后件中谓词的最大或最小个数，或属性、属性值和/或聚集之间的联系。

以上限制可以用高级数据挖掘查询语言说明，如用第4章介绍的语言。

上面的前4种限制已在本书或本章的前面讨论。本节，我们讨论使用规则限制对挖掘任务聚焦。这种基于限制的挖掘允许用户根据他们关注的目标，说明要挖掘的规则，因此使得数据挖掘过程更有功效。此外，可以使用复杂的挖掘查询优化程序，以便利用用户指定的限制，从而使得挖掘过程更有效率。基于限制的挖掘促进交互式探查挖掘与分析。在6.6.1小节，你将学习元规则制导的挖掘，那里用规则模板的形式说明了语法规则限制。6.6.2小节讨论进一步的规则限制使用，指定集合/子集联系、变量的常量初始化和聚集函数。 6.6.1 关联规则的元规则制导挖掘

“元规则有什么作用？”元规则使得用户可以说明他们感兴趣的规则的语法形式。规则的形式可以作为限制，帮助提高挖掘过程的性能。元规则可以根据分析者的经验、期望或对数据的直觉，或者根据数据库模式自动产生。

例6.8 假定作为AllElectronics的市场分析员，你已经访问了描述顾客的数据（如，顾客的年龄、地址和信誉度等），以及顾客事务的列表。你对找出顾客的特点和他购买的商品之间的关联关系感兴趣。然而，不是要找出反映这种联系的所有关联规则，你特别对什么样的一对顾客特点促进教育软件的销售感兴趣。可以使用一个元规则来说明你感兴趣的规则形式。这种元规则的一个例子是

P1(X,Y) ? P2(X,W) ? buys(X,”education software”) (6.23)

其中，P1和P2是谓词变量，在挖掘过程中被例示为给定数据库的属性；X是变量，代表顾客；Y和W分别取赋给P1和P2的属性值。典型地，用户要说明一个例示P1和P2需考虑的属性列表；否则，将使用省缺的属性集。

一般地，元规则形成一个关于用户希望探查或证实的、他感兴趣联系的假定。然后，挖掘系统可以寻找与给定元规则匹配的规则。例如，规则(6.24)匹配或遵守元规则(6.23)。

age(X,”30...39”) ) ? income(X,”41...60K”) ? buys(X,”education software”) (6.24)

?

“元规则如何用于指导挖掘过程？”让我们进一步考察这个问题。假定我们希望挖掘维间关联规则，如上例所示。元规则是形如

P1 ? P2 ?...? Pl ? Q1 ? Q2 ?...? Qr (6.31)

的规则模板。其中，Pi (i = 1, 2 ,..., l) 和Qj (j = 1, 2, ...,r )是例示谓词或谓词变量。设元规则中谓词的个数为p = l + r。为找出满足该模板的维间关联规则

? ?

我们需要找出所有的频繁p-谓词集Lp。

我们还必须有Lp中的l-谓词子集的支持度或计数，以计算由Lp导出的规则的置信度。

这是挖掘多维关联规则的典型情况，我们在6.4节已介绍。正如在那里看到的，数据方很适合多维关联规则的挖掘，因为它们具有存放聚集维值的能力。由于数据仓库和OLAP技术的流行，适合给定挖掘任务的、完全物化的n-D数据方可能已经存在。这里，n是被考虑的对谓词变量例示的属性数，加上在给定元规则中已经例示的谓词数，并且n ? p。通常，这种n-D数据方用方体的格表示，类似于图6.17中的那种。在这种情况下，我们只需要扫描p-D方体，将每个单元中的计数与最小支持度计数比较，以找出Lp。由于l-D方体已经计算，并包含Lp的l-D谓词子集的计数，然后调用规则产生过程，返回与元规则匹配的强规则。我们称这种方法为缩减的n-D方体搜索，因为它只考察p-D和l-D方体，而不是搜索整个n-D数据方。

如果用于元规则制导的挖掘任务的n-D数据方不存在，我们必须构造和搜索它。只需要计算p-D和l-D方体，而不是整个数据方。数据方的构造方法已在第2章讨论。 6.6.2 用附加的规则限制制导的挖掘

用户可以说明集合/子集联系，变量的常量初始化和聚集函数。这些可以与元规则制导的挖掘一起使用，或作为它的替代。本节，我们考察规则限制，看看怎样使用它们，使得挖掘过程更有效。让我们研究一个例子，其中规则限制用于挖掘混合维关联规则。

例6.9 假定AllElectronics有一个销售多维数据库，包含以下相互关联的关系：

? ? ? ?

sales(customer_name, item_name, transaction_id) lives(customer_name, region, city) item(item_name, category, price)

transaction(transaction_id, day, month, year)

其中，lives, item和transaction是三个维表，通过三个关键字customer_name, item_name和transaction_id分别链接到事实表sales。

我们的关联挖掘查询是“找出这样的销售，对于Vancouver的1999年的顾客，什么样的便宜商品（价格和低于$100）能够促进同类贵商品（最低价为$500）的销售？”该查询可以用DMQL数据挖掘查询语言表达如下。为方便讨论，查询的每一行已经编号。

(1) mine associations as (2) lives(C,_, “vancouver”) ? sales+(C,?{I},{S})? sales+(C,?{J},{T}) (3) from sales

(4) where S.year = 1999 and T.year = 1999 and I.category = J.category (5) group by C,I.category

(6) having sum(I.price) < 100 and min(J.price)?500 (7) with support threhold = 1% (8) with confidence threhold = 50%

在讨论规则限制之前，让我们仔细看看上面的查询。行1是知识类型限制，说明要发现关联模式。行2说明了元规则。这是下面混合维关联规则（多维关联规则，其中重复谓词是sales）的元规则的缩写形式：

lives(C,_,\Vacouver\)?sales(C,?I1,S1)?...?sales(C,?Ik,Sk)?I?{I1,...,Ik}?S?{S1,...,Sk) ?sales(C,?J1,T1)?...?sales(C,?Jm,Tm)?J?{J1,...,Jm}?T?{T1,...,Tm)这意味一个或多个sales记录以“sales(C,?I1,S1) ? ... ? sales(C,?Ik,Sk) ” 形式驻留在规则的前件（左部），问号“？”表示只有项的名字I1 ,..., Ik需要打印。“I={ I1 ,..., Ik }”意味出现在前件的所有的I取集合形式，由行4的类SQL的where-子句得到。类似的记号用于后件（右端）。

该元规则可能允许类似于下面的关联规则产生

lives(C,_,\Vancouver\)?sales(C,\Census_CD\,_)?sales(C,\MS/Office\,_)?sales(C,\MS/SQLServer\,_),[1.5%,68%] (6.26)

该规则意味, 如果顾客住在Vancouver，买了“Census_CD”和“MS/Office”，他多半会买“MS/SQLServer”（概率68%），并且所有顾客的1.5%买这三样。

数据限制在元规则的“lives(_,_,”Vancouver”)”部分指定（即，住在Vancouver的所有顾客），并在行3指出只有事实表sales需要显示引用。在多维数据库中，变量的引用被简化。例如，“S.year=1999”等价于SQL语句“from sales S, transaction R where S.transaction_ID = R.transaction_ID and R.year = 1999”。所有三个维(lives, item和transaction)都使用。层限制如下：对于lives，我们只考虑customer_name，因为只有city = “Vancouver”在选择中使用；对于item，我们考虑item_name和category，因为它们在查询中使用；对于transaction，我们只考虑transaction_ID，因为day和month未被引用，而year只在选择中使用。

规则限制包含在where（行4）和having（行6）子句的大部分，如“S.year = 1999”、 “T.year = 1999”、“ I.category = J.category”、“sum(I.price) < 100 ”和“min(J.price) ? 500”。最后，行7和8说明了两个兴趣度限制（即，阈值）：1%的最小支持度和50%的最小置信度。? 知识类型和数据限制在挖掘前使用。其它类型的限制可以在挖掘后使用，以便过滤发现的规则。然而，这可能使得挖掘过程非常低效，代价昂贵。维/层限制在6.3.2小节已讨论，而兴趣度限制在本章已广泛讨论。现在，让我们把注意力放在规则限制上。

“什么类型的规则限制可以在挖掘过程中使用，以缩小规则搜索空间？”你可能会问。“更特殊地，什么类型的规则限制可以‘推进’到挖掘过程，并且仍然保证回答挖掘查询的完全性？”

对于频繁项集挖掘，规则限制可以分为如下五类：（1）反单调的，（2）单调的，（3）简洁的，（4）可变的，（5）不可变的。对于每一类，我们将使用一个例子展示它的特性，并解释如何将这类限制用在挖掘过程中。

第一类限制是反单调性。考虑例6.9的规则限制”sum(I.price) < 100”。假定我们使用类似于Apriori的方法（逐层），对于每次迭代k，探查k-项集。其价格和不小于100的任何项集都可以由搜索空间剪去，因为向该项集中进一步添加项将会使它更贵，因此不可能满足限制。换一句话说，如果一个项集不满足该规则限制，它的任何超集也不可能满足该规则限制。如果一个规则具有这一性质，则称它是反单调的。根据反单调规则限制进行剪枝可以用于类-Apriori算法的每一次迭代，以帮助提高整个挖掘过程的性能，而保证数据挖掘任务的完全性。

注意，Apriori性质是说频繁项集的任何非空子集也必然是频繁的，它也是反单调的。如果给定的项集不满足最小支持度，则它的任何超集也不可能满足。这个性质用于Apriori算法的每次迭代，以减少考察的候选项集的个数，从而压缩关联规则的搜索空间。

反单调限制的其它例子包括”min(J.Price) ? 500”和”count(I) ? 10”等。任何违反这些限制的项集都可以丢弃，因为向这种项集中添加更多的项不可能满足限制。诸如”avg(I.price) ? 100”的限制不是反单调的。对于一个不满足该限制的项集，通过添加一些（便宜的）项得到的超集可能满足该限制。因此，将这种限制推进到挖掘过程之中，将不保证挖掘任务的完全性。表6.5的第二列给出刻画反单调性特性的基于SQL原语限制列表。为简化我们的讨论，只给出了存在性操作符（例如，?、?，但没有?、?）和带等号的比较（或包含）操作符（例如，?、?）。

第二类限制是单调性。如果例6.9中的规则限制是“sum(I.price) ? 100”，则基于限制的处理方法将很不相同。如果项集I满足该限制，即，集合中的单价和不少于100，进一步添加更多的项到I将增加价格，并且总是满足该限制。因此，在项集I上进一步检查该限制是多余的。换言之，如果一个项集满足这个规则限制，它的所有超集也满足。如果一个规则具有这一性质，则称它是单调的。类似的规则单调限制包括“min(I.price) ? 10”，“count(I) ? 10”等。表6.5的第三列给出刻画单调性特性的基于SQL原语限制列表。

表6.5 常用的基于SQL的限制的特性

限制 v?S S ? V S ? V min(S) ? v min(S) ? v max(S) ? v max(S) ? v count(S) ? v count(S) ? v

sum(S) ? v （?a?S,a ? 0） sum(S) ? v （?a?S,a ? 0） range(S) ? v range(S) ? v avg(S)? v, ??{=,?,?} support(S) ? ? support(S) ? ?

反单调的 否 否 是 否 是 是 否 是 否 是 否 是 否 可变的 是 否

单调的 是 是 否 是 否 否 是 否 是 否 是 否 是 可变的 否 是

简洁的 是 是 是 是 是 是 是 弱 弱 否 否 否 否 否 否 否

第三类是简洁性限制。对于这类限制，我们可以列出、并且仅仅列出所有确保满足该限制的集合。即，如果一个规则限制是简洁的，我们可以直接精确地产生满足它的集合，甚至在支持计数开始之前。这避免了产生-测试方式的过大开销。换言之，这种限制是计数前可剪枝的。例如，例6.9中的限制“min(J.price) ? 500”是简洁的。这是因为我们能够准确无误地产生满足该限制的所有项集。特殊地，这种集合至少包含一个项，其单价不低于$500。它是这种形式：S1 ? S2，其中S1 ? ?是集合中价格不低于$500的项的子集；而S2可能为空，是集合中价格不超过$500的项的子集。因为有一个精确“公式”，产生满足简洁限制的所有集合，在挖掘过程中不必迭代地检验规则限制。表6.5的第四列给出刻画简洁性特性的基于SQL原语限制列表。

第四类限制是可变的限制。有些限制不属于以上三类。然而，如果项集中的项以特定的次序排列，则对于频繁项集挖掘过程，限制可能成为单调的或反单调的。例如，限制“avg(I.price)”既不是反单调的，也不是单调的。然而，如果事务中的项以单价的递增序添加到项集中，则该限制就成了反单调的，因为如果项集I违反了该限制（即，平均单价大于$100），更贵的商品进一步添加到该项集中不会使它满足该限制。类似地，如果事务中的项以单价的递减序添加到项集中，则该限制就成了单调的，因为如果项集I违反了该限制（即，平均单价不超过$100），添加更便宜的商品到当前项集将使得平均单价不大于$100。除表6.5给出的“avg(S) ? v”和“avg(S) ? v”外，还有一些其它可变的限制，如“variance(S) ? v”和“standard_variation(S) ? v”等。

注意，以上讨论并不意味每种限制都是可变的。例如，“sum(S) ? v”不是可变的，其中, ??{?, ?}并且S中的元素可以是任意实数。因此，还有第五类限制，称作不可变的限制。一个好消息是：尽管有一些难处理的限制是不可变的，大部分使用SQL内部聚集的简单SQL表达式都属于前四类之一，对于它们可以使用有效的限制挖掘方法。

6.7 总结

?

大量数据之间的关联关系的发现在选择购物、决策分析和商务管理方面是有用的。一个流行的应用领域是购物篮分析，通过搜索经常一块购买的商品的集合（或序列），研究顾客的购买习惯。关联规则挖掘首先找出频繁项集（项的集合，如A和B，满足最小支持度阈值，或任务相关元组的百分比），然后，由它们产生形如A ? B的强关联规则。这些规则也满足最小置信度阈值（预定义的、在满足A的条件下满足B的概率）。 根据不同的标准，关联规则可以分成若干类型，如：

?

(1) 根据规则所处理的值的类型，关联规则可以分为布尔的和量化的。布尔关联规则表现离散

（分类）对象之间的联系。量化关联规则是多维关联规则，涉及动态离散化的数值属性。它也可能涉及分类属性。 (2) 根据规则中数据涉及的维，关联规则可以分成单维和多维的。单维关联规则涉及单个谓词

或维，如buys；而多维关联规则涉及多个（不同的）谓词或维。单维关联规则展示的是维内联系（即，同一个属性或维内的关联）；而多维关联规则展示的是维间联系（即，属性/维之间的关联）。 (3) 根据规则涉及的抽象层，关联规则可以分为单层和多层的。在单层关联规则中，项或谓词

的挖掘不考虑不同的抽象层；而多层关联规则考虑多个抽象层。 (4) 根据对关联挖掘的不同扩充，关联挖掘可以扩充为相关分析和最大频繁模式（“最大模

式”）与频繁闭项集挖掘。相关分析指出相关项的存在与否。最大模式是一个频繁模式p，使得p的任何真超集都不是频繁的。频繁闭项集是指：项集c是闭的，如果不存在c的真超集c’，使得包含c的子模式的每个事务也包含c’。

?

Apriori算法是一种有效的关联规则挖掘算法，它逐级探查，进行挖掘。Apriori性质：频繁项集的所有非空子集都必须是频繁的。在第k次迭代，它根据频繁k-项集，形成频繁(k+1)-项集候选，并扫描数据库一次，找出完整的频繁(k+1)-项集L k+1。

涉及散列和事务压缩的变形可以用来使得过程更有效。其它变形涉及划分数据（在每一部分上挖掘，然后合并结果）和数据选样（在数据子集上挖掘）。这些变形可以将数据扫描次数减少到一或两次。

频繁模式增长（FP-增长）是一种不产生候选的挖掘频繁项集方法。它构造一个高度压缩的数据结构（FP-树），压缩原来的事务数据库。不是使用类Apriori方法的产生-测试策略，它聚焦于频繁模式（段）增长，避免了高代价的候选产生，获得更好的效率。

多层关联规则可以根据每个抽象层上的最小支持度阈值如何定义，使用多种策略挖掘。当在较低层使用递减的支持度时，剪枝方法包括层交叉按单项过滤，层交叉按k-项集过滤。冗余的（后代）关联规则可以删除，不向用户提供，如果根据其对应的祖先规则，它们的支持度和置信度接近于期望值的话。

挖掘多维关联规则可以根据对量化属性处理分为若干类。第一，量化属性可以根据预定义的概念分层静态离散化。数据方非常适合这种方法，因为数据方和量化属性都可以利用概念分层。第二，可以挖掘量化关联规则，其量化属性根据分箱动态离散化，“临近的”关联规则可以用聚类组合。第三，可以挖掘基于距离的关联规则，其中区间根据聚类定义。 并非所有的强关联规则都是有趣的。对于统计相关的项，可以挖掘相关规则。

基于限制的挖掘允许用户聚焦，按提供的元规则（即，模式模板）和其它挖掘限制搜索规则。这种挖掘促进了说明性数据挖掘查询语言和用户界面的使用，并对挖掘查询优化提出了巨大挑战。规则限制可以分五类：反单调的、单调的、简洁的、可变的和不可变的。前四类限制可以在关联挖掘中使用，指导挖掘过程，导致更有功效和更有效率的挖掘。

关联规则不应当直接用于没有进一步分析或领域知识的预测。它们不必指示因果关系。然而，对于进一步探查，它们是有帮助的切入点。这使得它们成为理解数据的流行工具。

?

?

?

? ?

?

习题

6.1 Apriori算法使用子集支持度性质的先验知识。

(a) 证明频繁项集的所有非空子集必须也是频繁的。

(b) 证明项集s的任意非空子集s’的支持度至少和s的支持度一样大。

(c) 给定频繁项集l和l的子集s，证明规则”s’ ? (l-s’)”的置信度不可能大于”s ? (l-s)”的置信度。其中，s’是s的子集。

(d) Apriori的一种变形将事务数据库D中的事务划分成n个不重叠的部分。证明在D中是频繁的任何项集至少在D的一个部分中是频繁的。

6.2 6.2.2小节介绍了由频繁项集产生关联规则的方法。提出一个更有效的方法。解释它为什么比

6.2.2小节的方法更有效。（提示：考虑将习题6.1(b)和6.1(c)的性质结合到你的设计中） 6.3 数据库有4个事务。设min_sup = 60%，min_conf = 80%。

TID T100 T200 T300 T400

date 10/15/99 10/15/99 10/19/99 10/22/99

items_bought {K,A,D,B} {D,A,C,E,B} {C,A,B,E} {B,A,D}

(a) 分别使用Apriori和FP-增长算法找出频繁项集。比较两种挖掘过程的有效性。

(b) 列出所有的强关联规则（带支持度s和置信度c），它们与下面的元规则匹配，其中，X是代表顾客的变量，itemi是表示项的变量（例如，”A”、”B’等）：

? x? transaction, buys(X, item1) ?buys(X, item2) ? buys(X, item3) [s, c]

6.4 数据库有4个事务。设min_sup = 60%，min_conf = 80%。

cust_ID 01 02 01 03

TID T100 T200 T300 T400

items_bought（以brand-item_category形式）

{King’s-Carb, Sunset-Milk, Dairyland-Cheese,best-Bread}

{Best-Cheese, Dairyland-Milk, Goldenfarm-Apple, tasty-Pie, Wonder-Bread} {Westcoast-Apple, Dairyland-Milk, Wonder-Bread, Tasty-Pie} {Wonder-Bread, Sunset-Milk, Dairyland-Cheese}

(a) 在item_category粒度（例如，itemi可以是“Milk”），对于下面规则模板

? x? transaction, buys(X, item1) ?buys(X, item2) ? buys(X, item3) [s, c] 对最大的k, 列出频繁k -项集和包含最大的k的频繁k-项集的所有强关联规则。 (b) 在brand-item_category粒度（例如，可以是“Sunset-Milk”），对于下面的规则模板

? x? customer, buys(X, item1) ?buys(X, item2) ? buys(X, item3) 对最大的k, 列出频繁k -项集。注意：不打印任何规则。

6.5 假定一个大型存储具有分布在4个站点的事务数据库。每个成员数据库中的事务具有相同的格

式Tj: {i1 ,..., im}；其中，Tj是事务标识符，而ik(1 ? k ? m)是事务中购买的商品标识符。提出一个有效的算法，挖掘全局关联规则（不考虑多层关联规则）。你可以给出你的算法的要点。你的算法不必将所有的数据移到一个站点，并且不造成过度的网络通讯开销。 6.6 假定大型事务数据库DB的频繁项集已经存储。讨论：如果新的事务集?DB（渐增地）加进，

在相同的最小支持度阈值下，如何有效地挖掘（全局）关联规则？ 6.7 假定描述Big-University大学学生的数据关系已被泛化为表6.6的泛化关系R。

设概念分层如下：

status: {freshman, sophomore, junior, senior} ? undergraduate

{M.Sc, M.A, Ph.D} ? graduate

major: {physics, chemistry, math} ? science

{CS, engineering} ? appl_science

age: {16...20, 21-25} ? young

{26...30, over_30} ? old

nationality: {Asia, Europe, Latin_America}? foreign

{Canada, U.S.A.} ?North_America

表6.6 习题6.7的泛化关系

major French CS physics engineering philosophy French chemistry CS

philosophy French philosophy philosophy French math CS

philosophy philosophy French engineering math chemistry engineering French philosophy math

status M.A junior M.S Ph.D Ph.D senior junior senior M.S junior junior M.S junior senior junior Ph.D senior Ph.D junior Ph.D junior junior M.S junior junior

age over_30 16...20 26...30 26...30 26...30 16...20 21...25 16...20 over_30 16...20 26...30 26...30 16...20 16...20 16...20 26...30 26...30 over_30 21...25 26...30 16...20 21...25 over_30 21...25 16...20

nationality Canada Europe

Latin_America Asia Europe Canada U.S.A. Canada Canada U.S.A. Canada Asia Canada U.S.A. Canada Canada Canada Canada Europe

Latin_America U.S.A. Canada

Latin_America U.S.A. Canada

gpa 2.8...3.2 3.2...36 3.2...3.6 3.6...4.0 3.2...3.6 3.2...3.6 3.6...4.0 3.2...3.6 3.6...4.0 2.8...3.2 2.8...3.2 3.2...3.6 3.2...3.6 3.6...4.0 3.2...3.6 3.6...4.0 2.8...3.2 2.8...3.2 3.2...3.6 3.2...3.6 3.6...4.0 3.2...3.6 3.2...3.6 2.8...3.2 3.6...4.0

count 3 29 18 78 5 40 25 70 15 8 9 9 52 32 76 14 19 1 71 7 46 96 4 8 59

设最小支持度阈值为2%，最小置信度阈值为50%（每一层）。

(a) 画出status, major, age, nationality的概念分层。 (b) 对所有层使用一致的支持度，对于下面的规则模板

? S ? R P(S,x) ? Q(S,y) ? gpa(S, z) [s, c]

其中，P, Q ? {status, major, age, nationality}。找出R中的多层强关联规则。

(c) 使用层交叉单项过滤，找出R中的多层强关联规则。其中，递减的支持度10%用于如下规则模板的最低抽象层：

? S ? R P(S,x) ? Q(S,y) ? gpa(S, z) [s, c] 不要挖掘交叉层规则。 6.8 提出并给出挖掘多层关联规则的层共享挖掘方法的要点。其中，每个项用它的层位置编码，一

次初始数据库扫描收集每个概念层的每个项的计数，识别频繁和子频繁项集。将用该方法挖掘多层关联规则与挖掘单层关联规则的花费进行比较。

?的项集H的支持度与项集H-h?的支持度相同。解释如何将它用于6.9 证明：包含项h和其祖先h层交叉关联规则挖掘。

6.10 在挖掘层交叉关联规则时，假定发现项集”{IBM dssktop computer, printer}”不满足最小支持

度。这一信息可以用来剪去诸如”{IBM desktop computer, b/w printer}”的“后代”项集的挖掘吗？给出一个一般规则，解释这一信息如何用于对搜索空间剪枝。 6.11 提出一种挖掘混合维关联规则（多维关联规则，有重复谓词）的方法。

6.12 给出一个短例子，表明强关联规则中的项可能实际上是负相关的。

6.13 下面的相依表汇总了超级市场的事务数据。其中，hot dog表示包含热狗的事务，hotdog表示

不包含热狗的事务，humburgers表示包含汉堡包的事务，humburgers表示不包含汉堡包的事务。

hot dog hotdog

humburgers 2,000 500

1,000 1,500 humburgers 3,000 2,000 ?col

?row 2,500

2,500 5,000

(a) 假定发现关联规则”hot dog ? humburgers”。给定最小支持度阈值25%，最小置信度阈值50%，该关联规则是强的吗？ (b) 根据给定的数据，买hot dog独立于买humburgers吗？如果不是，二者之间存在何种相关联系？ 6.14 序列模式可以用类似于关联规则挖掘的方法挖掘。设计一个有效的算法，由事务数据库挖掘

多层序列模式。这种模式的一个例子如下：“买PC的顾客在三个月内将买Microsoft软件”，在其上，可以下钻，发现该模式的更详细的版本，如“买Pentium Pro的顾客在三个月内将买Microsoft Office ”。 6.15 证明下面表中的每一项正确地刻画了它对应的关于频繁项集挖掘的规则限制。

(a) (b) (c) (d)

规则限制 v?S S ? V min(S) ? v range (S) ? v

反单调性 否 是 否 是 可变的

单调性 是 否 是 否

简洁性 是 是 是 否

(e) avg(S) ? v

可变的 否

6.16 商店里每种商品的价格是非负的。商店经理只关心如下形式的规则：“一件免费商品可能触

发在同一事务中$200的总购物”。陈述如何有效地挖掘这种规则。 6.17 商店里每种商品的价格是非负的。对于以下每种情况，识别它们提供的限制类型，并简略讨

论如何有效地挖掘这种关联规则。

(a) 至少包含一件Nintendo游戏。

(b) 包含一些商品，它们的单价和小于$150。

(c) 包含一件免费商品，并且其它商品的单价和至少是$200。 (d) 所有商品的平均价格在$100和$500之间。

文献注释

关联规则挖掘首先由Agrawal, Imielinski和Swami[AIS93b] 提出。6.2.1小节讨论的Apriori算法由Agrawal和Srikant [AS94] 提出。使用类似的剪枝方法的算法变形独立地由Mannila, Toivonen和Verkamo[MTV94]开发。结合这些工作的联合出版物稍后出现在Aga\\rawal, Mannila, Skrikant, Toivonen和Verkamo[AMS+96]。产生关联规则的方法在Agrawal和Srikant[AS94a]中介绍。6.2.3小节的Apriori的变形包括如下引文。使用hash表提高关联规则挖掘效率被Park,Chen和Yu[PCY95]研究。扫描和事务压缩技术在Agrawal和Srikant[AS94b]，Han和Fu[HF95]，以及Park, Chen和Yu[PCY95a]中介绍。划分技术由Savasere, Omiecinski和Navathe[SON95]提出。选样方法在Toivonen[Toi96]中讨论。动态项集计数在Brin, Motwani, Ullman和Tsur[BMUT97]中给出。关联

规则挖掘有许多扩充，包括序列模式挖掘（Agrawal和Srikant[AS95]），espisodes挖掘（Mannila, Toivonen和Verkamo[MTV97]），挖掘空间关联规则（Kopeski和Han[KH95]），挖掘有环的关联规则（?zden, Ramaswamy和Silberschatz[ORS98]），挖掘否定的关联规则（Savasere, Omiecinski和Navathe[SON98]），挖掘事务间关联规则（Lu, Han和Feng[LHF98]）和日历购物篮分析（Ramaswamy, Mahajan和Silberschatz[RMS98]）。最大模式的挖掘在Bayaedo[Bay98]中介绍。频繁闭合项集的挖掘由Pasquier, Bastile, Taouil和Lakhal[PBTL99]提出，而有效的挖掘算法由Pei, Han和Mao[PHM00]提出。冰山查询在Fang, Shivakumar, Garcia-Molina等[FSGM+98] 中介绍，而Beyer和Ramakrishnan[BR99]开发了冰山查询的有效计算方法。频繁项集的深度优先产生由Agrawal,Aggarwal和Prasad[AAP00]提出。挖掘频繁模式而不产生候选的方法由Han, Pie和Yin[HPY00]提出。

多层关联规则挖掘在Han和Fu[HF95]，Srikant和Agrawal[SA95]中研究。在Srikant和Agrawal [SA]中，这种挖掘以广义关联规则的形式研究，并提出R-兴趣度度量，以删除冗余规则。

6.4.3小节介绍的根据规则聚类挖掘量化关联规则的ARCS系统由Lent,Swami和Widom[LSW97]提出。基于x-单调和直线区间挖掘量化规则的技术由Fukuda, Morimoto, Morishita和Tokuyama[FMMT96]，Yoda, Fukuda, Morimoto等[YFM+97]提出。挖掘量化关联规则的非基于栅格的技术使用部分完全性度量，由Srikant和Agrawal[SA96]提出。6.4.3小节介绍的挖掘区间数据上的（基于距离的）关联规则由Miller和Yang[MY97]提出。使用量化属性的静态离散化和数据方，挖掘多维关联规则被Kamber, Han和Chiang[KHC97]研究。

在数据挖掘中规则的统计独立性被Piatetski_Shapiro[PS91]研究。强关联规则的兴趣度问题被Chen, Han和Yu[CHY96]，Brin, Motwani和Silverstein[BMS97], Aggarwal和Yu[AY99]讨论。推广关联到相关的有效方法在Brin, Motwani 和Silverstein[BMS97]，并简略总结6.5.2小节中。评估关联规则兴趣度的支持度-置信度框架的其它替代在Brin, Motwani, Ullman和Tsur[BMUT97]，Ahmed, EI-Makky和Taha[AEMT00]中提出。Silverstein, Brin, Motwani和Ullman[SBMU98]研究了挖掘事务数据库因果关系结构的问题。

使用元规则作为语法或语义过滤器，定义单维关联规则的感兴趣形式由Klemettinen, Mannila, Ronkainen等[KMR+94]提出。元规则制导的挖掘在Shen, Ong, Mitbander 和Zaniolo[SOMZ96]中提出；那里，元规则后件指定用于满足元规则前件的数据的动作（如，贝叶斯聚类）。关联规则元规则制导的挖掘基于关系的方法在Fu和Han[HF95]中研究。基于数据方的方法在Kamber, Han和Chiang[KHC97]中研究。6.4.2小节基于限制的关联规则挖掘在Ng, Lakshmanan, Han和Pang[NLHP98]，Lakshmanan, Ng, Han和Pang [LNHP99], Pei和Han[PH00]中研究。挖掘受限的相关集的有效方法在Grahne, Lakshmanan和Wang[GLW00]中给出。涉及在挖掘中使用模板或谓词限制的其它思想在[AK93, DT93, HK91, LHC97, St96, SVA97]中讨论。

本章提供的关联规则挖掘语言基于Han, Fu, Wang等[HFW+96]提出的数据挖掘查询语言DMQL的扩充，结合了由Meo,Paila和Ceri[MPC96]提出的挖掘单维关联规则的类SQL的操作。预计今后的版本将遵循Microsoft公司提出的DM OLE DB[Mic00]语法。

挖掘关联规则的有效渐增更新由CheungHan, Ng和Wong[CHNW96]提出。在Apriori框架下，并行和分布关联规则挖掘被Park,Chen和Yu[PCY95b]，Agrawal和Shafer[AS96]，Cheung, han, Ng等[CHN+96]研究。另一种并行关联规则挖掘方法使用垂直数据库设计探查项集聚类，在Zaki, Parthasarathy, Ogihara和Li[ZPOL97]中提出。

本文来源：https://www.bwwdw.com/article/x7cg.html