机器算法验证 - 使用一组样本估计多组交集的大小 - 吾爱随笔录

我正在研究一种算法，该算法需要计算由至少 2 个集合的交集生成的集合的大小。进一步来说：

z = | A_{0} \cap \dots \cap A_{n} |

$z = \left |A_0 \cap \ldots \cap A_n \right |$

相交的集合是由 SQL 查询生成的，为了保持速度，我提前对每个查询进行计数，然后取计数最低的集合 ( ) 并将这些 ID 用作其余的大查询，因此交集有效地变为： $A_0$

z = | (A_{0} \cap A_{1}) \cap \dots \cap (A_{0} \cap A_{n}) |

$z = \left |\left ( A_0 \cap A_1 \right ) \cap \ldots \cap \left ( A_0 \cap A_n \right ) \right |$

即使这个策略也让我有一些相当大的查询要运行，因为有时可能很大。我处理这个问题的想法是随机抽取样本并将其与其余集合相交，然后再推断回对的正确估计。我的问题是：进行采样然后推断返回到值的最佳方法是什么，即，如果不完全准确，具有可预测的误差范围？ $\left | A_0 \right |$ $A_0$ $z$ $z$

这是我迄今为止尝试过的（在伪代码中）：

sample_threshold := 10000
factor := 1
if (len(A0) > sample_treshold) {
    factor = sample_threshold / len(A0)
}

// Take a random sample of size 10000 from A0

// Intersect all the other sets with the A0 sample, then with each other
working_set := A0
for i, a := range A {
    a = intersect(A0, a)
    working_set = intersect(working_set, a)
}

z := len(working_set) * (1 / factor)

此代码有效，但似乎始终高估z，样本量越小，估计值越高。此外，我不确定这将如何与两个以上的集合相交。

我希望这个问题是有道理的，让我知道是否可以进一步澄清。另外，如果这个问题离题或属于其他地方，请告诉我，我很乐意移动它。

根据比尔的评论，我进行了一些快速试验以显示样本量与错误。每个样本大小的存储桶运行 20 次，您可以看到有一个非常明显的趋势：