Random weighted sampling

This site is best viewed in a modern browser with JavaScript enabled.

leec

Hello,
I have a list of 1000 objects (Integer) each of which has an assigned weight, and I would like to do a weighted sampling of 5 objects from the 1000. I already have a KeyMap <Integer, Double> that contains the object and its respective weight.
At the moment I've created a new list with objects whose weight is equal to or greater than the 75th percentile, and then I choose my 5 objects randomly from this list, but there may be a better way to do what I want (ie. objects with a higher weight should be more likely selected).

My function is :

  let i_75 = 0
  let w = 0d
  let n = 1000
  fix l_final = new List<String>            //final list of 5 selected objects
  fix l_obj = new List<String>           // list of IDs where weight ≥ 75th percentile
  fix l_weight = new List<Double>   //list of weights
  for(val:km.values) {
    l_weight.add(val)       // put all weights in the list
  }
  i_75 = round(0.75*n).intValue   //get index for the 75th percentile
  w = l_weight.sort.get(i_75)         //get value on the 75th percentile
  for(key:km.keySet) {
    if(km.get(key) >= w)   
      l_obj.add("ID_"+key)       //add the id of the object  		
  }
// then I choose the 5 objects
fix ls_five = min(5,l_obj.size) 
while(ls_final.size < ls_five) {
  fix rand = (random*l_obj.size).intValue 
  if(!ls_final.contains(l_obj.get(rand))) 
  ls_final.add(l_obj.get(rand)) 
}

leec

Maybe this (?):

fix l_obj = new List<String>
let i = 0
let sum = 0d
for(val:km.values) {
  sum += val              //adds the weight of all objects
}
	  	
for (i = 0; i<1; i++)  {
 let s = 0d
 let r = random*sum           //random number between 0 and the sum of all weights 
 for (key : km.keySet) {
    s += km.get(key)           //get the weight for each key  
    if (s >= r) l_obj.add (“ID_”+key)       //if the s is higher than the random number, add it to the list
  }
}

And then I choose 5 objects from the list randomly…

padeg

Hi Leec, sorry for the delayed reply, I was on vacation.

I think your second proposition gets closer to a solution but would not give the expected result for several reasons. One being the for (i = 0; i<1; i++) statement that would be executed only once.

I believe it is more convenient to use two Lists instead of one KeyMap because it makes it easier to check if one value has already been choosen or not. And I would use another list (called blacklisted) to store the index of already choosen values and avoid choosing them again.

So if we consider that we already have one list of objects in lobj and a list of their corresponding weights in lweights, here is a proposed solution:

fix choosen = new List<Integer>  // where we store the resulting choosen objects
fix blacklisted = new List<Integer> // already choosen index
while (choosen.size < 5) {
    // compute the sum of all remaining weights
    let wsum = 0.0
    for (i : 0..lobj.size-1)
      if (!blacklisted.contains(i)) wsum += lweight.get(i)
    // Pick up one value that is not already choosen
    let found = false
    do {
        fix r = random*wsum
        let cursor = 0.0
        let choiceindex = 0
        while (r > cursor) {
          cursor += lweight.get(choiceindex)
          choiceindex++
        }
      if (!blacklisted.contains(choiceindex)) {
        choosen.add(lobj.get(choiceindex))
        blacklisted.add(choiceindex)
        found = true
      }
    } while (!found)
}
println(choosen)