Efficient support vector data descriptions for novelty detection

Efficient SVDD sampling with approximation guarantees for the decision boundary

Support Vector Data Description (SVDD) is a popular one-class classifier for anomaly and novelty detection. But despite its effectiveness, SVDD does not scale well with data size. To avoid prohibitive training times, sampling methods select small subsets of the training data on which SVDD trains a decision boundary hopefully equivalent to the one obtained on the full data set. According to the literature, a good sample should therefore contain so-called boundary observations that SVDD would select as support vectors on the full data set. However, non-boundary observations also are essential to not fragment contiguous inlier regions and avoid poor classification accuracy. Other aspects, such as selecting a sufficiently representative sample, are important as well. But existing sampling methods largely overlook them, resulting in poor classification accuracy. In this article, we study how to select a sample considering these points. Our approach is to frame SVDD sampling as an optimization problem, where constraints guarantee that sampling indeed approximates the original decision boundary. We then propose RAPID, an efficient algorithm to solve this optimization problem. RAPID does not require any tuning of parameters, is easy to implement and scales well to large data sets. We evaluate our approach on real-world and synthetic data. Our evaluation is the most comprehensive one for SVDD sampling so far. Our results show that RAPID outperforms its competitors in classification accuracy, in sample size, and in runtime.

An Efficient Representation-Based Method for Boundary Point and Outlier Detection

Detecting boundary points (including outliers) is often more interesting than detecting normal observations, since they represent valid, interesting, and potentially valuable patterns. Since data representation can uncover the intrinsic data structure, we present an efficient representation-based method for detecting such points, which are generally located around the margin of densely distributed data, such as a cluster. For each point, the negative components in its representation generally correspond to the boundary points among its affine combination of points. In the presented method, the reverse unreachability of a point is proposed to evaluate to what degree this observation is a boundary point. The reverse unreachability can be calculated by counting the number of zero and negative components in the representation. The reverse unreachability explicitly takes into account the global data structure and reveals the disconnectivity between a data point and other points. This paper reveals that the reverse unreachability of points with lower density has a higher score. Note that the score of reverse unreachability of an outlier is greater than that of a boundary point. The top- ranked points can thus be identified as outliers. The greater the value of the reverse unreachability, the more likely the point is a boundary point. Compared with related methods, our method better reflects the characteristics of the data, and simultaneously detects outliers and boundary points regardless of their distribution and the dimensionality of the space. Experimental results obtained for a number of synthetic and real-world data sets demonstrate the effectiveness and efficiency of our method.

Robust Novelty Detection via Worst Case CVaR Minimization

Novelty detection models aim to find the minimum volume set covering a given probability mass. This paper proposes a robust single-class support vector machine (SSVM) for novelty detection, which is mainly based on the worst case conditional value-at-risk minimization. By assuming that every input is subject to an uncertainty with a specified symmetric support, this robust formulation results in a maximization term that is similar to the regularization term in the classical SSVM. When the uncertainty set is l1 -norm, l∞ -norm or box, its training can be reformulated to a linear program; while the uncertainty set is l2 -norm or ellipsoidal, its training is a tractable second-order cone program. The proposed method has a nice consistent statistical property. As the training size goes to infinity, the estimated normal region converges to the true provided that the magnitude of the uncertainty set decreases in a systematic way. The experimental results on three data sets clearly demonstrate its superiority over three benchmark models.

Novelty detection using level set methods

This paper presents a level set boundary description (LSBD) approach for novelty detection that treats the nonlinear boundary directly in the input space. The proposed approach consists of level set function (LSF) construction, boundary evolution, and termination of the training process. It employs kernel density estimation to construct the LSF of the initial boundary for the training data set. Then, a sign of the LSF-based algorithm is proposed to evolve the boundary and make it fit more tightly in the data distribution. The training process terminates when an expected fraction of rejected normal data is reached. The evolution process utilizes the signs of the LSF values at all training data points to decide whether to expand or shrink the boundary. Extensive experiments are conducted on benchmark data sets to evaluate the proposed LSBD method and compare it against four representative novelty detection methods. The experimental results demonstrate that the novelty detector modeled with the proposed LSBD can effectively detect anomalies.