algorithm - 数値セットの均一性または不一致を計算する簡単な方法

Question

こんにちは、均一性の尺度をすばやく計算したい一連の数値があるとします。分散が最も明白な答えであることは知っていますが、単純なアルゴリズムの複雑さが高すぎるのではないかと心配しています。

Answer 1

分散を計算するための「直感的な」アルゴリズムは、通常、次のいずれかまたは両方の影響を受けます。

1. 2 つのループを使用します (1 つは平均の計算用、もう 1 つは分散の計算用)。
2. 数値的に安定していない

ループが 1 つだけで数値的に安定している優れたアルゴリズムは、(いつものように) D. Knuthによるものです。

ウィキペディアから：

n = 0
mean = 0
M2 = 0
 def calculate_online_variance(x):
    n = n + 1
    delta = x - mean
    mean = mean + delta/n
    M2 = M2 + delta*(x - mean)  # This expression uses the new value of mean

    variance_n = M2/n
    variance = M2/(n - 1) #note on the first pass with n=1 this will fail (should return Inf)
    return variance

ポイントごとに calculate_online_variance(x) を呼び出す必要があります。これまでに計算された分散が返されます。