【作者】 武志峰；

【导师】 吉根林；

【作者基本信息】 南京师范大学 ， 计算数学， 2005， 硕士

【摘要】 粗糙集理论是一种处理不精确、不相容和不完全数据的新型数学工具。本文介绍了粗糙集理论的相关概念,研究基于粗糙集理论的属性约简和值约简算法及其在入侵检测中的应用,实现了一个基于粗糙集的网络安全规则挖掘实验平台。 数据约简是粗糙集理论中一个非常重要的研究课题。论文在研究已有数据约简算法的基础上,提出了利用扩展决策矩阵计算属性最佳约简的完备的EDMAR算法。与传统基于区分矩阵的约简算法相比,该算法在时间和空间开销上具有一定优势。为了从不同的角度对数据进行浓缩和简化,为用户提供更多的信息,论文提出了基于小生境遗传算法的属性约简算法。该算法可以同时求解出信息表达系统中存在的不同约简,从而为特征提取、决策支持和数据挖掘等提供更多的信息。 求取决策表的最小值约简已被证明是一个NP难问题,因此很难通过枚举法求出问题的最小值约简。论文研究了一般的值约简算法和启发式值约简算法,并提出了一种新的值约简算法(EDMVR算法)。该算法可以有效地简化最终得到的决策规则。 最后,以入侵检测系统为应用背景,实现了一个基于粗糙集方法的网络安全规则挖掘原型系统,并通过实验说明了该原型系统的可用性。更多还原

【Abstract】 Rough Set theory is a new method for dealing with vague, imprecise, incomplete and uncertain data. This paper introduces the basic concepts in rough set theory, studies attribute reduction and attribute value reduction based on the rough set theory, and applies rough set theory to the field of intrusion detection, and designs a prototype system that is used to mine the security rules based on the rough set theory.Data reduction is one of important research issue in rough set theory. Motivated by the former algorithms, in this paper, a novel algorithm based on extended decision matrices for attribute reduction (EDMAR) is proposed. Its completeness is proved. Compared with algorithms based on discernibility matrix, EDMAR is much less both space complexity and time complexity. In order to providing more information for user, this paper proposes a new algorithm for knowledge reduction based on the niche genetic algorithm. Several different reduction subsets of attribute can be gotten with the algorithm. The algorithm can solve some problems that heuristic algorithm can’t do. It can find the different reductions of attribute in the knowledge system. It can provide more information for feature extraction, decision support and data mining.It is to be proved that value reduction is a NP hard problem. So it is too difficult to get the mini value reduction by enumeration. In this paper, we study the general algorithm of value reduction and the heuristic algorithm of value reduction. Furthermore, the paper presents a new algorithm (EDMVR) for value reduction based on decision matrices. And much more concise decision rules can be got with this method.On the basis of the research of rough set theory and the special demand of Intrusion Detection System, a prototype system is implemented for mining security rules from system log audit information within the framework of rough set theory. The usability of the prototype system is shown by the experiment using intrusion data set of KDD CUP 1999.更多还原