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