Алгоритм Уэлфорда (ru)
10-09-2025
Представьте, что к вам потоком поступают данные: миллионы транзакций, цены акций, показания датчиков. Вам нужно вычислить среднее значение, дисперсию и корреляции. Классический способ — сохранить все данные и затем вычислить. Но это занимает много памяти, вычисления становятся тяжелыми, на больших числах возникают ошибки округления. Недавно я столкнулся с алгоритмом Уэлфорда, который позволяет проводить онлайн-вычисления за одну итерацию без сохранения больших данных. Это очень элегантный, стабильный и точный алгоритм.
Постановка задачи довольно проста: мы хотим вычислять статистики (среднее, дисперсию, ковариацию, корреляцию) шаг за шагом, когда мы получаем \(n\) данных в потоке, без сохранения всех данных и дополнительных итераций. Напомним формулы базовым способом. Среднее:
Дисперсия:
Как видите, для среднего нужна сумма: первая проблема — как получить сумму без всех чисел? А для дисперсии нужно среднее: вторая проблема — как узнать среднее без всех данных?
# Интуиция метода
Попробуем прочувствовать интуицию метода Уэлфорда. Представьте, у нас есть набор данных: \(A = \{1, 2, 3\}\), среднее этого набора \(\overline{x}_A = \frac{1 + 2 +3}{3} = 2\), и затем мы получили еще одно число: \(6\). Чувствуете, что оно сдвинет наше среднее в сторону больших значений? Но насколько? Представьте похожий набор, но с большим количеством данных: \(B = \{1, 1, 2, 2, 3, 3\}\), среднее также равно \(2\), и мы также добавляем число \(6\). Снова чувствуем, что сдвиг будет в сторону больших значений, но не такой сильный. Проверим нашу интуицию:
Наша интуиция была права! Осталось понять, как мы можем вычислить эту дельту, если у нас есть только предыдущее среднее \(\overline{x}_{i - 1}\), новое число \(x_i\) и количество наших чисел. Метод Уэлфорда гласит: каждое новое значение сдвигает среднее в свою сторону с весом \(1/i\):
Проверим это для набора \(B\). У нас есть среднее без нового числа \(\overline{x}_{i - 1} = 2\) и новое число \(x_i = 6\), и это седьмое число, \(i = 7\). Цель — найти среднее \(\overline{x}_i\) по формуле Уэлфорда:
Как видите, это абсолютно точное значение. Отлично!
# Дисперсия, корреляция, ковариация
Истинная сила алгоритма Уэлфорда раскрывается при вычислении дисперсии. Наивный подход требует хранения всех точек данных и пересчета среднего перед вычислением дисперсии, что вычислительно дорого. Метод Уэлфорда изящно решает это, поддерживая текущую оценку дисперсии с использованием следующего рекуррентного соотношения:
Для дисперсии мы поддерживаем текущее среднее \(\overline{x}\) и сумму квадратов разностей \(S\). Для каждой новой точки данных \(x_n\) на шаге \(n\):
Дисперсию генеральной совокупности можно затем вычислить как \(\sigma^2 = S_n/n\), а выборочную дисперсию как \(s^2 = S_n/(n-1)\).
Этот подход красиво расширяется на ковариацию и корреляцию. Для двух переменных \(X\) и \(Y\) мы поддерживаем счетчики \(n\), средние \(\overline{x}\) и \(\overline{y}\), и накопленные произведения \(C_{xy}\):
Ковариация тогда равна \(\text{cov}(X,Y) = \frac{C_{xy_n}}{(n-1)}\), а корреляция \(\text{corr}(X,Y) = \frac{C_{xy_n}}{\sqrt{S_{x_n} S_{y_n}}}\).
# Реализация на C
Вот полная реализация алгоритма Уэлфорда на C для вычисления среднего и дисперсии:
#include <stdio.h>
#include <math.h>
typedef struct {
long long n;
double mean;
double M2;
} welford_state;
void welford_update(welford_state *state, double x) {
state->n++;
double delta = x - state->mean;
state->mean += delta / state->n;
state->M2 += delta * (x - state->mean);
}
double welford_mean(const welford_state *state) {
return state->mean;
}
double welford_variance(const welford_state *state) {
return (state->n > 1) ? state->M2 / (state->n - 1) : 0.0;
}
double welford_stddev(const welford_state *state) {
return sqrt(welford_variance(state));
}
int main() {
welford_state state = {0, 0.0, 0.0};
double test_data[] = {1.0, 2.0, 3.0, 6.0};
size_t data_size = sizeof(test_data) / sizeof(test_data[0]);
for (size_t i = 0; i < data_size; i++) {
welford_update(&state, test_data[i]);
printf("Added %.1f: mean=%.3f, variance=%.3f, stddev=%.3f\n",
test_data[i], welford_mean(&state),
welford_variance(&state), welford_stddev(&state));
}
return 0;
}
Для ковариации и корреляции мы можем расширить этот подход:
typedef struct {
long long n;
double mean_x, mean_y;
double C2;
} welford_cov_state;
void welford_cov_update(welford_cov_state *state, double x, double y) {
state->n++;
double delta_x = x - state->mean_x;
double delta_y = y - state->mean_y;
state->mean_x += delta_x / state->n;
state->mean_y += delta_y / state->n;
state->C2 += delta_x * (y - state->mean_y);
}
double welford_covariance(const welford_cov_state *state) {
return (state->n > 1) ? state->C2 / (state->n - 1) : 0.0;
}