In diesem Artikel wird der Algorithmus von Donald Knuth vorgestellt, der ein hervorragender Algorithmus zur Berechnung der Dispersion ist. Normalerweise verlasse ich mich bei der Berechnung der Verteilung auf die Bibliothek, und ich habe den Algorithmus nicht besonders berücksichtigt. Ich hoffe, dass ich diese Gelegenheit nutzen kann, um mein Wissen zu vertiefen.
Zunächst erkläre ich, warum Sie einen solchen Algorithmus benötigen. Die unverzerrte Verteilung wird durch die folgende Formel ausgedrückt.
\sigma^2 = \frac{1}{n(n-1)} \biggl(\sum_{i=1}^{n}x_i^2-\Bigl(\sum_{i=1}^{n}x_i\Bigr)^2\biggr) =\frac{1}{n-1}\Bigl(E[X^2]-E[X]^2\Bigr)
Hier sind zwei kumulative Summen. 1. Kumulative Summe von $ x $ selbst und 2. $ x ^ 2 $. Derzeit gibt es zwei Hauptprobleme. Erstens ist die Genauigkeit numerischer Berechnungen nicht garantiert, wenn $ x $ eine sehr große Zahl ist. Zweitens müssen wir wieder große Berechnungen durchführen, wenn wir mehr Proben haben. Um diese Herausforderungen zu lösen, schauen wir uns im nächsten Abschnitt den Algorithmus von Donald Knuth an.
Um die oben genannten Probleme zu lösen, wurde dieser Algorithmus entwickelt, um die Varianz sequentiell zu berechnen. Der Algorithmus ist unten gezeigt. $ M_k $ repräsentiert den Durchschnitt und $ s_k $ ist der Zähler der Dispersion.
Initialisierung: $ M_1 = x_1, S_1 = 0 $ Berechnen Sie die folgende allmähliche Gleichung in $ k \ geq 2 $
\begin{align}
M_k &= M_{k-1} + \frac{(x_k - M_{k-1})}{k}\\
S_k &= S_{k-1} + (x_k - M_{k-1})*(x_k - M_k)
\end{align}
Die zu berechnende geschätzte unverzerrte Varianz beträgt $ s ^ 2 = S_k / (k-1) $ bei $ k \ geq 2 $.
def calc_var(x, k=0, M=0, s=0):
print('k=', k)
print('M=', M)
print('s=', s)
print('-----------------------')
if k == 0:
M = x[0]
s = 0
delta = x[k] - M
M += delta/(k+1)
s += delta*(x[k]-M)
k += 1
if k == len(x):
return M, s/(k-1)
else:
return calc_var(x, k=k, M=M, s=s)
x = [3.3, 5, 7.2, 12, 4, 6, 10.3]
print(calc_var(x))
k= 0
M= 0
s= 0
-----------------------
k= 1
M= 3.3
s= 0.0
-----------------------
k= 2
M= 4.15
s= 1.4449999999999996
-----------------------
k= 3
M= 5.166666666666667
s= 7.646666666666666
-----------------------
k= 4
M= 6.875
s= 42.6675
-----------------------
k= 5
M= 6.3
s= 49.279999999999994
-----------------------
k= 6
M= 6.25
s= 49.355
-----------------------
(6.828571428571428, 10.56904761904762)
Selbst mit Numpy werde ich den Mittelwert und die Varianz berechnen und vergleichen. Das Schlüsselwortargument ddof = 1 dient zur Berechnung als unverzerrte Verteilung.
import numpy as np
x_arr = np.array(x)
print((x_arr.mean(), x_arr.var(ddof=1)))
Ausgabeergebnis
(6.828571428571428, 10.569047619047621)
Ich konnte so sequentiell rechnen. Eigentlich glaube ich nicht, dass Python-Rekursiv schneller als Numpy ist, also glaube ich nicht, dass ich die Möglichkeit habe, es selbst zu implementieren, aber obwohl es als verteilter Berechnungsalgorithmus ausgezeichnet ist, ist es nicht bekannt, also lassen Sie es mich schreiben Ich habe es erhalten. Ich hoffe, es wird für alle hilfreich sein.
Accurately computing running variance https://www.johndcook.com/blog/standard_deviation/
Recommended Posts