平均と分散を逐次的に計算するアルゴリズム

問題設定

状況
データが一つずつ、順番に流れてくる状況を考えます。流れてくるデータを、
$x_1,x_2,x_3,\cdots$
とします。

目標
今までに流れてきたデータの平均と分散を、順次求めるのが目標です。計算方法を工夫すれば、短い計算時間、少ないメモリ使用量で、平均と分散を順次計算できます。

記号
$n$ 番目までのデータの
平均を $\mu_n=\dfrac{x_1+x_2+\cdots +x_n}{n}$
分散を $\sigma_n^2=\dfrac{1}{n}\displaystyle\sum_{i=1}^n(x_i-\mu_n)^2$
とします。

平均の逐次計算

平均の更新式：
$\mu_{n+1}=\dfrac{1}{n+1}(n\mu_n+x_{n+1})$
を使います。

具体的なアルゴリズムとしては、
１．$\mu_n$ と $n$ を保持しておく。
２．データ $x_{n+1}$ が入ってきたら。
３．平均の更新式を使って $\mu_{n+1}$ を計算する。
４．$\mu_{n+1}$ と $(n+1)$ を保持し、次のデータを待つ。
というのを繰り返します。

※オンラインアルゴリズム、ストリームアルゴリズム、などと言われることもあります。

分散の逐次計算

分散の更新式：
$\sigma_{n+1}^2=\dfrac{n(\sigma_n^2+\mu_n^2)+x_{n+1}^2}{n+1}-\mu_{n+1}^2$
を使います。

具体的なアルゴリズムとしては、
１．$\mu_n$ と $\sigma_n^2$ と $n$ を保持しておく。
２．データ $x_{n+1}$ が入ってきたら。
３．平均の更新式を使って $\mu_{n+1}$ を計算する。
４．さらに、分散の更新式を使って $\sigma_{n+1}^2$ を計算する。
５．$\mu_{n+1}$ と $\sigma_{n+1}^2$ と $(n+1)$ を保持し、次のデータを待つ。
というのを繰り返す感じになります。

ちなみに、
・標準偏差を逐次計算したいときは、毎回４と５の間に平方根を取る操作を追加すればOKです。
・標本分散ではなく、不偏標本分散を逐次計算したいときは、、毎回４と５の間に $\dfrac{n+1}{n}$ 倍する操作を追加すればOKです。

更新式の証明

平均の更新式の証明
$\mu_{n+1}=\dfrac{x_1+\cdots +x_n+x_{n+1}}{n+1}\\
=\dfrac{\frac{x_1+\cdots +x_n}{n}\times n+x_{n+1}}{n+1}\\
=\dfrac{1}{n+1}(n\mu_n+x_{n+1})$

分散の更新式の証明
$\mathrm{Var}[X]=E[X^2]-E[X]^2$ という公式を（最初と最後で）使うと、
$\sigma_{n+1}^2=\dfrac{x_1^2+\cdots +x_{n+1}^2}{n+1}-\mu_{n+1}^2\\
=\dfrac{\frac{x_1^2+\cdots +x_n^2}{n}\times n+x_{n+1}^2}{n+1}-\mu_{n+1}^2\\
=\dfrac{n(\sigma_n^2+\mu_n^2)+x_{n+1}^2}{n+1}-\mu_{n+1}^2$

次回は ローレンツ曲線とジニ係数 を解説します。