Online-Schätzung von Quartilen ohne Speicherung von Beobachtungen

Ich muss Quartile (Q1, Median und Q3) in Echtzeit mit einer großen Datenmenge berechnen, ohne die Beobachtungen zu speichern. Ich habe zuerst den P-Quadrat-Algorithmus (Jain / Chlamtac) ausprobiert, war aber nicht zufrieden damit (etwas zu viel CPU-Auslastung und nicht überzeugt von der Genauigkeit zumindest meines Datensatzes).

Ich verwende jetzt den FAME-Algorithmus ( Feldman / Shavitt ) zum Schätzen des Medians im laufenden Betrieb und versuche, den Algorithmus so abzuleiten, dass auch Q1 und Q3 berechnet werden:

M = Q1 = Q3 = first data value 
step =step_Q1 = step_Q3 = a small value
for each new data :
        # update median M 
        if M > data:
            M = M - step
        elif M < data:
            M = M + step
        if abs(data-M) < step:
            step = step /2

        # estimate Q1 using M
        if data < M:
            if Q1 > data:
                Q1 = Q1 - step_Q1
            elif Q1 < data:
                Q1 = Q1 + step_Q1
            if abs(data - Q1) < step_Q1:
                step_Q1 = step_Q1/2
        # estimate Q3 using M
        elif data > M:
            if Q3 > data:
                Q3 = Q3 - step_Q3
            elif Q3 < data:
                Q3 = Q3 + step_Q3
            if abs(data-Q3) < step_Q3:
                step_Q3 = step_Q3 /2

Um fortzufahren, wird einfach der im laufenden Betrieb erhaltene Median M verwendet, um den Datensatz in zwei zu teilen, und dann wird derselbe Algorithmus für Q1 und Q3 wiederverwendet.

Das scheint irgendwie zu funktionieren, aber ich kann nicht demonstrieren (ich bin kein Mathematiker). Ist es fehlerhaft? Ich würde mich über jeden Vorschlag oder jede mögliche andere Technik freuen, die zum Problem passt.

Vielen Dank für Ihre Hilfe !

==== EDIT =====

Für diejenigen, die sich für solche Fragen interessieren, endete ich nach ein paar Wochen damit, Reservoir Sampling mit einem Ausgleichsbehälter von 100 Werten zu verwenden, und es ergab sehr zufriedenstellende Ergebnisse (für mich).

quantiles median online Louis Hugues
quelle

Suchen Sie einen Beweis dafür, dass Q1 und Q2 zu den wahren Quantilen konvergieren, wenn die Anzahl der Beispiele ähnlich wie bei der Markov-Kettenanalyse in den von Ihnen verknüpften Folien zunimmt? In Bezug auf die Implementierung scheint der obige Algorithmus nicht fehlerhaft zu sein (ich habe die Approximation von Quantilen für die Standardnormale in R getestet und der Algorithmus funktioniert einwandfrei).

Theja

@Theja danke, ich suche keinen Beweis (zu viel Arbeit), sondern nur Ratschläge und Kommentare. Das Hauptproblem, das ich sehe, besteht darin, die Berechnung auf der laufenden Schätzung des Medians zu basieren, wie whuber gezeigt hat.

Louis Hugues

Antworten:

Der Median ist der Punkt, an dem 1/2 der Beobachtungen unten und 1/2 oben liegen. In ähnlicher Weise ist das 25. Perzentil der Median für Daten zwischen dem Min und dem Median, und das 75. Perzentil ist der Median zwischen dem Median und dem Max. Also ja, ich denke, Sie sind auf einem soliden Fundament, wenn Sie den Median-Algorithmus anwenden, den Sie zuerst verwenden der gesamte Datensatz, um ihn zu partitionieren, und dann auf die beiden resultierenden Teile.

Update :

Diese Frage zum Stackoverflow führt zu dieser Arbeit: Raj Jain, Imrich Chlamtac: Der P²-Algorithmus zur dynamischen Berechnung von Quantiilen und Histogrammen ohne Speicherung von Beobachtungen. Kommun. ACM 28 (10): 1076-1085 (1985), dessen Zusammenfassung darauf hinweist, dass es für Sie wahrscheinlich von großem Interesse ist:

Für die dynamische Berechnung des Medians und anderer Quantile wird ein heuristischer Algorithmus vorgeschlagen. Die Schätzungen werden dynamisch erstellt, wenn die Beobachtungen generiert werden. Die Beobachtungen werden nicht gespeichert; Daher hat der Algorithmus eine sehr kleine und feste Speicheranforderung, unabhängig von der Anzahl der Beobachtungen. Dies macht es ideal für die Implementierung in einem Quantil-Chip, der in industriellen Steuerungen und Rekordern verwendet werden kann. Der Algorithmus wird weiter auf die Darstellung von Histogrammen erweitert. Die Genauigkeit des Algorithmus wird analysiert.

Avraham
quelle

Diese Antwort übersieht zwei subtile Punkte, von denen einer unwichtig, der andere jedoch möglicherweise sehr wichtig ist. Das unwichtige ist, dass die Doppelaufteilungstechnik die oberen und unteren Scharniere berechnet , die sich je nach Stichprobengröße geringfügig vom Median unterscheiden können. Das Wichtige ist, dass die doppelte Aufteilung auf einer laufenden Schätzung des Medians basiert . Bei Abweichungen zwischen dieser Schätzung und dem tatsächlichen Median variieren auch die Scharniere. Intuitiv sollte dies kein Problem sein, da die Datenmenge zunimmt, es handelt sich jedoch um ein Problem, das einer Analyse bedarf.

whuber

n

$n$

1 : 3

$1:3$

2 : 2

$2:2$ und nimmt dann eine dieser "2" und teilt es

1 : 1

$1:1$ . Ich bin zwar kein Theoretiker, aber im Allgemeinen wäre der Unterschied zwischen beiden nicht um höchstens eine Stelle nach links oder rechts verschieden und würde als konvergieren

n

$n$ erhöht sich? Ja, es könnte eine pathologische Verteilung erstellt werden, die jedoch auch unter einer direkten Mittelwertschätzung leiden würde. Natürlich ist es besser, alle Werte zu speichern.

Avraham

@Avraham, danke für den Hinweis auf das Papier, wie ich bereits erwähnte, habe ich den P-Quadrat-Algorithmus von Chain und Chlamtac ausprobiert. Auf meinem Datensatz gibt der von mir beschriebene Algorithmus ein besseres Ergebnis (MSE) und ist schneller. Also habe ich mich gefragt, ob es trotzdem ein Problem geben könnte. Wie bereits erwähnt, ist die Tatsache, dass eine laufende Schätzung verwendet wird, ein potenzielles Problem. aber ich weiß nicht, ob es wirklich wichtig ist oder nicht.

Louis Hugues

Hoppla, habe das gesehen und vergessen. Entschuldigen Sie.

Avraham

Eine geringfügige Änderung der von Ihnen veröffentlichten Methode, mit der Sie ein beliebiges Perzentil berechnen können, ohne alle Quantile berechnen zu müssen. Hier ist der Python-Code:

class RunningPercentile:
    def __init__(self, percentile=0.5, step=0.1):
        self.step = step
        self.step_up = 1.0 - percentile
        self.step_down = percentile
        self.x = None

    def push(self, observation):
        if self.x is None:
            self.x = observation
            return

        if self.x > observation:
            self.x -= self.step * self.step_up
        elif self.x < observation:
            self.x += self.step * self.step_down
        if abs(observation - self.x) < self.step:
            self.step /= 2.0

und ein Beispiel:

import numpy as np
import matplotlib.pyplot as plt

distribution = np.random.normal
running_percentile = RunningPercentile(0.841)
observations = []
for _ in range(1000000):
    observation = distribution()
    running_percentile.push(observation)
    observations.append(observation)

plt.figure(figsize=(10, 3))
plt.hist(observations, bins=100)
plt.axvline(running_percentile.x, c='k')
plt.show()

parrowdice
quelle