Algorithmus zur dynamischen Überwachung von Quantilen

24

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.

sinoTrinity
quelle
Einige Vorschläge (im Zusammenhang mit der Schätzung von Medianwerten) finden Sie im Thread unter stats.stackexchange.com/q/346/919 .
whuber
3
Diese Frage wird gecrosspostet auf math.SE.
Kardinal

Antworten:

16

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 0x 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 6 entwickelt werdenx0x6x0x6x0x6x0x6. 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,y,n)nx1,x2,,xny

y=(x[k+1](n)x[k+2](n)x[k+m](n)).

In dieser Notation bezeichnet den i - kleinsten der bisher gelesenen n x -Werte. m ist eine Konstante, die Größe des Puffers y .x[i](n)ithn xmy

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:ymqqxn+1

  • Wenn , Inkrement k .xn+1<x[k+1](n)k

  • Wenn , nichts zu tun.xn+1>x[k+m](n)

  • Andernfalls fügen Sie in y ein .xn+1y

In jedem Fall erhöhen Sie .n

Die Einfügeprozedur setzt in sortierter Reihenfolge in y und eliminiert dann einen der Extremwerte in y :xn+1yy

  • Wenn , dann entferne x ( n ) [ k + 1 ] von y und erhöhe k ;k+m/2<nqx[k+1](n)yk

  • Ansonsten entferne von y .x[k+m](n)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 ( Nmnx[qn](n)x[qn](n)ymN), 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)/nq

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=2Nq=.5x[qn](n)N=1012=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( √ erfolgenO(log(N))O(log(N))O(1)mal. Somit betragen die Berechnungskosten dieses AlgorithmusO(N+O(N)in der Zeit undO(O(N+Nlog(N))=O(N)eingelagert.O(N)

whuber
quelle
This is an extended work of P2 algorithm. [link] sim.sagepub.com/content/49/4/159.abstract. The storage is still too much for my application, which runs on small sensors with a total of 10K RAM. I can consume a few hundred bytes at most for quantile estimation only.
sinoTrinity
@whuber Actually I implement the extended P2 and test it with generated samples from various distributions such as uniform and exponential, where it works great. But when I apply it against data from my application, whose distribution is unknown, sometimes it fails to converge and yields relative error (abs(estimation - actual) / actual) up to 300%.
sinoTrinity
2
@sino The quality of the algorithm compared to using all the data shouldn't depend on the heaviness of the tails. A fairer way to measure error is this: let F be the empirical cdf. For an estimate q^ of the q percentile, what is the difference between F(q^) and F(q)? If it is on the order of 1/n you're doing awfully well. In other words, just what percentile is the P2 algorithm returning for your data?
whuber
You are right. I just measured the F(qˆ) and F(q) for the case I mentioned with relative error up to 300%. For q of 0.7, qˆ is almost 0.7, resulting in negligible error. However, for q of 0.9, qˆ seems to be around 0.95. I guess that's why I have huge error of up to 300%. Any idea why it's 0.95, not 0.9? BTW, can I post figure here and how can I post mathematical formula as you did?
sinoTrinity
2
@whuber I'm pretty confident that my implementation conforms to extended P2. 0.9 still goes to 0.95 or even larger when I simultaneously estimate 0.8, 0.85, 0.9, 0.95 quantiles. However, 0.9 goes very close to 0.9 if 0.8, 0.85, 0.9, 0.95 and 1.0 quantiles are tracked at the same time.
sinoTrinity
5

I think whuber's suggestion is great and I would try that first. However, if you find you really can't accomodate the O(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, , p11/12, p, p+(1p)/12, , p+11(1p)/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(1+cos(2i1)π22) and p+(1p)/2(1+cos(2i1)π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...

Erik P.
quelle
+1 I think this is a great idea given the OP's constraints. All one can hope for is an approximation, so the trick is to pick bins that have a high likelihood of being narrow and containing the desired quantile.
whuber
3

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.

denis
quelle
books.google.com/… for a version that doesn't require Flash.
ZachB
2

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

benhamner
quelle
The computational resources required of the algorithm you link to are unnecessarily large and do not meet the requirements of this question.
whuber
2

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.

Marc
quelle
1

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)

Ludo
quelle