88

一連の値の中央値、モード、歪度、および/または尖度を推定するアルゴリズムはありますが、すべての値を一度にメモリに保存する必要はありませんか?

基本的な統計を計算したい：

  • mean: 算術平均
  • 分散: 平均からの二乗偏差の平均
  • 標準偏差: 分散の平方根
  • 中央値: 数値の大きい方の半分と小さい方の半分を分ける値
  • モード: セットで見つかった最も頻繁な値
  • 歪度: tl; 博士
  • 尖度: tl; 博士

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

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

データはソートされていません。他のプロセスによって、オンザフライでランダムに生成されます。各セットのサイズは非常に可変であり、サイズは事前にわかりません。

セット内の各値を任意の順序で反復して、平均と分散を適切に処理する方法をすでに理解しています。(実際、私の場合、生成された順序でそれらを取得します。) これが私が使用しているアルゴリズムです。

  • 3 つの変数を初期化します: count、sum、および sum_of_squares
  • 各値について:
    • 増分カウント。
    • 合計に値を追加します。
    • 値の 2 乗を sum_of_squares に追加します。
  • 合計をカウントで割り、変数の平均として保存します。
  • sum_of_squares をカウントで割り、変数 mean_of_squares として格納します。
  • 二乗平均、square_of_mean として保存します。
  • mean_of_squares から square_of_mean を引き、分散として保存します。
  • 平均と分散を出力します。

この「オンライン」アルゴリズムには弱点があります (たとえば、sum_of_squares が整数の範囲や float の精度よりも急速に大きくなるため、精度の問題が発生するなど)、基本的には、各セットにすべての値を格納する必要がなく、必要なものが得られます。

しかし、追加の統計 (中央値、モード、歪度、尖度) を推定するための同様の手法が存在するかどうかはわかりません。N 個の値を処理するために必要なメモリが O(N) よりも大幅に少ない限り、偏った推定器や、精度をある程度損なう方法を使用することもできます。

ライブラリにこれらの操作の1つ以上を「オンライン」で計算する関数がある場合、既存の統計ライブラリを指すことも役立ちます。

4

14 に答える 14

57

私はこれらの増分/再帰平均および中央値推定量を使用します。これらは両方とも一定のストレージを使用します。

mean += eta * (sample - mean)
median += eta * sgn(sample - median)

ここで、etaは小さな学習率パラメーター（例：0.001）であり、sgn（）は{-1、0、1}のいずれかを返す符号関数です。（データが非定常であり、時間の経過に伴う変化を追跡する場合は、定数etaを使用します。それ以外の場合、定常ソースの場合、平均推定量にeta = 1 / nのようなものを使用できます。ここで、nは見られるサンプルの数です。はるかに...残念ながら、これは中央値推定量では機能しないようです。）

このタイプの増分平均推定量は、教師なしニューラルネットワーク学習ルールなど、あらゆる場所で使用されているようですが、中央値バージョンは、その利点（外れ値に対するロバスト性）にもかかわらず、あまり一般的ではないようです。中央値バージョンは、多くのアプリケーションで平均推定量の代わりに使用できるようです。

同様の形式のインクリメンタルモード推定器を見たいです...

更新（2011-09-19）

任意の分位数を推定するように増分中央値推定量を変更しました。一般に、分位関数は、データを2つの分数（pと1-p）に分割する値を示します。以下は、この値を段階的に推定します。

quantile += eta * (sgn(sample - quantile) + 2.0 * p - 1.0)

値pは[0,1]以内である必要があります。これにより、基本的にsgn（）関数の対称出力{-1,0,1}が片側に傾くようにシフトし、データサンプルが2つの等しくないサイズのビンに分割されます（データの分数pと1-pはより小さい/より大きい）それぞれ、分位数の推定値）。p = 0.5の場合、これは推定量の中央値に減少することに注意してください。

更新（2021-11-19）

ここで説明する中央値推定量の詳細については、以下のコメントにリンクされているこの論文を強調したいと思います：Bylander＆Rosen、1997、中央値を追跡するためのパーセプトロンのようなオンラインアルゴリズム。これは作者のウェブサイトからの追記版です。

于 2010-01-27T05:24:00.633 に答える
13

私が作成したLiveStatsというきちんとした Python モジュールに、観測値を保存せずに分位点とヒストグラムを動的に計算するための P-Square アルゴリズムを実装しました。それはあなたの問題を非常に効果的に解決するはずです。ライブラリは、モードを除いて、あなたが言及したすべての統計をサポートしています。モード推定の満足のいく解決策をまだ見つけていません。

于 2013-03-09T16:34:37.297 に答える
7

ライアン、あなたは平均と分散を正しく行っていないのではないかと心配しています...これは数週間前にここで出てきました. そして、オンライン バージョン (実際にはウェルフォード法と呼ばれる) の長所の 1 つは、それが特に正確で安定しているという事実です。ここでの議論を参照してください。長所の 1 つは、総和または総平方和を保存する必要がないという事実です...

リスト全体を一度に考慮する必要があるように思われるモードと中央値へのオンラインアプローチは考えられません。しかし、分散と平均のアプローチと同様のアプローチが、歪度と尖度にも機能する可能性があります...

于 2009-06-29T17:55:05.500 に答える
2

誰もがオンラインでモードを実行できないと言い続けていますが、それは単に真実ではありません. これは、1982 年にイェール大学の Michael E. Fischer と Steven L. Salzberg によって発明された、まさにこの問題を解決するためのアルゴリズムを説明する記事です。記事から：

多数決アルゴリズムは、レジスタの 1 つを使用して、ストリームからの 1 つのアイテムを一時的に格納します。このアイテムは、多数要素の現在の候補です。2 番目のレジスターは、0 に初期化されたカウンターです。ストリームの各要素について、アルゴリズムに次のルーチンを実行するように要求します。カウンターが 0 を読み取る場合、現在のストリーム要素を新しい多数決候補としてインストールします (既にレジスターにある可能性のある他の要素を置き換えます)。次に、現在の要素が多数決候補と一致する場合、カウンターをインクリメントします。それ以外の場合は、カウンターを減らします。サイクルのこの時点で、これまでに確認されたストリームの部分に多数要素がある場合、その要素は候補レジスタにあり、カウンターは 0 より大きい値を保持します。多数派の要素がない場合はどうなりますか? ストリーム環境では不可能な、データの 2 回目のパスを作成しないと、アルゴリズムはこの状況で常に明確な答えを返すことができません。過半数要素が存在する場合、それを正しく識別することを約束するだけです。

より多くのメモリを使用して上位 N を見つけるように拡張することもできますが、これでモードが解決されるはずです。

于 2012-02-19T17:22:20.867 に答える
2

数十億のデータ ポイントがある場合、厳密な回答ではなく、正確な回答が必要になる可能性は低くなります。一般に、数十億のデータポイントがある場合、それらを生成する基本的なプロセスは、ある種の統計的定常性/エルゴード性/混合特性に従う可能性があります。また、分布が合理的に連続的であると予想するかどうかも重要です。

このような状況では、正確な答えが必要ない場合は、オンライン、低メモリ、分位数の推定(中央値は 0.5 の分位数の特殊なケース)、およびモード用のアルゴリズムが存在します。これは統計のアクティブなフィールドです。

分位推定の例: http://www.computer.org/portal/web/csdl/doi/10.1109/WSC.2006.323014

モード推定の例: Bikel DR。連続データのモードと歪度の堅牢な推定量。計算統計とデータ分析。2002;39:153–163。ドイ: 10.1016/S0167-9473(01)00057-3.

これらは、計算統計のアクティブなフィールドです。あなたは、単一の最良の正確なアルゴリズムではなく、さまざまな特性、仮定、およびパフォーマンスを持つ多様なアルゴリズム (実際には統計推定量) がある分野に参入しています。実験数学です。このテーマについては、おそらく数百から数千の論文があります。

最後の質問は、歪度と尖度が本当に必要なのか、それとも確率分布を特徴付ける際により信頼性の高い他のパラメーターが必要なのかということです (確率分布があると仮定して!)。ガウスを期待していますか？

データをほとんどガウス風にするためにデータをクリーニング/前処理する方法はありますか? (たとえば、金融取引額は、対数を取った後、幾分ガウス型になることがよくあります)。有限の標準偏差を期待していますか? ファットテールを期待していますか？気になる量はテールですか、それともバルクですか?

于 2009-10-18T23:08:13.717 に答える
1

最終的に、分布に関する事前のパラメトリック知識がない場合は、すべての値を保存する必要があると思います。

とはいえ、ある種の病理学的状況に対処している場合を除き、治療法 (Rousseuw and Bassett 1990) で十分に目的を達成できる可能性があります。

非常に単純に、中央値のバッチの中央値を計算することが含まれます。

于 2009-07-27T21:14:47.043 に答える
0

中央値と最頻値は、利用可能な一定のスペースのみを使用してオンラインで計算することはできません。ただし、中央値と最頻値は「定量的」よりも「記述的」であるため、データセットをサンプリングするなどして推定できます。

データが長期的に正規分布している場合は、平均を使用して中央値を推定できます。

次の手法を使用して中央値を推定することもできます。たとえば、データストリーム内の1,000,000エントリごとに中央値推定M [i]を確立して、M[0]が最初の100万エントリの中央値M[1]になるようにします。 2番目の100万エントリの中央値など。次に、M [0] ...M[k]の中央値を中央値推定器として使用します。もちろん、これによりスペースが節約され、パラメーター1,000,000を「調整」することで、スペースを使用する量を制御できます。これは再帰的に一般化することもできます。

于 2009-06-29T16:18:00.017 に答える
0

OKおい、これらを試してみてください：

C++ の場合:

double skew(double* v, unsigned long n){
    double sigma = pow(svar(v, n), 0.5);
    double mu = avg(v, n);

    double* t;
    t = new double[n];

    for(unsigned long i = 0; i < n; ++i){
        t[i] = pow((v[i] - mu)/sigma, 3);
    }

    double ret = avg(t, n);

    delete [] t;
    return ret;
}

double kurt(double* v, double n){
    double sigma = pow(svar(v, n), 0.5);
    double mu = avg(v, n);

    double* t;
    t = new double[n];

    for(unsigned long i = 0; i < n; ++i){
        t[i] = pow( ((v[i] - mu[i]) / sigma) , 4) - 3;
    }

    double ret = avg(t, n);

    delete [] t;
    return ret;
}

サンプルの分散 (svar) と平均 (avg) を既に計算できると言う場合は、それらを関数に指定してそれを実行します。

また、ピアソンの近似を見てください。このような大規模なデータセットでは、かなり似ています。3 (平均 - 中央値) / 標準偏差 中央値を最大 - 最小/2

floats モードの場合は意味がありません。通常、それらを非常に大きなサイズのビンに貼り付けます（1/100 *（最大 - 最小）など）。

于 2013-01-29T13:37:50.900 に答える
-1 
for j in range (1,M):
    y=np.zeros(M) # build the vector y
    y[0]=y0

    #generate the white noise
    eps=npr.randn(M-1)*np.sqrt(var)

    #increment the y vector
    for k in range(1,T):
        y[k]=corr*y[k-1]+eps[k-1]

    yy[j]=y

list.append(y)
于 2016-01-18T14:27:41.890 に答える
-1

私は適応性のあるバケットを使用する傾向があります。バケットのサイズは、必要な精度にする必要があります。次に、データ ポイントが入るたびに、関連するバケットのカウントに 1 を追加します。これらは、各バケットをそのカウントで重み付けされた値としてカウントすることにより、中央値と尖度の単純な近似値を提供するはずです。

1 つの問題は、数十億回の操作の後に浮動小数点の解像度が失われる可能性があることです。つまり、1 つ追加しても値はそれ以上変化しません! これを回避するために、最大バケット サイズが制限を超えた場合、すべてのカウントから多くの数を取り除くことができます。

于 2010-10-28T23:38:11.960 に答える