基于改进Apriori算法的入侵检测数据挖掘模型研究
孙文静1,傅涛2
【摘 要】 将数据挖掘技术应用到入侵检测系统中,成为入侵检测研究的重要方向。本文对Apriori算法进行改进,以此构建入侵检测数据挖掘模型,运用该模型作入侵检测。实验表明,对以知攻击,采用误用检测和异常检测混合策略,其平均检测准确率达到80%以上,不失为一种效果良好的的入侵检测技术。 【期刊名称】软件
【年(卷),期】2014(035)008 【总页数】6
【关键词】 改进Apriori算法;数据挖掘模型;入侵检测
0 引言
Apriori算法是数据挖掘中关联规则产生的一种经典的Apriori算法,其过程是首先通过检索的方式找出数据库中所有的频繁项集,然后根据频繁项集产生所期望的强关联规则[1]。
实践表明,Apriori算法在处理较大数据时,需要大量的I/O操作和CPU的开销,使得运算效率出现瓶颈,这制约了其在数据挖掘中的应用性。
本文对Apriori算法进行改进,并将其应用到入侵检测数据挖掘模型中。实验结果显示,具有良好的有效性。
1 Apriori算法
Apriori(Repeated Incremental Pruning to Produce Error Reduction)算法是一种经典的关联规则算法:第一步通过检索的方式找出数据库中所有的频繁项集,第二步根据频繁项集产生所期望的强关联规则。其寻找频繁项集的步骤
为:
选取长度K=1,对数据库扫描,找到所有的K=1频繁项集;
以上一趟产生的频繁项集为基础,步长增加,对新的项集再次计算,生成真正的频繁项集;
重复(2)的过程,直到无法找到新的项集,算法终止。
Apriori算法是一个频繁项集的子集,也必定是频繁项集。根据这一性质,可先生成尽可能小的项集,如果有频繁项集不符合性质,则立即删除[1]。其算法如下:
输入:数据集D,最小支持度阈值min_sup。 输出:频繁数据集L,即入侵规则。
2 改进的Apriori算法
由(K-1)-频繁项集生成K-频繁项集时,当(K-1)-频繁项集中项集数目巨大,进行连接操作时效率很低。巨大数量的候补项目集,对它进行计算出现次数的统计时的处理开销非常大,导致了算法的效率低下。
目前普遍采用的是将水平格式的数据转换成垂直格式。事务库中的事务由ID-项构成,即每个ID对应一条记录,所包含的项成水平排列。Apriori算法处理的是这种水平格式的数据。所谓垂直格式数据是指项-ID形式,列出每个项所包含的事务ID,呈垂直形式。改进的算法就是处理这种格式的数据。
首先,我们通过一次扫描数据库D,在求频繁1项集的同时,把数据由水平格式转化为垂直格式,即记录下每个项集在事物数据库中出现时的该条数据在数据库D中的ID号,求项集的支持度计数就可以简单的转化为求项集的ID集的长度。从k等于2开始,可以根据Apriori产生候选频繁项集的性质,直接由
频繁k项集中符合Apriori性质中相交条件的项集进行Apriroi连接运算,然后根据这两项后面所携带的ID集的完整信息,直接进行集合的交运算,求出频繁k+l项集的ID集。如果该ID集的长度大于最小支持度,则该记录为频繁项集。重复该过程,每次k值增1,直到不能再找到频繁项集或候选项集。 具体改进算法描述如下:
输入:事物数据库D;最小支持度为min_sup 输出:D中的所有频繁项集。
该程序里生成频繁-项集的函数genAprioril与传统的Apriori算法生成频繁-项集的函数不同,它在生成项集的同时,记录包含该项集的TID集,该函数具体描述如下:
输入:事物数据库D;最小支持度min_sup 输出:所有的频繁-项集。
输入:频繁k-1项集。最小支持度min_sup 输出:所有的频繁k项集。
本算法与传统 Apriori算法相比,不同在于将数据由水平格式改成垂直模式,只需要扫描一次数据库。项集的支持度计数简单地是项集的ID集的长度。从k=1开始,可以根据Apriori性质,使用频繁k-项集来构造候选((k+1 )-项集。通过取频繁k-项集的ID集的交计算对应的((k+I)-项集的ID集。重复该过程,每次k增值1,直到不能在找到频繁项集或候选项集。
除了在产生候选((k+1)-项集时利用Apriori质之外,这种方法的另一优点是不需要扫描数据库来确定((k+1)-项集(对于k>1)的支持度。这是因为每个k-项集的ID集携带了计算支持度的完整信息。
基于改进Apriori算法的入侵检测数据挖掘模型研究
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)