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

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))

Answer 1

您应该能够将其建模为 assignment problem .构造一个带有顶点集 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) 运行时间来实现。其实我依稀记得在this text有一个运行时间为 O(n^2 log n) 的版本。我现在无法访问它，所以无法检查。)我在 90 年代使用的一个实现在标准台式机上运行了几秒钟就出现了 n = ~10k 的问题。现在应该可以做得更好。

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