Jak obliczyć średnią ruchomą bez zachowywania liczby i sumy danych?

118

Próbuję znaleźć sposób na obliczenie ruchomej średniej skumulowanej bez przechowywania liczby i łącznych danych, które zostały do ​​tej pory odebrane.

Wymyśliłem dwa algorytmy, ale oba muszą przechowywać liczbę:

  • nowa średnia = ((stara liczba * stare dane) + następne dane) / następna liczba
  • nowa średnia = stara średnia + (następne dane - stara średnia) / następny licznik

Problem z tymi metodami polega na tym, że liczba staje się coraz większa, co powoduje utratę precyzji w wynikowej średniej.

Pierwsza metoda używa starego liczenia i następnego liczenia, które oczywiście różnią się o 1. To sprawiło, że pomyślałem, że być może istnieje sposób na usunięcie liczby, ale niestety jeszcze go nie znalazłem. To jednak doprowadziło mnie nieco dalej, w wyniku czego powstała druga metoda, ale liczba nadal jest obecna.

Czy to możliwe, czy po prostu szukam niemożliwego?

user1705674
źródło
1
Uwaga: numeryczne przechowywanie aktualnej sumy i aktualnej liczby jest najbardziej stabilnym sposobem. W przeciwnym razie dla wyższych liczników następny / (następny licznik) zacznie niedomiar. Więc jeśli naprawdę martwisz się utratą precyzji, zachowaj sumy!
AlexR,
1
Zobacz Wikipedię en.wikipedia.org/wiki/Moving_average
xmedeko

Odpowiedzi:

91

Możesz po prostu zrobić:

double approxRollingAverage (double avg, double new_sample) {

    avg -= avg / N;
    avg += new_sample / N;

    return avg;
}

Gdzie Njest liczba próbek, dla których chcesz przeprowadzić średnią. Należy zauważyć, że to przybliżenie jest równoważne wykładniczej średniej ruchomej. Zobacz: Obliczanie średniej kroczącej / ruchomej w C ++

Muis
źródło
3
Nie musisz dodawać 1 do N w tym przed tą linią? avg + = new_sample / N;
Damian
20
To nie jest całkowicie poprawne. @Muis opisuje wykładniczo ważoną ruchomą średnią, która czasami jest odpowiednia, ale nie jest dokładnie tym, czego żądał PO. Jako przykład rozważ zachowanie, którego oczekujesz, gdy większość punktów mieści się w przedziale od 2 do 4, ale jedna wartość to ponad milion. EWMA (tutaj) będzie przechowywać ślady tego miliona przez dłuższy czas. Skończony splot, jak wskazuje OP, utraciłby go natychmiast po N krokach. Ma zaletę stałego przechowywania.
jma
9
To nie jest średnia ruchoma. To, co opisujesz, to jednobiegunowy filtr, który tworzy wykładnicze odpowiedzi na skoki sygnału. Średnia ruchoma tworzy liniową odpowiedź o długości N.
ruhig brauner
3
Pamiętaj, że jest to dość dalekie od powszechnej definicji średniej. Jeśli ustawisz N = 5 i wpiszesz 5 5próbek, średnia wyniesie 0,67.
Dan Dascalescu,
2
@DanDascalescu Chociaż masz rację, że tak naprawdę nie jest to średnia krocząca, to podana przez Ciebie wartość różni się o rząd wielkości. Z avginicjowane 0, skończy się 3.36po upływie 5 5s, a 4.46po 10: cpp.sh/2ryql na długie średnie, to jest z pewnością przydatna przybliżeniem.
cincodenada
80
New average = old average * (n-1)/n + new value /n

Zakłada się, że liczba zmieniła się tylko o jedną wartość. W przypadku zmiany wartości M to:

new average = old average * (n-len(M))/n + (sum of values in M)/n).

To jest wzór matematyczny (uważam, że jest najbardziej efektywny), wierzę, że możesz samodzielnie wykonać dalsze kodowanie

Abdullah Al-Ageel
źródło
Co to jest suma nowej wartości? czy różni się to w jakiś sposób od „nowej wartości” w pierwotnej formule?
Michaił
@Mikhail w drugim przykładzie mnowe wartości są uwzględniane w nowej średniej. Uważam, że sum of new valuetutaj ma być suma mnowych wartości używanych do obliczenia nowej średniej.
Patrick Goley
9
Nieco bardziej efektywny w przypadku pierwszego: new_average = (old_average * (n-1) + new_value) / n- Usuwa jeden z podziałów.
Pixelstix
A co powiesz na średnią z 3 elementów z 6,0,0,9?
Roshan Mehta
1
Kiedy wdrażam to równanie, wartość lub średnia bieżąca zawsze powoli rośnie. Nigdy nie opada - tylko w górę.
anon58192932
30

Z bloga na temat przeprowadzania przykładowych obliczeń wariancji, gdzie średnia jest również obliczana metodą Welforda :

wprowadź opis obrazu tutaj

Szkoda, że ​​nie możemy przesyłać obrazów SVG.

Trzepnięcie
źródło
3
Jest to podobne do tego, co zaimplementował Muis, z wyjątkiem tego, że dzielenie jest używane jako wspólny czynnik. Zatem tylko jeden podział.
Flip
W rzeczywistości jest bliżej @ Abdullah-Al-Ageel (zasadniczo przemienna matematyka), ponieważ Muis nie uwzględnia zwiększania N; Odniesienie do formuły kopiowania i wklejania: [Średnia z n] = [Średnia z n-1] + (x - [Średnia z n-1]) / n
drzaus
2
@Flip & drwaus: Czy rozwiązania Muis i Abdullah Al-Ageel nie są dokładnie takie same? To te same obliczenia, tylko inaczej napisane. Dla mnie te 3 odpowiedzi są identyczne, ta jest bardziej wizualna (szkoda, że ​​nie możemy używać MathJaxa na SO).
user276648
21

Oto kolejna odpowiedź zawierająca komentarz dotyczący tego , jak odpowiedź Muis , Abdullah Al-Ageel i Flipmatematycznie tym samym, z wyjątkiem tego , że są napisane inaczej.

Jasne, mamy analizę José Manuela Ramosa wyjaśniającą, jak błędy zaokrąglania wpływają na każdy z nich nieco inaczej, ale jest to zależne od implementacji i zmieni się w zależności od tego, jak każda odpowiedź została zastosowana do kodu.

Jest jednak dość duża różnica

Jest w Muis 's N, flip ' s k, a Abdullah Al-Ageel „s n. Abdullah Al-Ageel nie do końca wyjaśnić, co npowinno być, ale Ni króżnią się tym, że Njest „ liczba próbek, w których mają być średnio ponad ”, a kjest liczba wartości próbki. (Chociaż mam wątpliwości, czy podanie N liczby próbek jest dokładne.)

I tutaj dochodzimy do odpowiedzi poniżej. Zasadniczo jest to ta sama stara wykładnicza ważona średnia krocząca, co pozostałe, więc jeśli szukałeś alternatywy, zatrzymaj się tutaj.

Wykładnicza ważona średnia ruchoma

Początkowo:

average = 0
counter = 0

Dla każdej wartości:

counter += 1
average = average + (value - average) / min(counter, FACTOR)

Różnica jest min(counter, FACTOR)częścią. To to samo, co mówienie min(Flip's k, Muis's N).

FACTORto stała, która wpływa na to, jak szybko średnia „dogania” najnowszy trend. Im mniejsza liczba, tym szybciej. (W 1tym momencie nie jest już średnią i staje się najnowszą wartością).

Ta odpowiedź wymaga działającego licznika counter. Jeśli jest to problematyczne, min(counter, FACTOR)można je zastąpić just FACTOR, zamieniając je w odpowiedź Muis . Problem z robieniem tego polega na tym, że na średnią ruchomą wpływa to, co averagejest parafowane. Jeśli zostało zainicjowane 0, to zero może zająć dużo czasu, zanim wyjdzie ze średniej.

Jak to się kończy

Wykładnicza średnia krocząca

antak
źródło
3
Dobrze wyjaśnione. Po prostu tęsknię za zwykłą średnią na twoim wykresie, ponieważ o to prosił OP.
xmedeko
Może czegoś mi brakuje, ale czy przez przypadek, miałeś na myśli max(counter, FACTOR). min(counter, FACTOR)zawsze zwróci FACTOR, prawda?
WebWanderer
1
Uważam, że min(counter, FACTOR)chodzi o uwzględnienie okresu rozgrzewki. Bez tego, jeśli twój FACTOR (lub N, lub pożądana liczba próbek) wynosi 1000, będziesz potrzebować co najmniej 1000 próbek, zanim otrzymasz dokładny wynik, ponieważ wszystkie aktualizacje wcześniej zakładają, że masz 1000 próbek, kiedy możesz tylko mają 20.
rharter
Fajnie byłoby przestać liczyć po osiągnięciu współczynnika, pewnie tak byłoby szybciej.
inf3rno
8

Odpowiedź Flip jest obliczeniowo bardziej spójna niż odpowiedź Muis.

Używając formatu podwójnej liczby, możesz zobaczyć problem zaokrągleń w podejściu Muis:

Podejście Muis

Kiedy dzielisz i odejmujesz, zaokrąglenie pojawia się w poprzedniej zapisanej wartości, zmieniając ją.

Jednak podejście odwracania zachowuje przechowywaną wartość i zmniejsza liczbę podziałów, a tym samym zmniejsza zaokrąglenie i minimalizuje błąd propagowany do przechowywanej wartości. Dodanie tylko spowoduje zaokrąglenia, jeśli jest coś do dodania (gdy N jest duże, nie ma nic do dodania)

Podejście Flip

Te zmiany są niezwykłe, gdy uśredniamy duże wartości, które mają tendencję do zerowania.

Wyniki pokazuję za pomocą arkusza kalkulacyjnego:

Po pierwsze, uzyskane wyniki: Wyniki

Kolumny A i B to odpowiednio wartości n i X_n.

Kolumna C to podejście Flip, a kolumna D to podejście Muis, wynik przechowywany w średniej. Kolumna E odpowiada średniej wartości użytej w obliczeniach.

Wykres przedstawiający średnią parzystych wartości jest następny:

Wykres

Jak widać, między oboma podejściami istnieją duże różnice.

José Manuel Ramos
źródło
2
Niezupełnie odpowiedź, ale przydatne informacje. Byłoby jeszcze lepiej, gdybyś dodał trzecią linię do wykresu, dla prawdziwej średniej z n przeszłych wartości, abyśmy mogli zobaczyć, które z dwóch podejść jest najbliższe.
jpaugh
2
@jpaugh: Kolumna B zmienia się między -1,00E + 15 a 1,00E + 15, więc gdy N jest parzyste, rzeczywista średnia powinna wynosić 0. Tytuł wykresu to „Parzyste średnie częściowe”. Oznacza to, że trzecia linia, o którą pytasz, to po prostu f (x) = 0. Wykres pokazuje, że oba podejścia powodują błędy, które stale rosną i rosną.
desowin
Zgadza się, wykres pokazuje dokładnie błąd propagowany przy użyciu dużych liczb biorących udział w obliczeniach przy użyciu obu podejść.
José Manuel Ramos
Legenda twojego wykresu ma niewłaściwe kolory: Muis jest pomarańczowy, Flip jest niebieski.
xmedeko
6

Przykład wykorzystujący javascript dla porównania:

https://jsfiddle.net/drzaus/Lxsa4rpz/

function calcNormalAvg(list) {
    // sum(list) / len(list)
    return list.reduce(function(a, b) { return a + b; }) / list.length;
}
function calcRunningAvg(previousAverage, currentNumber, index) {
    // [ avg' * (n-1) + x ] / n
    return ( previousAverage * (index - 1) + currentNumber ) / index;
}

drzaus
źródło
1

W Javie8:

LongSummaryStatistics movingAverage = new LongSummaryStatistics();
movingAverage.accept(new data);
...
average = movingAverage.getAverage();

masz również IntSummaryStatistics, DoubleSummaryStatistics...

jmhostalet
źródło
2
OP prosi o algorytm, a nie o wskaźnik, jak obliczyć to w Javie.
olq_plo
0

Zgrabne rozwiązanie Pythona oparte na powyższych odpowiedziach:

class RunningAverage():
    def __init__(self):
        self.average = 0
        self.n = 0
        
    def __call__(self, new_value):
        self.n += 1
        self.average = (self.average * (self.n-1) + new_value) / self.n 
        
    def __float__(self):
        return self.average
    
    def __repr__(self):
        return "average: " + str(self.average)

stosowanie:

x = RunningAverage()
x(0)
x(2)
x(4)
print(x)
Dima Lituiev
źródło