Поиск аномалий (Anomaly Detection)

В этом посте поговорим об одной важной проблеме обучения без учителя (Unsupervised Learning) – задаче поиска аномалий (Anomaly Detection). Интересно, что в русскоязычных учебных курсах об этой задаче часто забывают. Даже в русской версии страницы обучение без учителя нет упоминания об этой задаче, в английской, конечно же, есть.

Строго говоря, в анализе данных есть два направления, которые занимаются поиском аномалий: детектирование выбросов (Outlier Detection) и «новизны» (Novelty Detection). Как и выброс «новый объект» — это объект, который отличается по своим свойствам от объектов (обучающей) выборки.  Но  в отличие от выброса, его в самой выборке пока нет (он появится через некоторое время, и задача как раз и заключается в том, чтобы обнаружить его при появлении). Например, если вы анализируете замеры температуры и отбрасываете аномально большие или маленькие, то Вы боретесь с выбросами. А если Вы создаёте алгоритм, который для каждого нового замера оценивает, насколько он похож на прошлые, и выбрасывает аномальные — Вы «боретесь с новизной».

Выбросы являются следствием:

• ошибок в данных (неточности измерения, округления, неверной записи и т.п.)
• наличия шумовых объектов (неверно классифицированных объектов)
• присутствия объектов «других» выборок (например, показаниями сломавшегося датчика).

Рис. 1. Модельная задача с двумя признаками

На рис. 1 видно, что шум (noise) — это выброс «в слабом смысле» (он может немного размывать границы класса/кластера). Нас же интересуют, прежде всего, выбросы «в сильном смысле», которые искажают эти границы.

Новизна, как правило, появляется в результате принципиально нового поведения объекта. Скажем, если наши объекты – описания работы системы, то после проникновения в неё вируса объекты становятся «новизной». Ещё пример – описания работы двигателя после поломки. Здесь важно понимать, что «новизна» называется новизной по той причине, что такие описания для нас абсолютно новые, а новые они потому, что мы не можем в обучающей выборке иметь информацию о всевозможных заражениях вирусами или всевозможных поломках. Формирование такой обучающей выборки трудозатратно и часто не имеет смысла. Зато можно набрать достаточно большую выборку примеров нормальной (штатной) работы системы или механизма.

Приложений здесь море:

• Обнаружение подозрительных банковских операций (Credit-card Fraud)
• Обнаружение вторжений (Intrusion Detection)
• Обнаружение нестандартных игроков на бирже (инсайдеров)
• Обнаружение неполадок в механизмах по показаниям датчиков
• Медицинская диагностика (Medical Diagnosis)
• Сейсмология

Стоит отметить, что возможных постановок задач здесь тоже много. Например, задача Positive-Unlabeled Classification (PU learning) – это когда часть выбросов обозначена (класс 1), но в остальных объектах  обучения (класс 0) также могут содержаться выбросы. Например, нам эксперт сказал, что оборудование давало сбой в такие-то моменты времени, но он мог заметить не все сбои.

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

Аномалии бывают не только в табличных данных, они могут быть в графах, временных рядах и т.д.

Рис. 2. Пример выбросов во временном ряде.

Рис. 3. Пример выбросов в графах и последовательностях.

Функционалы качества в задачах детектирования аномалий используют примерно такие же, как и в задачах классификации: PR AUC, AUROC, здесь всё определяется контекстом задачи (заказчиком).

Методы обнаружения выбросов

1. Статистические тесты

Как правило, применяют для отдельных признаков и отлавливают экстремальные значения (Extreme-Value Analysis). Для этого используют, например, Z-value или Kurtosis measure.

Рис. 4. Пример выбросов.

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

Важно понимать, что экстремальное значение и аномалия это разные понятия. Например, в небольшой выборке

[1, 39, 2, 1, 101, 2, 1, 100, 1, 3, 101, 1, 3, 100, 101, 100, 100]

значение 39 можно считать аномалией, хотя оно не является максимальным или минимальным. Также стоит отметить, что аномалия характеризуется, как правило, не только экстремальными значениями отдельных признаков (см. рис. 5)

Рис. 5. Пример выбросов в задаче с двумя признаками.

2. Модельные тесты

Идея очень простая – мы строим модель, которая описывает данные. Точки которые сильно отклоняются от модели (на которых модель сильно ошибается) и есть аномалии (см. рис. 2). При выборе модели мы можем учесть природу задачи, функционал качества и т.п.

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

Рис. 6. Применение SVD для нахождение выбросов в матрице

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

3. Итерационные методы

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

Рис. 7. Выпуклые оболочки множества точек.

4. Метрические методы

Судя по числу публикаций, это самые популярные методы среди исследователей. В них постулируется существование некоторой метрики в пространстве объектов, которая и помогает найти аномалии. Интуитивно понятно, что у выброса мало соседей, а у типичной точки много. Поэтому хорошей мерой аномальности может служить, например «расстояние до k-го соседа» (см. метод Local Outlier Factor). Здесь используются специфические метрики, например расстояние Махаланобиса.

Рис. 8. Соседи нескольких элементов выборки, связь с 5м показана красным

5. Методы подмены задачи

Когда возникает новая задача, есть большой соблазн решить её старыми методами (ориентированными на уже известные задачи). Например, можно сделать кластеризацию, тогда маленькие кластеры, скорее всего, состоят из аномалий. Если у нас есть частичная информация об аномалиях (как в задаче PUC), то можно решить её как задачу классификации с классами 1 (размеченные аномалии) и 0 (все остальные объекты). Если бы класс 0 состоял только из нормальных объектов, то такое решение было бы совсем законным, иначе остаётся надеяться, что недетектированных аномалий в нём немного.

Рис. 9. Пример кластеризации на малый (красный) и большой (синий) кластер.

6. Методы машинного обучения

А что если воспринять задачу нахождения аномалий как новую задачу машинного обучения (отличную от классификации и кластеризации)?!

Самые популярные алгоритмы (есть реализация даже в scikit-learn) здесь:

• Метод опорных векторов для одного класса (OneClassSVM)
• Изолирующий лес (IsolationForest)
• Эллипсоидальная аппроксимация данных (EllipticEnvelope)

Рис. 10. Визуализация работы разных алгоритмов поиска аномалий.

Первый метод — это обычный SVM, который отделяет выборку от начала координат. Идея немного сомнительна, но оказалась довольно работоспособной (см. рис. 10). Здесь правда не так много разнообразия в выборе параметров, как при решении задач классификации, поскольку в качестве ядра подойдёт лишь rbf (радиальные базисные функции), все остальные ядра показывают феноменально отвратительный результат. Интересно , что многие годы задачи детектирования поломок сложных механизмов решались именно с помощью OneClassSVM, почему-то без рассмотрения альтернатив (на нашей кафедре также защищались дипломы на эту тему). Полезно помнить, что OneClassSVM это скорее алгоритм поиска новизны, а не выбросов, т.к. «затачивается» под обучающую выборку.

Важные параметры реализации sklearn.svm.OneClassSVM:

• kernel – ядро (линейное: linear, полиномиальное: poly, радиальные базисные функции: rbf, сигмоидальное: sigmoid, своё заданное)
• nu – верхняя граница на %ошибок и нижняя на % опорных векторов (0.5 по умолчанию)
• degree – степень для полиномиального ядра
• gamma – коэффициент для функции ядра (1/n_features по умолчанию)
• coef0 – параметр в функции полиномиального или сигмоидального ядра

Изолирующий лес  (Isolation Forest) – это одна из вариаций идеи случайного леса. Как всегда: простая и надёжная.

• Состоит из деревьев
• Каждое дерево строится до исчерпании выборки
• Для построения ветвления в дереве: выбирается случайный признак и случайное расщепление
• Для каждого объекта мера его нормальности – среднее арифметическое глубин листьев, в которые он попал (изолировался)

Рис. 11. Вычисление оценки аномальности в изолирующем лесе.

Логика алгоритма простая: при описанном «случайном» способе построения деревьев выбросы будут попадать в листья на ранних этапах (на небольшой глубине дерева), т.е. выбросы проще «изолировать» (напомним, что дерево строится до тех пор, пока каждый объект не окажется в отдельном листе). Алгоритм хорошо отлавливает именно выбросы (см. рис. 12).

Рис. 12. Оценки изолирующего леса для одномерной выборки.

Важные параметры реализации sklearn.ensemble.IsolationForest

• n_estimators – число деревьев
• max_samples – объём выборки для построения одного дерева (если вещественное число, то процент всей выборки)
• contamination – доля выбросов в выборке (для выбора порога)
• max_features – число (или %) признаков, которые используются при построении одного дерева (пока работает только со значением 1.0)
• bootstrap – включение режима бутстрепа при формировании подвыборки

Эллипсоидальная аппроксимация данных — из названия понятно, что облако точек моделируется как внутренность эллипсоида. Метод хорошо работает только на одномодальных данных, а совсем хорошо – на нормально распределённых. Степень новизны здесь фактически определяется по расстоянию Махаланобиса.

7. Ансамбли алгоритмов

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

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

• Feature Bagging (не очень удачное название) – для каждого алгоритма берут случайное признаковое подпространство,
• Rotated Bagging – в выбранном случайном признаковом подпространстве совершают случайный поворот.

Кстати, здесь «усреднение» не обязательно означает среднее арифметическое всех оценок, интуитивно понятно, что часто может сработать максимум (если какой-то алгоритм уверен в аномальности объекта, то скорее всего так оно и есть).

История из практики

В задачах поиска аномалий важно понимать, как работают алгоритмы поиска, и объяснить это заказчику. Например, когда автор последний раз участвовал в решении подобной задачи, заказчик хотел средство для детектирования поломок, но из-за природы модели получился алгоритм детектирования «неправильного функционирования оборудования», т.е. он давал сигнал не только в случае поломок, но и в случае некорректной эксплуатации прибора, а также при работе в очень редких режимах. Некоторые поломки (очень частые) он всё-таки пропускал, т.к. «они уже стали для прибора нормой». Понятно, что при наличии большой размеченной выборки таких проблем не возникало бы, но на практике оборудование работает не так долго, поломок тоже мало (и не все возможные случаются), а некоторые поломки могли не заметить или заметить с запозданием. Кроме того, некоторые поломки никак не отражаются на показаниях датчиков. Изначально качество очень расстроило заказчика, но когда ему объяснили, как работает алгоритм, заказчик сверился с данными испытаний и убедился, что алгоритм очень полезный, даже если не находит какие-то поломки: его можно использовать как верификатор «работает ли прибор в штатном режиме», а это самое главное.

П.С. Код для получения рис.10 можно взять здесь.