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 с использованием стохастического градиентного спуска для иллюстрации приближения метода kernelized 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. Изоляция леса

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

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

Эта длина пути, усредненная по лесу таких случайных деревьев, является мерой нормальности и нашей функции принятия решений.

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

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

Этот алгоритм проиллюстрирован ниже.

В 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.

Ссылки

• Liu, Fei Tony, Ting, Kai Ming and Zhou, Zhi-Hua. «Изоляция леса». Data Mining, 2008. ICDM’08. Восьмая международная конференция IEEE.

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. См. Обнаружение новизны с использованием локального фактора выбросов.

Эта стратегия проиллюстрирована ниже.

Примеры

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

Ссылки

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