Effiziente Berechnung einer sich bewegenden Standardabweichung

Question

Unten sehen Sie meine C# -Methode zur Berechnung von Bollinger-Bändern für jeden Punkt (gleitender Durchschnitt, Aufwärtsband, Abwärtsband).

Wie Sie sehen können, verwendet diese Methode 2 for-Schleifen, um die sich bewegende Standardabweichung mithilfe des gleitenden Durchschnitts zu berechnen. Früher enthielt es eine zusätzliche Schleife, um den gleitenden Durchschnitt über die letzten n Perioden zu berechnen. Diesen könnte ich entfernen, indem ich den neuen Punktwert zu total_average am Anfang der Schleife hinzufüge und den i-n-Punktwert am Ende der Schleife entferne.

Meine Frage ist jetzt im Grunde: Kann ich die verbleibende innere Schleife in ähnlicher Weise entfernen, die ich mit dem gleitenden Durchschnitt geschafft habe?

public static void AddBollingerBands(SortedList<DateTime, Dictionary<string, double>> data, int period, int factor) 
    { 
     double total_average = 0; 

     for (int i = 0; i < data.Count(); i++) 
     { 
      total_average += data.Values[i]["close"]; 

      if (i >= period - 1) 
      { 
       double total_bollinger = 0; 
       double average = total_average/period; 

       for (int x = i; x > (i - period); x--) 
       { 
        total_bollinger += Math.Pow(data.Values[x]["close"] - average, 2); 
       } 

       double stdev = Math.Sqrt(total_bollinger/period); 

       data.Values[i]["bollinger_average"] = average; 
       data.Values[i]["bollinger_top"] = average + factor * stdev; 
       data.Values[i]["bollinger_bottom"] = average - factor * stdev; 

       total_average -= data.Values[i - period + 1]["close"]; 
      } 
     } 
    } 

Answer 1

Die Antwort ist ja, Sie können. Mitte der 80er Jahre habe ich in FORTRAN einen solchen (wahrscheinlich nicht originalen) Algorithmus für eine Prozessüberwachung und -steuerung entwickelt. Leider war das vor über 25 Jahren und ich kann mich nicht an die genauen Formeln erinnern, aber die Technik war eine Erweiterung der Methode für gleitende Mittelwerte, mit Berechnungen zweiter Ordnung anstatt nur linearer.

Nach dem Blick auf Ihren Code einige, denke ich, dass ich ausspreche, wie ich es damals getan habe. Beachten Sie, wie Ihre innere Schleife macht eine Summe von Quadraten ?:

  for (int x = i; x > (i - period); x--) 
      { 
       total_bollinger += Math.Pow(data.Values[x]["close"] - average, 2); 
      } 

in der gleichen Art und Weise, dass Ihr Durchschnitt haben muss ursprünglich hatte eine Summe von Werten? Die einzigen zwei Unterschiede sind die Reihenfolge (ihre Potenz 2 statt 1) ​​und dass Sie den Durchschnittswert jedes Werts subtrahieren, bevor Sie ihn quadrieren. Nun könnte das aussehen untrennbar miteinander verbunden, aber in der Tat können sie getrennt werden:

SUM(i=1; n){ (v[i] - k)^2 } 

ist

SUM(i=1..n){v[i]^2 -2*v[i]*k + k^2} 

die

SUM(i=1..n){v[i]^2 -2*v[i]*k} + k^2*n 

wird die

SUM(i=1..n){v[i]^2} + SUM(i=1..n){-2*v[i]*k} + k^2*n 

ist der auch ist,

Jetzt ist der erste Begriff nur eine Summe von Quadraten, Sie behandeln das auf die gleiche Weise, wie Sie die Summe der Werte für den Durchschnitt machen. Der letzte Term (k^2*n) ist nur das durchschnittliche Quadrat mal die period. Da Sie das Ergebnis trotzdem nach dem Zeitraum dividieren, können Sie einfach das neue durchschnittliche Quadrat ohne die zusätzliche Schleife hinzufügen.

schließlich im zweiten Term (SUM(-2*v[i]) * k), da SUM(v[i]) = total = k*n können Sie dann in das ändern:

-2 * k * k * n 

oder nur -2*k^2*n, das ist -2-fache des durchschnittlichen quadriert, sobald die Periode (n) ist wieder geteilt.So dass die endgültige kombinierte Formel:

SUM(i=1..n){v[i]^2} - n*k^2 

oder

SUM(i=1..n){values[i]^2} - period*(average^2) 

(sicher sein, die Gültigkeit dieses zu überprüfen, da ich es bin Ableitung der Spitze von meinem Kopf)

und die Einbeziehung in Ihrem Code sollte in etwa so aussehen:

public static void AddBollingerBands(ref SortedList<DateTime, Dictionary<string, double>> data, int period, int factor) 
{ 
    double total_average = 0; 
    double total_squares = 0; 

    for (int i = 0; i < data.Count(); i++) 
    { 
     total_average += data.Values[i]["close"]; 
     total_squares += Math.Pow(data.Values[i]["close"], 2); 

     if (i >= period - 1) 
     { 
      double total_bollinger = 0; 
      double average = total_average/period; 

      double stdev = Math.Sqrt((total_squares - Math.Pow(total_average,2)/period)/period); 
      data.Values[i]["bollinger_average"] = average; 
      data.Values[i]["bollinger_top"] = average + factor * stdev; 
      data.Values[i]["bollinger_bottom"] = average - factor * stdev; 

      total_average -= data.Values[i - period + 1]["close"]; 
      total_squares -= Math.Pow(data.Values[i - period + 1]["close"], 2); 
     } 
    } 
} 

Answer 2

Ich habe commons-math verwendet (und zu dieser Bibliothek beigetragen!) Für etwas sehr ähnliches. Es ist open-source, Portierung nach C# sollte einfach sein wie ein gekaufter Kuchen (hast du versucht, einen Kuchen von Grund auf neu zu machen !?). Schau es Dir an: http://commons.apache.org/math/api-3.1.1/index.html. Sie haben eine Klasse StandardDeviation. In die Stadt gehen!

Answer 3

Das Problem mit Ansätzen, die die Summe der Squ berechnen Ares ist, dass es und das Quadrat der Summen kann ziemlich groß werden, und die Berechnung ihrer Differenz kann eine very large error vorstellen, also lasst uns etwas besser denken. Warum dies erforderlich ist, finden Sie im Wikipedia-Artikel unter Algorithms for computing variance und John Cook unter Theoretical explanation for numerical results)

Zuerst, anstatt die Stddev berechnen wir konzentrieren uns auf die Varianz. Sobald wir die Varianz haben, ist stddev nur die Quadratwurzel der Varianz.

Angenommen, die Daten befinden sich in einem Array namens x; Wenn Sie ein n-großes Fenster um eins rollen, können Sie den Wert x[0] entfernen und den Wert x[n] hinzufügen. Wir bezeichnen die Mittelwerte von x[0]..x[n-1] und x[1]..x[n] durch μ bzw. μ '. Die Differenz zwischen den Abweichungen von x[0]..x[n-1] und x[1]..x[n] wird, nachdem er einige Bedingungen aufhebt und die Anwendung (a²-b²) = (a+b)(a-b):

Var[x[1],..,x[n]] - Var[x[0],..,x[n-1]] 
= (\sum_1^n x[i]² - n µ’²)/(n-1) - (\sum_0^{n-1} x[i]² - n µ²)/(n-1) 
= (x[n]² - x[0]² - n(µ’² - µ²))/(n-1) 
= (x[n]-µ’ + x[0]-µ)(x[n]-x[0])/(n-1) 

Deshalb ist die Varianz durch etwas gestört ist, die erfordert Sie nicht die Summe der Quadrate zu halten, was besser ist, für numerische Genauigkeit.

Sie können den Mittelwert und die Abweichung einmal am Anfang mit einem geeigneten Algorithmus berechnen (Welford's method). Danach müssen jedes Mal, wenn Sie einen Wert in das Fenster ersetzen x[0] durch ein anderes x[n] Sie den Durchschnitt und die Varianz wie folgt aktualisiert:

new_Avg = Avg + (x[n]-x[0])/n 
new_Var = Var + (x[n]-new_Avg + x[0]-Avg)(x[n] - x[0])/(n-1) 
new_StdDev = sqrt(new_Var) 

Answer 4

Am wichtigsten Informationen wurden oben bereits angegeben --- aber vielleicht ist dies nach wie vor von allgemeinem Interesse.

Eine kleine Java-Bibliothek berechnen Mittelwert und Standardabweichung bewegt, ist hier verfügbar: https://github.com/tools4j/meanvar

Die Implementierung kann auf einer Variante von Welford der oben genannten Verfahren basiert. Es wurden Methoden zum Entfernen und Ersetzen von Werten abgeleitet, die zum Verschieben von Wertfenstern verwendet werden können.