Selecione k elementos randoms de uma lista cujos elementos têm pesos

Selecionar sem nenhum peso (probabilidades iguais) é lindamente descrito aqui .

Eu queria saber se existe uma maneira de converter essa abordagem para uma ponderada.

Eu também estou interessado em outras abordagens também.

Atualização: Amostragem sem substituição

   

    Eu sei que esta é uma questão muito antiga, mas eu acho que há um truque legal para fazer isso em O (n) tempo, se você aplicar um pouco de matemática!

    A distribuição exponencial tem duas propriedades muito úteis.

    1. Dados n amostras de diferentes distribuições exponenciais com diferentes parâmetros de taxa, a probabilidade de que uma determinada amostra seja o mínimo é igual ao seu parâmetro de taxa dividido pela sum de todos os parâmetros de taxa.

    2. É “sem memory”. Então, se você já sabe o mínimo, então a probabilidade de que qualquer um dos elementos restantes seja o segundo-para-min é a mesma que a probabilidade de que se o min verdadeiro fosse removido (e nunca gerado), esse elemento teria sido o novo min. Isso parece óbvio, mas acho que por causa de alguns problemas de probabilidade condicional, pode não ser verdade para outras distribuições.

    Usando o fato 1, sabemos que a escolha de um único elemento pode ser feita gerando essas amostras de distribuição exponencial com parâmetro de taxa igual ao peso e, em seguida, escolhendo aquele com valor mínimo.

    Usando o fato 2, sabemos que não precisamos gerar novamente as amostras exponenciais. Em vez disso, basta gerar um para cada elemento e obter os k elementos com as amostras mais baixas.

    Encontrar o menor k pode ser feito em O (n). Use o algoritmo Quickselect para encontrar o k-ésimo elemento, então simplesmente dê outra passagem por todos os elementos e a saída será menor que a k-ésima.

    Uma observação útil: se você não tem access imediato a uma biblioteca para gerar amostras de distribuição exponencial, isso pode ser feito facilmente por: -ln(rand())/weight

    Se a amostragem for com substituição, você pode usar esse algoritmo (implementado aqui no Python):

     import random items = [(10, "low"), (100, "mid"), (890, "large")] def weighted_sample(items, n): total = float(sum(w for w, v in items)) i = 0 w, v = items[0] while n: x = total * (1 - random.random() ** (1.0 / n)) total -= x while x > w: x -= w i += 1 w, v = items[i] w -= x yield v n -= 1 

    Este é O ( n + m ) onde m é o número de itens.

    Por que isso funciona? É baseado no seguinte algoritmo:

     def n_random_numbers_decreasing(v, n): """Like reversed(sorted(v * random() for i in range(n))), but faster because we avoid sorting.""" while n: v *= random.random() ** (1.0 / n) yield v n -= 1 

    A function weighted_sample é justamente esse algoritmo fundido com uma caminhada da lista de items para selecionar os itens selecionados por esses números randoms.

    Isso, por sua vez, funciona porque a probabilidade de que n números randoms 0 ..v sejam todos menores que z é P = ( z / v ) n . Resolva para z e você obtém z = vP 1 / n . Substituir um número random por P escolhe o maior número com a distribuição correta; e podemos apenas repetir o processo para selecionar todos os outros números.

    Se a amostragem for sem substituição, você poderá colocar todos os itens em um heap binário, em que cada nó armazena em cache o total de pesos de todos os itens nesse sub-pico. Construir o heap é O ( m ). Selecionar um item random do heap, respeitando os pesos, é O (log m ). Remover esse item e atualizar os totais em cache também é O (log m ). Então você pode escolher n itens no tempo O ( m + n log m ).

    (Nota: “peso” aqui significa que toda vez que um elemento é selecionado, as possibilidades restantes são escolhidas com probabilidade proporcional aos seus pesos. Isso não significa que os elementos apareçam na saída com uma probabilidade proporcional aos seus pesos.)

    Aqui está uma implementação disso, comentada abundantemente:

     import random class Node: # Each node in the heap has a weight, value, and total weight. # The total weight, self.tw, is self.w plus the weight of any children. __slots__ = ['w', 'v', 'tw'] def __init__(self, w, v, tw): self.w, self.v, self.tw = w, v, tw def rws_heap(items): # h is the heap. It's like a binary tree that lives in an array. # It has a Node for each pair in `items`. h[1] is the root. Each # other Node h[i] has a parent at h[i>>1]. Each node has up to 2 # children, h[i< <1] and h[(i<<1)+1]. To get this nice simple # arithmetic, we have to leave h[0] vacant. h = [None] # leave h[0] vacant for w, v in items: h.append(Node(w, v, w)) for i in range(len(h) - 1, 1, -1): # total up the tws h[i>>1].tw += h[i].tw # add h[i]'s total to its parent return h def rws_heap_pop(h): gas = h[1].tw * random.random() # start with a random amount of gas i = 1 # start driving at the root while gas >= h[i].w: # while we have enough gas to get past node i: gas -= h[i].w # drive past node i i < <= 1 # move to first child if gas >= h[i].tw: # if we have enough gas: gas -= h[i].tw # drive past first child and descendants i += 1 # move to second child w = h[i].w # out of gas! h[i] is the selected node. v = h[i].v h[i].w = 0 # make sure this node isn't chosen again while i: # fix up total weights h[i].tw -= w i >>= 1 return v def random_weighted_sample_no_replacement(items, n): heap = rws_heap(items) # just make a heap... for i in range(n): yield rws_heap_pop(heap) # and pop n items off it. 

    Se a amostragem for feita com substituição, use a técnica de seleção de roleta (geralmente usada em algoritmos genéticos):

    1. ordenar os pesos
    2. calcular os pesos cumulativos
    3. escolha um número random em [0,1]*totalWeight
    4. encontrar o intervalo em que esse número cai
    5. selecione os elementos com o intervalo correspondente
    6. repita k vezes

    texto alternativo

    Se a amostragem for sem substituição, você pode adaptar a técnica acima removendo o elemento selecionado da lista após cada iteração e, em seguida, normalizando novamente os pesos para que sua sum seja 1 (function de distribuição de probabilidade válida)

    Eu fiz isso em Ruby

    https://github.com/fl00r/pickup

     require 'pickup' pond = { "selmon" => 1, "carp" => 4, "crucian" => 3, "herring" => 6, "sturgeon" => 8, "gudgeon" => 10, "minnow" => 20 } pickup = Pickup.new(pond, uniq: true) pickup.pick(3) #=> [ "gudgeon", "herring", "minnow" ] pickup.pick #=> "herring" pickup.pick #=> "gudgeon" pickup.pick #=> "sturgeon" 

    Se você deseja gerar grandes matrizes de inteiros randoms com substituição , você pode usar a interpolação linear por partes. Por exemplo, usando o NumPy / SciPy:

     import numpy import scipy.interpolate def weighted_randint(weights, size=None): """Given an n-element vector of weights, randomly sample integers up to n with probabilities proportional to weights""" n = weights.size # normalize so that the weights sum to unity weights = weights / numpy.linalg.norm(weights, 1) # cumulative sum of weights cumulative_weights = weights.cumsum() # piecewise-linear interpolating function whose domain is # the unit interval and whose range is the integers up to n f = scipy.interpolate.interp1d( numpy.hstack((0.0, weights)), numpy.arange(n + 1), kind='linear') return f(numpy.random.random(size=size)).astype(int) 

    Isso não é eficaz se você quiser experimentar sem reposição.

    Aqui está uma implementação Go de geodns :

     package foo import ( "log" "math/rand" ) type server struct { Weight int data interface{} } func foo(servers []server) { // servers list is already sorted by the Weight attribute // number of items to pick max := 4 result := make([]server, max) sum := 0 for _, r := range servers { sum += r.Weight } for si := 0; si < max; si++ { n := rand.Intn(sum + 1) s := 0 for i := range servers { s += int(servers[i].Weight) if s >= n { log.Println("Picked record", i, servers[i]) sum -= servers[i].Weight result[si] = servers[i] // remove the server from the list servers = append(servers[:i], servers[i+1:]...) break } } } return result } 

    Se você quiser escolher x elementos de um conjunto ponderado sem substituição, esses elementos são escolhidos com uma probabilidade proporcional aos seus pesos:

     import random def weighted_choose_subset(weighted_set, count): """Return a random sample of count elements from a weighted set. weighted_set should be a sequence of tuples of the form (item, weight), for example: [('a', 1), ('b', 2), ('c', 3)] Each element from weighted_set shows up at most once in the result, and the relative likelihood of two particular elements showing up is equal to the ratio of their weights. This works as follows: 1.) Line up the items along the number line from [0, the sum of all weights) such that each item occupies a segment of length equal to its weight. 2.) Randomly pick a number "start" in the range [0, total weight / count). 3.) Find all the points "start + n/count" (for all integers n such that the point is within our segments) and yield the set containing the items marked by those points. Note that this implementation may not return each possible subset. For example, with the input ([('a': 1), ('b': 1), ('c': 1), ('d': 1)], 2), it may only produce the sets ['a', 'c'] and ['b', 'd'], but it will do so such that the weights are respected. This implementation only works for nonnegative integral weights. The highest weight in the input set must be less than the total weight divided by the count; otherwise it would be impossible to respect the weights while never returning that element more than once per invocation. """ if count == 0: return [] total_weight = 0 max_weight = 0 borders = [] for item, weight in weighted_set: if weight < 0: raise RuntimeError("All weights must be positive integers") # Scale up weights so dividing total_weight / count doesn't truncate: weight *= count total_weight += weight borders.append(total_weight) max_weight = max(max_weight, weight) step = int(total_weight / count) if max_weight > step: raise RuntimeError( "Each weight must be less than total weight / count") next_stop = random.randint(0, step - 1) results = [] current = 0 for i in range(count): while borders[current] < = next_stop: current += 1 results.append(weighted_set[current][0]) next_stop += step return results 

    Na questão a que você ligou, a solução de Kyle funcionaria com uma generalização trivial. Digitalize a lista e some os pesos totais. Então a probabilidade de escolher um elemento deve ser:

    1 – (1 – (# necessário / (peso à esquerda)) / (peso em n). Depois de visitar um nó, subtraia seu peso do total. Além disso, se você precisar n e tiver n deixado, terá que parar explicitamente.

    Você pode verificar isso com tudo tendo peso 1, isso simplifica a solução de kyle.

    Editado: (tive que repensar o que o dobro da probabilidade significava)

    Este faz exatamente isso com O (n) e nenhum uso excessivo de memory. Eu acredito que esta é uma solução inteligente e eficiente e fácil de portar para qualquer idioma. As duas primeiras linhas são apenas para preencher dados de amostra no Drupal.

     function getNrandomGuysWithWeight($numitems){ $q = db_query('SELECT id, weight FROM theTableWithTheData'); $q = $q->fetchAll(); $accum = 0; foreach($q as $r){ $accum += $r->weight; $r->weight = $accum; } $out = array(); while(count($out) < $numitems && count($q)){ $n = rand(0,$accum); $lessaccum = NULL; $prevaccum = 0; $idxrm = 0; foreach($q as $i=>$r){ if(($lessaccum == NULL) && ($n < = $r->weight)){ $out[] = $r->id; $lessaccum = $r->weight- $prevaccum; $accum -= $lessaccum; $idxrm = $i; }else if($lessaccum){ $r->weight -= $lessaccum; } $prevaccum = $r->weight; } unset($q[$idxrm]); } return $out; } 

    Colocando aqui uma solução simples para escolher 1 item, você pode facilmente expandi-lo para k itens (estilo Java):

     double random = Math.random(); double sum = 0; for (int i = 0; i < items.length; i++) { val = items[i]; sum += val.getValue(); if (sum > random) { selected = val; break; } } 

    Eu implementei um algoritmo semelhante à idéia de Jason Orendorff em Rust aqui . Minha versão também suporta operações em massa: inserir e remover (quando você quer remover um monte de itens dados por seus IDs, não pelo caminho de seleção ponderada) da estrutura de dados em O(m + log n) tempo em que m é o número de itens a serem removidos e n o número de itens armazenados.

    Amostragem sem substituição com recursion – solução elegante e muito curta em c #

    // de quantas maneiras podemos escolher 4 de 60 alunos, de modo que toda vez que escolhermos diferentes 4

     class Program { static void Main(string[] args) { int group = 60; int studentsToChoose = 4; Console.WriteLine(FindNumberOfStudents(studentsToChoose, group)); } private static int FindNumberOfStudents(int studentsToChoose, int group) { if (studentsToChoose == group || studentsToChoose == 0) return 1; return FindNumberOfStudents(studentsToChoose, group - 1) + FindNumberOfStudents(studentsToChoose - 1, group - 1); } } 

    Eu usei um mapa associativo (peso, object). por exemplo:

     { (10,"low"), (100,"mid"), (10000,"large") } total=10110 

    espreitar um número random entre 0 e ‘total’ e percorrer as teclas até que esse número caiba em um determinado intervalo.