（计算机应用技术专业论文）基于粗糙集的属性约简研究.pdf

摘要 粗糙集理论是一种处理含糊和不确定性信息的新型数学工具，其 理论提出以来得到迅速的发展和广泛的应用。知识约简是粗糙集理论 重要研究内容之一，它的主要目的在于去除数据中的冗余信息，同时 保持原决策信息系统的分类能力不变。针对大量或海量数据，原有约 简方法效率低，须对粗糙集约简计算理论进行优化，发展完善相关计 算算法，以提高知识约简的效率。本文基于粗糙集理论，针对知识约 简优化计算问题进行了较为深入的研究。 对粗糙集理论三种知识约简方法进行比较，分析各类方法的优缺 点以及它们之间的相互关系。通过改进原有差别矩阵，在对象比较过 程中一次性提取核与用于求约简的所有分辨信息，并保证分辨信息之 间不存在包含关系。在此分辨信息基础上以属性频度为启发式信息给 出了一种基于改进差别矩阵的启发式约简及增量式更新方法。理论分 析与实验仿真表明，新启发式算法产生约简与分辨函数思想产生的最 小约简一致，说明算法的有效性。 基于约简算法完备性理论，指出现有知识约简算法的不完备性， 对本文的新启发式约简算法的完备性给出的了充分的证明。其次，在 p a w l a k 知识约简定义下，证明了任意决策信息系统约简个数是条件 属性的组合函数。利用己证明的重要性质提出一种非指数级的所有约 简计算方法，低于所有相关文献算法的时间复杂度。该结论有助于改 进知识约简的效率，进一步提高粗糙集数据分析能力。 关键词粗糙集，约简，信息系统，完备性 a b s t r a c t r o u g hs e tt h e o r yi s an e wm a t h e m a t i c a lt o o lt or e a s o na b o u t u n c e r t a i na n dv a g u ei n f o r m a t i o n i th a sb e e n r a p i d l yd e v e l o p e da n d w i d e l ya p p l i e di nm a n yf i e l d s r e d u c ti st h em o s ti m p o r t a n tc o n c e p ti n r o u g hs e t ，w h o s em a i np u r p o s ei st or e m o v et h er e d u n d a n ti n f o r m a t i o n a n dp r e s e r v e sc l a s s i f i c a t i o n a c c u r a c y o fo r i g i n a li n f o r m a t i o n s y s t e m f a c i n gw i t hh u g ea m o u n t so fd a t a ，t h eo l da l g o r i t h m sf o rr e d u c ti sn o t f e a s i b l e i ti sn e c e s s a r yt oo p t i m i z et h ec o m p u t a t i o nt h e o r y , a n dp r o p o s e s o m ep r a c t i c a la l g o r i t h m st oi m p r o v et h ee f f i c i e n c yo fr e d u c t b a s e do n r o u g hs e tt h e o r y , t h i st h e s i sm a i n l yf o c u s e so nt h ep r o b l e m so fo p t i m i z e d c o m p u t a t i o nf o rr e d u c t n o to n l yt h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h r e ek i n d so fr e d u c t i nr o u g hs e tb u ta l s ot h e i rr e l a t i o n sh a v eb e e nc o m p a r e da n da n a l y z e d t h r o u g hi m p r o v i n gd i s c e r n i b i l i t ym a t r i x ，t h ei n f o r m a t i o nf o rc o r ea n d r e d u c tw i t h o u ti n c l u s i o nr e l a t i o ni sg a i n e di nt h ep r o c e s so fc o m p a r i n g o b j e c t s b a s e do nt h i si n f o r m a t i o n ，an e wh e u r i s t i ca l g o r i t h mf o rr e d u c ti s p r o p o s e d t h ee x p e r i m e n t a l r e s u l t si n d i c a t et h a tt h er e d u c to fn e w h e u r i s t i ca l g o r i t h mi si d e n t i c a lw i t h t h em i n i m a lr e d u c t ，s h o w i n gt h e e f f i c i e n c yo f n e wa l g o r i t h m w i t hd e e p l y s t u d y i n gt h ec o m p l e t e n e s so fr e d u c ta l g o r i t h m ，t h e i n c o m p l e t e n e s so fe x i s t i n ga l g o r i t h m sf o rr e d u c ti sp o i n t e do u t ，a n dt h e t h e s i sa l s op r o v i d e st h ep r o o ft op r o v et h ec o m p l e t e n e s so fn e wh e u r i s t i c a l g o r i t h mf o rr e d u c t t h e n ，u n d e rt h ep a w l a k sd e f i n i t i o nf o rr e d u c t ，i ti s c e r t i f i e dt h a tt h em e m b e ro fr e d u c ti na n yd e c i s i o ni n f o r m a t i o ns y s t e mi s t h ec o m b i n a t i o nf u n c t i o no fc o n d i t i o na t t r i b u t e b a s e do nt h i sp r o p e r t y , a n o n e x p o n e n t i a la l g o r i t h mi sp u tf o r w a r dt oc o m p u t ea l lr e d u c t s ，w h i c hi s l e s st h a no t h e ra l g o r i t h m si nt h ec o m p l e x i t yo ft i m ea n ds p a c e t h e a l g o r i t h mi sh e l p f u lt oi m p r o v et h ee f f i c i e n c yo fr e d u c ta n de n h a n c e r o u g h s e t sc a p a c i t yo fa n a l y s i st ol a r g e rd a t a s e t k e yw o r d s ：r o u g hs e t ，r e d u c t ，i n f o r m a t i o ns y s t e m ，c o m p l e t e n e s s 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得中南大学或其他单位的学位或证书而使用过的材 料。与我共同工作的同志对本研究所作的贡献均已在论文中作了明 确的说明。 作者签名 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允 许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名： 聊繇通嗍乎地卫 m a s t e rd e g r e et h e s i s c h a p t e rii n t r o d u c t i o n 1 1 b a c k g r o u n d o h a p t e r1 in t r o d u c tio n i nc l a s s i c a ll o g i c ，t h e r eo n l ye x i s tt w ov a l u e s ：t r u ea n df a l s e ，b u tp r a c t i c a l l yl o t s o fv a g u ep h e n o m e n ae x i s tb e t w e e nt r u ea n df a l s e ，t h e r e f o r e ，m a n yp e o p l ed e v o t e t t h e m s e l v e st ov a g u ec o n c e p tr e s e a r c hf o ral o n gt i m e i n19 0 4 ，gf r e g ef i r s t l yp u t f o r w a r dt h ew o r d “v a g u e ”，a n di tc a l lb er e s o l v e di nb o u n d a r yr e g i o n ，i no t h e rw o r d s ， s o m ei n d i v i d u a l sc a n tb ec l a s s i f i e de i t h e ri ns o m es u b s e to ri t ss u p p l e m e n ts e t f o r i n s t a n c e ，“h i g h ”i sav a g u ec o n c e p t i n19 6 5 ，l a z a d e hp u tf o r w a r df u z z ys e tt h e o r y n ，m a n yc o m p u t e rs c i e n t i s t s w a n t e dt os o l v egf r e g ev a g u ec o n c e p tb yu s i n g f u z z ys e tt h e o r y b u tf u z z ys e t c a n tb ec o m p u t e d ，t h e r e f o r e ，t h e r ei sn ow a yt oc o m p u t et h en u m b e ro fv a g u e e l e m e n t si nab o u n d a r yr e g i o n i n19 8 2 ，z p a w l a kp r e s e n t e dr o u g hs e t s 2 】i nv i e wo fg f r e g e sb o u n d a r yi d e a ( r o u g hi st h ep o l i s ht r a n s l a t i o no fv a g u e ) ，i nr o u g hs e t s ， i n d i v i d u a l sw h i c hc a n tb ed e t e r m i n e dc a nb er e s o l v e di nb o u n d a r yr e g i o n ，a n dt h e b o u n d a r yi sd e f i n e dt ob ead i f f e r e n c es e tb e t w e e nt h eu p p e ra p p r o x i m a t i o na n dt h e l o w e r a p p r o x i m a t i o n ，s i n c et h eu p p e ra p p r o x i m a t i o na n dt h el o w e ra p p r o x i m a t i o nc a l l b em a t h e m a t i c a l l yd e t e r m i n e db ye q u i v a l e n c er e l a t i o n s h i p ，t h en u m b e ro fv a g u e e l e m e n t sc a nb ec o m p u t e d ，i no t h e rw o r d s ，v a g u ed e g r e eb e t w e e nt r u ea n df a l s ec a n b ec o m p u t e d l 3 1 s o m ei n f o r m a t i o nt h a t p e o p l er e c e i v e i nt h ef i e l do fe c o n o m y , f i n a n c e ， m a n a g e m e n ta n de n g i n e e r i n gc a n tb ed e n o t e db yc l a s s i c a ls e t w ec a l li tr o u g h i n f o r m a t i o n i ti sd i f f i c u l tf o ru st ou s er o u g hi n f o r m a t i o n ，b e c a u s ew ed o n th a v e a p p r o p r i a t et o o lt od e n o t et h e m r o u g hs e t st h e o r yg i v e sa ni m p o r t a n tt h e o r e t i c a lt o o l t os t u d yt h er o u g hi n f o r m a t i o na n di t sc h a r a c t e r i s t i c s r o u g hs e t st h e o r yi st h e f o u n d a t i o no fr o u g hs y s t e mt h e o r ya n da p p l i c a t i o n s m a s t e rd e g r e et h e s i s c h a p t e r1i n t r o d u c t i o n 1 2in t r o d u c t o na n dd e v eio p m e n to fr o u g hs e tt h e o r y i n19 8 2 ，p o l i s hs c h o l a rz p a w l a kp u b l i s h e dh i st h e s i sa b o u tr o u g hs e t b e c a u s et h ei n i t i a lr e s e a r c ht h e s e sa b o u tt h er o u g hs e tt h e o r yt h a tw e r ea l lp u b l i s h e d i np oli s hi n t e r n a t i o n a ls c h o l a r sd i d n tp a ya t t e n t i o nt ot h er e s e a r c ha c h i e v e m e n t s t h e r e s e a r c hw a so n l yw i t h i ns o m ee a s t e r ne u r o p e a nc o u n t r i e s i tw a s n tu n t i lt h el a t e 19 8 0 sa n dt h ee a r l y19 9 0 st h a tt h er o u g hs e tt h e o r yg o tm o r ea n dm o r ew o r l d w i d e a t t e n t i o nb e c a u s eo fi t ss u c c e s s f u la p p l i c a t i o n st ot h ef i e l d so fp a t t e r nr e c o g n i t i o ni n m a c h i n el e a r n i n g ，k n o w l e d g ed i s c o v e r y , a n ds oo n i n19 91 ，z p a w l a kp u b l i s h e dh i sf i r s tm o n o g r a p ho nr o u g hs e tt h e o r y , r o u g hs e t ： t h e o r e t i c a l a s p e c t so fr e a s o n i n ga b o u td a t a1 4 1 i n t h i sm o n o g r a p hh ee x p a t i a t e d s y s t e m i c a l l ya n dc o m p l e t e l yo nr o u g hs e tt h e o r y , e s t a b l i s h e dt h er i g o r o u s b a s i c m a t h e m a t i c sf o rr o u g hs e tt h e o r y i nl9 9 2 ，p o l i s hs c h o l a rr s l o w i n s k ie d i t e da n a p p l i c a t i o nm o n o g r a p ho fr o u g hs e tt h e o r y , i n t e l l i g e n td e c i s i o ns u p p o r t ：h a n d b o o ko f a p p l i c a t i o n sa n da d v a n c e so ft h er o u g hs e t st h e o r y 【5 j i n19 9 5 c o m m u n i c a t i o n so ft h e a c m ( v o l 38n o 1 1 ) 巾jl i s t e dr o u g hs e tt h e o r yo nt h ee m e r g e n tr e s e a r c ht o p i c si n t h ef i e l do fa r t i f i c i a li n t e l l i g e n c ea n dc o g n i t i v es c i e n c e ，a n di s s u e dr o u g hs e tw r i t t e n b y p a w l a ke ta 1 i n19 9 8 ，t h ej o u r n a l ，i n f o r m a t i o ns c i e n c e s ，p u b l i s h e das p e c i a l e d i t i o no nt h es t u d yo fr o u g hs e tt h e o r y i n19 9 2 ，t h ef i r s ti n t e r n a t i o n a lw o r k s h o po nr o u g hs e t sw a sh e l di nk i e k r z ， p o l a n d f r o mt h e no n ，i ti sh e l de v e r yy e a r t h ef i f t hi n t e r n a t i o n a lw o r k s h o po n r o u g hs e t sh e l di nt o k y oj a p a ni n19 9 6 wa n dt h ew o r k s h o ph e l di nc h i n ai n2 0 0 3 p r o m o t e dt h es t u d yo fr o u g hs e tt h e o r ya n d i t sa p p l i c a t i o n si nt h ea r e ao fa s i aa sw e l l a si nc h i n a t h es t u d yo fr o u g hs e tt h e o r yi nc h i n ab e g a ni n19 9 4 i ti sm a i n l y c o n c e n t r a t e do nt h es t u d yo fi t sm a t h e m a t i cp r o p e r t i e se f f i c i e n ta l g o r i t h m ，a n d d y n a m i cc h a r a c t e r i s t i c s ，s u c h a sk n o w l e d g er e p r e s e n t a t i o n ，k n o w l e d g er e d u c t i o n a l g o r i t h ma n dr o u g hl o g i ce t c a tp r e s e n t ，m a n yi n s p i r i n ga c h i e v e m e n t sh a v eb e e n m a d ea n dm a n yv a l u a b l ew o r k sh a v eb e e np u b l i s h e d 【7 ，8 ，9 1 f r o m2 0 01 c h i n e s e r o u g hs e ta n ds o f tc o m p u t a t i o nw o r k s h o p ( c r s s c ) i sh e l de v e r yy e a r 2 1 3dis s e r t a t io no u ti t i e e v e nt h o u g hr o u g hs e t si sg e t t i n gk n o w nw h e r e v e rt h ew o r l dm a n yp e o p l el i k et o d e a lw i t h p r e c i s ea n dc e r t a i ni n f o r m a t i o n u n c e r t a i n i n f o r m a t i o nt h o u g hv e r y i m p o r t a n t ，p e o p l ed o n tu s ei ts u f f i c i e n t l y i nt h i st h e s i s ，t h eb a s i c so fr o u g hs e t sa r eo u t l i n e d b e s i d e st h em a i np r i n c i p a l so f r o u g hs e t s ，d i f f e r e n tm e t h o d so f a l li n f o r m a t i o ns y s t e ms t u d yb a s e do nr o u g hs e t sa r e g i v e na n dc o m p a r e d a s w ek n o w , i nm a n yk i n d so fd a t a b a s e s ，t h e r ee x i s t sas i t u a t i o nw h e r eav a l u eo f d a t ai sn u l la n dt h e nd e a l i n gw i t hi ti sab i gp r o b l e m t os o l v et h i sp r o b l e m ，i nt h i st h e s i st h ee q u i v a l e n c er e l a t i o no fr o u g hs e tt h e o r y i sr e p l a c e db ya na s y m m e t r i c a ls i m i l a rr e l a t i o n ，a n df r o mt h i sr e l a t i o n ，w eh a v e d e f i n e da na s y m m e t r i c a ls i m i l a rm a t r i xa n dg i v e na ni m p l i c a t i o n a le x a m p l e 1 4c o n ciu sio n m o s ta p p l i c a t i o n so fr o u g hs e t sa r es t i l li nr e s e a r c hp r o g r e s sb e c a u s eo ft e d i o u s c o l l e c t i o no fe x p e r i m e n t a ld a t aa n dd e v e l o p m e n to fn e ws o f t w a r e s 【1 0 ，ii , 1 2 ，1 3 i f i e l d s l i k em i l i t a r ya r en o w a d a y si n t e r e s t e di nb u i l d i n gr o b u s ta u t o m a t i ct a r g e tr e c o g n i t i o n ( a t r ) s y s t e m s t ob u i l dt h e s es y s t e m s ，t h e r ei sas e to fm e a s u r e do rs y n t h e t i cd a t a t h a tc a l lb eu s e df o rt r a i n i n ga n dt e s t i nt h ep a s t ，s t a t i s t i c a lp a t t e mr e c o g n i t i o nh a s b e e nu s e dt ob u i l da t rs y s t e m s h o w e v e r ，i ft h et r a i n i n gd a t ai sv i e w e da sa l l i n f o r m a t i o ns y s t e m ，t h e nt h ep r o c e d u r e sa n dm e t h o d so fd a t am i n i n gc a nb eu s e dt o f i n dt h ep r e v i o u s l yu n r e c o g n i z e dr e l a t i o n s h i p si nt h ed a t at h a tw i l lc o n v e r tt h ed a t at o i n f o m a t i o n 【3 2 3 3 , 3 4 ，3 5 1 a ni n f o r m a t i o ns y s t e mc a nb ec h a r a c t e r i z e da sar e l a t i o n a ld a t a b a s e ，w h e r et h e i n f o r m a t i o ni ss t o r e di nat a b l e e a c hr o wi nt h et a b l er e p r e s e n t sa ni n d i v i d u a lr e c o r d e a c h c o l u m nr e p r e s e n t ss o m ea na t t r i b u t eo ft h er e c o r d so raf i e l d t h ec o l u m n s c o u l d r e p r e s e n tw e i 曲to rh e i g h t ，o re v e ns o m em e a s u r e m e n to fat a r g e ts u c ha sh e i g h to r l e n g t h t h em a i np r o b l e m st h a tc a nb ea p p r o a c h e du s i n gr o u g hs e tt h e o r yi n c l u d e sd a t a r e d u c t i o n ( i e ，e l i m i n a t i o no fs u p e r f l u o u sd a t a ) ，d i s c o v e r yo fd a t ad e p e n d e n c i e s ， e s t i m a t i o no fd a t as i g n i f i c a n c e ，g e n e r a t i o no fd e c i s i o n ( c o n t r 0 1 ) a l g o r i t h m sf r o md a t a ， a p p r o x i m a t ec l a s s i f i c a t i o no fd a t a ，d i s c o v e r yo fs i m i l a r i t i e s o rd i f f e r e n c e si nd a t a ， 3 m a s t e rd e g r e et h e s i s c h a p t e rl i n t r o d u c t i o n d i s c o v e r yo f p a t t e r n si nd a t a a n dd i s c o v e r yo f c a u s e e f f e c tr e l a t i o n s h i p s 【1 4 1 5 ，1 6 1 e v e nt h o u g ht h er e s e a r c ho fk n o w l e d g er e d u c t i o ni nr o u g hs e t si sm o s t l yb a s e d o nc o m p l e t ei n f o r m a t i o ns y s t e m ，i ti sm e a n i n g f u lt oe x t e n dr o u g hs e tt h e o r yi n t o i n c o m p l e t ei n f o r m a t i o ns y s t e m s a n dd e s i g na ne f f i c i e n tk n o w l e d g er e d u c t i o n a l g o r i t h m t h ep r o p e rd e f i n i t i o n so fr e d u c t sa l l o wt od e f i n ek n o w l e d g er e d u c t i o nt h a td o e s n o td i m i n i s ht h eo r i g i n a ls y s t e m sa b i l i t i e st oc l a s s i f yo b j e c t so rt om a k ed e c i s i o n s u n l i k ec l a s s i c a li n f o r m a t i o ns y s t e m s ，a ni n c o m p l e t ei sa l l o w st oa c h i e v em u c hl e s s n u m b e ro fd e c i s i o nr u l e s ，w h i c hi si m p l i e db yt h ec h a r a c t e ro fat o l e r a n c es i m i l a r i t y r e l a t i o n 4 c h a p t e r2 b a sicc o n c e p t sa b o u tr o u g hs e t 2 1 in f o r m a tio ns y s t e m 2 1 1d e f i n i t i 0 1 3 r o u g hs e tt h e o r yh a sb e e nc o n c e i v e da s at o o lt oc o n c e p t u a l i z e ，o r g a n i z ea n d a n a l y z ev a r i o u st y p e so fd a t a ，i np a r t i c u l a r ，t od e a lw i t hi n e x a c t ，u n c e r t a i no rv a g u e k n o w l e d g ei na p p l i c a t i o n sr e l a t e dt oa r t i f i c i a li n t e l l i g e n c e r o u g hs e ta p p r o a c hc a nb ep r e s e n t e dt oi n c o m p l e t ei n f o r m a t i o ns y s t e m s ，i e t o s y s t e m si nw h i c ha t t r i b u t ev a l u e sf o ro b j e c t sm a y b eu n k n o w n ( m i s s i n g , n u l l ) a n dt h i s t h e o r y sm a i nc o n c e r nc a n b ed e v o t e dt of i n d i n gr u l e sf r o ms u c hs y s t e m s a t h e o r yo fr o u g hs e t s ( r s ) i n t r o d u c e db yz p a w l a kd e f i n e sf o r m a l l y a n i n f o r m a t i o ns y s t e ma sas y s t e m s = 似州w h e r eu i st h eu n i v e r s e ( af i n i t es e to f o b j e c t s ，u = x 1 x 2 ，x m ) a n da i st h es e to f a t t r i b u t e s ( f e a t u r e s ，a t t r i b u t e s ) e a c ha t t r i b u t ea a ( a t t r i b u t eab e l o n g i n gt ot h ec o n s i d e r e ds e to fa t t r i b u t e sa ) d e f i n e sa l li n f o r m a t i o nf u n c t i o nf a ? u 一+ 圪，w h e r e 圪i st h es e to f v a l u e so fa ，c a l l e d t h ed o m a i no fa t t r i b u t ea e x a m p l e 2 1 c o n s i d e rad a t as e tc o n t a i n i n gt h er e s u l t so ft h r e em e a s u r e m e n t sp e r f o r m e df o r 10o b j e c t s t h er e s u l t sc a nb eo r g a n i z e di nam a t r i x ( 10 x 3 ) m a s t e rd e g r e et h e s i s c h a p t e r2b a s i cc o n c e p t sa b o u tr o u g hs e t u s i n gt h et e r m i n o l o g yo ft h er o u g hs e t st h e o r y , t h i sd a t as e tc a l lb ec o n s i d e r e da s a ni n f o r m a t i o ns y s t e m s = u t a ) 。w h e r eu n i v e r s eua n da t t r i b u t e sac o r r e s p o n dt o t h es e to fo b j e c t sa n dt ot h es e to f v a r i a b l e s ，r e s p e c t i v e l y ： 泸i x l x 2 , x 3 , x 4 , x 3 , x i d a = a | a 2 , a 3 t h ed o m a i n so ft h ep a r t i c u l a ra t t r i b u t e sa r e y l - f j 2 。3 y 2 = 1 2 z 3 1 2 3 4 j i e t h ed o m a i no fe a c ha t t r i b u t ei st h es e to fv a l u e so ft h i sa t t r i b u t e t h e i n f o r m a t i o nf u n c t i o n f 口f o rt h i ss y s t e mi sp r e s e n t e di nt a b l e2 1 t a b l e2 - 1g r o u po fo b j e c t s 6 3 1 3 3 4 2 1 4 3 l l 2 1 2 1 1 2 1 l 2 2 3 2 2 1 1 3 1 2 3 m a s t e rd e g r e et h e s i s c h a p t e r2b a s i cc o n c e p t sa b o u tr o u g hs e t 2 1 2i n d is c e r n i b iii t yr e i a t i o n r o u g hs e t sh a v eb e e ne m p l o y e dt or e m o v er e d u n d a n tc o n d i t i o n a lf e a t u r e sf r o m d i s c r e t e - v a l u e dd a t as e t s ，w h i l er e t a i n i n gt h e i ri n f o r m a t i o nc o n t e n t f o re v e r ys e to fa t t r i b u t e sboa ，a i li n d i s c e m i b i l i t yr e l a t i o ni n d ( b ) i sd e f i n e di nt h e f o l l o w i n gw a y ： t w oo b j e c t sx fa n d 而，a r ei n d i s c e r n i b l eb yt