[解決済み] 「統計的な中央値、最頻値、歪度、尖度を推定するためのオンライン（イテレータ）アルゴリズム？

質問

中央値、最頻値、歪度、尖度を推定するアルゴリズムで、すべての値を一度にメモリに格納する必要がないものはありますか？

基本的な統計量を計算したいのですが。

• 平均：算術平均
• 分散：平均値からの二乗偏差の平均値
• 標準偏差: 分散の平方根
• 中央値：数値の大きい半分と小さい半分を区切る値
• mode：集合の中で最も頻度の高い値
• 歪度：tl; dr
• 尖度：TL; DR

これらのいずれかを計算するための基本的な公式は小学校の算数で、私はそれを知っています。 また、それらを実装した多くの統計ライブラリがあります。

私の問題は、私が扱っているセット内の多数の(数十億の)値です。 Python で作業する場合、数十億の要素を持つリストまたはハッシュを作成することはできません。 Pythonで作業する場合、数十億の要素を持つリストやハッシュを作ることはできません。Cでこれを書いたとしても、10億要素の配列はあまり実用的ではありません。

データはソートされていない。 他の処理でその場その場でランダムに生成される。 各セットのサイズは大きく変動し、そのサイズも事前に知ることはできません。

私はすでに、集合の各値を任意の順序で反復して、平均と分散をかなりうまく処理する方法を見つけ出しています。 (実際には、私の場合、それらが生成された順序でそれらを取ります。) 以下は、私が使用しているアルゴリズムです。 http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_algorithm :

• count、sum、sum_of_squaresの3つの変数を初期化する。
• それぞれの値に対して
  • カウントをインクリメントします。
  • sumに値を追加します。
  • sum_of_squaresに値の2乗を追加。
• sumをcountで割って、変数meanとして格納。
• sum_of_squaresをcountで割って、mean_of_squaresという変数に格納。
• 平均を二乗し、square_of_meanとして格納。
• mean_of_squaresからsquare_of_meanを引き、分散として格納します。
• 平均と分散を出力します。

この "on-line" アルゴリズムには弱点（例えば、sum_of_squares がすぐに整数範囲や浮動小数点精度よりも大きくなるため精度の問題）がありますが、基本的には各セット内のすべての値を保存しなくても、私が必要とするものを与えてくれるものです。

しかし、追加の統計（中央値、最頻値、歪度、尖度）を推定するための同様のテクニックが存在するかどうかはわかりません。 N 個の値を処理するために必要なメモリが O(N) よりもかなり小さい限り、私は偏った推定量、またはある程度正確さを損なう方法さえも受け入れることができます。

もしライブラリがこれらの操作の1つまたは複数を計算する関数を持っているならば、既存の統計ライブラリを指し示してくれることも助けになるでしょう。

どのように解決するのですか？

歪度とクルトーシス

歪度とカルトーシスのオンライン・アルゴリズム（分散に沿ったもの）については、同じwikiページで を参照してください。 高次モーメント統計の並列アルゴリズムを参照してください。

中央値

中央値は、ソートされたデータでないと難しいです。もしデータポイントの数がわかっていれば、理論的には部分的にソートするだけでよく、たとえば 選択アルゴリズム . しかし、それは何十億もの値ではあまり役に立ちません。次のセクションを参照し、頻度カウントを使用することをお勧めします。

頻度カウントによる中央値および最頻値

整数であれば、数える 周波数 をカウントし、おそらく最高値と最低値は、もはや関連性がないと確信できる値を超えて切り捨てます。浮動小数点数（または多すぎる整数）の場合、私はおそらくバケット/間隔を作成し、整数の場合と同じ方法を使用します。(近似）最頻値と中央値の計算は、度数表に基づいて、簡単になります。

正規分布の確率変数

正規分布であれば、母集団の標本である 平均 , 分散 , 歪度 および 尖度 を小さな部分集合の最尤推定量として使用します。これらを計算するための（オンラインの）アルゴリズムは、既にご存知でしょう。例えば、推定誤差が十分に小さくなるまで、数十万または数百万のデータポイントを読み込むことができます。ただ、セットからランダムに選ぶようにする（例えば、最初の10万個の値を選ぶことによってバイアスがかからないようにする）。同じアプローチは、正規の場合の最頻値と中央値を推定するためにも使用できます（両方とも標本平均が推定量です）。

さらなるコメント

上記のアルゴリズムはすべて並列実行が可能です（QuickSortやQuickSelectなどの多くのソート・選択アルゴリズムも含む）、もしこれが役に立つなら。

私は常に(正規分布のセクションを除いて)、既知の分布を与えられた理論的なモーメントの推定量ではなく、サンプルモーメント、中央値、最頻値について話すと仮定してきました。

一般に、すべての観測が同じ確率変数の実現であり（同じ分布を持っている）、モーメント、最頻値、および中央値がこの分布に対して実際に存在する限り、データのサンプリング（つまり、サブセットだけを見ること）は、データ量に依存してかなり成功するはずです。最後の注意点は、無害なものではありません。例えば、平均値（およびすべての高次モーメント）は コーシー分布 は存在しません。この場合、「小さな」サブセットの標本平均は、標本全体の標本平均から大きく外れている可能性があります。