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.
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.
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.
math
x = (20 - ?) / 1 = 20 - ?
average = ? + 20 - ? = 20
math
x = (30 - 20) / 2 = 5
average = 20 + 5 = 25
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.
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.
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