вторник, 27 декабря 2022 г.

Как быстро найти аномалии в числовых рядах с помощью метода Хампеля

Копия статьи. Оригинал тут:
https://forworktests.blogspot.com/2022/12/blog-post.html

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

  • очистка зашумлённых данных в датасайнс (Data Science);
  • фильтрация выбросов в обучающей выборке для нейросетей в машинном обучении (Machine Learning);
  • поиск аномальной сетевой хакерской активности, при мониторинге трафика и событий в  кибербезопасности (Cybersecurity);
  • выявление выбросов или хвостов в потоке биржевых данных в алгоритмической торговле (Algorithmic Trading);
  • а также в любых задачах на поиск аномалий, где данные могут быть представлены в виде числового ряда.
Понятия числового ряда в математическом анализе и в статистике отличаются. Мы принимаем под числовым рядом его статистическое понимание, то есть конечную последовательность чисел (аналог выборки). Существуют различные толкования аномалии в числовых рядах. Их мы рассмотрим далее.

Также в статье показаны примеры, как быстро и эффективно найти аномалии в числовых рядах с помощью модифицированного метода Хампеля (Hampel F.R.).

Понятие аномалии числового ряда

Для одномерных данных оценка выбросов широко исследуется в статистической литературе. Традиционно наиболее полезными оценками для характеристики вариативности данных считаются выборочное среднее (sample mean) и дисперсия (variance) выборки. Они дают хорошую оценку местоположения и разброса данных в выборке, но только если выбросы её «не загрязняют». Даже если данные содержат только одно наблюдение, которое значительно отличается от остальных в выборке, то выборочное среднее может также значительно отклоняться от среднего в выборке без этого выброса.

Чтобы измерить устойчивость выбранного метода статистической оценки к выбросам, Хампель ввёл понятие точки разрыва (breakdown point). Точка разрыва — это наибольший процент «загрязнённых данных» (доля неправильных наблюдений или выбросов), которые выбранный метод может обработать, прежде чем начнёт выдавать неверный результат. Это могут быть произвольно большие аберрантные (отклоняющиеся от нормы, ошибочные) значения.

Интуитивно можно понять, что точка разрыва не может превышать 50%, потому что, если более половины наблюдений будут «загрязнены», то невозможно отличить основное распределение ряда от загрязняющего распределения. Следовательно, максимальная доля выбросов для точки разрыва равна 0.5. Существуют примеры статистик, которые достигают максимального значения для точки разрыва. Например, она равна 0.5 для медианы (Median). А для выборочного среднего она равна 1/n, где n — объём выборки.

Обычно считается, что чем выше значение точки разрыва, тем метод статистической оценки надёжнее. Статистику с высоким значением точки разрыва иногда называют устойчивой статистикой.

Чтобы более надёжно оценивать местоположение и разброс элементов выборки, часто рекомендуют комбинировать медиану и среднее абсолютное отклонение (MAD, Median Absolute Deviation). Именно они лежат в основе метода фильтрации выборки на выбросы по Хампелю [1].

Значение MAD вычисляется так:

MAD (X) = Median ( | x1 − Median (X) | , …, | xn − Median (X) | ),                                                ( 1 )

где X — выборка из n наблюдений x1, …, xn.

По Хампелю, под выбросом (outlier) выборки понимается такое число x из выборки X, модуль разности которого и медианы выборки больше, чем MAD выборки, вычисленное по формуле (1) и умноженное на специальный коэффициент k (scale factor), зависящий от распределения (≈1.4826 для нормального) [2].

На практике для построения фильтра выбросов Хампеля это определение модифицируется с использованием скользящих окон (sliding windows) и параметра s (sigma), порогового количества стандартных отклонений. Это значит, что медиана и MAD вычисляются для всех скользящих окон, состоящих из элементов выборки. Далее все модули разности элементов выборки и медианы сравниваются с MAD, умноженный на коэффициент k и умноженный на параметр s [3]. Более высокий порог s стандартного отклонения делает фильтр более щадящим, более низкий порог идентифицирует больше чисел как выбросы.

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

Определение 1. Под аномалией (anomaly) числового ряда понимается такое число x из ряда X, которое по модулю отличается от медианы скользящего окна более чем в s раз от MAD этого окна, умноженного на коэффициент k.

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

Все аномалии ряда образуют его некоторое подмножество A:

A = { a | | a − Median (Xi) | > s ∙ k ∙ MAD (Xi) },                                                                              ( 2 )

где a — аномальный элемент из X, вычисленный согласно определению 1, Х — исходный числовой ряд, Xi — ряд чисел i-го скользящего окна, всего окон: ( n − w + 1 ), где w — размер окна.

Фильтр аномалий числового ряда определим как функцию:

F: X → { True, False }.  F (xi) = True, если xi ∈ A; False, если xi ∉ A.                                           ( 3 )

Здесь Х — исходный числовой ряд, состоящий из n элементов xi, A — множество аномалий (2).

Фильтрация числового ряда на аномалии методом Хампеля

Для фильтрации числового ряда на наличие в нём аномалий, предлагается использовать Python-реализацию функции HampelFilter(). Эта функция позволяет обнаружить аномалию среди значений любого числового ряда, используя метод фильтрации по Хампелю. Фильтр обнаруживает аномалии, определяемые согласно (2). Настраиваемые параметры в этой функции-фильтре: window (переменная w из формул выше) — размер скользящего окна (по умолчанию 5), sigma (переменная s) — пороговое количество стандартных отклонений (по умолчанию 3), scaleFactor (переменная k) — специальный коэффициент, зависящий от распределения ряда (по умолчанию 1.4826).

Функция фильтрации HampelFilter() возвращает новый ряд F, согласно (3) состоящий из значений True или False, где True означает наличие аномального элемента на соответствующей позиции в исходном ряду.

Примеры входных данных и результатов, HampelFilter(window=5, sigma=3, scaleFactor=1.4826)

Входные данные             Вывод функции

[10, 10, 10, 10, 10]       [False, False, False, False, False]
[1, 10, 10, 10, 10]        [True, False, False, False, False]
[1, 5, 10, 10, 10]         [True, True, False, False, False]
[1, 5, 1, 1, 1]            [False, True, False, False, False]

Примеры входных данных и результатов, HampelFilter(window=3, sigma=3, scaleFactor=1.4826)

Входные данные             Вывод функции

[1, 5, 1, 1, 1]            [False, True, False, False, False]
[1, 10, 10, 1, 10, 1]      [True, False, False, False, False, False]
[1, 10, 10, 10, 10, 1]     [True, False, False, False, False, True]
[1, 1, 1, 10, 10, 10]      [False, False, False, False, False, False]

Поиск индекса первого аномального элемента

На практике часто бывает нужно определить только первый аномальный или первый среди наибольших в числовом ряду элемент. Для этого можно использовать Python-реализацию функции HampelAnomalyDetection(). Эта функция возвращает минимальный индекс элемента в списке найденных аномалий или индекс первого максимального элемента во входном ряду, если его индекс меньше индекса аномального элемента. Если в числовом ряду нет аномалий или все элементы равны (нет максимумов), то возвращается None.

Примеры входных данных и результатов, HampelAnomalyDetection() со значениями по умолчанию

Входные данные             Вывод функции

[1, 1, 1, 1, 111, 1]       4
[1, 1, 10, 1, 1, 1]        2
[111, 1, 1, 1, 1, 1]       0
[111, 1, 1, 1, 1, 111]     0
[1, 11, 1, 111, 1, 1]      1
[1, 1, 1, 111, 99, 11]     3
[-111, 1, 1, 1, 1]         0
[1, 2, 1, -1, 1]           1
[1]                        None
[1, 2]                     None
[1, 1, 1, 1, 1, 1]         None

Фильтрация биржевых цен на аномалии

Посмотреть использование указанных выше функций можно на примере задачи поиска выбросов в биржевых данных. Для этого мы сгенерировали временные ряды с данными, похожими на случайные биржевые цены, и аномалии в них при помощи библиотеки PriceGenerator, а затем применили к данным эти функции. Сами функции — в библиотеке TKSBrokerAPI (модуль TradeRoutines).

Решение задачи было реализовано на Jupyter Notebook: HampelFilteringExample.ipynb. Аномалии на графике цен после анализа методом Хампеля можно промаркировать, например, как показано на иллюстрации ниже.

Как видно невооружённым глазом, в ряду явно присутствуют выбросы, хвосты сверху и снизу у некоторых свечей. Нас интересуют не все такие выбросы, а только слишком длинные хвосты. Для нас это признаки ценовой аномалии. Фильтр Хампеля справился с обнаружением аномалий в ряду из 75 свечей при величине скользящего окна (параметр sliding window) равного размеру ряда, количестве стандартных отклонений равном 3 (параметр sigma) и постоянном коэффициенте, характеризующем нормальное распределение, равном 1.4826 (параметр scale factor). Аналогичным образом можно проанализировать на аномалии и размеры тел свечей.

Выводы

Конечно, у метода Хампеля есть и недостатки. Например, при реализации алгоритма можно столкнуться с тем, что присутствующие аномалии в первом и последнем элементах ряда по оригинальному алгоритму будут проигнорированы. Это связано с использованием скользящего окна. Чтобы обойти проблему, нам пришлось предварительно расширять числовые ряды спереди и сзади на размер этого окна. Только после этого удалось обнаружить аномалии и в первых, и в последних элементах исходных рядов.

Однако на практике фильтр Хампеля оказывается чрезвычайно эффективным. Благодаря современным библиотекам, таким как Pandas, он справляется с достаточно большими числовыми рядами на десятки тысяч элементов за считанные секунды, а также легко поддаётся оптимизации и распараллеливанию (с помощью CUDA Python и декоратора @cuda.jit от Numba, либо Python Multiprocessing ThreadPool).

Таким образом, если у вас стоит задача поиска аномалий в числовом ряду, попробуйте посмотреть в сторону их фильтрации методом Хампеля. Он даёт быстрые результаты, а также прост в понимании и реализации.


Авторы: Тимур Гильмуллин, к.т.н., Мансур Гильмуллин, к.п.н.

Источники:

  1. Hampel F. R. The influence curve and its role in robust estimation. Journal of the American Statistical Association, 69, 382–393, 1974.
  2. Hancong Liu, Sirish Shah and Wei Jiang. On-line outlier detection and data cleaning. Computers and Chemical Engineering. Vol. 28, March 2004, pp. 1635–1647.
    Link: https://sites.ualberta.ca/~slshah/files/on_line_outlier_det.pdf
  3. Lewinson Eryk. Outlier Detection with Hampel Filter. September 26, 2019.
    Link: https://towardsdatascience.com/outlier-detection-with-hampel-filter-85ddf523c73d
Исходный код модулей, используемых в примерах:

Автор: на
Ярлыки: , , , , , , , , ,