Unsupervised clustering approach for network
anomaly detection ——文献阅读笔记
论文：网络异常检测的无监督聚类方法
本文描述了无监督聚类方法在检测未知的网络入侵或攻击方面的应用。给出了五种聚类算法和它们在实际情况中的具体表现。五种聚类算法分别是：k-Means算法, 改进的k-Means算法, k-Medoids算法, EM聚类法和基于距离的孤立点检测法。
1 k-Means
k-Means是机器学习中最简单的一种聚类算法，算法需要事先定好类别的个数K，第一步是选择K个实例集合作为聚合质心，通常每个集合选择一个实例即可，尽可能远的能使每个类别分开。具体算法如下：
1. Select the total number of clusters (k) 选择聚合类别的个数K
2. Choose random k points and set as centroid 随机选择K个点和集合作为聚心
3. Calculate the distance from each instance to all centroids using Euclidean method 使用欧几里德方法计算每个实例到聚心的距离
4. Assign each instance to the closest centroid 将每个实例分配到距离最近的聚心的集合 5. Recalculate the positions of the centroids 重新计算各个聚心的位置
6. Repeat step 3-5 until the centroids do not change 重复3-5步，直到聚心不再改变
2 k-Medoids
k-Medoids算法和k-Means类似，但是本算法能将实例到聚心的距离最小化. 一个medoid定义为用来代表一个类集的模板数据点。k-Means算法对噪声和离群值比较健壮。具体算法如下：
1. Input a data set D consists of n objects 输入有个n对象的数据集D 2. Input the number of clusters K 输入聚合类别的个数K
3. Select k objects randomly as the initial cluster centres or cluster medoids 随机选择K个对象作为初始化聚心或medoid
4. Assign each object to the cluster with the nearest medoid 将每个对象分配到距离最近的medoid的集合
5. Calculate the total distance between the object and its cluster medoid计算对象到它的medoid的总距离
6. Swap the medoid with non-medoid object 交换medoid和非medoid
7. Recalculate the positions of the k medoids 重新计算K个medoids的位置
8. Repeat 4-7 until the medoids become fixed重复4-7步，直到medoids不再改变
3 EM Clustering
Expectation Maximization (EM) clustering最大期望聚类法是变种的k-Means算法，广泛使用在非监督聚类的数据点密度估计上。EM计算使数据的似然值最大的参数, 假定数据由K个正态分布生成.，算法同时得到正态分布的方法和协方差。算法需要输入数据集、聚合的类别个数、最大误差公差、最大迭代次数。
EM 可分为两个重要过程E过程(E-step) 和M过程(M-step).
1）E-step 目的是计算每个实例的似然值的期望，然后用它们的概率估计重新标记每个实例。
2）M-step 的目的是重新估计参数值，输出参数值作为下一个E-step的输入。 3）两个过程反复迭代计算，直到结果收敛。
4 Outlier Detection Algorithms
孤立点检测（Outlier detection）是为了找到数据中不合预期的行为的数据模式。大多数的聚类算法虽然不是为所有的点分配类别，但在在计算中其实都把噪声对象考虑了进去。Outlier detection算法首先实现一个聚类算法然后检索噪声集。因此算法的效果取决于聚类算法的好坏。算法有两种实现方式：基于距离的孤立点检测和基于密度的孤立点检测。
基于距离的孤立点检测，假设正常的数据对象有一个密集的分布区，孤立点距离那些区域很远。论文只给出了基于距离的孤立点检测算法。通过nested loop (NL) 算法来计算每一对儿对象的距离，而那些远离大多数对象的则被标记为孤立点。
基于密度的孤立点检测，假设正常的数据对象的密度与其相邻分布区密度相似，孤立点则大相径庭。算法通过计算孤立值来比较这种密度差异。 5
Experimental Setup实验过程
5.1 Intrusion Dataset入侵数据集
试验使用的是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,saint,sendmail,snmpgetattack,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。
5.2 Performance Metric评价指标
我们使用准确率和误报率作为评价指标：
Predicted Result 预测值 Intrusion Normal Actual Result 真实值 Intrusion True Positive (TP) False Negative (FN) Normal False Positive (FP) True Negative (TN) 用如下公式计算准确率和错误率：
5.3 Misuse Detection Module 错误检测模块
错误检测模块包括五个阶段：
1）特征提取feature extraction 2）降维dimensionality reduction 3）分类算法classification algorithms 4）模型应用apply model
5）性能测试和分析performance measurement & analysis。
5.4 Anomaly Detection Module异常检测模块
给定一个训练数据集,平均和标准偏差特征向量计算方法如下：
然后训练集中每个实例(特征向量)做如下转换:
6 Experimental Results and Discussion 实验结果及分析
6.1 Misuse Detection Module错误检测模块
在第一个实验中,我们只使用训练数据包含大约22个不同的类型的已知入侵。结果见表所示：
表中可见四个算法中有三个实现了高于99%的准确率和低于1%的误报率。效果显著。 在第二个实验中，我们使用一个错误检测模块的测试数据集评价的入侵检测模块的性能 。测试数据含有22种已知的入侵和18种未知的入侵。结果见表所示：
表中可见由于有大量的未知入侵数据，错误检测模块效果不是很好。最准确率仅为63.97%,最低的误报率是17.90%。
6.2 Anomaly Detection Module异常检测模块
我们实现了五种非监督聚类算法，分别是：k-Means算法, 改进的k-Means算法, k-Medoids算法, EM聚类法和基于距离的孤立点检测法。使用一个未标记的数据集作为输入。结果见下表：
与上一个错误检测模块相比，异常检测模块在检测新异常的表现上显然更好一些。这些聚类算法能够在没有先验知识的情况下检测入侵。实验中outlier detection 算法达到了最好的准确率80.15%, 第二好的是EM clustering算法 78.06%, k-Medoids 达到76.71%, 改进的k-Means 达到65.40% ， k-Means达到 57.81%。遗憾的是误报率也都超过20%。因此,我们未来的工作将集中在如何减少误报同时还提高准确率。
各个算法的执行时间如下图：
把入侵数据集分类为四个类型的入侵后，再用outlier detection算法检测结果如下：
7 Conclusions 总结
实验表明，错误检测技术在检测已知入侵方面能达到很好的性能，达到了高于99%准确率。但是当有大量未知数据时准确率仅仅63.97%。相反，异常检测技术的集中算法在未知数据上准确率都表现得良好，outlier detection 算法达到了最好的准确率80.15%，进一步的实验表明把入侵数据集分类后，再用outlier detection算法检测的效果更加好。因此,我们未来的工作将集中在寻找更先进的机器学习技术，来减少误报同时还提高准确率。
网络异常检测的无监督聚类方法
