Wie generiere ich Punkte, die ein Histogramm anzeigen lassen?

StackOverflow https://stackoverflow.com/questions/423006

Frage

Ich arbeite an einem Simulationssystem. Ich werde bald experimentelle Daten (Histogramme) für die reale Verteilung von Werten für mehrere Simulationseingänge.

Wenn die Simulation läuft, würde Ich mag Lage sein, Zufallswerte zu erzeugen, die die gemessene Verteilung entsprechen. Ich würde es vorziehen, dies zu tun, ohne die ursprünglichen Histogramme zu speichern. Was sind einige gute Möglichkeiten,

  1. Zuordnen eines Histogramms auf einen Satz von Parametern, die Verteilung darstellt?
  2. Erstellen von Werten, die auf diese Parameter zur Laufzeit basiert?

EDIT: Die Eingabedaten Ereignisdauern für verschiedene Arten von Veranstaltungen. Ich gehe davon aus, dass verschiedene Arten unterschiedliche Verteilungsfunktionen haben.

War es hilfreich?

Lösung

Mindestens zwei Möglichkeiten:

  1. Integrieren Sie das Histogramm und invertieren numerisch.
  2. Die Ablehnung

Numerische Integration

Von Berechnung in der modernen Physik von William R. Gibbs:

  

Man kann immer numerisch integrieren [die Funktion] und invertieren die [ CDF ]   aber das ist oft nicht sehr befriedigend vor allem, wenn die pdf ändern   schnell.

Sie bauen wahrsten Sinne des Wortes eine Tabelle, die den Bereich [0-1) in entsprechende Bereiche in der Zielverteilung übersetzt. Dann werfen Sie Ihre übliche (hohe Qualität) PRNG und übersetzen mit der Tabelle. Es ist mühsam, aber klar, praktikabel und ganz allgemein.

Ablehnung:

Normalisieren des Ziel Histogramm, dann

  1. Werfen Sie die Würfel eine Position (x) entlang des Bereichs zufällig zu wählen.
  2. Werfen Sie noch einmal, und diesen Punkt auswählen, wenn die neue Zufallszahl kleiner als das normalisierte Histogramm in diesem Fach ist. Ansonsten gehe zu (1).

Auch hier einfältig, aber klar und arbeitet. Es kann mit einer Menge von sehr geringer Wahrscheinlichkeit (Spitzen mit langen Schwänzen) für die Verteilung langsam sein.

Mit diesen beiden Methoden, Sie können die Daten mit stückweise Polynomanpassungen oder Splines annähernd eine glatte Kurve zu erzeugen, wenn eine Stufenfunktion Histogramm nicht erwünscht ist, --- aber das lassen später als kann es verfrüht Optimierung sein.

Bessere Methoden können für Sonderfälle sind.

All dies ziemlich normal ist und in jedem Numerischen Analysis Lehrbuch erscheinen sollte, wenn ich genauer erklärt werden muß.

Andere Tipps

Weitere Informationen über das Problem wären nützlich. Zum Beispiel, welche Art von Werten sind die Histogramme über? Sind sie kategorisch (zum Beispiel Farben, Buchstaben) oder kontinuierlich (z.B. Höhen, Zeit)?

Wenn die Histogramme über kategorische Daten sind denke ich, es schwierig sein kann, die Verteilungen parametrisieren, es sei denn es gibt viele Korrelationen zwischen Kategorien.

Wenn die Histogramme über kontinuierliche Daten können Sie versuchen, die Verteilung unter Verwendung von Mischungen von Gaussians zu passen. Das heißt, die versuchen, das Histogramm unter Verwendung eines $ \ sum_ passen {i = 1} ^ n W_i N (m_i, v_i) $ wo m_i v_i und ist der Mittelwert und die Varianz. Dann, wenn Sie Daten generieren möchten Sie zunächst proportional einen i von 1..n mit Wahrscheinlichkeit Probe auf die Gewichte W_i und dann ein x Probe ~ n (m_i, v_i), wie man es von einem beliebigen Gaußschen.

So oder so, Sie möchten mehr über Mischung Modelle lesen.

So scheint es, dass ich, was will, um eine gegebene probablity Verteilung zu erzeugen, ist eine Quantilsfunktion , das ist der Kehrwert der kumulative Verteilungsfunktion , wie @dmckee sagt.

Die Frage ist: Was ist der beste Weg, um eine Quantilsfunktion zu erzeugen und speichern ein gegebenes kontinuierliches Histogramm beschreiben? Ich habe das Gefühl, die Antwort wird in hohem Maße von der Form der Eingabe abhängen - wenn es irgendeine Art von Muster folgt soll Vereinfachungen über den allgemeinsten Fall sein. Ich werde hier aktualisieren, wie ich gehen.

Edit:

Ich hatte ein Gespräch in dieser Woche, die mich an dieses Problem erinnert. Wenn ich das Histogramm als eine Gleichung verzichten zu beschreiben, und speichern nur die Tabelle, kann ich Auswahlen in O (1) Zeit? Es stellt sich heraus, Sie können, ohne Verlust an Präzision, auf Kosten von O (N LGN) Bauzeit.

eine Reihe von N Artikeln erstellen. Eine gleichförmige Zufallsauswahl in dem Array wird ein Element mit probablilty 1 / N finden. Für jedes Element speichern den Anteil der Treffer für die dieses Element sollte tatsächlich ausgewählt werden, und der Index eines anderen Elements, die ausgewählt werden, wenn dieser nicht ist.

Weighted Random Sampling, C Umsetzung: 

//data structure
typedef struct wrs_data {
  double share; 
  int pair;
  int idx;
} wrs_t;


//sort helper
int wrs_sharecmp(const void* a, const void* b) {
  double delta = ((wrs_t*)a)->share - ((wrs_t*)b)->share;
  return (delta<0) ? -1 : (delta>0);
}


//Initialize the data structure
wrs_t* wrs_create(int* weights, size_t N) {
  wrs_t* data = malloc(sizeof(wrs_t));
  double sum = 0;
  int i;
  for (i=0;i<N;i++) { sum+=weights[i]; }
  for (i=0;i<N;i++) {
    //what percent of the ideal distribution is in this bucket?
    data[i].share = weights[i]/(sum/N); 
    data[i].pair = N;
    data[i].idx = i;
  }
  //sort ascending by size
  qsort(data,N, sizeof(wrs_t),wrs_sharecmp);

  int j=N-1; //the biggest bucket
  for (i=0;i<j;i++) {
    int check = i;
    double excess = 1.0 - data[check].share;
    while (excess>0 && i<j) {
      //If this bucket has less samples than a flat distribution,
      //it will be hit more frequently than it should be.  
      //So send excess hits to a bucket which has too many samples.
      data[check].pair=j; 
      // Account for the fact that the paired bucket will be hit more often,
      data[j].share -= excess;  
      excess = 1.0 - data[j].share;
      // If paired bucket now has excess hits, send to new largest bucket at j-1
      if (excess >= 0) { check=j--;} 
    }
  }
  return data;
}


int wrs_pick(wrs_t* collection, size_t N)
//O(1) weighted random sampling (after preparing the collection).
//Randomly select a bucket, and a percentage.
//If the percentage is greater than that bucket's share of hits, 
// use it's paired bucket.
{
  int idx = rand_in_range(0,N);
  double pct = rand_percent();
  if (pct > collection[idx].share) { idx = collection[idx].pair; }
  return collection[idx].idx;
}

Edit 2:   Nach einer wenig Recherche fand ich es sogar möglich, den Aufbau in O (N) Zeit zu tun. Mit einer sorgfältigen Tracking, müssen Sie nicht um das Array zu sortieren, die großen und kleinen Behälter zu finden. Aktualisiert Umsetzung hier

Wenn Sie eine große Anzahl von Proben mit einer gewichteten Verteilung von diskreten Punkten ziehen müssen, dann schauen Sie unter eine Antwort auf eine ähnliche Frage .

Wenn Sie jedoch eine kontinuierliche Zufallsfunktion mit Hilfe eines Histogramms nähern müssen, dann Ihre beste Wette ist wahrscheinlich numerische Integration Antwort des Dmckee. Alternativ können Sie das Aliasing verwenden, und speichern Sie den Punkt auf der linken Seite, und eine einheitliche Zahl zwischen den beiden Punkten holen.

So wählen Sie aus einem Histogramm (Original oder reduziert), Walker alias Methode ist schnell und einfach.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top