Привет, Хабр!

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

Сегодня предлагаю разобрать еще один интересный алгоритм: Isolation Forest, а также немного углубиться в проблематику задачи.

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

В некоторых работах используют следующую классификацию аномалий:
• глобальные (global)
• контекстные (contextual)
• коллективные (collective)

Глобальные аномалии

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

Пример из реальной практики: если большинство температурных показателей в регионе колеблются в пределах 10–25 °C, значение 50 °C будет считаться глобальной аномалией. Такие выбросы легко обнаружить, так как они не соответствуют общему распределению данных.

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

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

Пример: температура 29 °C в Москве летом — нормальное явление. Однако та же температура в ноябре становится контекстной аномалией, так как сочетание признаков «ноябрь» и «29 °C» противоречит типичным сезонным паттернам.

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

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

Пример: если служба поддержки обычно получает 2–3 обращения в час, внезапный всплеск до 10 обращений за тот же период будет коллективной аномалией. Каждое обращение само по себе обычное, но их высокая концентрация во времени указывает на проблему.

Ансамбли

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

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

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

Что это дает? Усредняя предсказания, мы также усредняем и ошибки. Поскольку у некоторых моделей ошибки были разнонаправленными, они компенсируют друг друга, и общая ошибка уменьшается.

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

Алгоритм Isolation Forest

Попробуем применить ансамблирование для поиска аномалий.

Данные имеют только два признака, измеряемые в «удавах» и «попугаях». Нормальные данные образуют заметный кластер, располагающийся в области примерно от 2 до 4 «попугаев» и от -2 до -4 «удавов». Вокруг нормальных данных расположено множество аномалий и шум.

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

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

In [1]: import random
In [2]: axes = ['попугаи', 'удавы']
In [3]: random.choice(axes)
Out[3]: 'удавы'

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

In [4]: random.uniform(df['удавы'].min(), df['удавы'].max())
Out[4]: 3.954197818641566

Теперь построим на графике пороговую линию с выбранным значением.

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

In [5]: random.choice(axes)
Out[5]: 'попугаи'
In [6]: random.uniform(df_b['попугаи'].min(), df_b['попугаи'].max())
Out[6]: -3.7345546743319455

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

In [7]: random.choice(axes)
Out[7]: 'попугаи'
In [8]: random.uniform(df_bl['попугаи'].min(), df_bl['попугаи'].max())
Out[8]: 4.55352143693694

Теперь в правой:

In [7]: random.choice(axes)
Out[7]: 'удавы'
In [8]: random.uniform(df_br['попугаи'].min(), df_br['попугаи'].max())
Out[8]: -0.6572094533790986

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

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

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

Глубину дерева, на которой происходит изоляция точки, можно рассматривать как индекс аномальности данных, только с обратным знаком. В этом случае аномальные записи будут получать высокий индекс (пусть и отрицательный: -1, -2, -3), а нормальные — низкий (например: -20, -30 …).

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

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

Однако возникает вопрос, насколько хороши полученные предсказания. Ведь для построения моделей мы просто делили пространство данных линейными гиперплоскостями, насколько финальная модель сможет описывать сложные закономерности в данных? С использованием библиотеки scikit-learn построим «контурную карту» аномальности.

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

Недостатки метода

По сравнению с методами HBOS и ECOD он несколько медленнее и не имеет встроенных способов интерпретации результатов. Объяснить предсказания индекса аномальности поможет метод SHAP-значений, а некоторое снижение скорости с лихвой компенсируется возможностью обнаружения контекстных аномалий.

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

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

В данном случае методу явно не хватило «мощности», чтобы хорошо описать нормальные данные. Например, модель посчитала бы нормальными данные, находящиеся в диапазоне от -1 до 1 удава, но не лежащие непосредственно на синусоиде. При определенных задачах это можно посчитать за ошибку.

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

Заключение

Isolation Forest — это мощный и элегантный алгоритм для поиска аномалий, который сочетает в себе простоту реализации и высокую эффективность, особенно на больших данных. В отличие от HBOS и ECOD, он не опирается на явные статистические свойства распределения, а вместо этого использует идею изоляции аномальных точек через случайные разбиения пространства. Это позволяет ему успешно находить не только глобальные, но и контекстные аномалии.

Главное преимущество Isolation Forest — его интуитивность и способность работать без предварительных предположений о данных. Если вам нужно быстро проанализировать новый датасет на наличие аномалий, начать стоит именно с него. А для интерпретации результатов можно воспользоваться методами объяснимого ML, такими как SHAP-значения.

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

Для более глубокого понимания работы алгоритма изоляционного леса можно ознакомится со статьями авторов метода:

Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. Isolation forest. In Data Mining, 2008.

Liu, Fei Tony, Ting, Kai Ming and Zhou, Zhi-Hua. “Isolation-based anomaly detection.” ACM Transactions on Knowledge Discovery from Data

Еще больше вопросов защиты данных приглашаю обсудить на конференции «Сохранить всё: безопасность информации», которая пройдет 16 октября в Москве в конгресс-центре Soluxe.