Outlier Detection via Online Oversampling in High Dimensional space

Abstract

Anomaly detection is an important topic in data mining. Many applications such as intrusion or credit card fraud detection require efficient method to identify deviated data instances, mostly anomaly detection methods are typically implemented in batch mode, and thus cannot be easily extended to large-scale problems without sacrificing computation and memory requirements. This paper proposes an online oversampling principal component analysis (osPCA) algorithm, and aim to detecting the presence of outliers from a large amount of data via an online updating technique. In prior principal component analysis (PCA)-based approaches, we store the entire data matrix or covariance matrix, and in proposed method there is no need to store the entire data matrix or covariance matrix thus this approach is especially of used in online or large-scale problems. Oversampling the target instance and extracting the principal direction of the data, the proposed osPCA allows determining the Anomaly or outlier of the target instance according to the variation of the resulting dominant eigenvector. In the proposed method osPCA need not perform Eigen analysis, so the proposed method is applicable for online applications Compared with the well-known power method for PCA and other popular anomaly detection algorithms, o ur experimental results verify proposed method is feasible in terms of both efficiency and accuracy.