大規模なデータセットの分位数をカウントする増分方法

StackOverflow https://stackoverflow.com/questions/2837311

質問

大規模なデータセットの分位数をカウントする必要があります。

一部の部分（つまり、大きな行列の 1 行)。第 3 四半期の分位数をカウントするには、データのすべての部分を取得してどこかに保存し、それを並べ替えて分位数をカウントする必要があります。

List<double> allData = new List<double>();
// This is only an example; the portions of data are not really rows of some matrix
foreach(var row in matrix) 
{
    allData.AddRange(row);
}

allData.Sort();
double p = 0.75 * allData.Count;
int idQ3 = (int)Math.Ceiling(p) - 1;
double Q3 = allData[idQ3];

データを中間変数に保存せずに分位点を取得する方法を見つけたいと考えています。最善の解決策は、最初の行の中間結果のパラメータをいくつかカウントし、それを次の行で段階的に調整することです。

注記：

  • これらのデータセットは非常に大きいです (各行に約 5000 要素)
  • Q3 は推定できますが、正確な値である必要はありません。
  • 私はデータの部分を「行」と呼んでいますが、異なる長さを持つこともできます。通常、それほど変化しません (+/- 数百サンプル) が、変化します。

この質問は次のようなものです 統計的中央値、最頻値、歪度、尖度を推定するための「オンライン」(反復子) アルゴリズム, 、しかし、分位数を数える必要があります。

また、このトピックに関する記事はほとんどありません。つまり、次のとおりです。

これらのアプローチを実装する前に、0.25/0.75 分位数を数える他のより迅速な方法はないのかと疑問に思いました。

役に立ちましたか？

解決 5

に触発された この答え 分位数を非常に適切に推定する方法を作成しました。私の目的には十分近い近似値です。

アイデアは次のとおりです。実際、0.75 分位値は、グローバル中央値を上回るすべての値の中央値です。それぞれ、0.25 分位数は、グローバル中央値を下回るすべての値の中央値です。

したがって、中央値を近似できれば、同様の方法で分位数も近似できます。

double median = 0;
double q1 = 0;
double q3 = 0;
double eta = 0.005;

foreach( var value in listOfValues) // or stream, or any other large set of data...
{
    median += eta * Math.Sign(p.Int - median);
}
// Second pass. We know the median, so we can count the quantiles.
foreach(var value in listOfValues)
{ 
    if(p.Int < median)
        q1 += eta*Math.Sign(p.Int - q1);
    else
        q3 += eta*Math.Sign(p.Int - q3);
}

備考：

  • データの分散がおかしい場合は、より大きなデータが必要になります。 eta 奇妙なデータに適合させるため。ただし精度は悪くなります。
  • 分布が奇妙でも、コレクションの合計サイズはわかっている場合 (つまり、N) を調整できます。 eta このようにパラメータを指定します。最初に設定します eta ある大きな値とほぼ等しいこと（すなわち、0.2）。ループが通過するにつれて、 の値を下げます。 eta したがって、コレクションのほぼ終わりに達すると、 eta はほぼ 0 になります (たとえば、ループ内で次のように計算します: eta = 0.2 - 0.2*(i/N);

他のヒント

I二バケットを使用してのアイデア。 100個のバケットに自分自身を制限しない - なども100万を使用することがあります。トリッキーな部分は、すべてが単一バケツで終わるしないように、あなたのバケット範囲を選択することです。おそらくあなたのバケット範囲を推定するための最良の方法は、あなたのデータの合理的なランダムなサンプルを取る簡単なソートアルゴリズムを用いて、10％と90％の分位数を計算し、その範囲を埋めるために同じサイズのバケットを生成することです。これは完璧ではありませんが、あなたのデータは、超奇妙な分布からではない場合、それが動作するはずです。

あなたはランダムなサンプルを行うことができない場合は、

、あなたは多くの問題にしています。新しいバケット範囲でやり直す、任意のバケット（通常、最初または最後のバケットが）超満員なれば、あなたのデータを通じて作業しながら、あなたの期待データ分布に基づいて、最初のバケットの推測を選ぶことができます。

極度の変位値の非常に良い推定値を提供し、このためのシンプルな、より最近の多くのアルゴリズムがあります。

の基本的な考え方は、より小さなビンの両方が小さなまたは大きなQのデータ構造のサイズと保証高精度の境界をする方法に極端で使用されることです。このアルゴリズムは、いくつかの言語や多くのパッケージで提供されています。 MergingDigestバージョンがMergingDigestがインスタンス化されると、それ以上のヒープ割り当てを必要としない...何の動的な割り当てを必要としません。

https://github.com/tdunning/t-digestする

  1. 本当に必要なデータのみを取得します。つまり、ソートのキーとして使用されている値であっても、それに関連付けられている他のすべての値ではありません。
  2. おそらく、Tony Hoare の選択アルゴリズムを使用すると、すべてのデータを並べ替えるよりも早く分位数を見つけることができます。

データにガウス分布がある場合は、標準偏差から分位数を推定できます。データがガウス分布ではないか、とにかく SD を使用しているだけだと思います。

データを 2 回通過できる場合は、次のようにします。

  • 最初のパスでは、最大、最小、SD、平均を計算します。
  • 2 番目のパスでは、範囲 [min,max] をいくつかのバケットに分割します (例:100);(mean - 2*SD,mean + 2*SD) についても同じことを行います (外れ値用に追加のバケットを使用します)。次に、データを再度実行して、数値をこれらのバケットに投入します。
  • データの 25% と 75% に達するまでバケットを数えます。さらに凝ったことをしたい場合は、バケット値の間を補間することができます。(つまり、25 分位に達するためにバケットの 10% が必要な場合、その値が下限から上限までの 10% であると仮定します)。

これにより、完全に歪んでいないほとんどのデータセットに対して問題なく動作する、かなり優れた線形時間アルゴリズムが得られます。

q-digest は、分位数を計算できる近似オンライン アルゴリズムです。 http://www.cs.virginia.edu/~son/cs851/papers/ucsb.sensys04.pdf

実装例は次のとおりです。

https://github.com/airlift/airlift/blob/master/stats/src/main/java/io/airlift/stats/QuantileDigest.java

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top