2.7. Обнаружение новизны и выбросов

2.7.2.1. Масштабирование One-Class SVM

Онлайн-версия линейного One-Class SVM реализована в linear_model.SGDOneClassSVM. Её сложность линейно зависит от количества образцов; с помощью приближения ядра её можно использовать для аппроксимации решения ядрового svm.OneClassSVM, сложность которого в лучшем случае квадратична по количеству образцов. Дополнительные сведения см. в разделе Онлайн-версия One-Class SVM.

Примеры

• См. Сравнение One-Class SVM и One-Class SVM со стохастическим градиентным спуском: в примере показана аппроксимация ядрового One-Class SVM с помощью linear_model.SGDOneClassSVM в сочетании с приближением ядра.

2.7.3.1. Подгонка эллиптической оболочки

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

В scikit-learn есть объект covariance.EllipticEnvelope, который подбирает устойчивую оценку ковариации данных, а затем строит эллипс вокруг центральных точек данных, игнорируя точки за пределами центральной моды.

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

Примеры

• См. Устойчивая оценка ковариации и значимость расстояний Махаланобиса: в примере показана разница между стандартной (covariance.EmpiricalCovariance) и устойчивой (covariance.MinCovDet) оценками положения и ковариации при определении степени отклонения наблюдения от нормы.
• См. Обнаружение выбросов в реальном наборе данных: в примере показана устойчивая оценка ковариации на реальном наборе данных.

Ссылки

• Rousseeuw, P.J., Van Driessen, K. «Быстрый алгоритм для оценщика минимального определителя ковариации» Technometrics 41(3), 212 (1999)

2.7.3.2. Isolation Forest

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

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

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

Случайное разбиение приводит к заметно более коротким путям для аномалий. Поэтому, если ансамбль случайных деревьев в совокупности создаёт более короткие пути для некоторых образцов, весьма вероятно, что они являются аномалиями.

Реализация ensemble.IsolationForest основана на ансамбле tree.ExtraTreeRegressor. В соответствии с оригинальной статьёй об Isolation Forest максимальная глубина каждого дерева равна \(\lceil \log_2(n) \rceil\), где \(n\) — количество образцов, использованных для построения дерева (подробности см. в [1]).

Работа алгоритма показана ниже.

ensemble.IsolationForest поддерживает warm_start=True, позволяющий добавлять деревья к уже обученной модели:

>>> from sklearn.ensemble import IsolationForest
>>> import numpy as np
>>> X = np.array([[-1, -1], [-2, -1], [-3, -2], [0, 0], [-20, 50], [3, 5]])
>>> clf = IsolationForest(n_estimators=10, warm_start=True)
>>> clf.fit(X)  # fit 10 trees
>>> clf.set_params(n_estimators=20)  # add 10 more trees
>>> clf.fit(X)  # fit the added trees

Примеры

• См. Пример IsolationForest, где показано использование IsolationForest.
• См. Сравнение алгоритмов обнаружения аномалий для выявления выбросов в искусственных наборах данных: здесь ensemble.IsolationForest сравнивается с neighbors.LocalOutlierFactor, svm.OneClassSVM (настроенным для работы в качестве метода обнаружения выбросов), linear_model.SGDOneClassSVM и методом обнаружения выбросов на основе ковариации с помощью covariance.EllipticEnvelope.

Ссылки

2.7.3.3. Локальный коэффициент выброса

Ещё один эффективный способ обнаружения выбросов в наборах данных умеренно высокой размерности — алгоритм Local Outlier Factor (LOF).

Алгоритм neighbors.LocalOutlierFactor (LOF) вычисляет оценку (называемую локальным коэффициентом выброса), отражающую степень аномальности наблюдений. Он измеряет отклонение локальной плотности заданной точки данных от плотности её соседей. Идея состоит в том, чтобы обнаружить образцы, плотность которых значительно ниже, чем у их соседей.

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

Число учитываемых соседей k (также называемое параметром n_neighbors) обычно выбирают так, чтобы оно 1) превышало минимальное количество объектов в кластере, позволяя считать другие объекты локальными выбросами относительно этого кластера, и 2) было меньше максимального количества близких объектов, которые потенциально могут быть локальными выбросами. На практике такая информация обычно недоступна, и в целом хорошо работает значение n_neighbors=20. Если доля выбросов велика (то есть превышает 10 %, как в примере ниже), значение n_neighbors следует увеличить (в примере ниже оно равно n_neighbors=35).

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

При использовании LOF для обнаружения выбросов методы predict, decision_function и score_samples недоступны, есть только метод fit_predict. Оценки аномальности обучающих образцов доступны через атрибут negative_outlier_factor_. Обратите внимание, что predict, decision_function и score_samples можно применять к новым, ранее не встречавшимся данным при использовании LOF для обнаружения новизны, то есть если параметру novelty задано значение True, однако результат predict может отличаться от результата fit_predict. См. раздел Обнаружение новизны с помощью Local Outlier Factor.

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

Эта стратегия показана ниже.

Примеры

• См. Обнаружение выбросов с помощью Local Outlier Factor (LOF), где показано использование neighbors.LocalOutlierFactor.
• См. Сравнение алгоритмов обнаружения аномалий для выявления выбросов в искусственных наборах данных, где метод сравнивается с другими методами обнаружения аномалий.

Ссылки

• Breunig, Kriegel, Ng и Sander (2000) LOF: обнаружение локальных выбросов на основе плотности. Proc. ACM SIGMOD