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

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

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

Ответ 1

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

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

Ответ 2

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

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)))

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

Ответ 3

На основе алгоритм Welford:

import numpy as np

class OnlineVariance(object):
    """
    Welford 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())