Ансамбли методов в алгоритмах поиска выбросов
Большое число практических задач, например, поиск мошеннических операций, выявление брака или аномалий, обнаружение вирусных атак на основе нетипичной активности сводятся к задачам определения выбросов в данных. Для определения выбросов обычно используют стандартные методы, например, метод ближайших соседей (KNN) или метод локального уровня выбросов (LOF). Применение ансамблей позволяет улучшить точность работы стандартных методов. Рассмотрим, как это сделать.
Идея ансамблей методов проста. Буду делать подвыборки из обучающей выборки и обучать на них базовые алгоритмы. Получаю набор из независимых детекторов (этот набор называется ансамбль), которые выдают оценки для каждой точки данных. Комбинируя оценки выбросов от базовых алгоритмов, обученных на различных подвыборках, получаю более точное предсказание выбросов.
Нужно обратить внимание, что ансамбли можно строить, также объединяя различные базовые методы, однако в посте будут исследоваться ансамбли одного метода, построенного на различных подвыборках.
Эффективность такого подхода достигается благодаря тому, что базовые алгоритмы, обученные на различных подвыборках, получаются достаточно различными, и их ошибки взаимно компенсируются при объединении. Приведу пример иллюстрирующий этот подход: если попросить человека на глаз определить вес предмета, то, как правило, он ошибётся, но если опросить несколько человек и затем усреднить их оценки, то результат будет гораздо ближе к истине.
Будем применять следующие методы формирования подвыборок:
- Подвыборка фиксированной длины (CS): из обучающей выборки выбирается фиксированное число точек.
- Подвыборка случайной длины (VS): из обучающей выборки выбирается случайное число точек.
- Подвыборка с уменьшением числа измерений (FB): из всех измерений обучающей выборки случайным образом выбирается r измерений.
Код формирования подвыборки фиксированной и случайной длины:
Размер подвыборки определяется параметром part, который изменятся в пределах от 0 до 1. Если необходимо сделать подвыборку случайной длины, то параметр part будет случайной величиной.
Для формирования подвыборки с уменьшением числа измерений из исходного набора данных случайным образом выбираю индексы по измерениям.
После того как сформированы подвыборки и на них обучена модели классификации необходимо как-то объединить результаты работы полученных детекторов. Буду использовать следующие методы объединения:
- Усреднение (AVG): оценки от разных детекторов усредняются.
- Максимизация (MAX): из всех оценок детекторов выбирается максимальная.
- Среднее максимумов (AOM): разбиваем все подвыборки на q групп. Для каждой группы выбирается максимальная оценка. Затем в качестве итоговой оценки выбирается среднее из всех оценок по группам.
Необходимо исследовать, как применение идеи ансамблей методов влияет на точность и время работы алгоритмов поиска выбросов. Для исследования буду использовать общедоступные наборы данных с выбросами, выложенными на сайте: http://odds.cs.stonybrook.edu. Использованные наборы данных приведены в табл.1, выбрал три характерных набора: с большим числом измерений (Musk); с малым числом точек (Glass); с умеренным числом точек и измерений (Satimage-2).
Наборы данных сохранены в файлах формата “.mat” – это двоичный формат данных, который использует программа MATLAB, формат “.mat” позволяет сохранять переменные, функции, массивы и другую информацию. В python есть возможность работать с “.mat” файлами с помощью библиотеки scipy.
Разобью наборы из таблицы 1 на две части: на тестовую и на тренировочную. Наборы разбиваются на две части случайным образом, точность работы базовых алгоритмов очень сильно зависит от того как разделились данные, поэтому, чтобы можно было сравнивать, как меняется точность при применении ансамблей методов буду использовать один и тот же набор тестовых и тренировочных данных для всего ансамбля. Набор тестовых и тренировочных данных сохраню с помощью pickle:
Для использования базовых алгоритмов поиска выбросов удобно использовать Python библиотеку pyod. Нужно исследовать алгоритмы LOF и kNN. Импортирую все необходимые библиотеки:
Функция расчета ошибок для каждого вида (AVG, MAX и AOM) объединения базовых детекторов:
Здесь для оценки точности используется площадь под кривой ROC, эта метрика вычисляется с помощью функции roc_auc_score из библиотеки sklearn.metrics. Методы объединения AVG, MAX и AOM уже реализованы в библиотеке pyod. Замечу, что перед объединением показаний базовых детекторов обязательно необходимо нормировать данные, здесь применяется Z-нормализация (функция standardizer).
Затем просто вызываю функцию для каждого базового метода и для каждого набора данных:
Результаты исследования алгоритма LOF представлены в таблицах 2 и 3. Результаты исследования алгоритма kNN представлены в таблицах 4 и 5.
Таблица 2. Результаты исследования точности для метода локального уровня выбросов (LOF).
Таблица 3. Результаты исследования времени для метода локального уровня выбросов (LOF).
Таблица 4. Результаты исследования точности для метода ближайших соседей (KNN).
Таблица 5. Результаты исследования времени выполнения для метода ближайших соседей (KNN).
В таблицах 2 и 4 выделил зеленом цветом по два самых точных метода, и красным по два метода с наименьшей точностью.
В целом методы ансамблей позволяют улучшить результат работы базового алгоритма, однако, время работы при этом увеличивается. Например, из таблиц 2 и 4 (для двух методов LOF и KNN) видно, что в двух строках из трех базовый метод помечен красным – т.е. точность базового метода без метода ансамблей меньше, чем в случае, когда применяется метод ансамблей.
Можно порекомендовать использовать методы ансамблей, когда вы не можете подобрать базовый метод, который давал бы вам необходимую точность и вам не очень критично время работы метода. А если базовый метод сам по себе дает неплохую точность, то использовать метод ансамблей не эффективно т.к. возрастает время работы алгоритма.