Wie berechnet man den gleitenden Durchschnitt, ohne die Anzahl und die Datensumme beizubehalten?

118

Ich versuche einen Weg zu finden, um einen gleitenden kumulativen Durchschnitt zu berechnen, ohne die Anzahl und die Gesamtdaten zu speichern, die bisher empfangen wurden.

Ich habe zwei Algorithmen entwickelt, aber beide müssen die Anzahl speichern:

  • neuer Durchschnitt = ((alte Zählung * alte Daten) + nächste Daten) / nächste Zählung
  • neuer Durchschnitt = alter Durchschnitt + (nächste Daten - alter Durchschnitt) / nächste Zählung

Das Problem bei diesen Methoden ist, dass die Anzahl immer größer wird, was zu einem Genauigkeitsverlust im resultierenden Durchschnitt führt.

Die erste Methode verwendet die alte und die nächste Zählung, die offensichtlich 1 voneinander entfernt sind. Dies brachte mich zu dem Gedanken, dass es vielleicht eine Möglichkeit gibt, die Zählung zu entfernen, aber leider habe ich sie noch nicht gefunden. Es hat mich zwar ein bisschen weiter gebracht, was zur zweiten Methode führte, aber die Anzahl ist immer noch vorhanden.

Ist es möglich oder suche ich nur das Unmögliche?

user1705674
quelle
1
Beachten Sie, dass das Speichern der aktuellen Gesamtsumme und der aktuellen Anzahl numerisch der stabilste Weg ist. Andernfalls beginnt bei höheren Zählungen next / (next count) zu unterlaufen. Also , wenn Sie wirklich besorgt sind , um Präzision zu verlieren, halten Sie die Summen!
AlexR
1
Siehe Wikipedia en.wikipedia.org/wiki/Moving_average
xmedeko

Antworten:

91

Sie können einfach tun:

double approxRollingAverage (double avg, double new_sample) {

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

    return avg;
}

Wo Nist die Anzahl der Stichproben, über die Sie einen Durchschnitt bilden möchten? Beachten Sie, dass diese Annäherung einem exponentiellen gleitenden Durchschnitt entspricht. Siehe: Berechnen Sie den gleitenden / gleitenden Durchschnitt in C ++

Muis
quelle
3
Müssen Sie vor dieser Zeile nicht 1 zu N hinzufügen? avg + = new_sample / N;
Damian
20
Das ist nicht ganz richtig. Was @Muis beschreibt, ist ein exponentiell gewichteter gleitender Durchschnitt, der manchmal angemessen ist, aber nicht genau das ist, was das OP angefordert hat. Betrachten Sie als Beispiel das Verhalten, das Sie erwarten, wenn die meisten Punkte im Bereich von 2 bis 4 liegen, ein Wert jedoch über einer Million liegt. Eine EWMA (hier) wird noch einige Zeit an Spuren dieser Million festhalten. Eine endliche Faltung, wie durch OP angezeigt, würde sie unmittelbar nach N Schritten verlieren. Es hat den Vorteil einer konstanten Lagerung.
JMA
9
Das ist kein gleitender Durchschnitt. Was Sie beschreiben, ist ein einpoliger Filter, der exponentielle Reaktionen auf Signalsprünge erzeugt. Ein gleitender Durchschnitt erzeugt eine lineare Antwort mit der Länge N.
Ruhiger Brauner
3
Beachten Sie, dass dies ziemlich weit von der üblichen Definition des Durchschnitts entfernt ist. Wenn Sie N = 5 setzen und 5 5Proben eingeben , beträgt der Durchschnitt 0,67.
Dan Dascalescu
2
@DanDascalescu Obwohl Sie richtig sind, dass es sich nicht um einen gleitenden Durchschnitt handelt, ist Ihr angegebener Wert um eine Größenordnung niedriger. Mit avginitialisiert auf erhalten 0Sie 3.36nach 5 5s und 4.46nach 10: cpp.sh/2ryql. Für lange Durchschnittswerte ist dies sicherlich eine nützliche Annäherung.
cincodenada
80
New average = old average * (n-1)/n + new value /n

Dies setzt voraus, dass sich die Anzahl nur um einen Wert ändert. Falls es um M Werte geändert wird, dann:

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

Dies ist die mathematische Formel (ich glaube die effizienteste). Glauben Sie, dass Sie selbst weiteren Code erstellen können

Abdullah Al-Ageel
quelle
Was ist die Summe der neuen Werte? unterscheidet sich das irgendwie von "neuem Wert" in Ihrer ursprünglichen Formel?
Mikhail
@Mikhail Im zweiten Beispiel werden mneue Werte in den neuen Durchschnitt einbezogen . Ich glaube, dass sum of new valuehier die Summe der mneuen Werte gemeint ist , die zur Berechnung des neuen Durchschnitts verwendet werden.
Patrick Goley
9
Etwas effizienter für den ersten: new_average = (old_average * (n-1) + new_value) / n- Entfernt eine der Teilungen.
Pixelstix
Wie wäre es mit einem laufenden Durchschnitt von 3 Elementen mit 6,0,0,9?
Roshan Mehta
1
Wenn ich diese Gleichung implementiere, steigt der Wert oder der laufende Durchschnitt immer langsam an. Es geht nie runter - nur rauf.
anon58192932
30

Aus einem Blog über das Ausführen von Stichprobenvarianzberechnungen, in dem der Mittelwert auch nach der Welford-Methode berechnet wird :

Geben Sie hier die Bildbeschreibung ein

Schade, dass wir keine SVG-Bilder hochladen können.

Flip
quelle
3
Dies ähnelt dem, was Muis implementiert hat, außer dass die Teilung ein gemeinsamer Faktor ist. Also nur eine Abteilung.
Flip
Es ist tatsächlich näher an @ Abdullah-Al-Ageel (im Wesentlichen kommutative Mathematik), da Muis das Inkrementieren von N nicht berücksichtigt; Referenz der Copy-Paste-Formel: [Durchschn. Bei n] = [Durchschn. Bei n-1] + (x - [Durchschn. Bei n-1]) / n
drzaus
2
@Flip & drwaus: Sind die Lösungen von Muis und Abdullah Al-Ageel nicht genau gleich? Es ist die gleiche Berechnung, nur anders geschrieben. Für mich sind diese 3 Antworten identisch, diese ist visueller (schade, dass wir MathJax nicht für SO verwenden können).
user276648
21

Hier ist noch eine weitere Antwort Angebot Kommentierung wie Muis , Abdullah Al-Ageel und Flip ‚s Antwort sind alle mathematisch die gleiche Sache außer dass sie unterschiedlich geschrieben sind.

Sicher, wir haben José Manuel Ramos 'Analyse, die erklärt, wie sich Rundungsfehler geringfügig voneinander auswirken, aber das hängt von der Implementierung ab und würde sich ändern, je nachdem, wie jede Antwort auf Code angewendet wurde.

Es gibt jedoch einen ziemlich großen Unterschied

Es ist in Muis 's N, Flip ' s k, und Abdullah Al-Ageel ‚s n. Abdullah Al-Ageel nicht ganz erklären , was nsein sollte, aber Nund kunterscheiden sich dadurch , dass Nist „ die Anzahl der Proben , bei denen Sie Durchschnitt wollen über “ , während kdie Anzahl der abgetasteten Werte. (Obwohl ich Zweifel habe, ob das Aufrufen N der Anzahl der Proben korrekt ist.)

Und hier kommen wir zur Antwort unten. Es ist im Wesentlichen der gleiche alte exponentiell gewichtete gleitende Durchschnitt wie die anderen. Wenn Sie also nach einer Alternative suchen, hören Sie hier auf.

Exponentiell gewichteter gleitender Durchschnitt

Anfänglich:

average = 0
counter = 0

Für jeden Wert:

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

Der Unterschied ist der min(counter, FACTOR)Teil. Dies ist das gleiche wie zu sagenmin(Flip's k, Muis's N) .

FACTORist eine Konstante, die beeinflusst, wie schnell der Durchschnitt den neuesten Trend "einholt". Je kleiner die Zahl, desto schneller. ( 1Es ist kein Durchschnitt mehr und wird nur zum neuesten Wert.)

Diese Antwort erfordert den laufenden Zähler counter. Wenn es problematisch ist, min(counter, FACTOR)kann das durch just ersetzt werden FACTOR, was es zu Muis 'Antwort macht. Das Problem dabei ist, dass der gleitende Durchschnitt von allem beeinflusst wird, was averageinitiiert wurde. Wenn es auf initialisiert 0wurde, kann es lange dauern, bis sich diese Null aus dem Durchschnitt herausarbeitet.

Wie es am Ende aussieht

Exponentieller gleitender Durchschnitt

Antak
quelle
3
Gut erklärt. Ich vermisse nur einen einfachen Durchschnitt in Ihrer Grafik, weil das, was OP gefragt hat.
Xmedeko
Vielleicht bin ich etwas fehlt, aber wussten Sie, durch Zufall, Mittelwert max(counter, FACTOR). min(counter, FACTOR)wird immer FACTOR zurückgeben, oder?
WebWanderer
1
Ich glaube, es min(counter, FACTOR)geht darum, die Aufwärmphase zu berücksichtigen. Wenn Ihr FAKTOR (oder N oder die gewünschte Probenanzahl) 1000 beträgt, benötigen Sie mindestens 1000 Proben, bevor Sie ein genaues Ergebnis erhalten, da bei allen vorherigen Aktualisierungen davon ausgegangen wird, dass Sie 1000 Proben haben, wenn Sie nur dürfen habe 20.
Rharter
Es wäre schön, nach Erreichen des Faktors mit dem Zählen aufzuhören, wahrscheinlich wäre es so schneller.
inf3rno
8

Die Antwort von Flip ist rechnerisch konsistenter als die von Muis.

Bei Verwendung des Doppelnummernformats konnten Sie das Rundungsproblem im Muis-Ansatz erkennen:

Der Muis-Ansatz

Wenn Sie dividieren und subtrahieren, wird im vorherigen gespeicherten Wert eine Rundung angezeigt, die sich ändert.

Der Flip-Ansatz behält jedoch den gespeicherten Wert bei und verringert die Anzahl der Teilungen, wodurch die Rundung verringert und der auf den gespeicherten Wert übertragene Fehler minimiert wird. Wenn Sie nur hinzufügen, werden Rundungen angezeigt, wenn etwas hinzugefügt werden muss (wenn N groß ist, gibt es nichts hinzuzufügen).

Der Flip-Ansatz

Diese Änderungen sind bemerkenswert, wenn Sie einen Mittelwert aus großen Werten erstellen, deren Mittelwert gegen Null tendiert.

Ich zeige Ihnen die Ergebnisse mit einem Tabellenkalkulationsprogramm:

Erstens wurden die Ergebnisse erhalten: Ergebnisse

Die Spalten A und B sind die Werte n und X_n.

Die C-Spalte ist der Flip-Ansatz und die D-Spalte ist der Muis-Ansatz, das Ergebnis wird im Mittelwert gespeichert. Die Spalte E entspricht dem bei der Berechnung verwendeten Mittelwert.

Ein Diagramm, das den Mittelwert der geraden Werte zeigt, ist das nächste:

Graph

Wie Sie sehen können, gibt es große Unterschiede zwischen beiden Ansätzen.

José Manuel Ramos
quelle
2
Nicht wirklich eine Antwort, aber nützliche Informationen. Es wäre sogar noch besser, wenn Sie Ihrem Diagramm die dritte Zeile für den wahren Durchschnitt über n vergangene Werte hinzufügen würden , damit wir sehen könnten, welcher der beiden Ansätze am nächsten kommt.
Jpaugh
2
@jpaugh: Die Spalte B wechselt zwischen -1,00 E + 15 und 1,00 E + 15, wenn also N gerade ist, sollte der tatsächliche Mittelwert 0 sein. Der Titel des Diagramms lautet "Gerade Teilmittel". Dies bedeutet, dass die dritte Zeile, nach der Sie fragen, einfach f (x) = 0 ist. Die Grafik zeigt, dass beide Ansätze Fehler verursachen, die immer weiter steigen.
Desowin
Das ist richtig, die Grafik zeigt genau den Fehler, der unter Verwendung großer Zahlen, die an den Berechnungen beteiligt sind, unter Verwendung beider Ansätze propagiert wird.
José Manuel Ramos
Die Legende Ihres Diagramms hat falsche Farben: Muis ist orange, Flip ist blau.
Xmedeko
6

Ein Beispiel mit Javascript zum Vergleich:

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
quelle
1

In Java8:

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

Sie haben auch IntSummaryStatistics, DoubleSummaryStatistics...

jmhostalet
quelle
2
OP fragt nach einem Algorithmus, nicht nach einem Zeiger, wie dies in Java berechnet werden kann.
olq_plo
0

Eine nette Python-Lösung basierend auf den obigen Antworten:

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)

Verwendung:

x = RunningAverage()
x(0)
x(2)
x(4)
print(x)
Dima Lituiev
quelle