实现用于二阶矩流近似的 Alon-Matias-Szegedy 算法

Question

我正在尝试在 python 中重新创建一个函数来估计数据流的二阶矩。

如乌尔曼书所述，"Mining of Massive Datasets"，第二个时刻：

Is the sum of the squares of the m_i ’s. It is some- times called the surprise number, since it measures how uneven the distribution of elements in the stream is.

其中 m_i 元素是流中的单义元素。

例如，拥有这个玩具problem\data流：

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次，以此类推）

因为我们不能将所有的数据流都存储在内存中，所以我们可以使用一个算法来估计二阶矩：

Alon-Matias-Szegedy 算法（AMS 算法），使用此公式估计二阶矩：

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

其中 X 是流的唯一元素，随机 selected，X.value 是一个计数器，当我们读取流时，每个元素加 1 当我们 select 编辑 x 元素时，我们再次遇到它。

n表示数据流的长度，"E"表示均值

用前面的数据流做一个例子，假设我们在数据流的第 13 个位置 selected "a"，第 8 个 "d" 和 "c" 3日。我们还没有 selected "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）非常接近。

现在专注于我的代码，我编写了这个用于计算 "true" 第二时刻的函数，通过向量（1d 数组）和 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()]))

以及计算二阶矩估计值的 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 个元素时，价值观，真正的第二时刻和尊重，是完全不同的。

我认为问题与我生成数据流的方式以及我决定 select 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 selection（在上面的代码中，在AMS函数中完成）

对于随机vector\data流的生成，一想到问题可能是由于缺少"variability"的向量（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

同时考虑：

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

这缺少除以采样元素的数量。

实现用于二阶矩流近似的 Alon-Matias-Szegedy 算法

Implementing the Alon-Matias-Szegedy Algorithm For The Second Moment Stream Approximation

python

random

data-mining

data-stream

bigdata