作为传统网络安全技术的一种合理补充手段,入侵检测技术逐渐受到了人们的广泛关注和研究。然而,入侵检测通常面临着比较庞大的数据源,因此,应用数据挖掘技术来从海量数据中发现入侵行为或正常行为模式就逐渐成为了入侵检测领域的一个重点研究方向。离群点检测方法作为数据挖掘中的一类方法,旨在寻找数据集中与大部分数据行为模式不同的数据,这也与入侵检测中试图发现异常行为数据的目标不谋而合。因此,如何合理地利用离群点检测来进行入侵检测也逐渐成为了离群点检测的一个重要应用领域和研究方向。本文根据现有的基于离群点检测的网络入侵检测算法的研究,提取出了基于离群点检测的网络入侵检测基本框架。通过分析该框架存在的问题,对其进行了改进,增加了选取参考样本的过程,从而剔除误标记点、降低算法对于训练数据集纯净性的依赖、以及降低检测过程的时间复杂度。为了解决参考样本选择过程中聚类数目难以确定的问题,引入了自然邻域图的思想,提出了基于自然邻域图的参考样本选取方法。利用自然邻域图具有一定的聚类能力这一特点,对训练数据集进行聚类,进而挑选出满足一定条件的簇作为候选簇,并计算得到参考样本。针对现有的基于离群点检测的网络异常检测算法手动设置异常阈值困难的问题,在前述研究的基础上,提出了能够自适应得到异常阈值的网络异常检测方法——基于自然邻域图的网络异常检测算法(NAD-NNG)。在建立正常行为轮廓阶段,算法首先利用选取参考样本过程中的小簇信息自适应的得到一个百分比值β;然后从所有样本的离群程度分值中选取第|X|×β个离群程度分值作为自适应得到的异常阈值。在异常检测阶段,通过选择待测样本的实际参考样本,来计算其离群程度分值,从而有效降低了检测阶段的时间复杂度。为了验证所提出的算法的有效性,本文在入侵检测基准数据集——KDDCUP99数据集上,选取了五个评价指标:检测率、误警率、分类正确率、ROC曲线、AUC值,进行了四个实验,即:选取参考样本的参数α的选择、过采样次数对检测结果的影响、算法对新攻击类型的检测结果、以及算法与其他三种入侵检测算法的对比。实验表明,所提出算法在降低了对参数选择依赖(尤其是对于异常阈值选择的依赖)的同时,仍然能够以一个较低的误警率和一个较高的检测率进行入侵检测,并且对新攻击类型有着一定的检测能力。