1

我在 mongodb 中有一组文档,我想计算某些属性的 CDF 并将其返回或存储在数据库中。显然,为每个文档添加一个新属性并不是一个好方法,我可以使用以后可以使用的近似值。这更像是一个理论问题。

因此,我使用 mapreduce 作业计算离散间隔上的 CDF 采样,如下所示(只是算法):

  1. 获取count,minmax属性someAttr
  2. 假设min = 5, max=70, count = 200.
  3. map()for (i=this.someAttr; i < max+1; i++) { emit(i, 1) }
  4. reduce()只需返回每个键的总和。
  5. finalize()中,将减少的输出除以记录数:return val / count

但是,这确实会输出包含来自 CDF 的样本的集合。

正如您所看到的,这里的间隔步骤是1,但是这种方法的巨大效率低下是即使从单个文档中也可能会产生大量的发射,即使集合中只有少数文档,因此这显然是不可扩展的,并且不管用。

输出如下所示:

{ _id: 5, val: 0}
{ _id: 6, val: 0.04}
{ _id: 7, val: 0.04}
...
{ _id: 71, val: 1.0}

从这里我可以很容易地得到任何值的 CDF 的近似值,如果这是合理的,甚至可以在它们之间进行插值。

有人可以让我深入了解您将如何使用 MapReduce(或者可能没有 MapReduce)计算 CDF(样本)吗?

4

1 回答 1

1

F_a根据定义,属性的累积分布函数a定义为

F_a(x) = # documents with attribute value <= x / # of documents

所以你可以计算CDF

F_a(x) = db.collection.count({ "a" : { "lte" : x }) / db.collection.count({ "a" : { "$exists" : true } })

分母中的计数假设您不想计算缺少该a字段的文档。一个索引a将使这更快。

您可以使用它来计算 cdf 的样本或仅按需计算 cdf。不需要map-reduce。

于 2014-11-25T02:33:09.630 回答