医药学论文：朴素贝叶斯分类在入侵检测中的应用

1 前言

　　在入侵检测系统中，为了提高系统的性能，包括降低误报率和漏报率，缩短反应时间等，学者们引入了许多方法，如专家系统、神经网络、遗传算法和数据挖掘中的聚类，分类等各种算法。例如：Cooper & Herkovits提出的一种基于贪心算法的贝叶斯信念网络，而Provan & Singh Provan，G.M & Singh M和其他学者报告了这种方法的优点。贝叶斯网络说明联合条件概率分布，为机器学习提供一种因果关系的图形，能有效的处理某些问题，如诊断：贝叶斯网络能正确的处理不确定和有噪声的问题，这类问题在任何检测任务中都很重要。

　　然而，在分类算法的比较研究发现，一种称作朴素贝叶斯分类的简单贝叶斯算法给人印象更为深刻。尽管朴素贝叶斯的分类器有个很简单的假定，但从现实数据中的实验反复地表明它可以与决定树和神经网络分类算法相媲美[1]。

　　在本文中，我们研究朴素贝叶斯分类算法，用来检测入侵审计数据，旨在开发一种更有效的，检验更加准确的算法。

　　2 贝叶斯分类器

　　贝叶斯分类是统计学分类方法。它们可以预测类成员关系的可能性，如给定样本属于一个特定类的概率。

　　朴素贝叶斯分类[2]假定了一个属性值对给定类的影响独立于其它属性的值，这一假定称作类条件独立。

　　设定数据样本用一个 n 维特征向量X={x1，x2，，xn}表示，分别描述对n 个属性A1，A2，，An样本的 n 个度量。假定有m个类 C1，C2，，Cm 。给定一个未知的数据样本 X（即没有类标号），朴素贝叶斯分类分类法将预测 X 属于具有最高后验概率（条件 X 下）的类，当且仅当P(Ci | X)> P(Cj | X)，1≤j≤m，j≠i 这样，最大化P(Ci | X)。其中P(Ci | X)最大类Ci 称为最大后验假定，其原理为贝叶斯定理：

　　公式(1)

　　由于P(X) 对于所有类为常数，只需要P(X | Ci)P(Ci)最大即可。并据此对P(Ci| X)最大化。否则，最大化P(X | Ci)P(Ci)。如果给定具有许多属性的数据集，计算P(X | Ci)P(Ci)的开销可能非常大。为降低计算P(X| Ci )的开销，可以做类条件独立的朴素假定。给定样本的类标号，假定属性值相互条件独立，即在属性间，不存在依赖关系，这样，

　　公式(2)

　　概率，可以由训练样本估值：

　　(1) 如果Ak是分类属性，则P(xk|Ci)=sik/si其中sik是Ak上具有值xk的类Ci的训练样本数，而si是Ci中的训练样本数。

　　(2) 如果Ak是连续值属性，则通常假定该属性服从高斯分布。因而

　　公式(3)

　　其中，给定类Ci的训练样本属性Ak的值， 是属性Ak的高斯密度函数，而 分别为平均值和标准差。

　　朴素贝叶斯分类算法(以下称为NBC)具有最小的出错率。然而，实践中并非如此，这是由于对其应用假定（如类条件独立性）的不确定性，以及缺乏可用的概率数据造成的。主要表现为：

　　①不同的检测属性之间可能存在依赖关系，如protocol_type，src_bytes和dst_bytes三种属性之间总会存在一定的联系；

　　②当连续值属性分布是多态时，可能产生很明显的问题。在这种情况下，考虑分类问题涉及更加广泛，或者我们在做数据分析时应该考虑另一种数据分析。

　　后一种方法我们将在以下章节详细讨论。

　　3 朴素贝叶斯的改进：核密度估计

　　核密度估计是一种普便的朴素贝叶斯方法，主要解决由每个连续值属性设为高斯分布所产生的问题，正如上一节所提到的。在[3]文中，作者认为连续属性值更多是以核密度估计而不是高斯估计。

　　朴素贝叶斯核密度估计分类算法（以下称K-NBC）十分类似如NBC，除了在计算连续属性的概率 时：NBC是使用高斯密度函数来评估该属性，而K-NBC正如它的名字所说得一样，使用高斯核密度函数来评估属性。它的标准核密度公式为

　　公式(4)

　　其中h=σ 称为核密度的带宽，K=g（x,0,1） ，定义为非负函数。这样公式（4）变形为公式（5）

　　公式(5)

　　在K-NBC中采用高斯核密度为数据分析，这是因为高斯密度有着更理想的曲线特点。图1说明了实际数据的概率分布更接近高斯核密度曲线。

　　图1 两种不同的概率密度对事务中数据的评估，其中黑线代表高斯密度，虚线为核估计密度并有两个不同值的带宽朴素贝叶斯算法在计算μc和σc时，只需要存储观测值xk的和以及他们的平方和，这对一个正态分布来说是已经足够了。而核密度在训练过程中需要存储每一个连续属性的值（在学习过程中，对名词性属性只需要存储它在样本中的频率值，这一点和朴素贝叶斯算法一样）。而为事例分类时，在计算连续值属性的概率 时，朴素贝叶斯算法只需要评估g一次，而核密度估计算法需要对每个c类中属性X每一个观察值进行n次评估，这就增加计算存储空间和时间复杂度，表1中对比了两种方法的时间复杂度和内存需求空间。

　　4 实验研究与结果分析

　　本节的目标是评价我们提出核密度评估分类算法对入侵审计数据分类的效果，主要从整体检测率、检测率和误检率上来分析。

　　表1 在给定n条训练事务和m个检测属性条件下，

　　NBC和K-NBC的算法复杂度

　　朴素贝叶斯 核密度

　　时间 空间 时间 空间

　　具有n条事务的训练数据 O(nm) O(m) O(nm) O(nm)

　　具有q条事务的测试数据 O(qm) O(qnm)

　　4.1 实验建立

　　在实验中，我们使用NBC与K-NBC进行比较。另观察表1两种算法的复杂度，可得知有效的减少检测属性，可以提高他们的运算速度，同时删除不相关的检测属性还有可以提高分类效率，本文将在下一节详细介绍对称不确定方法[4]如何对入侵审计数据的预处理。我们也会在实验中进行对比分析。

　　我们使用WEKA来进行本次实验。采用 KDDCUP99[5]中的数据作为入侵检测分类器的训练样本集和测试样本集，其中每个记录由41个离散或连续的属性(如：持续时间，协议类型等)来描述，并标有其所属的类型(如：正常或具体的攻击类型)。所有数据分类23类，在这里我们把这些类网络行为分为5大类网络行为（Normal、DOS、U2R、R2L、Probe）。

　　在实验中，由于KDDCUP99有500多万条记录，为了处理的方便，我们均匀从kddcup.data.gz 中按照五类网络行为抽取了5万条数据作为训练样本集，并把他们分成5组，每组数据为10000条，其中normal数据占据整组数据中的98.5%，这一点符合真实环境中正常数据远远大于入侵数据的比例。我们首先检测一组数据中只有同类的入侵的情况，共4组数据（DOS中的neptune，Proble中的Satan，U2R中的buffer_ overflow，R2l中的guess_passwd），再检测一组数据中有各种类型入侵数据的情况。待分类器得到良好的训练后，再从KDD99数据中抽取5组数据作为测试样本，分别代表Noraml-DOS，Normal-Probe，Normal-U2R，Normal-R2L，最后一组为混后型数据，每组数据为1万条。

　　4.2 数据的预处理

　　由于朴素贝叶斯有个假定，即假定所有待测属性对给定类的影响独立于其他属性的值，然而现实中的数据不总是如此。因此，本文引入对称不确定理论来对数据进行预处理，删除数据中不相关的属性。

　　对称不确定理论是基于信息概念论，首先我们先了解一下信息理论念，属性X的熵为：

　　公式(6)

　　给定一个观察变量Y，变量X的熵为:

　　公式(7)

　　P(xi )是变量X所有值的先验概率，P(xi|yi )是给定观察值Y，X的后验概率。这些随着X熵的降低反映在条件Y下，X额外的信息，我们称之为信息增益，

　　公式(8)

　　按照这个方法，如果IG(X|Y)＞IG(X|Y)，那么属性Y比起属性Z来，与属性X相关性更强。