7 聚类算法在网络入侵检测技术中的作用
7.1模式识别的概念
模式识别方法（Pattern Recognition Method）是一种借助于计算机对信息进行处理、判决分类的数学统计方法。在日常生产实践和社会研究中，往往所需处理的问题影响因素非常多且复杂，给问题的研究和解决增加了困难。模式识别方法可使人们在影响因素众多的情况下仍能对问题进行方便的处理，进而发现问题的解决途径和事物发展的潜在规律性。在一个多因素问题中，结果即目标与各因素即指标之间难以找出直接的联系，很难用理论的途径去解决。在各指标之间一时也寻找不到明显的关联，所能得到的只是些模糊的认识、由长期的经验所形成的感知和由测量所积累的数据。因此，若能用计算机技术对以往的经验、观察、数据进行总结，寻找目标与各指标之间的某种联系或目标的优化区域、优化方向，则对实际问题的解决是具有指导意义和应用价值的。模式识别方法正是基于此种思想，并获得广泛应用和取得较大成功的有效方法之一。

应用模式识别方法的首要步骤是建立模式空间。所谓模式空间是指在考察一客观现象时，影响目标的众多指标构成的多维空间。每个指标代表一个模式参量。假设一现象有几个事件（样本）组成，每一个事件都有P个特征参量（X1， X2，…Xp），则它就构成P维模式空间，每一个事件的特征参量代表一个模式。模式识别就是对多维空间中各种模式的分布特点进行分析，对模式空间进行划分，识别各种模式的聚类情况，从而作出判断或决策。
7.2模式分类
模式分类的方法有很多种，比如贝叶斯决策论，最大似然估计和贝叶斯参数估计，分参数技术，线性判别函数法，独立于算法的机器学习，利用这些方法，我们一直假设在设计分类器时，训练样本集中每个样本的类别归属是“被标记了”的，这种利用已标记样本集的方法称为“有监督”或“有教师”方法。
下面我们将介绍“无监督”或“无教师”方法，用来处理未被标记的样本集。
有许多理由使我们相信“无监督”方法是非常有用的：
1．收集并标记大型样本集是个非常费时费力的工作，若能在一个较小的样本空间上粗略地训练一个分类器，随后，允许它以自适应的方式处理大量的无监督的样本，我们就能节省大量的时间和精力。
2．存在很多应用，待分类模式的性质会随着时间发生缓慢的变化。如果这种性质的变化能在无监督的情况下捕捉到，分类器的性能就会大幅提升。
3．可以用无监督的方法提取一些基本特征，这些特征对进一步分类会很有用。
4．在任何一项探索性的工作中，无监督的方法都可以向我们揭示观测数据的一些内部结构和规律。
在无监督情况下，我们可以尝试以多种方式重新描述问题，其中之一是将问题陈述为对数据分组或聚类的处理。尽管得到的聚类算法没有很明显的理论性，但它们确实是模式识别研究中非常有用的一类技术。
下面我们详细介绍几种聚类算法并说明它们对入侵检测技术的贡献。
7.3基于异常的入侵检测技术
基于异常的入侵检测技术技术可以分为有监督的异常检测技术和无监督的异常检测技术，有监督的异常检测技术通过观察得到的正常数据建立正常数据模型，然后检测技术那些偏离正常模型的异常数据，一个比较典型的使用这种技术的系统是美国乔治梅森大学的MADAM/ID系统。这种方法能够检测技术新的攻击类型，因为这些新的攻击数据也会偏离正常的数据模型。有监督的异常检测技术的一个缺陷是需要一组完全正常的数据来训练获得模型，如果训练数据中包含攻击数据的话，这些攻击就很难检测技术到，因为该方法把这些攻击数据认为是正常数据，另一方面，要获取这些训练数据也是很困难的。
目前入侵检测技术技术研究的重点转移到了无监督的异常检测技术上，这种技术用一组没有标记的数据作为输入，发现其中存在的攻击数据，即试图从一组不知道什么是正常，什么是异常的数据集中发现那些异常的数据。无监督的异常检测技术与有监督的异常检测技术相比，它不需要完全正常的训练数据，只需要未加工的网络原始数据。无监督的异常检测技术技术有一个基本的假设，就是正常数据和异常数据有定性的不同，这样才可以将它们区分开来，例如通过一般的分析，可以知道拒绝服务攻击的数据在属性取值和模式上与正常的数据有很大的不同，所以可以利用无需指导的异常检测技术技术来有效地检测技术出拒绝服务攻击。
下面介绍的利用聚类算法的异常检测技术就是一种无监督的异常检测技术技术，这种方法可以在未标记的数据上进行，它将相似的数据划分到同一个聚类中，而将不相似的数据划分到不同的聚类，并为这些聚类加以标记表明它们是正常还是异常，然后将网络数据划分到各个聚类中，根据聚类的标记来判断网络数据是否异常。
7.4聚类算法简介
聚类算法是一个将数据集划分成若干个聚类的过程，使得同一聚类内的数据具有较高的相似性，而不同聚类中的数据不具有相似性。相似或者不相似根据描述数据的属性值来度量，通常使用基于距离的方法。通过聚类，可以发现数据的密集和稀疏的区域，从而发现数据整体的分布模式，以及数据属性间有意义的关联。
聚类算法涉及很多个领域，包括数据挖掘、统计、机器学习、空间数据库技术，目前研究重点是基于距离的聚类算法。聚类算法也是一种无指导的学习，它不像分类算法那样需要事先标记好的训练数据。聚类算法的输入是一个包含多个数据的数据集，每个数据通常用一个属性向量(x1,x2,...,xp)来表示，其中xi是一个连续的或离散的变量，代表数据的一个属性的取值。
聚类算法的输出是若干个聚类，每个聚类中至少包含一个数据，而且同一个聚类中的数据具有相似性，不同聚类的数据不具有相似性。
为了使用聚类算法，需要计算数据之间的差异，数据间的差异通常用距离来表示，距离计算方法包括欧几里德距离、Manhattan距离、Minkowski距离。其中最常用的是欧几里德距离，它的计算方法如下：

其中i,j分别代表数据集中的两个数据，它们都有P个属性。
可以给不同的属性赋以不同的权值，这样计算出来的距离称为加权的欧几里德距离，定义如下：

聚类算法有很多种，可以划分为几种类别：划分方法，层次方法，基于密度的方法，基于网格的方法和基于模型的方法，同时聚类也可以用于异常值(outlier)检测技术。
7.4.1 K-means算法
最常用的聚类算法是K-means算法，它是一种划分方法。给定一个包含n个数据的数据集，和产生的聚类的个数， K-means算法将个数据划分成k个子集，每个子集代表一个聚类，同一个聚类中的数据之间距离较近，而不同聚类的数据间距离较远。每个聚类由其中心值来表示，通过计算聚类中所有数据的平均值可以得到它的中心值。
K-means算法描述如下：
算法：K-means
输入：聚类的个数k和一个包含n个数据的数据集
输出：k个聚类
方法：任意选取k个数据作为初始的聚类中心
Do
将每个数据划分到一个聚类，依据数据与聚类中心值的距离最近为标准
更新聚类的中心值，即重新计算每个聚类中所有数据平均值
While划分没有发生变化时输出K个聚类
K-means算法在入侵检测技术中的应用原理
基于无监督聚类的入侵检测技术算法建立在两个假设上.：第一个假设是正常行为的数目远远大于入侵行为的数目。第二个假设是入侵的行为和正常的行为差异非常大。该方法的基本思想就是由于入侵行为是和正常行为不同的并且数目相对很少,因此它们在能够检测技术到的数据中呈现出比较特殊的特性。比如可以首先假定输出10个聚类，从数据集中任选10个数据作为这个聚类初始的中心值，然后将每10个数据划分到其中的一个聚类，方法是判断该数据到哪一个聚类的中心值的距离最近，则将该数据划分到这个聚类。划分完成后，重新计算每个聚类的中心值，方法是计算聚类中所有数据的平均值，把这个平均值作为新的聚类的中心值。接下来重新将每个数据划分到其中的一个聚类，如此反复地进行若干次划分和计算中心值的操作，直到数据的划分没有变化。
算法的优点和缺陷
算法的优点是不需要用人工的或其他的方法来对训练集进行分类 ,并且能够比较有效地检测技术未知入侵攻击。而且算法有良好扩展性，被广泛应用于各领域。
但是像K-means算法经常在聚类开始前就获得了全部数据（即离线的），但时常会有些对“在线聚类”的需求。比如存储空间不够记录所有的数据模式，或者系统对时间要求很高，以至于数据还没有全部出现算法就必须开始。
怎么解决这个问题呢？
大家都知道，算法设计要求中有一点就是效率与低存储量需求，所以衡量算法的复杂度有时间复杂度和空间复杂度两个方面。K-means算法的效率较高，但是得付出较大的存储空间。下面介绍一下迭代最优化算法。
7.4.2迭代最优化算法
输入：聚类的个数k，一个包含n个数据的数据集，每个聚类的均值mi
输出：k个聚类
方法：随机选取一个样本Xi （存在于某个均值为mi的聚类中）
While Xi离mj 的距离比离 mi 更近
Do
将Xi转移到均值为mj的这个聚类中
更新这个聚类的中心值，即重新计算这个聚类中所有数据平均值
While划分没有发生变化时输出K个聚类
算法分析：
对这个算法稍作考虑就会发现它其实是K-means算法的一种变形。K-means 算法在每次更新前都要对所有的数据点重新分类，而这个方法每次对一个样本重新分类后就进行更新。
但是这种算法更易陷入局部极小值，对全局入侵检测技术效率有影响。然而它毕竟是一种逐步求精的算法，对存储空间要求不高，而且很容易作些改动使得它能处理顺序数据流或需要在线聚类的场合，这也正符合入侵检测技术的环境。当然，在其他在许多领域也有广泛的应用。
7.4.3我的构想
虽然说衡量一个算法的效率有时间和空间两方面的要求，而且时空不可能同时达到最优，但是可以适当地将时空两方面兼顾一下，使对聚类分析时的存储空间要求不太高，同时分析过程也不太长。
在这里我再通过一个形象的比喻生动地描述一下K-means算法和迭代最优化算法，这样通俗易懂，大家可以更清晰地理解这两个算法的优缺点，同时也描述一下我的构想，让大家了解一下我所设想的算法的可行性和优越性。

[ft=,4,][ft=,,Tim

如果本文没有解决您的问题，请进老妖怪开发者社区提问