频繁偏序与地名词典：概念、算法与应用

# 频繁偏序与地名词典：概念、算法与应用 ## 1. 频繁偏序的定义与背景 频繁偏序（Frequent Partial Orders，FPO）是在给定一组偏序集合和阈值的情况下定义的。设存在一个包含 $n$ 个关于集合 $S$ 的偏序集合 $D$，以及一个阈值 $\theta \leq n$，若一个偏序 $P$ 与 $D$ 中超过 $\theta$ 个偏序兼容，则称 $P$ 为频繁偏序。通常情况下，$D$ 包含的是关于 $S$ 或其任意子集的全序。 频繁偏序的研究源于关联规则挖掘对时间信息的应用拓展。早期的研究主要集中在挖掘数据库中频繁出现的项集序列，这些序列可看作是对完整项集的偏序。之后，又有关于从事件序列中挖掘频繁事件片段的研究，这里的事件片段也是一种偏序。不过，早期的研究大多未明确将挖掘出的模式称为偏序。直到后来，才有论文专门讨论寻找能对输入序列集进行简洁描述的偏序集合的问题。而本文所定义的寻找频繁偏序的问题，最早由相关研究提出，并给出了在字符串数据库中寻找频繁闭偏序的高效算法，这里的闭偏序概念与频繁闭项集类似。 ## 2. 频繁模式挖掘基础 频繁模式挖掘的基本思想可形式化描述为：给定数据库 $D$、模式类 $P$ 和阈值 $\theta$，找出所有在 $D$ 中被超过 $\theta$ 行支持的 $P$ 的实例。支持度的精确定义取决于 $D$ 的内容和模式类 $P$。对于频繁偏序，模式类是关于某个固定集合 $S$ 的所有偏序集合，数据库 $D$ 可以包含关于 $S$ 的全序或偏序。所有与偏序 $P$ 兼容的 $D$ 中的序构成 $P$ 的支持集，记为 $s(P)$。给定 $D$ 和阈值 $\theta$，问题就转化为找出所有满足 $|s(P)| \geq \theta$ 的偏序 $P$。 如果一个模式不能在不减小其支持集大小的情况下进行扩充，则称该模式为闭模式。根据这个定义，在数据库 $D$ 中，若对于所有的 $u, v \in S$，都有 $|s(P \cup (u, v))| < |s(P)|$，则偏序 $P$ 是闭的。通常认为，只寻找频繁闭模式是有意义的，因为非闭模式包含的信息较少，但与闭模式具有相同的支持度，可被视为同样“可靠”。下面将介绍两种寻找频繁闭偏序的方法。 ## 3. 使用频繁项集挖掘算法寻找频繁闭偏序 自 20 世纪 90 年代初关联规则挖掘和频繁项集发现被提出以来，这一领域得到了广泛研究，目前存在大量高效的挖掘频繁闭项集的算法。如果输入数据格式合适，这些算法都可用于寻找频繁闭偏序。 假设数据库 $D$ 包含关于集合 $S$ 的全序，通常每个全序 $T \in D$ 以符号列表的形式给出。例如，$T = \langle a, b, c, d, e \rangle$ 表示在 $T$ 中 $a$ 排在第一位，$b$ 排在第二位，依此类推。这种列表表示法是一种紧凑且直观的全序表示方式，但不能直接用于频繁项集挖掘算法，因为这些算法只考虑符号的出现，而不考虑其在列表中的相对位置。 任何序关系都可以表示为有序对 $(u, v)$ 的集合。当在 $T$ 的列表表示中 $u$ 出现在 $v$ 之前时，有序对 $(u, v)$ 属于 $T$。例如，上述全序 $T$ 的集合表示为： \[ T = \{ (a, b), (a, c), (a, d), (a, e), (b, c), (b, d), (b, e), (c, d), (c, e), (d, e) \} \] 这种表示法与列表表示法的不同之处在于，它将符号对作为“项”。因此，如果两个全序具有相同的有序对 $(u, v)$，则它们在 $u$ 和 $v$ 的顺序上是一致的。 给定以列表表示的全序数据库 $D$，将 $D$ 中的每个成员转换为集合表示，得到的数据库记为 $\hat{D}$。$\hat{D}$ 的每一行是一个有序对 $(u, v)$ 的集合，这些有序对构成了 $D$ 中的一个全序 $T$。这种输入表示方式使得在 $\hat{D}$ 中，给定阈值 $\theta$ 下的每个频繁闭项集（有序对 $(u, v)$ 的集合）实际上都可以解释为一个频繁闭偏序。一个项集 $I$ 是闭的，当且仅当不能在不减小其支持集大小的情况下向 $I$ 中添加更多项。 需要注意的是，找到频繁闭项集非常重要，因为频繁项集可能并不对应于偏序。闭性保证了得到的有序对 $(u, v)$ 集合构成一个传递关系，而这是偏序所必需的。 然而，使用集合表示法寻找频繁偏序存在一些缺点： - **存储需求大**：$\hat{D}$ 的存储需求比 $D$ 大得多，因为每个具有 $l$ 个符号列表表示的全序必须替换为一个包含 $\frac{1}{2}l(l - 1)$ 个元素的集合。 - **可能不稀疏**：$\hat{D}$ 可能不是稀疏的，即每行（全序）中的项数与总项数相比不一定小，这可能导致频繁项集挖掘算法的性能不佳。 - **通常不需要完整偏序**：一般情况下，并不需要完整的偏序 $P$，很多时候找到其传递约简 $tr(P)$ 就足够了。$tr(P)$ 保留了 $P$ 中的所有序信息，更适合用于分析。例如，在将偏序可视化为有向无环图时，通常使用 $tr(P)$ 更好。虽然可以在得到频繁项集后计算传递约简，但这是另一个计算密集的步骤。而且，直接挖掘传递约简可以更高效地找到频繁偏序。 下面是使用频繁项集挖掘算法寻找频繁闭偏序的步骤总结： 1. 将以列表表示