algoritmo efficiente per selezionare casualmente oggetti con frequenza

Question

Dato un array di n coppie word frequenza:

[ (w0, f0), (w1, f1), ..., (wn-1, fn-1) ]

dove wi è una parola, fi è un frequencey intero, e la somma delle frequenze ∑fi = m,

Vorrei utilizzare un generatore di numeri pseudo-casuali (PRNG) per selezionare p parole wj0, wj1, ..., wjp-1 tale che la probabilità di selezionare una parola è proporzionale alla sua frequenza:

P(wi = wjk) = P(i = jk) = fi / m

(Nota, questa è la selezione con sostituzione, così la stessa parola potrebbe essere scelto ogni volta).

Sono venuto su con tre algoritmi finora:

1. Crea un array di dimensione m, e popolano così i primi f0 voci sono w0, i prossimi f1 voci sono w1, e così via, quindi l'ultima <= > voci sono fp-1.

   [ w0, ..., w0, w1,..., w1, ..., wp-1, ..., wp-1 ]

   Quindi utilizzare il PRNG per selezionare wp-1 indici della gamma 0...m-1, e riferire le parole memorizzate in tali indici.
   Questo richiede O(n + m + p) lavoro, che non è grande, dal momento che mi può essere molto molto più grande di n.

2. Passaggio attraverso l'array di input, una volta, di calcolo

   mi = ∑h≤ifh = mi-1 + fi

   e dopo aver calcolato xk, utilizzare il PRNG per generare un numero 0...mi-1 nella gamma k per ogni 0...p-1 in wjk e selezionare xk < fi per O(n + np) (eventualmente sostituendo il valore corrente di i) se mi-fi ≤ xk < mi.
   Ciò richiede O(n + p log n) lavoro.

3. Calcola <=> come nell'algoritmo 2, e generare il seguente matrice su n-word frequenza parziale somma triple:

   [ (w0, f0, m0), (w1, f1, m1), ..., (wn-1, fn-1, mn-1) ]

   e poi, per ogni k in <=>, utilizzare il PRNG per generare un numero <=> nella gamma <=> quindi effettuare una ricerca binaria sulla matrice di triple per trovare la <=> S.T. <=>, e selezionare <=> per <=>.
   Ciò richiede <=> lavoro.

La mia domanda è :? C'è un algoritmo più efficiente posso usare per questo, o sono questi come buono come si arriva

Answer 1

Ok, ho trovato un altro algoritmo: il metodo alias (menzionato anche in questa risposta ). In sostanza si crea una partizione dello spazio di probabilità in modo tale che:

• Ci sono delle partizioni n, tutte della stessa larghezza r S.T. nr = m.
• ogni partizione contiene due parole qualche rapporto (che sono memorizzati con la partizione).
• per ogni parola wi, fi = ∑partitions t s.t wi ∈ t r × ratio(t,wi)

Poiché tutte le partizioni sono della stessa dimensione, selezionare quale partizione può essere realizzata in opera costante (prelevamento un indice da 0...n-1 a caso), e il rapporto della partizione può quindi essere utilizzato per selezionare quale parola viene utilizzato in costante lavorare (confronta un numero pRNGed con il rapporto tra le due parole). Quindi questo significa che i p selezioni può essere fatto in O(p) lavoro, data una tale partizione.

La ragione per cui esiste una tale suddivisione è che esiste una parola fi < r S.T. wi', se e solo se esiste una parola fi' > r S.T. w'i, poiché r è la media delle frequenze.

Data una tale coppia f'i = r e fi/r possiamo sostituirlo con un pseudo-word 1 - fi/r di frequenza w'i' (che rappresenta f'i' = fi' - (r - fi) con probabilità O(n) e q > n con probabilità <= >) e una nuova parola q di frequenza impostata m rispettivamente. La frequenza media di tutte le parole sarà ancora r, e la regola dal paragrafo precedente si applica ancora. Poiché la pseudo-parola ha frequenza r ed è costituito da due parole con r frequenza ≠, sappiamo che se iteriamo questo processo, faremo mai una pseudo-parola di una pseudo-parola, e tale iterazione deve terminare con un sequenza di n pseudo-parole che sono la partizione desiderata.

Per costruire questa partizione in f'i = nfi tempo,

• passare attraverso la lista delle parole, una volta, la costruzione di due liste:
  • una delle parole con ≤ frequenza r
  • una delle parole con frequenza> r
• poi tirare una parola dal primo elenco
  • se la sua frequenza = r, quindi farne un elemento di una partizione
  • in caso contrario, tirare una parola dall'altra lista, e utilizzarlo per compilare una partizione di due parole. Poi mettere la seconda parola di nuovo in primo o secondo elenco in base alla sua frequenza impostata.

Questo funziona in realtà ancora se il numero di partizioni m' = mn (dovete solo per dimostrare in modo diverso). Se si vuole fare in modo che R è integrale, e non si può facilmente trovare un fattore di r' = m q = n S.T. O(n + p), è possibile pad tutte le frequenze di un fattore di <=>, così <=>, che aggiorna <=> e set <=> quando <=>.

In ogni caso, questo algoritmo richiede solo <=> lavoro, che devo pensare è ottimale.

In ruby:

def weighted_sample_with_replacement(input, p)
  n = input.size
  m = input.inject(0) { |sum,(word,freq)| sum + freq }

  # find the words with frequency lesser and greater than average
  lessers, greaters = input.map do |word,freq| 
                        # pad the frequency so we can keep it integral
                        # when subdivided
                        [ word, freq*n ] 
                      end.partition do |word,adj_freq| 
                        adj_freq <= m 
                      end

  partitions = Array.new(n) do
    word, adj_freq = lessers.shift

    other_word = if adj_freq < m
                   # use part of another word's frequency to pad
                   # out the partition
                   other_word, other_adj_freq = greaters.shift
                   other_adj_freq -= (m - adj_freq)
                   (other_adj_freq <= m ? lessers : greaters) << [ other_word, other_adj_freq ]
                   other_word
                 end

    [ word, other_word , adj_freq ]
  end

  (0...p).map do 
    # pick a partition at random
    word, other_word, adj_freq = partitions[ rand(n) ]
    # select the first word in the partition with appropriate
    # probability
    if rand(m) < adj_freq
      word
    else
      other_word
    end
  end
end

Answer 2

Questo suona come selezione roulette, utilizzato principalmente per il processo di selezione in algoritmi genetici / evolutivi.

Selezione Roulette in algoritmi genetici

Answer 3

Si può creare la matrice di destinazione, quindi scorrere le parole che determinano la probabilità che esso debba essere raccolto, e sostituire le parole della matrice secondo un numero casuale.

Per la prima parola della probabilità sarebbe f ₀ / m ₀ (dove m _n = f ₀ + .. + f _n ), cioè il 100%, quindi tutte le posizioni nella matrice di destinazione sarebbe riempito con w _{0 .}

Per i seguenti termini la probabilità cade, e quando si raggiunge l'ultima parola della matrice di destinazione è pieno di parole raccolte casualmente accoding alla frequenza.

Esempio di codice in C #:

public class WordFrequency {

    public string Word { get; private set; }
    public int Frequency { get; private set; }

    public WordFrequency(string word, int frequency) {
        Word = word;
        Frequency = frequency;
    }

}

WordFrequency[] words = new WordFrequency[] {
    new WordFrequency("Hero", 80),
    new WordFrequency("Monkey", 4),
    new WordFrequency("Shoe", 13),
    new WordFrequency("Highway", 3),
};

int p = 7;
string[] result = new string[p];
int sum = 0;
Random rnd = new Random();
foreach (WordFrequency wf in words) {
    sum += wf.Frequency;
    for (int i = 0; i < p; i++) {
        if (rnd.Next(sum) < wf.Frequency) {
            result[i] = wf.Word;
        }
    }
}