Изолирующий лес – неконтролируемый алгоритм обнаружения аномалий, который может обнаруживать выбросы в наборе данных с невероятной скоростью.
Изолирующий лес – это простой, но невероятный алгоритм, способный очень быстро выявлять выбросы или аномалии в наборе данных. Я должен сказать, что понимание этого инструмента является обязательным для любого начинающего специалиста по данным. В этой статье я кратко рассмотрю теории, лежащие в основе алгоритма, а также его реализации.
Его реализация Python от Scitkit Learn набирает огромную популярность благодаря своим возможностям и простоте использования. Но прежде чем мы перейдем непосредственно к реализации. Для нас всегда лучше изучить его варианты использования и его теорию. Тем не менее, не стесняйтесь сразу переходить к части реализации!
Некоторые теории
Во-первых, что такое аномалия?
Аномалия (выброс) может быть описана как точка данных в наборе данных, которая значительно отличается от других данных или наблюдений. Это может произойти по нескольким причинам:
- Выброс может указывать на плохие данные, которые являются неверными, или эксперимент может быть проведен неправильно.
- Выброс может быть вызван случайным изменением или может указывать на что-то интересное с научной точки зрения.
Это довольно упрощенная версия аномалии. Тем не менее, оба события — это то, что ученые данных хотели бы понять и углубиться в них.
Почему обнаружение аномалий?
Причина, по которой мы хотели бы углубиться в аномалии, заключается в том, что эти точки данных либо запутают вас, либо позволят вам определить что-то значимое.
В случае простой линейной регрессии плохой выброс может увеличить дисперсию в нашей модели и еще больше снизить способность нашей модели улавливать данные. Выбросы приводят к тому, что модели регрессии (особенно линейные) изучают искаженное понимание в сторону выброса.
Обзор работы Isolation Forest
Традиционно другие методы пытались построить профиль нормальных данных, а затем определить, какие точки данных не соответствуют профилю как аномалии.
Отличительной особенностью Isolation Forest является то, что он может напрямую обнаруживать аномалии с помощью изоляции (насколько далеко точка данных находится от остальных данных). Это означает, что алгоритм может работать с линейной временной сложностью, как и другие модели, связанные с расстоянием, такие как K-ближайшие соседи.
Алгоритм работает, опираясь на наиболее очевидные атрибуты выброса:
- Будет только несколько выбросов.
- Выбросы будут другими
Isolation Forest делает это, вводя (ансамбль) двоичных деревьев, которые рекурсивно генерируют разделы путем случайного выбора функции, а затем случайным выбором значения разделения для функции. Процесс разделения будет продолжаться до тех пор, пока он не отделит все точки данных от остальных выборок.
Так как из экземпляра для каждого дерева выбирается только один признак. Можно сказать, что максимальная глубина дерева решений на самом деле равна единице. Фактически, базовая оценка Изолирующего леса на самом деле является чрезвычайно случайным деревом решений (ExtraTrees) для различных подмножеств данных.
Пример одиночного дерева в изолированном лесу можно увидеть ниже.
Учитывая атрибуты выброса, упомянутые выше, мы можем заметить, что выбросу потребуется в среднем меньше разделов для их изоляции по сравнению с обычными выборками. Затем каждая точка данных получит оценку, основанную на том, насколько легко они изолируются после X раундов. Точки данных с аномальными оценками будут помечены как аномальные.
Подробности
Говоря более формально, мы рекурсивно делим каждый экземпляр данных, случайным образом выбирая атрибут q и значение разделения p (в пределах минимального максимума атрибута q), пока все они не будут полностью изолированы. Затем изолированный лес предоставит ранжирование, отражающее степень аномалии каждого экземпляра данных в соответствии с длиной их пути. Рейтинг или баллы называются баллами аномалий, которые рассчитываются следующим образом:
H(x): количество шагов до полной изоляции экземпляра данных x.
E[H(x)] : среднее значение H(x) из набора изолированных деревьев.
Метрики имеют смысл, но одна проблема заключается в том, что максимально возможные шаги iTree растут в порядке n, в то время как средние шаги растут только в порядке log n. Это приведет к проблемам, когда шаги нельзя сравнивать напрямую. Следовательно, необходимо ввести нормировочную константу, изменяющуюся на n.
c(n), константа нормализации длины пути со следующей формулой:
где H(i) — номер гармоники, который можно оценить как ln(i) + 0,5772156649 (постоянная Эйлера).
Полное уравнение оценки аномалии:
Следовательно, если мы пропустим весь набор данных через изолированный лес, мы сможем получить его показатель аномалии. Используя показатель аномалии s, мы можем сделать вывод, существуют ли аномалии всякий раз, когда есть экземпляры с показателем аномалии, очень близким к единице. Любая оценка ниже 0,5 будет считаться нормальным экземпляром.
Примечание.
В реализации sklearn оценки аномалий противоположны оценкам аномалий, определенным в исходной статье. Далее они вычитаются с константой 0,5. Это делается для того, чтобы легко идентифицировать аномалии (отрицательные баллы идентифицируются с аномалиями) Подробнее
Реализация изолированного леса
Закончили со всеми теориями? Давайте определим некоторые выбросы.
Во-первых, мы быстро импортируем некоторые полезные модули, которые будем использовать позже. Мы генерируем набор данных со случайными точками данных, используя функцию make_blobs().
import numpy as np import pandas as pd import matplotlib.pyplot as plt from sklearn.datasets import make_blobs data, _ = make_blobs(n_samples=500, centers=1, cluster_std=2, center_box=(0, 0)) plt.scatter(data[:, 0], data[:, 1]) plt.show()
Мы можем легко увидеть некоторые выбросы, так как это только вариант использования 2-D. Это хороший выбор для доказательства того, что алгоритм работает. Обратите внимание, что алгоритм можно без проблем использовать для набора данных с несколькими функциями.
Мы инициализируем объект изолированного леса, вызывая IsolationForest().
Используемые здесь гиперпараметры в основном установлены по умолчанию и рекомендованы в оригинальной статье.
Количество деревьев определяет размер ансамбля. Мы обнаружили, что длины путей обычно сходятся задолго до t = 100. Если не указано иное, мы будем использовать t = 100 в качестве значения по умолчанию в нашем эксперименте.
Эмпирически мы обнаружили, что установка выборки подмножества на 256 обычно обеспечивает достаточно деталей для обнаружения аномалий в широком диапазоне данных.
— Фей Тони Лю, Кай Мин Тинг (автор оригинальной статьи, Isolation Forest)
- Здесь N_estimators обозначает количество деревьев, а максимальная выборка здесь обозначает выборку подмножества, используемую в каждом раунде.
- Max_samples = 'auto' устанавливает размер подмножества как минимум (256, num_samples).
- Параметр загрязнения здесь означает долю выбросов в наборе данных. По умолчанию пороговое значение оценки аномалии будет таким же, как и в оригинальной статье. Однако мы можем вручную исправить долю выбросов в данных, если у нас есть какие-либо предварительные знания. Мы установили его на 0,03 здесь для демонстрационных целей.
Затем мы подгоняем и прогнозируем весь набор данных. Он возвращает массив, состоящий из [-1 или 1], где -1 означает аномалию, а 1 — нормальный экземпляр.
iforest = IsolationForest(n_estimators = 100, contamination = 0.03, max_samples ='auto)
prediction = iforest.fit_predict(data)
print(prediction[:20])
print("Number of outliers detected: {}".format(prediction[prediction < 0].sum()))
print("Number of normal samples detected: {}".format(prediction[prediction > 0].sum()))
Затем мы нанесем на график выбросы, обнаруженные Isolation Forest.
normal_data = data[np.where(prediction > 0)]
outliers = data[np.where(prediction < 0)]
plt.scatter(normal_data[:, 0], normal_data[:, 1])
plt.scatter(outliers[:, 0], outliers[:, 1])
plt.title("Random data points with outliers identified.")
plt.show()
Мы видим, что он работает довольно хорошо и идентифицирует точки данных по краям.
Мы также можем вызвать solution_function(), чтобы вычислить показатель аномалии для каждой точки данных. Таким образом, мы можем понять, какие точки данных более ненормальны.
score = iforest.decision_function(data) data_scores = pd.DataFrame(list(zip(data[:, 0],data[:, 1],score)),columns = ['X','Y','Anomaly Score']) display(data_scores.head())
Мы выбираем 5 лучших аномалий, используя оценки аномалий, а затем снова наносим их на график.
top_5_outliers = data_scores.sort_values(by = ['Anomaly Score']).head()
plt.scatter(data[:, 0], data[:, 1])
plt.scatter(top_5_outliers['X'], top_5_outliers['Y'])
plt.title("Random data points with only 5 outliers identified.")
plt.show()
Еда на вынос
Изолирующий лес — это принципиально другая модель обнаружения выбросов, которая может изолировать аномалии с большой скоростью. Он имеет линейную временную сложность, что делает его одним из лучших для работы с большими объемами данных.
Он основан на концепции, согласно которой, поскольку аномалий несколько и они разные, их легче изолировать по сравнению с нормальными точками. Его реализацию на Python можно найти на странице sklearn.ensemble.IsolationForest.
Спасибо, что нашли время в своем плотном графике, чтобы посидеть со мной и насладиться этим прекрасным алгоритмом.
Ссылка
Изолирующий лес Фей Тони Лю, Кай Мин Тинг Гиппсленд Школа информационных технологий Университета Монаша, Виктория, Австралия.
