Онлайн алгоритм для расчета стандартного отклонения

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://stackru.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);
    }

}