《粗糙集理论约简算法的研究》由会员分享，可在线阅读，更多相关《粗糙集理论约简算法的研究（76页珍藏版）》请在金锄头文库上搜索。
1、分类号 U D C 密级 学校代码! Q 垒窆2 ， 武多萎理歹大浮 学位论文 题目担糙塞堡途丝笪簋洼的壁寇 文 至h 曼B 皇墨曼丛堡鱼Q 壁R 曼亟堕鱼鱼Q 塾! g Q 煎! h 堡Q 题 目 Q 丛g hS 照墨! 鱼星Q 醒 研究生姓名姿堡 指导教师姓名整些已一职称立蛙L 学位 申请学位级别硕士 4 3 0 0 6 3 论文提交日期至Q ! ! 笙垒且论文答辩日期 2 Q ! ! 生且 学位授予单 答辩委员会 予日期 评阅 2 0 11 年0 5 月 川I I IIII I1 1 1 1 1I II II I IIIIl ：。Y 18 8 0 6 0 1 独创性声明 本人声明，所呈交
2、的论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得武汉理工大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 、 签名：日期：兰笙：3 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即学校有权保留并向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅。本人授权武汉理工大学可以将本 学位论文的全部内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手
3、段保存或汇编本学位论文。同时授权经武汉理 工大学认可的国家有关机构或论文数据库使用或收录本学位论 文，并向社会公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：忑芗幺导师( 签名) 掰日粉l l , m 。婶 摘要 粗糙集理论是由Z P a w l a k 于1 9 8 2 年提出的，它是一种处理信息的工具，可 以有效地对不精确、不一致、不完整信息进行分析。有关粗糙集理论的研究现 已成为热点，该理论的应用也非常广泛，如入侵检测、数据挖掘、知识发现等。 粗糙集理论中的一个重要内容是属性约简，属性约简的目的是在保持决策 表分类能力不变的情况下删除冗余的属性，得到一个精简
4、的决策表，以便于以 后的计算。 属性约简算法有很多，文中主要介绍基于差别矩阵的约简算法。首先介绍 了几种经典的属性约简算法，给出了它们的定义，对求解过程加以分析，指出 了它们的优缺点，对于它们的缺点，给出了相关的解决方法，并给出实例。 其次，介绍了_ 种新的属性约简模型，该模型与传统模型是等价的。在文 中给出了该模型的相关定义和求解属性约简的算法，并通过实例对算法的求解 过程加以演示。 再次，介绍一种基于差别矩阵的最小约简算法，该算法通过u ( e 划分来计 算最小约简，并指出其不足，如存在重复计算、结果错误等。分析了算法的不 足后，本文给出了一种改进算法，该算法首先对决策表中的数据进行压缩，
5、删 除冗余数据，降低了时间复杂度和空间复杂度，然后用基于属性核的思想求解 最小约简。 最后，对改进算法进行分析。在决策表中冗余数据较多的情况下，改进算法 才能充分发挥其优势。该算法还有待进一步完善，如将该算法与智能计算相结 合以提高计算效率。 关键字：粗糙集，差别矩阵，属性约简，最小约简 A b s t r a c t R o u g hS e t sT h e o r y , p r e s e n t e db yP a w l a ki n 19 8 2 ，i sa l lt o o lt oh a n d l e i n f o r m a t i o n ，i t c a l l e
6、 f f e c t i v e l y d e a l 诵li m p r e c i s e ，i n c o n s i s t e n t , i n c o m p l e t e i n f o r m a t i o n , e t c 1 1 1 er e s e a r c ho nr o u g hs e tt h e o r yh a sb e c o m eah o ts p o t ，t h et h e o r yi s w i d e l ya p p l i e di ni n s t r u s i o nd e t e c t i o n ，d a t am
7、 i n i n g , k n o w l e d g ed i s c o v e r ya n dS Oo n A t t r i b u t er e d u c t i o ni sa ni m p o r t a n tp a r to fR o u g hS e t sT h e o r y , t h ep u r p o s eo f a t t r i b u t er e d u c t i o ni st od e l e t et h er e d u n d a n ta t t r i b u t e su n d e rt h ec o n d i t i o
8、no f m a i n t a i n i n gt h ec l a s s i f i c a t i o n ，g e ta c o n c i s ed e c i s i o nt a b l et op r o v i d ec o n v e n i e n c ef o r t h el a t e rc a l c u l a t i o n T h e r ea r em a n ya l g o r i t h m so na t t r i b u t er e d u c t i o n ，b u tt h i s p a p e rm a i n l y i n
9、t r o d u c e st h ea l g o r i t h m sb a s e do nd i s c e r n i b i l i t ym a t r i x F i r s t l y , t h i sp a p e ri n t r o d u c e s s e v e r a lt y p i c a l r e d u c t i o na l g o r i t h m s ，g i v e st h ed e f i n i t i o n so ft h ea l g o r i t h m s ，a n a l y z e s t h es o l v
10、i n gp r o c e s s e so ft h ea l g o r i t h m s ，p o i n t so u tt h ea d v a n t a g e sa n dd i s a d v a n t a g e s o ft h e m ，g i v e sr e l e v a n ts o l u t i o n sf o rt h ef a u l t s ，g i v e se x a m p l e sa tl a s t S e c o n d l y ，an e wm o d e lo fa t t r i b u t e r e d u c t i
11、o ni si n t r o d u c e d ，t h i sm o d e li s e q u i v a l e n tt o t h et r a d i t i o n a lm o d e l S o m er e l a t e dd e f i n i t i o n so ft h i sm o d e la n d a t t r i b u t er e d u c t i o na l g o r i t h mb a s e do nt h i sm o d e la r ep r e s e n t e di n t h i sp a p e r ，a n d
12、a n e x a m p l ei sg i v e nt od e m o n s t r a t et h ea t t r i b u t er e d u c t i o np r o c e s so f t h ea l g o r i t h m T h i r d l y , a na l g o r i t h mb a s e do nd i s c e r n i b i l i t ym a t r i xi si n t r o d u c e d ，i tc a l c u l a t e s t h em i n i m u mr e d u c t i o n
13、b yU c p a r t i r i o n ，t h i sp a p e rp o i n t so u t t h e a l g o r i t h m S d i s a d v a n t a g e s ：t h e r ea r er e p e a t e dc o m p u t a t i o na n dt h ea l g o r i t h mm a y b eg e tw r o n g r e s u l t s A f t e rt h ed i s a d v a n t a g e so ft h ea l g o r i t h mi sa n a
14、l y z e d ，a ni m p r o v e da l g o r i t h mi s p r e s e n t e d ，f i r s t l y , t h ea l g o r i t h mc o m p r e s s e s t h ed a t ao fd e c i s i o n t a b l e ，d e l e t et h e r e d u n d a n td a t a , t h i sr e d u c e st h et i m ec o m p l e x i t ya n dt h es p a c ec o m p l e x i t
15、 y , t h e na m i n i m u ma t t r i b u t er e d u c t i o nb a s e do nc o r eo fa t t r i b u t e sa r eu s e dt oc o m p u t et h e m i n i m u mr e d u c t i o n F i n a l l y ，t h ei m p r o v e da l g o r i t h mi sa n a l y z e d ，o n l yi ft h e r ea r em a n yr e d u n d a n t d a t a si n
16、t h ed e c i s i o nt a b l e ，t h ei m p r o v e da l g o r i t h mC a nw o r ke f f e c t i v e l y ，t h ea l g o r i t h m n e e d sf u r t h e ri m p r o v e m e n t ，s u c ha sc o m b i n i n gw i t hi n t e l l i g e n tc o m p u t a t i o n K e yw o r d s ：R o u g hS e t s ，D i s c e m i b i l i t yM a t r i x ，A t t r i b u t eR e d u c t i o n , M i n i m u m R e d u c t i o n ： I I 目录 第1 章引言。l 1 1粗糙集理论的背景和特点
