algorithm - 创建尽可能接近均匀分布的样本的算法？

Question

我有一个带有日期的大型数据数据库。有很大的差距和没有差距的大块数据。我想获取这些数据的样本，以使日期尽可能均匀分布（即尽可能分散）。

例如，如果日期是[1, 2, 3, 4, 100]并且我想对 3 个元素进行采样，那么理想的样本将是[1, 50.5, 100]并且我会采用[1, 4, 100].

这是现有算法的已知问题吗？

我将这个问题形式化的尝试是：给定一个数组 A，选择一个子数组 B 使得以下内容最小化：

Σabs(B _i - (min(A) + i * (max(A) - min(A)) / (len(B) - 1))

标签： algorithmoptimization

Answer 1

您应该能够将此建模为分配问题。用顶点集 A 和 B 构造一个二分图。从 A_i 到 B_j 的边的权重类似于

abs(j / (|B| - 1) - (A_i - min(A) / (max(A) - min(A)))

在哪里A_0 <= A_1 <= ... <= A_{|A|-1}。

请注意，在您的问题中，图形很密集，因此很容易表示为权重 W[i,j] 的矩形矩阵。不需要明确的顶点或边数据结构。

最小权重匹配将识别样本的 A 元素。

有几种有效的算法可以解决分配问题。也许最著名的是匈牙利方法。这可以用 O(n^3) 运行时间来实现。实际上我隐约记得在这篇文章中有一个运行时间为 O(n^2 log n) 的版本。我现在无法访问它，所以无法检查。）我在 90 年代使用的一个实现在标准台式机上运行了几秒钟，因为 n = ~10k 的问题。现在应该可以做得更好。

你没有给出“大”的定义。如果数据库太大而无法作为单个分配问题处理，您可能可以通过分块工作来获得合理的结果。