Algorithmus zur dynamischen Überwachung von Quantilen

Ich möchte das Quantil einiger Daten schätzen. Die Daten sind so groß, dass sie nicht im Speicher gespeichert werden können. Und Daten sind nicht statisch, es kommen immer neue Daten. Kennt jemand einen Algorithmus zur Überwachung der Quantile der bisher beobachteten Daten mit sehr begrenztem Speicher und Rechenaufwand? Ich finde P2-Algorithmus nützlich, aber es funktioniert nicht sehr gut für meine Daten, die extrem stark verteilt sind.

Der P2-Algorithmus ist ein guter Fund. Dabei werden mehrere Schätzungen des Quantils vorgenommen, diese regelmäßig aktualisiert und das Quantil mithilfe einer quadratischen (nicht linearen, nicht kubischen) Interpolation geschätzt. Die Autoren behaupten, dass die quadratische Interpolation in den Schwänzen besser funktioniert als die lineare Interpolation, und Kubik würde zu wählerisch und schwierig werden.

Sie geben nicht genau an, wie dieser Ansatz für Ihre "schwerfälligen" Daten fehlschlägt, aber es ist leicht zu erraten: Schätzungen extremer Quantile für schwerfällige Verteilungen werden instabil, bis eine große Menge von Daten erfasst wird. Dies wird jedoch (in geringerem Maße) ein Problem sein, selbst wenn Sie alle Daten speichern würden. Erwarten Sie also keine Wunder!

Setzen Sie auf jeden Fall Hilfsmarker - nennen wir sie und x 6 -, in denen Sie sich sicher sind, dass das Quantil liegt, und speichern Sie alle Daten, die zwischen x 0 und x 6 liegen . Wenn Ihr Puffer voll ist, müssen Sie diese Marker aktualisieren und dabei immer x 0 ≤ x 6 beibehalten . Ein einfacher Algorithmus, um dies zu tun, kann aus einer Kombination von (a) der aktuellen P2-Schätzung des Quantils und (b) gespeicherten Zählwerten der Anzahl von Daten kleiner als x 0 und der Anzahl von Daten größer als x $x_0$$x_6$$x_0$$x_6$$x_0 \le x_6$$x_0$$x_6$. Auf diese Weise können Sie das Quantil mit hoher Sicherheit genau so gut schätzen, als ob Sie den gesamten Datensatz immer zur Verfügung hätten, aber Sie benötigen nur einen relativ kleinen Puffer.

Insbesondere schlage ich eine Datenstruktur , um Teilinformationen über eine Folge von n Datenwerten x 1 , x 2 , ... , x n aufrechtzuerhalten . Hier ist y eine verknüpfte Liste$(k, \mathbf{y}, n)$$n$$x_1, x_2, \ldots, x_n$$\mathbf{y}$

In dieser Notation bezeichnet den i - kleinsten der bisher gelesenen n x -Werte. m ist eine Konstante, die Größe des Puffers y .$x^{(n)}_{[i]}$$i^\text{th}$$n$ $x$$m$$\mathbf{y}$

Der Algorithmus beginnt damit, dass mit den ersten m gefundenen Datenwerten gefüllt und in die kleinste bis größte sortierte Reihenfolge gebracht wird. Sei q das zu schätzende Quantil; zB q = 0,99. Beim Lesen von x n + 1 gibt es drei mögliche Aktionen:$\mathbf{y}$$m$$q$$q$$x_{n+1}$

• Wenn , Inkrement k .$x_{n+1} \lt x^{(n)}_{[k+1]}$$k$

• Wenn , nichts zu tun.$x_{n+1} \gt x^{(n)}_{[k+m]}$

• Andernfalls fügen Sie in y ein .$x_{n+1}$$\mathbf{y}$

In jedem Fall erhöhen Sie .$n$

Die Einfügeprozedur setzt in sortierter Reihenfolge in y und eliminiert dann einen der Extremwerte in y :$x_{n+1}$$\mathbf{y}$$\mathbf{y}$

• Wenn , dann entferne x ( n ) [ k + 1 ] von y und erhöhe k ;$k + m/2 \lt n q$$x^{(n)}_{[k+1]}$$\mathbf{y}$$k$

• Ansonsten entferne von y .$x^{(n)}_{[k+m]}$$\mathbf{y}$

Vorausgesetzt, ist ausreichend groß, wird diese Prozedur das wahre Quantil der Verteilung mit hoher Wahrscheinlichkeit einklammern. In jedem Stadium n kann es auf die übliche Weise in Bezug auf x ( n ) [ [ q n n ] und x ( n ) [ ⌈ q n ⌉ ] geschätzt werden , die wahrscheinlich in y liegen werden . (Ich glaube, m muss nur wie die Quadratwurzel der maximalen Datenmenge skalieren ( $m$$n$$x^{(n)}_{[\lfloor{q n}\rfloor]}$$x^{(n)}_{[\lceil{q n}\rceil]}$$\mathbf{y}$$m$$N$), aber ich habe keine strenge Analyse durchgeführt, um dies zu beweisen.) In jedem Fall wird der Algorithmus feststellen, ob er erfolgreich war (durch Vergleichen von und ( k + m ) / n mit q ).$k/n$$(k+m)/n$$q$

Testen mit bis zu 100.000 Werten mit undq=0,5(der schwierigste Fall) zeigen an, dass dieser Algorithmus eine 99,5% ige Erfolgsrate beim Erhalten des korrekten Werts von x ( n ) [ ⌊ q n ⌋ ] aufweist . Für einen Strom vonN=10 12 Werten würde dies einen Puffer von nur zwei Millionen erfordern (drei oder vier Millionen wären jedoch die bessere Wahl). Die Verwendung einer sortierten doppelt verknüpften Liste für den Puffer erfordertO(log($m = 2\sqrt{N}$$q=.5$$x^{(n)}_{[\lfloor{q n}\rfloor]}$$N=10^{12}$=O(log(N))Aufwand beim Erkennen und Löschen des Maximums oder Minimums sindO(1)Operationen. Das relativ teure Einfügen muss typischerweise nur mitO($O(\log(\sqrt{N}))$$O(\log(N))$$O(1)$mal. Somit betragen die Berechnungskosten dieses AlgorithmusO(N+$O(\sqrt{N})$in der Zeit undO($O(N + \sqrt{N} \log(N)) = O(N)$eingelagert.$O(\sqrt{N})$

I think whuber's suggestion is great and I would try that first. However, if you find you really can't accomodate the $O(\sqrt N)$ storage or it doesn't work out for some other reason, here is an idea for a different generalization of P2. It's not as detailed as what whuber suggests - more like a research idea instead of as a solution.

Instead of tracking the quantiles at $0$, $p/2$, $p$, $(1+p)/2$, and $1$, as the original P2 algorithm suggests, you could simply keep track of more quantiles (but still a constant number). It looks like the algorithm allows for that in a very straightforward manner; all you need to do is compute the correct "bucket" for incoming points, and the right way to update the quantiles (quadratically using adjacent numbers).

Say you keep track of $25$ points. You could try tracking the quantile at $0$, $p/12$, $\dotsc$, $p \cdot 11/12$, $p$, $p + (1-p)/12$, $\dotsc$, $p + 11\cdot(1-p)/12$, $1$ (picking the points equidistantly in between $0$ and $p$, and between $p$ and $1$), or even using $22$ Chebyshev nodes of the form $p/2 \cdot (1 + \cos \frac{(2 i - 1)\pi}{22})$ and $p + (1 - p)/2 \cdot (1 + \cos \frac{(2i-1)\pi}{22})$. If $p$ is close to $0$ or $1$, you could try putting fewer points on the side where there is less probability mass and more on the other side.

If you decide to pursue this, I (and possibly others on this site) would be interested in knowing if it works...

Press et al., Numerical Recipes 8.5.2 "Single-pass estimation of arbitrary quantiles" p. 435, give a c++ class IQAgent which updates a piecewise-linear approximate cdf.

This can be adapted from algorithms that determine the median of a dataset online. For more information, see this stackoverflow post - /programming/1387497/find-median-value-from-a-growing-set

Ich würde die Quantil-Regression betrachten. Sie können es verwenden, um eine parametrische Schätzung der Quantile zu bestimmen, die Sie anzeigen möchten. In Bezug auf die Normalität wird keine Annahme getroffen, sodass die Heteroskedastizität recht gut gehandhabt wird und eine rollende Fensterbasis verwendet werden kann. Grundsätzlich handelt es sich um eine bestrafte L1-Norm-Regression, daher ist sie nicht zu zahlenintensiv, und es gibt ein ziemlich umfangreiches R-, SAS- und SPSS-Paket sowie einige Matlab-Implementierungen. Hier finden Sie das Haupt- und das R- Paket-Wiki für weitere Informationen.

Bearbeitet:

Schauen Sie sich die Quervernetzung zum Austausch von Mathematikstapeln an: Jemand hat ein paar Artikel veröffentlicht, in denen im Wesentlichen die sehr einfache Idee dargestellt ist, nur ein rollierendes Fenster mit Ordnungsstatistiken zum Schätzen von Quantilen zu verwenden. Sie müssen lediglich die Werte vom kleinsten zum größten sortieren, das gewünschte Quantil auswählen und den höchsten Wert innerhalb dieses Quantils auswählen. Sie können den jüngsten Beobachtungen offensichtlich mehr Gewicht beimessen, wenn Sie der Meinung sind, dass sie für die tatsächlichen aktuellen Bedingungen repräsentativer sind. Dies wird wahrscheinlich grobe Schätzungen geben, aber es ist ziemlich einfach zu tun und Sie müssen nicht durch die Bewegungen des quantitativen Schwerhebens gehen. Nur ein Gedanke.

It is possible to estimate (and track) quantiles on an on-line basis (the same applies to the parameters of a quantile regression). In essence, this boils down to stochastic gradient descent on the check-loss function which defines quantile-regression (quantiles being represented by a model containing only an intercept), e.g. updating the unknown parameters as and when observations arrive.

See the Bell Labs paper "Incremental Quantile Estimation for Massive Tracking" ( ftp://ftp.cse.buffalo.edu/users/azhang/disc/disc01/cd1/out/papers/kdd/p516-chen.pdf)

Another important algorithm is M. Greenwald and S. Khanna 2004 - Space-efficient online computation of quantile summaries.