近10万种数据按照它们出现的频率随机选取的可行办法？

JennyFaceOff

假如我有近10万个id，它们出现的次数多得可达50多万次，少的则只有10几次或几次。我希望用一种方法，在这近10万个id里每次随机抽取一个，希望抽取到的概率和这些id出现的频率接近。有什么好的办法？
我会用python，如果有能够使用的库也可以说一说。如果条件放宽，一次性可以抽取多个，只要满足多次抽取下所得的id次数和出现频率相近也可以。
它们的出现次数按照降序排列大致是这样的：


差不多2万名左右就是6000多次，5万名左右是300多次，8万名左右就只有十几次了。
我目前的想法是把id按照频率划分成多个层级，但不知道有没有什么成熟的办法

有土

numpy.random.choice

超纯锑

去搜一下
重要抽样法 Importance Sampling
很多蒙特卡罗模拟相关课程都会讲

runnerchin

将出现次数以10为底取对数，转成int，作为档位。这样问题就简化为：10万个id，分为0-6一共7档，概率逐次增大，同一档的概率考虑为相同。然后roll第一次确定档位，再roll一次从同档的这组数据中公平抽取。

الطائر

简单的做法是依次求和，给每个 ID 分配一个数 S(i)，使得 S(i+1) - S(i) 为后一ID的出现次数 A(i)，其中 S(0) = 0 不在选择范围内。
所有 ID 出现次数的和 S(n) = ∑{1->n} A(i)，则每个 ID 的频率为 p(i) = A(i)/S(n)，累积频率 q(i) = S(i)/S(n) ，用 q(i) 划分区间查找即可。

即在区间 (0, 1] 之间随机取浮点数 r，取对数，查找大于等于 r 的最小 q(i)，那么 i 就是所求 ID。总之概率等于频率，不需要考虑排序问题。

某浩

不考虑效率的话，可以简单做
假如id和次数都已知
MAP<id, 次数>

把次数求和得到N，然后从0到N范围取随机数 random(0, N)。得到的数值在Map里找到区间，就能得到id

jasonkiddyuan

你这个一眼幂律分布函数
1. 拟合一个幂律函数的参数
2. 按照参数生成概率分布函数
3. 抽样

翎羽

小白想问一下这是一个计算机问题吗，数字太多所以跟内存什么的有关？从数学角度看好像没有什么困难，因为概率分布函数已经知道了

الطائر

الطائر 发表于 2023-12-14 22:49
简单的做法是依次求和，给每个 ID 分配一个数 S(i)，使得 S(i+1) - S(i) 为后一ID的出现次数 A(i)，其中 S( ...

举例：出现次数为 1, 8, 27, 125, 343, 1331, 2197 的未知顺序数据：

ID A    S    q        ln(S)
1  343  343  0.085069 5.837730
2  27   370  0.091765 5.913503
3  8    378  0.093750 5.934894
4  1331 1709 0.423115 7.443663
5  125  1834 0.454861 7.514254
6  1    1835 0.455109 7.514799
7  2197 4032 1.000000 8.302017

假设随机数 r = 0.450000，则 0.423115 < r < 0.454861，对应 ID 5。也可以计算 ln(r) + ln(4032) = 7.503510：如果 ID 按频率从小到大排序，取对数后更均匀。

3Psm

按一定规则选取就不叫随机选取了吧：（

lgyzero

ID的分布是固定的还是每次会变？
规定的我做过不等概率抽卡
就是提前生成一个表，记录每个ID起始数和终止数
然而随机一个数，剩下就是查找了。。

非常朴素的方法

JennyFaceOff

之前担心这么大的量用random.choice方法会很慢，但是没想到居然可以，暂时不重复造轮子了。如果之后有需要我就看看楼里的其他方法。

midearth

2楼正解，记得加上replace=False

mahoraga

numpy确实应该就可以，如果嫌慢还有一些优化过的库之类的，效率其实不用太担心，pandas应该也有包装过的采样方法，更复杂的scikit-learn里应该有现成的，总之如果不是为了自己练算法之类的不用重新造轮子

百响

权重随机数，2楼正解咯