Exploring Global and Local Information for Anomaly Detection with Normal Samples

In this section, we introduce the proposed Anomaly Detector With Global and Loacal Information algorithm(GALDetector). Fig. 1 illustrates the overall framework of the proposed method, which consists of three main stages, i.e., global and local score calculation, potential anomalies selection and weighted detector construction.

In the first stage, we will calculate both local sparsity scores and global normal scores. For local sparsity scores, a local density integration algorithm based on partial identification is utilized to calculate the local sparsity scores of all unlabeled samples. And for global normal scores, a clustering operation is used to identify multiple patterns of normal samples and set them into different clusters, then the global normal scores of all samples are calculated based on these clustering centers. In the second stage, we select potential anomalies selection and set weights to all the samples. After the global normal scores of the samples are calculated according to the global normal scores and the local sparsity scores computed above, we set threshold to select the potential anomalies from the unlabeled samples. Then we assign corresponding weights to known normal samples and selected potentially anomalous samples based on the global normal scores. In the third stage, a weighted detector construction is built based on previous weights and the model parameters are optimized by training such samples. Our model will be employed to identify anomalous on the remaining unlabeled samples.

We let $\kappa=R^{d}$ denotes the sample space and $y=\left\{0,1\right\}$ represents label space, in which $y=0$ is for normal samples and $y=1$ is for anomalous samples. The corresponding data set we selected is $D=\left\{(x_{1},y_{1}),...,(x_{p},y_{p}),x_{p+1},...,x_{N}\right\}$. Among all given $N$ samples, the first $p$ samples are known normal ones $D_{n}=\left\{(x_{1},y_{1}),...,(x_{p},y_{p})\right\}$, and the leftover $(N-p)$ samples are unlabeled ones $D_{u}=\left\{x_{p+1},x_{p+2},...,x_{N}\right\}$.

Local Sparsity Score(LSS). The local sparsity score of each sample is first calculated. We adopt a certain strategy to divide the high-dimensional attribute space into independent subcubes with maximized sparsity variance, so as to portray the local sparsity characteristics of the nodes. To be specifically, we utilize a integration algorithm originated from decision trees, and each tree is built by a partial sample of the data set. Then each tree partitions the high-dimensional sample space into various dense and sparse subcubes.

For each tree, we firstly normalize each coordinate to $[0,1]$ and select a random sample $S\in\Omega$ of $N$ points. From the root, we pick a coordinate $j\in[d]$ at each internal node, then we select $f_{1}<f_{2}<\cdots<f_{p-1}$ which partition the corresponding coordinate $I_{j}$ into $p$ intervals, and split the current node space into $p$ intervals. The number of partitions $p$ is a hyper-parameter, and utilizing $p=5$ works well in practice. Then we partition the property space by selecting coordinates and breakpoints continuously, and the operation stops until reaching the maximum depth or only one point existing in a subcube. Finally the whole sample space is divided into several subcubes and the volume of subcube C can be represented as the product of the interval’s length on each selected coordinate:

Then the overall sparsity of C could be expressed as :

in which $\left|C\cap S\right|$ demonstrates the number of points in the intersection of subcube $C$ and the selected sample set $S$. The local sparsity score of point $x$ is displayed as $LSS(x)$, which is the mean sparsity of subcube containing $x$ in all trees and we have $T$ trees in total.

Our intention is to split C into sparse and dense subcubes, so it is intuitively that we ought to maximize the variance in the sparsity. Maximizing the variance has the advantage that it is equivalent to a well-studied histogram problem[22] and allows for a very efficient streaming algorithm[23]. Through such algorithm we can compute the best split along each coordinate.

Global Normal Score(GNS). To calculate the global normal score, we need to cluster the known normal samples so as to learn the corresponding normal patterns. Afterwards, by measuring the gap between unlabeled samples and normal patterns, we can obtain a representation of the global normal fraction. For the known normal samples $D_{n}=\left\{n_{1},n_{2},...,n_{p}\right\}$, we cluster them into k clusters, and each clustering center represents a normal pattern. Many clustering methods are tried here, considering the effectiveness and time complexity, we choose k-means clustering. We use the Euclidean distance to measure, so that the distance between two points is $dist(x_{m},x_{n})=\sqrt{\sum_{j=1}^{d}(x_{mj}-x_{nj})^{2}}$. The k-means algorithm constrains and optimizes the clustering centers by the following equation.

in which $\sigma_{i}$ is the $i$-th clustering center from the previous stage of clustering. Intuitively, the closer a sample is to its nearest clustering center, the more probably it is to subordinate to a normal pattern. Therefore we use the distance between the unlabeled sample and the nearest normal clustering center to calculate the global normal score. The specific calculation formula of global normal score is as follows:

Global and Local Score(GALScore). In stage two, we combine the local sparsity score and the global normal score after the two scores are calculated separately, so that we can obtain the anomaly characteristics of both global and local information of the sample points. The whole calculation process is shown in Algorithm 1.

in which $\mu\in R^{+}$ is a hyperparameter to consider the importance of the two scores together. Since the two scores indicate a tendency towards normal and anomalous respectively, therefore the calculation should take the negative sign. In addition, we normalize the combined score GALScore to adjust to the assignment of the weights in the following.

To facilitate the subsequent model training, we need to select several potential anomalies from the unlabeled samples. The strategy employed here is to pick the highest scores from the combined score by a certain percentage $\delta$ as potential anomalous samples and $\delta$ is often selected from 5% to 10%.

Then we set corresponding weights for all observed normal samples and potential anomalies. For normal samples, fixed weights are assigned to them, for instance 0.5. For unlabeled samples, the larger the GALScore is, the more likely it is to be an anomaly. Therefore, the following strategy is used to assign weights to the picked potential anomalous samples.

Thereby, the weights of potential anomalous samples are assigned between [0,1]. As for known normal samples, the imbalance in the number of known normal samples and potential anomalies is taken into account, and the weights of the known normal samples are set uniformly to $\epsilon\in[0,1]$. Our motivation is assigning larger weights to potential anomalous samples compared to normal samples, so as to solve the problem of unbalanced sample distribution.

In stage three, we build and train a weighted binary detector construction using known normal samples and selected potential anomalous samples when distinct weights are assigned to them. The following is the objective function to be optimized.

in which $w_{i}$ denotes the weight of the sample $x_{i}$, $R(w)$ is the regularization term, and $l(y_{i},f(x_{i}))$ is the loss term. Here we use a commonly employed classifier XGB[24].

To evaluate our method, we conduct experiments on three categories of datasets from different domains, containing different percentage of anomalies, diverse data volume, and various dimensions.

The first category is classification datasets from the UCI[25] and openML repository[26], concluding Thyroid, Seismic and Mammography. These three datasets deal with binary classification tasks, and the percentage of less class samples is around 5%. The second category is multi-categorical datasets, including Satimage-2, Vowels and Musk. These have been categorized into normal and abnormal classes based on existing work[27], and the less class accounts for 1% to 4%. The third category of the datasets is smtp and http, they are originated from the KDD Cup 1999 network intrusion detection task and their percentages of anomalies are all below 0.5%.

To evaluate the superiority of our method, we compare GALDetector with several state-of-the-art anomaly detection methods. The details of compared methods are introduced as follows.

For the unsupervised, supervised and semi-supervised algorithms, we adopt different experimental setups respectively. For the unsupervised algorithm, 80% of the total sample is taken each time to train the model and predict it, make the recall-precision curve, and take the F1 value at the maximum for effect evaluation. For the supervised algorithm, 80% of the total samples are taken for training and the remaining 20% for testing. For the semi-supervised algorithms, where PUL, ADOA, and CPI all select 80% of the total samples as unlabeled samples and 10% of the anomalous samples as known anomalies for training. For each algorithm and each dataset, 10 independent experiments are conducted and the mean value of the evaluation metrics is taken as the final criterion.

Since the sample distribution is hugely unbalanced in the anomaly detection task, the percentage of anomalies is generally tiny and below 5% in most datasets. So that evaluation criteria like accuracy is not much significant. In this paper, we mainly use the AUC value and $F_{1}$-measure as our evaluation criteria, and the details are demonstrated as follows:

1. (1)

   AUC value measures the area under the ROC curve. The ROC curve plots false positive rate on x-axis and false negative rate on y-axis.

2. (2)

   $F_{1}$-measure is a joint measurement to evaluate the prediction performance, which takes both the Recall and Precision into consideration, and the valid formula is $F_{1}=\frac{2\times Recall\times Precision}{Recall+Precision}$. In the equation, Recall is the percentage of correctly detected anomalies compared with all the anomalies, and is calculated by $Recall=\frac{TP}{TP+FN}$. And Precision is the percentage of anomalies correctly classified as anomalies compared with the samples which are classified as anomalies, calculated as $Precision=\frac{TP}{TP+FP}$. By setting different thresholds in the classifier, we can attain corresponding PR curve, then we need to select a specific threshold to obtain the $F_{1}$-measure.

To evaluate the performance of our proposed method, the experiments are employed on loads of various benchmark datasets originating from different domains. Before experiments are performed, normalization is carried out for each data set on all coordinates.

We demonstrate that GALDetector outperforms or matches lots of state-of-the-art anomaly detection algorithms on various real-world benchmarks. The comparison of the performance of our method with other algorithms was demonstrated in the two tables below. Table II shows the best AUC that can be obtained by varying the parameter settings, and Table III displays the best $F_{1}$-measure by setting different thresholds simultaneously. As we can see from the two tables, GALDetector is the top performing or joint top performing algorithm in 4 out of the 8 datasets in terms of AUC value, and is the top performing or jointly top performing algorithm in 4 out of the 8 datasets in terms of $F_{1}$-measure respectively.

As is shown in the experiments, our proposed method GALDetector has more stable results on most of the datasets instead of only achieving excellent results on several datasets as other methods do. Compared with the state-of-the-art unsupervised anomaly detection methods, i.e., PCA, iForest, PIDForest and LOF, our proposed method achieves better performance on almost all evaluation metrics for all datasets. More specifically, GALDetector achieves gains of 7.03%, 2.59%, 1.13% and 25.51% on these four unsupervised methods in terms of overall AUC value respectively. Then in terms of overall $F_{1}$-measure, the improvements are 19.08%, 15.35%, 14.99% and 42.91% on them separately. This is because unsupervised anomaly detection methods do not use label information, and different methods tend to have distinct effects on different datasets.

We also contrast our method with supervised anomaly detection algorithms, i.e., Supervised SVM and KNN. The experimental results show that our method outperforms supervised methods to some extent. More explicitly, Our method achieves gains of 22.51% and 16.69% on these two supervised methods in terms of overall AUC value respectively. And in terms of overall $F_{1}$-measure, the improvements are 16.15% and 20.78% on these two methods simultaneously. It is that we do not simply fit the samples to learn an exact delineation criterion, however we integrate global and local information and select several potential abnormal samples.

When contrasted with semi-supervised anomaly detection methods, i.e., PUL, CPI and ADOA, GALDetector can get results comparable to these three methods, and GALDetector outperforms these methods on at least five of the eight datasets in terms of AUC value. Different from these methods, GALDetector does not utilize any anomaly information, instead it explores the patterns that normal samples should conform to, which is more suitable for real-world scenarios. Moreover, we can see significant enhancement in terms of overall $F_{1}$-measure, and the improvements are 14.46%, 4.93% and 15.84% on those three methods simultaneously.