5

入力ファイルまたは標準出力データ ストリームのおおよその行数を取得する最速の方法は何ですか。参考までに、これは確率的アルゴリズムです。オンラインで多くの例を見つけることができません。

データは、csv ファイルの awk スクリプトからの 1 つまたは 2 つの列である可能性があります。列の1つに約groupbyが必要だとしましょう。データベース グループを使用しますが、行数は 60 ～ 70 億を超えています。最初のおおよその結果を 3 ～ 4 秒以内に取得したいと思います。次に、事前に決定が下された後、ベイズまたは何かを実行します。本当に大まかな初期グループ数についてのアイデアはありますか?

PythonまたはJavaでアルゴリズムの例を提供できれば、非常に役立ちます。

4

2 に答える 2

5

合計行数を数えたい場合は、@BenAllisonの答えが良い方法です。ベイズとそれ以前のことについておっしゃっていたので、その方向に答えを追加して、さまざまなグループの割合を計算します。（あなたの質問に対する私のコメントを参照してください。あなたが合計のアイデアを持っていて、あなたがしたいのであればgroupby、異なるグループのパーセンテージを推定することはより理にかなっていると思います）。

再帰的なベイジアン更新：

まず、グループが2つしかないことを前提としています（複数のグループで機能するように拡張できます。これについては、後の説明を参照してくださいgroup1）group2。

m group1処理した最初のn行（行）のうちのsについては、イベントをとして示しM(m,n)ます。明らかに、n-m group2sが表示されるのは、それらが2つの可能なグループのみであると想定しているためです。したがって、 （ ）M(m,n)のパーセンテージが与えられた場合のイベントの条件付き確率は、試行を伴う二項分布によって与えられます。私たちはベイジアンな方法で推定しようとしています。group1sns

二項分布の共役事前分布はベータ分布です。したがって、簡単にするために、（0,1）の一様分布でBeta(1,1)ある事前分布として選択します（もちろん、ここでalphaとに対して独自のパラメーターを選択できます）。betaそのため、このベータ分布については、alpha=1およびbeta=1。

二項+ベータ事前分布の再帰的更新式は次のとおりです。

if group == 'group1':
    alpha = alpha + 1
else:
    beta = beta + 1

後部sも実際にはベータ分布です。

                s^(m+alpha-1) (1-s)^(n-m+beta-1)
p(s| M(m,n)) = ----------------------------------- = Beta (m+alpha, n-m+beta)
                      B(m+alpha, n-m+beta)

ベータ関数Bはどこにありますか。推定結果を報告するには、分布の平均と分散を信頼できます。ここで、Beta

mean = alpha/(alpha+beta)
var = alpha*beta/((alpha+beta)**2 * (alpha+beta+1))

Pythonコード：groupby.py

stdinしたがって、データを処理してパーセンテージを推定するPythonの数行は、次のgroup1ようになります。

import sys

alpha = 1.
beta = 1.

for line in sys.stdin:
    data = line.strip()
    if data == 'group1':
        alpha += 1.
    elif data == 'group2':
        beta += 1.
    else:
        continue

    mean = alpha/(alpha+beta)
    var = alpha*beta/((alpha+beta)**2 * (alpha+beta+1))
    print 'mean = %.3f, var = %.3f' % (mean, var)

サンプルデータ

コードに数行のデータをフィードします。

group1
group1
group1
group1
group2
group2
group2
group1
group1
group1
group2
group1
group1
group1
group2

おおよその見積もり結果

そして、これが私が結果として得たものです：

mean = 0.667, var = 0.056
mean = 0.750, var = 0.037
mean = 0.800, var = 0.027
mean = 0.833, var = 0.020
mean = 0.714, var = 0.026
mean = 0.625, var = 0.026
mean = 0.556, var = 0.025
mean = 0.600, var = 0.022
mean = 0.636, var = 0.019
mean = 0.667, var = 0.017
mean = 0.615, var = 0.017
mean = 0.643, var = 0.015
mean = 0.667, var = 0.014
mean = 0.688, var = 0.013
mean = 0.647, var = 0.013

結果は、group1が15行目までに64.7％パーセント処理されると推定されることを示しています（以前のbeta（1,1）に基づく）。観測点が増えるため、分散が縮小し続けることに気付くかもしれません。

複数のグループ

ここで、3つ以上のグループがある場合は、下線分布を二項分布から多項分布に変更するだけで、対応する共役事前分布はディリクレになります。他のすべては、同様の変更を加えるだけです。

その他の注意事項

おおよその見積もりを3〜4秒でお願いします。この場合、データの一部をサンプリングし、出力を上記のスクリプトにフィードするだけです。

head -n100000 YOURDATA.txt | python groupby.py

それでおしまい。それが役に立てば幸い。

于 2012-11-26T23:34:37.183 に答える
3

データがIIDであると想定するのが合理的である場合（したがって、ストリームの特定の部分で特定のタイプのレコードが発生するなどのバイアスがない場合）、サブサンプリングして、おおよそのサイズでカウントをスケールアップします。

最初の100万件のレコードを考えてみましょう（これは数秒で処理できるはずです）。そのサイズはx単位（MB、文字、気になるものは何でも）です。フルストリームのサイズはyで、y >> xです。ここで、サンプルxから気になるもののカウントを導き出し、単純に係数y / * x *でスケーリングして、おおよそのフルカウントを求めます。例：フルストリームで値vの列1を持つレコードの概数を知りたいとします。最初の100万レコードのファイルサイズは100MBですが、合計ファイルサイズは10GBです。最初の100万件のレコードでは、そのうちの150,000件が値vを持っています列1の場合、10 GBのレコード全体で、その値で150,000 *（10,000,000,000 / 100,000,000）=15,000,000と表示されると想定します。サンプルで計算する統計は、同じ係数で単純にスケーリングして推定値を生成できます。

特定のレコードがファイルの特定の場所にある可能性が多かれ少なかれあるようにデータに偏りがある場合は、セット全体からランダムに（または等間隔で）サンプルレコードを選択する必要があります。これにより、偏りのない代表的なサンプルが保証されますが、おそらくはるかに大きなI/Oオーバーヘッドが発生します。

于 2012-11-26T10:16:14.067 に答える