Iterative oder Lazy Reservoir Sampling

Ich bin ziemlich vertraut mit Reservoir Sampling zu Probe aus einer Reihe von unbestimmten Länge in einem einzigen Durchgang über die Daten. Eine Einschränkung dieses Ansatzes besteht meines Erachtens darin, dass immer noch ein Durchlauf über den gesamten Datensatz erforderlich ist, bevor Ergebnisse zurückgegeben werden können. Konzeptionell ist dies sinnvoll, da man den Items in der gesamten Sequenz die Möglichkeit geben muss, zuvor angetroffene Items zu ersetzen, um eine einheitliche Probe zu erhalten.Iterative oder Lazy Reservoir Sampling

Gibt es eine Möglichkeit, einige zufällige Ergebnisse zu erhalten, bevor die gesamte Sequenz ausgewertet wurde? Ich denke an die Art von fauler Herangehensweise, die gut zu Pythons großer iertools-Bibliothek passen würde. Vielleicht könnte dies innerhalb einer vorgegebenen Fehlertoleranz gemacht werden? Ich würde jede Art von Feedback zu dieser Idee schätzen!

Nur um die Frage etwas zu verdeutlichen, fasst dieses Diagramm mein Verständnis der In-Memory-Streaming-Kompromisse verschiedener Sampling-Techniken zusammen. Was ich will, ist etwas, das in die Kategorie Stream Sampling fällt, wo wir die Länge der Bevölkerung vorher nicht kennen.

enter image description here

Offensichtlich gibt es einen scheinbaren Widerspruch nicht die Länge a priori zu wissen, und noch eine einheitliche Probe bekommen, da wir höchstwahrscheinlich Bias die Probe zu Beginn der Bevölkerung. Gibt es eine Möglichkeit, diese Verzerrung zu quantifizieren? Gibt es Kompromisse zu machen? Hat jemand einen cleveren Algorithmus, um dieses Problem zu lösen?

Quelle

2014-06-11 Stankalank

Sie könnten es so machen, aber dabei verlieren Sie die Fähigkeit, einige Sequenzen zu generieren. Wenn Sie z. B. 10 Elemente zufällig aus einer Liste auswählen möchten, aber eine Art vorzeitiger Rückgabe für ein oder mehrere Elemente ausführen, enthält Ihr Beispiel nie die letzten 10 Elemente in der Liste. Wenn es Ihnen gut geht, die Ausgabe zu beeinflussen, können Sie eine vorzeitige Rückgabe vornehmen. Andernfalls müssen Sie warten, bis die gesamte Liste überprüft wurde. –

Es wäre sinnvoller, Reservoir-Sampling zu implementieren, so dass es immer iterativ iteriert. Wenn ein Aufrufer ein schnelleres Ergebnis wünscht, das nicht über seine gesamte iterierbare Ebene iteriert, kann er selbst abgeschnittene iterierbare Abschnitte übergeben.Eine iterierbare Reservoirbildung wäre wenig sinnvoll, da aufeinanderfolgende Reservoirs extrem korreliert sind (sie unterscheiden sich in 0 oder 1 Positionen). –

@TimothyShields Ich stimme dem API-Design zu, man würde und sollte erwarten, dass sich ein Reservoir-Sample so verhält. Was ich hier suche, ist eine Art von analoger statistischer Klugheit, die es uns erlauben würde, Gegenstände früh zurückzugeben oder ein gutes Argument, warum dies überhaupt nicht möglich ist. – Stankalank

Wenn Sie im Voraus die Gesamtzahl der Elemente kennen, die von einer iterable population nachgegeben werden, ist es möglich, die Elemente einer Stichprobe von population zu erhalten, wie Sie zu ihnen kommen (nicht erst nach dem Ende erreicht). Wenn Sie die Populationsgröße nicht im Voraus wissen, ist dies unmöglich (da die Wahrscheinlichkeit, dass ein Element in der Stichprobe enthalten ist, nicht berechnet werden kann).

Hier ist ein schnell-Generator, der dies tut:

def sample_given_size(population, population_size, sample_size): 
    for item in population: 
     if random.random() < sample_size/population_size: 
      yield item 
      sample_size -= 1 
     population_size -= 1

Beachten Sie, dass der Generator Elemente in der Reihenfolge, wie sie in der Bevölkerung erscheinen ergibt (nicht in zufälliger Reihenfolge, wie random.sample oder die meisten Reservoire Sampling-Codes), so dass ein Scheibe der Probe wird keine zufällige Teilprobe sein!

Quelle

2014-06-11 23:26:40 Blckknght

Dies ist eine echte Streaming-Reservoir Probe, sehr nett. Ist das möglich, ohne vorher die Größe der Bevölkerung zu kennen? – Stankalank

@Stankalank: Nein. Denken Sie an das allererste Element in der Population: Wenn es uns nicht erlaubt ist, eine Entscheidung zum Einschluss oder Ausschluss von der Stichprobe zu "ändern" (wie ein "Streaming Output" -Algorithmus impliziert), wie weiter Erde sollen wir wissen mit welcher Wahrscheinlichkeit es aufzunehmen, es sei denn, wir kennen die Populationsgröße? –

@Stankalank, nein, hier ist es wichtig, die Größe im Voraus zu wissen. Vereinfachen Sie das und Sie werden es leichter sehen: Beschränken Sie Ihre Frage auf die Auswahl eines Beispiels der Größe 1. Sie sollten sich leicht davon überzeugen können, dass Sie die Bevölkerungsgröße nicht im Voraus kennen und nicht nur nicht frühzeitig ausschließen können , Sie können nicht einmal eine "Annäherung" finden, die von echtem Wert ist. Einfacher geht es nicht, wenn die Stichprobengröße 1 übersteigt ;-) –

Wenn die Populationsgröße vor der Hand bekannt ist, können Sie nicht einfach sample_size zufällige "Indizes" (im Stream) generieren und diese verwenden, um eine faule Ausbeute zu erzielen? Sie müssen nicht den gesamten Stream lesen.

Zum Beispiel, wenn population_size war 100 und SAMPLE_SIZE war 3, Sie eine zufällige Menge der ganzen Zahlen von 1 bis 100 erzeugen, sagen Sie 10, 67 erhalten und 72.

Jetzt liefern Sie den 10., 62. und 72. Elemente des Streams und den Rest ignorieren.

Ich denke, ich verstehe die Frage nicht.

Quelle

2014-06-12 04:32:44 Ukkonen

Das Problem ist ziemlich trivial, wenn die Populationsgröße a priori bekannt ist, siehe die akzeptierte Antwort für eine Lösung. Ich denke an einen Datenstrom, der eine __unknown__ Länge hat, wo wir sowohl die Population als auch die Probe streamen wollen. Was ich von den anderen Antworten zu bekommen scheint, ist, dass dies leider nicht möglich ist. – Stankalank

Antwort

Verwandte Themen