方差的并行计算

Question

我正在尝试使用MapReduce在JavaScript中实现方差的并行计算。我相信这种并行算法是可以使用的，但我不知道如何将其应用于任意数量的数据集。到目前为止，我得出的结论是，解决这个问题的最好方法是根据平方和进行约简，而不是根据方差进行约简。一个天真的实现看起来是这样的：

// 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阶段期间不需要计算方差。只需要平方和、和和和计数。

Answer 1

我不确定我是否清楚地理解你所说的的意思。reduce函数将为映射到一组worker上的整个数据集的每个子集获得一个四元组数组，如{variance，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] );

Answer 2

据我所知，添加到原始问题中的"天真"解决方案是最好的，因为它依赖于三个聚合（count、sum和sumsquare），而这三个聚合无论如何都需要在一次遍历中计算方差，它所做的只是对单个聚合求和，这对于方差的单程计算也是需要的。因此，它不会增加任何算术开销。因此，与集中计算相比，它不应该增加任何错误。