Szacowanie online kwartyli bez przechowywania obserwacji

Muszę obliczyć kwartyle (Q1, mediana i Q3) w czasie rzeczywistym na dużym zestawie danych bez zapisywania obserwacji. Najpierw wypróbowałem algorytm P-kwadrat (Jain / Chlamtac), ale nie byłem z niego zadowolony (nieco za dużo procesora i nie przekonałem się precyzją przynajmniej w moim zestawie danych).

Używam teraz algorytmu FAME ( Feldman / Shavitt ) do szacowania mediany w locie i próbuję wyprowadzić algorytm, aby obliczyć również Q1 i Q3:

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

Aby wznowić, po prostu używa mediany M uzyskanej w locie, aby podzielić zestaw danych na dwie części, a następnie ponownie użyć tego samego algorytmu zarówno dla Q1, jak i Q3.

To wydaje się działać jakoś, ale nie jestem w stanie tego zademonstrować (nie jestem matematykiem). Czy to jest wadliwe? Byłbym wdzięczny za wszelkie sugestie lub inne techniki pasujące do problemu.

Bardzo ci dziękuje za pomoc !

==== EDYCJA =====

Dla tych, którzy są zainteresowani takimi pytaniami, po kilku tygodniach w końcu skończyłem po prostu z użyciem próbkowania w zbiorniku z rewervoir 100 wartości i dało to bardzo satysfakcjonujące wyniki (dla mnie).

quantiles median online Louis Hugues
źródło

Czy szukasz dowodu, że pytania Q1 i Q2 są zbieżne z prawdziwymi kwantylami, gdy liczba przykładów rośnie w sposób podobny do analizy łańcucha markowa na połączonych slajdach? Pod względem implementacji powyższy algorytm nie wydaje się wadliwy (testowałem aproksymujące kwantyle dla standardowej normy w R i algorytm działa dobrze).

Theja

@ Theja dziękuję, nie szukam dowodu (zbyt dużo pracy), a jedynie porady i komentarze. Głównym problemem, jaki widzę, jest oparcie obliczeń na oszacowaniu mediany, jak wskazał Whuber.

Louis Hugues,

Odpowiedzi:

Mediana to punkt, w którym 1/2 obserwacji spada poniżej i 1/2 powyżej. Podobnie 25. perecentyl jest medianą danych między min a medianą, a 75 percentyl jest medianą między medianą a maksimum, więc tak, myślę, że jesteś na solidnym gruncie, stosując dowolny algorytm mediany, którego użyjesz najpierw cały zestaw danych, aby go podzielić na partycje, a następnie na dwóch wynikowych elementach.

Aktualizacja :

To pytanie dotyczące przepełnienia stosu prowadzi do tego artykułu: Raj Jain, Imrich Chlamtac: Algorytm P² do dynamicznego obliczania ilości i histogramów bez przechowywania obserwacji. Commun ACM 28 (10): 1076-1085 (1985), którego streszczenie wskazuje, że prawdopodobnie jest to dla ciebie bardzo interesujące:

Algorytm heurystyczny jest proponowany do obliczeń dynamicznych q mediany i innych kwantyli. Szacunki są tworzone dynamicznie w miarę generowania obserwacji. Obserwacje nie są przechowywane; dlatego algorytm ma bardzo małe i stałe wymagania dotyczące przechowywania, niezależnie od liczby obserwacji. To sprawia, że idealnie nadaje się do implementacji w chipie kwantowym, który może być wykorzystywany w kontrolerach przemysłowych i rejestratorach. Algorytm został rozszerzony na wykres histogramu. Dokładność algorytmu jest analizowana.

Avraham
źródło

Ta odpowiedź pomija dwa subtelne punkty, jeden nieważny, ale drugi być może bardzo ważny. Nieważne jest to, że technika podwójnego podziału oblicza górne i dolne zawiasy, które mogą nieznacznie różnić się od mediany, w zależności od wielkości próbki. Ważne jest to, że podwójne rozdzielanie wydaje się opierać na bieżącym oszacowaniu mediany. Wszelkie różnice między tym oszacowaniem a rzeczywistą medianą spowodują również różnice w zawiasach. Intuicyjnie nie powinno to stanowić problemu, ponieważ ilość danych rośnie, ale jest to problem wymagający analizy.

whuber

n

$n$

1 : 3

$1:3$

2 : 2

$2:2$

1 : 1

$1:1$

n

$n$

@Avraham, dzięki za wskazanie artykułu, jak już wspomniałem, wypróbowałem już algorytm P-kwadratowy od Chain i Chlamtac. w moim zestawie danych algo, które opisałem, daje lepszy wynik (MSE) i jest szybsze. Pytałem więc, czy może to mieć jakiś problem. Jak zauważył whuber, fakt, że wykorzystuje bieżące oszacowanie, jest potencjalnym problemem; ale nie wiem, czy to naprawdę ważne, czy nie.

Louis Hugues,

Ups, widziałem to i zapomniałem. Przepraszam.

Avraham

Bardzo niewielka zmiana w opublikowanej metodzie i można obliczyć dowolny dowolny percentyl, bez konieczności obliczania wszystkich kwantyli. Oto kod Python:

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

i przykład:

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
źródło