网络审计系统中Apriori算法的应用与研究

张继周+李婷

【摘 要】此文介绍了关联规则的主要内容，结合了网络审计系统中事务数据库的特征，从Apriori算法的基本概念出发，根据网络审计的特点，介绍了一种基于分片的改进的Apriori算法的，并给出证明。最后在改进的策略选择上给出结论。

【关键词】网络审计；关联规则；Apriori算法

网络安全审计是网络安全中重要的一环。审计系统一般架设在局域网络出口上，采用串联监控或旁路监控两种形式，对所有流通的封包进行审计挖掘。通过匹配规则库中的特征值来完成报警、拦截、日志等一系列审计工作。当前的网络审计的最大速度瓶颈就是面对海量的审计记录无法快速挖掘出异常行为，而且出现大量误报，影响管理者的判断，严重影响了网络审计系统的性能。

网络审计中的行为主要表现形式为大量的含有不同特征值的数据，这些数据都有同样的格式，即TCP报文或UDP报文，因此使用数据挖掘技术中的关联规则挖掘来进行发现特征数据就是很有效的方法。关联规则挖掘（Data Mining）首先由Rakesh Apwal等人提出。关联是指两个或两个以上项集的值之间的某中规律性。关联规则挖掘的目的是找出数据库中的隐藏的关联关系。从海量的数据中找出我们需要的知识和规律，这些知识和规律是隐含在数据仓库中具有决策价值的。由于关联规则挖掘技术在数据特征值分析方面有着先天的优势，所以采用关联规则挖掘技术进行网络审计的数据挖掘是目前最好的选择。运用关联规则挖掘用户的行为模式不但能发现相关属性值之间的关联规则，而且通过合并和泛化，可以形成新的有价值的特征。

1 关联规则

1.1 关联规则定义

关联规则是Agrawl等人于1993年提出的，关联规则发展至今已经成为数据挖掘中的一个重要研究内容。

设I={i1，i2……im}是一个项目合集，相关事务数据库M={t1，t2 ……tn}，其中每个事务tj表示M的第j个事务，是由I中的若干项目构成的集合，即tj？哿I。事务tj包含X，是指对于I的子集X，有X？哿tj。关联规则的主要表现形式为“X→Y”，其中X？哿I，Y？哿I，并且X∩Y=？覫。X称为关联规则的前项，Y称为关联规则的后项。

1.2 描述关联规则属性的两个参数

1.2.1 支持度（Support）

1.3 关联规则挖掘步骤

关联规则的挖掘有两个步骤。

1.3.1 发现频繁项集

通过给定的最小支持度（Smin），找到所有满足“支持度≥Smin”的项目集，满足条件的项集称为频繁项集。

1.3.2 生成关联规则

通过给定的最小（Cmin），如果对每个频繁项集进行置信度的计算，然后对比Cmin，计算量将耗费大量的时间，所有利用定理，频繁项集的子集也一定是频繁项集，就可以对每个最大频繁项集进行置信度的计算，大大减少了计算量。

对于第二个问题实现相对容易，所以，所有优化算法都是集中在第一个问题的研究上，它是关联规则算法的核心问题。

2 Apriori算法的应用与改进

2.1 Apriori算法

Apriori算法是一种寻找频繁项集的关联规则挖掘算法，通过多次扫面数据库来发现频繁项集。算法第一步采用逐层迭代的方法找出所有频繁项目集，要求频繁项集的支持度大于等于设定的最小支持度；第二步从频繁项集中构造置信度不小于设定的最低阈值。

2.2 算法步骤

步骤如下：

（1）设定最小支持度s和最小置信度c。

（2）Apriori算法使用候选项集。首先产生出候选的项的集合。即候选项集。若候选项集的支持度大于或等于最小支持度，则该候选项集为频繁项集。

（3）在Apriori算法的过程中，首先从数据库读入所有的事务，每个项都被看作候选1_项集，得出各项的支持度，再使用频繁1_项集合集来产生候选2_项集集合，因为先验原理保证所有非频繁的1_项集的超集都是非频繁的。

（4）再扫描数据库，得出候选2_项集集合，再找出频繁2_项集，并利用这些频繁2_项集集合来产生候选3_项集。

（5）重复扫描数据库，与最小支持度比较，产生更高层次的频繁项集，再从该集合里产生下一级候选项集，直到不再产生新的候选项集为止。

2.3 基于分片的算法改进

首先，把D中的事务划分成n个非重叠的分片，如果D中事务的最小相对支持度阈值为min_sup，则每个分片的最小支持度计数为min_supX该分片的事务数。对于每个分片，扫描数据库，找出所有的局部频繁项集[3]。局部频集可能是也可能不是整个数据库D的频集。然而，D的任何频集必须作为局部频集至少出现在一个分片中，证明如下：

证明：反证法。假设频集在D的任何一个分片都不频繁。令F为任意一个频集，D为事务数据库集合，C为D中的事务总数，A为D中包含F的事务总数，min_sup为最小支持度。因为F是一个频集，所以A=CXmin_sup。将D分成n个不重叠的分片：d1，d2，d3，…，dn，令C1，C2，C3，…，Cn为分片d1，d2，d3，…，dn各自对应的事务数，则C=C1+C2+C3+…+Cn。令a1，a2，a3，…，an为分片d1，d2，d3，…，dn中包含F的事务数，则A=a1+a2+a3+…+an。因此A=a1+a2+a3+…+an=（C1+C2+C3+…+Cn）Xmin_sup。因为前面已经假设F在D中任意一个分片d1，d2，d3，…，dn中都不频繁，则a1

因此，所有局部频集都是D的候选项集，来自所有分片的局部频集作为D的全局候选项集。然后，第二次扫描数据库D，评估每个候选的实际支持度，以确定全局频繁项集。它的优化算法步骤为：（1）把数据库划分成一些模块大小相当的块，记为N块；（2）在每一块内产生一组自己的频繁项目集；记为Li；（3）最后合并这些项目集生成一个全局候选的频繁项目集；（4）在数据库内，计算候选项频繁目集的支持度，得到确定的最终频繁项目集。

基于分片的Apriori算法在网络审计这种类型的事务库的挖掘中有着明显的优势，审计事务库的特点就是数据具有特有的类型，每个类型有着特定的特征值，利于分片挖掘，数据分布较为分散，数据之间的关联性不高，采用基于分片的Apriori算法显著提高了挖掘效率，提高算法的可用性。

3 结束语

在实际的应用中，针对不同特点的TCP网络，有着适合的改进策略，这些策略不用做到面面俱到，只要具有一定的针对性就可以。网络拥塞的改进是十分灵活的，方法也很非常多，其原因正是因为不同网络中传输的数据特点不同，从而选择合适的改进策略是关键。

【参考文献】

[1]Jiawei Han，Micheline Kamber.数据挖掘概念与技术[M].2版.范明，孟小锋，译.北京：机械工业出版社，2010.

[2]王丽珍，周丽华，陈红梅，等.数据仓库与数据挖掘原理及应用[M].北京：科学出版社，2005.

[3]王荣福，余丽娜，等.基于划分技术对Apriori算法的改进[J].科技创新导报，2008（12）.

[责任编辑：汤静]