

5 关联模式挖掘：高级概念

每个孩子都是进入更美好生活的冒险 ——一个改变旧模式并使其焕然一新的机会。” —— Hubert H. Humphrey

5.1 介绍

关联模式挖掘算法通常会发现大量的模式，并且很难将这个大输出用于特定于应用程序的任务。其中一个原因是绝大多数发现的关联可能对特定的应用程序而言是无趣或冗余的。本章讨论了一些高级方法，旨在使关联模式挖掘更加应用敏感：

1.总结：关联模式挖掘的输出通常非常大。对于最终用户来说，更小的一组发现项目集更容易理解和吸收。本章将介绍一些汇总方法，例如查找最大项目集，闭合项目集或非冗余规则。

2.查询：当大量项目集可用时，用户可能希望查询它们以获取较小的摘要。本章将讨论一些查询友好的专用汇总方法。这个想法是使用两阶段的方法，其中数据被预处理以创建摘要。 然后查询该摘要。

3.约束合并：在许多真实场景中，可能希望将特定于应用的约束合并到项目集生成过程中。 虽然基于约束的算法可能并不总是提供在线响应，但它确实允许使用低得多的支持级别来进行挖掘，而不是两阶段“预处理查询”方法。

表5.1：市场购物篮数据集快照示例（从第4章表4.1中复制）

tid	Set of items
1	{Bread,Butter,Milk}
2	{Eggs,Milk,Yogurt}
3	{Bread,Cheese,Eggs,Milk}
4	{Eggs,Milk,Yogurt}
5	{Cheese,Milk,Yogurt}

这些主题都与以不同方式从项目集中提取有趣的摘要信息有关。例如，项目集的压缩表示对查询非常有用。查询友好型压缩方案与旨在确保非冗余性的汇总方案有很大不同。 类似地，约束项目集比非约束项目集更少。 但是，发现项目集的收缩是由于约束而不是压缩或汇总方案。本章还将讨论关联模式挖掘的一些有用的应用。

本章安排如下。模式总结的问题在5.2节中得到解决。关于模式挖掘的查询方法的讨论请参见5.3节。第5.4节讨论了频繁模式挖掘的许多应用。5.5节中对结论进行了讨论。

5.2 模式总结

频繁的项目集挖掘算法通常会发现大量的模式。输出的大小为用户吸收结果并做出有意义的推论带来了挑战。一个重要的观察是绝大多数生成的模式往往是多余的。这是因为向下关闭属性，它确保频繁项目集的所有子集也很频繁。在频繁模式挖掘中存在不同类型的紧凑表示，这些表示保留了关于频繁模式及其支持值的真实集合的不同级别的知识。最知名的表示是最大频繁项目集，闭合频繁项目集和其他近似表示。这些表示在汇总表示中的信息损失程度上有所不同。关于项目集的支持和成员资格，闭合表示完全无损。最大表示在支持方面是有损的，但是在项目集的成员方面是无损的。大致精简的表示对于两者都是有损的，但通常在应用驱动的场景中提供最佳的实际替代。

5.2.1最大模式

上一章简要讨论了最大项目集的概念。为了方便起见，这里重申了最大项目集的定义：

定义5.2.1（最大频繁项集） 在最小支持的情况下，如果一个频繁项数集的任意一个超集都是非频繁集，那么这个频繁项数集就是最大频繁项集。

例如，考虑表5.1的示例，该示例从前一章表4.1的示例中复制而来。 很明显，项目组（鸡蛋，牛奶，酸奶）频繁出现在2的最低支持水平，也是最大的。 由于支持单调性属性，对最大项集合的适当子集的支持总是等于或大于后者。 例如，作为项目集{鸡蛋，牛奶，酸奶}的适当子集的{鸡蛋，牛奶}的支持是3.因此，总结的一种策略是仅挖掘最大项目集。 其余项目集作为最大项目集的子集派生。

尽管所有的项目集都可以通过子集方法从最大项目集中推导出来，但是它们的支持值不能派生出来。 因此，最大项目集是有损的，因为它们不保留有关支持值的信息。 为了在支持值方面提供无损表示，使用闭项目集挖掘的概念。这个概念将在下一节讨论。

寻找所有最大项目集的一个简单方法是使用任何频繁项目集挖掘算法来查找所有项目集。 然后，通过按照长度递减的顺序检查项目集，并且移除适当的子集，只有最大项可以保留在后处理阶段。这个过程一直持续到所有项目集都被检查或删除。 在终止时没有被移除的项目集是最大的。但是，这种方法是一个低效率的解决方案。当项目集非常长时，最大频繁项目集的数量可能比频繁项目集的数量小几个数量级。在这种情况下，设计可以在频繁项目集发现期间直接修剪部分模式搜索空间的算法是有意义的。大多数树形枚举方法都可以使用前瞻的概念来修改，以剪除模式的搜索空间。这个概念在前一章中DP算法的上下中被讨论过。

虽然前瞻的概念在第四章中有描述，这里为了完整再重复一遍。设P是项目集枚举树中的一个频繁模式，$F(P)$表示枚举树中P的候选扩展集合。那么，如果$P∪F(P)$是已经找到的频繁模式的子集，那么它意味着以P为根的整个枚举树是频繁的，因此可以从进一步考虑中去除。如果子树未被修剪，则需要计算P的候选扩展。在计数期间，统计$P∪F(P)$的支持，同时统计P的单项候选扩展的支持。如果$P∪F(P)$频繁，那么以P为根的子树也可以被修剪。前一种基于子集的修剪方法在深度优先方法中特别有效。这是因为最早的模式比深度优先策略早得多，而广度优先策略更早。对于长度为k的最大模式，深度优先方法在仅探索其前缀$(k-1)$后发现它，而不是探测$2^k$个可能性。此最大模式随后可用于基于子集的修剪。然后修剪剩下的包含$P∪F(P)$子集的子树。 DP算法的上下文中首先提到了深度优先方法的优越前瞻修剪。

修剪方法提供了一组较小的模式，其中包括所有最大模式，但也可能包括一些没有修剪的非最大模式。 因此，可以应用上面讨论的方法来去除这些非最大模式。 参考书目注释以获取各种最大频繁模式挖掘算法的指针。

5.2.2 封闭模式

封闭模式或闭合项目集的简单定义如下：

**定义5.2.2（封闭项目集）**如果项目集X，它的直接超集的支持度计数都不等于它本身的支持度计数，则它是封闭的。

频繁模式挖掘算法除了频繁之外，还需要闭合项目集。那么为什么闭合项目很重要？ 考虑一个闭合项集$X$和集合$S(X)$，它们是$X$的子集，它们与$X$具有相同的支持。唯一来自$S(X)$且由闭合频繁项集挖掘算法返回的项目集将会是$X$。包含在$S(X)$中的项目集可以被称为$X$的等支持子集。一个重要的观察结果如下：

观察结论5.2.1 设$X$是闭合项目集，$S(X)$是其等支持子集。对于任何一个项集$Y∈S(X)$，包含$Y$的事务集$T(Y）$是完全相同的。此外，在$S(X)$之外没有项集$Z$，这样$\top(Z)$中的事务集就是与$\top(X)$相同。

这种观察来自频繁项目集的向下闭合特性。 对于X的任何适当子集Y，事务集$\top(Y)$总是$\top(X)$的超集。 然而，如果$X$和$Y$的支持值相同，那么$\top(X)$和$\top(Y)$也是相同的。此外，如果任何项集$Z\notin\top(X)$产生$\top(Z)=\top(X)$，则$Z∪X$的支持必须与$X$的支持相同。因为$Z$不是$X$的一个子集，所以$Z∪X$必须是$X$的适当超集。这将导致与假设X闭合矛盾 。

理解项目集$X$编码关于$S(X)$中的任何项目集所需的所有非冗余计数信息的信息是很重要的。$S(X)$中的每个项目集都描述了同一组事务，因此，保留单个代表性项目组就足够了。$S(X)$中的最大项集$X$被保留。应该指出，定义5.2.2是基于使用集合闭包算子的更正式定义的简化。使用集合闭包算子的正式定义直接基于观察5.2.1（这是从简化定义导出的）。本章使用的非正式方法旨在更好地理解。频繁闭项集挖掘问题定义如下。

**定义5.2.3（频繁闭项集）**在最小支持的情况下，如果项目集$X$既是封闭的又是频繁的，则它是一个频繁闭项集。

可以通过两种方式发现闭合项集的集合：

1.可以确定在任何给定的最小支持水平上的频繁项目集合，并且可以从该集合导出频繁闭项集合。

2.算法可以设计为在频繁模式发现过程中直接找到闭合的频繁模式。

虽然第二类算法超出了本书的范围，但在此将提供查找所有闭合项目集的第一种方法的简要说明。读者可以参考第二种算法的书目注释。

一个寻找频繁闭项集的简单方法是首先将所有频繁项目集划分为等支持组。可以报告来自每个等支持组的最大项目集。考虑一组频繁模式$F$，从中需要确定闭合频繁模式。$F$中频繁模式按照支持的升序排序进行处理，并根据它们是否关闭来进行排序或排除。请注意，支持的升序排序也会保证闭合模式比其冗余子集早出现。最初，所有模式都没有标记。当未标记模式$X∈F$被处理时（基于增加的支持顺序选择），它被添加到频繁闭集$CF$。具有相同支持的X的正确子集不能关闭。因此，所有具有相同支持的X的适当子集都被标记。为了实现这个目标，表示$F$的项集网格的子集可以从X开始以深度优先或宽度优先的顺序遍历，并且探索X的子集。当$X$的子集具有与$X$遍历过程会在以较大的支持到达某个项目集时回退，或者项目集已被当前或前一次遍历标记。遍历完成后，选择下一个未标记的节点作进一步探索并添加到$CF$。重复标记节点的整个过程，从新添加到$CF$的模式开始。在过程结束时，$CF$中的项目集表示频繁的封闭模式。

5.2.3 近似频繁模式

近似频繁模式挖掘方案几乎总是有损方案，因为它们不保留有关项目集的所有信息。模式的近似可以用以下两种方式之一来执行：

1.事务方面的描述：闭包属性根据事务成员资格提供项目集的无损描述。这种想法的概括是允许“几乎”关闭，其中闭包属性并不完全满足，但大致指定。因此，在封闭定义的支持值中允许“游戏”。

2.根据项目集本身进行描述：在这种情况下，频繁项目集被聚集，并且可以从每个集群中绘制代表以提供简明摘要。在这种情况下，根据代表与剩余项目集之间的距离允许“游戏”。

这两种类型的描述会产生不同的见解。 一个是根据事务成员来定义的，而另一个是根据项目组的结构来定义的。请注意，在10个项目集X的子集中，9个项目集可能具有更高的支持度，但1个项目集可能具有与X完全相同的支持度。在第一个定义中，10个项目集和1个项目集在事务成员方面相对于彼此“几乎”是多余的。在第二个定义中，就项目集结构而言，10项目集和9项目集相对于彼此几乎是冗余的。 以下部分将介绍用于发现每种类型项目集的方法。

5.2.3.1 关于事务的近似

闭包属性用事务描述项目集，以及不同项目集与这个标准的等价关系。“大致关闭”的概念是这个标准的一个概括。 有多种方法可以定义“近似闭合”，为了便于理解，在这里引入了一个更简单的定义。

在较早的准确封闭情况下，人们以特定的支持值选择最大的超集。在近似闭包中，没有必要在特定支持值上选择最大超集，但允许在一系列支持范围内的“游戏”$δ$。因此，所有频繁项集$F$可以分割成k个“几乎相等支持”的不相交集合组$F_1…F_k$，使得对于任何$F_i$中的任何项目集$X$，$Y$的部分，$| sup（X） - sup（Y）| <span><span class="MathJax_Preview">的值最多是</span><script type="math/tex">的值最多是$δδ。 从每个$F_i$组，只报告最大的频繁代表。显然，当$δ$被选择为0时，这恰好是一组闭合项目集。如果需要，还可以存储从大致关闭的项目集中移除单个项目所获得的确切错误值。当然，支持值仍然存在一些不确定性，因为通过移除两个项目获得的项目集的支持值不能从该附加数据中准确推断出来。

请注意，当$δ> 0$时，“几乎等支持”组可能以许多不同方式构建。这是因为“几乎等支持”组的范围不一定是$δ$，也可能小于$δ$。当然，选择范围的贪心算法是始终选择支持度最低的项目集，然后在其中添加δ以选择范围的上限。重复此过程以构建所有范围。然后，可以基于这些范围提取频繁闭项集。

用于查找频繁“几乎关闭”项目集的算法与查找频繁闭项集非常相似。和前面的情况一样，可以将频繁项目集划分成几乎均等的支持组，并确定其中的最大项。根据图格子的遍历算法如下。

第一步是确定“几乎同等支持”组的不同支持范围。$F$中的项目集按照“几乎同等支持”组的支持范围递增顺序进行分组处理。在一个组中，未标记的项目集按照增加的支持顺序进行处理。当检查这些节点时，它们被添加到几乎关闭的项目$AC$中。当检查一个模式$X∈F$时，同一组内的所有适当的子集都被标记，除非它们已经被标记。为了实现这个目标，表示$F$的项集网格的子集可以像前面（精确）闭集的情况中讨论的那样进行遍历。这个过程在下一个没有标记的节点上重复进行。在过程结束时，项目$AC$包含频繁的“几乎关闭”模式。文献中提供了各种定义“几乎关闭”项目集的其他方法。书目注释包含这些方法的指示。

5.2.3.2 项目集的近似

项目集的近似也可以用许多不同的方式来定义，并且与聚类密切相关。从概念上讲，目标是从频繁项目集$calF$中创建集群，并从集群中选择代表$J= J_1 ... J_k$。 因为聚类总是相对于项目集$X$和$Y$之间的距离函数$Dist（X，Y）$定义的，所以$δ$近似集的概念也基于距离函数。

定义5.2.4（$δ$-近似集）如果对于每个频繁模式$X∈F$且每个$J_i∈J$，符合下面的描述，代表$J=\left\{J_1 ... J_k\right\}$的集合为$δ$近似:

$ Dist（X，J_i）\leqδ\tag{5.1}$

可以使用任何用于集值数据的距离函数，例如Jaccard系数。注意，集合$k$的基数定义了压缩水平。因此，目标是确定特定压缩水平$δ$的最小$k$值。这个目标与基于分区的聚类表达密切相关，其中k的值是固定的，并且单个对象与其代表的平均距离被优化。 从概念上讲，这个过程还会在频繁项目集上创建一个聚类。频繁项目集既可以严格划分到他们最近的代表，也可以允许他们属于多个集合，它们与最近代表的距离至多为$δ$。

那么，如何确定代表性集合的最优尺寸呢？事实证明，简单的贪婪解决方案在大多数情况下都非常有效。设$C（J）⊆F$表示$J$中代表所覆盖的频繁项目集的集合。那么$F$中的项目集由$J$中的代表所覆盖，如果它位于至少一个$J$的代表的最多$δ$的距离内。很明显，确定$J$使得$C（J）= F$并且集$J$的大小尽可能小。

贪心算法的思想是从$J = {}$开始，并且将$F$中的第一个元素添加到$J$中，该元素覆盖了$F$中项目集的最大数目。然后将覆盖项目集从$F$中删除。为了最大化残差集合$F$中的覆盖范围,通过贪婪地添加更多的元素到$F$迭代地重复该过程.当集合$F$为空时，该过程终止。可以证明函数$f（J）= | C（J）|$ 满足关于参数$J$的子模性属性。在这种情况下，贪婪算法在实践中通常是有效的。事实上，在这个问题的小变化中，$| C（J）| <span><span class="MathJax_Preview">直接针对</span><script type="math/tex">直接针对$JJ的固定大小进行优化，也可以对贪婪算法实现的质量建立理论界限。读者可以参考书目注释来了解子模数的指示。

5.3 模式查询

尽管压缩方法提供了对频繁项目集的简要总结，但可能存在用户可能希望查询具有特定属性的模式的情况。查询响应在应用程序中提供相关的模式集合。这个相关集合通常比整套模式要小得多。一些例子如下：

1.报告所有含有最小支持的X的频繁模式。

2.报告所有包含X的关联规则，这些关联规则有最小支持度和最小可信度。

一种可能性是彻底扫描所有频繁项目集并报告满足用户指定约束的项目集。然而，当频繁模式的数量很大时，这是非常低效的。有两种常用于查询感兴趣模式子集的方法类：

1.预处理一次查询许多范例：第一种方法是在低级别的支持下挖掘所有项目集，并以层次或格子数据结构的形式排列它们。由于第一阶段只需要以离线方式执行一次，因此可能有足够的计算资源。因此，低水平的支持被用来最大化第一阶段保存的模式数量。第二阶段可以用第一阶段做出的总结来解决许多疑问。

2.基于约束的模式挖掘：在这种情况下，用户指定的约束被直接推送到挖掘过程中。尽管对于每个查询来说，这种方法可能会比较慢，但它允许以比第一种方法更低的支持值挖掘模式。这是因为约束可以减少项目集发现算法的中间步骤中的模式大小，并且因此可以在比（无约束）预处理阶段更低的支持值处发现模式。

在本节中，将讨论这两种方法。

5.3.1 预处理一次查询许多范例

这种特殊的范例对于更简单的查询来说非常有效。在这种情况下，关键是首先确定所有频繁模式的支持度在一个很低的值。然后可以将结果项目集以数据结构的形式进行排列以供查询。最简单的数据结构是项目集格，它可以被视为查询的图形数据结构。但是，项目集也可以使用从信息检索文献中改编而来的数据结构来查询，这些数据结构使用词袋表示法。这两个选项将在本章中探讨。

5.3.1.1利用项目集格

正如前一章所讨论的，项目集的空间可以表示为一个格。为了方便起见，前一章的图4.1被复制为图5.1。虚线边界上方的项目集很频繁，而边界下方的项目集不频繁。

在预处理一次查询许多范例中，项目集以尽可能低的支持度$s$开采，这样项目集的格（图）中的大部分频繁部分就可以存储在主存中。这个阶段是一个预处理阶段; 因此，运行时间不是主要考虑因素。格上的边被实现为用于高效遍历的指针。此外，散列表将项目集映射到图中的节点。格具有许多重要属性，例如向下关闭，这使得能够发现非冗余关联规则和模式。

这个结构可以有效地提供对最小支持度$minsup≥s$的许多查询的响应。一些例子如下：

1.要确定在特定水平的最小支持度包含集合X的所有项集，可以使用散列表映射到项目集X。然后，遍历格以确定X的相关超集并报告它们。通过使用相反方向的遍历，可以使用类似的方法确定X中包含的所有频繁项目集。

2.可以通过在用户指定的最小支持度上标识对其直接超集没有边的节点，在遍历期间直接确定最大项目集。

3.通过在预定数量的步骤中从X向上和向下遍历格结构，可以识别X中具有特定汉明距离的节点和特定的最小支持。

使用这种方法也可以确定非冗余规则。例如，对于任意的项目集$y^‘\subseteq y$，规则$X⇒Y$的信任和支持不大于规则$X \Rightarrow Y^‘$。 因此，规则$X \Rightarrow Y^‘$对于规则$X⇒Y$是多余的。这被称为严格冗余。此外，对于任何项目集$I$，规则$I-Y^‘ \Rightarrow Y^‘$对于规则$I-Y \Rightarrow Y$仅在信任方面是多余的。这被称为简单冗余。网格结构提供了一种有效的方法来从简单冗余和严格冗余两方面来识别这种非冗余规则。读者在查找这些规则时可以参考书目注释以了解具体的搜索策略。

5.3.1.2 利用数据结构进行查询

在某些情况下，最好使用磁盘驻留表示进行查询。在这些情况下，基于内存的格点遍历过程很可能是低效的。两种最常用的数据结构是倒排索引和签名表。使用这些数据结构的主要缺点是它们不允许对频繁模式集进行有序探索，就像格子结构一样。

本节中讨论的数据结构可以用于事务或项目集。但是，这些数据结构中的某些数据结构（如签名表）对于项目集特别有效，因为它们明确利用项目集之间的相关性进行有效索引。请注意，在项目集的情况下，相关性比原始事务更重要。下面将详细描述这两种数据结构。

**倒排索引：**倒排索引是用于检索稀疏集值数据的数据结构，例如文本的词袋表示。因为频繁模式也是在更大范围的项目上绘制的稀疏集合，所以可以使用倒排索引高效地检索它们。

每个项目集都被分配了一个唯一的项目集$id$。 这可以通过散列函数轻松生成。 这个项目集$id$与用于表示事务的$tid$类似。项目集本身可以存储在由项目集$id$索引的辅助数据结构中。该辅助数据结构可以是基于用来创建项目集$id$的相同散列函数的散列表。

倒排列表包含每个项目的列表。每个项目都指向一个项目集$id$的列表。该列表可以存储在磁盘上。图5.2给出了一个倒排列表的例子。倒置表示对包含小项目集合的查询特别有用。考虑包含$X$的所有项目集的查询，其中$X$是一小组项目。$X$中每个项目的倒置列表都存储在磁盘上。这些列表的交集是确定的。这提供了相关的项目集$id$，但不提供项目集。如果需要，可以从磁盘访问相关项目集并进行报告。为了实现这个目标，磁盘上的辅助数据结构需要使用恢复的项目集$id$来访问。这是倒置数据结构的额外开销，因为它可能需要随机访问磁盘。对于大型查询响应，这种方法可能不实际。

虽然倒置列表对包含小项目集合的查询有效，但它们对于较长项目集的相似性查询并不十分有效。倒排索引的一个问题是它独立处理每个项目，并且不利用项目集中项目之间明显的相关性。此外，完整项目集的检索比只有项目集$id$更具挑战性。对于这些情况，签名表就是应选的数据结构。

**签名表：**签名表最初设计用于对购物篮事务进行索引。因为项目集具有与事务相同的集合式数据结构，所以它们可用于签名表的上下文中。签名表格对于稀疏二进制数据特别有用，其中不同项目之间存在显着相关性。因为项目集根据相关性固有的定义，并且不同项目集之间具有较大重叠，所以签名表格在这样的场景中特别有用。

一个签名是一组项目。原始数据中的项目集合$U$被分割成$K$个签名集合$S_1 ... S_k$，使得$U =∪_{i=1}^KS_i$。$K$的值被称为签名基数。一个项目集$X$被认为在级别$r$激活一个签名$S_i$当且仅当$| S_i∩X | ≥r$。这个级别$r$被称为激活阈值。换句话说，该项目组需要有一个用户指定的与签名共同的项目最小数量$r$来激活它。

一个项目集的超坐标存在于$K$维空间中，其中$K$是签名基数。超坐标的每个维度都与特定签名具有唯一的对应关系，反之亦然。此维度的值为$0-1$，表示相应签名是否由该项目集激活。因此，如果项目被划分为$K$个签名${S_1，... S_K}$，则有$2^K$个可能的超坐标。每个项目集映射到唯一的超坐标，如由该项目集激活的一组签名定义的。如果$S_{i_1}，S_{i_2}，...，S_{i_l}$是项目集激活的特征集，那么可以通过设置$l≤K$维$\left\{i_1，i_2，... i_l\right\}$超坐标为1，其余维度为0来定义该项目集的超坐标。因此，该方法创建了多对一映射，其中多个项目集可映射到相同的超坐标中。对于高度相关的项目集，只有少量的签名将被项目集激活，前提是将$U$划分为签名旨在确保每个签名包含相关项目。

签名表包含一组$2^K$个条目。签名表中的一个条目对应于每个可能的超坐标。这将根据项目集到超坐标的映射创建项目集的严格划分。这种分区可以用于相似性搜索。签名表可以存储在主存储器中，因为当$K$很小时，不同的超坐标的数量可以映射到主存储器。例如，当$K$被选择为20时，超坐标的数量约为一百万。由签名表的每个条目索引的实际项目集存储在磁盘上。签名表中的每个条目指向列表包含由该超坐标索引的项集的页面。签名表如图5.3所示。

签名可以理解为来自通用项目$U$的一小部分项目。因此，如果每个签名中的项目紧密相关，则项目集可能激活少量签名。这些签名提供了该项目组购买行为的近似模式的概念。因此，将项目聚类为签名至关重要，以便满足两个标准：

1.群集$S_i$中的项目是相关的。这确保了更具辨别性的映射，从而提供更好的索引性能。

2.每个集群内项目的总体支持类似。这对确保签名表是平衡的是必要的。

为了构建签名表，构建一个图，使图的每个节点对应一个项目。对于频繁的每一对项目，都会将边缘添加到图形中，并且边缘的权重是该对项目支持的函数。另外，节点的权重是特定项目的支持。希望确定将该图形聚类为$K$个分区，以便跨越分区的边缘的累积权重尽可能小并且分区平衡良好。减少分区边缘的权重可确保将相关的项目组合在一起。分区应该尽可能平衡，以便映射到每个超坐标的项目集尽可能平衡。因此，这种方法将项目转换成可以聚类到分区的相似度图。可以使用各种聚类算法将图分成项目组。在第19章讨论的任何图形聚类算法如$METIS$，可用于此目的。书目注释还包含指向签名表构造的一些方法的指针。

在签名确定之后，可以使用项目集的超坐标来定义数据的分区。每个项目集都属于由其超坐标定义的分区。与倒排列表的情况不同，项目集明确存储在该列表中，而不仅仅是它们的标识符。这确保了不需要访问辅助数据结构来明确地恢复项目集。这就是签名表可以用来恢复项目集本身的原因，而不仅仅是项目集的标识符。

签名表能够处理通过倒排列表无法有效解决的常规相似性查询。令$x$为项目集与目标$Q$相匹配的项数，$y$为与目标$Q$不同的项数。对于固定目标记录$Q$，签名表能够处理满足以下两个属性的形式为$f(x，y)$的相似函数：

$\frac{\Delta f(x,y)}{\Delta x}\ge0\tag{5.2}$

$\frac{\Delta f(x,y)}{\Delta x}\leq 0\tag{5.3}$

这被称为单调性。这些直观的函数条件可以确保匹配数量函数是一个递增函数，而汉明距离函数是递减函数。 虽然匹配函数和汉明距离明显满足这些条件，但可以证明其他用于逐个集合相似性的函数（例如余弦和$Jaccard$系数）也满足它们。例如，设$P$和$Q$是两个项目集中的项目集合，其中$Q$是目标项目集。那么，余弦函数可以用$x$和$y$表示如下：

$Cosine(P,Q)=\frac{x}{\sqrt{|P|}\sqrt{|Q|}}$

$=\frac{x}{\sqrt{2x+y-|Q|}\sqrt{|Q|}}$

$Jaccard(P,Q)=\frac{x}{x+y}$

这些函数是关于x的递增函数，y的递减函数。这些属性很重要，因为它们允许根据参数的边界在相似性函数上计算边界。换句话说，如果$\gamma$是x值的上界，$\theta$是y值的下界，那么可以证明$f(\gamma，\theta)$是函数$f(x，y)$的上界。这对于实现相似性计算的分支定界方法很有用。

设Q是目标项目集。计算从Q到每个超坐标内项目集的匹配和汉明距离的界限。这些界限可以表示为目标Q激活阈值和签名选择的函数。计算这些界限的精确方法在书目注释中的指针中描述。假设匹配的界限为$x_i$，距离的界限为第i个超坐标$y_i$。这些用于确定目标与第i个超坐标索引的任意目集之间的相似度$f(x，y)$的界限。由于单调性，该第i个超坐标的界限为$B_i = f(x_i，y_i)$。超坐标以边界$B_i$的递减顺序排序。Q与这些超坐标所指向的项目集的相似度按此排序顺序进行计算。到目前为止找到的最近的项目集是动态维护的。当到超坐标的界限$B_i$比到目标为止最近的项目组的相似度值更低（更差）时，该过程终止。此时，报告迄今为止找到的最近的项目集。

5.3.2 模式挖掘中的约束

本章到目前为止所讨论的方法都是为具有特定项目限制的检索查询而设计的。然而，在实际中，约束条件可能更为一般化，并且无法用任何特定的数据结构轻松解决。在这种情况下，可能需要将约束条件直接添加到挖掘过程中。

在所有以前的方法中，使用了预处理一次查询许多范例; 因此，查询过程受到在预处理阶段选择的初始最小支持度的限制。虽然这种方法的优点是为查询响应提供在线功能，但当约束导致删除大多数项目集时，它有时并不奏效。 在这种情况下，可能需要比最初预处理阶段合理选择的低得多的最低支持水平。将约束加入挖掘过程的优点在于约束可用于在执行频繁模式挖掘算法期间删除许多中间项目集。这允许使用更低的最低支持水平。这种灵活性的代价是，当数据集非常大时，生成的算法不再被认为是真正的在线算法。

例如，考虑将不同项目标记为不同类别的场景，例如零食，乳制品，烘焙产品等。希望确定模式，使所有项目属于同一类别。显然，这是发现潜在模式的一个制约因素。尽管可能首先将所有模式包含在内，然后过滤到相关模式，但这不是一个有效的解决方案。如果在预处理阶段挖掘的模式数量不超过$10^6$个，并且约束的选择性水平超过$10^{-6}$，那么返回的最终集合可能是空的，或者太小。

文献中已经开发了许多方法来直接在挖掘过程中解决这些约束。这些约束根据它们对挖掘算法的影响被分为不同的类型。众所周知的约束类型的一些例子包括简洁，单调，反单调和可转换。这些方法的详细描述超出了本书的范围。书目部分包含许多这些算法的指针。

5.4工作中的关联：应用

关联模式挖掘在各种各样的真实场景中有许多应用。本节将简要讨论一些这些应用。

5.4.1 与其他数据挖掘问题的关系

关联模型与其他数据挖掘问题密切相关，例如分类，聚类和异常值检测。关联模式可用于为这些数据挖掘问题提供有效的解决方案。本节将简要探讨这些关系。有关这些不同数据挖掘问题的许多相关算法在章节中也会讨论。

5.4.1.1 分类的应用

关联模式挖掘问题与分类密切相关。基于规则的分类器与关联规则挖掘密切相关。这些类型的分类器将在第10章的10.4部分详细讨论，这里只提供简要概述。

考虑规则$X⇒Y$，其中X是前提，Y是结果。在关联分类中，结果Y是与类变量相对应的单个项目，并且前提包含特征变量。这些规则是从训练数据中挖掘出来的。通常情况下，规则不是由传统的支持和信任度量来确定的。相反，需要确定关于不同类别的最具识别能力的规则。例如，考虑项目集X和两个类$c_1$和$c_2$。直观地说，如果规则$X⇒C_1$和$X⇒C_2$的绝对差异尽可能大，那么项目集X就可以区分这两个类别。因此，挖掘过程应该确定这样的区分规则。

有趣的是，已经发现，即使是对分类问题的关联框架的相对简单的修改也是非常有效的。这种分类器的一个例子是基于关联的CBA分类框架。关于基于规则的分类器的更多细节将在第10章的10.4部分讨论。

5.4.1.2 群集的应用

因为关联模式决定了高度相关的属性子集，所以它们可以在离散化之后应用于定量数据以确定数据中的密集区域。$CLIQUE$算法在第7章的7.4.1部分被讨论，利用离散化将量化数据转化为二进制。在转换的数据上发现关联模式。与这些区域重叠的数据点被报告为子空间群集。当然，这种方法报告了彼此高度重叠的群集。尽管如此，所得到的组对应于数据中的密集区域，这提供了关于基础聚类的重要见解。

5.4.1.3 离群值检测的应用

关联模式挖掘也被用于确定市场购物篮数据中的异常值。这里的关键思想是异常值被定义为不被数据中大多数关联模式“覆盖”的事务。据说当相应的关联模式包含在事务中时，事务被关联模式覆盖。这种方法在数据高维且传统基于距离的算法不易使用的情况下特别有用。由于事务数据具有固有的高维度，因此这种方法特别有效。这个方法在第9章的9.2.3部分中详细讨论。

5.4.2 市场购物篮分析

关联规则挖掘问题最初提出的原型问题是购物篮分析。在这个问题中，需要确定关于顾客购买行为的规则。这些规则的知识对于零售商可能非常有用。例如，如果关联规则显示出售啤酒意味着销售尿布，则商家可以使用这些信息来优化他或她的货架布置和促销决策。特别是，有趣或意想不到的规则对于购物篮分析来说是最具信息量的。市场购物篮分析的许多传统和替代模型都集中在这些决策上。

5.4.3 人口统计和分析

一个密切相关的问题是使用人口统计资料来提出建议。例子是在第4章的4.6.3部分谈论过的。

$Age[85,95] \Rightarrow Checkers$

其他人口统计学属性（如性别或邮政编码）可用于确定更精确的规则。这些规则被称为配置文件关联规则。配置文件关联规则对目标市场营销决策非常有用，因为它们可用于识别特定产品的相关人群细分。配置文件关联规则可以按照与分类规则类似的方式进行查看，不同之处在于，规则的前提通常会标识配置文件分段，并且随后会标识用于目标市场营销的人口分段。

5.4.4 推荐和协作过滤

上述应用程序都与推荐分析和协作过滤的通用问题密切相关。在协同过滤中，这个想法是根据其他类似用户的购买行为向用户提出建议。在这种情况下，本地化模式挖掘特别有用。在局部模式挖掘中，想法是将数据聚类成段，然后确定这些段中的模式。来自每个细分市场的模式通常更能抵抗来自全球数据分布的影响，并且能够更清晰地了解志同道合的客户中的模式。例如，在电影推荐系统中，诸如Gladiator、Nero、Julius Caesar等电影名称的特定模式在全球基础上可能没有足够的支持。但是，在对历史电影感兴趣的志趣相投的客户中，这种模式可能会得到充分的支持。此方法用于协作过滤等应用程序。由于需要同时确定聚类段和关联规则，因此局部模式挖掘的问题更具挑战性。书目部分包含指向这种本地化模式挖掘方法的指针。协作过滤在第18章的18.5部分详细讨论。

5.4.5 网页日志分析

网页日志分析是模式挖掘方法的常见方案。例如，会话期间访问的一组页面与包含交易的市场购物篮数据集没有区别。当频繁访问一组网页时，这提供了有关用户行为与网页相关性的有用见解。站点管理员可以利用这些见解来改进网站的结构。例如，如果一对网页页面在会话中经常一起访问但目前没有链接在一起，那么在它们之间添加链接可能会有所帮助。网页日志分析的最复杂形式通常与日志的时间方面一起工作，而不是频繁项目集挖掘的集合框架。这些方法将在第15章和第18章中详细讨论。

5.4.6 生物信息学

生物信息学中的许多新技术（如微阵列和质谱技术）允许收集各种非常高维的数据集。这种数据的典型例子是基因表达数据，其可以表示为$n×d$矩阵，其中列d的数量与典型的市场购物篮应用相比非常大。一个微阵列应用程序包含十万列的情况并不少见。在这些数据中发现频繁模式在发现由这些数据集编码的关键生物学特性方面有许多应用。对于这种情况，长模式挖掘方法（如最大和封闭模式挖掘）非常有用。实际上，在书目注释中讨论的许多方法都是专门为这些数据集设计的。

频繁模式挖掘算法已被推广到更复杂的数据类型，如时态数据，空间数据和图形数据。本书包含这些复杂数据类型的不同章节。这里提供了对这些更复杂的应用程序的简要讨论：

1.时间网页日志分析：使用来自网页日志的时间信息极大地丰富了分析过程。例如，某些访问模式可能会在日志中频繁发生，并且这些模式可以用来构建事件预测模型，以防从当前事件模式中预测未来事件。

2.空间共位模式：空间共位模式提供了有关不同个体之间空间相关性的有用见解。频繁模式挖掘算法已被推广到这种情况。参考第16章。

3.化学和生物图应用：在许多真实场景中，如化学和生物化合物，结构模式的确定提供了关于这些分子性质的见解。这样的模式也被用来创建分类模型。这些方法在第17章讨论。

4.软件缺陷分析：计算机程序的结构通常可以表示为调用图。对调用图中的频繁模式的分析以及与这些模式的主要偏差提供了有关底层软件中的错误的见解。

上述许多应用程序将在本书后面的章节中讨论。

5.5 总结

为了在数据驱动型应用程序中有效地使用频繁模式，创建基本模式的简明摘要至关重要。这是因为返回模式的数量可能非常大，难以解释。已经设计了许多方法来创建频繁模式的压缩摘要。最大模式提供了一个简洁的总结，但在基础模式的支持方面是有损的。通常可以通过在频繁模式挖掘算法中引入不同种类的修剪策略来有效地确定它们。

封闭模式提供了对潜在频繁项目集的无损描述。另一方面，从封闭模式获得的压缩并不像从使用最大模式获得的压缩那么重要。“几乎关闭”项目集的概念允许良好的压缩，但是在此过程中会有一定程度的信息丢失。压缩项目集的另一种方式是聚集项目集，以便所有项目集可以在特定代表的预定距离内表达。

项目集的查询处理在许多应用程序的上下文中很重要。例如，项目集格可以用来解决项目集上的简单查询。在某些情况下，格子可能不适合主存。对于这些情况，可能需要使用磁盘驻留数据结构，例如倒排索引或签名表。在约束条件是任意的或具有高选择性的情况下，可能需要将约束直接加入挖掘过程。

频繁模式挖掘有很多应用，包括将其用作其他数据挖掘问题的子例程。其他应用包括市场购物篮分析，文件分析，推荐，网页日志分析，空间数据和化学数据。本书后面的章节会讨论许多这些应用程序。

5.6 书目注释

在[82]中提出了第一种最大模式挖掘算法。随后，DepthProject [4]和GenMax [233]算法也被设计用于最大模式挖掘。DepthProject显示深度优先方法在确定最大模式方面有几个优点。MAFIA [123]中使用垂直位图来压缩底层tid列表的大小。封闭模式挖掘问题最早在[417]中提出，其中提出了一种基于Apriori的算法，称为A-Close。随后，提出了许多算法，如CLOSET [420]，CLOSET + [504]和CHARM [539]用于闭频繁模式挖掘。最后这些算法使用垂直数据格式以更高效的方式挖掘长模式。对于非常高维数据集的情况，分别以CARPENTE和COBBLER的形式提出了封闭模式挖掘算法[413,415]。另一种称为图案融合[553]的方法将不同的图案片段融合在一起以形成长图案。

[125]中的工作展示了如何使用演绎规则为所有频繁项集构造一个最小表示。在[126]中可以找到关于频繁项集的精简表示的优秀调查。随后提出了许多方法来近似δ自由度形式的闭合[107]。项目集压缩的信息论方法已在[470]中讨论过。

使用基于聚类的方法进行压缩的重点在于项目集而不是事务。[515]中的工作根据它们的相似性和频率对模式进行聚类，以创建模式的精简表示。在[403]中讨论了用于查找最佳覆盖项集的贪心算法中使用的子模性。

在[37]中讨论了使用项目集格进行交互式规则探索的算法。本文还讨论了简单冗余和严格冗余的概念。这种方法也被推广到配置文件关联规则的情况[38]。本章介绍的倒排索引可以在[441]中找到。在[41]中可以找到关于特定于购物篮的实施的讨论，以及签名表。[359]研究了用于存储和查询频繁项集的光盘结构。

已经为模式挖掘开发了各种基于约束的方法。简洁约束是最容易解决的，因为它们可以直接推送到数据选择中。单调约束只需要检查一次以限制模式增长[406,332]，而反单调约束需要深入到模式挖掘过程中。另一个约束 可以通过按升序或降序排列项目来限制图案增长来解决模式挖掘的形式，即可转换约束[422]。

CLIQUE算法[58]显示了关联模式挖掘方法如何用于聚类算法。基于规则的分类的CBA算法在[358]中讨论。基于规则的分类方法的调查可以在[115]中找到。频繁模式挖掘问题也被用于非常长的交易中的异常值检测[263]。 频繁模式挖掘也被用于生物信息学领域[413,415]。局部关联的确定[27]对于推荐和协作过滤问题非常有用。在生物信息学应用环境中挖掘长频繁模式的方法可以在[413,415,553]中找到。关联规则也可以用来发现空间共址模式[388]。 Aggarwal和Wang [26]详细讨论了图形应用的频繁模式挖掘方法，如软件bug分析和化学和生物数据。

5.7 练习

1.考虑下表中的事务数据库：

确定支持级别为2,3和4的事务数据库中的所有最大模式。

2.编写一个程序，从一组频繁模式中确定最大模式集合。

3.对于练习1的事务数据库，确定支持级别为2,3和4的所有封闭模式。

4.编写一个计算机程序，从一组频繁模式中确定一组关闭的频繁模式。

5.考虑下表中的事务数据库：

确定支持级别3,4和5的所有频繁最大和封闭模式。

6.编写一个计算机程序来实现用于从一组项目集中查找代表性项目集的贪心算法。

7.编写一个计算机程序来实现一组市场篮子上的倒排索引。实现一个查询来检索包含一组特定项目的所有项目集。

8.编写一个计算机程序，在一组市场购物篮上实现一个签名表。根据余弦相似度实现一个查询来检索距目标购物篮最近的购物篮。