Вычисление стандартного отклонения в потоке

Question

Используя Python, предположим, что я пробегаю известное количество элементов I, и у меня есть возможность определить время, необходимое для обработки каждого t, а также общее количество времени, потраченное на обработку T и количество обработанных товаров c.В настоящее время я вычисляю среднее значение на лету A = T / c, но это может быть искажено, скажем, одним элементом, занимающим необычайно много времени для обработки (несколько секунд по сравнению с несколькими миллисекундами).

Я бы хотел показать стандартное отклонение.Как я могу сделать это без учета каждого t?

Answer 1

Как указано в статье Википедии о стандартном отклонении , достаточно отслеживать следующие три суммы:

s0 = sum(1 for x in samples)
s1 = sum(x for x in samples)
s2 = sum(x*x for x in samples)

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

std_dev = math.sqrt((s0 * s2 - s1 * s1)/(s0 * (s0 - 1)))

Обратите внимание, что этот способ вычисления стандартного отклонения может быть численно некорректным, если ваши выборки являются числами с плавающей запятой, а стандартное отклонение мало по сравнению со средним значением выборок. Если вы ожидаете образцы этого типа, вам следует прибегнуть к методу Уэлфорда (см. Принятый ответ).

Answer 2

На основе алгоритма Уэлфорда :

import numpy as np

class OnlineVariance(object):
    """
    Welford's algorithm computes the sample variance incrementally.
    """

    def __init__(self, iterable=None, ddof=1):
        self.ddof, self.n, self.mean, self.M2 = ddof, 0, 0.0, 0.0
        if iterable is not None:
            for datum in iterable:
                self.include(datum)

    def include(self, datum):
        self.n += 1
        self.delta = datum - self.mean
        self.mean += self.delta / self.n
        self.M2 += self.delta * (datum - self.mean)

    @property
    def variance(self):
        return self.M2 / (self.n - self.ddof)

    @property
    def std(self):
        return np.sqrt(self.variance)

Обновлять дисперсию с каждым новым фрагментом данных:

N = 100
data = np.random.random(N)
ov = OnlineVariance(ddof=0)
for d in data:
    ov.include(d)
std = ov.std
print(std)

Сравните наш результат со стандартным отклонением, вычисленным по numpy:

assert np.allclose(std, data.std())

Answer 3

Я использую Метод Уэлфорда , который дает более точные результаты.Эта ссылка указывает на обзор Джона Д. Кука .Вот параграф из этого, который суммирует, почему это предпочтительный подход:

Этот лучший способ вычисления дисперсии восходит к статье 1962 года Б. П. Уэлфорда и представлен в книге «Искусство компьютерного программирования» Дональда Кнута, Vol.2, стр. 232, 3-е издание.Хотя это решение известно на протяжении десятилетий, об этом мало кто знает.Большинство людей, вероятно, не знают, что вычисление выборочной дисперсии может быть затруднено до тех пор, пока они в первый раз не вычислят стандартное отклонение и не получат исключение для получения квадратного корня из отрицательного числа.