Алгоритм Уэлфорда

Алгоритм Уэлфорда (также известный как онлайн-алгоритм вычисления дисперсии) — это итеративный метод вычисления среднего арифметического, дисперсии и стандартного отклонения набора данных, который позволяет обрабатывать данные последовательно, без необходимости хранения всей выборки в оперативной памяти. Алгоритм разработан британским статистиком Б. П. Уэлфордом в 1962 году и является частным случаем метода скользящего среднего.

История

До появления алгоритма Уэлфорда для вычисления дисперсии использовались двухпроходные методы: сначала вычислялось среднее арифметическое, затем — сумма квадратов отклонений от этого среднего. Такой подход требовал либо повторного чтения данных, либо их полного хранения в памяти. В 1962 году Б. П. Уэлфорд опубликовал в журнале Technometrics статью, в которой предложил рекуррентные формулы, позволяющие обновлять статистики на каждом шаге поступления нового элемента данных. Алгоритм быстро получил распространение в компьютерной статистике, особенно в системах реального времени и при обработке больших данных (big data), где объём выборки не позволяет загрузить её целиком.

Математическая основа

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

Обозначения

Пусть имеется последовательность чисел \( x_1, x_2, \dots, x_n \). Для каждого шага \( k \) (от 1 до \( n \)) определены:

• \( \bar{x}_k \) — среднее арифметическое первых \( k \) элементов;
• \( M_k \) — сумма квадратов отклонений от текущего среднего: \( M_k = \sum_{i=1}^{k} (x_i - \bar{x}_k)^2 \).

Рекуррентные формулы

Начальные условия (при \( k = 1 \)): \[ \bar{x}_1 = x_1, \quad M_1 = 0. \]

Для каждого следующего элемента \( x_{k+1} \) обновление выполняется в три шага:

1. \( \bar{x}_{k+1} = \bar{x}_k + \frac{x_{k+1} - \bar{x}_k}{k+1} \);
2. \( M_{k+1} = M_k + (x_{k+1} - \bar{x}_k)(x_{k+1} - \bar{x}_{k+1}) \).

После обработки всех \( n \) элементов дисперсия выборки вычисляется как: \[ \sigma^2 = \frac{M_n}{n} \quad \text{(для генеральной совокупности)} \quad \text{или} \quad s^2 = \frac{M_n}{n-1} \quad \text{(для несмещённой оценки дисперсии)}. \]

Стандартное отклонение получается извлечением квадратного корня из соответствующей дисперсии.

Свойства и особенности

Численная устойчивость

Алгоритм Уэлфорда обладает высокой численной устойчивостью по сравнению с наивным методом, который использует формулу \( \sum (x_i^2) - \frac{(\sum x_i)^2}{n} \). Наивный метод подвержен катастрофической потере точности при малых дисперсиях и больших значениях данных, так как вычитание двух близких больших чисел приводит к значительной ошибке округления. Алгоритм Уэлфорда избегает этого, поскольку оперирует непосредственно отклонениями от среднего, которые имеют порядок самой дисперсии.

Вычислительная сложность

Алгоритм требует \( O(n) \) времени и \( O(1) \) дополнительной памяти (не считая места для хранения входных данных, если они не генерируются на лету). На каждом шаге выполняется небольшое количество арифметических операций: два сложения, одно деление, одно умножение и одно вычитание.

Ограничения

• Алгоритм не позволяет удалять ранее добавленные элементы (не поддерживает «скользящее окно» без модификации).
• При очень больших объёмах данных (миллиарды элементов) возможно накопление ошибок округления, хотя на практике они остаются пренебрежимо малыми.
• Для вычисления дисперсии с произвольной точностью (например, с использованием арифметики с плавающей запятой произвольной длины) алгоритм не подходит без дополнительной адаптации.

Применение

Обработка потоковых данных

Алгоритм широко используется в системах, где данные поступают непрерывно (streaming data), например:

• в мониторинге сетевого трафика для вычисления средней загрузки канала и её вариативности;
• в системах управления технологическими процессами для контроля качества продукции;
• в финансовых приложениях для расчёта волатильности цен активов в реальном времени.

Встраиваемые системы и микроконтроллеры

Благодаря минимальным требованиям к памяти и вычислительным ресурсам, алгоритм Уэлфорда применяется в датчиках, измерительных приборах и устройствах Интернета вещей (IoT), где невозможно хранить полную историю измерений.

Научные расчёты

В статистических пакетах и библиотеках (например, NumPy, SciPy, Apache Spark) алгоритм используется как один из базовых методов для вычисления дисперсии в распределённых вычислениях, когда данные разбиты на части, обрабатываемые на разных узлах.

Пример реализации

Ниже приведён пример реализации алгоритма на языке Python, вычисляющий среднее и дисперсию на лету:

```python def welford_update(count, mean, M2, new_value): count += 1 delta = new_value - mean mean += delta / count delta2 = new_value - mean M2 += delta * delta2 return count, mean, M2

def compute_statistics(data): count = 0 mean = 0.0 M2 = 0.0 for x in data: count, mean, M2 = welford_update(count, mean, M2, x) if count < 2: return mean, float('nan') variance = M2 / (count - 1) # несмещённая оценка return mean, variance ```

Вариации и обобщения

Взвешенный алгоритм Уэлфорда

Для случая, когда каждое наблюдение имеет свой вес \( w_i \), разработана взвешенная версия алгоритма, в которой при обновлении учитывается сумма весов вместо количества элементов.

Алгоритм для ковариации и корреляции

Аналогичный рекуррентный подход может быть применён для вычисления ковариации между двумя переменными и коэффициента корреляции Пирсона. Для этого вводятся дополнительные переменные, отслеживающие совместные отклонения.

Параллельная версия

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

Критика

Основной недостаток алгоритма Уэлфорда — его неспособность обрабатывать скользящие окна (например, последние 1000 наблюдений) без полного пересчёта. Для таких задач существуют более сложные алгоритмы, такие как алгоритм скользящего среднего с экспоненциальным затуханием или алгоритмы на основе деревьев (например, алгоритм Чанга-Робертса). Кроме того, при очень малых значениях дисперсии (близких к машинному нулю) алгоритм может давать незначительные погрешности, хотя в большинстве практических приложений они несущественны.

Источники

• Welford, B. P. (1962). "Note on a Method for Calculating Corrected Sums of Squares and Products". Technometrics, 4(3), 419–420.
• Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley. — раздел 4.2.2.
• Higham, N. J. (2002). Accuracy and Stability of Numerical Algorithms (2nd ed.). SIAM. — глава 10.
• Chan, T. F., Golub, G. H., & LeVeque, R. J. (1983). "Algorithms for Computing the Sample Variance: Analysis and Recommendations". The American Statistician, 37(3), 242–247.