我正在尝试在 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 个元素)。