计算标准差的在线算法

Question

通常情况下，我有一个更技术性的问题，但是我会用一个计数球的例子来简化它。

假设我有不同颜色的球，并为每种颜色保留一个数组索引(初始化为所有0)。每次我选一个球，我就把相应的指数增加1。

球是随机挑选的，我一次只能选一个球。我唯一的目的是计算每种颜色的球数，直到我用完球为止。

我想计算不同颜色的球数的标准差，而我正在计算它们。我不想在计算完所有的球之后，再通过迭代数组来计算它。

想象：

按随机顺序排列的球：BBGRRYYBBGGGGGGB (每个字母代表颜色的第一个字母)数组索引从0到3分别对应于颜色B、G、R和Y。当我摘完球后，我的数组看起来就像[5,7,2,2]。

这是非常简单的计算标准偏差后，有最后的数组，但我想做它，当我填充这个数组。

我想用Java来做，我有大约1000种颜色。

实现这一目标的最有效方式是什么？或者，在最后的数组到手之前，还有什么方法可以做到吗？

Answer 1

由于平均偏差和标准差是使用和计算的，因此可以很容易地实现适当的累加器。然后，当您想要实际值时，完成其余的计算(特别是除法)。

平方和是一个棘手的部分，因为你增加了每个输入的一个频率。处理此问题的一种方法是保持到目前为止所看到的每种颜色的计数(使用适当的数据结构)。然后，当您在输入中看到一个颜色时，您可以减去它的前一个正方形，并将新的正方形加回(或等效地将这两个方格的差添加到累加器中)。

我将留给读者来实现这里描述的算法。

Answer 2

您不需要数组来计算标准偏差。

只需跟踪点数，总和，和平方的总和。您可以在任何时候计算平均值和标准差，而不必保留数组。

如果我理解您的需求，您将需要一个地图，其中颜色是关键，而统计实例是值。

这节课是为你做的。

package statistics;

/**
 * Statistics
 * @author Michael
 * @link http://stackoverflow.com/questions/11978667/online-algorithm-for-calculating-standrd-deviation/11978689#11978689
 * @since 8/15/12 7:34 PM
 */
public class Statistics {

    private int n;
    private double sum;
    private double sumsq;

    public void reset() {
        this.n = 0;
        this.sum = 0.0;
        this.sumsq = 0.0;
    }

    public synchronized void addValue(double x) {
        ++this.n;
        this.sum += x;
        this.sumsq += x*x;
    }

    public synchronized double calculateMean() {
        double mean = 0.0;
        if (this.n > 0) {
            mean = this.sum/this.n;
        }
        return mean;
    }

    public synchronized double calculateVariance() {
       double deviation = calculateStandardDeviation();
        return deviation*deviation;
    }

    public synchronized double calculateStandardDeviation() {
        double deviation = 0.0;
        if (this.n > 1) {
            deviation = Math.sqrt((this.sumsq - this.sum*this.sum/this.n)/(this.n-1));
        }
        return deviation;
    }
}

下面是它的单元测试：

package statistics;

import org.junit.Assert;
import org.junit.Test;

/**
 * StatisticsTest
 * @author Michael
 * @link http://www.wolframalpha.com/input/?i=variance%281%2C+2%2C+3%2C+4%2C+5%2C+6%29&a=*C.variance-_*Variance-
 * @since 8/15/12 7:42 PM
 */
public class StatisticsTest {

    private static final double TOLERANCE = 1.0E-9;

    @Test
    public void testCalculateMean() {
        double [] values = new double[] {
            1.0, 2.0, 3.0, 4.0, 5.0, 6.0
        };
        Statistics stats = new Statistics();
        for (double value : values) {
            stats.addValue(value);
        }
        double expected = 3.5;
        Assert.assertEquals(expected, stats.calculateMean(), TOLERANCE);
    }

    @Test
    public void testCalculateVariance() {
        double [] values = new double[] {
                1.0, 2.0, 3.0, 4.0, 5.0, 6.0
        };
        Statistics stats = new Statistics();
        for (double value : values) {
            stats.addValue(value);
        }
        double expected = 3.5;
        Assert.assertEquals(expected, stats.calculateVariance(), TOLERANCE);
    }


    @Test
    public void testCalculateStandardDeviation() {
        double [] values = new double[] {
                1.0, 2.0, 3.0, 4.0, 5.0, 6.0
        };
        Statistics stats = new Statistics();
        for (double value : values) {
            stats.addValue(value);
        }
        double expected = Math.sqrt(3.5);
        Assert.assertEquals(expected, stats.calculateStandardDeviation(), TOLERANCE);
    }

}