（计算机软件与理论专业论文）基于粗糙集和神经网络的数据分类技术研究.pdf

大连理工大学硕士学位论文 摘要 随着信息技术和数据库技术的飞速发展，人们可以非常容易地获取和存储海量数 据，然而要从海量数据中提取出有用信息却很困难。数据分类作为一种重要的数据分析 技术，可以用于提取描述重要数据类的模型和预测未来的数据趋势，帮助人们摆脱“数 据丰富，知识贫乏”的困境。入侵检测和文本分类都属于数据分类的范畴，入侵检测是 根据网络数据或主机数据的特征来判别该数据代表的行为属于哪种类型，而文本分类是 根据文档特征识别出其所属的文档类别。 粗糙集理论是一种处理不精确、不完整和不确定性问题的数学工具，通过属性约简 能有效地消除冗余信息，抽取分类规则；而神经网络也由于具有分类精度高，鲁棒性强 等显著优点。因此，近年来它们都被广泛逾应用于数据分类。但是，面对大规模的高维 数据分类问题如入侵检测和文本分类等，基于粗糙集的分类容错性差、泛化能力弱；而 神经网络作为分类器存在网络结构复杂、训练时间过长等缺陷。如何将粗糙集和神经网 络有机地结合起来，并针对入侵检测和文本分类各自的领域特点进行有效地运用是本文 的研究内容。 针对入侵检测数据存在维数大、冗余度高及噪声数据多等缺陷，给出了一种基于粗 糙集和神经网络的层次入侵检测模型。该模型用租糙集对数据进行预处理以降低维度， 以多个神经网络构成的层次分类器克服单个神经网络分类器的“稳定性可塑性”二难 问题。针对文本分类中的两个关键技术权值计算和特征提取，给出在文本预处理阶 段基于特征词类别分布差异进行特征过滤，并引入类别文档频数改进t f i d f 公式，给出 了一种基于可变精度粗糙理论的特征选择方法，进一步选择对分类贡献度大的特征，并 用s o l 实现；并采用r b f 网络作为文本分类器。实验结果表明了粗糙集和神经网络的 有机结合能很好地应用于数据分类。 关键词：粗棱集；神经网络；入侵检测；文本分类 大连理工大学硕士学位论文 r e s e a r c ho nd a t ac l a s s i f i c a t i o nb a s e do nr o u g hs e ta n dn e u r a l n e t w o r k a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n i q u e sa n dd a t a b a s et e c h n o l o g y p e o p l e c a ne a s i l ya c c e s sa n ds t o r em a s s i v ed a t a h o w e v e r , j ti sd i f f i c u l tt oe x t r a c tv e r yv a l u a b l e i n f o r m a t i o nf r o ml a r g ea m o u n to fd a t a a sa ni m p o r t a n td a t aa n a l y s i st e c h n o l o g y ，d a t a c l a s s i f i c a t i o nc a nb eu s e dt oe x t r a c tm o d e l st h a td e s c r i b es i g n i f i c a n td a t at y p e sa n dp r e d i c t t h et r e n do ff u t u r ed a t a , h e l p i n gp e o p l eg e tr i do ft h ep r e d i c a m e n to f “d a t ar i c hb u t i n f o r m a t i o np o o r i n t r u s i o nd e t e c t i o na n dt e x tc l a s s i f i c a t i o ne s s e n t i a l l yb e l o n gt od a t a c l a s s i f i c a t i o n i n t r u s i o nd e t e c t i o ni st od e t e r m i n ew h i c ht y p et h eb e h a v i o rb e l o n g st o a c c o r d i n gi o t h ec h a r a c t e r i s t i c so fh o s to rn e t w o r kd a t a ，w h i l et e x tc l a s s i f i c a t i o ni s c l a s s i f y i n gd o c u m e n t sa c c o r d i n gt ot h e i rf e a t u r e s r o u 【g hs e tt h e o r yi sam a t h e m a t i c a lt o o lw h i c hc a nw e l lp r o c e s si m p r e c i s e ，i n c o m p l e t e a n du n c e r t a i nd a t a i tc a ne f f e c t i v e l ye l i m i n a t er e d u n d a n ti n f o r m a t i o nt h r o u g ha t t r i b u t e s r e d u c t i o na n de x t r a c te l a s s i f i c a t i o nr u l e s n e u r a ln e t w o r ka sc l a s s i f i e rj so fh i g ha c c u r a c y a n dr o b u s t n e s s t h e r e f o r e t h e yh a v eb e e nw i d e l yu s e di nd a t ac l a s s i f i c a t i o ni nr e c e n ty e a r s h o w e v e r , c l a s s i f i c a t i o ns u c ha si n t r u s i o nd e t e e t i o na n dt e x te l a s s i f i c a t i o nc a n n o tb ec a p a b l e o ft h em a s s i v ea n dh i g h d i m e n s i o n a ld a t a t h ec l a s s i f i c a t i o nm e t h o d sb a s e do nr o u g hs e t t h e o r yh a v ep o o rf a u l t t o l e r a n c ea n dw e a kg e n e r a l i z a t i o na b i l i t yw h i l en e u r a ln e t w o r k c l a s s i f i e r sh a ss o m ed e f e c t ss u c ha sc o m p l e xn e t w o r ks t r u c t u r e s ，t o ol o n gt r a i n i n gt i m ea n d s oo n h o wt oc o m b i n er o u i 曲s e ta n dn e u r a ln e t w o r ke f f e c t i v e l yf o ri n t r u s i o nd e t e c t i o na n d t e x tc l a s s i f i c a t i o ni st h em a i nr e s e a r c hc o n t e n to ft h i sp a p e r a i m i n ga tt h ep r o b l e m st h a ti n t r u s i o nd e t e c t i o nd a t ai sh i g hd i m e n s i o n a l , r e d u n d a n ta n d n o i s y an o v e lh i e r a r c h i c a ii n t r u s i o nd e t e c t i o nm o d e ib a s e do nr o u g hs e ta n dn e u r a ln e t w o r k i sp r o p o s e d t h em o d e lu t i l i z e sr o b 吐s e ti np r e t r e a t m e n tt or e d u c ed a t aa n dc o n s t r u c t sa h i e r a r c h i c a lc l a s s i f i e rw i t hm a n yn e u r a ln e t w o r k st oe x t r i c a t et h ed i l e m m ab e t w e e ns t a b i l i t y a n dp l a s t i c i t y t w ok e yt e c h n o l o g i e so ft e x tc l a s s i f i c a t i o na r ed i s c u s s e d ：w e i g h tc a l c u l a t i o n a n df e a t u r ee x t r a c t i o n f e a t u r ef i l t e r i n gb a s e do nd i s t r i b u t i o n d i s c r e p a n c yo fc l a s s c h a r a c t e r - w o r d si su s e df o rt e x tp r e p r o c e s s i n g ，n ef r e q u e n c yo fd o c u m e n t s b e l o n gt h es a m e c l a s si si n t r o d u c e di n t ot om o d i f yt h ef o r m u l at f l d f i no r d e rt of u r t h e rs e l e c tf e a t u r e s w h i c hc o n t r i b u t em u c ht oc l a s s i f i c a t i o n v p r s o r i e n t e df e a t u r es e l e c t i o ni sp u tf o r t ha n d r e a l i z e db ys o l ：a n dr b fn e u r a ln e t w o r ka st e x te l a s s i f i e r e x p e r i m e n t a lr e s u l t ss h o wt h a t 基于粗糙集和神经网络的数据分类技术研究 t h eo r g a n i cc o m b i n a t i o nb e t w e e nr o u g hs e ta n dn e u r a ln e t w o r kc a l lb ea p p l i e di nd a t a c l a s s i f i c a t i o ne f f e c t i v e l y k e yw o r d s ：r o u g hs e t ；n e u r a ln e t w o r k ；i n t r u s i o nd e t e c t i o n ；t e x tc l a s s i f i c a t i o n i v ， 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：骝璺李 日期：2 丝：! 二z 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名；猛必 翩躲叁业 卫够4 月4 日 大连理工大学硕士学位论文 1绪论 本章首先阐明了论文的研究意义、对数据分类的概念和相关技术进行了简要地介 绍；最后，简要地介绍了论文的研究内容和文章的组织结构。 1 1 研究意义 2 0 世纪9 0 年代以来，随着信息技术和数据库技术的迅猛发展，人们可以非常方便 地获取和存储大量的数据。面对海量的数据，传统的数据分析土具( 如管理信息系统) 只 能进行一些表层的处理( 如查询、统计等) ，而不能获得数据之问的内在关系和隐含的信 息。为了摆脱“数据丰富，知识贫乏”的困境，人们迫切需要一种能够智能地自动地把 数据转换成有用信息和知识的技术和工具，这种对强有力数据分析工具的迫切需求使得 数据挖掘技术应运而生。 分类作为一种重要的数据挖掘技术，可以用于提取描述重要数据类的模型和预测未 来的数据趋势。分类技术在人工智能、机器学习以及模式识别等领域已经得到了广泛的 研究，并产生了许多的分类方法。但是，面对大规模的海量数据，传统的分类算法在可 扩展性和高效率性等方面存在着大量的问题。因此，近年来在“如何处理大规模数据”、 “如何使获得的分类知识更易于为人所理解及应用”等问题的激发下，分类问题已成为 数据挖掘领域的一项重要研究内容【1 j ，获得了更加广泛的、深入的研究。 现实中有很多问题实质上就是数据分类，也有很多问题可以转换为数据分类来解 决，因此数据分类存在着广泛的潜在应用。入侵检测是根据已知入侵类型的数据的特征 来对未知的数据进行分类来判断其所属类别，从而得出该数据代表的行为是否为异常如 果为异常则属于哪种类型的攻击；很多信息处理技术如信息过滤、信息检索、搜索引擎、 文本数据库等也都是以文本分类即数据分类技术为基础的，这些问题的实质都是数据分 类。从政府管理决策、商业经营、科学研究和工业企业决策支持等各个领域都可以找到 分类技术的用武之地。例如，可以建立一个分类模型，对银行的贷款客户进行分类，以 降低贷款的风险【2 j ；也可以通过建立分类模型，对工厂的机器运转情况进行分类，用来 预测机器故障的发生【3 ，4 】；类似的也能进行网络故障的诊断与预测f 5 l 。 因此，数据分类技术的进一步研究具有重要的理论息义和实际应用价值。入侵检测 ( i n t r u s i o nd e t e c t i o n 。i d ) 是一种积极主动地安全防护技术，提供了对内部攻击、外部攻击 和误操作的实时保护，在系统受到危害之前拦截和响应入侵。它作为继防火墙之后的第 二道安全防线，一直都备受国内外学者的广泛关注。文本分类作为处理和组织大量文本 数据的关键技术，可以在较大程度上解决信息杂乱现象的问题，方便用户准确地定位所 基于粗糙集和神经网络的数据分类技术研究 需的信息和分流信息。而且作为信息过滤、信息检索、搜索引擎、文本数据库、数字化 图书馆等领域的技术基础，文本分类技术有着广泛的应用前景。从表面上看这两个问题 好像毫无联系，但是它们的本质是相同的，即都是对数据进行分类。本文的主要工作就 是利用粗糙集和神经网络两种数据分类技术对入侵检测系统的结构模型和检测方法进 行探讨；同时，对文本分类中的特征降维方法进行了深入地研究。 1 2 数据分类技术 分类技术发展至今己取得了很大的成就，各种分类技术和理论不断涌现，基本上可 以分为三大类。一种是基于统计的方法，如贝叶斯网络、k n n ，支持向量机、回归模型、 最大熵模型等方法；另一种是基于连接的方法，如人工神经网络；还有一种是基于规则 的方法，如决策树、关联规则和粗糙集理论等【“。下面简要地介绍下什么是数据分类， 常见的数据分类技术及评价标准，数据分类技术的研究存在着哪些问题及未来的研究方 向。 1 2 1 数据分类技术及评价标准 分类( c l a s s i f i c a t i o n ) 是一个从现有的带有类别的数据集中寻找同一类别数据的共同 特征，并以这些特征为依据对新数据进行区分的过程。构造分类器( 即分类规则或模式) 的过程一般分为以下几个主要步骤。 ( 1 ) 将现有的已知类别的数据划分为训练数据和测试数据两部分。 ( 2 ) 通过构造分类算法对训练数据进行学习，最终得到一个符合学习要求( 如训练 精度) 的分类模型，它可以以分类规则、决策树或数学公式等形式给出。 ( 3 ) 使用分类模型对测试数据进行检测，如果符合测试要求( 如测试精度) ，则进行 ( 4 ) ；否则，返回( 2 ) 。 ( 4 ) 应用得到的分类模型对未知类别的新数据进行分类。 目前，用于数据分类的理论和技术有很多，下面对基于决策树、贝叶斯网络，支持 向量机的三种常用的分类方法先作简要介绍。基于神经网络、粗糙集理论的分类方法在 第二章将有详细地介绍。 基于决策树的分类方法是一种监督学习的方法，树的数量决定于分类的精度和树的 大小；决策树的算法有很多，1 9 8 6 年j r o s sq u i n l a n 给出i d 3 算法，它是国际上最早、 最有影响力的决策树算法，1 d 3 算法是基于信息熵的决策树分类算法，根据属性集的取 值选择实例的类别。1 9 9 6 年，j r o s sq u i n l a n 对i d 3 算法进行了补充和改进，给出了后 来非常流行的c 4 5 算法，该算法是一种归纳学习算法，但是这两种决策树算法对于相 大连理工大学硕士学位论文 对小的数据集是很有效的，但面对海量数据时，算法的有效性和可扩展性就成了关注的 问题。 贝叶斯分类是统计学分类方法，它基于贝叶斯定理，可以预测类成员关系的可能性， 给定样本属于某个特定类的概率。贝叶斯网络的研究在国外十分广泛，它可以对不确定 性知识进行推理。例如：医生看病，根据病人的症状，判断病人是否得了某种疾病，往 往是一种不确定的推理( 带概率的推理) ，多数情况下没有百分之百的把握。运用贝叶斯 网络进行推理，可以达到较好的效果。朴素贝叶斯分类算法能运用到大型数据库中，且 方法简单、分类准确率高、速度快。但是，贝叶斯定理假设一个属性值对给定类的影响 独立于其它属性的值，丽此假设在实际情况中经常是不成立的，因此其分类准确率可能 会下降。 v a p n i k 给出的一种新的基于统计学习理论的分类方法即基于支持向量机( s u p p o r t v e c t o rm a c h i n e ，s v m ) 的分类方法已成为机器学习领域研究的热点之一。支持向量机是 通过某种事先选择的非线性映射( 核函数) 将输入向量映射到一个高维特征空间，在这个 空间中构造最优分类超平面来实现分类的。目前，用s v m 构造分类器来处理海量数据 主要面临两个困难：首先，s v m 算法对大规模训练样本难以实施；其次，经典的s v m 算法只给出了二类分类的算法，对于解决多类的分类问题存在困难。 上面介绍的三种常用的分类算法决策树和支持向量机用于高维的海量数据分类时 存在着一些缺陷，而基于贝叶斯分类需要有先验概率且要求属性相对独立，更主要的是 这几种方法缺乏自学习和自适应能力。所以，论文选择了基于粗糙集和神经网络相结合 的分类方法。 粗糙集理论是一种刻划不完整和不确定性数据的数学工具，不需要先验知识，能有 效地处理各种不完备信息，从中发现隐含的知识，并和各种分类技术组合建立起能够对 不完备数据进行分类的算法。由于它在处理大数据量，消除冗余信息等方面的优良性能， 近年来在数据挖掘领域，特别是分类数据挖掘中得到了广发的应用，目前已成为最主要 的数据挖掘技术之- - 1 7 , 引。神经网络虽然因为训练时问长、分类知识解释性差等缺陷一 度被认为不适用于数据挖掘领域，但是由于它具有分类精度高，鲁棒性强等显著优点， 很多的神经网络仍被广泛应用于数据分类领域中。 不管是何种分类算法，我们评价它的好坏必须依据一定的标准，常用的分类算法的 比较和评估标准有如下几点。 ( 1 ) 预测准确率；指模型正确地预测新的或先前未见过的数据的类标号的能力； ( 2 ) 计算速度：分类的时间包括构造模型和使用模型进行分类的时间： ( 3 ) 强壮性：指给定噪音数据或具有空缺值的数据，模型正确预测的能力； 3 一 基于粗糙集和神经网络的数据分类技术研究 ( 4 ) 可规模性可伸缩性可扩展性：指给定大量数据，有效地构造模型的能力； ( 5 ) 可解释性：指学习模型提供的理解和洞察的层次。 1 2 2 数据分类技术面临的主要问题及未来研究方向 尽管分类技术继承了大量在人工智能、机器学习以及模式识别等领域已发展出的理 论与技术，但是它仍然面临大量问题的挑战。主要有以下几个方面的问题；9 1 ，有新的问 题就促使学者进行相应的研究，所以，数据分类技术未来的研究也主要围绕这些方面。 ( 1 ) 分类算法的有效性和可扩展性 现在的数据库包含的数据量往往达到g b 级，甚至t b 级。从海量的数据中有效地 抽取分类信息要求所用的分类算法的运行时间必须是可预测和可接受的，而且是可扩展 的，即对于小型数据具有很高分类精度而对于大海数据也应该具有较高的分类精度。所 以，对现有分类算法的改进和扩展，以及各种算法的有效结合来形成新的分类算法将成 为分类领域的一个研究热点，目前几经存在很多的基于粗糙集理论和神经网络相结合的 组合方法【1 0 1 。 ( 2 ) 有效的特征降维技术 目前，海量数据不仅是数据量大同时数据维数也非常高，如表示文本的向量空间模 型通常高达几千维甚至几万维。如果直接在输入空间上进行分类器训练，就可能带来两 个棘手的问题： 很多在低维空间具有良好性能的分类算法在计算上变得不可行； 在训练样本容量一定的前提下，特征维数的增加将使得样本统计特性的估计变得 史加困难，从而降低分类器的推广能力或泛化能力，呈现所谓的“过学习”或“过训练” 的现象i l “。 如何在无损失或少损失的前提下有效的降低数据的维数成为一个研究热点，在特征 降维和特征选择方面也取得了一定的成就【1 2 1 5 l ，但是很多已有的特征选择方法是针对具 体的应用问题的，所以，更多具有通用性和高效的特征降维方法需要进一步研究。 ( 3 ) 噪声数据和丢失数据的处理 这个问题在商业领域中尤其突出。可以想象，如果某数据库在建立时不是面向数据 挖掘的，其某些重要数据或属性可能丢失，某些数据的记录很可能产生模糊甚至错误。 这将干扰分类挖掘过程，降低挖掘知识的精确性。目前主要是使用统计和不确定性理论 来确定隐含变量及其依赖关系。所以，如何有效的去除噪声数据，合理的补全丢失的数 据，以提高算法的鲁棒性必将成为数据分类技术未来的研究热点之一。文献1 1 6 针对噪 声可能引起数据不一致的情况，通过引入可变精度粗糙集理论的思想，给基于熵的标准 大连理工大学硕士学位论文 赋予一个不一致度容忍系数，将决定规则的绝对条件放宽到概率性条件，从而增强了熵 不确定性标准抗噪声的能力。 ( 4 ) 时序数据和知识更新问题 在各种应用领域中的数据库大多是随时间变化的，这使得早期挖掘到的知识即分类 规则不适用于后期的情况或者有许多新的类型的数据或知识出现如入侵检测中随时可 能有新的攻击类型产生。这就要求数据挖掘系统能够保存已有知识的同时随时增加新知 识或更新已无用的旧知识的功能，并且通常采用增量学习等手段来处理时序数据。 ( 5 ) 模式易懂性 分类结果能否为人所理解是该分类算法能否为人所用的前提条件。简单明了的表达 方式能够提高挖掘结果的可理解性。目前的表达方式主要有：决策树、规则、图表、自 然语言表示，以及数据与知识的可视化等。决策树和图表表示虽然简单明了，但它只针 对数据量相对小的数据集有效，规则表示对于多类分类情况不够简洁，且规则的频繁更 新较困难，自然语言表示不够直观。所以，如何将分类结构表示得直观易懂，表示海量 数据的分类结果，对于多类分类都能够很直观表示等问题将是分类领域的又一关注点。 1 3 论文的主要内容及组织结构 论文的主要工作就是研究如何将粗糙集和神经网络有效地结合，并应用于海量的高 维数据的分类问题。任何方法的有效性都有一定的针对性，文中的分类方法主要是针对 入侵检测和文本分类这两个重要的数据分类领域进行的研究，其主要内容主要包括以下 两个部分。 ( 1 ) 针对入侵检测数据存在维数大、冗余度高及噪声数据较多等缺陷，神经网络如 r b f 网络、b p 网络和s o m 网络等作为分类器用于入侵检测具有如下的缺陷：首先，由 于神经网络本身不能识别出数据集中哪些属性是重要的，哪些属性是冗余的，即本身不 能进行数据的简化，这样导致神经网络分类器的结构十分复杂，网络的训练时间长，且 由于噪声数据的干扰，网络的分类性能下降；其次，很多神经网络模型如r b f 网络、 b p 网络、s o m 网络、h o p f i e l d 网络等网络模型都存在“稳定性可塑性”二难的缺陷 即学习性和记忆性存在着冲突。粗糙集对噪声数据敏感，在高噪声的环境下提取的分类 规则容错性差，泛化能力弱：再加之入侵检测中新的攻击类型不断涌现，且同一种入侵 类型以多种形式出现，这就要求规则的泛化能力相当好，且能不断更新规则库。综上所 述，文中给出了一种基于粗糙集和神经网络的层次入侵模型r s n n - i d s m 。通过粗糙集 的对数据进行预处理可以有效地去掉冗余的属性和数据降低数据的维数空间，这样可以 简化神经网络的结构；用神经网络作为分类器可以克服噪声数据的干扰提高方法的鲁棒 基于粗糙集和神经网络的数据分类技术研究 性，神经网络的自学习性和自组织性使之具有较强的泛化能力。文中详细讲解了该模型 的原理及算法的流程，最后，通过实验来验证了该基于该模型的入侵检测方法的合理性 和有效性。 ( 2 ) 权值计算和特征降维是影响文本分类的精度和效率的两个重要步骤。特征向量的高 维性不仅影响分类器的分类性能和分类速度且浪费了大量的存储空间。权值计算公式的 合理与否关系到能否正确的表征文档集，从而直接影响到分类的质量。所以，本文的另 外一个主要的工作是围绕着文本分类中的文本表示和特征降维展开。首先，根据特征词 的类别分布差异进行特征过滤；然后，分析传统的权值公式t f i d f ( t e r mf r e q u e n c y i n v e r s ed o c u m e n tf r e q u e n c y ) 。 的缺点，引入特征词的类别分作差异c d f 来改进的t f i d f ，改进后的权值计算公 式简记为t f i c d f 。根据t f i c d f 公式计算每个特征词的权值，生成文档集的向量空间 模型v s m ；接着，给出了一种基于可变精度粗糙理论( v p r s ) 的特征选择进一步选择对 分类贡献度大的特征，并用s q l 实现；最后，将经过上述一些特征降维方法简化过的 向量空间模型作为r b f 分类器的输入进行文本分类，分类结果表明文中给出的权值计 算和特征降维方法都是合理且有效的。 全文共分为五章，文章结构及各章主要内容组织如下： 第一章介绍了论文的研究意义，简述了数据分类及常用的分类方法，分析了数据分 类研究存在的问题及将来的研究方向；最后，给出了论文的主要研究内容及组织结构。 第二章介绍了论文中用到的两个理论粗糙集理论和神经网络理论，为后文方法的描 述做准备。重点介绍了基本粗糙集理论和可变粗糙集理论中的相关定义，粗糙集理论的 特点，处理问题的一般思路；详细描述了b p 网络和r b f 网络的原理和训练学习过程； 最后，分析了粗糙集和神经网络两种理论的可结合之处，及当前将两者结合的研究现状。 第三章首先介绍了入侵检测的相关知识包括经典的入侵检测模型，入侵检测的分类 及入侵检测的研究现状；接着详细描述了基于粗糙集和神经网络的层次入侵检测模型的 原理和算法流程；最后，从入侵检测的评估标准、国际上通用的数据集、本文实验的目 的和结果等几个方面对实验情况作了较为详细的介绍。 第四章分析了基于类别分布差异和v p r s 特征选择的文本分类方法。首先介绍了文 本分类的相关技术包括文本表示和特征降维；接着对基于类别分布差异的特征过滤方法 进行了详细介绍，分析了t f i d f 权值计算公式的缺陷而得到改进的权值计算公式 t f i c d f ，然后，分析了基于可变精度粗糙集的特征选择方法并给出了其s q l 语句的实 现；最后，详细介绍了实验的过程和结果。 最后总结了本文的研究工作，并对今后的研究做了展望。 大连理工大学硕士学位论文 2 相关理论 粗糙集理论作为一种处理不精确、不完整和不确定性的数学工具，利用属性约简算 法能有效地消除冗余信息，抽取分类规则：神经网络由于具有分类精度高，鲁棒性强等 显著优点被许多研究者用于数据分类。本章主要对粗糙集理论和神经网络的相关定义和 原理进行简要的介绍，并总结了它们可以结合的原因及目前存在的结合方法。 2 1粗糙集理论和可变粗糙集理论 粗糙集理论是一种刻划不完整性和不确定性的数学工具，能有效地分析不精确、不 一致、不完整等各种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的知 识，揭示潜在的规律。该理论与其他处理不确定和不精确问题理论的最显著的区别是它 无需提供问题所需处理的数据集合之外的任何先验信息，所以对问题的不确定性的描述 或处理可以说是比较客观的。由于粗糙集理论未能包含处理不精确或不确定原始数据的 机制，所以它与概率论，模糊数学和证据理论等其他处理不确定或不精确问题的理论有 很强的互补性。目前，粗糙集理论已被成功地应用于机器学习、决策分析、过程控制、 模式识别与数据挖掘等领域。下面针对论文中要用到的基本租糙集理论和可变精度粗糙 集理论做简要的介绍。 2 1 1 基本粗糙集理论 粗糙集理论( r o u 曲s e t ，r s ) 是波兰华沙理工大学的p a w l a k 教授于1 9 8 2 年给出的一 种处理模糊性和不确定性的数学工具m 。粗糙集理论是建立在分类机制的基础上的，它 将分类理解为在特定空间上的等价关系，而等价关系构成了对该空间的划分。粗糙集理 论将知识理解为对数据的划分，每一个被划分的集合称为概念，它的主要思想是利用已 知的知识库，将不精确或不确定的知识用已知的知识库中的知识来( 近似) 刻画。 一个信息表达系统s 可以表示为s 一( u ，a ，v ，) 其中u 是对象的集合，a 是属性的 集合，v u 屹，v a e a ，k 表示属性的值域，。u x a v 是一个信息函数，对 x e u ，a c a ，有，阮口) e v ，若爿可以分为条件属性集c 和决策属性集d ，即 c u d a ，c a d - 垂，则称s 为决策系统或决策表。在信息系统s 中，对任意一个属 性子集b c a ，可以定义一个不可分辨关系( 即等价关系) 形如式( 2 1 ) 。 i n d ( 曰) ：i n d ) ； x x c u 厂 ，b ) = f ( y ，6 ) v x e x ，y 石，6 曰 ( 2 1 ) 基于粗糙集和神经网络的数据分类技术研究 对于每个子集x u 和一个等价关系r _ c a ，r 的x 下近似集戤( l o w e r a p p r o x i m a t i o n ) ( 也称为z 的r 正域记作p n 倦) ) 和上近似集瓦y ( u p p e ra p p r o x i m a t i o n ) 分别定义为形如式( 2 2 ) ，( 2 3 ) 。 p o s r ( x ) i _ r xi u u r ：y x 砝= 懈e u r ：y a x 册 ( 2 2 ) ( 2 3 ) p o s 。( x ) 或星x 是由那些根据知识r 判断肯定属于x 的u 中元素组成的集合；r x 由 根据知识r 判断可能属于x 的u 中元素组成。当x 能表达成某些r 等价类的并时，则 x 是r 可定义的；否则x 为r 不可定义的。r 可以定义集称为r 的精确集，而r 不可定 义集称为r 非精确集或r 粗糙集。因此，盈x 可描述为中的最大可定义集，r a t 描述为 的最小不可定义集。由等价关系定义的集合的近似精确度定义公式形如式( 2 4 ) 。 郴) ；矧 ( 2 4 ) 其中，x 一妒，l x l 表示集合x 的基数。近似度僻) 用来反映集合x 的知识完全程 度。当僻) 1 ，x 为r 可定义的；当口。( x ) c 1 时，x 为r 不可定义的。定义概念的 模糊或者粗糙程度。因此，粗糙集与概率论和模糊集理论不同，不精确性的数值不是事 先假定的，而是通过表达知识不精确性的概念近似计算得到的。 设u 为论域，p ，q e a 为u 上的两个等价关系，q 的p 正域p o s e ( q ) 定义公式形 如式( 2 5 ) 。 p o s e ( q ) ；ug ( x ) ( 2 5 ) 那么，近似分类精度定义公式形如式( 2 6 ) 。 馓卜器 ( 2 6 ) q 的p 正域是u 中所有根据分类卯的信息可以准确的划分到关系q 的等价类中 去的对象集合。如果q 的所有或部分基本范畴能由p 来定义，那么p 和q 之问的知识 依赖度或者近似分类质量定义公式形如式( 2 7 ) 。 拈一掣 缇， 大连理工大学硕士学位论文 当k = l 时，q 完全依赖于p 当0 k = 0 0 ( 2 10 ) 基于租糙集和神经网络的数据分类技术研究 其中包含度c ( y ，z ) 刻画的是由关系r 形成的等价类被集合x 包含的程度，a e ( 0 5 ，1 1 为用户指定的包含度阈值。在关系r 下的等价类以大于少包含度包含在x 中， 这些等价类的元素构成了矿下近似。夕一上近似集则为u 中的等价类以大于1 书包含度 包含在石中的元素集合，当口= 1 时，此模型就退化为标准的粗糙集模型。p a w l a k 粗糙 集模型中的其它定义都是基于上下近似集的，因此，根据少上下近似集的定义可以得出 可变精度粗糙集中相应的定义，这里就不再一一列出。 粗糙集理论是对这些不确定信息进行定量化处理，可变精度粗糙集引入包含程度口 能更精细地划分边界上的样本。在概率意义上，若等价类中只有很少比例的元素不属于 x ，可以通过选择合适的口将其归为下近似集；或者只有很少的元素属于x ，通过口可 将其排除在上近似集之外。这样能更好地处理一些不一致信息。研究证明，适当选择口， 可以提高分类的精度，获得更好的分类效果l 加j 。 可变精度粗糙集是对标准粗糙集理论的一种扩展。它通过设置闽值参数，放松了标 准粗糙集理论对近似边界的严格定义。与粗糙集理论相比，可变精度粗糙集可以在不一 致数据中挖掘出具有一定一致度的决策规则，克服了标准粗糙集对数据噪声过于敏感的 缺点，因而增强了数据分析和处理的鲁棒性。 2 1 3 粗糙集处理问题的一般步骤 粗糙集理论的特点是不需要预先给定某些特征或属性的数量描述，而是直接从给定 问题的描述集出发，通过不可分辨关系( 等价关系) 确定给定问题的近似域，从而找出该 问题中的内在规律。基于粗糙集的算法的一般步骤如下： ( 1 ) 创建相关的目标数据集，选取样本数据集；将数据集转化为决策表或信息表( 即 二维表格的) 形式； ( 2 ) 数据预处理，主要包括两个方面：数据的补齐和离散化； ( 3 ) 属性约简，也即删除冗余的属性； ( 4 ) 对每个实例删除冗余的属性值，也就是值约简； ( 5 ) 将约简后的数据按照对应决策属性的相关联度大小进行规则提取。 上述的步骤并不是每一步都需要执行的，根据粗糙集理论应用于不同的方面而有所 不同，如果将其应用于基于规则的分类问题如自动文本挖掘，入侵检测或故障诊断等就 要执行到第五步，并且需要反复优化得到的规则；如果只是将粗糙集作为神经网络等分 类算法或其软计算方法相结合进行数据据的约简操作，则只需要执行到第三步即可。 大连理工大学硕士学位论文 属性约简的目标就是要从条件属性集合中发现部分必要的条件属性，使得根据这部 分条件属性形成的相对于决策属性的分类和所有条件属性形成的相对于决策属性的分 类一致，即和所有条件属性相对于决策属性d 有相同的分类能力。 对于属性约简后的信息表，并不是每条记录的所有条件属性值都是必须的。值约简 的过程对表中记录进行考察，删除所有不影响规则表达的冗余的条件属性值，即去掉信 息系统中的行的冗余列值。约简后的信息表比原有信息表具有较少的属性个数和较少的 属性值。 2 1 4 粗糙集理论的特点 粗糙集理论在数据分析和处理中有其显著的优点，主要体现在下面四个方面。 ( 1 ) 粗糙集理论无需提供被分析数据之外的任何先验信息。这也是它与其他处理 数据模糊性和不确定性的数学工具如证据理论和模糊集理论的最主要区别。具体地说， 证据理论对属性、数据或知识等局部的信念及全局信念的函数，模糊集理论中对隶属度 与隶属度函数，均需要凭借系统设者的经验事先给定，而粗糙集理论则无需这些先验的 信息，因此其对不确定性、模糊性的描述相对客观。 ( 2 ) 粗糙集理论是强大的数据分析工具，如表达和处理不完备信息；在保留关键信 息的前提下对数据进行约简，求得知识的最小表达；识别并评估数据之间的依赖关系【矧。 ( 3 ) 租糙集理论得到的知识为规则知识，可理解性强，而且容易验证。 ( 4 ) 粗糙集理论基于可靠的数学推导，可以与其它计算方法联合使用。例如，粗糙 集理论与神经网络、遗传算法、贝叶斯等方法结合。粗糙集理论与其它软计算方法的集 成也是当前粗糙集发展的一种趋势。 当然，粗糙集理论也存在自身的缺陷【川。首先，粗糙集理论未包含处理不精确或不 确定原始数据的机制，因此，单纯使用这个理论不一定能有效地描述数据不精确或不确 定的实际问题。其次，租集理论只适用于处理离散数据，要对具有连续属性值的数据进 行处理时，一般先要使用离散化方法将其转化为离散数据。 2 2 神经网络理论 神经网络( n e u r a ln e t w o r k ，简称n n ) 是人们在模仿人脑处理问题的过程中发展起来 的一种新型智能信息处理理论。它通过大量的称为神经元的简单处理单元构成非线性动 力学系统，对人脑的形象思维、联想记忆等进行模拟和抽象，实现与人脑相似的学习、 识别、记忆等信息处理能力。 神经网络由于具有良好的非线性映射能力和对任意函数的准确逼近能力，用于分类 问题往往能获得很高的分类精度，因而被公认为分类性雒最好的分类方法之一。神经网 基于粗糙集和神经网络的数据分类技术研究 络具有优良的鲁棒性，在噪声环境下也能很好地完成分类任务。另外，同粗糙集理论一 样，神经网络也无需提供被分析数据之外的任何先验信息。 2 2 1神经网络的特点和分类 神经网络之所以具有如此广阔的应用和发展前景，是与它所独有的特点分不开的， 下面将简要介绍下神经网络的特点和分类。 神经网络具有如下特点 2 5 , 2 6 l 。 ( 1 ) 大规模并行处理：神经网络具有并行处理的特征，大大提高了工作速度。 ( 2 ) 非线性处理：神经网络方法本身属于非线性模型，能够适应各种复杂的数据关 系。 ( 3 ) 自组织及自适应性：能够在学习过程中自适应地发现蕴含在样本数据中的内在 特性及规律：使它能够比很多分类算法更好地适应数据空问的变化。 ( 4 ) 分布式存储，存储与计算相结合：信息储存在神经元之间连接强度的分布上( 即 权值和闽值) ，存储区与运算区合为一体； ( 5 ) 联想能力：人脑具有很强的“容错性”和联想记忆功能，局部的神经元受损并 不影响整个网络的正常工作。 由于分类标准的不同，神经网络有多种分类方法。按照神经元互连模式的不同，神 经网络通常分为二种典型的网络结构。 ( 1 ) 前向网络( 前馈网络) 网络可划分为若干“层”，各层依次排列，通常情况下，第f 层的神经元只接受第 g 1 ) 层神经元给出的信号，各神经元之间没有反馈。输入节点层与输出节点层统称为“可 见层”，而其它中间层则成为“隐含层”，这些神经元称为隐单元。 ( 2 ) 反馈网络 反馈网络与前向网络的重要区别在于反馈网络至少有一个反馈连接。反馈连接既可 以是异反馈( 一个神经元的输出反馈到其它神经元作为输入) ，也可以是自反馈( 一个神 经元的输出反馈到自身作为输入) 。同时网络中还可以有计算功能的隐神经元。 神经网络的主要任务就是对外部世界进行建模，并通过学习使模型与外部环境充分 一致从而达到完成特定应用的目的。学习的实质就是使神经元之间的权重随外部激励 ( 环境) 作自适应变化。网络的基本学习方法有以下几种。 ( 1 ) 误差矫正学习 误差矫正学习是指当神经网络的实际输出与日标输出产生误差时，利用误差信号来 矫正调整神经元之间的连接权重，通过这样一个迭代序列矫正过程，使得神经网络的输 出逐渐逼近理想的期望输出。这可以通过最小化代价函数或性能指标来实现，代价函数 大连理工大学硕士学位论文 一般定义为信号误差的平方。误差矫正学习通常也称为w i d r o w - h o f f 规则、a d a l i n e 规 则或s 规则。前向网络通常采用误差矫正学习方法。 ( 2 ) h e b b i a n 学习 h e b b i a n 学习规则可简单描述为：如果一个神经元从另一神经元接受输入激励信号， 并且两者均处于高激励电平( 数学上就是两者的符号相同)