Spectral methods for outlier detection in machine learning

Abstract

Outliers are those instances in a sample that deviate signi cantly from the others. Their identi cation bears much importance since they carry valuable and actionable information in many real life scenarios. Spectral methods are unsupervised learning techniques that reveal low dimensional structure in high dimensional data. We analyze spectral methods, such as, Principal Components Analysis (PCA), Laplacian Eigenmaps (LEM), Kernel PCA (KPCA), Multidimensional Scaling (MDS) and present a uni ed view. We argue that the ability of such methods to reduce dimensionality is valuable for outlier detection. Hence, we propose spectral outlier detection algorithms where spectral decomposition precedes outlier detection. The four outlier detection methods we use are Active-Outlier, Local Outlier Factor, One-Class Support Vector Machine and Parzen Windows. We combine these methods with the spectral methods of LEM and MDS to form our algorithm. We evaluate the performance of our approach on various data sets and compare it with the performance of outlier detection without spectral transformation and with PCA. We observe that combining outlier detection methods with LEM increases the outlier detection accuracy. We discuss how the unique characteristics of LEM make it a valuable spectral method for outlier detection. We also con rm the merits of our approach on a face detection problem. Additionally, we provide an outlier detection toolbox in MATLAB that will be useful for researchers in this eld containing the implementations of the outlier detection algorithms and the spectral methods discussed in this thesis.