浅析入侵模式挖掘系统结构算法

《浅析入侵模式挖掘系统结构算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浅析入侵模式挖掘系统结构算法　　[摘要]网络日志数据量日益增大。如何从巨大的网络数据中提取有效信息是数据研究人员一直关心的问题。入侵模式挖掘系统（IntrusionDigger）结合了数据挖掘技术与入侵检测技术，旨在通过发现关联规则而对网络数据进行判别。最小支持度小于所有支持度的项集称为频繁项集，简称频集。基于划分改进的Apriori算法明显优越于原来的算法。基于划分改进的Apriori算法为入侵模式挖掘系统的设计提供了重要的理论支持。　　[关键词]入侵模式挖掘系统基于划分改进的Apriori算法数据挖掘　　[中图分类号]G642[文献标识码]

2、A[文章编号]2095-3437（2013）15-0036-02　　一、系统的实现原理　　众所周知，网络日志数据量日益增大，从巨大的网络数据中提取有用信息是入侵模式挖掘系统所要完成的工作。在这里我们使用数据挖掘的关联分析方法，即产生频繁项集与关联规则。关联规则就是我们得到的有用信息。在得到关联规则后，我们便可以使用关联规则对测试数据进行分析，判断测试数据是正常数据还是非正常数据。对于判断的结果，我们用一个评价体系来评测判断结果的好坏。入侵模式挖掘系统结合了数据挖掘技术与入侵检测技术，旨在通过发现关联规则而对网络数据来进行判别。因此，根据以上分析

3、，入侵模式挖掘系统的总体大致设计图如图1.1所示。　　■　　图1.1入侵模式挖掘系统总体设计图　　图1.1中方框内为数据或文件如原始网络日志数据、测试结果文件等，初步设计有三个大的子系统，分别是模式挖掘系统、测试系统、评价系统。箭头代表数据的流向或者结果的输出，椭圆框内为入侵模式挖掘系统的初步设计的子系统。　　二、系统的设计算法分析　　（一）Apriori算法　　本系统采用关联分析方法中的Apriori算法作为核心算法。目前，该算法是挖掘布尔关联规则频繁项集算法中最有影响力的一种，基于两阶段频集思想的递推算法是其核心。在此，最小支持度小于所有支

4、持度的项集称为频繁项集，简称频集。[1]在分类上该关联规则属于单层、单维和布尔关联规则，该关联规则为了生成所有频集，采用了递推的方法。　　算法思路：第一步，找出所有出现的频繁性至少和预定义的最小支持度一样的频集。第二步，由频集产生必须满足最小可信度和最小支持度的强关联规则。第三步，使用第一步找到的频集产生只包含集合项的所有规则，其中每一条定义为中规则的右部只有一项的规则。第四步，大于用户给定的最小可信度的规则被留下来生成我们需要的规则。　　程序算法如下：　　（1）L1=find_frequent_1_itemset（D）；　　（2）for（k=

5、2；Lk-1≠φ；k++）{　　（3）Ck=apriori_gen（Lk-1）；　　（4）foreacht∈D{　　（5）Ck=subset（Ck，t）；　　（6）Foreachc∈Ctc.count++；}　　（7）Lk={c∈Ck

6、c.count>min_sup}}　　（8）retrurnL=∪Lk　　该算法中首先产生频繁1项集L1，其次产生频繁2项集L2，然后直到有一个频繁r值使得对应项集Lr为空，此时算法终止。Ck中的项集是用来产生频集的候选项集，最终的频集Lk一定是集合Ck的一个子集。在第k次循环中，算法先产生候选项k项集的集合Ck，

7、Ck中的每一个项集属于项集Lk-1的频集来产生的下一个连接集合。Ck中的每个元素都需要在数据库中进行验证，然后才能决定该项是否能够加入频集Lk中。　　Apriori算法的两个严重不足会导致挖掘的效率非常低。一个方面，该算法在每进行一次迭代的时候扫描一次数据库，多次扫描数据库带来巨大I/O开销。另一个方面，该算法在迭代过程中需要在内存中产生、处理和保存数量巨大的候选频集，这也导致算法在深度和广度上的适应性很差。　　（二）基于划分改进的Apriori算法　　为了提高Apriori算法的效率，需要对Apriori算法进行改进。本系统引入了一种基于划分

8、改进的Apriori算法，该算法只需要扫描数据库两次。第一次扫描中，将产生一组潜在的频集，这组项集是最后需要确定的频集的超集，它也可能包含错误的选择，但绝对不可能漏掉正确的选择。第二次扫描中，对这些潜在的频集进一步计算它在整个数据库中的实际支持度，可以最后确定所求得的真正的频集。　　算法思路：第一步，将整个数据库尽可能划分成N个子块。第二步，针对每一个子块单独产生一组潜在的频集。第三步，将上一步所有潜在的频集合并为一个全局的候选频集。第四步，在整个数据库中，计算每个候选频集的实际支持度，从而确定最后有用的频集。　　程序算法如下：　　（1）P=p

9、artion_database（D）　　（2）n=numberofpartitions　　（3）fori=1tonbegin　　（4）read_in_