Оконные методы

Оконные методы – рассмотрение некоторого временного среза.

“Окно” – небольшая ограниченная часть потока данных.

Данные ограничены:

• Политикой срабатывания
• Политикой вытеснения

Скользящее окно

Политики вытеснения и срабатывания основаны на времени.

Факторы:

• протяжённость окна
• интервал скольжения

Протяжённость окна – время, в течение которого данные хранятся в окне и доступны для обработки. Политика вытеснения.

Интервал скольжения – по сути, интервал срабатывания. Политика срабатывания.

Поддержка в системах потоковой обработки разнится.

Прыгающее окно

Прыгающие окна могут работать по времени или по счётчику. Основное отличие от скользящего окна – каждое событие принадлежит только одному прыгающему окну.

Случайная выборка

Нужно для статистического анализа.

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

Для потоковых данны – резервуарная выборка.

Идея: хранить заранее определённое число значений из потока, делать его “более случайным” при поступлении новых данных.

\(k\) – размер резервуара. Первые \(k\) значений помещаются в резервуар. Для каждого следующего – помещается на случайное место с вероятностью \(k/i\), где \(i\) – номер значения (начиная с 1). Результат: в резервуаре равномерная случайная выборка.

Две реализации: простая и эффективная.

Простая реализация:

function reservoirSample(S, R) {
  for i := 1 to k{
    R[i] := S[i]
  }
  for i := k+1 to n {
    j := randomInteger(1, i)
    // равномерное случайное целое
    // в диапазоне [1, i]
    if j <= k {
      R[j] := S[i]
    }
  }
}

Эффективная реализация:

function reservoirSample(S, R) {
  for i = 1 to k
      R[i] := S[i]

  // random() -- случайное число на интервале (0,1)
  W := exp(log(random())/k)

  while i <= n {
    i := i + floor(log(random())/log(1-W)) + 1
    if i <= n {
      R[randomInteger(1,k)] := S[i]
      W := W * exp(log(random())/k)
    }
  }
}

Подсчёт уникальных элементов

В случае потоковой обработки – основан на вероятностных алгоритмах.

Две категории:

• На основе битовых комбинаций
• На основе порядковых статистик (MinCount, алгоритм Бар-Йоссефа)

Алгоритм:

1. Входящее значение \(x_t\) передаётся “хорошей” хэш-функции \(h = H(x_t)\)
2. \(h\) – в двоичную строку \(b = B(h)\)
3. \(m\) младших бит \(b\) – номер ячейки \(M[b_m]\)
4. \(M[b_m] = \max(M[b_m], l)\), где l – длина префикса старших \(|b|-m\) бит \(b\) вида 0...01
5. Кардинальность \[C ≈ α_m 2^{2m} \left(\sum_{j=1}^{2^m} 2^{-M[j]}\right)^{-1}\]

\(α_m < 1\) – коэффициент, учитывающий коллизии. Для \(m\in[4,7]\), \(α_m≈0.7\)

\(m\) – точность, определяет относительную погрешность (около \(\frac{1.04}{2^{m/2}}\))

Частота

Сколько раз встречается элемент \(x\)?

Популярный алгоритм – Count-Min sketch.

Счётчики \(M_i\) – набор числовых массивов. Индексируются с нуля.

Число счётчиков – ширина \(w\); размер счётчика – длина \(m\).

\(w\) хеш-функций \(H_i\) (по одной на счётчик).

\[\forall i \in [1,w]: M_i[H_i(v)] := M_i[H_i(v_t)]+1\]

\[F(x) ≈ \min_{i \in [1,w]} M_i[H_i(v)]\]

Погрешность \[\frac{\tilde x-x}{N} \le \frac{e}{m}\] с вероятностью \[1-δ = 1-e^{-w},\] где \(N\) – число элементов в потоке.

Вхождение в множество

Встречался ли данный элемент в потоке ранее?

Такой же подход, как и в случае с определением частот. Фильтр Блума (не путать с визуальным эффектом).

Может давать ложноположительный ответ, но не ложноотрицательный.

Отличия от CM sketch:

• вместо массивов чисел – один битовый вектор
• обновление – битовая дизъюнкция (вместо +1)
• конечная оценка – результат конъюнкции (вместо min)

Две основных задачи:

• Выявление структуры (определение закономерностей, построение модели)
• Прогнозирование (предсказание будущих значений на основе текущих)

Составляющие

Составляющие:

• Систематическая
• Случайная (шум, ошибка)

Систематическая составляющая содержит:

• Тренд – апериодическая компонента
• Сезонность – периодическая компонента.

Сезонность:

• Мультипликативная – линейно зависит от тренда
• Аддитивная – не зависит от тренда

Анализ тренда

Если тренд монотонный, возможен анализ регрессионными методами.

Необходимо исключение случайных составляющих. Основной метод – сглаживание.

Сглаживание подразумевает локальное усреднение.

Универсальный подход – скользящее среднее.

Реже – более сложные методы, такие как метод наименьших квадратов.

После удаления случайной компоненты – линейная или (реже) нелинейная регрессия.

Анализ сезонности

Анализ периодических составляющих – на основе автокорреляции.

Периодическая зависимость – формально корреляция между каждым i-м элементом ряда и (i-k)-м элементом ряда. k – лаг, или сдвиг.

Найти k – поиском минимума АКФ \[R(k) = \sum_i y_i y_{i-k}\]

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

Другой метод – исследование ЧАКФ. В ЧАКФ устраняется зависимость между промежуточными отсчётами (внутри лага), т.е. при вычислении ЧАКФ с лагом \(k\), из неё удаляются влияние автокорреляций с лагами \(0<l<k\).

Периодическая составляющая для лага \(k\) удаляется взятием разности временного ряда с самим собой с соответствующим сдвигом.

Таким образом можно определить скрытые периодические составляющие ряда.

Удаление сезонных составляющих делает ряд стационарным.

Процесс авторегрессии:

\[x_t = ξ + ε_t + \sum_{i=1}^p φ_i x_{t-i}\]

\(ξ\) – константа, \(ε\) – случайное воздействие, \(φ_i\) – параметры.

Процесс скользящего среднего:

\[x_t = μ + ε_t - \sum_{j=1}^q θ_j ε_{t-j},\] \(μ\) – константа, \(ε\) – случайное воздействие, \(θ_i\) – параметры.

В этом изложении – только для стационарного ряда.

Ряд можно сделать стационарным, вычисляя разности. Число необходимых разностей – \(d\).

Для нестационарного ряда:

\[(Δ^d x)_t = ξ + \sum_{i=1}^p φ_i (Δ^d x)_{t-i} + \sum_{j=1}^q θ_j ε_{t-j} + ε_t,\] \(Δ^d\) – оператор разности временного ряда порядка \(d\)

Параметры d, p, q в общем случае не могут быть определены автоматически.

Определение \(d\) требует анализа автокорреляционных свойств.

Параметры p и q выбираются минимальные из тех, которые хорошо предсказывают поведение ряда.

На практике, p и q редко бывают больше 2.

Общие рекомендации для выбора параметров на основе вида АКФ и ЧАКФ:

1. p=1, q=0. АКФ экспоненциально убывает, ЧАКФ имеет резко выделяющееся значение для лага 1.
2. p=2, q=0. АКФ периодическая или экспоненциально убывает. ЧАКФ имеет резко выделяющиеся значения на лагах 1, 2.
3. q=1, p=0. АКФ имеет резко выделяющееся значение на лаге 1, ЧАКФ экспоненциально убывает.

Общие рекомендации для выбора параметров на основе вида АКФ и ЧАКФ (продолжение):

4. q=2, p=0. АКФ имеет резко выделяющиеся значения на лагах 1, 2. ЧАКФ периодическая или экспоненциально убывает.
5. p=1, q=1. АКФ экспоненциально убывает с лага 1, ЧАКФ экспоненциально убывает с лага 1.

Для определения параметров \(φ_i\) и \(θ_i\), применяются методы оптимизации, минимизируется функция ошибки.

Полученные оценки параметров используются для прогноза.

Для получения прогноза в терминах исходного ряда – интегрирование разностей.

В ARIMA возможно добавить сезонную составляющую, введя для определённого лага сезонные параметры (ps, ds, qs). Обычно это поход, дающий значимо лучшие результаты, чем прямое увеличение d, p, q. Такая модель называется SARIMA (сезонная ARIMA).

Выделение \(b(t)\) – сглаживание скользящим средним. Последним наблюдениям – большие веса, чем предпоследним и т.д.

При простом экспоненциальном сглаживании, старым наблюдениям – экспоненциально убывающие веса. В отличие от скользящего среднего, учитываются все предшествующие наблюдения ряда:

\[s_t = α x_t + (1-α) s_{t-1},\] \(s_t\) – сглаженный ряд.

\[s_t = α x_t + (1-α) s_{t-1},\] \(s_t\) – сглаженный ряд.

Когда применяется рекурсивно, каждое сглаженное значение – взвешенное среднее текущего отсчёта и сглаженного ряда. Новое сглаженное значение – также прогноз.

Результат зависит от \(α\). При \(α=1\), прошлые наблюдения игнорируются, при \(α=0\), игнорируется новое наблюдение.

Выбор α – на основе методов оптимизации.

Метрики:

• среднеквадратичная ошибка \[\frac{1}{N}\sum_{i=1}^N (\tilde x_i - x_i)^2\]
• средняя абсолютная относительная ошибка \[\frac{1}{N}\sum_{i=1}^N \left|\frac{\tilde x_i - x_i}{x_i}\right|\]

Для коротких рядов – значительное влияние от начального \(s_0\). Его выбор тоже может осуществляться оптимизационными методами.

Для выбора \(α\), \(s_0\) есть эвристики.

Учёт сезонности и тренда

Сезонность и тренд – добавлением составляющих, имеющих задержку.

Аддитивная: \(π_t = s_t + i_{t-p}\)

Мультипликативная: \(π_t = s_t i_{t-p}\)

\(s_t\) – экспоненциально сглаженное значение, \(π_t\) – прогноз, \(i_{t-p}\) – сглаженный сезонный компонент.

Оценка сезонной компоненты:

Аддитивной: \(i_t = i_{t-p} + δ(1-α)e_t\)

Мультипликативной: \(i_t = i_{t-p} + δ(1-α)e_t/s_t\)

\(e_t = \tilde x_t - x_t\)

\[0 \le δ \le 1\]

Если \(δ = 0\), то сезонность не меняется между периодами.

Если \(δ=1\), то сезонность меняется “максимально”.

Аналогично можно учитывать тренд: экспоненциально сгладить разность 1 порядка временного ряда с отдельным параметром и добавить к прогнозу.

В общем случае, для мультипликативной сезонности:

\[\begin{align} s_0 & = x_0 \\ s_t & = α \frac{x_t}{c_{t-L}} + (1-α)(s_{t-1}+b_{t-1}) \\ b_t & = β(s_t - s_{t-1})+(1-β)b_{t-1} \\ c_t & = γ\frac{x_t}{s_t}+(1-γ)c_{t-L} \end{align}\]

Для аддитивной сезонности:

\[\begin{align} s_0 & = x_0 \\ s_t & = α (x_t-c_{t-L}) + (1-α)(s_{t-1}+b_{t-1}) \\ b_t & = β(s_t - s_{t-1})+(1-β)b_{t-1} \\ c_t & = γ(x_t-s_{t-1}-b_{t-1})+(1-γ)c_{t-L} \end{align}\]

Обычно, тренд и циклическую компоненту объединяют в \(tc_t\)

Основные варианты связей:

• Аддитивная: \(x_t = tc_t + s_t + i_t\)

• Мультипликативная: \(x_t = tc_t s_t i_t\)

Алгоритм:

1. Ряд сглаживается скользящим средним с периодом сезонности. В результате сезонная компонента практически исключается.
2. Из исходного ряда исключается сглаженный ряд (вычитанием или делением). Это даёт сезонную компоненту.

3. Вычисляется средняя сезонная составляющая на основе сезонной компоненты по всему ряду.
4. Из исходного ряда вычитается средняя сезонная компонента, что даёт сезонно-корректированный ряд.

5. Тренд-циклическая компонента оценивается применением к ряду с сезонной поправкой взвешенного скользящего среднего с линейно убывающими к краям весами.
6. Случайная компонента получается вычитанием из сезонно-корректированного ряда оценки тренд-циклической компоненты.

Метод – эвристический.

X-11 или Census II – больше специфических эвристик.

Может помочь выделить характерные периоды в каком-то массиве данных, которые могут быть не слишком очевидны.

Поскольку SARIMA или экспоненциальное сглаживание предполагают, что периодичность известна a priori, анализ при помощи ПФ позволяет более обоснованно выбирать параметры.