wake-up-neo.net

Berechnung oder Annäherung des Median einer Liste, ohne die Liste zu speichern

Ich versuche, den Mittelwert einer Menge von Werten zu berechnen, aber ich möchte nicht alle Werte speichern, da dies die Speicheranforderungen sprengen könnte. Gibt es eine Möglichkeit, den Median zu berechnen oder anzunähern, ohne alle einzelnen Werte zu speichern und zu sortieren?

Im Idealfall möchte ich meinen Code ein bisschen wie folgt schreiben

var medianCalculator = new MedianCalculator();
foreach (var value in SourceData)
{
  medianCalculator.Add(value);
}
Console.WriteLine("The median is: {0}", medianCalculator.Median);

Ich brauche nur den eigentlichen MedianCalculator-Code!

Update: Einige Leute haben gefragt, ob die Werte, für die ich den Median berechnen möchte, bekannte Eigenschaften haben. Die Antwort ist ja. Ein Wert liegt in 0,5-Schritten von etwa -25 bis -0,5. Das andere ist auch in 0,5-Schritten von -120 bis -60. Ich denke, das bedeutet, dass ich für jeden Wert eine Art Histogramm verwenden kann.

Vielen Dank

Nick

39
Nick Randell

Wenn die Werte diskret sind und die Anzahl der unterschiedlichen Werte nicht zu hoch ist, können Sie einfach die Häufigkeit des Auftretens jedes Werts in einem Histogramm aufsummieren und dann den Medianwert aus den Histogrammzählungen ermitteln (addieren Sie die Zählwerte von oben und unten des Histogramms bis zur Mitte). Oder wenn es sich um kontinuierliche Werte handelt, können Sie sie in Bins verteilen - das würde Ihnen nicht den genauen Medianwert angeben, aber es würde Ihnen einen Bereich geben, und wenn Sie es genauer wissen müssen, können Sie die Liste erneut durchlaufen und nur untersuchen die Elemente im zentralen Behälter.

40
David Z

Es gibt die "Remedian" -Statistik. Dazu werden zunächst k Arrays mit der Länge b eingerichtet. Datenwerte werden in das erste Array eingespeist, und wenn dieses voll ist, wird der Medianwert in der ersten Position des nächsten Arrays berechnet und gespeichert, wonach das erste Array erneut verwendet wird. Wenn das zweite Array voll ist, wird der Median seiner Werte in der ersten Position des dritten Arrays usw. gespeichert. Usw. Sie erhalten die Idee :)

Es ist einfach und ziemlich robust. Die Referenz ist hier ...

http://web.ipac.caltech.edu/staff/fmasci/home/astro_refs/Remedian.pdf

Hoffe das hilft

Michael

36
michael

Ich verwende diese inkrementellen/rekursiven Mittelwert- und Medianschätzer, die beide konstanten Speicher verwenden:

mean += eta * (sample - mean)
median += eta * sgn(sample - median)

wobei eta ein Parameter für die kleine Lernrate ist (z. B. 0,001), und sgn () die Signum-Funktion ist, die eine von {-1, 0, 1} zurückgibt.

Dieser Typ eines inkrementellen Mittelwertschätzers scheint überall verwendet zu werden, z. in unüberwachten neuronalen Netzwerk-Lernregeln, aber die mittlere Version scheint trotz ihrer Vorteile (Robustheit gegenüber Ausreißern) viel seltener zu sein. Es scheint, dass die Medianversion in vielen Anwendungen als Ersatz für den Mittelwertschätzer verwendet werden könnte.

Ich würde gerne einen inkrementellen Modusschätzer einer ähnlichen Form sehen ...

(Hinweis: Ich habe dies auch zu einem ähnlichen Thema hier gepostet: "On-line" (Iterator) -Algorithmen zum Schätzen des statistischen Median, Modus, Schiefe, Kurtosis? )

17
Tyler Streeter

Hier ist ein verrückter Ansatz, den Sie versuchen könnten. Dies ist ein klassisches Problem bei Streaming-Algorithmen. Die Regeln sind

  1. Sie haben einen begrenzten Speicherplatz, beispielsweise O(log n), wobei n die Anzahl der gewünschten Elemente ist
  2. Sie können sich jedes Element einmal ansehen und dann eine Entscheidung treffen, und was dann damit zu tun ist, wenn Sie es speichern, kostet es Speicher, wenn Sie es wegwerfen, ist es für immer verschwunden.

Die Idee zum Finden eines Medians ist einfach. Probieren Sie O(1 / a^2 * log(1 / p)) * log(n) Elemente aus der Liste nach dem Zufallsprinzip aus. Sie können dies über Reservoir-Sampling durchführen (siehe a vorherige Frage ). Nun geben Sie einfach den Mittelwert aus Ihren gesampelten Elementen mit einer klassischen Methode zurück.

Die Garantie ist, dass der Index des zurückgegebenen Artikels (1 +/- a) / 2 mit einer Wahrscheinlichkeit von mindestens 1-p lautet. Es besteht also eine Wahrscheinlichkeit, dass p fehlschlägt. Sie können es auswählen, indem Sie weitere Elemente abtasten. Der Medianwert wird nicht zurückgegeben oder garantiert, dass der Wert des zurückgegebenen Elements nahe am Medianwert liegt. Nur wenn Sie die Liste sortieren, liegt der zurückgegebene Artikel nahe an der Hälfte der Liste.

Dieser Algorithmus verwendet O(log n) zusätzlichen Platz und läuft in linearer Zeit.

13
Pall Melsted

Dies ist schwierig, um im Allgemeinen richtig zu sein, insbesondere um degenerierte Serien zu behandeln, die bereits sortiert sind oder eine Reihe von Werten am "Anfang" der Liste enthalten, das Ende der Liste hat jedoch Werte in einem anderen Bereich.

Die Grundidee eines Histogramms ist sehr vielversprechend. Auf diese Weise können Sie Verteilungsinformationen sammeln und Abfragen (wie den Median) beantworten. Der Medianwert ist ungefähr, da Sie offensichtlich nicht alle Werte speichern. Der Speicherplatz ist festgelegt, sodass er mit jeder beliebigen Längensequenz funktioniert.

Sie können jedoch nicht einfach aus den ersten 100 Werten ein Histogramm erstellen und dieses Histogramm kontinuierlich verwenden. Die Änderung der Daten kann dazu führen, dass das Histogramm ungültig wird. Sie benötigen also ein dynamisches Histogramm, das den Bereich und die Ablage im laufenden Betrieb ändern kann.

Erstellen Sie eine Struktur mit N Behältern. Sie speichern den X-Wert jedes Slot-Übergangs (N + 1 Werte insgesamt) sowie die Grundgesamtheit der Ablage. 

Stream in deine Daten. Notieren Sie die ersten N + 1-Werte. Wenn der Stream davor endet, sind alle Werte geladen, und Sie können den genauen Medianwert ermitteln und ihn zurückgeben. Sonst verwenden Sie die Werte, um Ihr erstes Histogramm zu definieren. Sortieren Sie die Werte einfach und verwenden Sie sie als Ablagendefinitionen, wobei jedes Abteil eine Population von 1 hat. Es ist in Ordnung, Dupes (0-breite Abstände) zu haben. 

Streamen Sie jetzt in neuen Werten. Bei jeder binären Suche nach der Bin, zu der sie gehört. In der Regel erhöhen Sie einfach die Grundgesamtheit dieser Bin und fahren fort. Wenn sich Ihre Probe außerhalb der Kanten des Histogramms befindet (am höchsten oder am niedrigsten), erweitern Sie einfach den Bereich des End-Bin-Bereichs, um ihn einzuschließen. Wenn Ihr Stream fertig ist, finden Sie den Median-Sample-Wert, indem Sie den Bin-Speicherplatz finden, der auf beiden Seiten gleich besetzt ist Behälterbreite.

Aber das ist noch nicht genug. Sie müssen das Histogramm dennoch an die Daten ADAPTIEREN, wenn diese in das Streaming einfließen. Wenn eine Bin voll ist, verlieren Sie Informationen über die Unterverteilung dieser Bin. Sie können dies beheben durch Anpassung basierend auf einer gewissen Heuristik ... Die einfachste und robusteste ist, wenn eine Bin eine bestimmte Schwellenwert-Population erreicht (etwa 10 * v/N, wobei v = # der Werte ist, die bisher im Stream gesehen wurden und N die Anzahl ist von Bins), Sie SPLIT diese überfüllten Abfalleimer. Fügen Sie am Mittelpunkt der Ablage einen neuen Wert hinzu, und geben Sie jeder Seite die Hälfte der Grundfläche der ursprünglichen Ablage. Aber jetzt haben Sie zu viele Behälter, also müssen Sie einen Behälter LÖSCHEN. Eine gute Heuristik ist, den Behälter mit dem kleinsten Produkt aus Bevölkerung und Breite zu finden. Löschen Sie es und mischen Sie es mit seinem linken oder rechten Nachbarn zusammen (je nachdem, welcher der Nachbarn selbst das kleinste Produkt aus Breite und Bevölkerungszahl hat). Fertig! Beachten Sie, dass beim Zusammenführen oder Aufteilen von Behältern Informationen verloren gehen. Dies ist jedoch unvermeidlich. Sie haben nur festen Speicher.

Dieser Algorithmus ist insofern nett, als er sich mit all Arten von Eingabeströmen befassen wird und gute Ergebnisse liefert. Wenn Sie den Luxus haben, die Musterreihenfolge zu wählen, ist eine Stichprobe am besten, da dadurch Aufteilungen und Zusammenführungen minimiert werden.

Mit dem Algorithmus können Sie auch jedes Perzentil abfragen, nicht nur den Median, da Sie eine vollständige Verteilungsschätzung haben.

Ich verwende diese Methode in meinem eigenen Code an vielen Stellen, hauptsächlich zum Debuggen von Protokollen. Dabei haben einige Statistiken, die Sie aufnehmen, eine unbekannte Verteilung. Mit diesem Algorithmus müssen Sie nicht im Voraus raten.

Der Nachteil ist die ungleiche Bin-Breite, was bedeutet, dass Sie für jedes Sample eine binäre Suche durchführen müssen, sodass Ihr Netto-Algorithmus O (NlogN) ist.

7
SPWorley

Davids Vorschlag scheint der sinnvollste Ansatz zur Annäherung an den Medianwert zu sein.

Ein laufendes mean für dasselbe Problem ist viel einfacher zu berechnen:

Mn = Mn-1 + ((Vn - Mn-1)/n)

Wo Mn ist der Mittelwert von n Werten, Mn-1 ist der vorherige Mittelwert und Vn ist der neue Wert.

Mit anderen Worten, der neue Mittelwert ist der vorhandene Mittelwert plus die Differenz zwischen dem neuen Wert und dem Mittelwert, dividiert durch die Anzahl der Werte.

Im Code würde dies ungefähr so ​​aussehen:

new_mean = prev_mean + ((value - prev_mean) / count)

natürlich möchten Sie vielleicht sprachspezifische Dinge wie Rundungsfehler mit Gleitkommazahlen usw. berücksichtigen.

3
GrahamS

Ich glaube nicht, dass es möglich ist, die Liste im Gedächtnis zu haben. Sie können sich natürlich mit annähern

  • durchschnitt, wenn Sie wissen, dass die Daten symmetrisch verteilt sind
  • oder einen korrekten Medianwert einer kleinen Teilmenge von Daten berechnen (die in den Speicher passen) - wenn Sie wissen, dass Ihre Daten die gleiche Verteilung über die Stichprobe haben (z. B. dass das erste Element dieselbe Verteilung hat wie das letzte)
3
Grzenio

Suchen Sie Min und Max der Liste, die N Elemente enthält, durch lineare Suche und benennen Sie sie als HighValue und LowValue . MedianIndex = (N + 1)/2

Binäre Suche erster Ordnung:

Wiederholen Sie die folgenden 4 Schritte, bis LowValue <HighValue ist.

  1. Erhalten Sie MedianValue ungefähr = (HighValue + LowValue)/2

  2. Hole NumberOfItemsWhichAreLessThanorEqualToMedianValue = K

  3. ist K = MedianIndex, geben Sie dann MedianValue zurück

  4. ist K> MedianIndex? dann HighValue = MedianValue Andernfalls LowValue = MedianValue

Es wird schneller sein, ohne Speicher zu verbrauchen 

Binäre Suche zweiter Ordnung:

LowIndex = 1 HighIndex = N

Wiederholen Sie die folgenden 5 Schritte bis (LowIndex <HighIndex)

  1. Ermitteln Sie den ungefähren DistrbutionPerUnit = (HighValue-LowValue)/(HighIndex-LowIndex)

  2. Ermitteln Sie den ungefähren MedianValue = LowValue + (MedianIndex-LowIndex) * DistributionPerUnit

  3. Hole NumberOfItemsWhichAreLessThanorEqualToMedianValue = K

  4. ist (K = MedianIndex)? MedianValue zurückgeben

  5. ist (K> MedianIndex)? dann HighIndex = K und HighValue = MedianValue Andernfalls LowIndex = K und LowValue = MedianValue

Es wird schneller als die 1. Ordnung sein, ohne Speicher zu verbrauchen 

Wir können auch daran denken, HighValue, LowValue und MedianValue mit HighIndex, LowIndex und MedianIndex in eine Parabola einzubauen, und können die dritte Ordnung der binären Suche erhalten, die schneller als die 2. Ordnung ist, ohne Speicher zu verbrauchen und so weiter ...

2
lakshmanaraj

Wenn sich die Eingabe in einem bestimmten Bereich befindet, beispielsweise 1 bis 1 Million, ist es einfach, ein Array von Zählungen zu erstellen: Lesen Sie den Code für "Quantile" und "Ibucket" hier: http://code.google.com/ p/ea-utils/source/durchsuchen/trunk/clipper/sam-stats.cpp

Diese Lösung kann als Annäherung verallgemeinert werden, indem die Eingabe in eine ganze Zahl innerhalb eines bestimmten Bereichs umgewandelt wird, wobei eine Funktion verwendet wird, die Sie auf dem Hinweg umkehren: IE: foo.Push ((int) input/1000000) und Quantile (foo) * 1000000 . 

Wenn Ihre Eingabe eine beliebige Zahl mit doppelter Genauigkeit ist, müssen Sie Ihr Histogramm automatisch skalieren, wenn Werte außerhalb des Bereichs eingegeben werden (siehe oben).

Sie können auch die in diesem Dokument beschriebene Methode der Median-Triplets verwenden: http://web.cs.wpi.edu/~hofri/medsel.pdf

0
Erik Aronesty

Ich habe die Idee der iterativen Quantilberechnung aufgegriffen. Es ist wichtig, einen guten Wert für Startpunkt und Eta zu haben, diese können aus Mittelwert und Sigma stammen. Also habe ich das programmiert:

Funktion QuantileIterative (Var x: Array von Double; n: Integer; p, Mittelwert, Sigma: Double): Double;
Var eta, Quantil, q1, dq: Double;
i: Ganze Zahl;
Start
Quantil: = Mittelwert + 1,25 * Sigma * (p-0,5);
q1: = Quantil;
eta: = 0,2 * Sigma/xy (1 + n, 0,75); // sollte nicht zu groß sein! Setzt die Genauigkeit
Für i: = 1 bis n Do quantile: = quantile + eta * (signum_smooth (x [i] - quantile, eta) + 2 * p - 1);
dq: = abs (q1-Quantil);
Wenn dq> eta
dann Beginnen
Wenn dq <3 * eta, dann eta: = eta/4;
Für i: = 1 bis n Do quantile: = quantile + eta * (signum_smooth (x [i] - quantile, eta) + 2 * p - 1);
Ende;
QuantileIterative: = Quantil
Ende;

Da der Median für zwei Elemente der Mittelwert wäre, habe ich eine geglättete Signum-Funktion verwendet und xy () ist x ^ y. Gibt es Ideen, um es besser zu machen? Wenn wir mehr a-priori-Kenntnisse haben, können wir natürlich Code mit min und max des Arrays, Skew usw. hinzufügen. Für große Daten würden Sie vielleicht kein Array verwenden, aber zum Testen ist es einfacher. 

0
user32038