对聚合数据集进行抽样
Sampling on a aggregated dataset
输入是一个数据集，其中每一行都包含一个事件，比如点击。会员 ID 是唯一 ID。
样本数据：
M1,100
M2,100
M3,50
M4,50
目标是抽取 1% 的点击次数，其中总点击次数是通过汇总所有成员 ID 的所有点击次数得出的。
如果我想在样本数据集上抽样 1%，我希望应用一种技术，对点击计数进行随机抽样并产生 1% 或 3 次点击，例如：
M1, 1
M2, 1
M4, 1
或一些其他组合，其中成员间的点击总和为 1%。
一种基本方法是分解输入中的所有条目并将其作为数据，然后从中抽取 1%。如果有数百万的会员点击次数达 100 次，这将非常 slow/inefficient。在不需要数据爆炸的情况下寻找更好的解决方案？
似乎显而易见的事情是从用户中抽样，每个用户的概率与他们的点击次数成正比，然后 select 给定用户随机均匀点击。在您给出的示例中，这意味着 select 概率为 100/300、100/300、50/300 和 50/300 的用户，然后 select 来自给定用户的点击。
您可以通过生成一个介于 0 和 1 之间的随机数 p，然后找到最小的 k（k = 1， 2, 3, ... #weights) 使得从 1 到 k 的权重之和小于或等于 p。
找到 k 的一种有效方法是构造一个权重的部分和列表（即 0、w1、w1 + w2、w1 + w2 + w3 ...），然后进行二分查找（不是线性）在该列表上。二分搜索将产生每个样本的时间，该时间随权重数量（在您的情况下是用户）呈对数增长，而线性搜索将产生线性增长。
编辑：一个例子。给定 n = 10 个用户，分别有 N = (100, 160, 200, 20, 500, 550, 400, 300, 120, 80) 个事件。总事件数 = 2430，权重 w = (10/243, 16/243, 20/243, 2/243, 50/243, 55/243, 40/243, 10/81, 4/81, 8/243) .权重的部分总和 S = (0, 10/243, 26/243, 46/243, 16/81, 98/243, 17/27, 193/243, 223/243, 235/243, 1)。 （注意：我之前弄错了；顺序应该是 (0, w1, w1 + w2, w1 + w2 + w3, ..., w1 + ... + w[n - 1], 1)。）
给定一个介于 0 和 1 之间的随机数 x，找到（通过二进制搜索）部分和的索引，使得 S[i] <= x < S[i + 1]。然后 select 从用户 i 的 N[i] 个事件中均匀地随机抽取一个事件。
我假设您可以从每个用户的事件中执行二进制搜索和抽样，所以我不会写出那部分。
EDIT2：修复了部分和列表的公式。该列表有 n + 1 个元素；搜索 i 使得 S[i] <= x < S[i + 1] 将因此产生 i = 1, 2, 3, ..., n。最后一个元素 1 永远不会被 selected，假设随机数总是小于 1。
输入是一个数据集，其中每一行都包含一个事件，比如点击。会员 ID 是唯一 ID。 样本数据： M1,100 M2,100 M3,50 M4,50 目标是抽取 1% 的点击次数，其中总点击次数是通过汇总所有成员 ID 的所有点击次数得出的。 如果我想在样本数据集上抽样 1%，我希望应用一种技术，对点击计数进行随机抽样并产生 1% 或 3 次点击，例如： M1, 1 M2, 1 M4, 1 或一些其他组合，其中成员间的点击总和为 1%。
一种基本方法是分解输入中的所有条目并将其作为数据，然后从中抽取 1%。如果有数百万的会员点击次数达 100 次，这将非常 slow/inefficient。在不需要数据爆炸的情况下寻找更好的解决方案？
似乎显而易见的事情是从用户中抽样，每个用户的概率与他们的点击次数成正比，然后 select 给定用户随机均匀点击。在您给出的示例中，这意味着 select 概率为 100/300、100/300、50/300 和 50/300 的用户，然后 select 来自给定用户的点击。
您可以通过生成一个介于 0 和 1 之间的随机数 p，然后找到最小的 k（k = 1， 2, 3, ... #weights) 使得从 1 到 k 的权重之和小于或等于 p。
找到 k 的一种有效方法是构造一个权重的部分和列表（即 0、w1、w1 + w2、w1 + w2 + w3 ...），然后进行二分查找（不是线性）在该列表上。二分搜索将产生每个样本的时间，该时间随权重数量（在您的情况下是用户）呈对数增长，而线性搜索将产生线性增长。
编辑：一个例子。给定 n = 10 个用户，分别有 N = (100, 160, 200, 20, 500, 550, 400, 300, 120, 80) 个事件。总事件数 = 2430，权重 w = (10/243, 16/243, 20/243, 2/243, 50/243, 55/243, 40/243, 10/81, 4/81, 8/243) .权重的部分总和 S = (0, 10/243, 26/243, 46/243, 16/81, 98/243, 17/27, 193/243, 223/243, 235/243, 1)。 （注意：我之前弄错了；顺序应该是 (0, w1, w1 + w2, w1 + w2 + w3, ..., w1 + ... + w[n - 1], 1)。）
给定一个介于 0 和 1 之间的随机数 x，找到（通过二进制搜索）部分和的索引，使得 S[i] <= x < S[i + 1]。然后 select 从用户 i 的 N[i] 个事件中均匀地随机抽取一个事件。
我假设您可以从每个用户的事件中执行二进制搜索和抽样，所以我不会写出那部分。
EDIT2：修复了部分和列表的公式。该列表有 n + 1 个元素；搜索 i 使得 S[i] <= x < S[i + 1] 将因此产生 i = 1, 2, 3, ..., n。最后一个元素 1 永远不会被 selected，假设随机数总是小于 1。