[PYTHON] Sequentielle Berechnung des Durchschnittswertes mit Online-Algorithmus

Ein Online-Algorithmus ist ein Algorithmus, der auch dann berechnet werden kann, wenn Daten nacheinander eingehen. Dies wird im Gegensatz zum Batch-Algorithmus (Offline-Algorithmus) aufgerufen, der berechnet, nachdem alle Daten angezeigt wurden.

Online-Algorithmen werden häufig verwendet, wenn große Datenmengen verarbeitet werden, bei denen es schwierig ist, alle Daten im Speicher zu halten. Sie können es oft im Zusammenhang mit maschinellem Lernen sehen. Im Zusammenhang mit maschinellem Lernen gibt es viele Dinge, die theoretisch schwierig sind. Da jedoch beim Erstellen eines einfachen Systems Mittelung, Streuung, Abtastung usw. relativ häufig verwendet werden, kann die Verarbeitung auch dann geschrieben werden, wenn Daten nacheinander eingehen. Sie können glücklich sein, wenn Sie werden.

Dieses Mal werde ich nur die Methode zur sequentiellen Berechnung des Durchschnittswerts schreiben.

Sequentielle Berechnung des Durchschnittswertes

Der Durchschnittswert, für den Sie "Durchschnitt", "Gesamt" finden möchten, ist die Anzahl der bisher verarbeiteten Daten. Ziel ist es, in der folgenden Form beschreiben zu können.

ruby/python


average += x
total += y

Um als Online-Algorithmus gültig zu sein, kann natürlich die Form "Durchschnitt * = z" angestrebt werden, aber im Fall des (additiven) Durchschnittswerts kann die Lösung erhalten werden, wenn die obige Form verwendet wird.

Erstens ist "y = 1", weil "total" die Häufigkeit darstellt.

Da "Durchschnitt" nicht offensichtlich ist, wird er durch Erweitern der Formel wie folgt berechnet. Wert ist hier ein Wert von Daten, für die ein neuer Durchschnitt erhalten werden soll.

math


average[new] = (average[old] * total[old] + value) / (total[old] + 1)
average[new] = average[old] + x

Als

average[old] + x = (average[old] * total[old] + value) / (total[old] + 1)

Wenn Sie das lösen

average[old] + average[old] * total[old] + x * (total[old]+1) = average[old] * total[old] + value
average[old] + x * (total[old]+1) = value

als Ergebnis

x = (value - average[old]) / (total[old] + 1)

Erhalten

Als Ergebnis des Schreibens in das Programm

ruby/python


average += (value - average) / (total + 1)
total += 1

Wird sein. Hier,

math


total[new] = total[old] + 1

In Anbetracht dessen programmatisch

ruby/python


total += 1
average += (value - average) / total

Kann cooler sein.

Überprüft mit einem konkreten Beispiel

Es gibt 3 Daten und der Wert ist

20 -> 30 -> 40 

Angenommen, es war.

Zu diesem Zeitpunkt ist der endgültige Durchschnitt

30

Und der Durchschnitt zu dieser Zeit ist

20 -> 25 -> 30

Es reicht aus, wenn es sich ändert.

Ich werde es tatsächlich versuchen.

1. Mal

math


x = (20 - ?) / 1 = 20 - ?
average = ? + 20 - ? = 20

Zweites Mal

math


x = (30 - 20) / 2 = 5
average = 20 + 5 = 25

3. Mal

math


x = (40 - 25) / 3 = 5
average = 25 + 5 = 30

Und Sie können sehen, dass es funktioniert.

Das erste "?" Ist übrigens der Anfangswert des Durchschnitts, und es kann ein beliebiger Wert eingegeben werden. Tatsächlich ist es "0", oder wenn der Durchschnittswert im Voraus geschätzt werden kann, ist es besser, den geschätzten Wert einzugeben.

Bonus

Tipps, um die Verteilung zu einem Online-Algorithmus zu machen

math


V(X) = E(X*X) - E(X)*E(X)

verwenden. Hier repräsentiert "V" die Verteilung und "E" den Durchschnitt. Mit anderen Worten kann es berechnet werden, indem der Durchschnittswert der quadratischen Werte der Daten gehalten wird.

Tipps, wie Sie Sampling zu einem Online-Algorithmus machen können

Zum Beispiel, wenn Sie nur einen Wert aus einer großen Datenmenge abtasten möchten Lassen Sie diese Daten "abgetastet" werden, und lassen Sie die Anzahl der bisher gesehenen Daten "total" sein.

In diesem Moment,

Dann kann das abgetastete Ergebnis mit gleicher Wahrscheinlichkeit erhalten werden.

Wenn Sie dies anwenden, können Sie natürlich nur drei probieren.

Recommended Posts

Sequentielle Berechnung des Durchschnittswertes mit Online-Algorithmus
Echtzeitberechnung des Durchschnittswertes mit Corroutine
Berechnung der gegenseitigen Informationsmenge (kontinuierlicher Wert) mit numpy
Fehlerfreie Berechnung mit Golangs big.Float
Implementierung der Dyxtra-Methode durch Python
[Algorithmus x Python] Berechnung der Basisstatistik Teil2 (Mittelwert, Median, am häufigsten)
[Algorithmus x Python] Berechnung der Basisstatistik (Gesamtwert, Maximalwert, Minimalwert)
Berechnung der mittleren IoU bei der Objekterkennung
Die Geschichte der numerischen Berechnung von Differentialgleichungen mit TensorFlow 2.0
1. Mit Python 1-3 gelernte Statistiken. Berechnung verschiedener Statistiken (Statistiken)
1. Mit Python 1-2 gelernte Statistiken. Berechnung verschiedener Statistiken (Numpy)
Visualisieren Sie das Verhalten des Sortieralgorithmus mit matplotlib
[Grundlagen der modernen mathematischen Statistik mit Python] Kapitel 2: Wahrscheinlichkeitsverteilung und Erwartungswert
Sequentielle Berechnung des Durchschnittswertes mit Online-Algorithmus
Berechnung der gegenseitigen Informationsmenge (kontinuierlicher Wert) mit numpy
Führt eine Hochgeschwindigkeitsberechnung nur für bestimmte Deskriptoren mit mordred durch
Höchstwahrscheinlich Schätzung des Mittelwerts und der Varianz mit TensorFlow
Nehmen Sie den Wert des SwitchBot-Thermo-Hygrometers mit Raspberry Pi
Umschalten der Bot-Thermo-Hygrometer-Werte mit Raspberry Pi