杨光辉，封均康

(1. 华北理工大学理学院，河北 唐山 063210；2. 西苏格兰大学工程与计算机科学学院，英国 佩斯利 PA1 2BE)

1 引言

大量的信息每天以人们想象不到的速度在网络上进行传播[1]，人们每天都被各种各样的网络信息所包围，网络成为人们日常生活中不可缺少的一部分[2]。随之而来的网络信息数据安全问题逐渐成为热点话题。传统的网络安全技术早已经满足不了现今日益进步的网络信息技术，在网络信息中存在大量的不安全信息，因此需要对网络入侵数据进行挖掘[3]。

文献[4]提出在云环境中改进FCM和规则参数优化的网络入侵数据挖掘方法，该方法通过互信息特征选择对样本特征进行降维，再运用改进模糊C均值聚类(IFCM)方法进行对网络入侵数据聚类训练，依据各个数据集群对应关系和样本特征取得初始模糊规则库。然后进行参数调优，获取准确规则库。最后利用规则库连接网络入侵数据进行模糊推理以此实现网络入侵数据挖掘。该方法在网络入侵数据规模较大时检测率较高且趋于平稳但是由于缺少改进Apriori算法所产生的网络入侵数据间的关联规则，所以在小型网络入侵数据样本检测时检测率却偏低，达不到效果。

文献[5]提出基于OSELM分类器和连接数据分析的网络入侵数据挖掘方法，该方法分析入侵数据库中存在的网络数据，并利用特征选择算法构建特征子集，进行多次迭代验证，采用Alpha剖析方法对样本尺寸进行调整，通过调整后的样本特征集对OSELM分类器进行训练，采用OSELM分类器实现网络入侵数据的挖掘，该方法虽然在检测正确率上较为稳定但是因其没有完整的基于关联规则的特征抽取环节，导致其漏报率低下。

为了解决上述方法中存在的问题，提出基于改进Apriori算法的网络入侵数据挖掘方法。

2 基于Apriori算法的关联规则挖掘

2.1 Apriori算法改进

传统Apriori算法[6]进行网络入侵数据挖掘时不但需要对网络入侵数据库进行多次重复扫描而且会产生海量的候选项集，针对这些问题，对Apriori算法进行改进：

通过MapReduce并行技术和矩阵进行结合，加强Apriori算法的并行处理能力，提升算法性能。

具体过程如下：

1)并行化：先将入侵数据库D区分为若干块τ0，τ1，…，τN，再将这若干块数据矩阵化，最后将矩阵化的数据分给对应的项集，进行Map和Reduce计算；

2)矩阵化：扫描事物数据库D，把转化来的信息用矩阵来储存，矩阵中的每一行代表一个事物，每一列代表事务中的一个项目，将数字“0”和“1”来代表该项是否存在于当前事务中，若存在就为“1”，不存在则为“0”；

3)计算支持度：根据项目集中事物和事物中的集进行排序。对于频繁的两个(k-1)项集lx和ly，若它们的前(k-2)项相同，那么它们就可以连接生成一个候选k项集Xk，若Xk的前(k-2)项来自于两者前(k-2)项，那么会产生两项候选集IX[k-1]与Iy[k-1]。通过IX[k-1]与Iy[k-1]的逻辑计算获取矩阵中频繁的两个(k-1)项集lx和ly的支持度。矩阵化直接缩减了对数据库的扫描次数，修改后对数据库只需进行两次扫描，就可以迅速获得频繁项目集及关联规则[7]。

2.2 挖掘准确性

通过改进后的Apriori算法挖掘数据可以使挖掘得到的规则更具准确性[8]，利用对目标项的预先设置来实现数据挖掘过程中所包含于候选项里的所有目标项。该方法不仅满足了用户需求，还缩减了频繁项目集的规模、节省了数据挖掘时间、提高了效率。

设挖掘目标项为NT，挖掘过程如下：

1)获取一项频繁项目集集合L1，如果L1当中包含NT两项，继续，若不包含，结束；

2)计算NT候选项目集的支持度，小于最小支持度停止挖掘，若大于或等于就继续；

3)连接目标项与频繁项目集L1中不属于N和T的项集，获取新的候选集A3，这时A3中的所有项目集都是NT*式，以此获得支持度。选取出大于最小支持度的频繁项目集L3，这时L3的每个项目集都包含了目标项NT，此后连接频繁项目集L3的候选项集都会包含NT项，最后获取的挖掘规则也都包含有NT项。利用此方法通过修改后的Apriori算法对数据进行挖掘会更大程度上的提高挖掘的准确性。

采用改进后Apriori算法挖掘关联规则的具体过程如下：

1)扫描数据库获取频繁项目集L1进行并行化与矩阵化处理。通过矩阵化分辨网络入侵数据是否处于当前目标项，以此来分析是否需要删减数据或划分给相应项目集；

2)连接频繁项目集L1与目标项中所有不属于目标项的数据，获得的项集L(t+1)中每个项集都包含了目标项，且t为目标项数量，以此实现算法目的；

3)通过改进后Apriori算法进行频繁项目集数据挖掘工作，运用项目集的逻辑运算获取目标项的局部支持度。通过Reduce运算，取得整合后各个项集、候选集的局部支持度，最后获取全局的频繁项目集。

改进后的Apriori算法只需要对网络入侵数据库进行两次扫描，第一次扫描生成频繁项目集，第二次扫描将其它数据转化为矩阵进行逻辑运算生成关联规则。对比传统的Apriori算法缩减了对于数据库的扫描次数，并在候选项集的处理中运用MapReduce对候选项集进行剪枝处理，连接目标项L1与目标项以外的项A3，使频繁项目集的每项都包含目标项，从而使改进后的Apriori算法更具目的性。很大程度上减少了候选项集，加快了对数据的挖掘速度。

3 抽取特征

根据挖掘的关联规则，采用KPCA方法提取网络数据的特征。

假设x1，x2，…，xa为训练数据，用{x1}表示输入空间。设相应的映射为Φ，将映射Φ与核函数相结合来实现特征的高维空间映射F，使网络入侵数据能满足特征空间中所需要的中心化条件。

设当前有M个网络入侵数据，其中单独的每一个数据具有N个特征(不包括类别特征)，根据KPCA基本原理，对M个入侵数据进行特征提取，具体过程如下：

1)将网络入侵数据中获取的N个特征，特征中存在的M个样本相结合，得到一个(M×N)维数据矩阵。

(1)

式中，α代表的是网络入侵数据；

2)对得到的矩阵进行计算，获取矩阵中的函数参数与高斯径向基，再由下式计算矩阵K

Kμν：=(Φ(xμ)·Φ(xν))

(2)

式中，ν=1，2，…，m，μ=1，Φ为对应的映射；

3)通过下式修正核矩阵得到KL：

(3)

4)通过修正的矩阵对KL的特征向量υ0，…，υM以及所属矩阵的特征值λ0，…，λM进行测试计算。

5)对特征值λ0，…，λM进行降序处理，相对应的特征向量υ0，…，υM进行修改。

6)利用Schmidt正交化处理特征向量，获取β1，…，βm。

7)依据特征向量计算得出的累计贡献率B1，…，BM根据指定的信息提取率P，若B1≥P且B1-t

8)对改正过的核矩阵KL进行计算，获得特征向量上的投影Y=KL.β，且β=(β1，…，βl)。

在函数替换原则的基础上对网络数据进行KPCA降维处理，获得网络数据的特征β=(β1，…，βl)，函数替换原则通过下式进行描述。

(4)

式中，νk为特征向量的空间投影，x为输入空间。

4 数据挖掘

根据网络入侵数据特征抽取，运用贝叶斯数据分类器对网络入侵数据进行挖掘，如图1所示。

P=(A/B)表示在已知事件B发生的前提下，事件A可能发生的概率，求解为下式

(5)

然而在朴素贝叶斯分类中，更注重P=(A|B)，所以通过条件概率公式变形，可以得到下式

(6)

贝叶斯数据分类用一个N维的属性向量样本Χ={x1，x2，…，xN}来表示每个入侵数据，详细说明了贝叶斯分类赋予了每个网络入侵数据的属性值a1，a2，…，an及测量每个入侵数据被赋予的n个属性的测量值。分类集合为：C={c0，c1，c2，…，cM}。

利用贝叶斯数据分类器分辨网络入侵数据中的单一数据是否属于Ci，当其属于且仅满足于条件

P(Cι|X)>P(Cj|X)

(7)

如此，最大后验假定P(Ci|X)的最大值为Ci。根据取得的式(6)，可知下式

(8)

其中P(Ci|X)是指特定的X={x1，x2，…，xN}状态下，分类集Ci有可能会出现的概率，而P(Ci)则是Ci选定状态下将要发生的概率。

因为分类集Ci在P(X)的状态下都是常量，所以预设的P(X)取值在先验概率未能得到准确值的情况下都是相等的常量，即表示为P(Ci)=P(C2)=…=P(CM)。因此分类是只需求得P(X|Ci)最大项集就能得到P(Ci)的发生概率的最大值，最后完成预定的数据分类。

因为需要在条件、类别所给定的属性极多的情况下对P(X|Ci)求解，计算要求多且数量巨大，所以在贝叶斯数据分类集X相互比较独立的各种条件属性下对其进行简便算法，过程中依赖关系不属于各个条件属性内，过程如下式

=P(X1|Ci)×P(X2|Ci)×…×P(Xn|Ci)

(9)

若a1是分类属性，则P(X1|C1)=S1j/S1，在这之中a1是属于S1j的属性，Ci是包含于值X1中的网络入侵数据的常量，分类集Ci所包括的Si是目标项目集中全部网络入侵数据量。

若a1有连续值的属性，则a1属性服从于一般假设，采用高斯分布，存在下式

(10)

其中，Ci是网络入侵数据属性Aj的值，g(xj，μcl，σcl)是属性Aj的高斯密度函数，其中μcl为所属函数平均值σcl为所属函数标准差。

贝叶斯数据分类器的最后目的是将选定后的网络入侵数据划分给相应项目集(项目集为后验概率最大项目集)进行计算，过程如下式：

(11)

将提取到的特征输入分类模型中，实现网络入侵数据的挖掘。

朴素贝叶斯分类器的工作流程如图2所示：

图2 贝叶斯分类器工作流程图

5 实验结果与分析

为了验证方法的整体有效性，需要对此方法进行测试。实验环境为：采用的CPU为Pentium(R)Dual-Core、操作系统为WindowsXP、120G硬盘、内存为2G。实验数据库是Access2000。

分别采用基于改进Apriori算法的网络入侵数据挖掘方法、文献[4]方法、文献[5]方法进行测试。

1)在相同量的数据下对比不同方法挖掘网络入侵数据所需的时间，测试结果如图3所示。

图3 挖掘时间测试结果

分析图4可知，所提方法对比文献[4]方法与文献[5]方法来看，所提方法明显在挖掘数据时间上要比文献[4]方法与文献[5]方法的效率更高，因为所提方法对传统的Apriori算法进行了矩阵化改进，使原来要进行的多次对网络入侵数据库的扫描现在只需要进行两次扫描，就可以获得数据之间存在的关联规则，在关联规则的基础上实现网络入侵数据的挖掘，减少了挖掘数据所需的时间，提高了挖掘效率。

2)通过对比网络入侵数据的检测率，进一步对所提方法、文献[4]方法和文献[5]方法进行测试，测试结果分别如图4所示。

图4 挖掘检测率测试结果

分析图4可知，所提方法的检测率对比文献[4]方法和文献[5]方法来看，所提方法在网络入侵数据挖掘的检测率要高于文献方法，且多次检测下来所提方法的检测率随着检测次数的增加效率下降较为平稳，主要因为所提方法利用Apriori算法在短时间内迅速挖掘了关联规则，并在挖掘过程中运用MapReduce对候选项集进行剪枝处理，通过剪枝处理，提高了关联规则的精准度，将高精准度的关联规则应用在网络入侵数据的特征提取中，提高了特征提取的准确率，进而提高了方法的检测率。

3)在测试过网络入侵数据挖掘的检测时间和检测率后，通过对所提方法、文献[4]方法、文献[5]方法进行误报率测试，进一步检测基于改进Apriori算法的网络入侵数据挖掘方法的可行性，测试结果如图5所示。

图5 挖掘误报率测试结果

分析图5可知，测试过程中所提方法与文献[4]方法、文献[5]方法在多次检测下误报率都相对增大但是所提方法比文献[4]方法和文献[5]方法稳定且误报率低。基于改进的Apriori算法在抽取特征过程中修改了核矩阵获取了新的特征向量，让特征抽取更具针对性以此降低网络入侵数据挖掘过程中的误报率。

6 结束语

传统的Apriori算法在进行网络入侵数据挖掘时挖掘时间长，检测效率低，误报效率高。提出基于改进Apriori算法的网络入侵挖掘方法，该方法基于改进的Apriori算法对数据进行并行化矩阵化生成关联规则，利用关联规则对网络入侵数据进行特征抽取，最后将抽取的特征放入贝叶斯分类器中完成数据分类。实验结果表明基于改进的Apriori算法的网络入侵数据挖掘，解决了挖掘过程中挖掘时间长，检测效率低、误报效率高的问题。