并行计算方差

我正在尝试使用MapReduce在JavaScript中实现variance的并行计算。我相信这个Parallel algorithm可以使用，但我cannott弄清楚如何将它应用于任意数量的数据集。到目前为止，我得出的结论是，解决这个问题的最好方法是根据平方和来进行缩减，而不是根据方差进行。一个天真的实施将看起来像：并行计算方差

// partials is an array of [count, sum, sumsquare] arrays 
function variance(partials) { 
    var count = 0; 
    var sum = 0; 
    var sumsquare = 0; 
    for (var i = 0; i < partials.length; ++i) { 
    count += partials[i][0]; 
    sum += partials[i][1]; 
    sumsquare += partials[i][2]; 
    } 
    return (sumsquare/count) - Math.pow(sum/count, 2); 
} 

// variance([[3, 6, 14], [3, 15, 77], [3, 24, 194]]) should return 6.666666666666668

不是作为一个统计学家，我有一个很难搞清楚这样的并行算法是否会引入太多的复利错误。但如果可以接受，值得注意的是，在map阶段不需要计算方差。只需要平方，总和和计数的总和。

来源

2014-09-28 Ismael Ghalimi

你应该分享你所拥有的，到目前为止，在代码方面。 – pizzasynthesis 2014-09-28 21:37:33

你是对的。在一些白板后，我设法得到了一个天真的执行。不知道它是否会持有水。 – 2014-09-28 22:05:14

有一篇维基百科文章讨论这个问题：https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance – 2014-09-29 19:33:38

我不确定我是否清楚明白的意思reduce函数会为映射到集合的整个数据集的每个子集获得一个四元组阵列，如{方差，sumsquare，sum，count}的工人。不过，根据您的代码剪断我会使用类似：

Array.sums = function (arr, addarr) { 
 
    var newarr = [0,0,0]; 
 
    if (addarr.length === arr.length) { 
 
     arr.forEach(function (v,i) { 
 
     newarr[i] = v + addarr[i]; 
 
     }); 
 
    } 
 
    return newarr; 
 
} 
 
    
 
function variance(arr) { 
 
    var summations = arr[0].map(function() {return 0;}); 
 
    arr.forEach(function (v){ 
 
    summations = Array.sums(v, summations); 
 
    }); 
 
    summations.unshift((summations[2]/summations[0]) - 
 
         Math.pow(summations[1]/summations[0], 2)); 
 
    // summations is now a quadruplet containing [variance, count, sum, sumsquare] 
 
    return summations; 
 
} 
 

 
alert(variance([[3, 6, 14], [3, 15, 77], [3, 24, 194]])[0]);

来源

2014-09-30 07:05:14 KooiInc

据我所知，添加到原始问题的“天真”解决方案就像它得到的一样好，因为它依赖于三个聚合（count，sum和sumsquare）无论如何都需要计算一次通过的方差，而且所要做的就是对单个总计进行求和，单次总计也可能需要单次计算方差。因此，它不会增加任何算术开销。因此，与集中计算相比，它不应该添加任何错误。

来源

2014-09-29 23:46:33

并行计算方差

回答

相关问题