Структура данных/алгоритм для эффективного сохранения взвешенного скользящего среднего

Я хотел бы суммировать скользящие средние для ряда различных категорий при хранении записей журнала. Представьте себе сервис, который сохраняет журналы веб-сервера по одной записи за раз. Давайте представим, что у нас нет доступа к лог-записям. Таким образом, мы видим их один раз, но не имеем к ним доступа позже.

Для разных страниц, я хотел бы знать

  • общее количество попаданий (легко)
  • «недавнее» среднее значение (например, один месяц или около того)
  • «долгосрочное» среднее (более года)

Существует ли какой-нибудь умный алгоритм/модель данных, который позволяет сохранять такие скользящие средние без необходимости их пересчета путем суммирования огромных объемов данных?

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

Одним из решений, вероятно, было бы автоматическое создание записей статистики за каждый месяц. Однако мне даже не нужна статистика за прошлый месяц, так что это кажется излишним. И это не дало бы мне скользящее среднее, а скорее переходило бы к новым значениям из месяца в месяц.


algorithm moving-average weighted-average data-structures
person Ortwin Gentz    schedule 21.11.2011    source источник

Ответы (3)


arrow_upward
6
arrow_downward

Простым решением было бы сохранить экспоненциально затухающий итог.

Его можно рассчитать по следующей формуле:

newX = oldX * (p ^ (newT - oldT)) + delta

где oldX — старое значение вашего итога (на момент oldT), newX — новое значение вашего итога (на момент newT); delta — вклад новых событий в общее количество (например, количество просмотров сегодня); p меньше или равно 1 и является коэффициентом затухания. Если мы возьмем p = 1, то получим общее количество попаданий. Уменьшая p, мы эффективно уменьшаем интервал, который описывает наша сумма.

person Rotsor    schedule 21.11.2011
comment
Спасибо. Имеет ли смысл использовать временные метки UNIX для newT и oldT, установить для delta значение 1 (чтобы заново оценивать формулу для каждой новой зарегистрированной записи)? - person Ortwin Gentz; 21.11.2011
comment
Кажется, работает отлично. Похоже, p=0.9 дает мне среднее значение в 10 единиц времени, а p=0.99 — среднее значение в 100 единиц времени. - person Ortwin Gentz; 22.11.2011
comment
Здорово! Кстати, не забудьте применить формулу с delta = 0 при выводе итогов пользователю. В противном случае пользователь сможет увидеть устаревшие значения. - person Rotsor; 22.11.2011
comment
Спасибо, реализовал формулу в геттере. Чтобы зарегистрировать новую запись, мне просто нужно добавить 1 к значению из метода получения. - person Ortwin Gentz; 22.11.2011

arrow_upward
1
arrow_downward

Если все, что вам действительно нужно, — это сглаженное значение с заданной постоянной времени, то проще всего использовать однополюсный рекурсивный БИХ-фильтр (также известный как AR или автоматический фильтр). регрессивный фильтр в анализе временных рядов). Это принимает форму:

Xnew = k * X_old + (1 - k) * x

где X_old — предыдущее сглаженное значение, X_new — новое сглаженное значение, x — текущая точка данных, а k — коэффициент, определяющий постоянную времени (обычно небольшое значение, ‹ 0,1). Возможно, вам потребуется определить два значения k (одно значение для «недавнего» и меньшее значение для «долгосрочного») эмпирически на основе вашей частоты дискретизации, которая в идеале должна быть достаточно постоянной, например. одно обновление в день.

person Paul R    schedule 21.11.2011
comment
В моем случае постоянная частота дискретизации не указана, так как я хочу избежать сохранения промежуточных значений в течение определенного периода времени (например, суммы записей в день). Поэтому я хотел бы оценить новые значения прямо при получении новой записи журнала. - person Ortwin Gentz; 21.11.2011

arrow_upward
0
arrow_downward

Это может быть решением для вас.

Вы можете агрегировать данные в промежуточное хранилище, сгруппированные по часам или дням. Затем функция группировки будет работать очень быстро, потому что вам нужно будет сгруппировать небольшое количество записей, и вставки также будут быстрыми. Точные решения за вами.

Это может быть лучше, чем автокоррелированные экспоненциальные алгоритмы, потому что вы можете легче понять, что вы рассчитываете, и не требует математики на каждом этапе.

Для данных за последний период вы можете использовать ограниченные коллекции с ограниченным количеством записей. Они изначально поддерживаются некоторыми БД, например MongoDB.

person varela    schedule 21.11.2011