孤立点挖掘技术在入侵检测系统中的应用(4)
3.2 改进思想
为了解决这个问题，我们针对CLARANS算法邻居结点的选定方法进行了改进。有当前的结点Current划分出的k个簇中，分别为每个簇计算出离簇中心点最远的t个对象，将这t个对象依次替换包含他们的簇中心点，形成t个Current的邻居结点，计算这些邻居结点与Current的代价差，如果比Current的代价小，将Current更新，这样孤立点就可能被准确的划分到新的簇中。
改进后的算法执行步骤描述如下：
1） 设置i=1，执行原算法的描述至第6步；
2） For in Current
3） 在p为中心点的簇内，计算出离中心点p最远的t个对象；
4） 将这t个对象一次转换p点，形成Current的邻居结点S’,并计算其与Current的代价差；
5） 如果S’的代价较小，则Current设为S’；
6） 转向2），直到由Current结点划分出的所有簇都被计算；
7） i++，如果i>numlocal，输出bestnode并停止；否则，转向1）；
3.3 CLARANS算法改进前后对比
原算法的缺点在于由于孤立点在数据总量中所占的比例很小，算法的随机性取样方式极有可能将这些孤立点忽略，而改进后的算法对邻居结点的选取条件做了进一步的限制，减小随机性，更利于检测孤立点。
4.LOCI孤立点算法
现实中的数据源通常随着时间的变化而变化，使得原有算法分析得到的孤立点可能会有更新。获取新孤立点的方法有两种重新计算和增量计算，由于我们通常面对的都是大数据集，重新计算，一方面代价太大，另一方面，因未利用有关历史信息，而导致重复计算。
本章先介绍基于密度的局部关联识别算法(Local Correlation Integral，LOCI),然后提出本文的改进方法。
4.1LOCI算法
基于密度的局部关联识别算法不再把异常看做是一种二元属性，而是用局部关联识别因子来表示对对象的异常程度。由于在数据库中的对象可以看做多文空间中的一个点，因此后面的文章我们混用了“对象”和“点”表示数据集合中对象。
为了更清晰明了的判定孤立点，我们先定义一下几个术语：
1） 对于任意正实数r，任意对象 的r-邻域是一个对象集，它包含了所有与对象 之间的距离不超过r的对象，即
2） 为对象 的r-邻域中的对象总数，即 =
3）
4）
定义1、对于p的多粒度偏离因子
对于任意对象 ，给定了r和 ,对象 的多粒度偏离因子定义为：
中永远包含 本身，也就是说 ，这就意着公式 永远成立
定义2、计算领域和取样领域
统计邻域为一个对象的半径为 r的邻域，而取样邻域为它的半径r的邻域
4.1统计和取样邻域示意图
则实线圈区域就是 的统计区域，另外 的取样区域中包含了三个点 、 、 ，我们也用虚线画出了它们的统计区域，于是我们定义：
为确保每个对象的邻居包含足够的对象，取样区域的计算半径一定要足够大，所以 值一般取1/16.
定义3、孤立点判定
多粒度偏离因子的定义抓住了异常的精髓，接着我们定义局部关联识别因子(Local Correlation Integral Factor) ,如果某个对象满足 这个条件，那么我们就认为它是孤立点。
4.2LOCI算法改进
原算法只适应于静态环境，如果数据集中的某个对象发生变化，则需要重新计算集合中所有对象的LCIF值，由于计算LCIF的时间复杂度太高，将LOCI算法直接应用于动态的数据库环境是不现实的。通过对LCIF特性的研究可知，每个数据对象的LCIF值，仅与该对象所处的局部环境有关，数据更新一般也仅对某些相关对象的异常程度造成异响。因此，针对动态数据环境，特别是网络入侵检测的实际需要，提出一种动态的局部异常检测更新挖掘算法（DLOCI）,在原有计算结果的基础上，只对受影响的部分数据重新计算，可以避免重新计算所有对象的LCIF值，从而在动态环境下大大提高孤立点的挖掘速度。