实现二阶矩流逼近的 Alon-Matias-Szegedy 算法

Question

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

\n\n

正如乌尔曼书《海量数据集的挖掘》中所述，第二个时刻：

\n\n

\n

是 m_i \xe2\x80\x99s 的平方和。它有时被称为意外数，因为它衡量流中元素分布的不均匀程度。

\n

\n\n

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

\n\n

例如，有这个玩具问题\\数据流：

\n\n

a, b, c, b, d, a, c, d, a, b, d, c, a, a, b\n

\n\n

我们这样计算第二个时刻：

\n\n

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

\n\n

（因为\'a\'在数据流中出现了5次，\'b\'出现了4次，以此类推）

\n\n

由于我们无法将所有数据流存储在内存中，因此我们可以使用一种算法来估计二阶矩：

\n\n

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

\n\n

E(n *(2 * X.value \xe2\x88\x92 1))\n

\n\n

其中 X 是流的单义元素，是随机选择的，X.value 是一个计数器，当我们读取流时，每当我们遇到 x 元素从我们选择它时起的另一个出现时，它就会加 1 。

\n\n

n表示数据流的长度，“E”是平均值。

\n\n

以前面的数据流为例，假设我们在数据流的第 13 个位置选择了“a”，在第 8 个位置选择了“d”，在第 3 个位置选择了“c”。我们还没有选择“b”。

\n\n

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

\n\n

像这样选择，我们有：

\n\n

X.element = "a"   X.value = 2\nX.element = "c"   X.value = 3\nX.element = "d"   X.value = 2\n

\n\n

AMS算法的估计为：

\n\n

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

\n\n

这非常接近之前计算的二阶矩的真实值（59）。

\n\n

现在专注于我的代码，我编写了这个函数来计算“真实”二阶矩，通过向量（一维数组）和 for 模拟数据流：

\n\n

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

\n\n

以及计算二阶矩估计的 AMS 函数：

\n\n

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

\n\n

问题是，当我尝试计算一个小玩具问题（如上面的问题）的自尊时，这些值在某种程度上是正确的，但是当我尝试将向量扩展到 10000 个元素时，这些值是真实的第二时刻和尊重，是截然不同的。

\n\n

我认为问题与我生成数据流的方式以及我决定选择 X.element 的方式有关。

\n\n

那是：

\n\n

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

\n\n

用于生成随机向量\数据流

\n\n

和

\n\n

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

\n\n

对于 X.element 选择（在上面的代码中，在 AMS 函数中完成）

\n\n

对于随机向量\\数据流的生成，认为问题可能是由于向量缺乏“可变性”（string.ascii_letters 只有 52 个元素）。

\n

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)

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