孤立点挖掘技术在入侵检测系统中的应用(3)
入侵检测系统能够适时的检测网络状态，遇到攻击能够主动向管理员报警，这种主动式防御的入侵检测系统的出现弥补了防火墙的不足。但是入侵检测系统同样有一些致命缺点，检测速度慢，漏报和误报情况严重，同其他网络安全设备互动性能差。因此面对飞速发展的网络技术，迫切需要研究更智能化、自动化、小吕更高的入侵检测方法。
2.2 数据挖掘
数据挖掘是从大型数据集中，挖掘隐含其中的、人们事先不知道的、对决策有用的知识的过程。
2.2 知识发现过程
2.3 孤立点挖掘技术
孤立点挖掘在数据领域是一项重要的挖掘技术。孤立点是在数据中与众不同的数据，其可能是由于测量数据、计算机录入错误、网络数据传输错误、人为错误等原因引起。许多数据挖掘算法试图使孤立点的影响最小化或者是排除它们，但是孤立点也可能隐藏着重要信息，所以对于孤立点应该给予保留并加以分析。总之，孤立点探测和分析是一项重要的、有意义的工作。
孤立点算法能够应用在入侵检测中是建立在两个基本假设之上：
(1)正常数据的数量远远大于入侵数据量；
(2)入侵数据在某些属性的取值偏离正常取值范围。
目前能直接应用于检测系统的孤立点挖掘算法相对较少，本文将给予聚类和密度的两种算法作为研究重点，加以改进。
3.CLARANS算法
3.1 CLARANS算法基本过程
聚类分析方法是数据挖掘的重要手段之一，它是用数学方法研究和处理所给数据对象的分类以及各类之间的亲疏程度，对所给未标记数据对象进行分析的工具。它将物理或抽象的对象集合划分为由类似的对象组成的多个簇。
聚类算法中CLARANS,DBSCAN,BIRCH等都具有一定的噪声处理能力，可用于孤立点检测系统。本文针对CLARANS算法做出一定的研究工作。
CLARANS（Cluster Larger Application based upon Randomized Search,也称随机搜索聚类算法）是一种基于划分的聚类算法，属于k-中心算法(k-medoids)的变种。
CLARANS算法在执行过程中并不检查一个结点的所有邻居结点，而是随机检查一定数量的邻居结点，邻居结点的数目被用户定义的一个参数(numlocal)加以限制。如果所选择的那些邻居结点的代价都比当前结点的代价大，那么，就认为当前结点为局部最小代价结点。CLARANS算法将多个局部最小代价结点中代价最小的那个结点作为结果输出。
CLARANS算法的描述如下：
输入：检查到的最大邻居数maxneighbor和寻找局部最小代价结点的次数numlocal。i设为1，mincost设置为一个大整数：
输出：局部最小代价结点bestcode
1) 在等待检测的图中任意选择一组k个初始中心点，记为初始节点Current;
2) 将j设置为1；
3) 在Current的邻居中随机选择一个结点S，并计算S与Current的代价差；
4) 如果S的代价小，则Current设为S，转向3）；
5) 如果Current的代价小，j++，如果j<maxneighbor，转向4）；
6) 如果j=maxneighbor，比较Current的代价与mincost，如果Current的代价较小，则将mincost设为Current的代价，将bestnode设为Current;
7) i++，如果i>numlocal，输出bestnode并停止；否则，转向2);
CLARANS算法不断迭代寻找局部最小代价结点，并划分出k个簇。于是就可以区分正常与异常数据；将所有的簇按其中包含的数据量大小排列，并设定一个比例数N，那些位于N以上的包含量最多的簇被判断为正常簇，其余的簇为异常，即孤立点集合。这种方法简单，易于理解和实现。但是该方法的缺点同样明显，由于孤立点在数据总量中所占的比例很小，算法的随机性取样方式极有可能将这些孤立点忽略，所以本文给出一些改进思想，有效改善CLARANS算法的性能。