inkrementaler Weg des Zählens Quantile für große Menge von Daten

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

Frage

Ich brauche die Quantile für eine große Menge von Daten zu zählen.

Nehmen wir an, wir die Daten über einige Abschnitte nur bekommen kann (das heißt eine Reihe einer großen Matrix). Um den Q3 Quantil ein Bedarf zu zählen alle die Teile der Daten zu erhalten und speichern Sie es irgendwo, dann sortieren sie und das Quantil zählen: 

List<double> allData = new List<double>();
// This is only an example; the portions of data are not really rows of some matrix
foreach(var row in matrix) 
{
    allData.AddRange(row);
}

allData.Sort();
double p = 0.75 * allData.Count;
int idQ3 = (int)Math.Ceiling(p) - 1;
double Q3 = allData[idQ3];

Ich möchte einen Weg finden, das Quantil zu erhalten, ohne die Daten in einer Zwischengröße zu speichern. Die beste Lösung wäre, einige Parameter der Mitte der Ergebnisse für die erste Zeilenanzahl und passen Sie sich für die nächsten Zeilen Schritt für Schritt.

Hinweis:

  • Diese Datensätze sind wirklich groß (ca 5000 Elemente in jeder Zeile)
  • Die Q3 kann abgeschätzt werden, es muss keine exakte Wert sein.
  • Ich nenne die Teile der Daten „Reihen“, aber sie können unterschiedliche leghts haben! Normalerweise ändert sich nicht so viel (+/- paar hundert Proben), aber es ändert sich!

Diese Frage ist ähnlich wie „On-line “(Iterator) Algorithmen zur Schätzung statistischen Median, Modus, Schiefe, Kurtosis , aber ich brauche quantiles zu zählen.

Auch gibt es einige Artikel zu diesem Thema, d.h .:

Bevor Sie versuchen, diese Ansätze zu implementieren, fragte ich mich, ob es vielleicht noch andere, schnellere Wege, die 0,25 / 0,75 quantiles Zählen?

War es hilfreich?

Lösung 5

Inspiriert von diese Antwort ich habe eine Methode, die die Quantile recht gut schätzt. Es ist Annäherung nahe genug für meine Zwecke.

Die Idee ist folgende: die 0,75 Quantil in der Tat ein Median aller Werte, die liegt über dem globalen Median. Und jeweils 0,25 Quantil ist ein Median aller Werte unter dem globalen Median.

Wenn wir also den Median annähern können, können wir in ähnlicher Weise die Quantile nähern. 

double median = 0;
double q1 = 0;
double q3 = 0;
double eta = 0.005;

foreach( var value in listOfValues) // or stream, or any other large set of data...
{
    median += eta * Math.Sign(p.Int - median);
}
// Second pass. We know the median, so we can count the quantiles.
foreach(var value in listOfValues)
{ 
    if(p.Int < median)
        q1 += eta*Math.Sign(p.Int - q1);
    else
        q3 += eta*Math.Sign(p.Int - q3);
}

Bemerkungen:

  • Wenn die Verbreitung Ihrer Daten seltsam ist, müssen Sie größere eta haben, um auf die fremden Daten zu passen. Aber die Genauigkeit schlechter sein wird.
  • Wenn die Verteilung ist seltsam, aber Sie wissen, die Gesamtgröße Ihrer Sammlung (d N) können Sie den eta Parameter auf diese Weise einstellen kann: bei der beggining die eta gesetzt fast gleich etwas großen Wert zu sein (das heißt 0,2). Da die Schleife verläuft, so dass der Wert eta senken, wenn man fast das Ende der Sammlung zu erreichen, wird die eta fast gleich 0 sein (beispielsweise compute in Schleife es wie folgt aus: eta = 0.2 - 0.2*(i/N);

Andere Tipps

Ich schließe ich die Idee des Eimer mit. Beschränken Sie sich nicht zu 100 Eimer - könnte genauso gut eine Million verwenden. Der schwierige Teil ist Ihre Eimer Bereiche zu holen, so dass alles in einem einzigen Eimer nicht am Ende. Wahrscheinlich der beste Weg, um Ihre Eimer Bereiche zu schätzen ist eine angemessene Stichprobe Ihrer Daten zu nehmen, berechnet das 10% und 90% Quantile den einfachen Sortieralgorithmus verwendet wird, dann gleich große Eimer zu erzeugen, um diesen Bereich zu füllen. Es ist nicht perfekt, aber wenn Ihre Daten nicht von einer Super-seltsamer Verteilung ist, sollte es funktionieren.

Wenn Sie nicht Stichprobe tun können, sind Sie in mehr Mühe. Sie können eine erste Bucketing Vermutung basierend auf Ihre erwartete Datenverteilung wählen, dann, während sie durch Ihre Daten zu arbeiten, wenn eine Schaufel (in der Regel die erste oder letzte Eimer) übervoll wird, wieder von vorn anfangen mit einem neuen Eimer Bereich.

Es ist ein neuerer und viel einfacher Algorithmus für diese, die sehr gute Schätzungen der extremen Quantile bietet.

Die Grundidee ist, dass kleinere Fächer an den Extremen in einer Weise verwendet werden, daß sowohl die Größe der Datenstruktur begrenzt und garantiert eine höhere Genauigkeit für kleine oder große q. Der Algorithmus ist in mehreren Sprachen und viele Pakete zur Verfügung. Die MergingDigest Version erfordert keine dynamische Zuweisung ... sobald die MergingDigest instanziiert wird, wird keine weitere Heapzuordnung erforderlich.

Siehe https://github.com/tdunning/t-digest

  1. Es werden nur die Daten abrufen Sie wirklich brauchen - d. H, unabhängig von Wert (e) ist / sind als Schlüssel verwendet werden, zum Sortieren, nicht alles, was mit ihm verbunden
  2. Sie können sich wahrscheinlich Tony Hoare Select-Algorithmus verwenden, um Ihre Quantils schneller zu finden, als alle die Daten zu sortieren.

Wenn Ihre Daten eine Gaußsche Verteilung hat, können Sie die Quantile aus der Standardabweichung abzuschätzen. Ich nehme an, Ihre Daten nicht gaußverteiltes oder Sie würden einfach mal so die SD werden.

Wenn Sie zweimal Ihre Daten passieren kann, würde ich Folgendes tun:

  • First Pass berechnet den max, min, SD und Mittelwert.
  • Second Pass teilt den Bereich [min, max] in eine Anzahl von Schaufeln (z.B. 100); das gleiche für (Mittelwert - 2 * SD, Mittelwert + 2 * SD) (mit extra Eimer für Ausreißer). Dann wieder die Daten durchlaufen, werfend Zahlen in diese Eimer.
  • Count Eimer, bis Sie bei 25% und 75% der Daten sind. Wenn Sie extra Lust bekommen möchten, können Sie zwischen Bucketwerte interpoliert werden. (Das heißt, wenn Sie benötigen 10% eines Eimers Ihr 25. Quantil zu treffen, übernehmen der Wert 10% des Weges ist von der niedrigen auf die obere Grenze gebunden ist.)

Dies sollte Ihnen eine ziemlich gute lineare Zeit Algorithmus, der für die meisten Arten von nicht-ganz-perverse Daten in Ordnung funktioniert.

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