Как эффективно рассчитать текущее стандартное отклонение?


у меня есть массив списков цифр, например:

[0] (0.01, 0.01, 0.02, 0.04, 0.03)
[1] (0.00, 0.02, 0.02, 0.03, 0.02)
[2] (0.01, 0.02, 0.02, 0.03, 0.02)
     ...
[n] (0.01, 0.00, 0.01, 0.05, 0.03)

что я хотел бы сделать, это эффективно вычислить среднее и стандартное отклонение по каждому индексу списка, по всем элементам массива.

чтобы сделать среднее, я перебирал массив и суммировал значение по заданному индексу списка. В конце концов, я делю каждое значение в моем "среднем списке" на n.

чтобы сделать стандартное отклонение, я повторяю цикл снова, теперь, когда у меня есть среднее значение рассчитанный.

Я хотел бы избежать прохождения массива дважды, один раз для среднего, а затем один раз для SD (после того, как у меня есть среднее).

есть ли эффективный метод для вычисления обоих значений, только проходя через массив один раз? Любой код на интерпретируемом языке (например, Perl или Python) или псевдокод прекрасен.

14 72

14 ответов:

ответ заключается в использовании алгоритма Уэлфорда, который очень четко определен после "наивных методов" в:

это более численно устойчиво, чем либо двухпроходные или онлайн простая сумма квадратов коллекторов, предложенных в других ответах. Стабильность имеет значение только тогда, когда у вас есть много значений, которые близки друг к другу, поскольку они приводят к тому, что известно как "катастрофические отмены " в литературе с плавающей точкой.

вы также можете освежить разницу между делением на количество выборок (N) и N-1 в вычислении дисперсии (квадратное отклонение). Деление на N-1 приводит к несмещенной оценке дисперсии из выборки, тогда как деление на N в среднем недооценивает дисперсию (потому что оно не учитывает дисперсию между средним значением выборки и истинным средним).

I написал две записи в блоге на эту тему, которые идут в более подробную информацию, в том числе как удалить предыдущие значения в интернете:

вы также можете взглянуть на мою реализацию Java; javadoc, исходный код и модульные тесты все онлайн:

основной ответ состоит в том, чтобы накопить сумму обоих x (назовем его 'sum_x1') и x2 (назовите его "sum_x2"), как вы идете. Значение стандартного отклонения тогда:

stdev = sqrt((sum_x2 / n) - (mean * mean)) 

здесь

mean = sum_x / n

это стандартное отклонение выборки; вы получаете стандартное отклонение популяции, используя 'n' вместо 'n - 1' в качестве делителя.

возможно, Вам придется беспокоиться о численной устойчивости, принимая разницу между двумя большими числами, если вы имеете дело с большими выборками. Перейдите к внешним ссылкам в других ответах (Wikipedia и т. д.) Для получения дополнительной информации.

возможно, не то, что вы спрашивали, но ... Если вы используете массив NumPy, он будет делать работу за вас, качественно:

from numpy import array

nums = array(((0.01, 0.01, 0.02, 0.04, 0.03),
              (0.00, 0.02, 0.02, 0.03, 0.02),
              (0.01, 0.02, 0.02, 0.03, 0.02),
              (0.01, 0.00, 0.01, 0.05, 0.03)))

print nums.std(axis=1)
# [ 0.0116619   0.00979796  0.00632456  0.01788854]

print nums.mean(axis=1)
# [ 0.022  0.018  0.02   0.02 ]

кстати, в этом блоге есть интересная дискуссия и комментарии к однопроходным методам вычислительных средств и дисперсий:

вот буквальный чистый перевод Python реализации алгоритма Уэлфорда из http://www.johndcook.com/standard_deviation.html:

https://github.com/liyanage/python-modules/blob/master/running_stats.py

class RunningStats:

    def __init__(self):
        self.n = 0
        self.old_m = 0
        self.new_m = 0
        self.old_s = 0
        self.new_s = 0

    def clear(self):
        self.n = 0

    def push(self, x):
        self.n += 1

        if self.n == 1:
            self.old_m = self.new_m = x
            self.old_s = 0
        else:
            self.new_m = self.old_m + (x - self.old_m) / self.n
            self.new_s = self.old_s + (x - self.old_m) * (x - self.new_m)

            self.old_m = self.new_m
            self.old_s = self.new_s

    def mean(self):
        return self.new_m if self.n else 0.0

    def variance(self):
        return self.new_s / (self.n - 1) if self.n > 1 else 0.0

    def standard_deviation(self):
        return math.sqrt(self.variance())

использование:

rs = RunningStats()
rs.push(17.0);
rs.push(19.0);
rs.push(24.0);

mean = rs.mean();
variance = rs.variance();
stdev = rs.standard_deviation();

The Python runstats Module для этих целей. установить runstats от PyPI:

pip install runstats

сводки Runstats могут создавать среднее, дисперсию, стандартное отклонение, асимметрию и эксцесс за один проход данных. Мы можем использовать это для создания вашей "запущенной" версии.

from runstats import Statistics

stats = [Statistics() for num in range(len(data[0]))]

for row in data:

    for index, val in enumerate(row):
        stats[index].push(val)

    for index, stat in enumerate(stats):
        print 'Index', index, 'mean:', stat.mean()
        print 'Index', index, 'standard deviation:', stat.stddev()

статистические сводки основаны на методе кнута и Уэлфорда для вычисления стандартного отклонения за один проход, как описано в технике компьютера Программирования, Том 2, стр. 232, 3-е издание. Преимуществом этого является численно стабильные и точные результаты.

отказ от ответственности: я автор модуля Python runstats.

посмотреть PDL (произносится " piddle!").

это язык данных Perl, который предназначен для высокоточной математики и научных вычислений.

вот пример использования ваших цифр....

use strict;
use warnings;
use PDL;

my $figs = pdl [
    [0.01, 0.01, 0.02, 0.04, 0.03],
    [0.00, 0.02, 0.02, 0.03, 0.02],
    [0.01, 0.02, 0.02, 0.03, 0.02],
    [0.01, 0.00, 0.01, 0.05, 0.03],
];

my ( $mean, $prms, $median, $min, $max, $adev, $rms ) = statsover( $figs );

say "Mean scores:     ", $mean;
say "Std dev? (adev): ", $adev;
say "Std dev? (prms): ", $prms;
say "Std dev? (rms):  ", $rms;


Который производит:

Mean scores:     [0.022 0.018 0.02 0.02]
Std dev? (adev): [0.0104 0.0072 0.004 0.016]
Std dev? (prms): [0.013038405 0.010954451 0.0070710678 0.02]
Std dev? (rms):  [0.011661904 0.009797959 0.0063245553 0.017888544]


Взгляните на PDL:: Primitive подробнее о statsover

Статистика::Начертательная это очень приличный модуль Perl для таких типов вычислений:

#!/usr/bin/perl

use strict; use warnings;

use Statistics::Descriptive qw( :all );

my $data = [
    [ 0.01, 0.01, 0.02, 0.04, 0.03 ],
    [ 0.00, 0.02, 0.02, 0.03, 0.02 ],
    [ 0.01, 0.02, 0.02, 0.03, 0.02 ],
    [ 0.01, 0.00, 0.01, 0.05, 0.03 ],
];

my $stat = Statistics::Descriptive::Full->new;
# You also have the option of using sparse data structures

for my $ref ( @$data ) {
    $stat->add_data( @$ref );
    printf "Running mean: %f\n", $stat->mean;
    printf "Running stdev: %f\n", $stat->standard_deviation;
}
__END__

выход:

C:\Temp> g
Running mean: 0.022000
Running stdev: 0.013038
Running mean: 0.020000
Running stdev: 0.011547
Running mean: 0.020000
Running stdev: 0.010000
Running mean: 0.020000
Running stdev: 0.012566

насколько велик ваш массив? Если это не миллионы элементов длиной, не беспокойтесь о циклическом прохождении через него дважды. Код прост и легко тестируется.

мое предпочтение было бы использовать включает в себя расширение Array maths для преобразования вашего массива массивов в массив NumPy 2D и получения стандартного отклонения напрямую:

>>> x = [ [ 1, 2, 4, 3, 4, 5 ], [ 3, 4, 5, 6, 7, 8 ] ] * 10
>>> import numpy
>>> a = numpy.array(x)
>>> a.std(axis=0) 
array([ 1. ,  1. ,  0.5,  1.5,  1.5,  1.5])
>>> a.mean(axis=0)
array([ 2. ,  3. ,  4.5,  4.5,  5.5,  6.5])

если это не вариант, и вам нужно чистое решение Python, продолжайте читать...

если Ваш массив

x = [ 
      [ 1, 2, 4, 3, 4, 5 ],
      [ 3, 4, 5, 6, 7, 8 ],
      ....
]

тогда стандартное отклонение:

d = len(x[0])
n = len(x)
sum_x = [ sum(v[i] for v in x) for i in range(d) ]
sum_x2 = [ sum(v[i]**2 for v in x) for i in range(d) ]
std_dev = [ sqrt((sx2 - sx**2)/N)  for sx, sx2 in zip(sum_x, sum_x2) ]

если вы решили перебирать массив только один раз, текущие суммы могут быть объединены.

sum_x  = [ 0 ] * d
sum_x2 = [ 0 ] * d
for v in x:
   for i, t in enumerate(v):
   sum_x[i] += t
   sum_x2[i] += t**2

это не так элегантно, как решение для понимания списка выше.

Я думаю, этот вопрос поможет вам. стандартное отклонение

вы можете посмотреть статью в Википедии на Стандартное Отклонение, в частности раздел о методах быстрого расчета.

есть также статья, которую я нашел, которая использует Python, вы должны быть в состоянии использовать код в нем без особых изменений:Подсознательные Сообщения-Запуск Стандартных Отклонений.

n=int(raw_input("Enter no. of terms:"))

L=[]

for i in range (1,n+1):

    x=float(raw_input("Enter term:"))

    L.append(x)

sum=0

for i in range(n):

    sum=sum+L[i]

avg=sum/n

sumdev=0

for j in range(n):

    sumdev=sumdev+(L[j]-avg)**2

dev=(sumdev/n)**0.5

print "Standard deviation is", dev

Как описано в следующем ответе: обеспечивает ли pandas/scipy / numpy кумулятивную функцию стандартного отклонения? Модуль Python Pandas содержит метод для расчета выполнения или совокупное стандартное отклонение. Для этого вам нужно будет преобразовать ваши данные в фрейм данных pandas (или серию, если это 1D), но для этого есть функции.

вот "однострочный", разбросанный по нескольким строкам, в стиле функционального программирования:

def variance(data, opt=0):
    return (lambda (m2, i, _): m2 / (opt + i - 1))(
        reduce(
            lambda (m2, i, avg), x:
            (
                m2 + (x - avg) ** 2 * i / (i + 1),
                i + 1,
                avg + (x - avg) / (i + 1)
            ),
            data,
            (0, 0, 0)))

Я хотел бы выразить обновление таким образом:

def running_update(x, N, mu, var):
    '''
        @arg x: the current data sample
        @arg N : the number of previous samples
        @arg mu: the mean of the previous samples
        @arg var : the variance over the previous samples
        @retval (N+1, mu', var') -- updated mean, variance and count
    '''
    N = N + 1
    rho = 1.0/N
    d = x - mu
    mu += rho*d
    var += rho*((1-rho)*d**2 - var)
    return (N, mu, var)

чтобы однопроходная функция выглядела так:

def one_pass(data):
    N = 0
    mu = 0.0
    var = 0.0
    for x in data:
        N = N + 1
        rho = 1.0/N
        d = x - mu
        mu += rho*d
        var += rho*((1-rho)*d**2 - var)
        # could yield here if you want partial results
   return (N, mu, var)

обратите внимание, что это вычисление выборочной дисперсии (1/N), а не несмещенной оценки дисперсии популяции (которая использует 1/(N-1) коэффициент нормализации). В отличие от других ответов, переменная, var, то есть отслеживание текущей дисперсии не растет пропорционально количеству выборок. Во все времена это просто дисперсия множества образцов, увиденных до сих пор (нет окончательного "деления на n" при получении дисперсии).

в классе это будет выглядеть так:

class RunningMeanVar(object):
    def __init__(self):
        self.N = 0
        self.mu = 0.0
        self.var = 0.0
    def push(self, x):
        self.N = self.N + 1
        rho = 1.0/N
        d = x-self.mu
        self.mu += rho*d
        self.var += + rho*((1-rho)*d**2-self.var)
    # reset, accessors etc. can be setup as you see fit

Это также работает для взвешенных образцов:

def running_update(w, x, N, mu, var):
    '''
        @arg w: the weight of the current sample
        @arg x: the current data sample
        @arg mu: the mean of the previous N sample
        @arg var : the variance over the previous N samples
        @arg N : the number of previous samples
        @retval (N+w, mu', var') -- updated mean, variance and count
    '''
    N = N + w
    rho = w/N
    d = x - mu
    mu += rho*d
    var += rho*((1-rho)*d**2 - var)
    return (N, mu, var)