- PVSM.RU - https://www.pvsm.ru -
Когда наблюдаемых метрик становится слишком много, отслеживание всех графиков самостоятельно становится невозможным. Обычно в этом случае для менее значимых метрик используют проверки на достижение критичных значений. Но даже если значения подобраны хорошо, часть проблем остается незамеченной. Какие это проблемы и как их обнаруживать — под катом.
Disclaimer
Автор хотя и имеет математическое образование, никак не связан ни с Data Mining, ни со статистическим анализом. Данный материал является результатом исследования, проведенного с целью выяснить возможность написания модуля поиска аномалий (пусть даже слабого) для разрабатываемой системы мониторинга.
Конечно в реальности, не всегда все так просто: только на б), д) и е) явная аномалия.
Источник cyberleninka.ru [2]
Коммерческие продукты почти всегда представлены в виде сервиса, использующего как статистику, так и машинное обучение. Вот некоторые из них: AIMS [3], Anomaly.io [4] (прекрасный блог с примерами), CoScale [5] (возможность интеграции, напр. с Zabbix), DataDog [6], Grok [7], Metricly.com [8] и Azure [9] (от Microsoft). У Elastic есть модуль X-Pack [10] на основе машинного обучения.
Open-source продукты, которые можно развернуть у себя:
На мой взгляд open-source по качеству поиска значительно уступает. Чтобы понять, как работает поиск аномалий и можно ли исправить ситуацию, придется немного окунуться в статистику. Математические детали упрощены и скрыты под спойлерами.
Для анализа временного ряда используют модель, которая отражает предполагаемые особенности (компоненты) ряда. Обычно модель состоит из трех компонент:
Можно включить дополнительные компоненты, например циклическую [21], как множитель тренда,
аномальную (Catastrophic event) [22] или социальную (праздники) [23]. Если тренд или сезонность в данных не просматриваются, то соответсвующие компоненты из модели можно исключить.
В зависимости от того, как связаны между собой компоненты модели, определяют её тип. Так, если все компоненты складываются, чтобы получить наблюдаемый ряд, то говорят, что модель аддиктивна, если умножаются, то мультипликативна, если что-то умножается, а что-то сладывается, то смешаная. Обычно тип модели выбирается исследователем на основе предварительного анализа данных.
Выбрав тип модели и набор компонент можно приступать к декомпозиции временного ряда, т.е. его разложению на компоненты.
Источник Anomaly.io [24]
Сперва выделяем тренд, сгладив исходные данные. Метод и степень сглаживания выбираются исследователем.
Если использовать не одно, а несколько предшедствующих значений, т.е. среднее арифметическое k-соседних значений, то такое сглаживание называется простым скользящим средним с шириной окна k
Если для каждого предыдушего значения использовать какой то свой коэффициент, определяющий степень влияния на текущий, то получим взвешенное скользящее среднeе [25].
Несколько другой способ — эсконенциальное сглаживание. Сглаженный ряд вычисляется следующим образом: первый элемент совпадает с первым элементом исходного ряда, а вот последующие вычисляются по форумуле
Где α — коэффициент сглаживания, от 0 до 1. Как легко видеть чем ближе α к 1, тем больше получаемый ряд будет похож на исходный.
Для определения линейного тренда можно взять методику расчета линейной регрессии методом наименьших квадратов [26]: , , где и — средние арифметические и .
Источник Википедия [27]
Для определения сезонной составляющей из исходного ряда вычитаем тренд или делим на него, в зависимости от типа выбранной модели, и еще раз сглаживаем. Затем делим данные по длине сезона (периоду), обычно это неделя, и находим усредненный сезон. Если длина сезона не известна, то можно попытаться найти её:
Для поиска авто-корреляцией просто сдвигаем функцию вправо и ищем такое положение, чтобы расстояние/площадь между исходной и сдвинутой функцией (выделено красным) было минимально. Очевидно для алгоритма должен быть задан шаг сдвига и максимальный предел, при достижении которого считаем, что поиск периода не удался.
Более подробно о моделях и декомпозиции можно узнать из статей «Extract Seasonal & Trend: using decomposition in R» [24] и «How To Identify Patterns in Time Series Data» [30].
Удалив из исходного ряда тренд и сезонный фактор, получаем случайную компоненту.
Если анализировать только случайную компоненту, то многие аномалии можно свести к одному из следующих случаев:
Считаем, что на входе ряд чисел — , ,… , всего штук. — -ое число.
Стандартные тесты достаточно просты в реализации и требуют лишь вычисление среднего , стандартного отклонения и иногда медианы — среднее значение, если упорядочить все числа по возрастанию и взять то, которое по середине.
Правило трех сигм [32]
Если , то считаем выбросом.
Z-оценка [33] и уточненный метод Iglewicz и Hoaglin [34]
— выброс, если больше задаваемого порога, обычно равному 3. По сути переписанное правило трех сигм.
Уточненный метод заключается в следующем: для каждого числа ряда вычисляем и для получившихся значений находим медиану, обозначаемую .
— выброс, если больше порога.
Межквартильный размах [35]
Сортируем исходные числа по возрастанию, делим на двое и для каждой части находим медианные значения и .
— выброс, если .
Тест Граббса [36]
Находим минимальное и максимальное значения и для них вычисляем и . Затем выбираем уровень значимости α [37] (обычно один из 0.01, 0.05 или 0.1), заглядываем в таблицу критичных значений [38], выбираем значение для n и α. Если или больше табличного значения, то считаем соответствующий элемент ряда выбросом.
Обычно тесты требуют, чтобы исследовалось нормальное распределение, но зачастую это требование игнорируется.
Основная идея метода в том, что каждая из трех компонент экспоненциально сглаживается, используя отдельный коэффициент сглаживания, поэтому метод зачастую называется тройным экспоненциальным сглаживанием. Формулы рассчета для мультипликативного и аддиктивного сезонов есть в Википедии [42], а подробности о методе в статье на Хабре [43].
Три параметра сглаживания должны выбираться так, чтобы получаемый ряд был «близок» к исходному. На практике такая задача решается перебором, хотя RRDTool требует явного задания этих значений.
Недостаток метода: требует минимум три сезона данных.
Другой способ, примененный в Одноклассниках [44], — выбрать значения из других сезонов, соответсвующие анализируемому моменту, и проверить их совокупность на наличие выброса, например тестом Граббса.
Также Twitter предлагает AnomalyDetection [45], который на тестовых данных [46] показывает хорошие результаты. К сожалению, как и BreakoutDetection, он уже два года без обновлений.
Источник alexanderdyakonov.wordpress.com [48]
Более слабый метод состоит в том, чтобы отслеживать насколько метрики зависят друг от друга во времени и в случае, когда зависимость теряется, выдавать сообщение об аномалии. Для этого, вероятно, можно использовать один из методов.
Коэффициент корреляции Пирсона
Чем коэффициент по модулю ближе к 1, тем большая зависимость. Если коэффициент ближе к -1, то зависимость обратная, т.е. рост связан с убыванием .
Для определения похожести графиков можно оттолкнуться от алгоритма [49], использованного в KALE
Вначале исходный ряд значений, например, ряд вида [960, 350, 350, 432, 390, 76, 105, 715, 715], нормализуется: ищется максимум — ему будет соответствовать 25, и минимум — ему будет соответствовать 0; таким образом, данные пропорционально распределяются в пределе целых чисел от 0 до 25. В итоге мы получаем ряд вида [25, 8, 8, 10, 9, 0, 1, 18, 18]. Затем нормализованный ряд кодируется с помощью 5 слов: sdec (резко вниз), dec (вниз), s (ровно), inc (вверх), sinc (резко вверх). В итоге получается ряд вида [sdec, flat, inc, dec, sdec, inc, sinc, flat].
Закодировав два временных ряда таким образом, можно узнать расстояние между ними. И если оно меньше какого то порога, то считать, что графики похожи и связь имеется.
Разумеется, многие алгоритмы нахождения аномалий уже реализованы на языке R [50], предназначенном для статистической обработки данных, в виде пакетов: tsoutliers [51], strucchange [52], Twitter Anomaly Detection [45] и других [53]. Подробнее о R в статьях А вы уже применяете R в бизнесе? [54] и Мой опыт введения в R [55]. Казалось бы, подключай пакеты и используй. Однако есть проблема — задание параметров статистических проверок, которые в отличии от критических значений далеко не очевидны для большинства и не имеют универсальных значений. Выходом из данной ситуации может быть их подбор перебором (ресурсоёмко), с редким периодичным уточнением, независимо для каждой метрики. С другой стороны, большая часть аномалий, не связанных с сезонностью, хорошо определяется визуально, что наталкивает на мысль использовать нейронную сеть на отрендеренные графики.
Ниже привожу собственные алгоритмы, которые работают сопоставимо с Twitter Breakout по результатам, и несколько быстрее по скорости при реализации на Java Script.
Вначале значения обоих рядов разбиваются на несколько (около десятка) категорий. Далее для каждой категории вычисляется число , вошедших в него значений из ряда , и делится на длину ряда . Аналогично для ряда . Для каждой категории находим и затем общий максимум по всем категориям. Проверяемое значение критерия вычисляется по формуле .
Выбирается уровень значимости (один из 0.01, 0.05, 0.1) и по нему определяется критичное значение по таблице [57]. Если больше критичного значения, то считается, что группы различаются существенно.
Автор: little-brother
Источник [58]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/270774
Ссылки в тексте:
[1] Anomaly.io: https://anomaly.io/blog/
[2] cyberleninka.ru: https://cyberleninka.ru/article/v/analiz-informativnyh-priznakov-v-zadachah-obnaruzheniya-anomaliy-trafika-statisticheskimi-metodami
[3] AIMS: http://www.aimsinnovation.com
[4] Anomaly.io: https://anomaly.io
[5] CoScale: https://www.coscale.com
[6] DataDog: https://docs.datadoghq.com/guides/anomalies/
[7] Grok: http://grokstream.com/
[8] Metricly.com: https://www.metricly.com
[9] Azure: https://docs.microsoft.com/ru-ru/azure/machine-learning/team-data-science-process/apps-anomaly-detection-api
[10] X-Pack: https://www.elastic.co/products/x-pack/machine-learning
[11] Atlas: https://github.com/Netflix/atlas/wiki
[12] Banshee: https://github.com/eleme/banshee
[13] Skyline: https://github.com/etsy/skyline
[14] Oculus: https://github.com/etsy/oculus
[15] Morgoth: https://github.com/nathanielc/morgoth/
[16] отклонение Дженсена-Шеннона: https://en.wikipedia.org/wiki/Jensen%E2%80%93Shannon_divergence
[17] Prometheus: https://prometheus.io/blog/2015/06/18/practical-anomaly-detection/
[18] RRDTool: https://oss.oetiker.ch/rrdtool/
[19] Мониторинг прогнозированием, оповещения о потенциальном сбое: https://habrahabr.ru/post/135086/
[20] ~2000 репозитариев на GitHub: https://github.com/search?q=anomaly
[21] циклическую: http://www.statsoft.com/Textbook/Time-Series-Analysis#census
[22] аномальную (Catastrophic event): http://www.changes-itn.eu/Portals/0/Content/2013/Barcelonnette/Thom_Change%20detection2.pdf
[23] социальную (праздники): http://www.gks.ru/free_doc/new_site/rosstat/NMS/prez-met6.pdf
[24] Anomaly.io: https://anomaly.io/seasonal-trend-decomposition-in-r/
[25] взвешенное скользящее среднeе: https://ru.wikipedia.org/wiki/%D0%A1%D0%BA%D0%BE%D0%BB%D1%8C%D0%B7%D1%8F%D1%89%D0%B0%D1%8F_%D1%81%D1%80%D0%B5%D0%B4%D0%BD%D1%8F%D1%8F
[26] методом наименьших квадратов: https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0%D0%B8%D0%BC%D0%B5%D0%BD%D1%8C%D1%88%D0%B8%D1%85_%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82%D0%BE%D0%B2
[27] Википедия: https://en.wikipedia.org/wiki/Linear_regression
[28] Detect Seasonality using Fourier Transform in R: https://anomaly.io/detect-seasonality-using-fourier-transform-r/
[29] Простыми словами о преобразовании Фурье: https://habrahabr.ru/post/196374/
[30] «How To Identify Patterns in Time Series Data»: http://www.statsoft.com/Textbook/Time-Series-Analysis#identifying
[31] Нахождение выбросов: https://en.wikipedia.org/wiki/Outlier#Detection
[32] Правило трех сигм: https://en.wikipedia.org/wiki/68%E2%80%9395%E2%80%9399.7_rule
[33] Z-оценка: https://en.wikipedia.org/wiki/Standard_score
[34] уточненный метод Iglewicz и Hoaglin: http://www.itl.nist.gov/div898/handbook/eda/section3/eda35h.htm
[35] Межквартильный размах: https://en.wikipedia.org/wiki/Interquartile_range
[36] Тест Граббса: https://en.wikipedia.org/wiki/Grubbs%27_test_for_outliers
[37] уровень значимости α: https://ru.wikipedia.org/wiki/%D0%A1%D1%82%D0%B0%D1%82%D0%B8%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B7%D0%BD%D0%B0%D1%87%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D1%8C
[38] таблицу критичных значений: http://arhiuch.ru/lab4.html
[39] обнаружения сдвига: https://en.wikipedia.org/wiki/Step_detection
[40] Twitter Breakout Detection: https://github.com/twitter/BreakoutDetection
[41] гладко: https://anomaly.io/anomaly-detection-using-twitter-breakout/
[42] Википедии: https://en.wikipedia.org/wiki/Exponential_smoothing
[43] Хабре: https://habrahabr.ru/company/ods/blog/327242/
[44] Одноклассниках: https://habrahabr.ru/company/odnoklassniki/blog/321402/
[45] AnomalyDetection: https://github.com/twitter/AnomalyDetection
[46] тестовых данных: https://anomaly.io/anomaly-detection-twitter-r/
[47] кластерным анализом: https://en.wikipedia.org/wiki/Cluster_analysis
[48] alexanderdyakonov.wordpress.com: https://alexanderdyakonov.wordpress.com/2017/04/19/%D0%BF%D0%BE%D0%B8%D1%81%D0%BA-%D0%B0%D0%BD%D0%BE%D0%BC%D0%B0%D0%BB%D0%B8%D0%B9-anomaly-detection/
[49] алгоритма: https://habrahabr.ru/post/219377/
[50] R: https://www.r-project.org/
[51] tsoutliers: https://cran.r-project.org/web/packages/tsoutliers/tsoutliers.pdf
[52] strucchange: https://cran.r-project.org/web/packages/strucchange/index.html
[53] других: https://stats.stackexchange.com/a/270193
[54] А вы уже применяете R в бизнесе?: https://habrahabr.ru/post/340316/
[55] Мой опыт введения в R: https://habrahabr.ru/post/168817/
[56] Колмогорова-Смирнова: https://studfiles.net/preview/1582412/page:9/
[57] таблице: https://studfiles.net/preview/1582412/page:14/
[58] Источник: https://habrahabr.ru/post/344762/?utm_source=habrahabr&utm_medium=rss&utm_campaign=344762
Нажмите здесь для печати.