Reservoir Sampling 蓄水池抽样算法,经典抽样

简介: 随机读取数据,如何保证真随机是不可能的,因为计算机的随机函数是伪随机的。 但是在不考虑计算机随机函数的情况下,如何保证数据的随机采样呢? 1.系统提供的shuffle函数   C++/Java都提供有shuffle函数,可以对容器内部的数据打乱,保持随机排序。

随机读取数据,如何保证真随机是不可能的,因为计算机的随机函数是伪随机的。

但是在不考虑计算机随机函数的情况下,如何保证数据的随机采样呢?

1.系统提供的shuffle函数

  C++/Java都提供有shuffle函数,可以对容器内部的数据打乱,保持随机排序。

  C++:

1 template <class RandomAccessIterator, class URNG>
2   void shuffle (RandomAccessIterator first, RandomAccessIterator last, URNG&& g);

  Java:

1 static void    shuffle(List<?> list);
2 static void    shuffle(List<?> list, Random rnd);

  这些函数对数量一定的数据的随机打乱顺序,并不能处理数量不定的数据流。

2.在序列流中取一个数,如何确保随机性,即取出某个数据的概率为:1/(已读取数据个数)

  假设已经读取n个数,现在保留的数是Ax,取到Ax的概率为(1/n)。

  对于第n+1个数An+1,以1/(n+1)的概率取An+1,否则仍然取Ax。依次类推,可以保证取到数据的随机性。

  数学归纳法证明如下:

    当n=1时,显然,取A1。取A1的概率为1/1。

           假设当n=k时,取到的数据Ax。取Ax的概率为1/k。

           当n=k+1时,以1/(k+1)的概率取An+1,否则仍然取Ax

    (1)如果取Ak+1,则概率为1/(k+1);

    (2)如果仍然取Ax,则概率为(1/k)*(k/(k+1))=1/(k+1)

  所以,对于之后的第n+1个数An+1,以1/(n+1)的概率取An+1,否则仍然取Ax。依次类推,可以保证取到数据的随机性。

  代码如下:

 1 //在序列流中取一个数,保证均匀,即取出数据的概率为:1/(已读取数据个数)
 2 void RandNum(){    
 3     int res=0;
 4     int num=0;
 5     num=1;
 6     cin>>res;
 7 
 8     int tmp;
 9     while(cin>>tmp){
10         if(rand()%(num+1)+1>num)
11             res=tmp;
12         num++;
13     }
14     cout<<"res="<<res<<endl;
15 }

3.在序列流中取k个数,如何确保随机性,即取出某个数据的概率为:k/(已读取数据个数)

  建立一个数组,将序列流里的前k个数,保存在数组中。(也就是所谓的"蓄水池")

  对于第n个数An,以k/n的概率取An并以1/k的概率随机替换“蓄水池”中的某个元素;否则“蓄水池”数组不变。依次类推,可以保证取到数据的随机性。

  数学归纳法证明如下:

    当n=k是,显然“蓄水池”中任何一个数都满足,保留这个数的概率为k/k。

           假设当n=m(m>k)时,“蓄水池”中任何一个数都满足,保留这个数的概率为k/m。

           当n=m+1时,以k/(m+1)的概率取An,并以1/k的概率,随机替换“蓄水池”中的某个元素,否则“蓄水池”数组不变。则数组中保留下来的数的概率为:

 

  所以,对于第n个数An,以k/n的概率取An并以1/k的概率随机替换“蓄水池”中的某个元素;否则“蓄水池”数组不变。依次类推,可以保证取到数据的随机性。

  代码如下:

 1 //在序列流中取n个数,保证均匀,即取出数据的概率为:n/(已读取数据个数)
 2 void RandKNum(int n){
 3     int *myarray=new int[n];
 4     for(int i=0;i<n;i++)
 5         cin>>myarray[i];
 6 
 7     int tmp=0;
 8     int num=n;
 9     while(cin>>tmp){
10         if(rand()%(num+1)+1<n)    
11             myarray[rand()%n]=tmp;
12     }
13 
14     for(int i=0;i<n;i++)
15         cout<<myarray[i]<<endl;
16 }

 

相关文章
|
11月前
|
机器学习/深度学习 算法 大数据
蓄水池抽样算法详解及Python实现
蓄水池抽样是一种适用于从未知大小或大数据集中高效随机抽样的算法,确保每个元素被选中的概率相同。本文介绍其基本概念、工作原理,并提供Python代码示例,演示如何实现该算法。
215 1
|
算法 数据可视化
R语言马尔可夫MCMC中的METROPOLIS HASTINGS,MH算法抽样(采样)法可视化实例
R语言马尔可夫MCMC中的METROPOLIS HASTINGS,MH算法抽样(采样)法可视化实例
R语言马尔可夫MCMC中的METROPOLIS HASTINGS,MH算法抽样(采样)法可视化实例
|
算法 数据可视化 Python
Python用MCMC马尔科夫链蒙特卡洛、拒绝抽样和Metropolis-Hastings采样算法
Python用MCMC马尔科夫链蒙特卡洛、拒绝抽样和Metropolis-Hastings采样算法
|
机器学习/深度学习 算法
R语言使用Metropolis- Hasting抽样算法进行逻辑回归
R语言使用Metropolis- Hasting抽样算法进行逻辑回归
|
机器学习/深度学习 传感器 算法
基于类帕累托贯序抽样算法求解单目标优化问题附matlab代码
基于类帕累托贯序抽样算法求解单目标优化问题附matlab代码
|
存储 算法
一文足矣——动态规划经典之Floyd(弗洛伊德)算法
一文足矣——动态规划经典之Floyd(弗洛伊德)算法
382 0
一文足矣——动态规划经典之Floyd(弗洛伊德)算法
|
8天前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
|
11天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
|
9天前
|
传感器 机器学习/深度学习 算法
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)

热门文章

最新文章