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 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?
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:
eta haben, um zu den seltsamen Daten zu passen. Aber die Genauigkeit wird schlechter sein. 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);
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.
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 Ссылка
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:
Dies sollte Ihnen einen ziemlich guten linearen Zeitalgorithmus geben, der für die meisten Sätze nicht-perverser Daten in Ordnung ist.
Tags und Links algorithm statistics numerical-methods quantile