23

バインドされていないデータセットの平均値と標準偏差を計算するアルゴリズムがあるかどうか疑問に思います。

たとえば、電流などの測定値を監視しています。すべての履歴データの平均値が欲しいのですが。新しい値が来るたびに、平均と標準偏差を更新しますか?データが大きすぎて保存できないため、データを保存せずに平均値と標準偏差をその場で更新できることを願っています。

データが保存されていても、標準的な方法(d1 + ... + dn)/ nは機能せず、合計によってデータ表現が失われます。

約sum(d1 / n + d2 / n + ... d3 / n)を通過しますが、nが大きい場合、エラーが大きすぎて累積されます。また、この場合、nはバインドされていません。

データの数は間違いなく無制限です。データが来るたびに、値を更新する必要があります。

そのためのアルゴリズムがあるかどうか誰かが知っていますか?

4

5 に答える 5

19

【質問変わった?多分私は最初だけ読んだ。より良い返信をするために更新/編集しました:]

私が知っている完璧な解決策はありませんが、さまざまなアプローチを提供できます。

sum_xまず、基本的な計算では、すべての値の合計 ( ) 、2 乗の合計 ( sum_x2)、および合計数 ( )のみが必要ですn。それから:

mean = sum_x / n
stdev = sqrt( sum_x2/n - mean^2 )

これらすべての値 ( sum_xsum_x2n) は、ストリームから更新できます。

問題は(あなたが言うように)オーバーフローおよび/または限られた精度を扱うことです。sum_x2が大きすぎて内部表現に単一の二乗値の大きさの値が含まれていない場合に浮動小数点を考慮すると、これを見ることができます。

この問題を回避する簡単な方法は、正確な算術演算を使用することですが、これはますます遅くなります (また、O(log(n)) メモリを使用します)。

役立つ別の方法は、値を正規化することです-値が通常であることがわかっている場合は、合計が小さくなるX計算を行うことができます(明らかに、平均に追加します!)。これは、精度が失われるポイントを延期するのに役立ちます(また、ここで他の方法と組み合わせることができます/組み合わせる必要があります-たとえば、ビニングの場合、前のビンの平均を使用できます)。これを段階的に行う方法については、このアルゴリズム (knuth の方法) を参照してください。x - XX

(小さな定数係数)O(n)のメモリコストを気にしない場合は、すべての値を再起動Nできます(たとえば、100万-精度が低すぎる場合を検出してこの値を適応させる方が賢明です)、以前の平均値とstdevを保存し、次に、最終結果を結合します(したがって、平均は、最近の現在の合計と古いビン化された値から適切に加重された値です)。

ビニングアプローチはおそらく複数のレベルに一般化でき(ビンのビニングを開始します)、O(log(n))のメモリ使用量に削減されますが、詳細はわかっていません。

最後に、より実用的な解決策は、たとえば 1000 個の値に対して最初のアプローチを実行し、それから新しい合計を並行して開始することです。2 つの加重平均を表示し、別の 1000 の値の後で、古い合計を削除して (重みを徐々に減らした後)、新しいセットを開始することができます。したがって、常に 2 セットの合計があり、それらの間の加重平均を表示すると、最後の 1000 個の値 (のみ) を反映する連続データが得られます。場合によっては、それで十分だと思います(「最近の」データのみであるため、正確な値ではありませんが、滑らかで代表的であり、固定量のメモリを使用します)。

ps、後で私に起こったこと-実際、これを「永遠に」行うことは、とにかくあまり意味がありません。値が古いデータによって完全に支配されるようになるからです。古い値の重みを減らす「移動平均」を使用することをお勧めします。たとえば、https://en.wikipedia.org/wiki/Moving_averageを参照してください-ただし、stdev に相当する一般的なものはわかりません。

于 2012-04-28T15:56:31.837 に答える
5

興味深い質問です。

少し単純なので、最初に平均について説明しましょう。

実行中の合計の丸め誤差については正しいです。データセットが十分に大きい場合、精度が低下します。最初に小さなデータを合計して、データを事前に並べ替えたいとします。もちろん、これはあなたの場合は不可能です。ただし、いくつかの実行中の合計を保持することで、並べ替えられたデータの利点のほとんどを実現できます。

概念的な例、C または C++ スタイル:

const double max_small  =    0.001;
const double max_medium = 1000.0;

double total_small;
double total_medium;
double total_large;

while(true) {
    const double datum = get_datum(); // (Use here whatever function you use to get a datum.)
    if (!is_datum_valid()) break;
    if (abs(datum) <= max_small) total_small += datum;
    else if (abs(datum) <= max_medium) total_medium += datum;
    else total_large += datum;
}

double total = 0.0;
total += total_small;
total += total_medium;
total += total_large;

現実的なコードでは、おそらく 3 つ以上の実行中の合計を保持することになります (もちろん、データの 2 乗の実行中の合計も保持します)。詳細を入力できます。

また、@andrewcooke のアイデアを採用すると、次のような方法でループを展開できます。

while(true) {
    const double datum = get_datum();
    if (!is_datum_valid()) break;
    if (abs(datum) <= max_small) {
        total_small += datum;
        if (abs(total_small) > max_medium) {
            total_large += total_small;
            total_small = 0.0;
        }
    }
    else if (abs(datum) <= max_medium) total_medium += datum;
    else total_large += datum;
}

ここでも、詳細を入力できます。幸運を。

付録: 標準偏差の実際の計算

ここのさまざまなコメント スレッドで、平均値を事前に知らなくても標準偏差を計算する方法に関して、良い質問が提起されています。幸いなことに、標準偏差を計算するためのトリックが知られています。裏技を解説したメモを2ページ用意しました(PDF)。

いずれにせよ、実行中の統計に標準偏差を含めるために必要なのは、データだけでなくデータの 2 乗も合計することだけです。もちろん、上記のコードと同じパターンに従って、データ自体と同様の方法で平方を合計することもできます。

于 2012-04-28T16:07:24.487 に答える
4

いいえ。

(私は思った:いいえ、しかし私は間違っていることが証明されています)。

合計とカウントを運ぶことができるので、

sum(i)=500, count(i)=50, => avg:=10
next value = 20
sum=520, count=51 => avg:= 10.19

しかし、stddev はそのように構築することはできません。すべての値の新しい平均に対するデルタを生成し、それらを 2 乗し、その後でのみ N で除算する必要があります。 ただし、問題は、それらの値がどのようなものかということです (数学的な観点から - 物理学には近づかないでください! :) )。通常の状況では、2000 個の要素の後に値が変更されるとは思いません。そうでなければ、そもそも mean と stddev を構築することに疑問があるかもしれません。

また、2000 個の要素の場合、値を高速に計算できるはずです。

おそらく、バッファを使用して、2000 個の値ごとに最後の 2000 個の値の avg と stddev を常に計算できます。これが意味のあるデータかどうかは、あなたが決めなければならないことです。


チャットでの議論がうまく続かない...

マークダウンを詳しく説明していないためです。したがって、私は自分の投稿を使用して、主に thb のコメントに広がっている自分の立場を明確にしていますが、andrew は stddev のスライド計算も信じているようです。

これは、計算を明確にし、従うのを容易にするための広い表です。列は次のとおりです。

  • i: 実行中のインデックス。最初に値 1 ~ 3 を計算し、次に値 1 ~ 5 を計算します。
  • x(i) は、私が任意に選択したデータです。3,4,5 および 4,6
  • 合計は、それらが合計したものにすぎません。興味深いのは、グループの最後の 12 と 22 です。注: 3 つの値と 2 つの値の合計をとるのではなく、最初の 3 と最初の 5 の合計を取ります。
  • 平均はわずか 12/3 または 22/5 です。i と合計がわかっている場合、平均はスライドして計算できます。sum(i+1) = (sum (i)+x(i))/i+1ここまで異論なし。
  • stddev. を計算するには、各値の差を平均に取り、それを 2 乗する必要があります (これにより、符号が失われます。そうしないと、差が無効になり、常に 0 になります)。2 番目の効果は、いくつかの大きな距離が、多くの小さな距離よりも大きな stddev につながることです。距離(1,1,-1,-1)=> 4*1² = 4.対照的に: (2,-2)=> 2² + -2² = 4+4 = 8. 最初の列は 3 つの値、2 番目の列は 5 つの値 (計算に従うため) です。
  • 次の列 (最後)² は二乗を行います。
  • まとめて
  • n-1 で割る
  • 平方根を取る

計算付きスプレッドシート (oocalc スクリーンショット)

おそらく、これが stddev を計算する有効な方法であることに同意できるでしょう。ここで問題は、完全な行 3 (x(3)=5 を除く) を知っている場合にどのように計算するかです。シートに示されているように、(x( i) i = 1、2、3 の場合。

私の申し立ては失敗しました: できます。

わかりました - あなたの数式を使用しようとしました。

ð² = 1/(N-1) (合計 (x i ²) - 1/N (合計 (x i ))²)

だから私が得る4つの値について

  • N=5
  • 合計(x i ) = 22
  • 合計(x i ²) = 102

数式に挿入:

ð² = 1/(N-1) (Sum (x<sub>i</sub>²) - 1/N (Sum (x<sub>i</sub>))²)
ð² = 1/4 (102 - 1/5 (22²))
ð² = 1/4 (102 - 1/5 (484))
ð² = 1/4 (102 - 96.8)
ð² = 1/4 (5.2)
ð² = 1.3
ð  = 1.140

私の結果は 1.14 で、あなたの結果は 1.14です。ショートカットがあります。非常に興味深い - 私はまだ驚いています。

于 2012-04-28T16:14:35.330 に答える
2

実際、標準偏差を計算するときに小さなデータ セットであっても、二乗和を計算するべきではありません。この問題は壊滅的なキャンセルと呼ばれます(リンクはウィキペディアへ)。

ウィキペディアには、この問題から抜け出すのに役立つ 2 つの記事もあります。

  • 多数の非常に小さな値を合計する場合 (たとえば、すべての x/n 値を合計する場合) に、系統誤差を回避するためのキャリーオーバーを持つKahan 合計アルゴリズム
  • 分散を計算するためのアルゴリズム、特に「オンライン」バージョンは、大規模なデータ セットに適している必要があります。観測値ごとに平均値が段階的に更新されるため、値はデータのスケールのままです! 最初のオンラインアルゴリズムは平均からの二乗偏差の合計を計算するため、分散に高次バージョンを使用する必要がある場合があります。そのため、n が大きいと、値の範囲が破綻する可能性があります。高次バージョンの M2 には、平均からの偏差の二乗平均が含まれている必要があります。これは、出力のスケールにあります。

これはおそらく、単純な統計計算で最も一般的な問題の 1 つです。

平均が 0 付近にとどまり、分散よりもはるかに小さい場合、問題は発生しないことに注意してください。

于 2013-05-01T11:59:33.710 に答える