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

《网络审计系统中apriori算法的应用与研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、网络审计系统中Apriori算法的应用与研究　　【摘要】此文介绍了关联规则的主要内容，结合了网络审计系统中事务数据库的特征，从Apriori算法的基本概念出发，根据网络审计的特点，介绍了一种基于分片的改进的Apriori算法的，并给出证明。最后在改进的策略选择上给出结论。　　【关键词】网络审计；关联规则；Apriori算法　　网络安全审计是网络安全中重要的一环。审计系统一般架设在局域网络出口上，采用串联监控或旁路监控两种形式，对所有流通的封包进行审计挖掘。通过匹配规则库中的特征值来完成报警、拦截、日志等一系列审计工作。当前的网络审计的最大速度瓶颈就是面对海量的审计记录无法快速挖掘出异常行为，而

2、且出现大量误报，影响管理者的判断，严重影响了网络审计系统的性能。　　网络审计中的行为主要表现形式为大量的含有不同特征值的数据，这些数据都有同样的格式，即TCP报文或UDP报文，因此使用数据挖掘技术中的关联规则挖掘来进行发现特征数据就是很有效的方法。关联规则挖掘（DataMining）首先由Rakesh6Apwal等人提出。关联是指两个或两个以上项集的值之间的某中规律性。关联规则挖掘的目的是找出数据库中的隐藏的关联关系。从海量的数据中找出我们需要的知识和规律，这些知识和规律是隐含在数据仓库中具有决策价值的。由于关联规则挖掘技术在数据特征值分析方面有着先天的优势，所以采用关联规则挖掘技术进行网络审

3、计的数据挖掘是目前最好的选择。运用关联规则挖掘用户的行为模式不但能发现相关属性值之间的关联规则，而且通过合并和泛化，可以形成新的有价值的特征。　　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=？?I。X称为关联规则的前

4、项，Y称为关联规则的后项。　　1.2描述关联规则属性的两个参数　　1.2.1支持度（Support）　　1.3关联规则挖掘步骤　　关联规则的挖掘有两个步骤。　　1.3.1发现频繁项集　　通过给定的最小支持度（Smin），找到所有满足“支持度≥Smin”的项目集，满足条件的项集称为频繁项集。　　1.3.2生成关联规则6　　通过给定的最小（Cmin），如果对每个频繁项集进行置信度的计算，然后对比Cmin，计算量将耗费大量的时间，所有利用定理，频繁项集的子集也一定是频繁项集，就可以对每个最大频繁项集进行置信度的计算，大大减少了计算量。　　对于第二个问题实现相对容易，所以，所有优化算法都是集中在第一个

5、问题的研究上，它是关联规则算法的核心问题。　　2Apriori算法的应用与改进　　2.1Apriori算法　　Apriori算法是一种寻找频繁项集的关联规则挖掘算法，通过多次扫面数据库来发现频繁项集。算法第一步采用逐层迭代的方法找出所有频繁项目集，要求频繁项集的支持度大于等于设定的最小支持度；第二步从频繁项集中构造置信度不小于设定的最低阈值。　　2.2算法步骤　　步骤如下：　　（1）设定最小支持度s和最小置信度c。　　（2）Apriori算法使用候选项集。首先产生出候选的项的集合。即候选项集。若候选项集的支持度大于或等于最小支持度，则该候选项集为频繁项集。　　（3）在Apriori算法的过程中

6、，首先从数据库读入所有的事务，每个项都被看作候选1_项集，得出各项的支持度，再使用频繁1_项集合集来产生候选2_项集集合，因为先验原理保证所有非频繁的1_项集的超集都是非频繁的。　　（4）再扫描数据库，得出候选2_项集集合，再找出频繁2_项集，并利用这些频繁2_项集集合来产生候选3_项集。6　　（5）重复扫描数据库，与最小支持度比较，产生更高层次的频繁项集，再从该集合里产生下一级候选项集，直到不再产生新的候选项集为止。　　2.3基于分片的算法改进　　首先，把D中的事务划分成n个非重叠的分片，如果D中事务的最小相对支持度阈值为min_sup，则每个分片的最小支持度计数为min_supX该分片的事

7、务数。对于每个分片，扫描数据库，找出所有的局部频繁项集[3]。局部频集可能是也可能不是整个数据库D的频集。然而，D的任何频集必须作为局部频集至少出现在一个分片中，证明如下：　　证明：反证法。假设频集在D的任何一个分片都不频繁。令F为任意一个频集，D为事务数据库集合，C为D中的事务总数，A为D中包含F的事务总数，min_sup为最小支持度。因为F是一个频集，所以A=CXmin_sup。将D分成n个不