Алгоритмы поиска аномалий HBOS и ECOD28.03.2025 15:16

Привет, Хабр! Меня зовут Михаил Васильев, я старший специалист по машинному обучению в компании Makves (входит в группу компаний «Гарда»). По работе мне часто приходится заниматься поиском аномалий в данных, однако я заметил, что в русскоязычном интернете этой задаче посвящено очень мало материалов. В частности, я не нашел хорошего разбора различных алгоритмов поиска аномалий, где были бы описаны их плюсы и минусы.

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

Рассмотрим:

• аномалии,

• метод трех сигм,

• алгоритм HBOS,

• алгоритм ECOD.

Аномалии

Если отталкиваться от определения, данного в книге D. Hawkins. Identification of Outliers, аномалии — это данные, которые настолько отличаются от других (нормальных) данных, что кажется, что они получены из иного источника. Например, поведение хакера в корпоративной сети будет сильно отличаться от поведения простых работников компании. Обращение мошенника с деньгами на скомпрометированном счете будет сильно отличаться от действий нормального пользователя. Раннее обнаружение подобных аномалий крайне важно для предотвращения финансовых и репутационных потерь.

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

Во-первых, аномалии по природе своей довольно редки. Решение задачи с сильно несбалансированными классами требует особых подходов, например, генерации синтетических данных, under-sampling или over-sampling.

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

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

Именно поэтому задача поиска аномалий часто решается через методы машинного обучения без учителя (unsupervised learning). В некоторых случаях задачу поиска аномалий удобно свести к задаче определения степени аномальности (anomaly score). Уже затем мы сможем отобрать, например, 5% самых аномальных записей для анализа, либо подобрать какое-либо пороговое значение, при превышении которого запись будет считаться аномалией.

Рассмотрим несколько алгоритмов, которые позволят нам получить anomaly score на не размеченных данных.

Метод трех сигм

Предположим, мы работаем с нормально распределенными одномерными данными. Для расчета степени аномальности можно использовать количество стандартных отклонений от среднего. В этом случае нам помогут хорошо известные свойства нормального распределения, например то, что 99,7% данных лежат в пределах трех стандартных отклонений от среднего. Просто, понятно, легко реализуемо. Эмпирически подбираем пороговое значение и можно работать.

Алгоритм HBOS

Однако ситуация меняется, если наше распределение не похоже на нормальное. Для примера рассмотрим гистограмму ниже.

Гистограмма примерно отображает распределение возрастов сотрудников на моей первой работе. Там было много сотрудников предпенсионного возраста и «вчерашних» студентов, но работников среднего возраста почти не было. На гистограмме видно, что к аномалиям можно отнести сотрудников возрастной категории от 35 до 50 лет (их очень мало), но метод трех сигм в данной ситуации бесполезен — нормальные данные (возрастные категории от 20 до 35 и от 50 до 70 лет) получат большую степень аномальности, так как они лежат дальше от среднего значения (на гистограмме показано пунктирной линией).

Что же делать? Давайте попробуем пойти простым путем. На нашей гистограмме самые высокие столбцы соответствуют нормальным данным, а низкие — аномалиям. Давайте представим гистограмму в виде таблицы, в первой колонке запишем диапазоны столбцов (их еще называют бины), а во второй — количество сотрудников, попадающих в диапазон.

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

Мы получили вероятности, с ними работать намного приятнее. Тут стоит учесть, что наши данные скорее всего многомерны: помимо возраста мы можем знать, например, данные о зарплате или трудовом стаже сотрудника. Авторы оригинальной статьи предлагают упростить вычисления и сделать предположение, что признаки не зависят друг от друга. В самом деле, вероятность двух независимых событий рассчитывается как произведения вероятностей каждого события. Мы могли бы просто перемножить полученные значения для каждого из признаков, однако в этом случае легко столкнуться с тем, что при перемножении очень маленьких чисел мы рискуем выйти за пределы точности чисел с плавающей запятой. Чтобы обойти потенциальную проблему, применим популярный математический трюк. Воспользуемся следующим свойством логарифма: log (xy) = log (x) + log (y). Заменим произведение вероятностей на сумму логарифмов.

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

Нанесем наш результат на исходную гистограмму.

Получилось ровно то, что нам нужно: бины с аномальными данными получают высокую степень аномальности, их легко отличить от бинов с нормальными данными. Мы только что разобрали алгоритм HBOS (Histogram Based Outlier Selection). Этот метод быстрый и легко реализуется с нуля, хотя имеет и свой недостаток: результаты его работы сильно зависят от выбора числа бинов в изначальной гистограмме. Если мы разобьем данные на слишком много бинов, эффективность метода упадет, так как нормальные данные будут размечаться с более высокой степенью аномальности. А если использовать слишком мало бинов, то аномальные данные будут теряться в широких бинах нормальных данных.

Алгоритм ECOD

Существует способ отказаться от необходимости выбора числа бинов. Для этого перейдем от использования гистограммы к функции распределения.

Функция распределения — это статистический инструмент, который помогает понять, как распределены значения в наборе данных. Она показывает вероятность того, что случайно выбранное значение будет меньше или равно определенному уровню. Например, если у вас есть данные о ежедневных продажах в магазине, функция распределения может показать, какова вероятность того, что в случайно выбранный день объем продаж будет меньше 1 000 единиц товара.

На практике, когда у нас есть ограниченный набор данных, мы часто используем выборочную эмпирическую функцию распределения (ЭФР). Она строится на основе реальных данных и показывает, какая доля данных имеет значение меньше или равное заданному уровню.

Чтобы построить выборочную ЭФР, нужно выполнить следующие шаги:

1.          Сортируем данные: располагаем все значения по порядку.

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

Разберем на примере с данными о ежедневных продажах. На верхнем графике представлена гистограмма распределения продаж за день. Она показывает, как часто встречаются различные уровни продаж. На нижнем графике изображена выборочная эмпирическая функция распределения. Она показывает, какая доля дней имеет продажи меньше или равные определенному значению. Например, если посмотреть на точку, где продажи равны 1000 единицам, можно увидеть, что примерно 50% дней имеют продажи меньше или равные этому значению. Таким образом, ЭФР позволяет анализировать реальные данные без необходимости знать теоретическое распределение.

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

Нормальные данные сосредоточены в нижнем правом углу (от 2 до 4 попугаев и от -4 до -2 удавов), а вокруг них довольно много шума и аномалий. Построим гистограмму и график ЭФР для каждого из признаков по отдельности.

На нижнем графике наглядно видно, что значительной части аномалий (всему левому «хвосту») соответствуют низкие значения ЭФР. У нормальных данных значения лежат в диапазоне примерно от 0,2 до 0,9. Теперь посмотрим на удавов.

Здесь с нормальными данными ситуация аналогична (в диапазоне примерно от 0,1 до 0,8), а вот большая часть аномалий имеет высокие значения ЭФР.

Теперь для каждой записи рассчитаем, во-первых, значение ЭФР, и во-вторых, значение 1 ‒ ЭФР (ведь ЭФР всегда лежит в диапазоне от 0 до 1, так что для аномалий одно из этих значений точно будет очень низким). В таблице ниже представлены расчеты для части записей по признаку «удавы».

Затем рассчитаем отрицательные значения логарифмов ЭФР и 1 ‒ ЭФР (в оригинальной статье учитывается еще и скошенность распределения, но для простоты объяснения мы опустим этот момент). Сложим их с отрицательными значениями логарифмов по другим признакам (по попугаям).

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

Все вычисления готовы, посмотрим на наши данные, размеченные с помощью алгоритма ECOD.

В этой разметке четко выделился кластер нормальных данных, у записей на удалении от кластера степень аномальности выше. И для работы алгоритма не требуется подбирать гиперпараметры (например, размер бина, как в случае с HBOS)!

Мы рассмотрели работу двух важных алгоритмов для поиска аномалий: HBOS и ECOD. Оба алгоритма обладают несколькими преимуществами:

1.          Простота понимания и реализации.

2.          Высокая скорость работы.

3.          Объяснимость.

Сама архитектура обоих алгоритмов позволяет нам легко (даже без использования SHAP values) интерпретировать результаты их работы.

К недостаткам можно отнести тот факт, что мы делаем предположение о независимости признаков. Но для задачи поиска аномалий это условие часто не выполняется. Аномальна ли погода в 29° в Москве? Нет. Аномальная ли эта погода в Москве в ноябре? Да.

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

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

1.      Charu C. Aggarwal. Outlier Analysis, Second Edition (Springer, 2017, ISBN 978–3–319–47578–3);

2.      Kishan G. Mehrotra, Chilukuri K. Mohan, HuaMing Huang. Anomaly Detection Principles and Algorithms (Springer, 2017, ISBN 978–3–319–67526–8);

3.      Jiawei Han, Micheline Kamber, Jian Pei. Chapter 12. Outlier Detection // Data Mining Concepts and Techniques, Third Edition (Morgan Kaufmann, 2012, ISBN 978–0–12–381479–1).