Sequential Ensemble Learning for Outlier Detection: A Bias-Variance Perspective

Summary

In this paper, Rayana et al. develop a new sequential ensemble method called Cumulative Agreement Rates Ensemble (CARE) for outlier detection. As we know, ensemble methods have always been widely used in classification problems to gain the aggregated strength of many base models. Until recently, there are some work [1,2,3] exploring ensemble methods to this field - anomaly detection.

Inspired by Aggarwal and Sathe’s work [2], they consider outlier detection problem as a binary classification task where labels are unknown, the inliers being the majority class and the outliers being the minority class. The detection error can be decomposed into bias and variance, but existing outlier ensembles are following in parallel framework to combine multiple base detector’s outcome to only reduce variance. They claim that their sequential ensemble is able to not only reduce variance but also bias.

Specifically, the main steps in CARE outlier ensemble are as following:

·      Firstly, they create multiple feature-bagging outlier detectors as base detectors of the ensemble. Two versions of CARE are constructed using (a) distance-based approach AveKNN and (b) density-based approach LOF.

·      In each iteration, there are two aggregation stages to reduce variance: (a) in the first stage, they combine all the results from base detectors by weighted aggregation instead of binary selection of base detectors. To obtain the weights, they first estimate errors through the unsupervised Agreement Rates [4], and then assign weights inversely proportional to the corresponding errors; (b) in the second stage, they aggregate the results of the current iteration with all previous iterations to compute outlierness scores.

·      Before going into the next iteration, they first remove some outliers based on outlierness scores obtain from the last iteration to reduce bias. In particular, they sample a subsample from the original data using Filtered Variable Probability Sampling (FVPS) and use the sample as inputs for next iteration.

·      Iterations (2-3) will be stopped until stopping condition is satisfied.

The main advantage of CARE is that its filtered sampling reduces both bias and variance more than any other procedures. Results show that CARE beats AveKNN and LOF based baselines across many datasets, yet it becomes more difficult for CARE to outperform all the state-of-the-art ensembles in all the datasets.