Matrix Decomposition Acceleration Method For Network Traffic Anomaly Detection

Network traffic anomaly detection is a critical task in Internet management.The traditional approaches based on Principal Component Analysis(PCA)are effective only when the corruption is caused by small additive i.i.d.Gaussian noise.Recently,the Direct Robust Matrix Factorization(DRMF)is proven to be more robust and accurate in anomaly detection.However,DRMF needs to reuse singular value decomposition(SVD)during the low-rank partial approximation of the network traffic matrix until the optimal solution is found,which makes the computational time complexity of DRMF very high.This paper focuses on the computational time complexity of DRMF in network traffic anomaly detection.The main work and innovation of this paper are as follows:1.Aiming at the computational complexity of DRMF in network traffic anomaly detection,this paper proposes an anomaly detection algorithm subspace-NoReuse based on subspace search.We present the equivalence of the low rank matrix approximation problem in DRMF to search the subspace problem,which makes the projection of the network traffic matrix on it have the minimum projection error.The algorithm can adaptive search subspace,realize fast approximation of low rank part of network traffic matrix,and indirectly realize fast detection of network traffic anomaly.It contains two novel key technologies:First,the multi-layer locality sensitive hashing table,which is used to rearrange the OD pairs row vector(the row vector consists of the traffic data between the source node and the destination node in the network),and promote the adaptive matrix division to fast find subspace;Second,the principle of adaptive matrix partitioning is used for matrix partitioning,and each time the sub-matrix with the largest projection error in the current subspace is chosen to be divided so that the overall projection error of the matrix is minimized.2.Based on the anomaly detection algorithm Subspace-NoReuse,this paper proposes a fast network traffic anomaly detection algorithm LSH-subspace,which consists of Subspace-NoReuse and lightweight localized hash table update algorithm.Among them,the lightweight locality sensitive hashing table update algorithm is a key algorithm of LSH-subspace.In the two successive iterations,the algorithm reuses the multi-layer locality sensitive hashing table established in the previous step,only a part of the row is updated in the current iteration step,and then using Subspace-NoReuse,makes the time complexity of adaptive search subspace is greatly reduced.Therefore,the low-rank partial approximation of network traffic matrix is further accelerated,and the detection of network traffic anomaly is indirectly further accelerated,which reflects the superiority of LSH-subspace in terms of network traffic anomaly detection speed.3.Simulation experiments are performed on the public traffic trace data.In this paper,two kinds of network traffic anomaly detection algorithms,Subspace-NoReuse and LSH-subspace,are compared with the current advanced network traffic anomaly detection algorithm.The experimental results show that the proposed algorithm is effective and achieves the effect of rapid detection of network traffic anomaly.Subspace-NoReuse and LSH-subspace anomaly detection speed up to 2.5 times and 3 times the DRMF,at the same time,both algorithms have high anomaly detection accuracy.