Время прочтения: 6 мин.

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

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

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

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

Будем применять следующие методы формирования подвыборок:

  • Подвыборка фиксированной длины (CS): из обучающей выборки выбирается фиксированное число точек.
  • Подвыборка случайной длины (VS): из обучающей выборки выбирается случайное число точек.
  • Подвыборка с уменьшением числа измерений (FB): из всех измерений обучающей выборки случайным образом выбирается r измерений.

Код формирования подвыборки фиксированной и случайной длины:

def get_subsampling(x,y,part):
    part=int(x.shape[0]*part)
    index_value=random.sample(list(enumerate(x[:,0])),part)
    indexes=[]
    for idx,val in index_value:
        indexes.append(idx)
    return x[indexes,], y[indexes]

Размер подвыборки определяется параметром 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. Наборы данных для исследования

НаборЧисло точекЧисло измеренийПроцент выбросов
Musk30621663.2 %
Glass21494.2 %
Satimage-25803361.2 %

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

import pickle
from scipy.io import loadmat
from sklearn.model_selection import train_test_split
from pyod.utils.utility import standardizer

mat_file='satimage-2.mat'
mat=loadmat(mat_file)
X=mat['X']
y=mat['y'].ravel()

# 75% data for training and 25% for testing
X_train,X_test,y_train,y_test=train_test_split(X,y,test_size=0.25)
# Z - normalized data
X_train_norm,X_test_norm=standardizer(X_train,X_test)

data=
{
    'X_train_norm':X_train_norm,
    'X_test_norm':X_test_norm,
    'y_train':y_train,
    'y_test':y_test,
}
#Save train and test data
with open('.'.join([mat_file.split('.')[0],'pickle']), 'wb') as f:
    pickle.dump(data, f)

Для использования базовых алгоритмов поиска выбросов удобно использовать Python библиотеку pyod. Нужно исследовать алгоритмы LOF и kNN. Импортирую все необходимые библиотеки:

import numpy as np
import random
import matplotlib.pyplot
import time
from sklearn.model_selection import train_test_split
from scipy.io import loadmat
import pickle

from pyod.models.combination import aom, average, maximization
from pyod.utils.utility import standardizer
from sklearn.metrics import roc_auc_score

from pyod.models.knn import KNN
from pyod.models.lof import LOF

Функция расчета ошибок для каждого вида (AVG, MAX и AOM) объединения базовых детекторов:

def test_method(method,data,subsample_method):
    X_train_norm=data['X_train_norm']
    X_test_norm=data['X_test_norm']
    y_train=data['y_train']
    y_test=data['y_test']

    n_base = 100  # number of base detectors
    all_det_scores=np.zeros(([X_test_norm.shape[0], n_base]))

    for i in range(n_base):
        if type(subsample_method) == float:
            sub_x,sub_y =get_subsampling(X_train_norm,y_train,subsample_method)
            sub_x_test=X_test_norm
        elif subsample_method == 'VS':
            sub_x,sub_y=get_subsampling(X_train_norm,y_train,random.uniform(0.1,0.9))
            sub_x_test=X_test_norm
        elif subsample_method == 'FB':
            dim=list(range(0,X_train_norm.shape[1]))
            r=random.sample(dim,dim[-1]//2)
            sub_x=X_train_norm[:,r]
            sub_x_test=X_test_norm[:,r]
        else:
            raise ValueError('Wrong subsample_method')
        clf = method()
        clf.fit(sub_x)

        test_scores = clf.decision_function(sub_x_test)
        all_det_scores[:,i]=standardizer(np.reshape(test_scores,(-1,1))).T
    # Combination by average
    y_by_average = average(all_det_scores)
    err_avg=roc_auc_score(y_test, y_by_average)
    # Combination by max
    y_by_maximization = maximization(all_det_scores)
    err_max=roc_auc_score(y_test, y_by_maximization)
    # Combination by aom
    y_by_aom = aom(all_det_scores, n_buckets=5)
    err_aom=roc_auc_score(y_test, y_by_aom)
    return err_avg,err_max,err_aom

Здесь для оценки точности используется площадь под кривой ROC, эта метрика вычисляется с помощью функции roc_auc_score из библиотеки sklearn.metrics. Методы объединения AVG, MAX и AOM уже реализованы в библиотеке pyod. Замечу, что перед объединением показаний базовых детекторов обязательно необходимо нормировать данные, здесь применяется Z-нормализация (функция standardizer).

Затем просто вызываю функцию для каждого базового метода и для каждого набора данных:

with open('satimage-2.pickle', 'rb') as f:
    data = pickle.load(f)
time._startTime = time.time()
err_avg,err_max,err_aom =test_method(KNN,data,'VS')
print('Executed time: ', time.time() - time._startTime)
print(err_avg,err_max,err_aom)

Результаты исследования алгоритма LOF представлены в таблицах 2 и 3. Результаты исследования алгоритма kNN представлены в таблицах 4 и 5.

Таблица 2. Результаты исследования точности для метода локального уровня выбросов (LOF).

Таблица 3. Результаты исследования времени для метода локального уровня выбросов (LOF).

Таблица 4. Результаты исследования точности для метода ближайших соседей (KNN).

Таблица 5. Результаты исследования времени выполнения для метода ближайших соседей (KNN).

В таблицах 2 и 4 выделил зеленом цветом по два самых точных метода, и красным по два метода с наименьшей точностью.

В целом методы ансамблей позволяют улучшить результат работы базового алгоритма, однако, время работы при этом увеличивается. Например, из таблиц 2 и 4 (для двух методов LOF и KNN) видно, что в двух строках из трех базовый метод помечен красным – т.е. точность базового метода без метода ансамблей меньше, чем в случае, когда применяется метод ансамблей.

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