實施第二次矩流近似的Alon-Matias-Szegedy算法

Question

我試圖在數據流的第二個時刻估計的python中重新創建一個函數。

如前所述由烏爾曼書，第二個瞬間「大規模數據集的挖掘」：

是對M_I的平方的總和。由於它測量流中元素的分佈有多不均勻，因此它被稱爲驚喜數。

其中m_i元素是流中的唯一元素。

例如，具有這種玩具問題\數據流：

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

我們計算所述第二時刻是這樣的：

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

（因爲 'A' 出現在數據流中的5倍， 'b'4次，依此類推）

因爲我們無法在內存中存儲所有的數據流，所以我們可以使用一個算法來估計第二時刻：

的阿龍-的Matias-Szegedy算法（AMS算法），使用這種配方，估計所述第二時刻：

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

在其中X是流的單義元件，randomically選擇，和X.值是一個計數器，當我們讀取數據流時，每增加一個，我們就會在我們選擇它的時候再次出現x元素。

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 

這是非常接近之前計算的第二時刻的真實價值（ 59）。

現在着眼於我的代碼，我寫了這個功能爲「真」二階矩的計算，模擬由矢量（1D陣列）中的數據流和用於：

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()])) 

和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個元素，其值爲true第二刻和尊重，是非常不同的。

我認爲問題與我生成數據流的方式以及我決定選擇X.element的方式有關。

即：

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

對於隨機矢量\數據流

而且

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

對於X.element選擇（在上面的代碼完成的生成，在AMS功能）

對於生成隨機向量\數據流，認爲th問題可能是由於缺乏矢量的「可變性」（string.ascii_letters只有52個元素）。

Answer 1

這是一個有趣的問題。

說我們先從

import random 
import string 

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

然後第一個實現與你相似（請注意使用的collections.Counter，雖然）：

from collections import Counter 

def secondMoment(seq): 
    c = Counter(seq) 
    return sum(v**2 for v in c.values()) 

>>> secondMoment(seq) 
192436972 

第二種方案比你的不同更顯著，雖然。請注意，首先找到隨機索引。

from collections import defaultdict 

def AMSestimate(seq, num_samples=10): 
    inds = list(range(len(seq))) 
    random.shuffle(inds) 
    inds = sorted(inds[: num_samples]) 

    d = {} 
    for i, c in enumerate(seq): 
     if i in inds and c not in d: 
      d[c] = 0 
     if c in d: 
      d[c] += 1 
    return int(len(seq)/float(len(d)) * sum((2 * v - 1) for v in d.values())) 

>>> AMSestimate(seq) 
171020000 

---

編輯關於原始代碼在問題

在代碼中：然後，一個元件被僅在其第一次出現之後的索引中的一個計數（如果有的話）問題，考慮你的循環

for el in vector: 
    if el in elements: 
     elements[el] += 1 
    elif random.choice(range(0, 10)) == 0: 
     elements[el] = 1 

（未成年人）的取樣是有問題的：它是在0.1

01硬編碼的概率

還認爲：

estimateM2 += lenvect * ((2 * value) - 1) 

這通過取樣元件的數量缺乏一個部門。