大数据算法MOOC笔记3：水库抽样Reservoir Sampling（蓄水池问
发布时间：2022-10-24 11:12:59 所属栏目：大数据 来源：
导读： （1）第一步初始化。出现在水库中的前k个元素，直接保存在数组A中。前k个数被选中的概率都是一致的，都是1。
（2）第二步。在处理第k+1个元素时分两种情况：
情况1：第k+1个元素未被选中大数据算
（2）第二步。在处理第k+1个元素时分两种情况：
情况1：第k+1个元素未被选中大数据算
|
（1）第一步初始化。出现在水库中的前k个元素，直接保存在数组A中。前k个数被选中的概率都是一致的，都是1。 （2）第二步。在处理第k+1个元素时分两种情况： 情况1：第k+1个元素未被选中大数据算法，数组中没有元素被替换；此时，数组中每个元素的出现概率肯定是一样的，这很显然。但具体是多少呢？就是第k+1个元素未被选中的概率：1-P(第k+1个元素被选中)=1-k/(k+1)=1/(k+1)。（由于第k+1个元素被选中的概率是k/(k+1)（根据公式k/i）） 情况2：第k+1个元素被选中，数组中某个元素被第k+1个元素替换掉。第k+1个元素被选中的概率是k/(k+1)（根据公式k/i），所以这个新元素在水库中出现的概率就一定是k/(k+1)（不管它替换掉哪个元素）。下面来看水库中原有元素最终还能留在水库中的概率，水库中原有数据被替换的几率都相等为1/k。水库中任意一个元素被替换掉的概率是：(k/k+1)*(1/k)=1/(k+1)，意即首先要第k+1个元素被选中，然后该元素在k个元素中被选中。那它未被替换的概率就是1-1/(k+1)=k/(k+1)。可以看出来，旧元素和新元素出现的概率是相等的。 （3）第k+1之后面每个元素都重复第二步，即第i （i>k+1）个元素以k/i的概率决定是否将它放入蓄水池，最终所有元素出现在水库中的概率相等。 （编辑：天瑞地安资讯网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐