基于大步回退剪枝最大频繁模式挖掘的入侵检测系统研究

作     者：尹敬涛 

作者单位：燕山大学 

学位级别：硕士

导师姓名：吕梦雅

授予年度：2006年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 0839[工学-网络空间安全] 08[工学] 

主      题：入侵检测 频繁模式 最大频繁模式 剪枝 数据挖掘 

摘      要：频繁模式的挖掘是数据挖掘中的一个基础和核心问题,具有广泛的应用领域。由于它是数据挖掘过程中最耗时的部分,挖掘算法的好坏直接影响数据挖掘尤其是关联挖掘的效率和应用范围。因此,最大频繁模式挖掘算法的研究具有重要的理论和应用价值。本文着重从以下几方面进行深入的研究和探讨。 首先,在分析与研究传统剪枝策略的基础上提出了新的剪枝策略——大步回退剪枝策略。与文献中深度优先搜索中逐层回退策略相比,可大幅度削剪搜索空间,达到提高解决问题效率的目的。 其次,在分析了现有最大频繁模式挖掘算法的基础上,针对其不足,提出了一个改进的挖掘最大频繁模式的算法DoMax(Doing Maximal)。DoMax采用了垂直的数据库表示形式,按照自顶向下深度优先的策略对项集空间进行搜索,采用了大步回退剪枝、根部剪枝、频繁扩展和不扩展等多种剪枝优化策略,大幅度削剪了搜索空间。实验和分析表明,在长模式密集的情况下,DoMax的性能优于目前同类算法。 然后,在算法DoMax上提出了一个基于最大频繁模式挖掘入侵检测系统模型MMFIID (Mining Maximal Frequent Itemset for Intrusion Detection)。通过挖掘训练数据中的最大频繁模式建立系统和用户的正常行为模型以及攻击模型,用一个滑动窗口来检测是否有不被正常行为模型覆盖的频繁模式发生,以此达到检测入侵的目的。实验表明,MMFIID对在短时间内频繁发生的攻击类型有较高的检测速度和精度。