Improved histogram-based anomaly detector with the extended principal component features
Sunil Aryal Arbind Agrahari Baniya KC Santosh









Improved histogram-based anomaly detector









Aryal et. al.





^1Deakin University, Geelong, Victoria, Australia 
 
 ^2University of South Dakota, Vermillion, SD, USA 
 









Improved histogram-based anomaly detector with the extended principal component features
    Sunil Aryal^1, Arbind Agrahari Baniya^1 and KC Santosh^2
    December 30, 2023
========================================================================================







In this era of big data, databases are growing rapidly in terms of the number of records. Fast automatic detection of anomalous records in these massive databases is a challenging task. Traditional distance based anomaly detectors are not applicable in these massive datasets. Recently, a simple but extremely fast anomaly detector using one-dimensional histograms has been introduced. The anomaly score of a data instance is computed as the product of the probability mass of histograms in each dimensions where it falls into. It is shown to produce competitive results compared to many state-of-the-art methods in many datasets. Because it assumes data features are independent of each other, it results in poor detection accuracy when there is correlation between features. To address this issue, we propose to increase the feature size by adding more features based on principal components. Our results show that using the original input features together with principal components improves the detection accuracy of histogram-based anomaly detector significantly without compromising much in terms of run-time.     









§ INTRODUCTION



 While majority of records in databases are normal or expected, some of them can be unusual or unexpected. Those data records or instances which are deviated significantly and do not conform to normal data are called anomalies or outliers. Automatic detection of such anomalies using computers is the task of Anomaly Detection (AD) in data mining <cit.>. It has many applications such as intrusion detection in computer networks, fraudulent transaction detection in banking and malignant tumor detection in healthcare.
 
 In the data mining literature, the problem of anomaly detection is solved using three learning approaches <cit.>:
 
     
  * Supervised: A classification model is learned using training instances from both normal and anomalous classes and the learned model is used to predict the class labels of test data. It requires sufficient labelled training samples from both classes. In many real-world applications, it might be very expensive or even impossible to obtain labelled training samples from the anomalous class.
     
  * Unsupervised: Instances in a database are ranked directly based on some outlier score. This approach does not require a training process and labelled samples. Assuming that anomalies are few and different, it uses distance/density to rank them. While this approach works quite well in scenarios where the assumption holds, it results in poor performance when this assumption does not hold, i.e., when  there are far too many anomalies.
     
  * Semi-supervised: A profile of normal data is learned using labelled training data from the normal class only. In the testing phase, instances are ranked based on how well they comply with the learned profile of normal data. Neither it makes any assumption about anomalies nor it requires training samples from anomalous class.
     
 
Many traditional unsupervised and semi-supervised approaches are based on k-Nearest Neighbours (kNN) <cit.> which require pairwise distance calculations. Being few and different anomalies are expected to have large distances to their kNNs compared to their neighbours. Because of the computational complexity to compute pairwise distances, these distance based methods are limited to small databases. They can not be used in databases with large number of instances.

In this era of big data, databases are growing rapidly in terms of both the number of instances and dimensionality. Fast automatic detection of  anomalies in these massive databases is a challenging task. There are some efficient unsupervised anomaly detectors <cit.> which are applicable to large databases. 

Univariate histograms based method <cit.> is arguably the fastest anomaly detector. It creates univariate histograms in each dimension and computes anomaly score of an instance as the product of probability data mass in histograms where the instance falls in all dimensions. It assumes that attributes are independent of each other. Despite the strong assumption, it has been shown to produce competitive results compared to state-of-the-art contenders and runs very fast<cit.>. It can detect anomalies that show outlying characteristics in any input features (i.e., one-dimensional subspaces). We refer to such anomalies as `Type I Anomalies'. However, it can not detect anomalies which look normal in each one-dimensional subspaces but show outlying characteristics in multidimensional subspaces (we refer to them as `Type II Anomalies') as it does not capture the relationship between input features. It may be the case in many applications that there is a correlation between input features and anomalies are not different from normal instances in any single feature but they look different only if features are examined together.

In this paper, we attempt to overcome the above mentioned limitation of histogram based method using principal components <cit.>. Principal Components (PCs) are mappings of subspaces of possibly correlated features in the input space into a new space. We introduce a new variant of histogram based anomaly detection method called `SPAD+' where anomaly scores of instances are computed based on univariate histograms of the input features and principal components. This way, histograms in input features contribute to detect Type I anomalies and histograms in PCs contribute to detect Type II anomalies. Our empirical results in 15 benchmark datasets show that SPAD+ significantly improves the detection accuracy of SPAD, a histogram based anomaly detector using input features only, without compromising much in terms of runtimes. It produces better results in terms of both detection accuracy and runtime than traditional nearest neighbour based method and more recent faster anomaly detectors.

Rest of the paper is structured as follows. Preliminaries related to this paper and a review of widely used state-of-the-art fast anomaly detection methods are provided in Section <ref>. The proposed method of SPAD+ is discussed in Section <ref> followed by experimental results in Section <ref> and conclusions in the last section.





§ PRELIMINARIES AND RELATED WORK



In this paper, we focus on continuous domain where each data instance x is represented by an M-dimensional vector ⟨ x_1,x_2,⋯,x_M⟩∈ℝ^M (where ℝ is a real domain). Each x_i∈ℝ is the value of the i^th feature of x.
We use semi-supervised approach for anomaly detection where a profile of normal data is learned from training data and test data (a mixture of normal and anomalous data) are ranked according to their anomaly scores based on the learned profile of normal data. Let D be a collection of N training data (all normal) and Q be a collection of n test data (normal and anomalies). The task is to model the profile of normal data from D and ranked data in Q based on their compliance to the profile of normal data.

In the rest of this section we review most widely used and fast anomaly detection methods.




 §.§ Local Outlier Factor (LOF)


Local Outlier Factor (LOF) <cit.> is the most widely used and popular kNN based anomaly detection method. It does not require any training. The anomaly score of x∈ Q is calculated based on the distances to its kNNs in D. It uses the concept of local reachability distance (lrd). Let kNN( x, D) be the set of kNNs of x in D, d( x, y) = √(∑_i=1^M (x_i-y_i)^2) is the euclidean distance between x and y, and d^k( x, D) is the euclidean distance between x and its k^th NN in D. The anomaly score of x is calculated as:


    s_lof( x) = ∑_ y∈ N^k( x, D)lrd( y)/|N^k( x, D)|× lrd( x)

lrd( x) = |N^k( x, D)|/∑_ y∈ N^k( x, D)max(d^k( y, D), d( x,  y)). Note that |N^k( x, D)| may not be exactly k when there are many instances are equidistant to x, i.e., N^k( x, D)={ y∈ D : d( x, y)≤ d^k( x, D)}.

The anomaly score of s_lof( x) is computed with respect to its local neighbourhood in D defined by  N^k( x, D). It measures how different is x with respect to it kNNs in terms of lrd. The anomaly score is based on the distances x to its kNNs and their distances to their kNNs. It can be computationally very expensive when D is large limiting its use in small datasets only.




 §.§ Isolation forest (iforest)


Isolation forest (iforest) <cit.> is an efficient anomaly detector method which does not require pairwise distance calculations. It uses a collection of t unsupervised random trees where each tree T_i is constructed from a small subsamples of training data D_i⊂ D, | D_i|=ψ≪ N. The idea is to isolate every sample in D_i. At each internal node of T_i, the space is partitioned into two non-empty regions with a random split on a randomly selected attribute. The partitioning continued until the node has only one instance (which is isolated from the rest) or the maximum height of ⌊log_2ψ⌋ is reached. The anomaly score of x∈ Q is estimated as the average path length over t trees:


    s_if( x) = 1/t∑_i=1^t ℓ_i( x)

where ℓ_i( x) is the path length of x in tree T_i.

The simple intuition is that anomalies are more susceptible to isolation and they have shorter average path lengths than normal instances. It is shown to produce competitive detection accuracy to LOF but runs significantly faster as it does not require distance calculations <cit.>.  




 §.§ Nearest neighbour distance in a small subsample (Sp)


Instead of using kNNs of x in the entire training data D, Sugiyama and Borgwardt (2013) <cit.> argued that it is sufficient to use 1NN (k=1) in a small subsample of data D⊂ D, | D|=ψ≪ N. They suggested to use the distance of x to it nearest neighbour in D as the anomaly score.


    s_sp( x) = min_ y∈ D d( x, y)


It has been shown that ψ as small as 20 or 25 produces competitive results to LOF but runs orders of magnitude faster in large datasets <cit.>.




 §.§ Histogram based method


Another simple and efficient anomaly detection method is based on univariate histograms <cit.>. In each dimension i, it creates histograms with a fixed number of equal-width bins h_i,1,h_i,2,⋯,h_i,b and records the number of training instances falling in each h_i,j. Anomalies are expected to fall in bins with small number of training samples. 

Aryal et al. (2016) introduced a simple probabilistic anomaly detector (SPAD) <cit.> where multivariate probability of x, P( x), is approximated as the product of univariate probabilities P(x_i) assuming attributes are independent of each other. Approximation of P(x_i) is estimated using probability mass by discretising values in dimension i based on equal-width histograms. They use a modified version of equal-width discretisation which is more robust to skewed distribution of data in dimension i. Instead of dividing the entire data range defined by [min_i, max_i] (min_i and max_i are the minimum and maximum value in dimension i) into b equal-width bins, they divide the range [μ_i-3σ_i, μ_i+3σ_i] (μ_i and σ_i are the mean and standard deviation of values in dimension i) into b equal-width bins. The bin width in each dimension depends on the data variance in that dimension. The anomaly score of x is then estimated as:


    s_spad( x) = ∑_i=1^M log|H_i( x)|+1/N+b


H_i( x) is the bin in dimension i where x falls into. Note that the RHS of Eqn <ref> is equivalent to the logarithm of P̂( x)=∏_i=1^M P̂(x_i).

Simple univariate histogram based method is shown to produce competitive results to LOF, iforest and Sp and it runs faster than them <cit.>.

Among the four anomaly detection methods reviewed above, LOF is a widely used baseline and other three methods are fast anomaly detectors for large datasets. Their time and space complexities are provided in Table <ref>. In terms of time and space complexities, SPAD is clearly the most efficient one.





§ THE PROPOSED METHOD: SPAD+



Though SPAD can detect anomalous data exhibiting outlying characteristics in any dimension (Type I Anomalies), it can not detect anomalous data which look normal in each dimension but exhibit outlying characteristics only when examined on multiple features together (Type II Anomalies) <cit.>. For example, the data point shown on blue in Fig <ref>(a) looks perfectly normal when examined from each dimension individually (it is in the middle of the distribution in each dimension). SPAD can not detect such obvious anomaly. This is because it does not capture the relationship between input features. In many real-world applications, features can be related and anomalous data may not conform to it.

We believe the above mentioned issue of SPAD can be addressed to some extent with Principal Component Analysis (PCA)<cit.>. PCA is a tool to transform potentially correlated features into new uncorrelated features <cit.>. It learns the transformation matrix using the covariance matrix of observed data. Fig <ref>(b) is the transformation of data in Fig <ref>(a) in the PC space. The anomalous instance on blue is clearly an outlier in the second principal component (vertical axis in the Fig <ref>(b)) which can be easily detected by SPAD in the new PC space.



In order to cater for both Type I and Type II of anomalies, we propose to add principal components (PCs) as new features in addition to the input features. Input features  contribute  to  detect Type  I  anomalies and PCs contribute to detect Type II anomalies. Using PCs only may not be a good idea because it may mask anomalies which are easily detectable in the input space[In our experiments, we observed that using PCs only produced worst results in many datasets.]. 

For semi-supervised anomaly detection, PCA is applied to the training dataset D to learn the transformation matrix which is used to transform data in both D and Q. The feature size is increased from M to 2M by adding all M PCs. In SPAD, histograms are constructed in each dimension of the input space and PC space. We refer the SPAD used in input features and PCs as SPAD+. Let x' be the transformation of x in the PC space. The anomaly score of x∈ Q is estimated as:


    s_spad+( x) = ∑_i=1^M log|H_i( x)|+1/N+b + ∑_j=1^M log|H_j( x')|+1/N+b


In the literature, PCA is used mainly to reduce dimensionality of data where top m<M PCs that capture the most variance in data are selected and PCs with low variance are ignored. However, the purpose of using PCs in SPAD+ is not to reduce dimensionality, they are used to capture correlation between attributes to detect Type II anomalies. Low variance PCs can be very useful to detect anomalies as they may contain few values which are significantly different from the rest, more likely to be anomalies (e.g., in Fig!<ref>(b), the blue point is an outlier in the second PC where variance is lower than in the first PC). Ignoring low variance PCs can be counter productive for anomaly detection[In our experiments, we observed that adding top PCs capturing 95% variance of data produced worse results than adding all PCs in many datasets.]. Thus, we add all PCs so that maximum possible anomalies are detected.   

In terms of runtime and space complexities, SPAD+ has similar complexities as SPAD. It requires additional O(NM+M^3) time (worst case) in the training process to compute the covariance matrix of the training data D and its eigen decomposition. In the testing phase the only difference is that M is increased to 2M. Because of O(M^3), it can be computationally expensive in high dimensional datasets where M is large. However, it is the worst case and on average case it can be done faster. It may not be an issue unless M is very large in thousands or millions.






§ EMPIRICAL EVALUATION



In this section, we provide details of our experimental setup to evaluate performances of SPAD+ against the four methods (LOF, iforest, Sp and SPAD) discussed in Section <ref> and discuss results. We conducted experiments in semi-supervised setting — half of the data belonging to the normal class were used as training set D and the remaining half along with data belonging to the anomaly class were used as test set Q as done in <cit.>. Anomaly detection model was learned from the training data and test data were ranked based on their anomaly score using the learned model. We used Area under the receiver operation curve (AUC) as the performance evaluation measure. For the random methods - iforest and Sp, each experiment was repeated 10 times and reported the average AUC over 10 runs. For a dataset, the same D and Q pair were used for all experiments. Min-max normalisation<cit.> was used to ensure feature values in each dimension are in the same range. 

All methods were implemented in Python using the Scikit-learn machine learning library <cit.>. We used the LOF implementation available on the Scikit-learn library. All experiments were conducted on a Linux machine. Parameters in all algorithms were set to default values suggested by respective papers — LOF (k=⌊√(N)⌋); iforest (t=100 and ψ=256); Sp (ψ=25); and b=⌊log_2N⌋+1 in SPAD and SPAD+.

We used 15 widely used publicly available benchmark datasets from various application areas such as space physics, health and medicine, cyber security, pharmaceutical chemistry and geographical information system (GIS). The characteristics of datasets in terms of dimensionality, training data size, the numbers of normal data and anomalies in the test data and application area are provided in Table <ref>.  





The AUC of all five contenders in the 15 datasets are provided in Table <ref>. SPAD+ produced the best results in seven datasets, while producing the second best results in six datasets and the third best results in the remaining two datasets. It was ranked among the top three best performing methods in all the 15 datasets. The baseline method of LOF is the closest contender with the best AUC in six datasets. It was ranked second in one dataset, third in three datasets and fourth in four datasets. It was the worst performing method in the remaining four datasets. Sp and iforest did not produce the best result in any dataset and each of them produced the worst results in two datasets. While original SPAD produced the best result in two datasets, it produced the worst results in seven datasets. 

From this results, it is clear that adding PCs, SPAD+ significantly improved the AUC in 13 out of 15 datasets, making it the top performing method from the worst. This is because of the ability to examine anomalies in individual input features and multidimensional subspaces represented by PCs which enable SPAD+ to detect both Type I and Type II anomalies. Existing fast anomaly detectors' results are not comparable to those of SPAD+. iforest did not produce better AUC than SPAD+ in any dataset whereas Sp produced better AUC than SPAD+ in two datasets only. Compared to SPAD, SPAD+'s was slightly worse in Satellite and was significantly worse in Annthyroid but it was still better than all other contenders. 




The total runtimes (training and testing) of the five contending measures in the 15 datasets are provided in Table <ref>. As expected SPAD+ ran slower than SPAD. Compared to other contenders, though it was slower in small datasets, it ran faster than them in large datasets. For example, SPAD+ was one order of magnitude faster than LOF in the largest dataset.   

These results show that SPAD+ significantly improves anomaly detection performance without compromising much in terms of runtime, particularly in large datasets with a large number of data instances. It is a simple and intuitive method which is more appropriate for big data characterised by large data size. 

The only difference between SPAD and SPAD+ is the addition of PCs as new features. One can argue that we can use the same idea with existing methods. We tested using the original input features and PCs and the results are presented in Table <ref>. The results of LOF and Sp remained largely unchanged whereas that of iforest were improved in some datasets. iforest managed to produce better AUC than SPAD+ in Ionosphere only, it's results in other 14 datasets were worse than those of SPAD+.



Adding PCs did not add any value to LOF and Sp. It is because of the anomaly scores used which are based on nearest neighbours distances. They are already examining anomalies using all dimensions even when only input features are used. Adding PCs results in additional redundant feature and does not necessarily impact the outcome of the algorithm.  

However, PCs can be useful in iforest. When only input features are used, it can examine anomalies using multiple dimensions to some extent because leaf nodes in trees are constructed by partitioning space using different attributes. However, the number of attributes used in the examination are restricted by the height of the leaf nodes. In best case, it can use up to 8 (log_2 256 as ψ was to 256 by default) dimensions. Because attribute is selected at random and tree building process terminates early when a sample instance is isolated, even 8 attributes may not be used. Therefore adding PCs enables it to examine anomalies using many attributes at the same time to detect more Type II anomalies. Because iforest mostly examines anomalies using randomly selected multiple attributes, it forces correlation even though it may not exist in the dataset which results in false positive — some normal instances may appear to be anomalies. This could possibly be one of the reasons why iforest can not perform as good as SPAD+ when input features and PCs are used because PCs by definition are uncorrelated, i.e., they are orthogonal to each other. 

In SPAD, PCs are very useful to examine anomalies using potentially correlated attributes together to detect Type II anomalies. Because it examines each dimension individually and does not force any non existing correlation, it can avoid false positive cases like those in iforest. In SPAD+, original input features can be useful to detect Type I anomalies and PCs can be useful to detect Type II anomalies, complimenting each other to produce better outcome when applied together. 


































§ CONCLUDING REMARKS



The idea of estimating multivariate probability as the product of univariate probabilities assuming that variables are independent of each other is widely used in other data mining and machine learning tasks such as naive Bayes classifier <cit.>. It has not been explored enough in the anomaly detection task. Histogram based method such SPAD are simple, intuitive and very fast for anomaly detection. It should be a simple baseline to compare the performances of more complex and recent approaches. However, only a few studies such as <cit.> are using it.

Even though SPAD produces results quite competitive to other efficient anomaly detectors, it has a limitation on detecting anomalies which rely on multiple attributes because it examines each attribute separately assuming that they are independent from each other <cit.>. In this paper, we show that this limitation can be addressed to some extent by using principal components (PCs) of data as additional features. The idea is to double the feature size with input features and PCs.Then, use SPAD in the new space. We call the new variant of SPAD using PCs as SPAD+. Our empirical results show that SPAD+ significantly improves the performance of SPAD without compromising much in runtime and results in better performance than state-of-the-art methods. It runs faster than other existing fast anomaly detection methods. 

It's simplicity, effectiveness and efficiency make SPAD+ an ideal anomaly detector to use in big data with hundreds of thousands to millions of data instances. We believe this simple method sets a new baseline for anomaly detection performance comparison. 

PCs based on the covariance matrix only capture linear relationships between input features. They can not capture non-linear relationships between features. Kernel-PCA <cit.> that uses kernel matrix can capture the non-linear relationships but it requires calculations of pairwise kernel similarities of data instances. It is computationally very expensive, limiting its use in small datasets only. We are looking forward to investigating how non-linear relationships present among different attributes in a dataset can be captured efficiently; thereby, improvising the current performance of SPAD+ algorithm. 








splncs


