5

データ ストリームの 2 次モーメントを推定するために、Python で関数を再作成しようとしています。

ウルマン・ブック「大規模なデータセットのマイニング」で述べられているように、2 番目の瞬間:

m_i の平方和です。これは、ストリーム内の要素の分布がどの程度不均一であるかを測定するため、サプライズ ナンバーと呼ばれることもあります。

m_i 要素は、ストリーム内の一義的な要素です。

たとえば、このおもちゃの問題\データ ストリームがあるとします。

a, b, c, b, d, a, c, d, a, b, d, c, a, a, b

次のように 2 番目のモーメントを計算します。

5^2 + 4^2 + 3^2 + 3^2 = 59

('a' はデータ ストリームで 5 回、'b' は 4 回など)

すべてのデータ ストリームをメモリに格納することはできないため、次のアルゴリズムを使用して 2 次モーメントを推定できます。

次の式を使用して 2 次モーメントを推定するAlon-Matias-Szegedy アルゴリズム (AMS アルゴリズム) :

E(n *(2 * X.value − 1))

ここで、X はランダムに選択されたストリームの一義的な要素であり、X.value はカウンターであり、ストリームを読み取るときに、選択した時点から x 要素の別の発生に遭遇するたびに 1 に加算されます。

n はデータ ストリームの長さを表し、「E」は平均表記です。

前のデータ ストリームの例で、データ ストリームの 13 番目の位置で "a"、8 番目で "d"、3 番目で "c" を選択したとします。「b」は選択していません。

a, b, c, b, d, a, c, d, a, b, d, c, a, a, b
1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
      x              x              x

このように選択すると、次のようになります。

X.element = "a"   X.value = 2
X.element = "c"   X.value = 3
X.element = "d"   X.value = 2

AMS アルゴリズムによる推定値は次のとおりです。

(15*(2 * 2 - 1) + 15*(2 * 3 - 1) + 15*(2 * 2 - 1))/3 = 55

これは、以前に計算された 2 番目のモーメントの真の値 (59) にかなり近いものです。

ここでコードに注目して、「真の」2 番目のモーメントを計算するためにこの関数を作成し、vector(1d array) と for によってデータ ストリームをシミュレートします。

def secondMoment(vector):
    mydict = dict()
    for el in vector:
        if el not in mydict:
            mydict[el] = 1
        else:
            mydict[el] += 1
    return (sum([pow(value, 2) for key, value in mydict.items()]))

および 2 次モーメントの推定値を計算する AMS 関数:

def AMSestimate(vector):
    lenvect = len(vector)
    elements = dict()
    for el in vector:
        if el in elements:
            elements[el] += 1
        elif random.choice(range(0, 10)) == 0:
            elements[el] = 1
    # E(n * (2 * x.value - 1))
    lendict = len(elements)
    estimateM2 = 0
    for key, value in elements.items():
        estimateM2 += lenvect * ((2 * value) - 1)
    print(lendict)
    if lendict > 0:
        return estimateM2/lendict

問題は、小さなおもちゃの問題 (上記のようなもの) の評価を計算しようとすると、値がある程度正しいことですが、ベクトルをたとえば 10000 要素に拡張しようとすると、値が真の Second Moment になります。と自尊心はかなり異なります。

問題は、データストリームを生成する方法と、X.element を選択する方法に関連していると思います。

あれは：

[random.choice(string.ascii_letters) for x in range(size)]

ランダム vector\data ストリームの生成用

と

elif random.choice(range(0, 10)) == 0:
    elements[el] = 1

X.element の選択 (上記のコードの AMS 関数で実行)

ランダムな vector\data ストリームの生成について、ベクトルの「可変性」の欠如が問題の原因である可能性があると考えられました (string.ascii_letters は 52 要素しか取得しませんでした)。

4

1 に答える 1