（计算机应用技术专业论文）粗集中的属性选择算法及优化方法.pdf

摘要 摘要 粗糙集理论是z p a w l a k 于1 9 8 2 年提出的一种数据挖掘新方法，已成功应用于特征 选择、模式识别、机器学习、决策分析等领域基于粗糙集技术的数据挖掘是通过属性 约简来实现的，属性约简算法可粗略地分为三类：前向属性约简算法、后向属性约简算 法和其他属性约简算法( 如基于区分矩阵的属性约简算法) 前向属性约简方法得到的 约简大多都存在冗余属性，本文对h o r a f a 属性约简算法进行改进，提出了一种新的基于 差别矩阵的前向选择算法，首先删除区分矩阵中属性重要性最小的属性，然后选择只包 含一个属性的矩阵元素，并将其加入到属性约简集合中，确保最终得到一个不存在冗余 属性的约简对于后向属性约简方法，通过分析删除待删属性后得到的等价类的性质，提 出了一种以划分基数为停止基准的后向属性约简算法，运用该算法可以得到更少的决策 规则通过分析集合覆盖的性质，对集合覆盖的概念进行了扩展，提出了新的集合覆盖概 念，并将其应用到基于区分矩阵的属性约简算法针对前向属性约简算法在添加新属性 后，前续结果需重复计算的问题，提出了一种递归计算方法在区分矩阵的建立过程中， 利用决策属性首先对实例集合进行划分，然后再建立区分矩阵，提高了建立区分矩阵的 效率 关键词属性约简核属性选择前向选择后向选择 a b s t r a c t a b s t r a c t r o u g h s e t st h e o r yp r o p o s e do r i g i n a l l yb yz p a w l a ki san e wd a t am i n i n gm e t h o d ，w h i c h h a sb e e ns u c c e s s f u l l ya p p l i e di nm a n yf i e l d s ，s u c h 硒f e a t u r es e l e c t i o n , p a t t e r nr e c o g n i t i o n , m a c h i n el e a r n i n g ，d e c i s i o na n a l y s i s ，e t c d a t am i n i n gb a s e do nr o u g hs e t st e c h n i q u ei s a e c o m p l i s h e db yu s i i 冯a t t r i b u t e sr e d u c t i o na l g o r i t h m ，w h i c hc a nb er o u g h l yc l a s s i f i e di n t o t h r e ec a t e g o r i e s ：f o r w a r dr e d u c t i o na l g o r i t h m s ，b a c k w a r dr e d u c t i o na l g o r i t h m s ，a n do t h e r r e d u c t i o na l g o r i t h m s ( f o re x a m p l et h ea t t r i b u t er e d u c t i o na 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 y m a t r i x ) t h er e d u c t so b t a i n e db yf o r w a r dr e d u c t i o na l g o r i t h m su s u a l l y r e t a i ns o m e d i s p e n s a b l ea t t r i b u t e sf o rc l a s s i f i c a t i o n ；t h i sp a p e rh a si m p r o v e dt h eh o r a f aa l g o r i t h mt o r e m o v et h es u p e r f l u o u sa t t r i b u t e s f i r s t l y , a na t t r i b u t ew i t ht h el o w e s ts i g n i f i c a n c ei sd e l e t e d f r o mt h ed i s c e r n i b i l i t ym a t r i x s e c o n d l y , m a t r i xu n i tw i t ho n ea t t r i b u t eo n l yi sa d d e dt ot h e r e d u c ts t e pb ys t e p ，f i n a l l yar e d u c tw i t h o md i s p e n s a b l ea t t r i b u t e sc a l lb eo b t a i n e d f o r b a c k w a r dr e d u c t i o na l g o r i t h m s ，s o m ee q u i v a l e n c ec l a s s e sc a nb eo b t a i n e db yr e m o v i n ga 1 1 a t t r i b u t e ，t h ep r o p e r t i e so ft h ee q u i v a l e n c ec l a s sa r ea n a l y z e d ，an o v e lb a c k w a r dr e d u c t i o n a l g o r i t h m sw i t hh a l tc r i t e r i o nb a s e do nc 莉i n a l 时o fp a r t i t i o ni sp r o p o s e d ，t h en u m b e r so f d e c i s i o nr u l ec o n v e r t e df r o mt h eo b t a i n e dr e d u c tc a nb ed e c r e a s e d an e wc o n c e p to fs e tc o v e r i sp r e s e n t e d ，w h i c hi st h eg e n e r a l i z a t i o no ft r a d i t i o n a ls e tc o v e r , a n dw ei n t e g r a t et h en e w c o n c e p ti na t t r i b u t er e d u c t i o na l g o r i t h m sb a s e do nd i s e m i b i l i t ym a t r i x w h e nw eu s et h e f o r w a r dr e d u c t i o na l g o r i t h m st or e d u c et h ed i s p e n s a b l ea t t r i b u t e s ，t h ep r e v i o u sr e s u l t sm u s tb e r e p e a t e d l yc o m p u t e d ，i no r d e rt oo v e r c o m et h ed r a w b a c ka ni t e r a t i v e l ym e t h o d si sp r o p o s e d w ef i r s t l yp a r t i t i o nt h ei n s t a n c e sb yu s i n gt h ed e c i s i o nb e f o r ew ec o n s t r u c tt h ed i s c e m b i l i t y m a t r i x ，t h i sc a l le f f e c t i v e l yd e c r e a s et h et i m ef o rc o n s t r u c t i n gt h ed i s c e m b i l i t ym a t r i x k e y w o r d s a t t r i b u t er e d u c t i o ns e l e c t i o no fc o r ea t t r i b u t e sa n t e r i o rs e l e c t i o n b a c k s e l e c t i o n i i 河北大学 学位论文独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教 育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了致谢。 作者签名：主越 日期：垄璺2 年 其中，c 中的属性被称为条件属性，d 中的属性被称为决策属性 对于含有多个决策属性的决策表，可以利用后面提到的知识将它转化成只含有一个 决策属性的决策表的等价形式 定义3 3 2 在信息系统s 中，对于每个属性子集b 彳，可以定义一个不可区分关 系i n d ( b ) ：i n d ( b ) = ( x ，y ) u xuv b b ，f ( x ，b ) = f ( y ，6 ) ) 显然，i n d ( b ) 是一个等价关系根据等价关系的自反性、传递性和对称性，具有等 价关系的所有元素组成的集合构成了一个等价类，对象x 的等价类 x 肋定义为： 【z 】肋= y i y u ，( y ，x ) n d ( b ) ，简单的记为 x 口定义在集合u 上，根据等价关系b 得到的所有等价类组成的集合簇，构成了b 对u 的一个划分，称u 根据b 得到的划分，记 为t7 b 表3 3 1 ：条件属性a ，b ，c ，d ，e 决策属性：f ua b cdef 101001o 2ool0 1o 3l1 1 01 1 1 6 第3 章属性约简的基础知识 对于表3 3 1 ，如果a 、b 、c