random - 对聚合数据集进行采样
问题描述
输入是一个数据集,其中每一行都包含一个事件,比如点击。成员 ID 是唯一 ID。样本数据:M1,100 M2,100 M3,50 M4,50 目标是对 1% 的点击进行采样,其中总点击数是通过对所有成员 ID 的所有点击求和得出的。如果我希望在样本数据集上采样 1%,我希望应用一种随机采样点击计数并产生 1% 或 3 次点击的技术,例如:M1、1 M2、1 M4、1 或其他组合,其中成员之间的点击总和为 1%。
一种基本方法是分解输入中的所有条目并将其作为数据,然后从中抽取 1%。如果有数百万点击数为 100 的成员,这将非常缓慢/低效。正在寻找不需要数据爆炸的更好解决方案?
解决方案
似乎显而易见的事情是从用户中抽样,每个用户的概率与他们的点击次数成正比,然后为给定的用户随机均匀地选择一次点击。在您给出的示例中,这意味着选择概率为 100/300、100/300、50/300 和 50/300 的用户,然后从给定用户中选择一次点击。
您可以通过生成介于 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]。然后从用户 i 的 N[i] 个事件中均匀地随机选择一个事件。
我假设您可以执行二进制搜索和每个用户事件的采样,所以我不会写出那部分。
EDIT2:修正了部分总和列表的公式。该列表有 n + 1 个元素;搜索 i 使得 S[i] <= x < S[i + 1] 将因此产生 i = 1, 2, 3, ..., n。假设随机数始终小于 1,则永远不会选择最后一个元素 1。
推荐阅读
- windows - 使用 MFC 函数播放内存中的原始声音数据
- python - 如何将没有控制台的 python 3 应用程序的 C 扩展标准输出重定向到文件?
- jvm - 为什么 GraalVM (SubstrateVM) 本机映像在运行时使用的内存比相应的 JIT 构建少得多?
- python - 如何将 NUKE API 添加到 Visual Studio 代码?
- javascript - 如何防止我的导航菜单在移动视图中覆盖我的网站内容?
- python - 无法将 Keras Generator 图像传递给人脸识别
- json - 在成员切片类型中使用自定义 UnmarshalJSON 解组 JSON 失败
- r - 使用变量在select(dplyr)中选择多个列
- javascript - 如何从 Javascript 获取 AWS 静态文件 url?
- reactjs - 有没有办法使用 @apollo/react-hooks 访问多个 graphql 突变的选项