В какой-то момент я столкнулся с необходимостью вычислять статистические характеристики очень больших массивов данных. Таких больших, что они не помещаются ни в память, ни на диск одной машины. Тогда-то я и открыл для себя кумулятивные вычисления.
Действительно. Рассчитать, скажем, сумму всех элементов просто: достаточно один раз пройти по всем элементам и накопить сумму в одной переменной. Так же можно рассчитать и количество. Кажется, что и среднее рассчитать не сложно, знаю сумму и количество. (Хотя, на практике, всё не так просто. Сумма огромного количества элементов может оказаться очень большой.)
Но уже со среднеквадратичным отклонением дело обстоит хуже. Если идти классическим путём, то вам придётся перебрать все элементы дважды. Сперва посчитать среднее, а потом (второй проход) сумму квадратов отклонения от среднего.
Это уже делать не хочется. Хочется всё сделать в один проход.
Другая, хотя и похожая, задача возникает, когда вы хотите иметь всегда свежие статистические данные «на данный момент».
Скажем, у вас работает сервер. Для каждого запроса он оценивает время исполнения. Вам хочется иметь информацию о среднем времени и среднеквадратичном отклонении в любой момент. Но вам не хочется (да и возможности у вас такой нет) хранить всю историю запросов и вычислять статистику каждый раз заново.
Все эти задачи решаются кумулятивными методами вычисления статистических величин.
Сразу покажу код:
#!/usr/bin/python
# coding: utf-8
import math
class CumulativeMovingAverage:
'''
CMA(n-1) = (a(1) + ... + a(n-1))/(n-1)
CMA(n) = (a(1) + ... + a(n-1) + a(n))/(n-1) * (n-1)/n =
= (CMA(n-1) + a(n)/(n-1)) * (n-1)/n =
= ( a(n) + (n-1) * CMA(n-1) ) / n
'''
def __init__(self):
self.cma = 0.0
self.n = 0
def update(self, v):
self.cma = (v + self.n * self.cma) / (self.n + 1)
self.n += 1
def average(self):
if self.n == 0:
raise ValueError('No data')
return self.cma
def len(self):
return self.n
class CumulativeMovingStandardDeviation:
'''
X — set of data
E[X] = μ — average or expected value
σ² = E[(X-μ)²] = E[X²]-2μE[X]+μ² = E[X²]-μ²
Uncorrected sample standard deviation = √(σ²)
Corrected sample standard deviation = √((N/(N-1))σ²) = √(N/(N-1) √(σ²)
'''
def __init__(self):
self.cma = CumulativeMovingAverage()
self.cma2 = CumulativeMovingAverage() # mean of squares
def update(self, v):
self.cma.update(v)
self.cma2.update(v * v)
def average(self):
return self.cma.average()
def len(self):
return self.cma.len()
def std_deviation_square(self):
m = self.average()
return self.cma2.average() - m * m
def std_deviation(self):
return math.sqrt(self.std_deviation_square())
def corrected_std_deviation(self):
n = self.len()
if n < 2:
raise ValueError('Not enough data')
return self.std_deviation() * math.sqrt(float(n)/(n - 1))
a = CumulativeMovingStandardDeviation()
for x in range(0, 5):
a.update(x)
for x in range(4, -1, -1):
a.update(x)
print a.average() # 2.0
print a.std_deviation() # 1.41421356237 (√2)
print a.corrected_std_deviation() # 1.490711985 (√(20/9))
Тут два класса, объекты которых имеют схожий интерфейс.
CumulativeMovingAverage — для расчёта среднего,
CumulativeMovingStandardDeviation — для расчёта разных типов
среднеквадратичного отклонения.
Объект каждого класса не хранит всю последовательность, а лишь накапливает информацию о ней. Новые члены случайной последовательности поступают в методы update каждого из классов.
Тут всё понятно из комментария. Формула тоже однозначно читается в методе CumulativeMovingAverage.update()
Обратите внимание, что мы не считаем сумму, а сразу накапливаем среднее.
Мне кажется, что в комментарии достаточно информации. Имея класс, вычисляющий среднее, вычислить среднеквадратичное не трудно.
Наш класс умеет рассчитывать стандартное отклонение и скорректированное стандартное отклонение. Так называемую, несмещённую дисперсию.
Точность. При добавлении каждого элемента выполняется целый ряд операций с плавающей точкой. Каждая из них немного крадёт точность. На больших объёмах данных это может стать очень заметным.
Тут вы можете воспользоваться знанием о природе ваших данных и переписать код так, что все вычисления были целочисленными.
Для этого достаточно изменить только класс, подсчитывающий среднее.
Например, вы можете знать, что вам предстоит работать с деньгами. А сумма всех денег не может превысить бюджет вашей организации. Примерно представляя бюджет, вы можете с определённостью решить, что сумма всех элементов не выйдет за пределы определённой величины. Тогда можно будет без опасений перевести класс CumulativeMovingAverage на метод «всё просуммировать, а потом поделить». При этом вы полностью избавитесь от потерь точности при накоплении новых данных.