Effizienter Algorithmus zur zufälligen Auswahl von Objekten mit Häufigkeit

8

Gegeben ein Array von n Wort-Frequenz Paaren:

%Vor%

Dabei ist wi ein Wort, fi ist eine ganze Zahl und die Summe der Häufigkeiten ∑fi = m ,

Ich möchte einen Pseudozufallszahlengenerator (pRNG) verwenden, um p words wj0, wj1, ..., wjp-1 so auszuwählen, dass Die Wahrscheinlichkeit, ein Wort auszuwählen, ist proportional zu seiner Häufigkeit:

%Vor%

(Bitte beachten Sie, dass es sich um eine Auswahl mit Ersatz handelt, daher kann jedes Mal das gleiche Wort gewählt werden.)

Ich habe bis jetzt drei Algorithmen entwickelt:

  1. Erstellen Sie ein Array der Größe m , und füllen Sie es so, dass die ersten f0 -Einträge w0 , die nächsten f1 -Einträge w1 usw. sind, also die letzten fp-1 -Einträge wp-1 .

    %Vor% Verwenden Sie dann den pRNG, um p -Indizes im Bereich 0...m-1 auszuwählen, und melden Sie die in diesen Indizes gespeicherten Wörter.
    Dies dauert O(n + m + p) work, was nicht großartig ist, da m viel viel größer sein kann als n.

  2. Gehen Sie einmal durch das Eingabe-Array und berechnen Sie

    %Vor% und nach Berechnung von mi , benutze den pRNG, um eine Zahl xk im Bereich 0...mi-1 für jede k in 0...p-1 zu generieren und wählen Sie wi für wjk (möglicherweise ersetzt den aktuellen Wert von wjk ) wenn xk < fi .
    Dies erfordert O(n + np) work.
  3. Berechne mi wie in Algorithmus 2 und erzeuge das folgende Array auf n Wort-Frequenz-Partialsummen-Tripeln: 
    [ (w0, f0), (w1, f1), ..., (wn-1, fn-1) ]
    und dann, für jedes k in 0...p-1 , benutze das pRNG, um eine Zahl xk im Bereich 0...m-1 zu erzeugen, dann führe eine binäre Suche auf dem Tripelfeld durch, um die i s.t. mi-fi ≤ xk < mi , und wählen Sie wi für wjk .
    Dies erfordert O(n + p log n) work.

Meine Frage ist : Gibt es einen effizienteren Algorithmus, den ich dafür verwenden kann, oder sind diese so gut wie es geht?

    
rampion 16.05.2009, 14:48
quelle

3 Antworten

1

Ok, ich habe einen anderen Algorithmus gefunden: die Alias-Methode (auch erwähnt < a href="https://stackoverflow.com/questions/352670/weighted-random-selection-with-and-without-replacement/353576#353576"> in dieser Antwort ). Im Grunde erstellt es eine Partition des Wahrscheinlichkeitsraums, so dass:

  • Es gibt n Partitionen, die alle die gleiche Breite r s.t. nr = m .
  • Jede Partition enthält zwei Wörter in einem bestimmten Verhältnis (das zusammen mit der Partition gespeichert wird).
  • für jedes Wort wi , fi = ∑partitions t s.t wi ∈ t r × ratio(t,wi)

Da alle Partitionen dieselbe Größe haben, wählen Sie, welche Partition in konstanter Arbeit ausgeführt werden kann (wählen Sie zufällig einen Index von 0...n-1 ), und das Partitionsverhältnis kann dann verwendet werden, um auszuwählen, welches Wort in konstant verwendet wird arbeiten (vergleiche eine pRNGed-Zahl mit dem Verhältnis zwischen den beiden Wörtern). Das bedeutet, dass die p -Auswahl in O(p) work bei einer solchen Partition erfolgen kann.

Der Grund dafür, dass eine solche Partitionierung existiert, besteht darin, dass ein Wort wi s.t. fi < r , wenn und nur wenn ein Wort wi' s.t. fi' > r , da r der Durchschnitt der Frequenzen ist.

Bei einem solchen Paar wi und wi' können wir sie durch ein Pseudowort w'i der Häufigkeit f'i = r ersetzen (das wi mit der Wahrscheinlichkeit fi/r und wi' mit der Wahrscheinlichkeit% co_de darstellt %) und ein neues Wort 1 - fi/r der angepassten Häufigkeit w'i' . Die durchschnittliche Häufigkeit aller Wörter ist immer noch r, und die Regel aus dem vorherigen Absatz gilt immer noch. Da das Pseudowort die Frequenz r hat und aus zwei Wörtern mit der Häufigkeit r besteht, wissen wir, dass wir, wenn wir diesen Prozess iterieren, niemals ein Pseudowort aus einem Pseudowort erzeugen werden, und diese Iteration muss mit a enden Sequenz von n Pseudowörtern, die die gewünschte Partition sind.

Um diese Partition in f'i' = fi' - (r - fi) time zu erstellen,

  • gehe einmal durch die Liste der Wörter und konstruiere zwei Listen:
    • eines der Wörter mit der Häufigkeit ≤ r
    • eines der Wörter mit Häufigkeit & gt; r
  • Dann ziehe ein Wort aus der ersten Liste
    • wenn seine Häufigkeit = r, dann mache es zu einer Ein-Element-Partition
    • andernfalls, ziehen Sie ein Wort aus der anderen Liste und verwenden Sie es, um eine Zwei-Wort-Partition auszufüllen. Dann lege das zweite Wort entsprechend der eingestellten Frequenz wieder in die erste oder zweite Liste.

Das funktioniert auch noch, wenn die Anzahl der Partitionen O(n) ist (du musst es nur anders beweisen). Wenn Sie sicherstellen wollen, dass r integral ist und Sie nicht einfach einen Faktor q > n von q s.t. m , Sie können alle Frequenzen mit einem Faktor von q > n auffüllen, also n , wodurch f'i = nfi aktualisiert und m' = mn bei r' = m festgelegt wird.

In jedem Fall braucht dieser Algorithmus nur q = n work, was ich für optimal halte.

In Ruby:

%Vor%     
rampion 23.05.2017, 11:48
quelle
6

Das klingt wie eine Rouletteradauswahl, die hauptsächlich für den Auswahlprozess in genetischen / evolutionären Algorithmen verwendet wird.

Sehen Sie sich Roulette-Auswahl in genetischen Algorithmen

an     
seb 16.05.2009 15:06
quelle
1

Sie könnten das Zielarray erstellen, dann die Wörter durchgehen, die die Wahrscheinlichkeit bestimmen, dass es ausgewählt werden soll, und die Wörter im Array nach einer Zufallszahl ersetzen.

Für das erste Wort würde die Wahrscheinlichkeit f 0 / m <0 sein (wobei mn = f0 ) > + .. + f n ), dh 100%, so dass alle Positionen im Zielarray mit w 0 gefüllt würden.

Für die folgenden Wörter fällt die Wahrscheinlichkeit, und wenn Sie das letzte Wort erreichen, wird das Zielfeld mit zufällig ausgewählten Wörtern entsprechend der Häufigkeit gefüllt.

Beispielcode in C #:

%Vor%     
Guffa 16.05.2009 15:54
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Wie verschiebe ich meinen RoutinedCommand-Handler von View-codebehind nach ViewModel?