9

大量のデータセットの分位数を数える必要があります。

一部の部分(つまり、大きな行列の1行)からのみデータを取得できると仮定します。Q3分位数をカウントするには、データのすべての部分を取得してどこかに保存してから、並べ替えて分位数をカウントする必要があります。

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分位数を数える他のもっと速い方法があるのではないかと思いました。

4

6 に答える 6

1

私はバケットを使用するという考えを2番目にしています。100バケットに制限しないでください。100万を使用することもできます。トリッキーな部分は、すべてが単一のバケットに収まらないようにバケット範囲を選択することです。おそらく、バケット範囲を推定する最良の方法は、データの妥当なランダムサンプルを取得し、単純な並べ替えアルゴリズムを使用して10%と90%の分位数を計算し、その範囲を満たすために同じサイズのバケットを生成することです。完璧ではありませんが、データが非常に奇妙なディストリビューションからのものでない場合は、機能するはずです。

ランダムなサンプルを作成できない場合は、さらに問題が発生します。予想されるデータ分布に基づいて最初のバケットの推測を選択し、データを処理しているときに、バケット(通常は最初または最後のバケット)がいっぱいになった場合は、新しいバケット範囲で最初からやり直すことができます。

于 2010-05-15T00:01:41.927 に答える
1

これには、極端な分位数の非常に優れた推定値を提供する、より最近のはるかに単純なアルゴリズムがあります。

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

https://github.com/tdunning/t-digestを参照してください

于 2017-02-27T09:43:04.863 に答える
0
  1. 本当に必要なデータのみを取得します。つまり、並べ替えのキーとして使用されている値はすべて取得します。他のすべての値は取得しません。
  2. Tony HoareのSelectアルゴリズムを使用すると、すべてのデータを並べ替えるよりもすばやく分位数を見つけることができます。
于 2010-05-14T20:26:10.790 に答える
0

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

データを2回渡すことができる場合は、次のようにします。

  • 最初のパスで、最大、最小、SD、および平均を計算します。
  • 2番目のパスでは、範囲[min、max]をいくつかのバケット(たとえば100)に分割します。(平均-2 * SD、平均+ 2 * SD)についても同じことを行います(外れ値用の追加のバケットを使用)。次に、データを再度実行し、これらのバケットに数値を入れます。
  • データの25%と75%になるまで、バケットをカウントします。特別な機能が必要な場合は、バケット値間を補間できます。(つまり、25番目の変位値をヒットするためにバケットの10%が必要な場合は、値が下限から上限までの10%であると想定します。)

これにより、完全に逆ではないデータのほとんどのセットで問題なく機能する、非常に優れた線形時間アルゴリズムが得られるはずです。

于 2010-05-14T21:18:11.910 に答える
0

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

考え方は次のとおりです。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);
于 2010-05-25T14:45:37.100 に答える
0

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

于 2015-10-21T16:22:04.370 に答える