定数ストレージを使用して無制限シーケンスを要約する

Question

特定の値を頻繁にサンプリングし、そのサンプルについて統計を保持したいとします。最も簡単なアプローチは、すべてのサンプルを保存して、必要な統計情報を計算できるようにすることですが、これには無制限のストレージが必要です。一定量のストレージを使用して、最小値や最大値などの統計情報を記録できます。一定の記憶域だけを使用してその他何を追跡できますか？私はパーセンタイル、標準偏差、およびその他の有用な統計を考えています。

これは理論的な質問です。私の実際の状況では、サンプルは単純にミリ秒のタイミングです。長時間実行するアプリケーションのプロファイリング情報です。数百万のサンプルがありますが、それほど多くはないでしょう。だから、例えば10個の変数だけを使ってサンプルのためにどのような統計を保持することができますか？

Answer 1

最小、最大、平均、合計カウント、分散はすべて簡単で便利です。それは5つの値です。 通常、平均値ではなく合計値を保存します。平均値が必要な場合は、合計値をカウント値で割ります。

ので、

maxVal=max(x, maxVal); 
minVal=min(x, minVal); 
count+=1; 
sum+=x; 
secondorder+=x*x; 

後のあなたのループでは、これらの統計情報のいずれかを印刷することができます。平均と標準偏差はいつでも計算できます。

mean=sum/count; 
std=sqrt(secondorder/count - mean*mean); 

中央値と百分率の推定はより困難ですが、可能です。通常のトリックはヒストグラムビンのセットを作り、その中にサンプルが見つかるとビンを埋めることです。 これらのビン集団の分布を見ることで、中央値などを見積もることができます。 これは、配布には近似のみですが、しばしば十分です。正確な中央値を見つけるには、すべてのサンプルを保存する必要があります。

Answer 2

よく、それらの多く。例えば、σと考えてください。平均値とデータポイントから計算された分散の平方根。ポイントX _iには、これまでのすべてのポイントの推定分散があります。次の見積もりの​​ために（x-μ）²を追加します。 wikipediaには素晴らしいセクションがあります。

あなたが探しているものは、一般的に「オンライン計算法」と呼ばれています。

Answer 3

質問に答える記事は次のとおりです：Accurately computing running variance。

正確な算術では同等ですが、有限精度を使用するコンピュータではない分散または標準偏差を計算するには、いくつかの方法があることに注意してください。理論的にうまくいくアルゴリズムの中には、実際には不正確なものがあります。上記の記事は、実行中の分散、すなわち定数メモリを計算し、正確に計算します。

パーセンタイルを計算するには、データセットのサイズによってメモリ要件が異なることになります。たとえば、5番目と95番目のパーセンタイルが必要な場合、メモリ要件はデータセットのサイズに比例します。しかし、例えば、5番目または95番目の最小要素がほしいと思うなら、それを一定の記憶の中で行うことができます。 CodeProjectの記事Calculating percentiles in memory-bound applicationsを参照してください。