频繁模式挖掘中推动更严格约束

### 频繁模式挖掘中推动更严格约束 在数据挖掘领域，频繁项集挖掘是一项关键任务，它在关联规则、相关性分析、序列挖掘等众多数据挖掘任务中都发挥着重要作用。然而，挖掘所有频繁项集通常会产生大量结果，其中真正对用户有价值的项集往往只占一小部分。这不仅会导致挖掘效率低下，甚至在某些情况下变得不可行，还会使识别有价值的知识片段变得困难。因此，基于约束的挖掘范式应运而生，它可以聚焦于有价值的知识，减少挖掘的模式数量，并能深入到模式发现算法中以提高性能。 #### 1. 受限频繁模式挖掘的定义 - **基本概念**：设 $I = \{x_1, ..., x_n\}$ 是一组不同的文字，通常称为项，项是具有预定义属性（如价格、类型等）的对象。项集 $X$ 是 $I$ 的非空子集，如果 $|X| = k$，则 $X$ 称为 $k$ - 项集。项集上的约束是一个函数 $C : 2^I →\{true, false\}$，当且仅当 $C(I) = true$ 时，称项集 $I$ 满足约束。约束的理论定义为满足该约束的项集的集合：$Th(C) = \{X ∈2^I | C(X)\}$。事务数据库 $D$ 是项集 $t ∈2^I$ 的集合，通常称为事务。 - **支持度与频繁项集**：项集 $X$ 在数据库 $D$ 中的支持度，记为 $supp_D(X)$，是包含 $X$ 的事务的数量。给定用户定义的最小支持度 $\sigma$，如果 $supp_D(X) ≥\sigma$，则项集 $X$ 在 $D$ 中称为频繁项集。这定义了最小频率约束：$C_{freq}[D,\sigma](X) ⇔ supp_D(X) ≥\sigma$。当数据集和最小支持度阈值在上下文中明确时，我们简单地将频率约束表示为 $C_{freq}$。因此，频繁项集挖掘问题需要计算所有频繁项集的集合 $Th(C_{freq})$。一般来说，给定约束的合取 $C$，受限频繁项集挖掘问题需要计算 $Th(C_{freq}) ∩ Th(C)$。 #### 2. 相关工作和约束分类 - **Anti - monotone 约束**：给定项集 $X$，约束 $C_{AM}$ 是反单调的，如果 $\forall Y ⊆ X : C_{AM}(X) ⇒ C_{AM}(Y)$。频率约束是最著名的反单调约束示例。Apriori 算法利用频率的反单调性，如果项集 $X$ 不满足 $C_{freq}$，则 $X$ 的任何超集都不能满足 $C_{freq}$，因此可以进行剪枝。其他反单调约束可以很容易地深入到频繁项集挖掘计算中，因为它们的行为与 $C_{freq}$ 完全相同。 - **Succinct 约束**：简洁约束 $C_S$ 是指，项集 $X$ 是否满足它可以根据 $X$ 中的单元素项来确定。简洁约束是预计数可推的，即可以在候选生成时满足：这些约束通过用适当的（相对于 $C_S$）候选生成过程替换通常的生成 Apriori 过程，被推到逐层计算中。既是反单调又是简洁的约束可以在逐层计算开始之前（预处理时）完全推到计算中。 - **Monotone 约束**：给定项集 $X$，约束 $C_M$ 是单调的，如果 $\forall Y ⊇ X : C_M(X) ⇒ C_M(Y)$。由于频繁项集计算是以反单调的 $C_{freq}$ 为导向的，单调约束在计算中更难推动，并且在剪枝搜索空间方面效果较差。不过，最近的研究表明，通过结合项集搜索空间和输入数据库，使用 ExAnte 数据缩减技术，可以利用这两种相反类型约束的协同作用。 - **Convertible 约束**：可转换约束分为可转换反单调约束和可转换单调约束。可转换反单调约束 $C_{CAM}$ 是指存在项的顺序 $R$，使得当项集 $X$ 满足 $C_{CAM}$ 时，$X$ 的任何前缀也满足。可转换单调约束 $C_{CM}$ 是指存在项的顺序 $R$，使得当项集 $X$ 违反 $C_{CM}$ 时，$X$ 的任何前缀也违反。在相关研究中，引入了基于 FP - growth 的算法 FICA 和 FICM 来挖掘受限频繁项集，但这些算法存在一些局限性，如需要初始数据库和所有中间投影数据库都能放入主内存，并且难以充分利用不同约束的合取。 - **非可转换约束处理**：第一篇尝试解决如何推动非可转换约束问题的工作基于找到见证项集的概念，即通过测试见证项集是否满足约束来推断其他项集的属性，从而剪枝搜索空间。但该方法可能需要二次时间来找到见证项集，并且即使进行近线性时间搜索，也不能保证找到有助于剪枝的见证项集。 #### 3. 论文贡献 - **扩展约束分类**：扩展了频繁模式计算中可推动的约束的现有分类，展示了如何推动基于方差或标准差等严格约束。 - **改进可转换约束挖掘**：表明可以在逐层 Apriori 类计算中推动可转换约束，提出的算法优于先前基于 FP - growth 的算法。 - **提出通用算法**：提出了一种基于数据缩减技术的通用 Apriori 类算法，能够推动目前研究的所有可能类型的约束。 #### 4. 松散反单调约束 - **定义**：给定项集 $X$ 且 $|X| > 2$，约束是松散反单调的（记为 $C_{LAM}$），如果 $C_{LAM}(X) ⇒ ∃i ∈ X : C_{LAM}(X \ {i})$。 - **示例**：以方差约束为例，计算方差是许多统计分析中的重要任务，方差的定义为 $var(X) = \frac{\sum_{i∈X}(i - avg(X))^2}{|X|}$。基于方差的约束不是可转换的，但它是松散反单调的。例如，对于项集 $X$，如果它满足 $var(X.A) ≤ v$，那么去掉与 $avg(X.A)$ 距离最远的元素 $i$ 后，$var(\{X \ {i}\}.A) ≤ var(X.A) ≤ v$。类似地，可以证明基于标准差、无偏方差估计器、平均偏差等的约束也是松散反单调的。 - **分类更新**：常见约束的分类更新如下表所示： | Constraint | Anti - monotone | Monotone | Succinct | Convertible | CLAM | | --- | --- | --- | --- | --- |