基于改进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算法的入侵检测数据挖掘模型研究
