Year: 2019

Abstract:
This paper proposes a novel method to detect anomalies in large datasets under a fully unsupervised setting. The key idea behind our algorithm is to learn the representation underlying normal data. To this end, we leverage the latest clustering technique suitable for handling high dimensional data. This hypothesis provides a reliable starting point for normal data selection. We train an autoencoder from the normal data subset, and iterate between hypothesizing normal candidate subset based on clustering and representation learning. The reconstruction error from the learned autoencoder serves as a scoring function to assess the normality of the data. Experimental results on several public benchmark datasets show that the proposed method outperforms state-of-the-art unsupervised techniques and is comparable to semi-supervised techniques in most cases.

heading: 1 INTRODUCTION
text: Anomaly detection refers to the identification of patterns that do not conform to expected normal behavior (Chandola et al. (2009)). It is a critical task in diverse application domains such as fraud detection (Phua et al. (2010)), intrusion detection (Lazarevic et al. (2003)) and surveillance video profiling (Xiang & Gong (2008); Saligrama et al. (2010)). While the concept of an anomaly is intuitively easy for humans to understand, it is hard to define mathematically. Fundamentally, an anomaly is something with insufficient similarity to the rest of the data. This similarity can be computed on the basis of some feature difference. However, what makes an ideal feature representation for the data depends on what constitutes an anomaly. This forces anomaly detection into a chicken-or-egg problem in which there are a pair of problems, neither of which can be solved before the other.
To date, a number of works have attempted this problem by training an autoencoder to create lowdimensional representations for anomaly detection (Chalapathy et al. (2018); Zhai et al. (2016); Zong et al. (2018)). The anomalies are rejected and the autoencoder retrained (Mishne & Cohen (2017); Wang et al. (2017)). While this gives reasonable results, it is fundamentally dependent on how well the first iteration solves the problem.
We propose a solution in which anomalies can be defined using approximately correct features. This is achieved through an observation. Given a feature, anomalies approximately correspond to instances of high variance distributions. Such instances can be identified using a distribution-clustering (Lin et al. (2018)) framework. This hypothesis provides a reliable starting point for normal data selection. We train an autoencoder from the normal data subset, and iterate between hypothesizing normal candidate subset and representation learning. The reconstruction error serves as a scoring function to assess the normality of the data. The proposed framework does not rely on any training labels. Instead, it iteratively distills out anomalous data and improves the learned representation of normal data by incorporating clustering techniques into the process.
We extensively assess the broad applicability of the proposed model on network intrusion, image and video data. Empirical results show that the proposed method outperforms the existing state-of-art approaches in terms of both accuracy and robustness to the percentage of anomalous data.

heading: 2 RELATED WORKS
text: Existing anomaly detection methods can be grouped into three categories.
Reconstruction-based method These methods assume that anomalies are incompressible and thus cannot be effectively reconstructed from low-dimensional projections. Classical methods like Principle Component Analysis(PCA) (I.T.Jolliffe (1986)) and Robust-PCA (Candès et al. (2011)) are motivated by this assumption. In recent works, different forms of deep autoencoder are proposed to analyze the reconstruction error. Xia et al. (Xia et al. (2015)) show that by introducing a regularizing term to a convolutional autoencoder, the anomalies tend to produce a bigger reconstruction error. Variational Autoencoder (VAE) (An & Cho (2015)) and Generative Adversarial Networks (GANs) (Schlegl et al. (2019)) have also been introduced to perform reconstruction-based anomaly detection. These methods demonstrate promising results when the anomaly ratio is fairly low. Although the reconstruction of anomalous samples, based on a reconstruction scheme optimized for normal data, tends to generate a higher error, a significant amount of anomalous samples could mislead the autoencoders to learn the correlations in the anomalous data instead.
Density estimation and clustering Motivated by the assumption that anomalies occur less frequently, these algorithms treat anomalies as low-density regions in some feature space. Clustering analysis, such as Robust-KDE (JooSeuk Kim & Scott (2008)), is often used for density estimation and anomaly detection. Unfortunately, due to the curse of dimensionality, these methods are less applicable to analysing high-dimensional data, where density estimation is a challenge in itself.
A two-step approach is normally adopted to counter this issue, where dimensionality reduction is conducted first, followed by clustering analysis as a separate step. One drawback of this approach is that dimensionality reduction is trained without the guidance from the subsequent clustering analysis; hence the key information for clustering analysis could be lost during dimensionality reduction. Recent works jointly learn dimensionality reduction and clustering components based on deep autoencoder (Zhai et al. (2016); Zong et al. (2018)). Notably, DAGMM (Zong et al. (2018)) utilizes an autoencoder to generate a low-dimensional representation and its reconstruction error, which is further fed into an estimation network based on Gaussian Mixture Model(GMM). However, as its autoencoder was trained on the whole dataset, it is vulnerable to a high percentage of anomalous samples and may learn wrong correlations. In contrast, our proposed method addresses this issue by first finding a normal candidate subset to train an autoencoder and then iterating between representation learning and refinement of the normal candidate.
One-class classification One-class SVM (Erfani et al.; Chalapathy et al. (2018)) is also widely used. Under this framework, a discriminative boundary surrounding the normal instances is learned by algorithms. However, when dimensionality goes higher, such techniques often suffer from suboptimal performance due to the curse of dimensionality. OCNN (Chalapathy et al. (2018)) attempted to circumvent this problem by using an autoencoder for dimensionality reduction. However, OCNN requires training data with relatively low anomaly ratio, in order to obtain an optimized NN model to differentiate anomalies from single-class normal data.

heading: 3 PROBLEM FORMULATION
text: Let X = {xi}, i = 1, . . . , N , x ∈ Rk be the set of input data points that contains a certain percentage of anomaly. The goal of anomaly detection is to learn a scoring function h(x), h : Rk 7→ R, to classify samples xi based on some threshold λ:
yi = { 0, if h(xi) < λ 1, if h(xi) ≥ λ
(1)
where yi are the labels. yi = 0 indicates xi is normal and yi = 1 indicates anomalous.
An overview of the proposed end-to-end anomaly detection system is presented in Fig. 1. The major component of this system is an autoencoder that learns a low-dimensional representation of the input data that are often of high dimensions, to enable simplified modeling of the underlying distribution of the data. Under a fully unsupervised setting, the only information we are given is the set of input data X, without any label information. As an initialization, we leverage the latest clustering technique for high-dimensional data (Lin et al. (2018)) to provide soft supervisory signals.
Since our input data is unlabelled, we derive a “training” set Strain, where Strain ⊂ X based on the following:
Strain = C(X, p0) (2)
where C represents a selection process based on clustering output, and p0 represents the percentage of anomaly, it controls which are the clusters to be accepted into the “training” set. In our experiments, we compute the threshold as the (100− p0)th percentile of cluster variance, and accept clusters with variance smaller than this threshold. The assumption here is that clusters with large variance are likely to contain anomalous members.

heading: 3.1 SCORING FUNCTION LEARNING
text: The autoencoder network provides two sources of features: (1) a low-dimensional representation of the original input data; and (2) the reconstruction error by comparing the input with its decoded counter-part. Using the training set Strain = {s1, s2, · · · , sM}, the autoencoder learns the encoding function fen: zc = fen(s; Θen), ∀s ∈ Strain, zc ∈ Rkbn (3) where Θen are the learned parameters for the encoder. zc are known as the bottle-neck features of dimension kbn.
Similarly, for the decoding part, we have:
x′ = fde(zc; Θde), (4)
where Θde are the learned parameters for decoding. x′ are the reconstructed features.
Upon training, we have a learned autoencoder with optimized parameters {Θen,Θde}. We run the entire input set X forward through the encoder network and produce a set of new features Z = {z1, z2, · · · , zN}, by concatenating the bottle-neck feature with the reconstruction error:
z = [zc; zr] , z ∈ Rkbn+1, (5)
where the reconstruction error zr is measured in terms of cosine similarity between x and its decoded counter-part:
zr = d(x,x ′) = cos−1
( xTx′
‖ x ‖‖ x′ ‖
) (6)
Note that Z is now of a much lower dimension than the input data X. Hence, traditional clustering techniques such as Gaussian Mixture Model would suffice for subsequent training set selection. To ensure the initial training set can capture most of the normal samples, we adopt a more conservative cluster variance threshold.
With the new encoding scheme, the entire input set X is now represented as Z. We can “re-label” the training set X by using Z as a proxy. Similar to the initial training set selection, we select members that belong to low-variance clusters in Z. The process of Training set selection → Autoencoder training→ New feature computation is performed iteratively. The training set is updated as follows:
Zt+1train = C(Z t, p), (7)
St+1train = {xj : ∀zj ∈ Z t+1 train}, (8)
where the superscript t here refers to the tth iteration.
Finally, the training process terminates when there is no change in the set of selected normal samples between two successive iterations. After the last iteration, t = tF , we obtain the autoencoder parameters {ΘtFen,Θ tF de}, and use it to construct the scoring function:
h(x) = d(x,x′) = d(x, fde(fen(x; Θ tF en); Θ tF de )), (9)
where x′ is the result of going through the encoding-decoding process according to the trained autoencoder.

heading: 3.2 ALGORITHM
text: The proposed framework is summarized in Algorithm 1. We obtain an initial split of the data into normal and abnormal subsets through clustering (i.e. GMM for KDDCUP data and Distribution Clustering (Lin et al. (2018)) for image and video data). Selected outputs for CIFAR-10 and MNIST datasets using Distribution Clustering are presented in Fig. 4 in the appendix. We observe that as cluster variance increases, the samples’ appearance become more anomalous.
Algorithm 1 Deep end-to-end Unsupervised Anomaly Detection Input: X = {xi}, i = 1, 2..., N : set of normal and anomalous input examples.
r: number of epochs required for re-evaluation of the membership of the entire input set X. p0 and p: thresholds for initial and subsequent training set selection, respectively
Output: Reconstruction-based anomaly score function h(x) and trained autoencoder {ΘtFen,Θ tF de},
1: procedure GET DECISION SCORE(X, r, p, fen, fde) 2: Strain ← C(X, p0) . Run clustering, select instances from low-variance clusters 3: L = {k : ∀xk ∈ Strain} . L is the set of indices of selected normal training samples 4: Lold := ∅ 5: while setdiff(Lold,L) 6= ∅ do 6: for each epoch do 7: if ((CurrentEpoch+ 1) mod r) == 0 then . Re-evaluate normality every r epochs 8: Zc ← fen(X,Θen) . Bottle-neck features 9: X′ ← fde(Zc,Θde) 10: Zr ← d(X,X′) . Reconstruction error 11: Z← [Zc;Zr] 12: Strain ← C(Z, p) . Get new training set according to threshold p 13: Lold := L 14: L← Strain . Update set of indices for training samples 15: else 16: Train fen, fde on Strain to obtain {Θen,Θde} 17: end for 18: end while 19: ΘtFen = Θen, Θ tF de = Θde 20: Output h(x) according to finalized autoencoder {ΘtFen,Θ tF de} base on Eq. (9) 21: end procedure
Convergence Assuming a p% anomaly ratio, our algorithm starts with a tight cut-off, accepting clusters with variances below (100− p0)th percentile as an initial training set, where p0 > p. This ensures the initial training set is as pure as possible. Our assumption is that given partial normal data, the autoencoder would be able to learn a representation and generalize well on the “unseen” normal data that was discarded, and progressively recover them as iterations go on. Empirically, we plotted the AUROC, AUPRC and F-score for 20 iterations for the KDDCUP experiment, presented in Fig. 5 of the appendix. It demonstrates the convergence as iteration progresses. The same behavior was observed throughout our experiments on other datasets.

heading: 4 EXPERIMENTS

heading: 4.1 BASELINE METHODS
text: On the topic of anomaly detection, there exist different terminologies concerning the nature of supervision: (a) Algorithm uses label information of the normal class for training (label information could be used in part, or all of the stages of an algorithm); (b) No training labels are given, algorithm treats the entire dataset with both normal and anomalous classes as input. For the purpose of this paper, we term type (a) semi-supervised and type (b) unsupervised. We evaluate our proposed algorithm against the following state-of-the-art methods:
OC-NN (semi-supervised) One-class neural networks (OC-NN) (Chalapathy et al. (2018)) contains 2 major components: a deep autoencoder and a feed-forward convolutional network. The deep encoder is trained on normal data for representation learning. The trained encoder, with its parameters frozen, is subsequently used as the input layers of a feed-forward network with 1 extra hidden layer. Variants of OC-NN employ different activation functions (i.e. linear, sigmoid, relu) in the hidden layer. We report the best score attained among all possible activation functions in our experiments.
OC-SVM (unsupervised) One-class support vector machine (OC-SVM) (Erfani et al.) is a kernelbased method for anomaly detection. The algorithm searches for best-performing hyper-parameters γ (kernel coefficient) and ν (upper bound of the fraction of training errors and lower bound of the fraction of support vectors) to obtain the optimal AUROC (Buitinck et al. (2013)).
DAGMM (unsupervised) Deep autoencoding Gaussian mixture model (DAGMM) (Zong et al. (2018)), comprised of one compression net and one estimation net, is a method based on representation learning. The compression network provides low-dimensional representations of input samples and the reconstruction error features. They are fed into the estimation network, which functions as a Gaussian Mixture Model, to predict the mixture membership for each sample. We modify the original DAGMM algorithm by adding a small value to the diagonal elements of the covariance matrix. The model achieves better results than the reported score from the original work.
Deep anomaly detection using geometric transformations (semi-supervised) This method (Golan & El-Yaniv (2018)) employs a deep neural model to identify out-of-distribution samples of image data, given only the examples from the normal class. A series of geometric transformations are applied to the normal class to create a multi-class dataset. A deep neural net, trained using this dataset, is then employed to discriminate the transformations applied. Subsequently, given an unseen instance, the model applies each transformation on it and assigns membership scores. The final normality score is determined based on the combined log-likelihood of softmax response vectors.

heading: 4.2 DATASETS
text: We employ five benchmark datasets, namely, KDDCUP, MNIST, CIFAR-10, CatVsDog and UCFCrime, to evaluate our proposed method, together with other methods described above.
• KDDCUP: The KDDCUP network intrusion dataset (Lichman et al. (2013)) contains samples of 41 dimensions. Similar to (Zong et al. (2018)), categorical features are prepared by applying one-hot encoding. 20% of the ”normal” samples form the minority group, while the rest 80% are treated as ”attackers”. As ”normal” samples are the minorities, they are treated as anomalies
• MNIST: The MNIST dataset (LeCun & Cortes (2010)) consists of 60,000 gray-scale 28 × 28 images of handwritten digits from 0 to 9. We formulate an anomaly detection task as per described in (Chalapathy et al. (2018)) and (Zhou & Paffenroth (2017)), where 4,859 images of digit 4 are randomly sampled as normal instances and 265 images are evenly sampled from all other categories as anomalies.
• CatVsDog: The CatVsDog dataset consists of dogs and cats images of varying sizes, which are extracted from the ASIRRA dataset (Elson et al. (2007)) following the settings specified in (Golan & El-Yaniv (2018)). 12,500 images of dogs and 2,500 images of cats are sampled to form an anomaly detection task. The cat images are treated as anomalies.
• UCF-Crime: The UCF-Crime dataset (Sultani et al. (2018)) contains 1,900 long and untrimmed videos captured from CCTV cameras. It covers 13 real-world anomalies, including incidents like fighting, burglary, abuse and etc. In both of the training and testing sets, videos are of different length and anomalies happens at various temporal locations. Some of the videos may have multiple anomalies. In the experiment, we randomly select reasonably long videos with at least 1000 frames and anomaly ratio less than 0.35 across 4 categories.

heading: 4.3 EVALUATIONS
text: We adopt Area Under the curve of the Receiver Operating Characteristic (AUROC) as the main evaluation metric to measure the discrimination power of different models. AUROC is a standard method to assess the effectiveness of a classifier (Fawcett (2006)). It can be interpreted as the probability that an anomalous instance is assigned to a higher anomaly score than a normal instance (Davis & Goadrich (2006)). In this section, we compare the performance of our method against other baseline methods.
KDDCUP: Network Intrusion Data In this experiment, we divide the KDDCUP dataset following the setting in (Zong et al. (2018)). 50% of the data is reserved for testing by random sampling. From the remaining 50% of the data reserved for training, we take all samples from the normal class and mix them with different percentages of samples from the anomaly class to form the training set. Parameters for this experiment (see Algorithm 1) are set to: p0 = 35%, p = 30%, r = 10.
Table 2 and 3 reports the AUROC and AUPRC of OC-SVM, DAGMM and our model on the KDDCUP dataset after 200 epochs, with anomaly ratio in training set being 5%, 10% and 20%, respectively. It can be observed that the increase in ratio of anomalous data undermines the detection performance of OC-SVM and DAGMM more severely, while our method remains robust to such changes.
Figure 2 shows the Receiver Operating Characteristic (ROC) curves of different models when the anomaly ratio of the training data is 20%. In our unsupervised setting where no prior knowledge of normal class is known, our method is clearly more robust to contaminated training data.
Image Data In table 4, we compare the AUROC scores obtained from OC-NN, OC-SVM, DAGMM, Geometric Transformation and our model, based on multiple image datasets. It should be noted that Geometric Transformation approach trains on data from the normal class only (hence classified as semi-supervised). Our method, on the other hand, does not require label information.
Results in Table 4 demonstrate an outstanding performance of our method over other unsupervised approaches. In addition, on CIFAR-10, the performance of our proposed algorithm is comparable to that of Geometric Transformation, a semi-supervised method. In the last column of Table 4, we report results obtained using distribution clustering alone. The combination of distribution clustering and autoencoder significantly improves the discrimination against anomalies. Details of the parameters used in the experiments are reported in the appendix.
We make several key observations based on the attained results in Table 4. Unlike all other methods that tend to perform better on simpler datasets (e.g. MNIST), the advantage of our method becomes more evident on datasets with higher complexity. Notably, our method outperforms other unsupervised approaches on CIFAR-10 and CatVsDog. The shortfall of our method on MNIST dataset could be due to the adoption of NetVLad feature extractor (4096-d feature vectors), which may not be an ideal choice of feature representation since the images are pre-aligned and hence of low dimensionality. We repeat the same experiment using raw image features from MNIST. It shows improved AUROC score, suggesting that raw feature is a better representation.
We also observe that while our method is able to produce results comparable to semi-supervised approaches, the gap is wider on CatVsDog dataset as compared to CIFAR-10. We attribute this to the high noise level in the CatVsDog dataset. For example, some images consist of both dog and cats. Moreover, training on normal data (with augementation through geometric transformation) gives
Geometric Transform a natural advantage. According to (Elson et al. (2007)), ASIRRA dataset, from which the CatVsDog is extracted, is deemed extremely challenging for computers. Sample images of the dataset are presented in the appendix.
Video Data We apply the proposed approach on UCF-Crime dataset (Sultani et al. (2018)), with features extracted using C3D (Tran et al. (2015)) descriptor. In default C3D settings, every 16 frames are aggregated to generate 1 feature vector. As our method is unsupervised, it needs a sufficient amount of feature vectors for training. We select videos with at least 65 vectors (1040 frames).
In (Sultani et al. (2018)), although the AUROC score of each video category is not reported, the AUROC averaged across the entire testing set of UCF-Crime dataset is 75.4%. It is achieved by adopting a semi-supervised method of multiple instance learning (MIL). The AUROC scores on 4 randomly selected video categories, using our method and DAGMM, are reported in Table 7. The parameters used in training, as well as individual video-level scores are detailed in the appendix.
A good correspondence between the ground truth and our anomaly scores can be observed in Figure 3, where frames with anomalous events under the orange lines are assigned to higher anomaly scores. It can be observed that our method significantly out-performs DAGMM. Moreover, our method is able to produce AUROC higher than 75.4% for some action categories. Despite under a fully unsupervised setting, our method is as effective in detecting anomalies from video data as its semi-supervised competitor, demonstrating its strength in handling complex and high-dimensional data.
Run Time Excluding feature extraction and clustering process, on a single NVIDIA Tesla P100 GPU, our method takes 4 minutes 20 seconds on average to complete the CIFAR-10 experiment described above (consisting of 5,500 instances). This timing is averaged over 5 runs.

heading: 4.4 ABLATION STUDY
text: Initialization To examine the effect of adopting distribution clustering as the initialization method for high-dimensional data, a variety of other mainstream clustering methods, including K-means, HDBSCAN (McInnes et al. (2017)) and Gaussian Mixture Model (GMM) are used to replace the distribution clustering component in the initial normal subset selection. We compare results on the CIFAR-10 task.
For K-means and GMM, prior information on the number of clusters/components is set to 20, which is consistent with the setting of the GMM employed in the proposed model. For HDBSCAN, the minimum size of a cluster is set to 5, that follows the setting as distribution clustering. Table 6 reports the AUROC scores obtained from CIFAR-10 anomaly detection task with different clustering techniques. The results demonstrate that using distribution clustering initialisation provides better supervisory signals and leads to favourable performance.
To further understand the effectiveness of distribution clustering, we tabulated in the AUROC achieved using distribution clustering alone, for the experiments on image data (refer to right-most column of Table 4). Surprisingly, this result is even better than those of DAGMM and OC-NN on the challenging CatVsDog dataset.

heading: 5 DISCUSSION AND CONCLUSION
text: This paper presents an end-to-end method for anomaly detection under a fully unsupervised setting. The key insight of our algorithm is to model normal data. We leverage distribution clustering technique to make an educated guess on the normal data subset. By incorporating clustering to provide supervisory signals, we iterate between hypothesizing normal candidate subset and representation learning. This framework iteratively distills out anomalous data and improves the learned representation of normal data. Extensive experiments on benchmark datasets demonstrate our proposed method outperforms existing unsupervised approaches and is comparable to semi-supervised solutions in most cases.
Limitations and future work: Using only an autoencoder, our current method may be insufficient to handle highly complex patterns and hence falls short on difficult dataset such as CatVsDog. For future work, we seek to explore more sophisticated generative frameworks for representation learning.

heading: B CONVENGENCE
text: To investigate the convergence behavior, we plotted the AUROC, AUPRC and F-score for 20 iterations for the KDDCUP experiment in Fig. 5 in the appendix, where the ground truth anomaly ratio is 20%. It demonstrates the convergence as iteration progresses. The same behavior was observed throughout our experiments.

heading: C RESULT BREAKDOWN OF UCF CRIME
text: Video with less than 65 segments or anomaly ratio higher than 0.35 are not taken into consideration.
Results obtained after running 5 rounds of experiments. (take average and standard deviation)

heading: D NETWORK PARAMETERS
text: Table 8 reports the settings and parameters for each experiments.
Note: for video with small number of segments, the value of p is set to be larger because anomalous samples take larger proportion given the small number of total segments.
Note: Relu is adopted as the activation function except for static data where tanh is used instead.

heading: E PARAMETER OF DISTRIBUTION CLUSTERING
text: Please refer to the original work on distribution clusteringLin et al. (2018) for more information on parameters. Table 9 reports the parameters used for distribution clustering.

heading: F SAMPLE CATVSDOG DATA
text: Figure 7 and 6 presents some example images of dogs and cats from ASIRRA dataset.

Review summaries:
In the article, the authors solve the problem of anomaly detection using a fully unsupervised approach. They try to deal with the main challenge of anomaly detection: a lack of certainty on what defines normal data and anomaly one. For this purpose, the authors iteratively use: 1) autoencoders to learn the representation of the data; 2) applying in the latent space clustering to get a new training set and retrain autoencoders. The experimental results show that the author’s method performed better results than such a baseline model as one-class SVM and one-class NN. 

In this paper the authors propose a framework for anomaly detection. The method is based on autoencoders and reconstruction error, but instead of training the autoencoder using all the data-points, the method iteratively uses some form of clustering to determine the points which presumably belong to the normal set, and uses them for training the autoencoder. This helps make the method robust when the portion of anomalous data-points is high.

The paper proposed an unsupervised anomaly detection method for the scenarios where the training data not only includes normal data but also a lot of anomaly data. The basic idea of this paper is to iteratively refine the normal data subset, selected from the whole training data set. Specifically, the paper first train an auto-encoder (AE) and determine which are the normal data samples according to the reconstruction errors. Then, using the normal data to retrain the AE again, and re-select the normal samples. Repeat the above two steps until convergence.