数据挖掘概念与技术CHAPTER6挖掘大型数据库中的关联规则

1、挖掘大型数据库中的关联规则关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。随着大量数据不停地收集和存储，许多业界人士对于从他们的数据库中挖掘关联规则越来越感兴趣。从大量商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物和贱卖分析。关联规则挖掘的一个典型例子是购物篮分析。该过程通过发现顾客放入其购物篮中不同商品（图6.1）之间联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。例如，在同一次去超级市场，如果顾客购买牛奶，他也购买面包（和什么类型的面包）的可能性有多大？通过帮助零售商有选择地经销和安排货架

2、，这种信息可以引导销售。例如，将牛奶和面包尽可能放近一些，可以进一步刺激一次去商店同时购买这些商品。图6.1 购物篮分析数据是事务的或关系的，如何由大量的数据中发现关联规则？什么样的关联规则最有趣？我们如何帮助或指导挖掘过程发现有趣的关联规则？对于关联规则挖掘，什么样的语言结构对于定义关联挖掘查询是有用的？本章我们将深入研究这些问题。6.1 关联规则挖掘关联规则挖掘寻找给定数据集中项之间的有趣联系。本节简要介绍关联规则挖掘。6.1.1小节给出一个购物篮分析的例子，这是关联规则挖掘的最初形式。挖掘关联规则的基本概念在6.1.2小节给出。6.1.3小节给出一个路线图，指向可挖掘的各种不同类型关联规

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

4、的顾客一路挑选其它商品。例如，在决定购买一台很贵的计算机之后，去看软件陈列，购买财务软件，路上可能看到安全系统，可能会决定也买家庭安全系统。购物篮分析也可以帮助零售商规划什么商品降价出售。如果顾客趋向于同时购买计算机和打印机，打印机降价出售可能既促使购买打印机，又促使购买计算机。如果我们想象全域是商店中可利用的商品的集合，则每种商品有一个布尔变量，表示该商品的有无。每个篮子则可用一个布尔向量表示。可以分析布尔向量，得到反映商品频繁关联或同时购买的购买模式。这些模式可以用关联规则的形式表示。例如，购买计算机也趋向于同时购买财务管理软件可以用以下关联规则表示：support=2%,confiden

5、ce=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。关联规则是

6、形如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之间的值表示支持度和置信度。项的集合称为项集

7、 在数据挖掘研究界，“itemset”比“item set”更常用。包含k个项的项集称为k-项集。集合computer, financial_management_ software是一个2-项集。项集的出现频率是包含项集的事务数，简称为项集的频率、支持计数或计数。项集满足最小支持度min_sup，如果项集的出现频率大于或等于min_sup与D中事务总数的乘积。如果项集满足最小支持度，则称它为频繁项集 在早期的工作中，满足最小支持度的项集称为大的。然而，该术语有时易混淆，因为它具有项集中项的个数的内涵，而不是集合出现的频率。因此，我们使用当前术语频繁。频繁k -项集的集合通常记作Lk。 尽管频

8、繁已取代大的，由于历史的原因，频繁k-项集仍记作Lk。“如何由大型数据库挖掘关联规则？”关联规则的挖掘是一个两步的过程：找出所有频繁项集：根据定义，这些项集出现的频繁性至少和预定义的最小支持计数一样。由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和最小置信度。如果愿意，也可以使用附加的兴趣度度量。这两步中，第二步最容易。挖掘关联规则的总体性能由第一步决定。6.1.3 关联规则挖掘：一个路线图购物篮分析只是关联规则挖掘的一种形式。事实上，有许多种关联规则。根据下面的标准，关联规则有多种分类方法：根据规则中所处理的值类型：如果规则考虑的关联是项的在与不在，则它是布尔关联规则。例如，

9、上面的规则(6.1)是由购物篮分析得到的布尔关联规则。如果规则描述的是量化的项或属性之间的关联，则它是量化关联规则。在这种规则中，项或属性的量化值划分为区间。下面的规则(6.4)是量化关联规则的一个例子，其中，X是代表顾客的变量。 (6.4)注意，量化属性age 和income已离散化。根据规则中涉及的数据维：如果关联规则中的项或属性每个只涉及一个维，则它是单维关联规则。注意，(6.1)式可以写作 (6.5)规则(6.1)是单维关联规则，因为它只涉及一个维buys 按照多维数据库使用的术语，我们把规则中的每个不同谓词称作维。如果规则涉及两个或多个维，如维buys, time_of_transa

10、ction和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”高的抽象层）。我们称所挖掘的规则

11、集由多层关联规则组成。反之，如果在给定的规则集中，规则不涉及不同抽象层的项或属性，则该集合包含单层关联规则。根据关联挖掘的各种扩充：关联挖掘可以扩充到相关分析，那里，可以识别项是否相关。还可以扩充到挖掘最大模式（即，最大的频繁模式）和频繁闭项集。最大模式是频繁模式p，使得p的任何真超模式 q是p的超模式，如果p是q的子模式；即，如果q包含p。都不是频繁的。频繁闭项集是一个频繁的、闭的项集；其中，项集c是闭的，如果不存在c的真超集c，使得每个包含c的事务也包含c。使用最大模式和频繁闭项集可以显著地压缩挖掘所产生的频繁项集数。本章的其余部分，你将学习上述每种关联规则的挖掘方法。由事务数据库挖掘单维

12、布尔关联规则本节，你将学习挖掘最简单形式的关联规则的方法。这种关联规则是单维、单层、布尔关联规则，如6.1.1小节所讨论的购物篮分析中的那些。我们以提供Apriori算法开始（6.2.1小节）。AprioriApriori算法的一些变形，用于提高效率和可规模性。6.2.4小节提出一些挖掘关联规则方法，不象Apriori，它们不涉及“候选”Apriori的原则用于提高冰山查询的效率。冰山查询在购物篮分析中是常见的。6.2.1 Apriori算法：使用候选项集找频繁项集Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。算法的名字基于这样的事实：算法使用频繁项集性质的先验知识，正如我

13、们将看到的。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）不可

14、能比I更频繁出现。因此，I A也不是频繁的，即P(I A) s。该性质属于一种特殊的分类，称作反单调，意指如果一个集合不能通过测试，则它的所有超集也都不能通过相同的测试。称它为反单调的，因为在通不过测试的意义下，该性质是单调的。“如何将Apriori性质用于算法？”为理解这一点，我们必须看看如何用Lk - 1找Lk。下面的两步过程由连接和剪枝组成。连接步：为找Lk，通过Lk - 1与自己连接产生候选k-项集的集合。该候选项集的集合记作Ck。设l1和l2是Lk - 1中的项集。记号lij表示li的第j项（例如，l1k-2表示l1的倒数第3项）。为方便计，假定事务或项集中的项按字典次序排序。执行连

15、接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。剪枝步：Ck是Lk的超集；即，它的成员可以是，也可以不是频繁的，但所有的频繁k-项集都包含在Ck中。扫描数据库，确定Ck中每个候选的计数，从而确定Lk（即，根据定义，计数值不小于最小支持度计数

16、的所有候选是频繁的，从而属于Lk）。然而，Ck可能很大，这样所涉及的计算量就很大。为压缩Ck，可以用以下办法使用Apriori性质：任何非频繁的(k-1)-项集都不是可能是频繁k-项集的子集。因此，如果一个候选k-项集的(k-1)-子集不在Lk - 1中，则该候选也不可能是频繁的，从而可以由Ck中删除。这种子集测试可以使用所有频繁项集的散列树快速完成。例 让我们看一个Apriori的具体例子。该例基于图6.2的AllElectronics的事务数据库。数据库中有9个事务，即|D| = 9。Apriori假定事务中的项按字典次序存放。我们使用图6.3解释Apriori算法发现D中的频繁项集。Al

17、lElectronics数据库TIDList of item_IDsT100T200T300T400T500T600T700T800T900I1,I2,I5I2,I4I2,I3I1,I2,I4I1,I3I2,I3I1,I3I1,I2,I3,I5I1,I2,I3图 AllElectronics某分店的事务数据在算法的第一次迭代，每个项都是候选1-项集的集合C1的成员。算法简单地扫描所有的事务，对每个项的出现次数计数。假定最小事务支持计数为2（即，min_sup = 2/9 = 22%）。可以确定频繁1-项集的集合L1。它由具有最小支持度的候选1-项集组成。为发现频繁2-项集的集合L2，算法使用L

18、1L1产生候选2-项集的集合C2 L1L1等价于L1 L1，因为LkLk的定义要求两个连接的项集共享k-1=0个项。C2由个2-项集组成。下一步，扫描D中事务，计算C2中每个候选项集的支持计数，如图6.3的第二行的中间表所示。确定频繁2-项集的集合L2，它由具有最小支持度的C2中的候选2-项集组成。图6.3 候选项集和频繁项集的产生，最小支持计数为2连接：C3= L2L2=I1,I2,I1,I3,I1,I5,I2,I3,I2,I4,I2,I5I1,I2,I1,I3,I1,I5,I2,I3,I2,I4,I2,I5 = I1,I2,I3,I1,I2,I5,I1,I3,I5,I2,I3,I4,I2,

19、I3,I5,I2,I4,I5使用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

20、,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候选3-项集的集合C3的产生详细地列在图6.4中。首先，令C3 = L2L2 =

21、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)-子集是否频繁。扫描D中事务，以确定L3，它由具有最小支持度的C3中的候选3-项集组成（图6.3）。算法使用L3L3产生候选4-项集的集合C4。尽管连接产生结果I1,I2,I3,I5，这个项集被剪去，因为它的子集I1,I3

22、,I5不是频繁的。这样，C4 = ，因此算法终止，找出了所有的频繁项集。Apriori算法和它的相关过程的伪代码。Apriori的第1步找出频繁1-项集的集合L1。在2-10步，Lk - 1用于产生候选C k，以找出L k。Apriori_gen过程产生候选，然后使用Apriori性质删除那些具有非频繁子集的候选（步骤3）。该过程在下面描述。一旦产生了所有的候选，就扫描数据库（步骤4）。对于每个事务，使用subset函数找出事务中是候选的所有子集（步骤5），并对每个这样的候选累加计数（步骤6和7）。最后，所有满足最小支持度的候选形成频繁项集L。然后，调用一个过程，由频繁项集产生关联规则。该过程

23、在6.2.2小节介绍。算法 (Apriori) 使用逐层迭代找出频繁项集输入：事务数据库D；最小支持度阈值。输出：D中的频繁项集L。方法：L1 = find_frequent_1_itemsets(D);for (k = 2; Lk-1 ; k+) Ck = aproiri_gen(Lk-1,min_sup);for each transaction tD /scan D for countCt = subset(Ck,t); /get subsets of t that are candidatesfor each candidate cCt c.count+;Lk=cCk | c.coun

24、t min_supreturn L = kLk；procedure apriori_gen(Lk-1: frequent (k-1)-itemset; min_sup: support)for each itemset l1Lk-1for each itemset l2Lk-1if (l11=l21).(l1k-2=l2k-2)(l1k-11)。例如，当扫描数据库中每个事务，由C1中的候选1-项集产生频繁1-项集L1时，我们可以对每个事务产生所有的2-项集，将它们散列（即，映射）到散列表结构的不同桶中，并增加对应的桶计数（图6.6）。在散列表中对应的桶计数低于支持度阈值的2-项集不可能是频繁2

25、-项集，因而应当由候选项集中删除。这种基于散列的技术可以大大压缩要考察的k-项集（特别是当k = 2时）。事务压缩（压缩进一步迭代扫描的事务数）：不包含任何k-项集的事务不可能包含任何(k+1)-项集。这样，这种事务在其后的考虑时，可以加上标记或删除，因为为产生j-项集(j k)，扫描数据库时不再需要它们。划分（为找候选项集划分数据）：可以使用划分技术，它只需要两次数据库扫描，以挖掘频繁项集（图6.7）。它包含两遍。在第I遍，算法将D中的事务划分成n个非重叠的部分。如果D中事务的最小支持度阈值为min_sup，则每个部分的最小支持度计数为min_sup该部分中事务数。对每一部分，找出该部分内的

26、频繁项集。这些称作局部频繁项集。该过程使用一种特殊的数据结构，对于每个项集，记录包含项集中项的事务的TID。这使得对于k = 1,2,.，找出所有的局部频繁k-项集只需要扫描一次数据库。局部频繁项集可能不是整个数据库D的频繁项集。D的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。这样，所有的局部频繁项集作为D的候选项集。所有部分的频繁项集的集合形成D的全局候选项集。在第II遍，第二次扫描D，评估每个候选的实际支持度，以确定全局频繁项集。每一部分的大小和划分的数目这样确定，使得每一部分能够放入内存，这样每遍只需要读一次。图 通过划分挖掘选样（在给定数据的一个子集挖掘）：选样方法的基本思想

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

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

29、情况下，Apriori的候选产生-检查方法大幅度压缩了候选项集的大小，并导致很好的性能。然而，它有两种开销可能并非微不足道的。它可能需要产生大量候选项集。例如，如果有104个频繁1-项集，则Apriori算法需要产生多达107个候选2-项集，累计并检查它们的频繁性。此外，为发现长度为100的频繁模式，如a1 ,., a100，它必须产生多达2100 1030个候选。它可能需要重复地扫描数据库，通过模式匹配检查一个很大的候选集合。对于挖掘长模式尤其如此。“可以设计一种方法，挖掘全部频繁项集，而不产生候选吗？”一种有趣的方法称作频繁模式增长，或简单地，FP-增长，它采取如下分治策略：将提供频繁项集

30、的数据库压缩到一棵频繁模式树（或FP-树），但仍保留项集关联信息；然后，将这种压缩后的数据库分成一组条件数据库（一种特殊类型的投影数据库），每个关联一个频繁项，并分别挖掘每个数据库。让我们看一个例子。例 使用频繁模式增长方法，我们重新考察例中图事务数据库D的挖掘。数据库的第一次扫描与Apriori相同，它导出频繁项（1-项集）的集合，并得到它们的支持度计数（频繁性）。设最小支持度计数为2。频繁项的集合按支持度计数的递减序排序。结果集或表记作L。这样，我们有L = I2:7, I1:6, I3:6, I4:2, I5:2。然后，FP-树构造如下：首先，创建树的根结点，用“null”标记。二次扫描

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

32、增加1，为随在前缀之后的项创建结点并链接。为方便树遍历，创建一个项头表，使得每个项通过一个结点链指向它在树中的出现。扫描所有的事务之后得到的树展示在图6.8中，附上相关的结点链。这样，数据库频繁模式的挖掘问题就转换成挖掘FP-树问题。图6.8 存放压缩的频繁模式信息的FP-树FP-树挖掘处理如下。由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基（一个“子数据库”， 由FP-树中与后缀模式一起出现的前缀路径集组成）。然后，构造它的（条件）FP-树，并递归地在该树上进行挖掘。模式增长通过后缀模式与由条件FP-树产生的频繁模式连接实现。FP-树的挖掘总结在表6.1中，细节如下。让我们首先

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

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

35、, (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。输出：频繁模式的完全集。方法：按以下步骤构造FP-树：扫描事务数据库D一次。收集频繁项的集合F和它们的支持度。对F按支持度降序排序，结果为频繁项表L。创建FP-树的根结点，

36、以“null”标记它。对于D中每个事务Trans，执行：选择Trans中的频繁项，并按L中的次序排序。设排序后的频繁项表为p | P，其中，p是第一个元素，而P是剩余元素的表。调用insert_tree(p | P, T)。该过程执行情况如下。如果T有子女N使得 = ，则N的计数增加1；否则创建一个新结点N，将其计数设置为1，链接到它的父结点T，并且通过结点链结构将其链接到具有相同item-name的结点。如果P非空，递归地调用insert_tree(P, N)。FP-树的挖掘通过调用FP_growth(FP_tree, null)实现。该过程实现如下：procedure FP_growth(

37、Tree, )if Tree 含单个路径P then for 路径P中结点的每个组合（记作）产生模式 ，其支持度support = 中结点的最小支持度；else for each a i 在Tree的头部 产生一个模式 = a i ，其支持度support = a i .support；构造的条件模式基，然后构造的条件FP-树Tree；if Tree then调用 FP_growth (Tree, )；图 不产生候选，发现频繁项集的FP-增长算法FP-增长方法将发现长频繁模式的问题转换成递归地发现一些短模式，然后与后缀连接。它使用最不频繁的项作后缀，提供了好的选择性。该方法大大降低了搜索开销。

38、当数据库很大时，构造基于内存的FP-树是不现实的。一种有趣的替换是首先将数据库划分成投影数据库的集合，然后在每个投影数据库上构造FP-树并挖掘它。该过程可以递归地用于投影数据库，如果它的FP-树还不能放进内存。对FP-树方法的性能研究表明：对于挖掘长的和短的频繁模式，它都是有效的和可规模化的，并且大约比Apriori算法快一个数量级。它也比树-投影算法快。树-投影算法递归地将数据库投影为投影数据库树。6.2.5 冰山查询Apriori算法可以用来提高回答冰山查询的效率。冰山查询在数据挖掘中经常用，特别是对购物篮分析。冰山查询在一个属性或属性集上计算一个聚集函数，以找出大于某个指定阈值的聚集值。

39、给定关系R，它具有属性a_1, a_2, . , a_n和b，一个聚集函数agg_f，冰山查询形如select from group byhaving R.a_1, R.a_2, . ,R.a_n, agg_f(R.b)relation Ragg_f(R.b) = threshold给定大量输入数据元组，满足having子句中的阈值的输出元组数量相对很少。输出结果看作“冰山顶”，而“冰山”是输入数据集。 一个冰山查询：假定给定销售数据，你想产生这样的一个顾客-商品对的列表，这些顾客购买商品的数量达到3件或更多。这可以用下面的冰山查询表示selectfromgroup byhavingP.cus

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

41、ngPurchases PSUM(P.qty) = 3产生item_list，被顾客购买的、数量为3或更多的商品表。例如selectfromgroup byhavingP. item_IDPurchases PSUM(P.qty) = 3由先验知识，我们可以删除许多被散列/排序方法产生的顾客-商品对：仅对cust_list中的顾客和在item_list中的商品产生候选顾客-商品对。对每个这样的对，维持一个计数。尽管该方法通过预先裁减许多对或分组提高了性能，所产生的顾客-商品对数量可能依然很大，不能放进内存。可以将散列和选样策略集成到该过程，帮助提高该查询回答技术的总体性能。6.3 由事务数据库

42、挖掘多层关联规则本节，你将学习挖掘多层关联规则的方法。多层关联规则是这样一些规则，它们涉及多个抽象层中的项。本节还讨论检查冗余多层规则的方法。6.3.1 多层关联规则对于许多应用，由于多维数据空间数据的稀疏性，在低层或原始层的数据项之间很难找出强关联规则。在较高的概念层发现的强关联规则可能提供普遍意义的知识。然而，对一个用户代表普遍意义的知识，对另一个用户可能是新颖的。这样，数据挖掘系统应当提供一种能力，在多个抽象层挖掘关联规则，并容易在不同的抽象空间转换。让我们考察下面的例子。 假定给定表6.2事务数据的任务相关数据集，它是AllElectronics分店的计算机部的销售数据，对每个事务TI

43、D给出了购买的商品。商品的概念分层在图6.11给出。概念分层定义了由低层概念到高层更一般的概念的映射序列。可以通过将数据内的低层概念用概念分层中的其高层概念（祖先）替换，对数据进行泛化 概念分层已在第2、4章详细介绍。为了使得本书的没章尽可能自包含，我们在此再次给出它的定义。泛化在第5章已介绍。图6.11的概念分层有4层，记作0, 1, 2和3层。为方便计，概念分层中的层自顶向下编号，根结点all（最一般的抽象概念）为第0层。因此，第1层包括computer, software, printer和computer accessory，第2层包括desktop computer, laptop

44、computer, education software, financial management software, .，而第3层包括IBM desktop computer,., Microsoft education software，等等。第3层是该分层结构的最特定的抽象层。概念分层可以由熟悉数据的用户指定，也可以在数据中蕴涵存在。表 任务相关数据DTID购买的商品T1T2T3T4T5.IBM desktop computer, Sony b/w printerMicrosoft educationsoftware, Microsoft finacial management sof

45、twareLogitech mouse computer accessory, Ergo-way wrist pad computer accessoryIBM desktop computer, Microsoft finacial management software IBM desktop computer.图 AllElectronics计算机商品的概念分层表中的项在图概念分层的最低层。在这种原始层很难找出有趣的购买模式。例如，如果“IBM desktop computer”和“Sony b/w (黑白) printer”每个都在很少一部分事务中出现，则可能很难找到涉及它们的强关联规

46、则。很少人同时购买它们，使得“ 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”。换句话说，包含更一般项的项

47、集，如“ IBM desktop computer, b/w printer ”和“ computer, printer ”，比仅包含原始层数据的项集，如“ IBM desktop computer, Sony b/w printer ”，更可能满足最小支持度。因此，在多个概念层的项之间找有趣的关联比仅在原始层数据之间更容易找。由具有概念分层的关联规则挖掘产生的规则称为多层关联规则，因为它们考虑多个概念层。6.3.2 挖掘多层关联规则的方法“我们如何使用概念分层有效地挖掘多层关联规则？”让我们看一些基于支持度-置信度框架的方法。一般地，可以采用自顶向下策略，由概念层1开始向下，到较低的更特定的

48、概念层，在每个概念层累加计数计算频繁项集，直到不能再找到频繁项集。即，一旦找出概念层1的所有频繁项集，就开始在第2层找频繁项集，如此下去。对于每一层，可以使用发现频繁项集的任何算法，如Apriori或它的变形。这种方法有许多变形，介绍如下，并用图6.12到图6.16解释。图中矩形指出项或项集已被考察，而粗边框的矩形指出已考察的项或项集是频繁的。对于所有层使用一致的支持度（称作一致支持度）：在每一层挖掘时，使用相同的最小支持度阈值。例如，在图6.12中，整个使用最小支持度阈值5%（例如，对于由“computer”到“laptop computer”）。“ computer”和“laptop co

49、mputer”都是频繁的，但“desktop computer”不是。图6.12 具有一致支持度的多层挖掘使用一致的最小支持度阈值时，搜索过程是简单的，并且用户也只需要指定一个最小支持度阈值。根据祖先是其后代的超集的知识，可以采用优化策略：搜索时避免考察这样的项集，它包含其祖先不具有最小支持度的项。然而，一致支持度方法有一些困难。较低层次抽象的项不大可能象较高层次抽象的项出现得那么频繁。如果最小支持度阈值设置太高，可能丢掉出现在较低抽象层中有意义的关联规则。如果阈值设置太低，可能会产生出现在较高抽象层的无兴趣的关联规则。这导致了下面的方法。在较低层使用递减的支持度（称作递减支持度）：每个抽象层

50、有它自己的最小支持度阈值。抽象层越低，对应的阈值越小。例如，在图6.13，层1和层2的最小支持度阈值分别为5%和3%。用这种方法，“computer”、“laptop computer”和“desktop computer”都是频繁的。图6.13 具有递减支持度的多层挖掘对于具有递减支持度的多层关联规则挖掘，有许多可用的搜索策略，包括：逐层独立：这是完全的宽度搜索，没有频繁项集的背景知识用于剪枝。考察每一个结点，不管它的父结点是否是频繁的。层交叉用单项过滤：一个第i层的项被考察，当且仅当它在第(i-1)层的父结点是频繁的。换一句话说，我们由较一般的关联考察更特定的关联。如果一个结点是频繁的，它

51、的子女将被考察；否则，它的子孙将由搜索中剪枝。例如，在图中，“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”、“

52、 desktop computer, b/w printer”和“desktop computer, color printer”被考察。图6.15 具有递减支持度的多层挖掘，使用层交叉用k-项集过滤，其中k=2“如何比较这些方法？”逐层独立策略的条件很松，可能导致在低层考察大量非频繁的项，找出一些不太重要的关联。例如，如果“computer furniture”很少购买，考察特定的“computer chair”是否与“laptop computer”关联没什么意思。然而，如果“computer accessories”经常出售，考察“laptop”与“mouse”之间是否存在关联购买模式可

53、能是有意义的。层交叉用k-项集过滤策略允许系统仅考察频繁k-项集的子女。这一限制可能太强，通常没有多少k-项集组合后仍是频繁的（特别是当k 2时）。因此，有些有价值的模式可能被该方法过滤掉。层交叉用单项过滤策略是上两个极端的折衷。然而，这种方法也可能丢失低层项之间的关联；根据递减的最小支持度，这些项是频繁的，但它们的祖先不满足最小支持度（由于每层的支持度阈值可能不同）。例如，如果根据第i层的最小支持度阈值，“color monitor”在第i层是频繁的，但是它在(i-1)层的父结点“monitor”，根据第(i-1)层的最小支持度阈值，不是频繁的，则频繁的关联“desktop computer

54、 color monitor”将丢失。层交叉单项过滤策略有一个修改版本，称作受控的层交叉单项过滤策略。可以设置一个称作层传递阈值的阈值，用于向较低层“传递”相对频繁的项（称作子频繁项）。换句话说，如果满足层传递阈值，则该方法允许考查不满足最小支持度阈值项的子女。每个概念层可以有它自己的层传递阈值。通常，对于一个给定层，层传递阈值设置为下一层的最小支持度阈值和给定层的最小支持度阈值之间的一个值。用户可以在较高层选择“下滑”或降低层传递阈值，使得子频繁项的后代在较低层被考察。降低层传递阈值到最低层的最小支持度阈值将使得项的所有后代被考察。例如，在图6.16中，设置层1的层传递阈值(level_pa

55、ssage_sup)为8%，使得第2层的“laptop computer”和“desktop computer”被考察，并发现是频繁的，尽管它们的父结点“computer”不是频繁的。通过增加这种机制，用户对进一步控制多概念层上的挖掘过程有了更多的灵活性，同时减少无意义关联的考察和产生。图6.16 多层挖掘，受控的层交叉单项过滤迄今为止，我们的讨论集中在发现这样的频繁项集，它的所有项都属于同一概念层。这可能导致形如“computer printer”（其中，”computer”和”printer”都在概念层1）和“desktop computer b/w printer”（其中，”deskto

56、p computer”和”b/w printer”都在给定概念层的第2层）的规则。假定我们想要发现跨越概念层边界的规则，如“computer b/w printer”，规则中的项不要求属于同一概念层。这些规则称作交叉层关联规则。“如何挖掘交叉层关联规则？”如果挖掘由层i到层j的关联，其中层j比层i更特定（即，在较低的抽象层），则应当使用层j的最小支持度阈值，使得层j的项可以包含在分析中。6.3.3 检查冗余的多层关联规则概念分层在数据挖掘中是有用的，因为它们允许不同的抽象层的知识发现，如多层关联规则。然而，当挖掘多层关联规则时，由于项之间的“祖先”关系，有些发现的规则将是冗余的。例如，考虑下面

57、的规则，其中，根据图的概念分层，”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)“如果挖掘出规则和，那么后一个规则是有用的吗？”你可能怀疑“它真的提供新颖的信息吗？”如果后一个具有较小一般性的规则不提供新的信息，应当删除它。让我们看看如何来确定。规则R1是规则R2的祖先，如果将R2中的项用它在概念分

58、层中的祖先替换，能够得到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

59、%1/4）的支持度。如果确实是这种情况，规则(6.10)不是有趣的，因为它不提供附加的信息，并且它的一般性不如规则(6.9)。6.4 由数据库和数据仓库挖掘多维关联规则本节，你将学习挖掘多维关联规则的方法。多维关联规则是涉及多个属性或谓词的规则（例如，关于顾客的buys和顾客的age的规则）。这些方法可以根据他们对量化属性的处理组织。6.4.1 多维关联规则到本章这里，我们研究了蕴涵单个谓词，即谓词buys的关联规则。例如，在挖掘AllElectronics数据库时，我们可能发现布尔关联规则“IBM desktop computer Sony b/w printer”，它也可以写成buys(X

60、,”IBM desktop computer”) buys(X,”Sony b/w printer”) (6.11)其中，X是变量，代表在AllElectronics购物的顾客。沿用多维数据库使用的术语，我们把每个不同的谓词称作维。这样，我们称规则(6.11)为单维或维内关联规则，因为它们包含单个不同谓词（即，buys）的多次出现（即，谓词在规则中出现多次）。正如我们在本章的前几节看到的，这种规则通常由事务数据挖掘。然而，假定不是使用事务数据库，销售和相关数据存放在关系数据库或数据仓库中。根据定义，这种存储是多维的。例如，除记录购买的商品之外，关系数据库可能记录与商品有关的其它属性，如购买数量