logo资料库

Rough Sets.pdf

第1页 / 共16页
第2页 / 共16页
第3页 / 共16页
第4页 / 共16页
第5页 / 共16页
第6页 / 共16页
第7页 / 共16页
第8页 / 共16页
资料共16页,剩余部分请下载后查看
I n t e r n a t i o n a l J o u r n a l o f C o m p u t e r a n d I n f o r m a t i o n S c i e n c e s , V o l . 1 1 , N o . 5 , 1 9 8 2 R o u g h S e t s Z d z i s t a w P a w l a k 1 R e c e i v e d J u n e 1 9 8 1 ; r e v i s e d S e m p t e m b e r 1 9 8 2 W e i n v e s t i g a t e i n t h i s p a p e r a p p r o x i m a t e o p e r a t i o n s o n s e t s , a p p r o x i m a t e e q u a l i t y o f s e t s , a n d a p p r o x i m a t e i n c l u s i o n o f s e t s . T h e p r e s e n t e d a p p r o a c h m a y b e c o n s i d e r e d a s a n a l t e r n a t i v e t o f u z z y s e t s t h e o r y a n d t o l e r a n c e t h e o r y . S o m e a p p l i c a t i o n s a r e o u t l i n e d . K E Y W O R D S : A r t i f i c i a l i n t e l l i g e n c e ; a u t o m a t i c c l a s s i f i c a t i o n ; c l u s t e r a n a l y s i s ; f u z z y s e t s ; i n d u c t i v e r e a s o n i n g ; l e a r n i n g a l g o r i t h m s ; m e a s u r e m e n t t h e o r y ; p a t t e r n r e c o g n i t i o n ; t o l e r a n c e t h e o r y . A p a r t f r o m t h e k n o w n a n d t h e u n k n o w n , w h a t e l s e i s t h e r e ? H a r o M P i n t e r ( T h e H o m e c o m i n g ) 1 . I N T R O D U C T I O N T h e a i m o f t h i s p a p e r i s t o d e s c r i b e s o m e p r o p e r t i e s o f r o u g h s e t s , i n t r o d u c e d i n R e f . 7 a n d i n v e s t i g a t e d i n R e f s . 1 , 2 , 4 , 5 , 6 , 8 , 9 , a n d 1 1 . T h e r o u g h s e t c o n c e p t c a n b e o f s o m e i m p o r t a n c e , p r i m a r i l y i n s o m e b r a n c h e s o f a r t i f i c i a l i n t e l l i g e n c e , s u c h a s i n d u c t i v e r e a s o n i n g , a u t o m a t i c c l a s s i f i c a t i o n , p a t t e r n r e c o g n i t i o n , l e a r n i n g a l g o r i t h m s , e t c . T h e i d e a o f a r o u g h s e t c o u l d b e p l a c e d i n a m o r e g e n e r a l s e t t i n g , l e a d i n g t o a f r u i t f u l f u r t h e r r e s e a r c h a n d a p p l i c a t i o n s i n c l a s s i f i c a t i o n t h e o r y , c l u s t e r a n a l y s i s , m e a s u r e m e n t t h e o r y , t a x o n o m y , e t c . T h e k e y t o t h e p r e s e n t e d a p p r o a c h i s p r o v i d e d b y t h e e x a c t m a t h e m a t i c a l f o r m u l a t i o n o f t h e c o n c e p t o f a p p r o x i m a t i v e ( r o u g h ) e q u a l i t y o f s e t s i n a g i v e n a p p r o x i m a t i o n s p a c e ; a n a p p r o x i m a t i o n s p a c e i s u n d e r s t o o d a s a p a i r ( U , R ) , w h e r e U i s a c e r t a i n s e t c a l l e d u n i v e r s e , a n d R c U X U i s a n i n d i s c e r n i b i l i t y r e l a t i o n . W e a s s u m e t h r o u g h o u t t h i s p a p e r t h a t R i s a n e q u i v a l e n c e r e l a t i o n . I n s t i t u t e o f C o m p u t e r S c i e n c e s , P o l i s h A c a d e m y o f S c i e n c e s , P . O . B o x 2 2 , 0 0 - 9 0 1 W a r s a w , P K i N . 3 4 1 0 0 9 1 - 7 0 3 6 / 8 2 / 1 0 0 0 - 0 3 4 1 5 0 3 . 0 0 / 0 9 1 9 8 2 P l e n u m P u b l i s h i n g C o r p o r a t i o n
3 4 2 P a w l a k S o m e i d e a s u n d e r l y i n g t h e t h e o r y o u t l i n e d h e r e a r e c o m m o n t o f u z z y s e t t h e o r y , ( 1 3 ) t o l e r a n c e t h e o r y , ( 1 4 ) n o n s t a n d a r d a n a l y s i s . ( 1 2 ) H o w e v e r , w e a r e p r i m a r i l y a i m i n g a t l a y i n g m a t h e m a t i c a l f o u n d a t i o n s f o r a r t i f i c i a l i n t e l l i g e n c e , a n d n o t a n e w s e t t h e o r y o r a n a l y s i s . S o m e a p p l i c a t i o n s o f t h e p r e s e n t e d i d e a s a r e g i v e n i n R e f s . 1 , 4 , 5 , 6 . T h e i d e a s g i v e n i n t h i s p a p e r h a v e b e e n i n s p i r e d b y t h e r e s u l t s o f M i c h a l s k i ( s e e R e f . 3 ) c o n c e r n i n g a u t o m a t i c c l a s s i f i c a t i o n . W e u s e t h r o u g h o u t t h i s p a p e r s t a n d a r d m a t h e m a t i c a l n o t a t i o n s , a n d w e a s s u m e t h a t t h e r e a d e r i s f a m i l i a r w i t h b a s i c s e t t h e o r e t i c a l a n d t o p o l o g i c a l n o t i o n s . T h a n k s a r e d u e t o P r o f . E . O d o w s k a a n d P r o f . W . M a r e k f o r f r u i t f u l d i s c u s s i o n s , a n d t o t h e r e v i e w e r f o r v a l u a b l e c o m m e n t s a n d r e m a r k s . 2 . A P P R O X I M A T I O N S P A C E ; A P P R O X I M A T I O N S 2 A . B a s i c N o t i o n s L e t U b e a c e r t a i n s e t c a l l e d t h e u n i v e r s e , a n d l e t R b e a n e q u i v a l e n c e r e l a t i o n o n U . T h e p a i r A = ( U , R ) w i l l b e c a l l e d a n a p p r o x i m a t i o n s p a c e . W e s h a l l c a l l R a n i n d i s e e r n i b i l i t y r e l a t i o n . I f x , y E U a n d ( x , y ) E R w e s a y t h a t x a n d y a r e i n d i s t i n g u i s h a b l e i n A . S u b s e t s o f U w i l l b e d e n o t e d b y X , Y , Z , p o s s i b l y w i t h i n d i c e s . T h e e m p t y s e t w i l l b e d e n o t e d b y 0 , a n d t h e u n i v e r s e U w i l l a l s o b e d e n o t e d b y 1 . E q u i v a l e n c e c l a s s e s o f t h e r e l a t i o n R w i l l b e c a l l e d e l e m e n t a r Y s e t s ( a t o m s ) i n A o r , b r i e f l y , e l e m e n t a r y s e t s . T h e s e t o f a l l a t o m s i n A w i l l b e d e n o t e d b y U / R . W e a s s u m e t h a t t h e e m p t y s e t i s a l s o e l e m e n t a r y i n e v e r y A . E v e r y f i n i t e u n i o n o f e l e m e n t a r y s e t s i n A w i l l b e c a l l e d a c o m p o s e d s e t i n A , o r i n s h o r t , a c o m p o s e d s e t . T h e f a m i l y o f a l l c o m p o s e d s e t s i n A w i l l b e d e n o t e d a s C o r n ( A ) . O b v i o u s l y C o m ( A ) i s a B o o l e a n a l g e b r a , i . e . , t h e f a m i l y o f a l l c o m p o s e d s e t i s c l o s e d u n d e r i n t e r s e c t i o n , u n i o n , a n d c o m p l e m e n t o f s e t s . L e t X b e a c e r t a i n s u b s e t o f U . T h e l e a s t c o m p o s e d s e t i n A c o n t a i n i n g X w i l l b e c a l l e d t h e b e s t u p p e r a p p r o x i m a t i o n o f X i n A , i n s y m b o l s A p r , ( X ) ; t h e g r e a t e s t c o m p o s e d s e t i n A c o n t a i n e d i n X w i l l b e c a l l e d t h e b e s t l o w e r a p p r o x i m a t i o n o f X i n A , i n s y m b o l s A p r A ( x ) . I f A i s k n o w n , i n s t e a d o f A p r A ( X ) ( A p r , ( X ) ) w e s h a l l w r i t e A p r ( X ) ( a p r ( X ) ) . T h e s e t B n d A ( X ) = A p r A ( X ) - - A p r A ( X ) ( i n s h o r t B n d ( X ) ) w i l l b e c a l l e d t h e b o u n d a r y o f X i n A .
R o u g h S e t s 3 4 3 ( \ " ' I \ \ / F i g . 1 X S e t s E d g ~ ( X ) = X - A p r A ( X ) ( i n s h o r t E d g ( X ) ) a n d E d g A ( X ) = A p r A ( X ) - - X , ( i n s h o r t E d g ( X ) ) a r e r e f e r r e d t o a s a n i n t e r n a l a n d a n e x t e r n a l e d g e o f X i n A , r e s p e c t i v e l y . O f c o u r s e B n d A ( X ) = E d g A ( X ) U E d g A ( X ) . F i g . 1 s h o w s t h e n o t i o n o f a n u p p e r a n d l o w e r a p p r o x i m a t i o n i n a t w o - d i m e n s i o n a l a p p r o x i m a t i o n s p a c e c o n s i s t i n g o f a r e c t a n g l e p a r t i t i o n e d i n t o e l e m e n t a r y s q u a r e s . L e t u s d e f i n e t w o m e m b e r s h i p f u n c t i o n s - - ~ A , ~ ( c a l l e d s t r o n g a n d w e a k m e m b e r s h i p , r e s p e c t i v e l y ) , a s f o l l o w s : x _ C A X i f f x ~ A p r ~ ( X ) x ~ A X i f f x ~ A p r A ( X ) I f x - ~ A X , w e s a y t h a t " X s u r e l y b e l o n g s t o X i n A , " w h i l e x ~ A X i s t o m e a n t h a t " X p o s s i b l y b e l o n g s t o X i n A . " T h u s w e c a n i n t e r p r e t e a p p r o x i m a t i o n s a s c o u n t e r p a r t s o f n e c e s s i t y a n d p o s s i b i l i t y i n m o d a l l o g i c . O f c o u r s e , A p r 4 ( X ) = { x : x C A X } A p r A ( X ) = { x : x ~ A X } T h u s w e c a n d e v e l o p o u r t h e o r y i n t e r m s o f s t r o n g a n d w e a k m e m b e r s h i p f u n c t i o n s o r i n t e r m s o f a p p r o x i m a t i o n s . F o r t h e s a k e o f s i m p l i c i t y w e s h a l l u s e h e r e t h e a p p r o x i m a t i o n a l a p p r o a c h . 2 . 2 . A p p r o x i m a t i o n S p a c e a n d T o p o l o g i c a l S p a c e I t i s e a s y t o c h e c k t h a t t h e a p p r o x i m a t i o n s p a c e A = ( U , R ) d e f i n e s u n i q u e l y t h e t o p o l o g i c a l s p a c e T ( A ) ( i n s h o r t T A ) , w h e r e T A = ( U , C o r n ( A ) ) , a n d C o m ( A ) a r e t h e f a m i l y o f a l l o p e n s e t s i n T A , a n d U / R i s a b a s e f o r T A . I t f o l l o w s f r o m t h e d e f i n i t i o n o f ( l o w e r a n d u p p e r ) a p p r o x i m a t i o n s t h a t C o r n ( A ) i s b o t h t h e s e t o f a l l o p e n a n d c l o s e d s e t s i n T A . T h u s , A p L 4 ( X ) a n d
3 4 4 P a w l a k A p r A ( X ) c a n b e i n t e r p r e t e d a s a n i n t e r i o r a n d c l o s u r e o f t h e s e t X i n t h e t o p o l o g i c a l s p a c e T A , r e s p e c t i v e l y . I f A p r A ( X ) = A p r A ( X ) f o r e v e r y X c U , t h e n A = ( U , R ) w i l l b e c a l l e d a d i s c r e t e a p p r o x i m a t i o n s p a c e . O n e c a n e a s i l y c h e c k t h a t i f A i s a d i s c r e t e a p p r o x i m a t i o n s p a c e , t h e n a l l a t o m s i n A a r e u n i t y s e t s . O f c o u r s e a d i s c r e t e a p p r o x i m a t i o n s p a c e A g e n e r a t e s t h e d i s c r e t e t o p o l o g i c a l s p a c e T ~ . 2 . 3 . P r o p e r t i e s o f A p p r o x i m a t i o n s I t f o l l o w s f r o m t h e t o p o l o g i c a l o p e r a t i o n s t h a t f o r e v e r y X , Y c U a n d e v e r y A = ( U , R ) t h e f o l l o w i n g p r o p e r t i e s h o l d : A p r ( X ) ~ X D A p r ( X ) A p t ( l ) = A p t ( l ) = 1 A p r ( 0 ) = A p r ( 0 ) = 0 A p r ( A p r ( X ) ) = A p r ( A p r ( X ) ) = A p r ( X ) A p r ( A p r ( X ) ) = A p r ( A p r ( X ) ) = A p r ( X ) A p r ( X U Y ) = A p r ( X ) U A p r ( Y ) A p r ( X C 3 Y ) = A p t ( X ) N A p r ( Y ) A p r ( X ) = - - A p r ( - - X ) n p r ( X ) = - - A p r ( - - X ) w h e r e - X i s a n a b b r e v i a t i o n f o r U - X . M o r e o v e r w e h a v e A p r ( X N Y ) c A p r ( X ) V 3 A p r ( Y ) A p r ( X U I 1 ) D A p r ( X ) U A p r ( Y ) A p r ( X - I 1 ) D A p r ( X ) - A p t ( Y ) T h e f o l l o w i n g i m a t i o n s : i n t e r p r e t a t i o n o f t h e a p p r o x i m a t i o n a p p r o x i m a t i o n s p a c e ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) ( 8 ) ( 9 ) ( 1 0 ) ( 1 1 ) ( 1 2 ) A p r ( X - - Y ) c A p r ( X ) - A p r ( Y ) ( 1 3 ) a r e c o u n t e r p a r t s o f t h e l a w X U - X = 1 f o r a p p r o x - A p r ( X ) U A p r ( - - X ) = 1 A p r ( X ) U A p r ( - - X ) = 1 ( 1 4 ) ( 1 5 )
R o u g h S e t s 3 4 5 A p r ( X ) U A p r ( - X ) = 1 ( 1 6 ) A p r ( X ) U A p r ( - X ) = - B n d ( X ) ( 1 7 ) T h e l a w X N - - X = 0 h a s t h e f o l l o w i n g a n a l o g u e s f o r a p p r o x i m a t i o n s : A p r ( X ) n a p r ( - X ) = 0 ( 1 8 ) a p r ( X ) N A p r ( - - X ) = B n d ( X ) ( 1 9 ) A p r ( X ) N a p r ( - X ) = 0 ( 2 0 ) A p r ( X ) n A p r ( - - X ) = 0 ( 2 1 ) D e M o r g a n ' s l a w s h a v e t h e f o l l o w i n g c o u n t e r p a r t s : - ( A p t ( X ) U A p r ( Y ) ) = A p r ( - X ) N a p r ( - - Y ) ( 2 2 ) - - ( A p r ( X ) U a p r ( Y ) ) = A p r ( X ) n a p r ( Y ) ( 2 3 ) - ( A p r ( X ) U a p r ( Y ) ) = A p r ( - X ) N a p r ( - Y ) ( 2 4 ) - - ( A p r ( X ) U A p r ( Y ) ) = A p r ( - X ) N a p r ( - - Y ) ( 2 5 ) - ( A p r ( X ) N A p r ( Y ) ) = A p r ( - X ) U A p r ( - Y ) ( 2 6 ) - - ( A p r ( X ) N A p r ( Y ) ) = A p r ( - X ) U A p r ( - - Y ) ( 2 7 ) - - ( A p r ( X ) N A p r ( Y ) ) = A p r ( - - X ) U A p r ( - - Y ) ( 2 8 ) - ( A p r ( X ) N A p r ( X ) ) = A p r ( - X ) U A p r ( - Y ) ( 2 9 ) M o r e o v e r w e h a v e I f X c 1 7 . , t h e n A p r ( X ) c A p r ( Y ) a n d A p t ( X ) c A p r ( Y ) ( 3 0 ) N o t e t h a t X = A p r A ( X ) a n d X = A p r A ( X ) i f f X i s a c o m p o s e d s e t i n A . 2 . 4 . A c c u r a c y o f a n A p p r o x i m a t i o n I n o r d e r t o e x p r e s s t h e " q u a l i t y " o f a n a p p r o x i m a t i o n w e i n t r o d u c e s o m e a c c u r a c y m e a s u r e . L e t A = ( U , R ) b e a n a p p r o x i m a t i o n s p a c e , a n d l e t X c U . B y _ # A ( X ) ( / 2 A ( X ) ) w e d e n o t e t h e n u m b e r o f a t o m s i n A p r , ( X ) ( A p r A ( X ) ) , a n d w e c a l l ( A ( X ) ( ~ T A ( X ) ) t h e i n t e r n a l ( e x t e r n a l ) m e a s u r e o f Y i n A . I f # _ A ( X ) = ~ A ( X ) w e s a y t h a t X i s m e a s u r a b l e i n A . T h u s t h e s e t X i s m e a s u r a b l e i n A i f a n d o n l y i f X i s a c o m p o s e d s e t i n A .
3 4 6 P a w l a k L e t A = ( U , R ) b e a n a p p r o x i m a t i o n s p a c e a n d l e t X c U . B y t h e a c c u r a c y o f a p p r o x i m a t i o n o f X i n A w e m e a n t h e n u m b e r i " / A ( X ) = ~ A ( X ) w h e r e f i A ( X ) r 0 g . ( x ) ' O b v i o u s l y , 0 ~ t I A ( X ) ~ < 1 f o r a n y a p p r o x i m a t i o n s p a c e A = ( U , R ) a n d a n y X c U . F o r a n y m e a s u r a b l e s e t X i n A , t l A ( X ) - - 1 . I f X i s n o t m e a s u r a b l e i n A , t h e n 0 ~ q A ( X ) < 1 . I n p a r t i c u l a r r l A ( X ) = 0 , i f f A p r 4 ( X ) = 0 . F o r a n y s e t X i n a d i s c r e t e a p p r o x i m a t i o n s p a c e A = ( U , R ) , t l A ( X ) - ~ 1 a n d t h i s i s t h e g r e a t e s t p o s s i b l e a c c u r a c y . 2 . 5 . E x a m p l e s I n t h i s p a r a g r a p h w e i l l u s t r a t e t h e n o t i o n s i n t r o d u c e d p r e v i o u s l y w i t h s i m p l e e x a m p l e s . E x a m p l e 1 . L e t R + b e t h e s e t o f n o n n e g a t i v e r e a l n u m b e r s , a n d l e t S b e t h e i n d i s c e r n i b i l i t y r e l a t i o n o n R § d e f i n e d b y t h e f o l l o w i n g p a r t i t i o n : ( 0 , 1 ) , ( 1 , 2 ) , ( 3 , 3 ) . . . . w h e r e ( i , i + 1 ) , i = 0 , 1 , 2 . . . . d e n o t e s a h a l f - o p e n e d i n t e r v a l . T h e c o r r e s p o n d i n g a p p r o x i m a t i o n s p a c e w i l l b e d e n o t e d a s A = ( R + , S ) . L e t u s c o n s i d e r a p p r o x i m a t i o n s o f a n o p e n i n t e r v a l ( 0 , r ) , w h e r e n ~ < r n + 1 f o r a c e r t a i n n ~ > 0 . B y d e f i n i t i o n w e h a v e t / - - I A p r 0 , r ) = U ( i , i + 1 ) - - ( 0 , n ) , f o r n > / 1 , a n d 0 f o r n = 0 i = 0 A p r ( 0 , r ) = G ( i , i + l ) = ( 0 , n + 1 ) i = o T h e i n t e r n a l a n d e x t e r n a l m e a s u r e s o f ( 0 , r ) i n A a r e _ ~ ( 0 , r ) = n f i ( O , r ) = n + 1 a n d t h e a c c u r a c y o f ( 0 , r ) i n A i s n r ) - n + l
R o u g h S e t s 3 4 7 T h u s , w e c a n i n t e r p r e t t h e a p p r o x i m a t i o n s p a c e A = ( R + , S ) a s a m e a s u r e m e n t s y s t e m , w h e r e f i A ( i , i + 1 } = ~ A ( i , i + 1 } = 1 , i = 0 , 1 , . . . i s t h e u n i t o f m e a s u r e m e n t i n A , a n d r / ( 0 , r ) i s t h e a c c u r a c y o f ( 0 , r ) i n A . F o r m o r e d e t a i l s e e R e f . 6 . E x a m p l e 2 . L e t V b e a f i n i t e s e t c a l l e d a v o c a b u l a r y a n d l e t V * b e t h e s e t o f a l l f i n i t e s e q u e n c e s o v e r V . A n y s u b s e t o f V * w i l l b e c a l l e d a l a n g u a g e o v e r V . L e t R ~ V * X V * b e a n i n d i s e e r n i b i l i t y r e l a t i o n , a n d l e t A = ( V * , R ) b e a n a p p r o x i m a t i o n s p a c e d e f i n e d b y V * a n d R . A l a n g u a g e L c V * i s r e c o g n i z a b l e i n A i f A p r A ( L ) = A p r A ( L ) . T h e f a m i l y o f a l l r e c o g n i z a b l e l a n g u a g e s i n A , d e n o t e d a s R e c ( A ) , i s t h e t o p o l o g y i n d u c e d b y A = ( V * , R ) a n d t h e b a s e o f t h e t o p o l o g y i s V * / R . T h a t i s t o s a y t h a t i f t h e l a n g u a g e L i s n o t r e c o g n i z a b l e i n A w e a r e a b l e t o r e c o g n i z e o n l y t h e l o w e r a n d u p p e r a p p r o x i m a t i o n s i n A . T h i s p r o p e r t y c a n b e u s e d i n s p e a c h r e c o g n i t i o n , p a t t e r n r e c o g n i t i o n , f a u l t t o l e r a n t c o m p u t e r s , e t c . E x a m p l e 3 . L e t S = ( X , A , V , p ) b e a n i n f o r m a t i o n s y s t e m ( s e e R e f . 1 0 ) , w h e r e X i s t h e s e t o f o b j e c t s A i s t h e s e t o f a t t r i b u t e s V = U v a , v a i s t h e s e t o f v a l u e s o f a t t r i b u t e a C A p : X X A ~ V i s a n i n f o r m a t i o n f u n c t i o n , P x : A ~ V x C X i s c a l l e d a n i n f o r m a t i o n a b o u t x i n S , w h e r e p x ( a ) = p ( x , a ) f o r e v e r y x ~ X a n d a E A . W e d e f i n e t h e b i n a r y r e l a t i o n S o v e r X i n t h e f o l l o w i n g w a y : X ~ s y i f f P x = P y O b v i o u s l y S i s a n e q u i v a l e n c e r e l a t i o n a n d A = ( X , S ) i s t h e a p p r o x - i m a t i o n s p a c e i n d u c e d b y t h e i n f o r m a t i o n s y s t e m S . A n y s u b s e t Y c X i s c a l l e d d e s c r i b a b l e i n S i f f A p r 4 ( Y ) = A p r A ( Y ) . T h e s e t o f a l l d e s c r i b a b l e s e t s i n S , d e n o t e d a s D e s ( S ) , i s a t o p o l o g y i n d u c e d b y S o n X , a n d t h e b a s e o f t h e t o p o l o g y i s X / S .
3 4 8 P a w l a k T h a t i s t o m e a n t h a t i f w e c l a s s i f y s o m e o b j e c t s a c c o r d i n g t o s o m e a t t r i b u t e s , i n a g e n e r a l c a s e w e a r e u n a b l e t o d e f i n e a n a r b i t r a r y s u b s e t o f o b j e c t s b y t h e s e a t t r i b u t e s ; o n l y t h o s e s u b s e t s w h i c h a r e d e s c r i b a b l e i n S , c a n b e d e f i n e d b y m e a n s o f t h e a t t r i b u t e s o f t h e s y s t e m S . T h i s p r o p e r t y m u s t b e t a k e n i n t o c o n s i d e r a t i o n , i n a n y c l a s s i f i c a t i o n s y s t e m i n w h i c h o b j e c t s a r e c l a s s i f i e d b y m e a n s o f a t t r i b u t e s . 3 . R O U G H E Q U A L I T Y O F S E T S B a s i c D e f i n i t i o n s L e t A = ( U , R ) b e a n a p p r o x i m a t i o n s p a c e a n d l e t X , Y c U . W e s a y 3 . 1 . t h a t ( a ) ( b ) ( c ) T h e s e t s X , Y a r e r o u g h l y b o t t o m - e q u a l i n A , i n s y m b o l s X ~ A Y , i f f A p r . ( X ) = a p r A ( Y ) . T h e s e t s X , Y a r e r o u g h l y t o p - e q u a l i n A , i n s y m b o l s X ~ A Y , i f f A p r A ( X ) = A p r A ( Y ) . T h e s e t s X , Y a r e r o u g h l y e q u a l i n A , i n s y m b o l s X ~ A Y , i f f X ~ A Y a n d X - - - A Y - I t i s e a s y t o c h e c k t h a t ~ - ~ ~ a r e e q u i v a l e n c e r e l a t i o n s o n P ( U ) . A ~ A ~ A ( P ( U ) d e n o t e s t h e p o w e r s e t o f U . ) I n w h a t f o l l o w s w e s h a l l o m i t t h e s u b s c r i p t A i f t h e a p p r o x i m a t i o n s p a c e A i s u n d e r s t o o d - - a n d w r i t e ~ , ~ - , ~ , i n s t e a d o f i f , i f , A " 3 . 2 . P r o p e r t i e s o f R o u g h E q u a l i t y F o r a n y a p p r o x i m a t i o n s p a c e A = ( U , R ) f o l l o w i n g p r o p e r t i e s a r e t r u e : I f X ~ Y , t h e n I f X ~ - Y , t h e n I f X ~ X ' a n d I f X ~ X ' a n d a n d a n y X , Y c U t h e X A Y ~ X ~ Y X U Y ~ _ X ~ - Y Y - ~ Y ' , t h e n X U Y ~ X ' U Y ' Y ~ Y ' , t h e n X n Y ~ X ' N Y ' I f X ~ Y , t h e n X - Y ~ 0 X - Y ~ O i f f X = Y I f X ~ Y , t h e n - ( - - X ) ~ Y I f X ~ - - Y , t h e n - ( - - X ) ~ Y ( 3 1 ) ( 3 2 ) ( 3 3 ) ( 3 4 ) ( 3 5 ) ( 3 6 ) ( 3 7 ) ( 3 8 )
分享到:
收藏