5

我正在尝试在 python 中重新创建一个函数,以估计数据流的第二时刻。

正如 Ullman 的书“海量数据集的挖掘”所述,第二个时刻:

是 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 次,依此类推)

因为我们无法将所有数据流存储在内存中,所以我们可以使用一种算法来估计二阶矩:

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 

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

现在专注于我的代码,我已经编写了这个函数来计算“真实”第二时刻,通过向量(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 个元素时,这些值是真的 Second Moment和尊重,是完全不同的。

我认为问题与我生成数据流的方式以及我决定选择 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 函数中完成)

对于随机向量\数据流的生成,一个想法可能是由于向量缺乏“可变性”(string.ascii_letters 只得到了 52 个元素)。

4

1 回答 1

3

这是个有趣的问题。

说我们从

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)

这没有除以采样元素的数量。

于 2016-03-20T15:20:13.283 回答