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

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

обнаружение выбросов:

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

обнаружение новизны:

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

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

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

estimator.fit(X_train)

Затем новые наблюдения могут быть отсортированы как входящие наблюдения или выбросы с помощью метода predict:

estimator.predict(X_test)

Входящие наблюдения помечаются как 1, а выбросы - как -1. Метод предсказания использует порог для функции необработанной оценки, вычисленной моделью. Эта функция доступна через метод score_samples, а порог можно контролировать с помощью параметра contamination.

Метод decision_function также определяется из функции оценки, таким образом, что отрицательные значения являются выбросами (outliers), а неотрицательные - входящие наблюения (inliers):

estimator.decision_function(X_test)

Обратите внимание, что neighbors.LocalOutlierFactor по умолчанию не поддерживает методы predict, decision_function и score_samples, а только метод fit_predict, так как эта модель изначально предназначался для обнаружения выбросов. Баллы аномальности обучающих выборок доступны через атрибут negative_outlier_factor_.

Если вы действительно хотите использовать neighbors.LocalOutlierFactor для обнаружения новизны, т.е. предсказывать метки или вычислять оценку аномальности новых невидимых данных, вы можете инициализировать модель с параметром novelty, установленным в True перед обучением модели. В этом случае функция fit_predict недоступна.

Предупреждение

Обнаружение новинок с помощью локального фактора выбросов

Если параметр novelty установлен в значение True, помните, что вы должны использовать predict, decision_function и score_samples только на новых неизвестных данных, а не на обучающих выборках, так как это приведет к неправильным результатам. То есть результат predict не будет совпадать с результатом fit_predict. Оценка аномальности обучающих образцов всегда доступны через атрибут negative_outlier_factor_.

Поведение neighbors.LocalOutlierFactor обобщено в следующей таблице.

Метод	Обнаружение выбросов	Обнаружение новизны
fit_predict	OK	Not available
predict	Not available	Use only on new data
decision_function	Not available	Use only on new data
score_samples	Use negative_outlier_factor_	Use only on new data
negative_outlier_factor_	OK	OK

2.7.1. Обзор методов обнаружения выбросов

Сравнение алгоритмов обнаружения выбросов в scikit-learn. Local Outlier Factor (LOF) не показывает границу принятия решения черным цветом, так как не имеет метода предсказания, применяемого к новым данным, когда он используется для обнаружения выбросов.

ensemble.IsolationForest и neighbors.LocalOutlierFactor достаточно хорошо работают на рассматриваемых здесь наборах данных. Известно, что svm.OneClassSVM чувствителен к выбросам и поэтому не очень хорошо работает для обнаружения выбросов. При этом обнаружение выбросов в высокой размерности или без каких-либо предположений о распределении исходных данных является очень сложной задачей. svm.OneClassSVM все еще может использоваться для обнаружения выбросов, но требует тонкой настройки гиперпараметра nu для обработки выбросов и предотвращения перебора. linear_model.SGDOneClassSVM предоставляет реализацию линейной одноклассовой SVM с линейной сложностью по количеству выборок. Эта реализация используется с техникой аппроксимации ядра для получения результатов, аналогичных svm.OneClassSVM, которая по умолчанию использует гауссово ядро. Наконец, covariance.EllipticEnvelope предполагает, что данные являются гауссовскими, и вычисляет эллипс. Более подробную информацию о различных оценках можно найти в примере Comparing anomaly detection algorithms for outlier detection on toy datasets и в следующих разделах.

Примеры:

• См. Comparing anomaly detection algorithms for outlier detection on toy datasets для сравнения svm.OneClassSVM, ensemble.IsolationForest, neighbors.LocalOutlierFactor и covariance.EllipticEnvelope.

• См. Evaluation of outlier detection estimators для примера, показывающего, как оценивать методы обнаружения выбросов, neighbors.LocalOutlierFactor и ensemble.IsolationForest, используя ROC-кривые из metrics.RocCurveDisplay.

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

Рассмотрим набор данных из \(n\) наблюдений из одного и того же распределения, описываемого \(p\) признаками. Рассмотрим теперь, что мы добавляем еще одно наблюдение в этот набор данных. Отличается ли новое наблюдение от остальных настолько, что мы можем сомневаться в его регулярности? (т. е. происходит ли оно из того же распределения?) Или, наоборот, оно настолько похоже на другие, что мы не можем отличить его от исходных наблюдений? Именно этот вопрос решают инструменты и методы обнаружения новизны.

В общем случае речь идет о том, чтобы узнать грубую, близкую границу, ограничивающую контур распределения исходных наблюдений, построенный во вложенном \(p\)-мерном пространстве. Затем, если последующие наблюдения лежат в пределах подпространства, ограниченного границей, они считаются происходящими из той же популяции, что и исходные наблюдения. В противном случае, если они лежат за пределами границы, мы можем сказать, что они являются аномальными с заданной уверенностью в нашей оценке.

Одноклассовая SVM была введена Шелкопфом и др. для этой цели и реализована в модуле Метод опорных векторов (Support Vector Machines - SVM) в объекте svm.OneClassSVM. Он требует выбора ядра и скалярного параметра для определения границы. Обычно выбирается ядро RBF, хотя не существует точной формулы или алгоритма для установки его параметра полосы пропускания. В реализации scikit-learn оно используется по умолчанию. Параметр nu, также известный как маржа одноклассовой SVM, соответствует вероятности нахождения нового, но обычного наблюдения за пределами границы.

Ссылки:

• Estimating the support of a high-dimensional distribution Schölkopf, Bernhard, et al. Neural computation 13.7 (2001): 1443-1471.

Примеры:

• См. One-class SVM with non-linear kernel (RBF) для визуализации границы, полученной вокруг некоторых данных с помощью объекта:class:svm.OneClassSVM.

• Species distribution modeling

2.7.2.1. Масштабирование одноклассовой SVM

Линейная онлайн-версия одноклассовой SVM реализована в linear_model.SGDOneClassSVM. Эта реализация линейно масштабируется с числом выборок и может быть использована с аппроксимацией ядра для приближения решения кернелизированной svm.OneClassSVM, сложность которой в лучшем случае квадратична по числу выборок. Подробнее см. в разделе Онлайновая одноклассовая SVM.

Примеры:

• См. One-Class SVM versus One-Class SVM using Stochastic Gradient Descent для иллюстрации аппроксимации SVM одного класса с ядром с помощью linear_model.SGDOneClassSVM в сочетании с аппроксимацией ядра.

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

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

2.7.3.1. Обучение эллиптической огибающей

Один из распространенных способов обнаружения выбросов заключается в предположении, что обычные данные имеют известное распределение (например, данные имеют гауссовское распределение). Исходя из этого предположения, мы обычно пытаемся определить “форму” данных, и можем определить выброшенные наблюдения как наблюдения, которые достаточно далеко отстоят от формы.

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

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

Примеры:

• Смотрите Robust covariance estimation and Mahalanobis distances relevance для иллюстрации разницы между использованием стандартной (covariance.EmpiricalCovariance) или робастной оценки (covariance.MinCovDet) местоположения и ковариации для оценки степени изгоев наблюдения.

Ссылки:

• Rousseeuw, P.J., Van Driessen, K. “A fast algorithm for the minimum covariance determinant estimator” 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\) - количество образцов, используемых для построения дерева (см. (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 example для иллюстрации использования IsolationForest.

• См. Comparing anomaly detection algorithms for outlier detection on toy datasets для сравнения 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. Eighth IEEE International Conference on.

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

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

Примеры:

• См. Outlier detection with Local Outlier Factor (LOF) для иллюстрации использования neighbors.LocalOutlierFactor.

• См. Comparing anomaly detection algorithms for outlier detection on toy datasets для сравнения с другими методами обнаружения аномалий.

Ссылки:

• Breunig, Kriegel, Ng, and Sander (2000) LOF: identifying density-based local outliers. Proc. ACM SIGMOD

2.7.4. Обнаружение новизны с локальным фактором выброса

Чтобы использовать neighbors.LocalOutlierFactor для обнаружения новизны, то есть предсказывать метки или вычислять оценку аномальности новых невидимых данных, необходимо инициализировать модель с параметром novelty, установленным в True перед обучением модели:

lof = LocalOutlierFactor(novelty=True)
lof.fit(X_train)

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

Предупреждение

Обнаружение новинок с помощью локального фактора выбросов

Если для novelty установлено значение True, помните, что вы должны использовать predict, decision_function и score_samples только на новых невидимых данных, а не на обучающих выборках, так как это приведет к неправильным результатам. То есть результат predict не будет совпадать с результатом fit_predict. Оценки ненормальности обучающих выборок всегда доступны через атрибут negative_outlier_factor_.

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