Обнаружение аномалий с помощью великолепного неконтролируемого алгоритма (доступно также в Scikit-learn)

Isolation Forest - блестящий алгоритм обнаружения аномалий, родившийся в 2009 году (вот оригинальная статья). С тех пор он стал очень популярным: он также реализован в Scikit-learn (см. Документацию).

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

«Почему так сложно обнаружить аномалии?»

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

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

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

  • аномалии встречаются редко;
  • аномалии новые;
  • аномалии отличаются друг от друга.

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

Что такого особенного в Isolation Forest

Традиционный подход к обнаружению аномалий был примерно таким:

  1. Опишите, как выглядят «нормальные экземпляры» (обычно это включает кластерный анализ).
  2. Пометьте все экземпляры, которые не попадают в эти профили, как выбросы.

Инновация, представленная Isolation Forest, заключается в том, что она начинается непосредственно с выбросов, а не с обычных наблюдений.

Основная идея состоит в том, что должно быть очень легко «изолировать» аномалии на основе характеристик, которые делают их уникальными.

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

Что это значит? Поясним это на примере.

Предположим, что у нас есть набор данных, содержащий данные обо всех 7 932 843 214 живущих сейчас людях. У нас есть столько переменных, сколько мы хотим: возраст, собственный капитал, место жительства, должность ...

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

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

Джеффа Безоса, который находится вне группы, проще изолировать: достаточно спросить: «Стоит ли он больше 170 миллиардов долларов?» чтобы найти его среди почти 8 миллиардов человек. С другой стороны, поскольку я намного более обыкновенен, чем Джефф Безос, вам, вероятно, понадобится как минимум 10 вопросов «верно / неверно», чтобы сузить область поиска до тех пор, пока вы не найдете меня.

Заглядывая под капот

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

import pandas as pd
df = pd.DataFrame({
    'x': [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 2.0],
    'y': [2.1, 2.4, 3.0, 2.6, 2.2, 2.8, 3.7]
}, index = ['A', 'B', 'C', 'D', 'E', 'F', 'G'])

Пункты от A до F представляют собой довольно компактное облако точек: это «нормальные» точки данных. По сравнению с этими экземплярами G, вероятно, является выбросом: он имеет аномальные значения как для x, так и для y.

Isolation Forest основан на деревьях, поэтому давайте построим дерево на основе этих данных:

Обратите внимание, что это дерево было выращено случайным образом.

Самым фундаментальным понятием здесь является глубина листа, на котором находится каждый элемент. Например, в этом дереве наблюдение под названием G (наш выброс) находится на глубине 1 (например, на 1 уровне от корневого узла), тогда как C находится на глубине 3.

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

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

Изолированный лес в Scikit-learn

Давайте посмотрим на пример использования реализации Scikit-learn.

from sklearn.ensemble import IsolationForest
iforest = IsolationForest(n_estimators = 100).fit(df)

Если мы возьмем первые 9 деревьев из леса (iforest.estimators_[:9]) и построим их график, мы получим следующее:

Взглянув на эти первые 9 деревьев, мы уже можем увидеть закономерность: G обычно находится на гораздо меньшей глубине (в среднем 1,44), чем любая другая точка. Действительно, вторая точка - А со средней глубиной 2,78.

По идее, алгоритм работает именно так: более низкая средняя глубина означает более высокую вероятность выброса.

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

где n - количество экземпляров, h (x) - глубина, на которой точка данных находится в конкретном дереве (E (h (x) ) - его среднее значение по разным деревьям), а H - армоническое число.

s (x, n) - это число от 0 до 1, где чем выше оценка, тем больше вероятность, что это выброс.

Примечание. Реализация Scikit-learn возвращает противоположное баллу, определенному выше. Таким образом, сказанное выше остается в силе, но с отрицательным знаком.

В нашем небольшом наборе данных оценки выражаются следующим образом:

scores = iforest.score_samples(df)

Давайте посмотрим, как оценивается каждый из наших пунктов:

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

Помимо нашего набора данных о игрушках, интересно смоделировать, что алгоритм даст в некоторых конкретных случаях. Например, если мы возьмем некоторые точки данных, которые примерно образуют форму круга от двух переменных (x и y), это контурный график оценок, которые мы бы получили через Лес изоляции:

Интересно, что выбросами могут быть не только самые крайние зоны, но и часть в центре круга, поскольку это необычная комбинация x и y .

Спасибо за чтение! Надеюсь, этот пост был вам полезен.

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