BOFE: Anomaly Detection in Linear Time Based on Feature Estimation

In this paper, we propose an anomaly detection algorithm based on feature estimation. The key insight of our algorithm is a fast and accurate feature estimator based on multiple mapping tables, called ensemble mapping table. These mapping tables, which are the novel representation of data set transformed by mapping functions, contain the feature information and corresponding probability. By establishing these mapping tables, we can obtain the empirical probability distribution of each feature. Then we can estimate the degree of abnormality of each feature according to its probability distribution, and count the number of anomaly features. This number will be treated as anomaly score of instances. In order to obtain unbiased score, the final anomaly score are the average value of the scores obtained from the ensemble mapping table. We derive the theoretical upper bound for the proposed algorithm and analyze the rationality of the anomaly score calculation method from statistical perspective. Experimental evaluations on multiple benchmark data sets illustrate that, compared to the existing state-of-the-art methods, our algorithm BOFE can achieve better AUC score and need less running time.