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

当数据库很大时，构造基于内存的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)为单维或维内关联规则，因为它们包含单个不同谓词

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据挖掘CHAPTER6挖掘大型数据库中的关联规则(3)在线全文阅读。