T E L KO M NIK A In d o n e s i a n  J o u r n a l o f   E le c t r ic a E n g in e e r in g V o l . 1 2 , No .  9 S e p te m b e r  2 0 1 4 , p p . 6 9 0 3 ~ 6 9 0 8 DO I: 1 0 . 1 1 5 9 1 /t e l k o m n i k a .v 1 2 i 9 . 6 2 6 4 6 9 0 3 Re c e i v e d No v e m b e r   2 4 2 0 1 3 ; R e v i s e d M a y 2 0 , 2 0 1 4 ;   A c c e p te d J u n e 1 0 ,  2 0 1 4 A   B isec t io n  M et h o d   f o r  I n f o r m a t io n  S y s t e m  K n o w led g e Red u ct io n Z h i Hu ila i Sc h o o l   o f   C o m p u t e S c i e n c e   a n d   T e c h n o l o g y ,   H e n a n   P o l y t e c h n i c   U n i v e rs i t y , J i a o z u o   H e n a n   P. R . C h i n a , E - m a i l : z h i h u i l a i @ 1 2 6 . c o m Ab s t r a c t I n   ro u g h   s e t   t h e o ry ,   a t t ri b u t e   r e d u c t i o n   a i m s   t o   re t a i n   t h e   d i s c e rn a b i l i t y   o f   t h e   o ri g i n a l   a t t r i b u t e   s e t , a n d m a n y   a t t r i b u t e   re d u c t i o n   a l g o r i t h m s   h a v e   b e e n   p ro p o s e d   i n   l i t e ra t u r e s .   H o w e v e r ,   t h e s e   m e t h o d s   a r e c o m p u t a t i o n a l l y t i m e - c o n s u m i n g   f o l a rg e   s c a l e   d a t a s e t s .   W e   d e v e l o p   a   b i s e c t i o n   m e t h o d   f o a t t ri b u t e re d u c t i o n   a n d   t h e   m a i n   o p i n i o n   i s   t o   p a rt i t i o n   t h e   u n i v e r s e   i n t o   s m a l l e r   o n e s b y   u s i n g p a rt i t i o n   c o re a t t ri b u t e s t o   re d u c e   t h e   c o m p l e x i t y .   Ex p e ri m e n t s   a n d   a n a l y s i s   s h o w   t h a t ,   c o m p a re d   w i t h   t h e   t ra d i t i o n a l   u n - b i s e c t i o n   re d u c t i o n   a l g o ri t h m ,   t h e   d e v e l o p e d   b i s e c t i o n   a l g o ri t h m   c a n   s i g n i f i c a n t l y   re d u c e   c o m p u t a t i o n a l t i m e   w h i l e   m a i n t a i n i n g   t h e i r   re s u l t s a s s a m e   a s   b e f o re . K e y w o r d s : i n f o rm a t i o n   s y s t e m , k n o w l e d g e r e d u c t i o n , b i s e c t i o n   m e t h o d C o p y r i g h t © 2 0 1 4 I n s ti tu t e   o f   A d v a n c e d   En g i n e e r i n g   a n d   Sc i e n c e .   A l l   r i g h t s   r e s e r v e d . 1 . In t r o d u c t io n In   a p p l i c a ti o n s   s u c h   a s   i m a g e   p r o c e s s i n g b i o i n f o r m a ti c s a s tr o n o m y f i n a n c e th e n u m b e r   o o b j e c ts   i s   v e r y   l a r g e   a n d   th e   d i m e n s i o n ( th e   n u m b e r   o a ttr i b u te s )   i s   v e r y   h i g h   a s   w e l l [1 - 2 ].  A t tr i b u te s   i r r e l e v a n to   r e c o g n i ti o n   ta s k s   m a y   d e te r i o r a te   t h e   p e r f o r m a n c e   o f   l e a r n i n g a l g o r i th m s   [3 ].  F e a tu r e   s e l e c ti o n   p l a y s   a n   i m p o r ta n r o l e   i n   th e   p r e p r o c e s s i n g   s te p   i n   th e s e a p p l i c a t i o n s .   It  p r o v i d e s   te c h n i q u e s   t o   r e d u c e   k n o w l e d g e   i n   d a ta b a s e ,   b y   w h i c h   t h e   i r r e l e v a n t   o r s u p e r f l u o u s   k n o wl e d g e   ( a t tr i b u t e s )   c a n   b e   e l i m i n a te d   a c c o r d i n g   to   th e   l e a r n i n g   ta s k   w i th o u t l o s i n g   e s s e n ti a l   i n f o r m a ti o n   a b o u t h e   o r i g i n a l   d a t a   i n   th e   d a ta b a s e s I n   i n f o r m a ti o n   s y s t e m i n c o n tr a s to   th e   f e a tu r e   s e l e c ti o n   wh i c h   u s u a l l y   k e e p s   u s e f u l   k n o w l e d g e a ttr i b u te   r e d u c ti o n   i s p r o c e s s   o f   g e r i d   o f   i r r e l e v a n o r   s u p e r f l u o u s   k n o wl e d g e T o   th i s   e x te n t,    a ttr i b u te   r e d u c ti o n   a n d f e a tu r e  s e l e c t i o n  a r e  t h e  f a c e ts  o f  a  s a m e  p r o b l e m . F e a tu r e   s e l e c ti o n   c a n   b e   d i v i d e d   i n to   t w o   m a i n   c a te g o r i e s d i s ta n c e - b a s e d   a n d c o n s i s te n c y - b a s e d   [3 ].   F o r   c o n s i s te n c y - b a s e d   f e a tu r e   s e l e c ti o n a ttr i b u t e   r e d u c ti o n   i s   r e g a r d e d a s   a   s p e c i a l   f o r m   o f   f e a tu r e   s e l e c ti o n   i n   r o u g h   s e t h e o r y   a n d   o f f e r s   a   s y s te m a ti c th e o r e ti c f r a m e w o r k w h i c h   d o e s   n o t   a tte m p to   m a x i m i z e   t h e   c l a s s   s e p a r a b i l i t y   b u t   r a th e r   to   r e t a i n   t h e d i s c e r n i b l e  a b i l i t y  o f  o r i g i n a l  a ttr i b u te  s e ts  f o r  th e  o b j e c ts  f r o m  th e  u n i v e r s e  [4 - 6 ]. In   th e   l a s t wo   d e c a d e s m a n y   r e d u c t i o n   a l g o r i th m s   h a v e   b e e n   p r o p o s e d   a n d   c a n   b e d i v i d e d   i n t o   t wo   t y p e s f i n d i n g   a l l   r e d u c ts   ( o r   a n   o p ti m a l   r e d u c t )   a n d   f i n d i n g   o n e   r e d u c t [ 7 ].  T h e we l l   k n o w n   a l g o r i th m   w h i c h   c a n   f i n d   a l l   r e d u c ts   i s   u s i n g   a   d i s c e r n i b i l i t y   m a tr i x   a n d   p r o p o s e d   b y S k o w r o n [8 - 9 ].   Ho we v e r n e a r l y   1 0   y e a r s   b e f o r e     i h a s   b e e n   p r o v e d   to   b e   a n   N P - h a r d   p r o b l e m to   f i n d   a l l   r e d u c ts   [1 0 ].  He u r i s ti c   k n o w l e d g e [1 1 ],  v a r i o u s   t y p e   o f   i n f o r m a ti o n   e n t r o p i e s [1 2 - 1 4 ] a r e  u s e d   i n   o r d e r  t o  r e d u c e  i ts  c o m p l e x i t y . A l t h o u g h   e n d l e s s   e f f o r ts   h a s   b e e n   m a d e th e   q u e s t i o n   w h e th e r   t h e r e   i s   a   r o o m   f o r f u r th e r  i m p r o v e m e n t s ti l l   p l a g u e s   u s . F o r tu n a t e l y b i s e c ti o n   m e th o d w h i c h   i s   i g n o r e d   a n d s e l d o m m e n ti o n e d   i n   t h i s   p r o b l e m b e f o r e b r i n g s   h o p e   to   u s In c o m p u te r   s c i e n c e   b i s e c ti o n   m e th o d   i s   s u c c e s s f u l l y   u s e d   i n s e a r c h i n g   a   f i n i te   s o r t e d   a r r a y [1 5 ],  wh i c h   i s   c a l l e d   a b i n a r y   s e a r c h o r h a l f - i n te r v a l   s e a r c h A b i n a r y   s e a r c h   i s   a d i c h o to m y d i v i d e   a n d   c o n q u e r s e a r c h   a l g o r i th m   a n d   h a l v e s   th e n u m b e r   o f i te m s   to   c h e c k   w i t h   e a c h   i te r a ti o n s o   l o c a ti n g   a n   i te m   o r   d e te r m i n i n g   i ts   a b s e n c e ta k e s l o g a r i t h m i c   ti m e T h e r e f o r e i n   th i s   p a p e r   we   wi l l   u s e   t h i s   p r o m i s i n g   m e th o d   i n   i n f o r m a ti o n s y s t e m  a ttr i b u te  r e d u c t i o n . Evaluation Warning : The document was created with Spire.PDF for Python.
IS S N: 2 3 0 2 - 4 0 4 6 T E L KO M NIK A V o l 1 2 , No . 9 S e p t e m b e r  2 0 1 4 : 6 9 0 3 6 9 0 8 6 9 0 4 T h e   r e s o f   s tu d y   i s   o r g a n i z e d   a s   f o l l o w s R e l a ti v e   b a s i c   c o n c e p i s   i n   S e c t i o n   2 In S e c ti o n   3 we   d e v e l o p   a   b i s e c ti o n   m e th o d   f o r   a ttr i b u t e   r e d u c t i o n I n   S e c t i o n   4 a l g o r i t h m a n a l y s i s   a n d   e x p e r i m e n ts   a r e   c a r r i e d   o u t   to   v e r i f y   i ts   e f f i c i e n c y T h e n c o n c l u s i o n   c o m e   i n S e c ti o n  5 . 2 . P r e lim in a r i e s A n   i n f o r m a ti o n   s y s te m a s   a   b a s i c   c o n c e p i n   r o u g h   s e th e o r y [1 6 - 1 7 ] p r o v i d e s   a c o n v e n i e n f r a m e w o r k   f o r   t h e   r e p r e s e n ta ti o n   o f   o b j e c ts   i n   t e r m s   o f   th e i r   a t tr i b u t e   v a l u e s . T h e f o l l o wi n g   d e f i n i ti o n s   f r o m  D e f n i ti o n  1   to  D e f i n i t i o n  5   o r i g i n a te d  f r o m  [5 - 7 ]. De f i n i t i o n   1 A n   i n f o r m a ti o n   s y s t e m   i s   a   q u a d r u p l e ( , , , ) S U A V f wh e r e U i s   a   f i n i t e n o n e m p t y   s e o f   o b j e c ts   a n d   i s   c a l l e d   t h e   u n i v e r s e   a n d A i s   a   f i n i t e   n o n e m p t y   s e o f   a ttr i b u t e s , a A a V V wi th a V b e i n g   th e   d o m a i n   o f a a n d : f U A V i s   a n   i n f o r m a ti o n   f u n c ti o n   wi t h ( , ) a f x a V f o r  e a c h a A a n d x U . T h e  s y s te m S c a n  o f te n   b e  s i m p l i f i e d  a s ( , ) S U A . De f i n i t i o n   2 L e t ( , ) S U A b e   a n   i n f o r m a ti o n   s y s te m   a n d   e a c h   n o n e m p t y   s u b s e t B A , 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  i s  d e f i n e d  a s : { ( , ) | ( , ) ( , ) , } B R x y U U f x a f y a a B . It  i s   e a s i l y   t o   p r o v e   th a i s B R a   e q u i v a l e n c e   r e l a t i o n a n d   i p a r t i ti o n s U i n to   s o m e e q u i v a l e n c e   c l a s s e s   g i v e n   b y / {[ ] | } B B U R x x U wh e r e [ ] B x d e n o te s   th e   e q u i v a l e n c e c l a s s  d e te r m i n e d  b y x wi t h  r e s p e c t to B , i .e . , {[ | ( , ] } [ ) B B x U R y x y . P r o p o s i ti o n   1 L e t ( , ) S U A b e   a n   i n f o r m a ti o n   s y s te m   a n d   a n   n o n e m p t y   s u b s e t B A . If | | B k , th e n | / | 2 k B U R , i n c l u d i n g  e m p t y   e q u i v a l e n c e  c l a s s e s . De f i n i t i o n   3 L e t ( , ) S U A b e   a n   i n f o r m a ti o n   s y s te m   a n d B A T h e n , B i s   d e f i n e d a s   th e   p a r t i ti o n   c o n s i s te n t   s e o f S i f B A R R M o r e o v e r , B i s   d e f i n e d   a s   t h e   p a r t i ti o n r e d u c ti o n  s e o f S i f  a n y   p r o p e r  s u b s e t o f B i s  n o t a  p a r t i ti o n  c o n s i s t e n t s e t  o f S . De f i n i t i o n   4 L e t ( , ) S U A b e   a n   i n f o r m a ti o n   s y s te m T h e n p a r ti ti o n   d i s c e r n i b i l i t y   s e o f [ ] i A x a n d [ ] j A x i s  d e f i n e d   a s : ( [ ] , [ ] ) { | ( ) ( ) } i A j A l l i l j D x x a A f x f x . De f i n i t i o n   5 L e t ( , ) S U A b e   a n   i n f o r m a ti o n   s y s te m   a n d { | ( ) } k k r B b e   a l l   th e p a r ti t i o n   r e d u c t i o n   s e ts   o f S a n d k r k C B , k r k B C K , k r k I A B T h e n   a n y e l e m e n o f C i s   c a l l e d   a   p a r t i ti o n   c o r e   a ttr i b u t e a n d C i s   c a l l e d   p a r ti t i o n   c o r e   s e t;  a n y   e l e m e n t o f K i s   c a l l e d   a   p a r ti t i o n   n e c e s s a r y   a ttr i b u te a n d K i s   c a l l e d   p a r ti t i o n   n e c e s s a r y   a ttr i b u te   s e t; a n y   e l e m e n o f I i s   c a l l e d   a   p a r ti t i o n   u n n e c e s s a r y   a ttr i b u te a n d I i s   c a l l e d   p a r ti t i o n u n n e c e s s a r y  a ttr i b u t e  s e t. 3 A B i s e c t io n A p p r o a c h  f o r I n f o r m a t io n S y s t e m Kn o w le d g e R e d u c t io n De f i n i t i o n   6 L e t 1 2 , { , } , n F F F b e   a   s e t   f a m i l y T h e n s e t H i s   c a l l e d   a   m i n i m a l c o v e r   o f i f F i , H F i a n d S H , F i , S F i M o r e o v e r , | {             } M c H H is a m in im a l c o v e r o f i s  c a l l e d   th e  m i n i m a l  c o v e r  f a m i l y  o f . F o r   e x a m p l e , { { , , } , { , } , { , } } a b c a b b c a c c o r d i n g   t o D e f i n i t i o n   6 , { , } a c i s   a   m i n i m a l c o v e r  o f , a n d { } b i s  a l s o  a  m i n i m a l  c o v e r  o f . T h e o r e m   1 L e t 1 2 , { , } , n F F F . , i j F F i f i j F F th e n ( ) ( ) j M c M c F . Evaluation Warning : The document was created with Spire.PDF for Python.
T E L KO M NIK A IS S N: 2 3 0 2 - 4 0 4 6 A  B i s e c ti o n   M e th o d  f o r  In f o r m a ti o n   S y s te m   K n o wl e d g e  Re d u c t i o n ( Z h i  H u i l a i ) 6 9 0 5 Co n v e r ti n g   a   f o r m u l a   f r o m   CNF ( c o n j u n c ti v e   n o r m a l   f o r m )   to   DNF ( d i s j u n c t i v e   n o r m a l f o r m )   i s   e q u i v a l e n t   to   c a l c u l a ti n g   t h e   m i n i m a l   c o v e r   o f   a   g i v e n   s e f a m i l y F o r   e x a m p l e we   h a v e ( ) ( ) ( ) ( ) a b c a b b c a c b a n d ( { { , , } , { , } , { , } } ) { { , } , { } } M c a b c a b b c a c b . T h e o r e m   2 L e t 1 2 , , , { } s U U U U b e   a   s e fa m i l y a n d   f o r   a n y i j , i j U U If 1 2 , , , s D D D a r e   th e   d i s c e r n i b i l i t y   s e ts   o f 1 2 , , , s U U U r e s p e c ti v e l y th e n   a   m i n i m a l d i s c e r n i b i l i t y  s e o f U i s H , H i s  a  m i n i m a l  c o v e r   o f } 1 2 { , , , s D D D D . P r o o f : A s H i s   a   m i n i m a l   c o v e r   o f } 1 2 { , , , s D D D D a c c o r d i n g   t o   th e   d e f i n i t i o n   o f m i n i m a l   c o v e r g i v e n   a n y i D D , i H D , wh i c h m e a n s   th a t H c o n ta i n s   th e   a ttr i b u te s   th a t c a n   d i s t i n g u i s h   e v e r y   o b j e c ts   o f U f o r m   e a c h   o th e r M o r e o v e r , S H , i D D , i S D , a n d   th i s   m e a n s   th a t H i s   th e   m i n i m a l   s e th a c o u l d   d i s t i n g u i s h   e v e r y   o b j e c ts   o f U f o r m   e a c h o th e r S o ,  th e  th e o r e m  h o l d s . T h e o r e m   3 [8 ] L e t ( , ) S U A b e   a n   i n f o r m a ti o n   s y s te m   a n d a A th e   f o l l o w i n g p r o p o s i t i o n s a r e e q u i v a l e n t: ( 1 ) a i s  a  p a r ti t i o n  c o r e  a t tr i b u te ; ( 2 ) th e r e  m u s t b e  a   p a i r   o f  o b j e c ts i x U a n d j x U m a k e ( [ ] , [ ] ) { } i j A A D x x a ; ( 3 ) { } A A a R R . F o r  a n y  o b j e c t u U w e   l e t ( ) | } { a A u has at t r i b a f ut e u . Co r o l l a r y   1 :   F o r   a n y   o b j e c t , x y U i f ( ) ( ) f x f y a n d | ( ) | | ( ) | 1 f y f x th e n   th e a ttr i b u te ( ) ( ) d f y f x m u s t b e  a  p a r t i ti o n  c o r e  a ttr i b u te  o f S . T h e o r e m   4 L e t ( , ) S U A b e   a n   i n f o r m a ti o n   s y s te m   a n d C b e   i ts   p a r ti ti o n   c o r e   s e t.  L e t { [ ] | [ ] 1 , } { } c c t t T V x x x U V ( T i s   th e   i n d e x   s e t ) a n d t D i s   t h e   d i s c e r n i b i l i t y   s e o f t V f o r e a c h t T T h e n   a   m i n i m a l   d i s c e r n i b i l i t y   s e o f U i s C H , H i s   a   m i n i m a l   c o v e r   o f { } t t T D D . P r o o f A s V i s   f o r m e d   b y   e q u i v a l e n c l a s s e s th e n   f o r   a n y , i j T i f i j , i j V V . B y   T h e o r e m   2 we   k n o w H i s   a   m i n i m a l   d i s c e r n i b i l i t y   s e o f V A s   th e   e l e m e n ts   c o n ta i n e d   i n U V a r e d i s ti n g u i s h e d   f r o m   e a c h   o th e r   b y C s o   a   m i n i m a l   d i s c e r n i b i l i t y   s e o f U i s   th e   u n i o n o f C a n d H . L e t ( , ) S U A b e   a n   i n f o r m a ti o n   s y s t e m b a s e d   o n   T h e o r e m   4 we   c a n   g e a   b i s e c ti o n m e th o d  f o r  i n f o r m a ti o n  s y s t e m  a ttr i b u te  r e d u c ti o n   a s  s h o w n   i n   A l g o r i th m  1 : A l g o r i t h m  1 : a  b i s e c t i o n  m e th o d  f o r  i n f o r m a ti o n  s y s t e m  a ttr i b u te  r e d u c t i o n In p u t : a n  i n f o r m a ti o n  s y s te m ( , ) S U A O u tp u t:  p a r t i ti o n  r e d u c ti o n   s e t o f S S te p  1 : f i n d  p a r t i t i o n  c o r e  s e t C o f S ; 1 - 1   s o r o b j e c ts   o f U i n to   a   s e q u e n c e L b y   a s c e n d i n g   o r d e r   a c c o r d i n g   to   t h e i r   n u m b e r o f  a ttr i b u t e s ; 1 - 2  In i ti a l i z e C ; F o r   a n y  t wo  o b j e c t , x y i n   n e i g h b o r h o o d   i n  s e q u e n c e L d o i f , x y s a ti s f y t h a t ( ) ( ) f x f y a n d | ( ) | | ( ) | 1 f y f x th e n   a d d   a ttr i b u t e ( ) ( ) d f y f x i n t o C ; E n d f o r ; S te p  2 b i s e c ti o n  t h e   u n i v e r s e U b y   u s i n g  e a c h  a ttr i b u te   i n C ; 2 - 1  L e t | | k C , 2 b , 1 i nde x , s e t a n  a t tr a y [ ] s a n d  i n i t i a l i z e [ 1 ] s U ; 2 - 2 : F o r 0 i to 1 k d o W h i l e i n d e x b d o { * 2 l e f t i nde x ;   1 r i g h t l e f t ; Evaluation Warning : The document was created with Spire.PDF for Python.
IS S N: 2 3 0 2 - 4 0 4 6 T E L KO M NIK A V o l 1 2 , No . 9 S e p t e m b e r  2 0 1 4 : 6 9 0 3 6 9 0 8 6 9 0 6 B y   u s i n g   o n e   a ttr i b u te   i n C d i v i d e [ ] s i nde x i n t o   t w o   g r o u p s o n e   g r o u p   i s   s to r e d   i n [ ] s l e f t , a n d  th e  o th e r  g r o u p  i s  s to r e d  i n [ ] s r i ght ; i n d e x ; } E n d wh i l e ; * 2 b b ; E n d f o r ; S te p   3 c o m p u te   th e   p a r ti ti o n   d i s c e r n i b i l i t y   s e o f   th e   u n - d i s ti n g u i s h e d   o b j e c t s a n d d e n o te  t h e  r e s u l ts  a s { | } i D D i r ; S te p  4 : c o m p u te  t h e  m i n i m a l  c o v e r ( ) M C D o f  th e  s e t f a m i l y D ; S te p   5 :   g e t p a r ti t i o n   r e d u c ti o n   s e t   o f S b y   t h e   u n i o n   o f   p a r ti ti o n   c o r e   s e t C a n d ( ) M C D . E x a m p l e   1 Co n s i d e r   d e s c r i p ti o n s   o f   s e v e r a l   o b j e c ts   i n   T a b l e   1 T h i s   i s   a n   i n f o r m a ti o n s y s t e m , w h e r e { 1 , 2, 3 , 4, 5 , 6, 7 , 8 } U , a n d , , , , , , , , { } a b c d e f g h A i . T a b l e  1 . O b j e c t D e s c r i p ti o n s a b c d e f g h i 1 * * * 2 * * * * 3 * * * * * 4 * * * * * 5 * * * * 6 * * * * * 7 * * * * 8 * * * * S te p  1 g e p a r ti ti o n  c o r e  s e t C . A s ( 2 ) ( 1 ) f f h , ( 6 ) ( 5 ) f f c , ( 6 ) ( 8 ) f f b , s o { , , } C h c b S te p   2 :   b i s e c ti o n   t h e   u n i v e r s e U b y   u s i n g   e v e r y   a ttr i b u te   o f C th e   p r o c e s s   i s   s h o wn   i n F i g u r e   1 , a n d  f i n a l l y   we   g e s e t f a m i l y { { 1 , 5 } , { 6 } , { 7 , 8 } , { 3 } , { 4 } } . F i g u r e   1 . B i s e c ti o n   P r o c e s s o f  th e U n i v e r s e S te p   3 c o m p u te   th e   p a r ti t i o n   d i s c e r n i b i l i t y   s e o f   th e   u n - d i s ti n g u i s h e d   o b j e c ts { 1 , 5 } a n d { 7 , 8 } , a n d   w e   g e t ( { 1 , 5 } ) { , , } D d f g , a n d ( { 7 , 8 } ) { , } D e f ; S te p   4 c o m p u te   th e   m i n i m a l   c o v e r   o f   th e   s e f a m i l y { ( { 1 , 5 } ) , ( { 7 , 8 } ) } D D D a n d   w e g e t ( ) { { , } , { , } , { } } M c D d e e g f ; S te p   5 u n i o n   p a r ti t i o n   c o r e   s e t C a n d ( ) M c D a n d   we   g e th e   p a r t i ti o n   r e d u c ti o n   s e t , , , } , { h c b d e , , , , } , { h c b e g a n d   , , } , { h c b f . U 1 5 6 7 8 2 3 4 1 5 h c b 6 7 8 2 3 4 1 5 6 3 4 7 8 Evaluation Warning : The document was created with Spire.PDF for Python.
T E L KO M NIK A IS S N: 2 3 0 2 - 4 0 4 6 A  B i s e c ti o n   M e th o d  f o r  In f o r m a ti o n   S y s te m   K n o wl e d g e  Re d u c t i o n ( Z h i  H u i l a i ) 6 9 0 7 4 . A lg o r it h m A n a l y s is   a n d E x p e r im e n t T h e   tr a d i ti o n   m e th o d   a s   we l l   a s   i ts   i m p r o v e d   o n e s   o f   i n f o r m a ti o n   s y s te m   a tt r i b u te r e d u c ti o n   i s  b a s e d  o n d i s c e r n i b i l i t y  f u n c t i o n w h i c h  a p p e a r s  a s : | 0 , { } j i n i j i j f m m , i j m i s   th e p a r ti t i o n   d i s c e r n i b i l i t y   s e o f o b j e c ts i x a n d j x . A p p a r e n t l y ,   a f te r   c o n v e r ti n g f f o r m   CNF   to   DNF th e   c o n j u n c ti v e   c l a u s e s   c o n n e c te d   b y th e   s y m b o l     a r e   th e   p a r ti t i o n   r e d u c t i o n s   o f   th e   i n f o r m a ti o n   s y s te m S o   th e   c o m p l e x i t y   o f   CNF d e te r m i n e s   th e   e f f i c i e n c y   o f   i n f o r m a ti o n   s y s t e m   a ttr i b u te   r e d u c ti o n i .e th e   m o r e d i s j u n c ti o n c l a u s e s  c o n t a i n e d  i n  CNF th e   l o we r  th e  e f fi c i e n c y  b e c o m e s , a n d  v i c e   v e r s a . B a s e d  o n  th e  p r e v i o u s  d i s c u s s i o n   i n  s e c t i o n  3 we  k n o w   th e  c a l c u l a t i o n  o f  m i n i m a l  c o v e r f a m i l y   o f   a   g i v e n   s e i s   e q u i v a l e n to   a   c o n v e r s i o n f o r m   CNF   to   DNF S o   we   c a n   e s ti m a te a l g o r i th m  e f f i c i e n c y   b y   u s i n g  th e  n u m b e r  o f  d i s j u n c ti o n c l a u s e s  c o n t a i n e d   i n   th e  C NF  f o r m u l a . L e t ( , ) S U A b e   a   i n f o r m a ti o n   a n d | | U n In   th e   tr a d i ti o n a l   u n - b i s e c ti o n   m e th o d , th e r e  a r e * ( 1 ) / 2 n n d i s j u n c ti o n c l a u s e s  c o n ta i n e d   i n   th e   i n i ti a l  d i s c e r n i b i l i t y  f u n c t i o n . No w   w e  c o m p a r e  o u r  m e th o d   wi th  t h e  tr a d i t i o n a l  u n - b i s e c ti o n  m e th o d . ( 1 )   W o r s c a s e i n   s te p   2 i f   i n   e a c h   t i m e   b y   u s i n g   o n e   p a r t i ti o n   c o r e   a ttr i b u te   o n l y o n e o b j e c ts   c a n   b e   a p a r f r o m   t h e   o th e r s th e n   a f te r   r u n n i n g k ti m e s   b i s e c ti o n   o n U th e r e   wi l l   b e ( ) n k u n d i s ti n g u i s h e d   o b j e c ts   l e f t,  s o   th e r e   w i l l   b e ( ) ( 1 ) / 2 n k n k d i s j u n c ti o n c l a u s e s   i n   t h e f a m i l y  s e t D . T h e  r a ti o  o f  o u r  m e th o d   to  t h e  tr a d i t i o n a l   u n - b i s e c ti o n   m e th o d  i s ( ) * ( 1 ) * ( 1 ) n k n k n n . ( 2 )   B e s c a s e i n   s te p   2 i f   i n   e a c h   ti m e   b y   u s i n g   o n e   p a r ti ti o n   c o r e   a t tr i b u te   th e   u n i v e r s e i s d i v i d e d   i n t o   t w o   p a r ts   e q u a l l y th e n   a f te r   r u n n i n g   b i s e c ti o n   p r o c e s s k ti m e s , U i s   d i v i d e d   i n t o 2 k c l a s s e s a n d   e a c h   c l a s s   h a s / 2 k n u n d i s g u i s e d   o b j e c ts Co m p u ti n g   th e   p a r ti ti o n d i s c e r n i b i l i t y   s e o f   a l l   th e s e   u n d i s g u i s e d   o b j e c ts th e r e   wi l l   b e * * ( 1 ) / 2 * ( / 1 ) / 2 2 2 2 2 n n n k n n k k k d i s j u n c ti o n c l a u s e s  i n  th e  f a m i l y  s e t D . T h e  r a ti o  o f  o u r  m e th o d   to  t h e  tr a d i t i o n a l   u n - b i s e c ti o n   m e th o d  i s 1 1 / 2 2 1 k n k n . ( 3 )   A v e r a g e   c a s e we   c a r r y   t h i s   a n a l y s i s   b y   p r o g r a m m i n g   i n   J a v a In   i n i t i a l i z a t i o n w e r a n d o m l y   g e n e r a t e   th e   u n i v e r s e   a n d   th e   n u m b e r   o f   i ts   o b j e c ts   v a r i e s   a th e   r a n g e   o f   1 0 0   to 1 0 0 0 In   s te p   3 w e   r e c o r d   th e   n u m b e r   o f   p a r ti ti o n   c o r e   a ttr i b u te s   a n d   t h e   n u m b e r   o f   d i s j u n c ti o n c l a u s e s  c o n t a i n e d   i n  t h e  f a m i l y  s e t D . A f te r   r e p e a t i n g   th e   e x p e r i m e n 1 0 0 0 0   t i m e s ,   b a s e d   o n   th e   n u m b e r   o f d i s j u n c ti o n c l a u s e s th e   a v e r a g e   r a t i o   o f   o u r   m e th o d   to   th e   tr a d i ti o n a l   u n - b i s e c ti o n   m e th o d   i s d e r i v e d ,   w h i c h   h a s   a   s tr o n g   r e l a ti o n s h i p   wi th   t h e   n u m b e r   o f   p a r ti t i o n   c o r e   a ttr i b u te s W h e n   th e n u m b e r   o f   p a r ti ti o n   c o r e   a t t r i b u te s   i n c r e a s e s th e   r a ti o   d e c r e a s e s   d r a m a ti c a l l y   a s   s e e n   i n   T a b l e 2 . T a b l e 2 E x p e r i m e n t o n  A r t i f i c i a l  Da ta   S e t n u m b e r   o f   p a r t i t i o n   c o r e   a t t r i b u t e s 1 2 3 4 5 6 7 8 r a t i o   o f   o u r   m e t h o d   t o   u n - b i s e c t i o n   m e t h o d 6 1 . 4 % 3 3 . 7 % 2 3 . 3 % 1 4 . 5 % 8 . 9 % 5 . 6 % 3 . 5 % 2 . 3 % E x p e r i m e n o n   UCI  d a ta b a s e w e   s e l e c d a ta   s e ts   m o n k s c a n c e r   a n d   m o n k e y a n d c o n s tr u c i n f o r m a ti o n   s y s t e m   b y   u s i n g   th e i r   c o n d i t i o n a l   a ttr i b u te s A n d   t h e n   we   p r o g r a m   i n   J a v a , a n d   r u n   i o n   a   c o m p u te r   wi th   A M D 1 .4 HZ   p r o c e s s o r a n d   2 G   m e m o r y T h e   e x p e r i m e n r e s u l i s s h o w n   i n  T a b l e  3 . Evaluation Warning : The document was created with Spire.PDF for Python.
IS S N: 2 3 0 2 - 4 0 4 6 T E L KO M NIK A V o l 1 2 , No . 9 S e p t e m b e r  2 0 1 4 : 6 9 0 3 6 9 0 8 6 9 0 8 T a b l e 3 . E x p e r i m e n t o n  UC I D a ta S e ts n u m b e r   o f   s a m p l e s n u m b e r   o f   a t t r i b u t e s u n - b i s e c t i o n   m e t h o d o u r   m e t h o d m o n k s 4 3 2 6 6 . 1 4 7 1 s 1 . 7 1 9 2 s c a n c e r 6 8 2 9 5 3 . 7 8 5 4 s 8 . 1 7 5 3 s m o n k e y 5 5 6 1 7 7 1 . 0 9 6 3 s 5 1 . 1 8 4 8 s 5 . Co n c lu s io n T h i s   p a p e r   d e v e l o p e d   a   b i s e c ti o n   r e d u c ti o n   a l g o r i th m   f o r   i n f o r m a ti o n   s y s t e m . T h e o r e ti c a l   a n a l y s i s   a n d   e x p e r i m e n ta l   r e s u l ts   h a v e   s h o w n   th a t,  c o m p a r e d   wi th   th e   tr a d i ti o n a l n o n - b i s e c ti o n   r e d u c ti o n   a l g o r i th m th e   p r o p o s e d   a l g o r i t h m   i s e ff e c ti v e   a n d   e f f i c i e n t It  i s   o u r   w i s h th i s   s tu d y   p r o v i d e s   n e w   v i e w s   a n d   t h o u g h ts   o n   d e a l i n g   w i t h   k n o w l e d g e   r e d u c t i o n   f o r   i n f o r m a ti o n s y s t e m s   f o r  a l l  th e  d a ta  t y p e s , s u c h  a s  i n te r v a l  n u m b e r , r e a l   n u m b e r , e n u m e r a ti o n  a n d  s o  o n . T h e   w o r k   p r e s e n te d   i n   th i s p a p e r   i s   s u p p o r te d   b y   Na t i o n a l   S c i e n c e   F o u n d a t i o n   o f   Ch i n a ( G r a n No 6 0 9 7 5 0 3 3 )   a n d   Do c to r i a l   F o u n d a ti o n   o f   He n a n   P o l y te c h n i c   Un i v e r s i t y   ( G r a n No . B 2 0 1 1 - 1 0 2 ) . Re f e r e n c e s [ 1 ] Pa w l a k   Z .   R o u g h   Se t s :   T h e o re t i c a l   A s p e c t s   o f   R e a s o n i n g   a b o u t   D a t a .   B o s t o n :   Kl u w e r Ac a d e m i c Pu b l i s h e r s . 1 9 9 1 . [ 2 ] G u y o n   I ,   El i s s e f f   A.   A n   i n t r o d u c t i o n   t o   v a ri a b l e   f e a t u re   s e l e c t i o n . J o u rn a l   o f   M a c h i n e   L e a rn i n g R e s e a r c h .   2 0 0 3 ;   3 ( 1 ) :   1 1 5 7 - 1 1 8 2 . [ 3 ] H u   Q H ,   X i e   Z X ,   Y u   D R .   H y b ri d   a t t ri b u t e   re d u c t i o n   b a s e d   o n   a   n o v e l   f u z z y - ro u g h   m o d e l   a n d i n f o r m a t i o n g r a n u l a t i o n . P a t t e r n   R e c o g n i t i o n . 2 0 0 7 ;   4 0 ( 2 ) :   3 5 0 9 - 3 5 2 1 . [ 4 ] Ba b u   V S,   V i s w a n a t h   P.   R o u g h - f u z z y   w e i g h t e d   k - n e a re s t   l e a d e r c l a s s i f i e f o l a rg e   d a t a s e t s . P a t t e r n R e c o g n i t i o n .   2 0 0 9 ;   4 2 ( 9 ) :   1 7 1 9 - 1 7 3 1 . [ 5 ] J e n s e n   R ,   Sh e n   Q .   Se m a n t i c s - p r e s e rv i n g   d i m e n s i o n a l i t y   re d u c t i o n :   ro u g h   a n d   f u z z y - r o u g h - b a s e d a p p ro a c h e s .   I EEE   T ra n s a c t i o n s   o n   K n o w l e d g e   a n d   D a t a   En g i n e e r i n g .   2 0 0 4 ; 1 6 ( 1 2 ) :   1 4 5 7 - 1 4 7 1 . [ 6 ] Sw i n i a rs k i R , Sk o w ro n ,   A.   R o u g h   s e t   m e t h o d s   i n   f e a t u re   s e l e c t i o n   a n d   re c o g n i t i o n . Pa t t e r n R e c o g n i t i o n   L e t t e r s .   2 0 0 3 ;   2 4 ( 6 ) :   8 3 3 - 8 4 9 . [ 7 ] Q i a n   Y H ,   L i a n g   J Y .   C o m b i n a t i o n   e n t ro p y   a n d   c o m b i n a t i o n   g ra n u l a t i o n   i n   ro u g h   s e t   t h e o ry . I n t e rn a t i o n a l   J o u r n a l   o f   U n c e rt a i n t y ,   F u z z i n e s s   a n d   K n o w l e d g e - Ba s e d   S y s t e m s .   2 0 0 8 ; 1 6 ( 2 ) :   1 7 9 - 1 9 3 . [ 8 ] Sk o w ro n   A,   R a u s z e C . T h e   d i s c e r n i b i l i t y   m a t r i c e s   a n d   f u n c t i o n s   i n   i n f o rm a t i o n   s y s t e m s .   R o m a n Sl o w i n s k i .   I n t e l l i g e n t   D e c i s i o n   Su p p o rt - H a n d b o o k   o f   Ap p l i c a t i o n s   a n d   Ad v a n c e s   o f   t h e   R o u g h   Se t s T h e o ry .   D o rd re c h t ,   N e t h e r l a n d : Kl u w e Ac a d e m i c   Pu b l i s h e r s . 1 9 9 2 :   3 3 1 - 3 6 2 . [ 9 ] Sk o w ro n   A.   Bo o l e a n   R e a s o n i n g   f o D e c i s i o n   R u l e s   G e n e ra t i o n . 7 t h I n t e rn a t i o n a l   Sy m p o s i u m   o n M e t h o d o l o g i e s   f o I n t e l l i g e n c e   Sy s t e m s .   T ro n d h e i m ,   N o rw a y .   1 9 9 3 :   2 9 5 - 3 0 5 . [ 1 0 ] Sl e z a k   D .   Ap p ro x i m a t e   e n t ro p y   re d u c t s . F u n d a m e n t a   I n f o rm a t i c a e . 2 0 0 2 ;   5 3 ( 3 - 4 ) : 3 6 5 - 3 9 0 . [ 1 1 ] H u   X   H ,   C e rc o n e   N .   L e a rn i n g   i n   re l a t i o n a l   d a t a b a s e s :   a   ro u g h   s e t   a p p r o a c h .   I n t e rn a t i o n a l   J o u rn a l   o f C o m p u t a t i o n a l   I n t e l l i g e n c e .   1 9 9 5 ;   1 1 ( 2 ) :   3 2 3 - 3 3 8 . [ 1 2 ] W a n g   G Y ,   Z h a o   J ,   An   J J .   A   c o m p a ra t i v e   s t u d y   o f   a l g e b r a   v i e w p o i n t   a n d   i n f o r m a t i o n   v i e w p o i n t   i n a t t ri b u t e   re d u c t i o n . F u n d a m e n t a   I n f o rm a t i c a e . 2 0 0 5 ;   6 8 ( 3 ) :   2 8 9 - 3 0 1 . [ 1 3 ] L i a n g   J Y , C h i n   KS,   D a n g   C Y ,   e t   a l .   n e w   m e t h o d   f o m e a s u ri n g   u n c e rt a i n t y   a n d   f u z z i n e s s   i n   ro u g h s e t   t h e o ry . I n t e rn a t i o n a l   o f   J o u rn a l   G e n e ra l   S y s t e m s . 2 0 0 2 ;   3 1 ( 4 ) :   3 3 1 - 3 4 2 . [ 1 4 ] L i a n g   J Y ,   X u   Z B.   T h e   a l g o ri t h m   o n   k n o w l e d g e   re d u c t i o n   i n   i n c o m p l e t e   i n f o rm a t i o n   t a b l e s . I n t e r n a t i o n a l J o u rn a l   o f   U n c e rt a i n t y ,   F u z z i n e s s   a n d   K n o w l e d g e - B a s e d   Sy s t e m s .   2 0 0 2 ;   1 0 ( 1 ) :   9 5 - 1 0 3 . [ 1 5 ] T h o m a s   H   C o rm e n , C h a rl e s   L e i s e rs o n , R o n a l d   L   R i v e s t ,   C l i f f o rd   St e i n . I n t r o d u c t i o n   t o Al g o ri t h m s . 1 s t   e d i t i o n .   c a m b ri d g e : M I T   Pre s s .   1 9 9 0 . [ 1 6 ] Z h a n g   Y i .   R e s e a rc h   o f   St ra t e g i c   A l l i a n c e   St a b l e   D e c i s i o n - m a k i n g   M o d e l   B a s e d   o n   R o u g h   Se t a n d D EA. T EL KO M N I KA  I n d o n e s i a n   J o u rn a l   o f   E l e c t ri c a l   E n g i n e e ri n g .   2 0 1 3 ; 1 1 ( 1 2 ) :   7 2 6 9 - 7 2 7 6 . [ 1 7 ] Y u e   H o u .   R o u g h   Se t   Ex t e n s i o n   M o d e l   o f   I n c o m p l e t e   I n f o r m a t i o n   Sy s t e m . T EL KO M N I K I n d o n e s i a n J o u rn a l   o f   El e c t ri c a l   En g i n e e r i n g . 2 0 1 4 ; 1 2 ( 4 ) : 2 8 4 3 - 2 8 4 9 . Evaluation Warning : The document was created with Spire.PDF for Python.