並行計算方差

我正在嘗試使用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

並行計算方差

回答

相關問題