在线计算标准差的算法

Question

在线计算标准差的算法

javaalgorithmstatisticsstandard-deviationonline-algorithm

3

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

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

球是随机选择的，我只能一次选一个球。我的唯一目的是计算每种颜色的球的数量，直到我用完所有的球。

我想在统计它们时计算不同颜色的球的数量的标准差，而不是在完成计数所有球之后再迭代一次数组来计算它。

为了可视化：

随机顺序的球：BBGRRYYBBGGGGGGB（每个字母代表一种颜色的第一个字母）从0到3的数组索引对应于颜色B、G、R和Y。当我选完球后，我的数组看起来像[5,7,2,2]。

在填充这个数组时计算标准差非常简单，但我想在填充这个数组时计算它。

我想用Java实现它，大约有1000种颜色。

最有效的实现方式是什么？或者在手头拿到最终的数组之前，是否有一种方法可以做到这一点？

- Erol

1

这被称为一个 https://en.wikipedia.org/wiki/Online_algorithm。 - Mechanical snail

我不太明白标准差在颜色方面的含义。绿色比红色离蓝色更远吗？ - meriton

意思不重要，我只是举个例子来简化我的情况。 - Erol

2

@meriton 我相信 OP 的意思是每种颜色的频率的标准差。 - Code-Apprentice

没错，我正在计算每种颜色的球数。 - Erol

2个回答

1

由于平均值和标准差是使用总和计算的，因此您可以轻松地为这些实现适当的累加器。然后，当您想要实际值时，完成其余的计算（特别是除法）。

平方和是棘手的部分，因为您会为每个输入增加一个频率。处理这种情况的一种方法是使用适当的数据结构维护到目前为止看到的每种颜色的计数。然后，当您在输入中看到一种颜色时，您可以减去其先前的平方并将新的平方加回去（或等效地将两个平方的差异添加到累加器中）。

我将让读者实现此处描述的算法。

- Code-Apprentice

"减去先前的平方，再加上新的平方。所以你可以这样做：-=n*n; += (n+1)*(n+1)。这有点低效，你可以用+= 2*n+1代替。" - MSalters

@MSalters 请阅读：“或等价于...” - Code-Apprentice

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- duffymo · Accepted Answer

计算标准差不需要数组。

只需跟踪点数、总和和平方总和即可在任何时候计算平均值和标准差，无需保留数组。

如果我理解您的要求正确，您将需要一个Map，其中颜色是键，Statistics的实例是值。

这是一个为您完成此操作的类。

package statistics;

/**
 * Statistics
 * @author Michael
 * @link https://dev59.com/0WfWa4cB1Zd3GeqPf1PW#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);
    }

}