S-элементы, M Коэффициенты взвешенного алгоритма выбора

Question

Я хочу нарисовать в общей сложности S образцов из M ковшей. Каждое ведро имеет вес W, который описывает представление элементов из данного ковша в конечном образце. Например, если у меня есть ведра A, B и C с весами 0,5, 0,2 и 0,3 соответственно, а также достаточно большое количество выборок на каждый ковш, тогда, если мой последний размер выборки S = ​​10, я ожидаю, что моя выборка содержать 5 образцов из ковша A, 2 из ведра B и 3 для ведра C. Задача становится более сложной, если учесть, что каждый ковш может не содержать требуемое количество выборок, рассчитанных из весов и общего размера выборки. В этом случае другие весы необходимо отрегулировать, чтобы доставлять образец как можно ближе к желаемому взвешенному представлению. Кто-нибудь знает об этом алгоритме?

Answer 1

Я написал решение в Java. Он может вернуть еще один или два образца по запросу из-за ошибок округления, но это нормально для моего приложения. Если вы видите какие-либо способы улучшить алгоритм, не стесняйтесь публиковать решение.

SampleNode.java

public abstract class SampleNode { 
    protected double weight; 

    protected abstract int getNumSamplesAvailable(); 
    protected abstract boolean hasSamples(); 
    protected abstract int takeAllSamples(); 
    protected abstract void sample(int target); 
    public abstract boolean takeOneSample(); 
} 

LeafSampleNode.java

public class LeafSampleNode extends SampleNode { 
    private int numselected; 
    private int numsamplesavailable; 

    public LeafSampleNode(double weight, int numsamplesavailable) { 
     this.weight = weight; 
     this.numsamplesavailable = numsamplesavailable; 
     this.numselected = 0; 
    } 

    protected void sample(int target) { 
     if(target >= numsamplesavailable) { 
      takeAllSamples(); 
     } 
     else { 
      numselected += target; 
      numsamplesavailable -= target; 
     } 
    } 

    @Override 
    protected int getNumSamplesAvailable() { 
     return numsamplesavailable;  
    } 

    protected boolean hasSamples() { 
     return numsamplesavailable > 0; 
    } 

    protected int getNumselected() { 
     return numselected; 
    } 

    protected int takeAllSamples() { 
     int samplestaken = numsamplesavailable; 
     numselected += numsamplesavailable; 
     numsamplesavailable = 0; 
     return samplestaken; 
    } 
@Override 
public boolean takeOneSample() { 
    if(hasSamples()) { 
     numsamplesavailable--; 
     numselected++; 
     return true; 
    } 
    return false; 
} 
} 

RootSampleNode.java:

import java.util.ArrayList; 
import java.util.List; 

public class RootSampleNode extends SampleNode {  
    private List<SampleNode> children; 

    public RootSampleNode(double weight) { 
     this.children = new ArrayList<SampleNode>(); 
     this.weight = weight; 
    } 

    public void selectSample(int target) { 
     int totalsamples = getNumSamplesAvailable(); 
     if(totalsamples < target) { 
      //not enough samples to meet target, simply take everything 
      for(int i = 0; i < children.size(); i++) { 
       children.get(i).takeAllSamples(); 
      } 
     } 
     else { 
      //there are enough samples to meet target, distribute to meet quotas as closely as possible 
      sample(target); 
     } 
    } 

    protected void sample(int target) { 
     int samplestaken = 0; 
     double totalweight = getTotalWeight(children); 
     samplestaken += sample(totalweight, target, children); 
     if(samplestaken < target) { 
      sample(target - samplestaken); 
     } 
    } 

    private int sample(double totalweight, int target, List<SampleNode> children) { 
     int samplestaken = 0; 
     for(int i = 0; i < children.size(); i++) { 
      SampleNode child = children.get(i); 
      if(child.hasSamples()) { 
       int desired = (int) (target * (child.weight/totalweight) + 0.5); 
       if(desired >= child.getNumSamplesAvailable()) { 
        samplestaken += child.takeAllSamples(); 
       } 
       else { 
        child.sample(desired); 
        samplestaken += desired; 
       } 
      }   
     } 
    if(samplestaken == 0) { //avoid deadlock/stack overflow...someone just take a sample 
     for(int i = 0; i < children.size(); i++) { 
      if(children.get(i).takeOneSample()) { 
       samplestaken++; 
       break; 
      } 
     } 
    } 
     return samplestaken; 
    } 

@Override 
public boolean takeOneSample() { 
    if(hasSamples()) { 
     for(int i = 0; i < children.size(); i++) { 
      if(children.get(i).takeOneSample()) { 
       return true; 
      } 
     }   
    } 
    return false; 
} 

    protected double getTotalWeight(List<SampleNode> children) { 
     double totalweight = 0; 
     for(int i = 0; i < children.size(); i++) { 
      SampleNode child = children.get(i); 
      if(child.hasSamples()) { 
       totalweight += child.weight; 
      } 
     } 
     return totalweight; 
    } 

    protected boolean hasSamples() { 
     for(int i = 0; i < children.size(); i++) { 
      if(children.get(i).hasSamples()) { 
       return true; 
      } 
     } 
     return false; 
    } 

    protected int takeAllSamples() { 
     int samplestaken = 0; 
     for(int i = 0; i < children.size(); i++) { 
      samplestaken += children.get(i).takeAllSamples(); 
     } 
     return samplestaken; 
    } 

    protected int getNumSamplesAvailable() { 
     int numsamplesavailable = 0; 
     for(int i = 0; i < children.size(); i++) { 
      numsamplesavailable += children.get(i).getNumSamplesAvailable(); 
     } 
     return numsamplesavailable; 
    } 

    public void addChild(SampleNode sn) { 
     this.children.add(sn); 
    } 
} 

Некоторые UnitTests:

import static org.junit.Assert.assertTrue; 

import org.junit.Test; 

public class SampleNodeTest { 

    @Test 
    public void test1() { 
     RootSampleNode root = new RootSampleNode(1); 
     LeafSampleNode bucketA = new LeafSampleNode(0.5, 5); 
     LeafSampleNode bucketB = new LeafSampleNode(0.2, 2); 
     LeafSampleNode bucketC = new LeafSampleNode(0.3, 3); 
     root.addChild(bucketA); 
     root.addChild(bucketB); 
     root.addChild(bucketC); 
     root.selectSample(9); 
     assertTrue(bucketA.getNumselected() == 5); 
     assertTrue(bucketB.getNumselected() == 2); 
     assertTrue(bucketC.getNumselected() == 3); 
    } 

    @Test 
    public void test2() { 
     RootSampleNode root = new RootSampleNode(1); 
     LeafSampleNode bucketA = new LeafSampleNode(0.5, 5); 
     LeafSampleNode bucketB = new LeafSampleNode(0.2, 2); 
     LeafSampleNode bucketC = new LeafSampleNode(0.3, 3); 
     root.addChild(bucketA); 
     root.addChild(bucketB); 
     root.addChild(bucketC); 
     root.selectSample(13); 
     assertTrue(bucketA.getNumselected() == 5); 
     assertTrue(bucketB.getNumselected() == 2); 
     assertTrue(bucketC.getNumselected() == 3); 
    } 

    @Test 
    public void test3() { 
     RootSampleNode root = new RootSampleNode(1); 
     LeafSampleNode bucketA = new LeafSampleNode(0.5, 5); 
     LeafSampleNode bucketB = new LeafSampleNode(0.2, 2); 
     LeafSampleNode bucketC = new LeafSampleNode(0.3, 3); 
     root.addChild(bucketA); 
     root.addChild(bucketB); 
     root.addChild(bucketC); 
     RootSampleNode branch1 = new RootSampleNode(0.5); 
     LeafSampleNode bucketD = new LeafSampleNode(0.5, 10); 
     LeafSampleNode bucketE = new LeafSampleNode(0.2, 12); 
     branch1.addChild(bucketD); 
     branch1.addChild(bucketE); 
     root.addChild(branch1); 
     root.selectSample(13); 
     assertTrue(bucketA.getNumselected() == 4); 
     assertTrue(bucketB.getNumselected() == 2); 
     assertTrue(bucketC.getNumselected() == 3); 
     assertTrue(bucketD.getNumselected() == 3); 
     assertTrue(bucketE.getNumselected() == 1); 
    } 

    @Test 
    public void test4() { 
     RootSampleNode root = new RootSampleNode(1); 
     LeafSampleNode bucketA = new LeafSampleNode(0.5, 5); 
     LeafSampleNode bucketB = new LeafSampleNode(0.2, 2); 
     LeafSampleNode bucketC = new LeafSampleNode(0.3, 3); 
     root.addChild(bucketA); 
     root.addChild(bucketB); 
     root.addChild(bucketC); 
     RootSampleNode branch1 = new RootSampleNode(1); 
     LeafSampleNode bucketD = new LeafSampleNode(0.5, 10); 
     LeafSampleNode bucketE = new LeafSampleNode(0.2, 12); 
     branch1.addChild(bucketD); 
     branch1.addChild(bucketE); 
     root.addChild(branch1); 
     root.selectSample(13); 
     assertTrue(bucketA.getNumselected() == 3); 
     assertTrue(bucketB.getNumselected() == 1); 
     assertTrue(bucketC.getNumselected() == 2); 
     assertTrue(bucketD.getNumselected() == 5); 
     assertTrue(bucketE.getNumselected() == 2); 
    } 

    @Test 
    public void test5() { 
     RootSampleNode root = new RootSampleNode(1); 
     LeafSampleNode bucketA = new LeafSampleNode(0.5, 5); 
     LeafSampleNode bucketB = new LeafSampleNode(0.2, 2); 
     LeafSampleNode bucketC = new LeafSampleNode(0.3, 3); 
     root.addChild(bucketA); 
     root.addChild(bucketB); 
     root.addChild(bucketC); 
     RootSampleNode branch1 = new RootSampleNode(1); 
     LeafSampleNode bucketD = new LeafSampleNode(0.5, 10); 
     LeafSampleNode bucketE = new LeafSampleNode(0.2, 12); 
     branch1.addChild(bucketD); 
     branch1.addChild(bucketE); 
     root.addChild(branch1); 
     root.selectSample(4); 
     assertTrue(bucketA.getNumselected() == 1); 
     assertTrue(bucketB.getNumselected() == 0); 
     assertTrue(bucketC.getNumselected() == 1); 
     assertTrue(bucketD.getNumselected() == 1); 
     assertTrue(bucketE.getNumselected() == 1); 
    } 

    @Test 
    public void test6() { 
     RootSampleNode root = new RootSampleNode(1); 
     LeafSampleNode bucketA = new LeafSampleNode(0.5, 5); 
     LeafSampleNode bucketB = new LeafSampleNode(0.2, 2); 
     LeafSampleNode bucketC = new LeafSampleNode(0.3, 3); 
     root.addChild(bucketA); 
     root.addChild(bucketB); 
     root.addChild(bucketC); 
     RootSampleNode branch1 = new RootSampleNode(1); 
     LeafSampleNode bucketD = new LeafSampleNode(0.5, 10); 
     LeafSampleNode bucketE = new LeafSampleNode(0.2, 12); 
     branch1.addChild(bucketD); 
     branch1.addChild(bucketE); 
     root.addChild(branch1); 
     root.selectSample(2); 
     assertTrue(bucketA.getNumselected() == 1); 
     assertTrue(bucketB.getNumselected() == 0); 
     assertTrue(bucketC.getNumselected() == 0); 
     assertTrue(bucketD.getNumselected() == 1); 
     assertTrue(bucketE.getNumselected() == 0); 
    } 

    @Test 
    public void test7() { 
     RootSampleNode root = new RootSampleNode(1); 
     LeafSampleNode bucketA = new LeafSampleNode(0.5, 50); 
     LeafSampleNode bucketB = new LeafSampleNode(0.2, 20); 
     LeafSampleNode bucketC = new LeafSampleNode(0.3, 33); 
     root.addChild(bucketA); 
     root.addChild(bucketB); 
     root.addChild(bucketC); 
     RootSampleNode branch1 = new RootSampleNode(1); 
     LeafSampleNode bucketD = new LeafSampleNode(0.5, 100); 
     LeafSampleNode bucketE = new LeafSampleNode(0.2, 120); 
     branch1.addChild(bucketD); 
     branch1.addChild(bucketE); 
     root.addChild(branch1); 
     root.selectSample(200); 
     assertTrue(bucketA.getNumselected() == 50); 
     assertTrue(bucketB.getNumselected() == 20); 
     assertTrue(bucketC.getNumselected() == 30); 
     assertTrue(bucketD.getNumselected() == 71); 
     assertTrue(bucketE.getNumselected() == 29); 
    } 

    @Test 
    public void test8() { 
     RootSampleNode root = new RootSampleNode(1); 
     RootSampleNode branch1 = new RootSampleNode(5); 
     LeafSampleNode bucketA = new LeafSampleNode(0.5, 50); 
     LeafSampleNode bucketB = new LeafSampleNode(0.2, 20); 
     LeafSampleNode bucketC = new LeafSampleNode(0.3, 33); 
     branch1.addChild(bucketA); 
     branch1.addChild(bucketB); 
     branch1.addChild(bucketC); 
     RootSampleNode branch2 = new RootSampleNode(1); 
     LeafSampleNode bucketD = new LeafSampleNode(0.5, 100); 
     LeafSampleNode bucketE = new LeafSampleNode(0.2, 120); 
     branch2.addChild(bucketD); 
     branch2.addChild(bucketE); 
     root.addChild(branch1); 
     root.addChild(branch2); 
     root.selectSample(200); 
     assertTrue(bucketA.getNumselected() == 50); 
     assertTrue(bucketB.getNumselected() == 20); 
     assertTrue(bucketC.getNumselected() == 33); 
     assertTrue(bucketD.getNumselected() == 70); 
     assertTrue(bucketE.getNumselected() == 27); 
    } 
} 

Надеюсь, кто-то посчитает это полезным.

Answer 2

Если я правильно понял вопрос, я бы просто взял floor каждого результата, а затем распределил остаток.

Давайте использовать ваш пример из трех ведер A, B и C с весами 0.5, 0.2 и 0.3, но на этот раз S = 13.

A: floor(13 * 0.5) = floor(6.5) = 6 
B: floor(13 * 0.2) = floor(2.6) = 2 
C: floor(13 * 0.3) = floor(3.9) = 3 

Итак, мы начинаем с 6 образцов в A, 2 в образцах B и 3 образцов в C, в результате чего 2 образца осталось.

Чтобы выбрать ведра для размещения оставшихся образцов, мы сортируем ведра по их дробной емкости в порядке убывания. Дробно емкость составляет 0,5, В 0,6 В и С составляет 0,9, так что остальные образцы добавляют к С и В, а конечный результат

A: 6 
B: 3 
C: 4 

Answer 3

Мое предложение было бы написать цикл, в котором образцы из ковша, текущий вес которого больше всего от желаемого веса и который не пуст. Вот какой-то псевдокод. Очевидно, вы хотели бы обобщить это для большего количества ведер, но это должно дать вам эту идею.

set buckets[] = { // original items }; 
double weights[] = { 0.5, 0.2, 0.3}; // the desired weights 
int counts[] = { 0, 0, 0 }; // number of items sampled so far 

for (i = 0; i < n; i++) { 
    double errors[] = { 0.0, 0.0, 0.0 }; 
    for (j = 0; j < 3; j++) { 
    if (!empty(buckets[j])) 
     errors[j] = abs(weights[j] - (counts[j]/n)) 
    else 
     errors[j] = 0; 
    } 
    // choose the non-empty bucket whose current weight is 
    // furthest from the desired weight 
    k = argmax(errors); 
    sample(buckets[k]); // take an item out of that bucket 
    counts[k]++;   // increment count 
} 

Если вам нужно, чтобы он переводился на действительную Java, меня можно было бы поговорить с этим :). Это всегда будет производить образцы n (при условии, что они содержат не менее n элементов, в противном случае они будут отображать все их) с распределением как можно ближе к желаемым весам.