inkrementelle Methode zum Zählen von Quantilen für große Datenmengen

9

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

Nehmen wir an, wir können die Daten nur durch einige Teile erhalten (d. h. eine Reihe einer großen Matrix). Um das Q3-Quantil zu zählen, muss man alle Teile der Daten erhalten und irgendwo speichern, dann sortiere sie und zähle das Quantil:

%Vor%

Ich möchte einen Weg finden, das Quantil zu erhalten, ohne die Daten in einer Zwischenvariablen zu speichern. Die beste Lösung wäre, einige Parameter der mittleren Ergebnisse für die erste Zeile zu zählen und sie dann Schritt für Schritt für die nächsten Zeilen anzupassen.

Hinweis:

  • Diese Datensätze sind wirklich groß (ca. 5000 Elemente in jeder Zeile)
  • Das Q3 kann geschätzt werden, es muss kein genauer Wert sein.
  • Ich nenne die Teile von Daten "Zeilen", aber sie können unterschiedliche Zeilen haben! Normalerweise variiert es nicht so sehr (+/- einige hundert Proben), aber es variiert!

Diese Frage ähnelt "On-line "(Iterator) Algorithmen zur Schätzung von statistischem Median, Modus, Schiefe, Kurtosis , aber ich muss Quantile zählen.

Es gibt auch einige Artikel in diesem Thema, nämlich:

Bevor ich versuchte, diese Ansätze zu implementieren, fragte ich mich, ob es vielleicht noch andere, schnellere Möglichkeiten gibt, die 0,25 / 0,75-Quantile zu zählen?

    
Gacek 14.05.2010, 20:14
quelle

6 Antworten

0

Inspiriert von diese Antwort Ich habe eine Methode erstellt, die die Quantile ziemlich gut schätzt. Es ist Näherung nahe genug für meine Zwecke.

Die Idee ist folgende: Das 0,75-Quantil ist tatsächlich ein Median aller Werte, der über dem globalen Median liegt. Das 0.25-Quantil ist ein Median aller Werte unterhalb des globalen Medians.

Wenn wir also den Median annähern können, können wir auf ähnliche Weise die Quantile annähern.

%Vor%

Anmerkungen:

  • Wenn die Verteilung Ihrer Daten merkwürdig ist, müssen Sie ein größeres eta haben, um zu den seltsamen Daten zu passen. Aber die Genauigkeit wird schlechter sein.
  • Wenn die Verteilung merkwürdig ist, Sie aber die Gesamtgröße Ihrer Sammlung kennen (dh N), können Sie den Parameter eta auf diese Weise anpassen: am Anfang wird eta fast gleich einem großen Wert gesetzt ( dh 0,2). Wenn die Schleife übergeben wird, senken Sie den Wert von eta . Wenn Sie also fast das Ende der Sammlung erreicht haben, ist eta fast gleich 0 (z. B. in loop compute it so: eta = 0.2 - 0.2*(i/N);
Gacek 25.05.2010, 14:45
quelle
1

Ich habe die Idee, Buckets zu verwenden. Beschränken Sie sich nicht auf 100 Eimer - Sie könnten auch 1 Million verwenden. Der schwierige Teil besteht darin, Ihre Bucket-Bereiche so auszuwählen, dass alles nicht in einem einzigen Bucket endet. Der beste Weg, Ihre Bucket-Bereiche zu schätzen, ist wahrscheinlich, eine vernünftige Stichprobe Ihrer Daten zu nehmen, die 10% und 90% Quantile mit dem einfachen Sortieralgorithmus zu berechnen und dann gleich große Buckets zu generieren, um diesen Bereich zu füllen. Es ist nicht perfekt, aber wenn Ihre Daten nicht von einer super-seltsamen Distribution stammen, sollte es funktionieren.

Wenn Sie keine Stichproben machen können, haben Sie mehr Probleme. Basierend auf der erwarteten Datenverteilung können Sie eine erste Bucketing-Schätzung auswählen. Wenn Sie dann einen Bucket durchlaufen (in der Regel den ersten oder letzten Bucket), arbeiten Sie während der Verarbeitung Ihrer Daten erneut mit einem neuen Bucket-Bereich.

    
Keith Randall 15.05.2010 00:01
quelle
1

Es gibt einen neueren und viel einfacheren Algorithmus dafür, der sehr gute Schätzungen der extremen Quantile liefert.

Die Grundidee ist, dass kleinere Bins an den Extremen so verwendet werden, dass sie die Größe der Datenstruktur begrenzen und eine höhere Genauigkeit für kleine oder große q garantieren. Der Algorithmus ist in mehreren Sprachen und vielen Paketen verfügbar. Die MergingDigest-Version erfordert keine dynamische Zuordnung ... Sobald das MergingDigest instanziiert ist, ist keine weitere Heap-Zuweisung erforderlich.

Siehe Ссылка

    
Ted Dunning 27.02.2017 09:43
quelle
0
  1. Ermitteln Sie nur die Daten, die Sie wirklich benötigen - d. h., welche Werte als Schlüssel zum Sortieren verwendet werden, und nicht alles, was damit verbunden ist.
  2. Sie können wahrscheinlich Tony Hoares Select-Algorithmus verwenden, um Ihr Quantil schneller zu finden als das Sortieren aller Daten.
Jerry Coffin 14.05.2010 20:26
quelle
0

Wenn Ihre Daten eine Gaußverteilung haben, können Sie die Quantile aus der Standardabweichung schätzen. Ich gehe davon aus, dass Ihre Daten nicht Gauß-verteilt sind oder Sie einfach nur die SD verwenden.

Wenn Sie Ihre Daten zweimal durchreichen können, würde ich Folgendes tun:

  • Erster Durchlauf, berechnen Sie die Max, Min, SD und Mittelwert.
  • Zweiter Durchgang, dividiere den Bereich [min, max] in eine Anzahl von Eimern (z. B. 100); Machen Sie dasselbe für (Mittelwert - 2 * SD, Mittelwert + 2 * SD) (mit zusätzlichen Buckets für Ausreißer). Durchlaufen Sie die Daten erneut und werfen Sie Zahlen in diese Eimer.
  • Zählen Sie die Buckets, bis Sie bei 25% und 75% der Daten sind. Wenn Sie extravagant werden möchten, können Sie zwischen Bucket-Werten interpolieren. (Wenn Sie beispielsweise 10% eines Buckets benötigen, um Ihr 25. Quantil zu treffen, nehmen Sie an, dass der Wert 10% des Weges von der unteren Grenze zur oberen Grenze beträgt.)

Dies sollte Ihnen einen ziemlich guten linearen Zeitalgorithmus geben, der für die meisten Sätze nicht-perverser Daten in Ordnung ist.

    
Rex Kerr 14.05.2010 21:18
quelle
0

q-digest ist ein ungefährer Online-Algorithmus, mit dem Sie Quantile berechnen können: Ссылка

Hier ist eine Implementierung:

Ссылка

    
Haozhun 21.10.2015 16:22
quelle