25

平均を計算するための最良の方法は何ですか？この質問では、平均を計算するためのどのアルゴリズムが数値的な意味で最適であるかを知りたいと思います。丸め誤差が最小である必要があり、オーバーフローやアンダーフローなどの影響を受けないようにする必要があります。

ありがとうございました。

追加情報：値の数がRAMに収まらない可能性があるため、増分アプローチが推奨されます（4 GBを超えるファイルでのいくつかの並列計算）。

4

6 に答える 6

12

O（N）アルゴリズムが必要な場合は、カハンの加算を見てください。

于 2011-09-26T08:29:09.653 に答える
10

http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.3535（Nick Higham、「浮動小数点の合計の精度」、SIAM Journal of Scientific Computation、1993）をご覧ください。 。

私が正しく覚えていれば、すべての数値が正の場合、少なくともそれらを並べ替えて昇順で加算するのと同じくらい良い場合は、補償された加算（カハンの加算）が適しています（数値が非常に多い場合を除く）。一部の数値が正で一部が負の場合、話ははるかに複雑になるため、キャンセルされます。その場合、降順で追加するという議論があります。

于 2011-09-26T10:33:00.953 に答える
5

数値を大きさの昇順で並べ替えます。それらを合計します。最初に低マグニチュードです。カウントで割ります。

于 2011-09-26T08:27:49.313 に答える
5

私は常に次の擬似コードを使用します。

float mean=0.0; // could use doulbe
int n=0;  // could use long

for each x in data:
    ++n;
    mean+=(x-mean)/n;

その安定性の正式な証明はありませんが、データ値が適切に動作していると仮定すると、数値のオーバーフローに問題がないことがわかります。これは、クヌースのThe Art ofComputerProgrammingで言及されています

于 2014-06-03T19:44:50.193 に答える
3

さらなる議論のために1つの可能な答えを追加するだけです：

各ステップの平均を段階的に計算します。

AVG_n = AVG_（n-1）*（n-1）/ n + VALUE_n / n

またはペアワイズの組み合わせ

AVG_（n_a + n_b）=（n_a * AVG_a + n_b * AVG_b）/（n_a + n_b）

（式が十分に明確であることを願っています）

于 2011-09-26T14:06:48.563 に答える
3

非常に遅い投稿ですが、コメントするのに十分な評判がないため、@Daveの方法はGnuScientific Libraryで使用されている方法です（2020年12月現在） 。

mean_source.cから抽出されたコードは次のとおりです。

double FUNCTION (gsl_stats, mean) (const BASE data[], const size_t stride, const size_t size)
{
/* Compute the arithmetic mean of a dataset using the recurrence relation mean_(n) = mean(n-1) + (data[n] - mean(n-1))/(n+1)   */

long double mean = 0;
size_t i;

for (i = 0; i < size; i++)
{
  mean += (data[i * stride] - mean) / (i + 1);
}

return mean;
}

GSLは同じアルゴリズムを使用して分散を計算します。分散は、結局のところ、特定の数値との差の2乗の平均にすぎません。

于 2020-12-20T17:28:39.047 に答える