网络异常检测的无监督聚类方法

1、Unsupervised clustering approach for networkanomaly detection文献阅读笔记论文：网络异常检测的无监督聚类方法本文描述了无监督聚类方法在检测未知的网络入侵或攻击方面的应用。给出了五种聚类 算法和它们在实际情况中的具体表现。五种聚类算法分别是：k-Means算法，改进的k-Means 算法,k-Medoids算法,EM聚类法和基于距离的孤立点检测法。k-Meansk-Means是机器学习中最简单的一种聚类算法，算法需要事先定好类别的个数K，第一 步是选择K个实例集合作为聚合质心，通常每个集合选择一个实例即可，尽可能远的能使 每个类别分开。

2、具体算法如下：Select the total number of clusters (k)选择聚合类别的个数 KChoose random k points and set as centroid随机选择K个点和集合作为聚心Calculate the distance from each instance to all centroids using Euclidean method 使用欧 几里德方法计算每个实例到聚心的距离Assign each instance to the closest centroid将每个实例分配到距离最近的聚心的集合Recalculate the positi

3、ons of the centroids 重新计算各个聚心的位置Repeat step 3-5 until the centroids do not change 重复 3-5 步，直到聚心不再改变k-Medoidsk-Medoids算法和k-Means类似，但是本算法能将实例到聚心的距离最小化.一个 medoid定义为用来代表一个类集的模板数据点。k-Means算法对噪声和离群值比较健壮。具 体算法如下：Input a data set D consists of n objects 输入有个 n 对象的数据集 DInput the number of clusters K 输入聚合类别的个

4、数 KSelect k objects randomly as the initial cluster centres or cluster medoids 随机选择 K 个 对象作为初始化聚心或medoidAssign each object to the cluster with the nearest medoid 将每个对象分配到距离最近的 medoid的集合Calculate the total distance between the object and its cluster medoid 计算对象到它的 medoid的总距离Swap the medoid with non-m

5、edoid object 交换 medoid 和非 medoidRecalculate the positions of the k medoids 重新计算 K 个 medoids 的位置Repeat 4-7 until the medoids become fixed 重复 4-7 步，直到 medoids 不再改变EM ClusteringExpectation Maximization (EM) clustering最大期望聚类法是变种的k-Means算法，广泛 使用在非监督聚类的数据点密度估计上。EM计算使数据的似然值最大的参数，假定数据由 K个正态分布生成.，算法同时得到正态分布的

6、方法和协方差。算法需要输入数据集、聚合 的类别个数、最大误差公差、最大迭代次数。EM可分为两个重要过程E过程(E-step)和M过程(M-step).E-step目的是计算每个实例的似然值的期望，然后用它们的概率估计重新标记每个 实例。M-step的目的是重新估计参数值，输出参数值作为下一个E-step的输入。两个过程反复迭代计算，直到结果收敛。Outlier Detection Algorithms孤立点检测(Outlier detection)是为了找到数据中不合预期的行为的数据模式。大多 数的聚类算法虽然不是为所有的点分配类别，但在在计算中其实都把噪声对象考虑了进去。 Outlier d

7、etection算法首先实现一个聚类算法然后检索噪声集。因此算法的效果取决于聚类 算法的好坏。算法有两种实现方式：基于距离的孤立点检测和基于密度的孤立点检测。基于距离的孤立点检测，假设正常的数据对象有一个密集的分布区，孤立点距离那些区 域很远。论文只给出了基于距离的孤立点检测算法。通过nested loop (NL)算法来计算每一 对儿对象的距离，而那些远离大多数对象的则被标记为孤立点。基于密度的孤立点检测，假设正常的数据对象的密度与其相邻分布区密度相似，孤立点 则大相径庭。算法通过计算孤立值来比较这种密度差异。Experimental Setup 实验过程Intrusion Dataset

8、入侵数据集试验使用的是NSL-KDD入侵数据。训练和测试数据都出现的入侵数据：back, buffer_overflow, ftp_write, guess_passwd, imap,ipsweep, land, loadmodule, multihop, neptune, nmap, phf, pod, portsweep, rootkit, satan, smurf,spy,teardrop,warezclient,warezmaster。只在测试数据中出现的入侵数据：apache2,httptunnel,mailbomb,mscan,named,perl,processtable,ps,

9、saint,sendmail,snmpgetattac k,snmpguess,sqlattack,udpstorm,worm,xlock,xsnoop,xterm。训练数据集包含有25191个实例，测试数据集包含有11950个实例。四十种不同入侵分为四类：DoS (Denial of Service), R2L (Remote to Local Attack),U2R(User to Root Attack) and Probing Attack,Performance Metric 评价指标我们使用准确率和误报率作为评价指标:Actual Result 真实值IntrusionNormal

10、Predicted Result预测值IntrusionTrue Positive (TP)False Positive (FP)NormalFalse Negative (FN)True Negative (TN)用如下公式计算准确率和错误率：Accuracy rate = TP+FN(1), False Positive = (2)JTP+TN+FP+FN TP+FP 7Misuse Detection Module 错误检测模块错误检测模块包括五个阶段：特征提取 feature extraction降维 dimensionality reduction分类算法 classificatio

11、n algorithms模型应用apply model性能测试和分析 performance measurement & analysis。Anomaly Detection Module 异常检测模块Fig. 2. Anomaly Detection System Design给定一个训练数据集，平均和标准偏差特征向量计算方法如下:1 Navg_vectorj = instancestd_vectorj= N avg_vectorj)2i=i然后训练集中每个实例（特征向量）做如下转换：.rvectorf/lstd_vectorjnew_instancej-Experimental Resul

12、ts and Discussion 实验结果及分析6.1Misuse Detection Module 错误检测模块在第一个实验中，我们只使用训练数据包含大约22个不同的类型的已知入侵。结果见表 所示：AlgorithmAccuracyFalse PositiveNaive BayesS9.59%10,60%Nearest Neighbour99.44%0.60%Rule Induction99.58%0.40%Decision Tree99.56%0.40%表中可见四个算法中有三个实现了高于99%的准确率和低于1%的误报率。效果显著。在第二个实验中，我们使用一个错误检测模块的测试数据集评价的

13、入侵检测模块的性 能。测试数据含有22种已知的入侵和18种未知的入侵。结果见表所示：AlgorithmAecu racyFalse PositiveNaive Bayes55.77%34.80%Nearest Neighbour624%20.90%Rule Induction63.69%Decision Tree63.97%17.90%表中可见由于有大量的未知入侵数据，错误检测模块效果不是很好。最准确率仅为 63.97%,最低的误报率是17.90%。6.2 Anomaly Detection Module 异常检测模块我们实现了五种非监督聚类算法，分别是： k-Means算法，改进的k-Mea

14、ns算法, k-Medoids算法，EM聚类法和基于距离的孤立点检测法。使用一个未标记的数据集作为输 入。结果见下表：AlgorithmAccuracyFalse Positivek-Means57.81%22.95%improved k-Mcans65.40%21.52%k-Mcdoids76.71%2L83%EM clustering78.06%20.74%Distance-based outlier detection80.15%21.14%与上一个错误检测模块相比，异常检测模块在检测新异常的表现上显然更好一些。这 些聚类算法能够在没有先验知识的情况下检测入侵。实验中outlier detection算法达到了最 好的准确率80.15%,第二好的是EM clustering算法78.06%, k-Medoids达到76.71%,改进的 k-Means达到65.40%，k-Means达到57.81%。遗憾的是误报率也都超过20%。因此，我们 未来的工作将集中在如何减少误报同时还提高准确率。各个算法的执行时间如下图:把入侵数据集分类为四个类型的入侵后，再用outlier detection