14965
既にある平均値を更新し続けるアルゴリズムを教えてください。  
平均値や分散を逐次求めるアルゴリズムを教えてください。
CC BY-SA 3.0
2015-08-28T12:51:41.873
14964
2015-08-29T10:51:26.547
11041
question
アルゴリズム
既にある平均値を更新し続けるアルゴリズムを教えてください。
こういったアルゴリズムは数学的帰納法を利用して数式を求めます。  
一般に平均の式は以下の式で表されます。  
[![（１）](https://i.stack.imgur.com/tU0oG.gif)](https://i.stack.imgur.com/tU0oG.gif)（１）

この式のN+1の時は以下で表されます。  
[![画像の説明をここに入力](https://i.stack.imgur.com/Tf7Ti.gif)](https://i.stack.imgur.com/Tf7Ti.gif)

上の式の中で（１）が登場すれば良いので

[![画像の説明をここに入力](https://i.stack.imgur.com/tGmxC.gif)](https://i.stack.imgur.com/tGmxC.gif)  
のようにします。最後に式をまとめると

[![画像の説明をここに入力](https://i.stack.imgur.com/luMRH.gif)](https://i.stack.imgur.com/luMRH.gif)

mean=(COUNT*mean+x)/(COUNT+1)  
これで完成です。
CC BY-SA 3.0
2015-08-28T12:51:41.873
14965
2015-08-28T12:51:41.873
11041
14964
answer
![](https://latex.codecogs.com/gif.latex?S_n&space;=&space;%5Csum_%7Bi=1%7D%5E%7Bn%7D&space;x_i)

と置いたとき,
![](https://latex.codecogs.com/gif.latex?%5Cinline&space;%5C%7Bx_i%5C&space;|%5C&space;i&space;=&space;1,%5Cdots,n%5C%7D)
の平均 ![](https://latex.codecogs.com/gif.latex?%5Cinline&space;a_n) は

![](https://latex.codecogs.com/gif.latex?a_n&space;=&space;%5Cfrac%7BS_n%7D%7Bn%7D)

と書けます. ![](https://latex.codecogs.com/gif.latex?%5Cinline&space;S_n)
を漸化式の形で書くと

![](https://latex.codecogs.com/gif.latex?S_%7Bn+1%7D&space;=&space;S_n&space;+&space;x_%7Bn+1%7D%5C&space;\(n&space;%5Cgeq&space;1\))

となり, これより ![](https://latex.codecogs.com/gif.latex?%5Cinline&space;a_n) を
![](https://latex.codecogs.com/gif.latex?%5Cinline&space;S_n) と
![](https://latex.codecogs.com/gif.latex?%5Cinline&space;x_n) を用いて

![](https://latex.codecogs.com/gif.latex?a_%7Bn+1%7D&space;=&space;%5Cfrac%7BS_n&space;+&space;x_%7Bn+1%7D%7D%7Bn+1%7D)

と書けます.

この方式では ![](https://latex.codecogs.com/gif.latex?%5Cinline&space;n) と
![](https://latex.codecogs.com/gif.latex?%5Cinline&space;S_n) だけ保持しておけばよく,
![](https://latex.codecogs.com/gif.latex?%5Cinline&space;a_n&space;*&space;n)
を計算して ![](https://latex.codecogs.com/gif.latex?%5Cinline&space;S_n)
を復元する処理が不要になります.

分散は

![](https://latex.codecogs.com/gif.latex?V_n&space;=&space;%5Cfrac%7B1%7D%7Bn%7D&space;%5Csum_%7Bi=1%7D%5E%7Bn%7D&space;\(x_i&space;-&space;a_n\)%5E2)

と定義されますが, これを式変形して

![](https://latex.codecogs.com/gif.latex?V_n&space;=&space;%5Cfrac%7B1%7D%7Bn%7D&space;%5Csum_%7Bi=1%7D%5E%7Bn%7D&space;x_i%5E2&space;-&space;a_n%5E2)

と書けます. 先程と同様

![](https://latex.codecogs.com/gif.latex?Q_n&space;=&space;%5Csum_%7Bi=1%7D%5E%7Bn%7D&space;x_i%5E2)

の漸化式

![](https://latex.codecogs.com/gif.latex?Q_%7Bn+1%7D&space;=&space;Q_n&space;+&space;x_%7Bn+1%7D%5E2)

を考え, ![](https://latex.codecogs.com/gif.latex?%5Cinline&space;V_n)
を逐次計算しやすい形で書くと

![](https://latex.codecogs.com/gif.latex?V_%7Bn+1%7D&space;=&space;%5Cfrac%7BQ_n&space;+&space;x_%7Bn+1%7D%5E2%7D%7Bn+1%7D&space;-&space;%5Cleft\(%5Cfrac%7BS_n&space;+&space;x_%7Bn+1%7D%7D%7Bn+1%7D%5Cright\)%5E2)

となります. 分散の場合は
![](https://latex.codecogs.com/gif.latex?%5Cinline&space;n,&space;S_n,&space;Q_n)
を保持しておけばよくなります.

注. ![](https://latex.codecogs.com/gif.latex?%5Cinline&space;x_n)
の性質によっては計算で発生する誤差を考える必要がありますが, ここでは一般的な話として特に考慮は入れてありません.
CC BY-SA 3.0
2015-08-28T19:52:58.727
14981
2015-08-29T10:51:26.547
2017-03-10T09:42:49.017
-1
2281
14964
answer