Какой алгоритм я должен использовать для обнаружения аномалий на временных рядах?

70

Фон

Я работаю в Центре сетевых операций, мы отслеживаем компьютерные системы и их производительность. Одним из ключевых показателей для мониторинга является количество посетителей \ клиентов, которые в настоящее время подключены к нашим серверам. Чтобы сделать это видимым, мы (команда Ops) собираем такие метрики, как данные временных рядов и рисуем графики. Graphite позволяет нам делать это, имеет довольно богатый API, который я использую для создания системы оповещений, чтобы уведомлять нашу команду о внезапных падениях (в основном) и других изменениях. На данный момент я установил статический порог, основанный на значении avg, но он не очень хорошо работает (есть много ложных срабатываний) из-за разной нагрузки в течение дня и недели (фактор сезонности).

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

Фактические данные (пример для одной метрики, 15-минутный интервал времени; первое число - количество пользователей, второе - метка времени):

[{"target": "metric_name", "datapoints": [[175562.0, 1431803460], [176125.0, 1431803520], [176125.0, 1431803580], [175710.0, 1431803640], [175710.0, 1431803700], [175733.0, 1431803760], [175733.0, 1431803820], [175839.0, 1431803880], [175839.0, 1431803940], [175245.0, 1431804000], [175217.0, 1431804060], [175629.0, 1431804120], [175104.0, 1431804180], [175104.0, 1431804240], [175505.0, 1431804300]]}]

Чего я пытаюсь достичь

Я создал скрипт Python, который получает последние точки данных, сравнивает их с историческим средним и оповещает, если происходит внезапное изменение или падение. Из-за сезонности «статический» порог не работает, а скрипт генерирует ложные срабатывания. Я хочу улучшить алгоритм оповещения, чтобы быть более точным и заставить его работать без постоянной настройки порога оповещения.

Какие советы мне нужны и что я обнаружил

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

Мне нравится Python и я немного знаком с R, поэтому буду рад увидеть примеры для этих языков. Пожалуйста, порекомендуйте хорошую книгу или статью, которая поможет мне решить мою проблему. Спасибо за ваше время и простите за такое длинное описание

Полезные ссылки

Похожие вопросы:

Внешние ресурсы:

machine-learning time-series python computational-statistics anomaly-detection Илья Хадыкин
источник

1

Вы взглянули на один из самых простых алгоритмов, таких как CUSUM?

Владислав Довгальец

@xeon, пока нет. Я новичок в этой теме, и мне нужно время, чтобы все переварить. Спасибо, что подняли этот вопрос, это хорошая отправная точка, я могу реализовать это прямо сейчас

Илья Хадыкин

1

Это отличный вопрос, @ ma-ge. У меня похожий сценарий. Мой подход состоял в том, чтобы настроить оповещения путем создания непрерывных периодических прогнозов, используя auto.arimaфункцию из превосходного forecastпакета R (см. Jstatsoft.org/v27/i03/paper ). Вы можете настроить уровни достоверности, отрегулировав levelпараметр, например

data.model <- auto.arima(data.zoo, ic = c("bic")); data.prediction.warningLimits <- forecast(data.model, h=1, level=0.99)

.

Алекс Вулфорд

3

Ребята из твиттера написали очень интересную статью на эту тему. Проверьте это: blog.twitter.com/2015/…

ognjenz

Привет @IlyaKhadykin Надеюсь, у тебя все хорошо! Вы когда-нибудь получали какое-либо решение для этой проблемы. Я делаю то же самое, в котором каждую минуту у нас есть определенные пользователи, и мы также получаем много ложных срабатываний. На данный момент мы рассчитываем балл за каждые 5 минут данных интервала и сопоставляем его с историческим паттерном. Если вы получили какой-то конкретный алгоритм работы, вы можете поделиться, как вы это сделали. Заранее спасибо!

ak3191

24

Я думаю, что ключ является «неожиданным» классификатором в вашем графике. Чтобы обнаружить неожиданное, вам нужно иметь представление о том, что ожидается .

Я бы начал с простой модели временных рядов, такой как AR (p) или ARMA (p, q). Подгоните его под данные, добавьте сезонность по мере необходимости. Например, ваша модель SAR (1) (24) может быть: , где - время в часах. Итак, вы будете предсказывать график на следующий час. Всякий раз, когда ошибка прогнозирования "слишком велика", вы предупреждение. $y_{t}=c+\phi y_{t-1}+\Phi_{24}y_{t-24}+\Phi_{25}y_{t-25}+\varepsilon_t$ $t$ $e_t=y_t-\hat y_t$

Оценив модель, вы получите дисперсию ошибки . В зависимости от ваших предположений о распределении, например нормальных, вы можете установить порог на основе вероятности, например для 99,7% или односторонний . $\sigma_\varepsilon$ $\varepsilon_t$ $|e_t|<3\sigma_\varepsilon$ $e_t>3\sigma_\varepsilon$

Количество посетителей, вероятно, довольно постоянное, но супер сезонное. Может быть лучше попробовать сезонные манекены вместо мультипликативной сезонности, тогда вы попробуете ARMAX, где X обозначает экзогенные переменные, которые могут быть чем-то вроде праздничных манекенов, часовых манекенов, манекенов выходных и т. Д.

Аксакал
источник

5

Этот подход предполагает конкретную модель ARIMA, которая будет иметь смещенные параметры, основанные на аномалиях, которые предположительно предположительно не существуют. Более общий подход состоял бы в том, чтобы ТАКЖЕ идентифицировать сначала аномалии, а затем оптимальную модель ARIMA, ведущую к встроенным тестам значимости. К дополнительным аномалиям могут относиться сдвиги уровней, сезонные импульсы и локальные тренды времени, которые требуют более общего решения, чем предлагается здесь. См. Unc.edu/~jbhill/tsay.pdf для полной процедуры. Вы также можете Google "Автоматическое обнаружение вмешательства" для получения дополнительной информации.

IrishStat

@IrishStat Я предложил ARIMAX с манекенами для событий. OP может учитывать известные события, такие как сбои веб-сайта с помощью макетов. Это уменьшит дисперсию ошибок, и будет больше предупреждений. Нет смысла строить сложную модель, потому что просто невозможно учесть все, что касается трафика веб-сайта. Простые модели будут работать лучше всего.

Аксакал

2

@ ma-ge, еще одна вещь: вы можете использовать перекрывающиеся интервалы. Допустим, вы собираете данные каждую минуту, но для моделирования вы можете выбрать шаг за 10 минут. Это создает некоторые проблемы для оценки (из-за автокорреляции), но полученная модель, скорее всего, будет более устойчивой.

Аксакал

Модели @Aksakal должны быть настолько простыми, насколько это необходимо, НО не слишком простыми.

IrishStat

17

В техническом блоге Netflix есть статья об их инструменте Robust Anomaly Detection (RAD). http://techblog.netflix.com/2015/02/rad-outlier-detection-on-big-data.html

Он имеет дело с сезонностью и очень большими объемами данных, поэтому он может соответствовать вашим требованиям. Код с открытым исходным кодом Java и Apache Pig https://github.com/Netflix/Surus/blob/master/resources/examples/pig/rad.pig

Базовый алгоритм основан на надежном PCA - см. Оригинальную статью здесь: http://statweb.stanford.edu/~candes/papers/RobustPCA.pdf

Пол МакГеттиган
источник

12

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

Ниже я обрисовываю некоторые доступные подходы пакетов в open source R:

tsoutliers : Реализует алгоритм обнаружения выбросов Чена и Лю в рамках arima. см мой предыдущий вопрос на этом сайте. Фантастический подход, но очень медленный, не уверенный, сможет ли он обрабатывать высокочастотные данные, подобные вашим. Он имеет преимущество обнаружения всех типов выбросов, как упомянуто в моем предыдущем вопросе / посте.
Обнаружение аномалий в Twitter : использует алгоритм Рознера для обнаружения аномалий, основанных на временных рядах. Алгоритм разбивает временные ряды, а затем обнаруживает аномалии. По моему личному мнению, это не эффективно и точно при обнаружении outlires во временных рядах.
tsoutlier в пакете прогноза: аналогичен алгоритму Твиттера с точки зрения разложения временных рядов с последующим обнаружением выбросов. Только обнаружит аддитивные выбросы или импульсы.

Существуют коммерческие пакеты, в которых есть специальные подходы для обнаружения аномалий. Другим классическим подходом является алгоритм определения выбросов Цая по временным рядам, аналогичный подходу Чена и Лю, он обнаруживает различные типы выбросов. Недавно я также наткнулся на это коммерческое программное решение под названием metafor, которое может быть более подходящим для ваших данных.

Надеюсь, это полезно

предсказатель
источник

Спасибо, это дает мне представление о похожих проблемах и подходах; Отдельное спасибо за ссылки!

Илья Хадыкин

Если кто-то ищет Metafor, мы приобрели Splunk. Наши алгоритмы TSAD включены в последние версии Splunk IT Service Intelligence («ITSI»).

Алекс Круз

5

Кажется, что другие ответы не упоминали, что ваша проблема звучит как обнаружение точки изменения . Идея обнаружения changeapoint заключается в том, что вы ищете сегменты в ваших данных, которые значительно различаются по свойствам терминов (например, среднее значение, дисперсия). Это может быть достигнуто с использованием оценки максимального правдоподобия, где для точек изменения функция правдоподобия $m$

L (m, τ_{1 : m}, θ_{1 : (m + 1)}) = \prod_{i = 1}^{m + 1} p (y_{(τ_{i - 1} + 1) : τ_{i}} ∣ θ_{i})

$L(m, \tau_{1:m}, \theta_{1:(m+1)}) = \prod_{i=1}^{m+1} p(y_{(\tau_{i-1} + 1):\tau_i}\mid \theta_i)$

где - ваши данные, - граничные точки, обозначающие изменения, а распределения вероятности параметризованы для каждого сегмента. Это может быть легко обобщено на различные ситуации. Существует ряд алгоритмов для нахождения параметров, включая поиск неизвестного . Существует также программное обеспечение, которое доступно для оценки таких моделей, например, пакет для R. Если вы хотите узнать больше, вы можете проверить следующие публикации и ссылки, которые они предоставляют: $y_1,\dots,y_n$ $1 < \tau_1 <\dots<\tau_m<n$ $p$ $\theta_i$ $i$ $m$ changepoint

Ребекка Киллик и Идрис А. Экли. (2013) точка изменения: пакет R для анализа точек изменения. (интернет-газета)

Экли И. А., Фернхед П. и Киллик Р. (2011) Анализ моделей точек изменения. [в:] Байесовские модели временных рядов , ред. Д. Барбер, А. Т. Джемгил и С. Чиаппа, издательство Кембриджского университета.

Тим
источник

4

Вы пробовали использовать правила статистического контроля процессов (например, Western Electric http://en.wikipedia.org/wiki/Western_Electric_rules )?

Я использую их для данных временных рядов - часто с легкой интуицией в отношении данных - чтобы оценить, куда идут данные, и я не хочу, чтобы они шли. Как и в вашем примере, эти правила говорят, что если дельта / изменение согласовано в нескольких точках данных, это указывает на возможную проблему.

Также Статистический контроль процесса (SPC) может быть полезен для тренировки, если вы становитесь лучше или хуже, чем раньше.

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

MarkR
источник

4

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

Простое одношаговое различие обнаружит внезапное падение от предыдущего значения

y_{t}^{'} = y_{t} - y_{t - 1}

$y_t'= y_t - y_{t-1}$

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

y_{t}^{'} = y_{t} - y_{t - n} where n = length of period

$y_t'= y_t - y_{t-n} \quad \text{where } n=\text{length of period}$

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

Если выборка проводится каждый час, в приведенном выше уравнении должно быть равно $n$ $24*7 = 168$

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

y_{t}^{*} = \frac{y_{t}}{y_{t - n}}

$y_t^*= \frac{y_t}{y_{t-n}}$

Я провел несколько тестов в R, используя смоделированный набор данных. В нем данные отбираются 6 раз в день, и существуют сильные ежедневные и еженедельные периоды, наряду с другими шумами и колебаниями. Капли добавляли в случайных местах и продолжительностью от 1 до 3.
Для выделения капель сначала рассчитывали отношения на расстоянии 42, а затем пороговое значение, установленное на 0,6, поскольку представляет интерес только отрицательное изменение определенного размера. Затем была рассчитана разница в один шаг, и пороговое значение было установлено равным -0,5. В конце концов один ложный положительный результат, похоже, проскользнул (тот, что в конце недели 16). Графики слева и справа показывают одни и те же данные, только по-разному.

AkselA
источник

3

Было бы более полезно думать об изменениях во временных рядах как о начале новой тенденции, а не как об аномалии? Изучение разницы между соседними точками поможет определить, когда меняется наклон (производная), и может сигнализировать о начале нового тренда в дате. Также может быть полезно взять различия значений разности (вторая производная). Выполнение поиска в Google по «началу временного ряда» может дать хорошие подсказки для методов. В финансовых данных последнее внимание уделяется новым тенденциям (вы покупаете или продаете?), Поэтому есть статьи на эту тему.

Хорошее вступление к вейвлету - «Мир по вейвлетам» Хаббарда. Я считаю, что это автор.

DavidF
источник

2

Мне удалось получить хорошие результаты для временных рядов с несколькими сезонностями (ежедневно, еженедельно), используя два разных алгоритма:

Разложение по сезонным трендам с использованием лесса (или STL) для установления ряда средней точки.
Нелинейная регрессия для установления порогов вокруг этой средней точки на основе взаимосвязи между дисперсией и уровнем.

STL выполняет декомпозицию временной области вашего временного ряда на компонент тренда, один сезонный компонент и остаток. Сезонный компонент - это ваша высокочастотная сезонность (например, ежедневно), тогда как тренд включает в себя как низкочастотную сезонность (например, еженедельно), так и сам тренд. Вы можете разделить их, просто запустив STL снова на тренде. В любом случае, как только вы изолируете оставшуюся серию от других компонентов, вы можете выполнить обнаружение аномалий по этой серии.

Я сделал более подробную запись здесь:

https://techblog.expedia.com/2016/07/28/applying-data-science-to-monitoring/

Вилли Уилер
источник

1

Вдохновленный Дэвидом, вы пытались использовать БПФ? Это может быть в состоянии обнаружить внезапные падения, потому что они указывают на ваши аномалии. Аномалии могут появляться в узком спектре. Таким образом, вы можете легко захватить их.

Ромео Кинцлер
источник

Какой алгоритм я должен использовать для обнаружения аномалий на временных рядах?

Фон

Чего я пытаюсь достичь

Какие советы мне нужны и что я обнаружил

Полезные ссылки

Ответы: