Support Vector Data Description Based Novelty Detection And Kernel Feature Extraction

The goal of novelty detection(ND)is to distinguish between objects from target class(or normal class)and all other possible data from non-target class(or negative class).It is assumed that only examples of one of the classes,the target class,are available,while statistically-representative non-target data is absent.An example is a machine diagnostics problem,where measurements on all faulty operation conditions of a machine are very difficult.As a new type of one-class classifier,the support vector data description(SVDD)models the boundary of the target data by a hypersphere with minimal volume around the data.Analogous to the support vector classifier,the boundary is described by a few training objects,the support vectors.It has the ability to replace normal inner products by kernel functions to obtain more flexible data descriptions.As the fact that only the boundary of the data is modelled,SVDD is less dependent on the quality of the sampling of the target class.The SVDD can cope with situations in the exact density of the target class is unknown,but where just the area in the feature space can be estimated.Despite the usefulness of SVDD in novelty detection,however,conventional method may not identify the optimal solution of target description.The sensitivity to outliers in the target data is considered as one of the major problems that may affect the accuracy of the results.Moreover,the spherical description is a relatively conservative method,especially in the case of the polynomial kernel.Both of the above problems affect the performance of SVDD-based novelty detection.The goal of kernel feature extraction is to remove higher-order dependencies in the data to realize dimensional reduction and reveal the hidden,simplified structures that often underlie a complex data set.As another successful application of kernel methods,Kernel Principal Component Analysis(KPCA)can explore higher-order features by embedding the data into high-dimensional feature spaces using different kernels.Compared to other techniques for nonlinear feature extraction,kernel PCA has the advantages that it requires only the solution of an eigenvalue problem,not nonlinear optimization.From another perspective the fact that KPCA is completely nonparametric goes against improving classical method.In practice,it has two deficiencies: the lack of sparseness defeats the goal of obtaining both an informative and concise representation,and also leads to computational and storage problems.Besides,it can be affected by outliers so strongly that the resulting eigenvectors will be tilted toward them since the lack of robustness.Starting from Support Vector Data Description,this thesis treats the previous problems in novelty detection and kernel feature extraction.It starts with an introduction of the backgoruds of novelty detection and kernel feature extraction,followed by an overview of SVDD.Next,it explains the main work of this thesis.In the second chapter we present the basic theory of SVDD and discuss the problem of the choice of kernel functions.We also present a simple whitening preprocessing method suitable for SVDD to handle the large differences in variance along each feature direction when the data is mapped into kernel space.Besides,we elucidate the equivalence between SVDD and one-calss SVM.The possibility of determining the free parameters in the method based on an error estimate on the target set is also explored.In chapter three the robustness of SVDD is investigated.Conventional SVDD can suffer a lot from contaminated target data(e.g.,outliers or mislabeled observations),resulting in unreliable data descriptions.Assigning different weights to each observation in SVDD training process will alleviate its sensitivity to outlying objects.Several weighting schemes are compared and a robust SVDD is presented based on the Stahel-Donoho(SD)outlyingness,which can be calculated in arbitrary kernel spaces.Finally,a diagnostic plot is constructed to provide a visual representation of SVDD –based multivariate outlier detection,which is helpful for practitioners of SVDD to evaluate their model.In the fourth chapter a new type of data description method is presented,the ellipsoidal data description.As the fact that a spherical boundary only characterizes the data by its center and radius,SVDD can lead to large empty areas around the normal class in the input space in cases that the input dimensions are not isotropic or independent.An ellipsoid is thus preferred to model the heterogeneous dataset,which takes into account the differences in variance for each dimension as well as covariance between them.Discriminant for novelty detection is given and the problem of model selection is investigated in detail for ELPDD.A stability analysis for novelty detection is provided,as well as the Rademacher complexity bound for our model.The fifth chapter investigates the sparseness and robustness of KPCA.Inspired by the sparse solutions obtained from support vector machine,we exploit the possibility to introduce the merits of SVM into kernel PCA.The geometric interpretation of PCA as estimating the best-fit ellipsoid provides a way to parameterize kernel PCA.The associated optimal ellipsoid turns out to be a variant of SVM,which actually is the ELPDD proposed in Chapter 4.The resulting expansion for each principal component is sparse in that only support objects have nonzero weights.To overcome the issue of robustness,a robust distance is computed to identify the uncontaminated data subset.The following algorithms based on the “clean data” will not be affected much by potential outliers.Moreover,a kernel PCA outlier map is proposed to display and classify the outliers.The above study further enriches the methods and theories of support vector based data descriptions.Its application in novelty detection and kernel feature extraction is investigated.In particular,the ellipsoidal data description will have great significance in data mining and robust statistics.