面向网络流量异常检测的矩阵分解加速方法

摘要

网络流量异常检测是互联网管理中的一项重要任务。基于主成分分析（PCA）的传统方法仅仅对由小的独立同分布的高斯噪声引起的破坏是有效的。最近，直接鲁棒矩阵分解（DRMF）被证明在异常检测中表现出良好的鲁棒性和精度。然而，DRMF在进行网络流量矩阵的低秩部分逼近过程中需要重复利用奇异值分解（SVD），直到找到最优解，这使得DRMF的计算时间复杂度非常高。
　　本文围绕DRMF在网络流量异常检测中存在的计算时间复杂度问题进行深入研究，本文主要的工作和创新点如下：
　　1.针对DRMF在网络流量异常检测中存在的计算复杂度问题，本文提出基于子空间寻找的异常检测算法Subspace-NoReuse。我们把DRMF中的低秩矩阵逼近问题等价阐述为寻找子空间问题，该子空间使得网络流量矩阵在它上面的投影具有最小投影误差。该算法可以自适应寻找子空间，实现网络流量矩阵低秩部分快速逼近，间接实现网络流量异常快速检测，它包含两项新颖的关键技术：（1）多层局部敏感哈希表，该表用于重排OD对行向量（网络中源结点与目的结点之间的流量数据构成的行向量），促进自适应矩阵划分，快速寻找子空间；（2）自适应矩阵划分原则，该原则用于矩阵划分，每次都选择在当前子空间上投影误差最大的子矩阵进行划分，使得矩阵的整体投影误差最小化。
　　2.本文在异常检测算法Subspace-NoReuse的基础上，提出快速的网络流量异常检测算法LSH-subspace，该算法由Subspace-NoReuse和轻量级局部敏感哈希表更新算法组成。其中，轻量级局部敏感哈希表更新算法是LSH-subspace的关键算法，该算法在连续的两个迭代步骤中，重用前一步骤建立的多层局部敏感哈希表，在当前迭代步骤仅仅更新一部分行，然后，再运用Subspace-NoReuse，使得自适应寻找子空间的时间复杂度大大降低，从而，实现网络流量矩阵低秩部分逼近进一步加速，间接实现网络流量异常检测进一步加速，体现了LSH-subspace在网络流量异常检测速度方面的优越性。
　　3.在公开流量跟踪数据上进行仿真实验，将本文提出的两种网络流量异常检测算法Subspace-NoReuse和LSH-subspace，与当前先进的网络流量异常检测算法进行了对比，实验结果表明了本文所提算法的有效性，实现了网络流量异常快速检测的效果，Subspace-NoReuse和LSH-subspace的异常检测速度最高达到DRMF的2.5倍和3倍，同时，这两种算法都具有很高的异常检测精度。

目录

声明

第1章 绪论

1.1 研究背景及其意义

1.2 国内外研究现状

1.3 本文的研究内容

1.4 本文的组织结构

第2章 网络流量异常与相关技术概述

2.1网络流量异常的基本概念与分类

2.2 矩阵恢复技术概述

2.3 基于矩阵恢复的异常检测方法

2.4 局部敏感哈希概述

2.5 本章小结

第3章 基于子空间寻找的异常检测算法

3.1系统建模与方法概述

3.2 多层局部敏感哈希表

3.3 自适应寻找子空间算法

3.4 网络流量异常检测算法

3.5 本章小结

第4章 快速的网络流量异常检测算法

4.1 问题分析

4.2 轻量级局部敏感哈希表更新算法

4.3 快速的网络流量异常检测算法

4.4 算法复杂度分析

4.5 本章小结

第5章 仿真实验与结果分析

5.1 实验配置与检测指标

5.2 异常检测仿真实验结果及其分析

5.3 重排相似度验证实验结果及其分析

5.4 本章小结

结论

参考文献

附录A 攻读学位期间所发表的学术论文

附录B 攻读学位期间参加的科研项目

致谢