Обнаружение аномалий.

Якимов Николай Михайлович

Обнаружение аномалий

Аномалия – отклонение поведения системы от ожидаемого.

Обнаружение аномалий – поиск непредвиденных значений или шаблонов последовательностей значений в потоках данных.

Аномалии могут возникать в результате:

ошибок при получении и сборе данных
аварий
преднамеренных взломов
и т.п.

Виды аномалий

Аномалии обычно относят к одному из трёх типов:

Точечные аномалии
Контекстные аномалии
Коллективные аномалии

Точечные o_1 и o_2 и коллективные O_3 аномалии в двумерных данных — Точечные $o_1$ и $o_2$ и коллективные $O_3$ аномалии в двумерных данных

Контекстная аномалия t_2 во временном ряде — Контекстная аномалия $t_2$ во временном ряде

Обнаружение точечных аномалий

Часто необходима модель системы.

Если нет детерминированной математической модели, то статистическая модель.

Методики построения статистических моделей:

Распознавание с учителем
Распознавание частично с учителем
Распознавание без учителя

Распознавание с учителем

Требует наличия полноценной обучающей выборки.

Применяется в 2 этапа:

обучение на вручную размеченных данных
распознавание, классифицируются новые данные

Статистические свойства модели не должны меняться с течением времени, иначе требуется повторное обучение.

Основная сложность – формирование данных для обучения:

Трудозатратно
Аномальный класс хуже представлен

Распознавание частично с учителем

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

Аномальные данные определяются методом исключения

Распознавание без учителя

При отсутствии априорной информации – единственный возможный вариант.

Исходит из предположения, что аномальные данные встречаются достаточно редко.

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

Применение на потоковых данных затруднено: для хорошей оценки среднего и ожидаемых отклонений необходимо иметь представление о всём массиве данных.

Методы распознавания аномалий

Классификация
Кластеризация
Статистический анализ
Алгоритмы на основе ближайших соседей
Спектральные методы

Классификация

Нормальное поведение системы определяется одним или несколькими классами. Экземпляры, не принадлежащие ни одному из классов – аномальные.

Подход “частично с учителем”.

Основные механизмы:

нейронные сети
Байесовские сети
метод опорных векторов
на основе правил

Кластеризация

Основан на группировке похожих значений в кластеры.

Не требует знаний о свойствах возможных отклонений.

Предположения:

Нормальные экземпляры данных относятся к какому-то кластеру
Нормальные данные ближе к центру кластера, чем аномальные
Нормальные данные образуют большие плотные кластеры, а аномальные – маленькие и разрозненные.

Статистический анализ

Строится статистическая модель процесса, затем сравнивается с реальным поведением. Если реальное поведение отличается, то вывод о наличии аномалий.

Две группы методов:

Параметрические методы. Нормальные данные имеют априорную функцию плотности вероятности $ρ(x,θ)$, где $θ$ – вектор параметров, $x$ – наблюдение.
Непараметрические методы. Структура модели определяется из предоставленных данных.

Алгоритмы на основе ближайших соседей

Вводится метрика (мера похожести между объектами).

Два подхода:

Расстояние до k-го ближайшего соседа. Аномальные данные наиболее удалены от всех других данных.
Использование относительной плотности. Экземпляры в областях с низкой относительной плотностью оцениваются как аномальные.

Спектральные методы

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

Резюме

Метод	Результат	Режим	Классификация аномалий	Обучение
Классификация	Метка	С учителем, частично с учителем	Да	Необходимо
Кластеризация	Метка	С учителем, частично с учителем	Нет	Необходимо
Статистический анализ	Степень	Частично с учителем	Нет	Необходимо
Ближайший сосед	Степень	Без учителя	Нет	Не необходимо
Спектральные методы	Метка	Без учителя, частично с учителем	Нет	Не необходимо

Обнаружение аномалий во временных рядах

Можно применять (с модификацией) подходы из предыдущего раздела.

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

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

На основе скользящих окон.

Подпоследовательность фиксированной длины за раз. Подпоследовательности отстоят друг от друга на расстояние, меньшее длины окна.

Берутся обучающие временные ряды $S_i$, из каждого извлекается $p$ окон $s_i^{(k)}$, из тестовых временных рядов $T_j$ извлекается $r$ окон $t_j^{(l)}$.

Аномальность тестового окна $t_j^{(l)}$ – исходя из сходства с обучающими окнами. В простейшем случае – корреляции, разность Евклидовых норм и т.п.

Более сложные варианты включают классификаторы (напр., на основе метода опорных векторов)

Недостатки:

чувствительность к размеру окна (аномалии должны укладываться в окно)
относительная вычислительная “дороговизна”

Не лучше, чем $O(nprw)$ для каждого тестового ряда, где $w$ – размер окна, $n$ – число обучающих рядов, $p$, $r$ – число окон в каждом обучающем и тестовом рядах соответственно.

Достоинства:

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

Прямые метрические методы

Основаны на сравнении тестовых рядов с обучающими с использованием меры расстояния или подобия. Предположение: аномальные временные ряды отличаются от нормальных, что отражается мерой близости.

Мера аномальности – расстояние от тестового ряда до k-го ближайшего соседа в обучающем наборе.
Кластеризация. Мера аномальности – расстояние от тестового ряда до центра ближайшего кластера.

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

Например, скорость процессов немного отличается, или в начале временных рядов различная задержка.

Для выравнивания временной шкалы – алгоритм динамической трансформации временной шкалы (Dynamic time wrapping, DTW).

Идея: минимизировать отличия по оси значений трансформацией по оси времени.

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

DTW в общем имеет квадратичную сложность, но есть линейные алгоритмы, такие как fastDTW, вычисляющие “достаточно хорошее приближение”.

DTW хуже работает для несинхронизированных периодических временных рядов.

Для таких случаев, анализ автокорреляционной функции позволяет найти задержку и выровнять ряды.

Недостатки:

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

Методы на основе прогнозирования

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

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

Могут обнаружить все типы аномалий.

В качестве модели: спектральные модели, ARIMA и т.п.

Алгоритмы на основе скрытых марковских моделей

Основное предположение: наблюдаемый ряд является косвенным наблюдением “скрытого” ряда. Процесс, описывающий “скрытый” ряд – марковский, т.е. описывается моделью AR(1): $X_{t}=c+\alpha X_{t-1}+\varepsilon_{t}$

Для построения СММ – алгоритм Баума-Велша. Затем вычисляется вероятность порождения тестового ряда моделью.

Если предположение верно, позволяет обнаруживать все типы аномалий. В противном случае, может не работать.

Алгоритм k-means

На основе k средних значений выделяет k кластеров.

Даны начальные значения средних $m_1, \ldots, m_k$.

Наивный алгоритм в 2 шага.

Присваивание. \[S_i^{(t)} = \{x_p : \lVert x_p-m_i^{(t)}\rVert^2 \le \lVert x_p-m_j^{(t)}\rVert^2,\, \forall p, \forall j \in [1,k]\}\] Каждый $x_p$ – только одному кластеру.

Обновление. \[m_i^{(t+1)} = \frac{1}{|S_i^{(t)}|}\sum_{x\in S_i^{(t)}} x\]

Для инициализации обычно:

Forgy
случайное разделение.

Forgy случайным образом выбирает k наблюдений и использует их в качестве начальных.

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

Более сложный алгоритм выбора начальных средних, дающий лучшие результаты – алгоритм k-means++:

Случайно (с равномерным распределением) выбрать одно наблюдение в качестве первого среднего
Для каждого из оставшихся наблюдений $x$, вычислить $D(x)$ – расстояние между $x$ и ближайшим средним, из уже выбранных.
Выбрать новое наблюдение в качестве нового среднего с вероятностью, пропорциональной $D(x)^2$.
Повторять шаги 2, 3 пока не выбрано $k$ средних.

k-means++ требует дополнительных затрат на генерацию начального приближения, но значительно уменьшает число итераций основного алгоритма.

Кроме того, имеет лучшие оценки оптимальности распределения – чаще сходится к глобальному оптимуму, чем стандартный.

Метод опорных векторов

Каждое наблюдение представляется точкой в $p$-мерном пространстве. Каждая точка принадлежит одному из двух классов.

Вопрос: можно ли разделить эти точки гиперплоскостью размерности $p-1$. Это задача линейной разделимости.

Если есть хотя бы одна разделяющая гиперплоскость, то их может быть бесконечно много. Интересует оптимальная гиперплоскость – максимизирующая расстояние до ближайших точек с обеих сторон (“зазор”).

Формально, полагаем, обучающий набор вида \[\{(\vec x_1, c_1), \ldots, (\vec x_n, c_n)\},\] где $c_i \in \{-1, 1\}$ – класс точки $\vec x_i$. $\vec x_i$ – нормализованный $p$-мерный вектор.

Строится гиперплоскость \[\vec w \cdot \vec x - b = 0,\] где $\vec w$ – перпендикуляр, $\frac{b}{|\vec w|}$ – расстояние от начала координат.

Размер зазора – расстояние между гиперплоскостями (с точностью до нормировки) \[\vec w \cdot \vec x - b = 1\] \[\vec w \cdot \vec x - b = -1\]

Тогда зазор $d = \frac{2}{|\vec w|}$. Максимизация зазора – минимизация $|\vec w|$.

В зазоре не должно быть точек данных, поэтому \[c_i(\vec w \cdot \vec x_i - b) \ge 1\]

Это задача ограниченной оптимизации.

На практике, решается “смягчённая” задача, смягчающая неравенство:

\[|\vec w|^2 + C\sum_{i=1}^n\xi_i \to \min_{\vec w, b, \vec \xi}\] \[c_i (\vec w\cdot \vec x_i - b) \ge 1 -\xi_i\] \[\xi_i \ge 0\]

Если исходные данные линейно-неразделимы, используется “трюк с ядром”: скалярное произведение заменяется на “ядро” – скалярное произведение в пространстве с большей размерностью.

Линейно-неразделимые данные в двумерном пространстве легко разделимы в трёхмерном

Этот метод применим к временным рядам, если рассматривать серию значений во временном ряде как вектор:

\[x(t) = \{x(t-E+1), x(t-E+2), \ldots, x(t)\}^{\mathrm T},\]

$E$ – размерность пространства

Подход близок по сути к оконным методам.

Алгоритм Баума-Велша

СММ – вертоятностная модель множества случайных переменных $\{Y_1,\ldots,Y_t, Q_1, \ldots, Q_t\}$. $Y_i$ – наблюдения, $Q_i$ – скрытые величины.

Предположения:

$Q_t$ зависит только от $Q_{t-1}$: \[P(Q_t | Q_{t-1}, Y_{t-1}, \ldots, Q_{1}, Y_{1}) =P(Q_t | Q_{t-1})\]
$Y_t$ зависит только от $Q_t$: \[P(Y_t | Q_{t-1}, Y_{t-1}, \ldots, Q_{1}, Y_{1}) =P(Y_t | Q_t)\]

Пусть $Q_t \in \{1,\ldots,N\}$. Если модель однородна по времени, т.е. $ t P(Q_t | Q_{t-1}) = $, мы можем задать матрицу переходов \[A = \{a_{ij}\} = p(Q_t=j|Q_{t-1}=i).\]

Вероятности начальных состояний – из начального распределения $π_i = p(Q_1 = i).$

Наблюдения $Y_t \in \{o_1,\ldots,o_L\}$. Вероятность данного наблюдения тогда \[b_{ij} = b_j(o_i) = p(Y_t = o_i | Q_t = j),\] матрица $B = \{b_{ij}\}$ размера $L\times N$.

Тогда модель описывается тройкой $(A, B, π)$, которую мы обозначим $λ$.

Алгоритм Баума-Велша находит $λ^* = \arg \max_λ P(y|λ)$, параметры, максимизирующие вероятность наблюдений $y$.

Алгоритм

В качестве исходных выбираются случайные значения $λ=(A,B,π)$. Алгоритм итеративно обновляет $λ$ до схождения к неподвижной точке.

Прямая процедура

\[α_i(t) = p(Y_1=y_1, \ldots, Y_t=y_t, Q_t = i | λ)\] вероятность появления заданной последовательности измерений $\{y_1, \ldots, y_t\}$

Можно вычислить рекурсивно:

\[α_i(t) = π_i \cdot b_i(y_1)\] \[α_i(t+1) = b_i(y_{t+1})\sum_{j=1}^N α_j(t)\cdot a_{ji}\]

Обратная процедура

\[β_i(t) = p(Y_{t+1}=y_{t+1}, \ldots, Y_T=y_T | Q_t=i, λ)\] вероятность “будущей” последовательности измерений, при условии что в “текущий” момент $t$ скрытое состояние – $i$

Можно вычислить рекурсивно:

\[β_i(T) = p(Y_T=y_T | Q_t=i, λ) = 1\] \[β_i(t) = \sum_{j=1}^N β_j(t+1)a_{ij}b_j(y_{t+1})\]

Зная $α$ и $β$, можно вычислить

\[γ_i(t) = p(Q_t=i|y, λ) = \frac{α_i(t)β_i(t)}{\sum_{j=1}^N α_j(t)β_j(t)}\] \[ξ_{ij}(t) = p(Q_t=i, Q_{t+1}=j|y, λ) = \frac{α_i(t)a_{ij}β_j(t+1)b_j(y_{t+1})}{\sum_{k=1}^N\sum_{w=1}^N α_k(t)a_{kw}β_w(t+1)b_w(y_{t+1})}\]

Из этого – новые параметры модели:

\[π_i^* = γ_i(1)\] \[a_{ij}^* = \frac{\sum_{t=1}^{T-1}ξ_{ij}(t)} {\sum_{t=1}^{T-1} γ_i(t)}\] \[b_i^*(o_k) = \frac{\sum_{t=1}^{T}δ_{y_t=o_k}γ_i(t)} {\sum_{t=1}^{T} γ_i(t)}\]