Online Anomaly Detection With High Accuracy

Abstract

Anomaly detection is the identification of rare items, events or observations which raise suspicions by differing significantly from the majority of the data. Traffic anomaly detection is critical for advanced Internet management. Existing detection algorithms generally convert the high-dimensional data to a long vector, Moreover, they are generally designed based on the separation of normal and anomalous data in a time period, which not only introduces high storage and computation cost but also prevents timely detection of anomalies. Online and accurate traffic anomaly detection is critical but difficult to support. To address the challenge, this project directly models the monitoring data in each time slot as a 2-D matrix, and detects anomalies in the new time slot based on bilateral principal component analysis (B-PCA). A new novel techniques was proposed in Online BPCA to support quick and accurate anomaly detection in real time, including a novel BPCA- based anomaly detection principle that jointly considers the variation of both row and column principal directions for more accurate anomaly detection, an approximate algorithm to avoid using iteration procedure to calculate the principal directions in a close-form, and a sequential anomaly algorithm to quickly update principal directions with low computation and storage cost when receiving a new data matrix at a time slot. To the best of our knowledge, this is the first work that exploits 2-D PCA for anomaly detection.

Existing System

A novel multi-layer locality sensitive hashing (LSH) table to facilitate the matrix partition procedures. The table can reorder and buffer origin and destination (OD) pairs based on LSH function with various similarity levels in different layers, which allows the sub-matrices partitioned to hold OD pairs with higher correlations. To speed up the subspace searching and minimize the projection error, we propose a novel partition principle, which further partitions the sub-matrix that is least represented by the partial-subspace found until the dimension of the subspace reaches the desired k. To reduce the overall computation cost in the iterative process for anomaly detection, a lightweight algorithm was proposed to exploits the sparsity of the outlier matrix.

Proposed System

Several novel techniques was proposed in Online BPCA to support quick and accurate anomaly detection in real time, including a novel BPCA- based anomaly detection principle. It jointly considers the variation of both row and column principal directions for more accurate anomaly detection, an approximate algorithm to avoid using iteration procedure to calculate the principal directions in a close-form. And a sequential anomaly algorithm to quickly update principal directions with low computation and storage cost when receiving a new data matrix at a time slot.

Architecture

ARCHITECTURE DIAGRAM