TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol. 12, No. 8, August 201 4, pp. 6346 ~ 6353   DOI: 10.115 9 1 /telkomni ka. v 12i8.556 8          6346     Re cei v ed  Jan uary 3, 2014;  Re vised Ma rch 28, 2014; A c cepted Ap ril 14, 2014   Rules Mining Based on Rough Set of Compatible  Relation      Weiy an Xu* 1 ,  Ming Zhang 2 Bo Sun 1 , Meng y un Lin 1 , Rui Cheng 1   1 School of Mat hematics a nd  Ph y s ics, Jian g s Univ ersit y  o f   Science  an d T e chnolog y,   Z henj ian g  21 2 003, Ch in a      2 School of Co mputer scie n ce  and Eng i n eeri ng, Ji an gsu U n iversit y   of Scie nce an d T e chnolo g y   Z henj ian g  21 2 003, Ch in a,  *Corres p o ndi n g  author, e-ma i l : x w y_ ya n @ ho tmail.com       A b st r a ct   Rou gh s e mo del  bas ed  on   tolera nce r e lati on, h a s b e e n   w i dely  used  to  de al w i th  inc o mpl e te   infor m ati on sy stems. How e v e r, this mod e l i s  not so  p e rfe c t becaus e n o t all of th e el e m e n ts in  a tole rant   class  are  mutu ally  toler ant, b u t they  are  a ll t o ler ant w i th  th e g e n e ratin g   el ement  of this  cl ass. T o   me nd  thi s   li mitatio n , the compati b le re lati on is redefi n e d ,  and t hen the  conce p t of max i mal co mp lete  compati b le cl a s in i n co mplete   infor m ati on sy stem  is pr ese n ted fo r t he  p u rpos e that  a n y tw o ele m e n ts in th e sa me   compati b le   mo dul e ar mutu ally  co mp atibl e . F u rther more,   tw o meth ods  a r e p u t forw ard  in th interest   of  selecti ng  opti m a l  co mpatib l e  class f o r an  obj ect,  w h ich  can  be  used  in kn ow led ge r educti on. Bes i des,   coveri ngs on  univ e rse pro d u ced by tol e r ance a nd co mp atib le rel a ti ons are d eep l y  investig ated  and  compar ed. F i n a lly, a med i cal  decisi on ta ble i s  analy z e d , so me co mpact ru les are  mi ned.     Ke y w ords :  ro ugh s e t, inco mp lete  infor m ation syste m tolera nce re lati on, co mp atibl e  relati on, o p ti ma l   compati b le cl a ss, Reductio n     Copy right  ©  2014 In stitu t e o f  Ad van ced  En g i n eerin g and  Scien ce. All  rig h t s reser ve d .       1. Introduc tion  Rou gh set th eory ha s develope d sin c Pawla k ' s  pap er [1-2] as a  new math em atical tool  for analy z ing  vague an d i m pre c i s e de scriptio ns  of  object s . It use s  indi scernibil i ty (equivalen c e)  relation  to re pre s ent  cla ssification. In  rece nt  years,  rou gh  set t heory  ha s b een  su ccessf ully  applie d to so  many fields  such a s  Artifici al Intelligen ce, Data Minin g , Machi ne L earni ng, Pattern   Re cog n ition, Knowle dge  A c qui sition an so on  [2 -11 ].  Rough set prop osed  by Pawla k   is ba sed   on the  a s su mption of  co mplete info rmation  syste m s, i.e. the r e  are n o  u n kn own  value s  i n  the  informatio n table. Ho wev e r, in practi cal appli c ation s , incomplete  information  system s can  be   see n  every w here fo r a lot  of unpre d ict able reason s. Therefo r e, mining rule s from incompl e te  informatio n systems i s  one  of the important  dire ction s  for the development of ro ugh set.  In gene ral in compl e te inf o rmatio n sy stems, un kno w n valu es m a y have two  different   explanation s :  in the first case, all  un kn own val u e s  a r e “do n o t ca re”  co ndition;  in the  se con d   ca se, all  un kno w n val u e s  a r e l o st. In Refe re nce  [10], Grzym a la-Bu s se firstly studi ed  the  unkno wn val ue ( “d o n o t  care”) fro m  the vi e w p o int of roug h set theo ry, con s e quent ly,  Kryszkiewi cz [12] transformed t he indiscernibility relation to tolerance rel a tion (reflecti ve,  symmetri c ).  On the othe r hand, in comp lete inform ati on syste m s in  which  all un known value s  are   lost, from th e  viewpoi nt of rou gh  set th eory, we re  s t udied for the firs t time in  Referenc e [12],  whe r e two al gorithm s for  rule ind u ctio n were  pre s ented. Base d  on Grzym a la-Bu s se's  wo rk,   Stefanowski [ 13] advan ced  the  non-sym m etric  simila ri ty relation (ref l ective, transit ive).  In this pap er, all unkn o wn values  are  looke d  a s  “do not care ”,  that is to say, each   unkno wn value co uld be repla c ed by al l values from   the domain of  the attri bute, therefore, what  we  have  don e are all  ba se d on  the fu rth e r inve stigat i on of tol e ra nce rel a tion. In t he  cla ssifi cati on   prod uced by toleran c rel a tion, not all of the el eme n ts in the sa me tolera nt class are m u tual   tolerant, but they are all tol e rant with th e  generating el ement of this  tolerant cl ass.  Owin g to  su ch limitation  of tolera nce  rel a tion,  a  bina ry relation  call ed  comp atibl e  rel a tion  is re -defin ed.  Acco rdin g to com patible  relation, a  complete  cove ring o n  unive rse  ca n be g o t.  That is to sa y, any  two elements in th e same  com patible class are mutually  compatible. It is   clea r that thi s  kind  of cl assi fication of  uni verse   in in co mplete info rm ation sy stem s meets with t he  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Rule s Minin g  Based o n  Ro ugh Set of Co m patible Rela tion (Weiya n Xu)  6347 pra c tical  ap pli c ation s  m o re  than that i s  b a se d on  tole rance relation.  Furth e rm ore,  sin c any o n e   obje c t in the universe i s  likely to be incl uded into t w o  or mo re diffe rent compatib le cla s ses, two   different meth ods a r e p r e s e n ted for choo sing o p timal compatible  cla ss.       2. Basic Con cepts   An  in co mp le te  in fo rma t io n s y s t em is  a q u a d r up le   S= <U AT V f> , where  is a  nonem pty finite set of objects called uni verse a nd  AT  is a nonempt y finite set of  attributes, su ch   that a AT a a V V U AT a :  whe r V a   is calle d the value set o f   a ; any attribute dom ain  V a   may co ntain  spe c ial  sym bol “ ” to in dicate th at the value  of  an attrib ute i s  un kn own;  V  is  rega rd ed a s  the valu set of all  attributes an d t hen  a AT a V V ; let us define  as a n   informatio n function  su ch that  f ( x, a V a  for any   a AT  and   x U Defini tion 1 .  Let  S= < U AT V f>  b e  a n  in compl e te  inform ation  system AT A ,  a  binary relatio n  SIM ( A ) ca n be define d  as [12]:     *} ) , ( * ) , ( ) , ( ) , ( , : ) , {( ) ( a y f a x f a y f a x f A a y x A SIM                                         (1)    The  SIM ( A )  i s  a  tole ran c e  relatio n   sin c e it is reflexive an symme tric. Fu rthe rm ore, let   us den ote  by   S A ( x ) the   se t of obj ect s  f o whi c h   SIM ( A )    ho ld s ,  In  o t he r   w o rd s ,   S A ( x ) is t he  maximal set of  obje c ts which   a r e po ssibly  in disce r nible by  A  wi th  x  an d a n y one  el ement  in  S A ( x ha s a t o lera nce rela tion with  x , it is  called the tolerant class of  x . It is  c l ear that  S A ( x ) is  actually a ki n d  of neighb orhood of  x Let  U/SIM ( A ) denote s  cl assificatio n  for  A AT , which is  the family s e t {  S A ( x ):  x }.  What  sho u ld  be noti c ed i s  that all tolerant cla s se s i n   U/SIM ( A d o  not con s titute a pa rtition in  gene ral, but a  coverin g  on  universe  U , namely,  U x S A U x ) ( and ) ( x S A ( x U ).       Table 1. Inco mplete Inform ation System   Car  Price  M ileage   Si z e   M a x-spee d   High High  Full  Low   Low     F u ll Low      Compact  High  High    F u ll High      F u ll High  Low  High  Full        In Table  1,   AT ={  Pr i c e Mileage ,  Siz e Max-speed  },  then we  h a v e  U/SIM ( A )={ S AT (1),  S AT (2),  S AT (3),  S AT (4),  S AT (5),  S AT (6)}={ {1},{2,6 }, {3},{ 4 ,5},{4,5,6},{ 2 ,5,6}}.   Tolera nt classe s are  the ba sis of d e fining lo we and u ppe r a p p roximatio n of a set  X U .  The  A- l o wer approximatio and the  A- u p per ap proximation of  are :     } ) ( : { ) ( X x S U x X A A  and  } ) ( : { ) ( X x S U x X A A                                                          (2)     Even though  toleran c e relation ha been  widely  used in  de aling with in compl e te   informatio n system, it has the following  dra w ba cks.  In the first place, we can see that different   two tolerant  cla s ses m a y have incl usi o n relatio n . Fo r insta n ce, in  Table 1, S AT (2) S AT (6) a nd  S AT (4) S AT (5 ) hold, this ki nd of situatio n sometim e is unrea son a b le whe n  defi n ing app roxi mate   sets.  Furth e rmore, fo r all   obje c ts i n  S AT ( x ),  they ma y have n o   common  attrib ute value s . F o example, in T able 1, S AT  (5 )= {4,5,6},   f (4 Pric e )= { high } while   f (6,  Pr i c e )= { Lo w }. From thi s  poi nt  of view, it is clear that obje c ts 4 an d 6 a r disce r n abl e. From wh at have been di scusse d abo ve,  we shoul d make a mo re reasona ble cl assifica tio n  in  incompl e te informatio n sy stem.             Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 8, August 2014:  634 6 –  6353   6348 3. Rough Set Based o n  O p timal Comp atible Clas s   3.1. Compati b le Relation   Defini tion 3.  Let  S  be a n  incom p lete  information  syst em, ea ch  sub s et of attributes  A AT  determ i nes a  comp a t ible relation  COM ( A ).     *} ) , ( * ) , ( ) , ( ) , ( , : ) , {( ) ( a y f a x f a y f a x f A a y x A COM                                     (3)    Defini tion 4.  Let  S  be an incompl e te informatio n sy stem an A AT , then  U / COM ( A (repres ents  c l ass i fic a tion) is  defined as  f o llows :     ))} ( }) { ( ( ), ( : { ) ( / A COM x B B x U x A COM B B U B A COM U 2          (4)    In Definition  3, com patible  relation  is  rea lly sam e  t o  the tole ran c relation.  Ho wever,   U/CO M ( A ) i n  Definition  2 i s  quitely  different  with  U/S I M ( A ) be ca use any two ele m ents i n   B  are   mutually com patible. Fu rth e rmo r e, if a n y  other  elem ent in  U  i s  ad ded into  the  compatible  cl a ss,  compatible  relation in this  comp atible  cl ass  will be destroyed an yway. Thi s   kind of  com pati b le  cla ss  meet with the a c tu al nee ds m o re than  to lerant cla s s an d as  a result, it is calle the  maximal complete com p atible clas s .   For example,   Let  u s  co nsi der Tabl 1,  U/CO M ( AT )={{1},  {2,6},  {3} ,  {4,5}, { 5 ,6}}.  For an y   B U/CO M ( AT ),  B  is t he max i mal com p l e t e  comp at ibl e  cla ss.   Property  1.    If   COM ( A ) i s  a  compatibl e  relation, then:     A a a COM A COM )} {( ) (                                                                                                     (5)    Theorem 1 . Let  S  be  an in compl e te inform atio n syste m  an A C AT ,  for any   M U/C O M ( C ), there mu st be  N U/C O M ( A )  such that  M N.  Proof . By  A C AT   and  property 1, th ere mu st be   COM ( C )= ( CO M ( A ) ( c C-A COM ({ c} ),   then  CO M ( C ) COM ( A ). If  M U/C O M ( C ), then we  h a ve  M 2 CO M ( C ) COM ( A ). It means  that  any two elem ents in  M  a r e  mutually co mpatible on  set of attributes  A . If  M U/COM ( A ), then the  theore m  is ob vious. If  M U/C O M ( A ), the n , according t o  the kno w le dge of discret e mathemati c s,  there mu st be  one cla s s su ch that  M N  and  M U/CO M ( A ).   As  far as   U/S I M ( A ) is con c erne d, we ca n say about tolera nt cla ss  for any  x U , and for  U/CO M ( A we ca n only  say ab out n on-ex clu s ive  coverage  of  U  by all maximal com p lete  comp atible  cl asse s. Howe ver, the follo wing  theo rem   tells us  that maximal com p lete compatible  cla s ses a r e so tightly related with tolera nt classe s.   Theorem 2 . Let  S  be an in incom p lete informatio n system and  A AT , then for any  x U ) ( } , / : { X S B x COM U B B A hold s Proof y { B:B U/C O M ( A ),  x B  }, we have  ( x, y ) COM ( A )= SIM ( A ). By se ction 2,   S A ( x )= { y U :( x, y ) SIM ( A )}, then th ere  must  be  y S A ( x ) .  Sinc y  i s  a r bitrary ,  then  we  m u st  have { B:B U/CO M ( A ),  x B  }  S A ( x ).   For any  y S A ( x ), ( x, y ) SIM ( A )= COM ( A holds . If  { x, y is the maximal complete  comp at ible cl as B , then t he theo rem i s  tru e . If { x, y }  is not th e m a ximal one, t here  mu st be   B   su ch t hat  { x, y } B  and  B U/C O M ( A ), then  y { B:B U/COM ( A ),  x B  }ho l ds. Since  y  is  arbitrary, then   S A ( x { B:B U/COM ( A ),  x B  }.  From the a b o v e discusse d,  the theorem  2 is prove d   3.2. Optimal Compa t ible Class es   Let  S  be  an i n com p lete i n formatio n sy stem,  U/C O M ( A )={ B 1 B 2 ,...,   B n } wh ere   A AT , for  any  x U , we  call  B 1  t he max i mal com p l e t e  com pat ibl e  cla ss  of   x  if and only if 1     n  an x B i Neverth e le ss,  it is not difficult to find that there  may be two  or mo re m a ximal com p l e te  comp at ible cl as se s f o x U .   For exam ple,  the obje c t 5  in Table 1,  {4,5 } an d {5, 6 } are all it's maximal co mplete  comp at ible cl as se s.   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Rule s Minin g  Based o n  Ro ugh Set of Co m patible Rela tion (Weiya n Xu)  6349 It is natu r al  to con s ide r  h o w  to  ch oo se  a cl ass  (calle optimal compatible class ) fr om  several maxi mal complet e  compatible classes  of  object  x  fo comp uting  re ductio n . In the  followin g , two  different method s are p r e s ented.   Metho d  1.  The first meth od of cho o si n g  optimal co mpatible cl ass ro ots from t he ba sic  idea of value d  toleran c relation [13]. Simply, for  x U ,  we sh o u ld ch oo se a  max i mal com p let e   comp atible  cl ass in  whi c h  element s a r e most  po ssi bly having  sa me value s  of  attribute s  a s   x   has. Assumi n g  that the set  of possible v a lue s  on  e a ch  attribute  is discrete, we make hypoth e si that there ex its a  uniform  pro bability  di strib u tion a m ong su ch  values. Co nsider  a AT  in   incom p lete i n formation  system  S  and  a s so ciate it to t he  set { a 1 a 2 , ...,  a m } of all possibl e valu es,  given an obj e c x U , if  f ( x,  a )= , then we assume th a t  the proba bility  f ( x,  a )=  a j  ( j = 1 ,2,…,  m ) is  equal to 1/ Car d ({ a 1 a 2 ,...,   a m }).  Defini tion  5 The probabilit y of two objects  x y  h a ving  sam e  valu on a  set  of attribute s   A  is  pr A ( x , y )=  ) , ( y x pr a A a  wher pr a ( x , y ) i s  the probability of two  obj ect s  having  same val ue  on sin g le attri bute  a For any  x y U  and  a AT pr a ( x y coul d  be comp uted  as follows:     ) , ( ) , ( : ) , ( ) , ( : * ) , ( * ) , ( : )) ( /( *) ) , ( * ) , ( ( : ) ( / ) , ( a y f a x f a y f a x f a y f a x f V card a y f a x f V card y x Pr a a a 0 1 1 1 2                                                                 (6)    Defini tion 6 .  Let  S  be  an  incom p lete in formation  system in which  A AT , for any  x U the optim al  co mpatible  cla s s of   x  is  S A OPT ( x )= B i  if  and  only if  the valu e  of  } { }) { ( / ) , ( x B y i A i x B card y x Pr  is maximal for any  B i U/C O M ( A ) x B i Not e   1 . For  x U , if the r e a r e t w or  more  compati b le  cla s ses h a ve the  sa me  maximal  value of  {} (, ) / ( { } ) i yB x A i Pr x y C a rd B x  , th en their inte rse c tion is a c cepta b le a s  the optimal   comp at ible cl as s of   x For exa m ple,  the obj ect  5 in Ta ble 1 ,  there a r e t w o m a ximal  compl e te  co mpatible   cla s ses, {4, 5 }  and {5, 6}. For maximal  compl e te co mpatible cl ass {4, 5},  11 1 24 8 5, 4 AT pr  , for  maximal complete compatible  class {5,6},  11 1 1 22 2 8 5, 6 AT pr  . The r efore,  5{ 4 , 5 } { 5 , 6 } { 6 } OPT AT S  Metho d  2 . In  method  2,  we only  co nsi d er tho s e   valu es  are  all  kn own. In  all  m a ximal  compl e t e  co mpat ible cla s se of   x U ,  there  is at le ast o ne i n  whi c eleme n ts  have the  max i mal  numbe rs of attributes  who s e certai n valu es ar e equ al to the attribute s ' certain valu es of  x In incom p lete information  system  S , let  x y U  and  a A AT , su ppo se that  t =1 if and   only if  f ( x , a )= f ( y ,  a ) whil f ( x a ) a nd  f ( y ,  a ) are all kno w n, othe rwi s e   t =0. Therefore, for any  x U A AT , we define  {} () ii B yB x a A x t   whe r x B i Defini tion 7 .  In incom p let e  information system  S , in which  A AT , for any  x U , the  optimal com p atible cla ss o f   x  is  S A OPT ( x )= B  if and o n ly if  the value of  () / ( { } ) i Bi x Ca r d B x  is   maximal for any  B i U/CO M ( A ) x B i Not e   2 . Fo any  x U , if there  are two  or mo re  co mpatible  cla s se s have th e  sam e   maximal value of  () / ( { } ) i Bi x Ca r d B x , then their inte rse c tion is  a c ceptabl e as optimal   comp at ible cl as s of   x For exampl e, in Table 1, there are t w o ma x i mal  comp at ible cl as se s f o r ob ject  5,   N 1 ={ 4,5},  N 2 ={5,6}, respec tively. Ac c o rdi ng to d e finition 7, it is ea sy to work o u 1 (5 ) N = 2  a nd  2 (5 ) N =1,  so  Ma x ( 1 (5 ) N , 2 (5 ) N )= 2,  5 OPT AT S ={ 4,5}.   Defini tion  8 .  Giv e n  an  in compl e t e  i n f o rmat ion  sy st e m   S   a nd a n on-e m pty  su bset of  attributes  A AT , with each  sub s et of obj ects  X U  we  asso ciate two  sets:     () { : ( ) } OPT OPT A A Xx U S x X   and  () { : ( ) } OP T OP T A AX x U S x X                 (7)   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 8, August 2014:  634 6 –  6353   6350 Not e   3 . Acco rding to the compatible rel a tion of roug h set theory,  A -lower an A -upp er  of  X  have two instan ce s i n  respe c t that two diffe ren t  methods of  cho o si ng opti m al com patib le   cla ss.     3.3. Compari s on bet w e e n  Tolerance a nd Compa t ib le Relation s   From the vie w poi nt of gra nular  comp ut ing  [14], classe s are the  basi c  buildi n g blocks   and  call ed  el ementa r y g r a nule s  [15]. T hey a r e th smalle st  non empty sub s e t s that  ca n b e   defined, ob served o r  me asu r ed. Of course, diffe re nt binary rel a tions m a y produ ce diffe rent   elementa r y g r anul es.  Fro m  what h a ve  bee n di scu s sed  ab ove,  classe s p r o d u c ed  by tole ra nce  and compatib le relation s re spe c tively, all form cove rin g s on the u n i v erse.   Each  cove rin g  rep r e s e n ts  one g r an ulat ed view of th e universe.  Due to the diff eren ce  of  method s in  cl assifying, tole ran c and  co mpatib le relat i ons  produ ce different cove ring s calle 1    and  2 , re sp ectively. Accordin g to T h eore m  2, it i s   clea r that  coveri ng  2  i s  a  refin e me nt of   coveri ng  1  o r  equival ently  1  is a  coa r sening  of  2 , denote d  by  1  2  or  2  1 , for the rea s on  that every block of  2  is contai ned in  some bl ock  of  1 . Given two cove ring 1  and  2 , their  meet  1  2  is the large s t covering  whi c h  is a refineme n t of both  1  and  2 , and their join  1  2  is  the small e st  coveri ng  whi c h is a  coa r se ning of both  1  and  2 . Fro m  what h a ve  been  discu s sed,  coveri ng  2  h a s a smalle r level of granul ation for probl em solving th an cove ring  1 Let  U  be  a  n on-e m pty finite set of  obje c ts, a n d  let  RU U   denote  an  bi nary  relatio n   on  U . The pai apr =< U R > is called a n  approximatio n spa c e [1]. The cove ring o f  the universe  is  calle d the qu otient set in d u ce d by  R  a nd is  denote d  by  U/R . E v en thoug h rough  set d a ta   analysi s  i s  a   symboli c  met hod  of analy s is, it u s es  co unting info rm ation p r ovide d  by the  cla s se of the bina ry  relation s u n d e con s ide r ati on. T he i nhe rent statisti c o f  an app roxim a tion spa c < U R > is the  accura cy me asure of  rou gh  set  app roximatio n  [1]  () ( ( ) ) / ( ( ) ) A Ca r d A X Ca r d A X . It may  be interpreted as the probability t hat an element bel ongs to the lo wer approximation, given that  the element  belon gs to the uppe r app roximation an d expre s ses t he deg ree of  compl e tene ss of  o u r  kn ow le dge  o f   X Toleran c e an d comp atible  relation s pro duce differen t  accu ra cy measure s  of ro ugh set   approximatio n named a s 1 () A and 2 () A , respe c ti vely. Accordi ng to theore m  2, it is easy to  validate that () () () () OP T OP T A XA XX A X A X  , therefo r e,   ( ( )) ( ( )) OPT Card A X C a rd A X  an ( ( )) ( ( )) OP T Card A X Card A X , so  we  hav 12 0( ) ( ) 1 AA  . That is to say, with  c o mpatible  relation, we can get more knowl edge of  X  than tolera nce relation.       4. Kno w l e d g e Redu ction   An incompl e te de ci sion t a ble [4] i s  a n  i n com p lete i n formatio syst em  DT =< U AT { d },  V f > where  d  is call ed de cision attri bute  and  V d  is the  value domai n of the deci s ion attribute  d corre s p ondin g ly, element s in  AT  a r called  con d itio n attribute s In addition,  AT { d }=  a nd  V d  Any deci s ion  table may be  rega rd ed a s   a set of d e ci sion rul e of the form: (, ) ( , ) av d w  , where  a AT v V c w V d . Owing to difference o f  classificatio n  betwee n  compatible a n d   toleran c rel a tions, the computation o f  genera lize d  deci s ion fu nction [12] that is used  in   kno w le dge re ductio n  sh oul d be modified Defini tion  9 . Let  DT =< U AT { d },  V f be an in comp lete deci s io n system a nd then th e   gene rali zed d e ci sion fun c ti on is defin ed  as follo ws:     : ( ), , { : ( ), ( ) } OP T Ad A A UP V A A T i i d y y S x                                                             (8)    Defini tion  10 . Let  DT =< U AT { d },  V f > be a n  in co mplet e  de ci si on sy st em,   A AT  is a  redu ction of  DT (relative re ductio n ) iff  AA T  and for any  C A CA In the process of investi gation, it i s   conv enient t o  use  discernibility functi on [12] to  comp ute re du ction in in com p lete inform ation and d e ci si on syste m s.   In inco mplete  deci s io n sy stem, for any  A AT , let  (, ) A x y  be a  set of att r ibute s   a A   su ch t h at  ( x , y ) COM ({ a } )  a nd a s   a result if ( x , y ) COM ({ a } )  th en  (, ) A xy . Let (, ) A x y  be  a   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Rule s Minin g  Based o n  Ro ugh Set of Co m patible Rela tion (Weiya n Xu)  6351 Boolean  expression th at is equal  to 1 if   (, ) A xy , otherwise,  (, ) A x y  be a  disj un ction of  variable  co rre spo ndin g  to attributes  cont ained in  (, ) A x y Defini tion  11 is a di scerni bility function for  incomplet e  deci s ion sy stem if:    (, ) { : ( ) ( ) } (, ) A A xy U z U d z x x y                                                                                                    (9)    Defini tion  12 () x  is a discernibility function for object  x  in incomplete decisi on  sy st em if :     () { : ( ) ( ) } () ( , ) A A yz U d z x x xy                                                                                                   (10)      5. Illustrativ e  Example  In this se ctio n, a medical treatment de ci si on table  will be analyze d by roug h set base d   on  comp atibl e  relation.  Of co urse, t w method s of  choo sing  opti m al  comp atib le cl asse are all   work ed out.  Table 2 dep icts an in co mplete de cision table ab out medical  treatment deci s ion.   Age , Sarcou s pain Fe ve re d , and  H e ada c h e   are  the con d itional attributes,  Rem edial schem e  is  the deci s io n attribute (in t he se quel,  a 1 a 2 a 3 a 4 , and  d  will  stand for  Age Sarco u s pai n Feve re d He ada ch  a nd  Rem edial schem , resp ect i v e ly ).  V a 1 ={ a dult enfant  ,  infant }={1,2, 3 },  V a 2 ={ no pain  pain }={1,2},  V a 3 ={ no rm al hyperpyre xi a }={1,2},  V a 4 ={ n o  he ada che hea da ch e  }  ={1,2 } , an V d ={ m edical  therap y ph ys ica l  th er a p y com b inatio n  of m edicati on a nd  physics ={1,2,3 }     Table 2. Medi cal Deci sio n  Table   a a 2   a 3   a 4   1 1  2 1  2 1    2 1  3 1  2 2  4 1  5 1      6 2    2 1    2 2  9 2  10 3  1 3      The followi ng  are ten de cision rule s for T able 2:   r 1 : ( a 1 , 1)  ( a 2 )  ( a 3 )  ( a 4 , 2)  ( d , 1)  r 2 : ( a 1 , 1)  ( a 2 , 2)  ( a 3 )  ( a 4 , 2)  ( d , 1)  r 3 : ( a 1 , 1)  ( a 2 )  ( a 3 , 2)  ( a 4 , 2)  ( d , 1)  r 4 : ( a 1 , 1)  ( a 2 , 1)  ( a 3 , 1)  ( a 4 , 2)  ( d , 2)  r 5 : ( a 1 , 1)  ( a 2 , 1)  ( a 3 , 1)  ( a 4 )  ( d , 2)  r 6 : ( a 1 , 2)  ( a 2 )  ( a 3 , 1)  ( a 4 , 2)  ( d , 2)  r 7 : ( a 1 )  ( a 2 , 1)  ( a 3 , 1)  ( a 4 )  ( d , 2)  r 8 : ( a 1 )  ( a 2 , 2)  ( a 3 , 2)  ( a 4 , 1)  ( d , 3)  r 9 : ( a 1 , 2)  ( a 2 , 1)  ( a 3 , 2)  ( a 4 , 1)  ( d , 3)  r 10 : ( a 1 , 3)  ( a 2 )  ( a 3 )  ( a 4 , 1)  ( d , 3)  From  Table  2. we  ha ve  U/C O M ( AT )={{1,2,3 },{ 1 ,2,5,7},{1,4, 5 },{6},{ 7 ,10},{ 8,10},{9 }}.   Acco rdi ng to Method 1, we  have:     (1) { 1 , 4 , 5} OPT AT S (1) { 1 , 2 , 3 } OPT AT S ;    ( 3 ) { 1, 2 , 3} OPT AT S (4 ) { 1 , 4 , 5 } OPT AT S (5 ) { 1 , 4 , 5 } OPT AT S (6) { 6 } OP T AT S ;       (7 ) { 1 , 2 , 5 , 7 } OPT AT S ; (8 ) { 8 , 1 0 } OP T AT S ;   (9) { 9 } OP T AT S ;        ( 10) { 8 , 1 0 } OPT AT S   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 8, August 2014:  634 6 –  6353   6352 Acco rdi ng to Method 2, we  have:     (1) { 1 , 2 , 3 } OPT AT S (1) { 1 , 2 , 3 } OPT AT S ;   ( 3 ) { 1, 2 , 3} OPT AT S ;   (4 ) { 1 , 4 , 5 } OPT AT S (5 ) { 1 , 4 , 5 } OPT AT S (6) { 6 } OP T AT S ;      (7 ) { 1 , 2 , 5 , 7 } OPT AT S ; (8 ) { 8 , 1 0 } OP T AT S ;    (9) { 9 } OP T AT S ;        ( 10) { 8 , 1 0 } OPT AT S     Owin g to we  have two method s of cho o si ng opt imal com pati b le cla s se s, then two  different gen e r alized de ci si on functio n s ( 1 AT , 2 AT , respe c tively) are  worke d  out in Table 3 .       Table 3. Gen e rali zed  De ci sion Fu nctio n s   U\AT   1   3 4 5  6 7 8  10  η AT 1   1,2  1 1,2  1,2  2 1,2  η AT 2   1 1  1 2  1,2  1,2  3 3      Owing to different generaliz ed decisi on functions,  the  computation of discernibility   function  will be different, too. Formally , using  1 AT  we  can  com pute  out all of the rel a tive   redu ction s  of Table 2:     4 (1 ) a  ;   24 (2 ) aa  34 (3 ) aa  12 1 3 (4 ) aa aa  ;   13 (5 ) aa  13 1 4 (6) aa a a  ;     3 (7 ) a  34 (8 ) aa  13 1 2 4 (9 ) aa a a a  ;    1 (1 0 ) a 1 234 aa a a    From relative redu ction s  of obje c ts, we  can get followi ng com p a c t rules:   r 1 : ( a 4 , 2)  ( d , 1)  ( d , 2)             r 2 : ( a 1 , 1)  ( a 2 , 2)   ( d , 2)            r 3 : ( a 3 , 2)   ( d ,2)                             r 4 : ( a 1 , 2) ( a 4 , 2)  ( d , 2)              r 5 : ( a 3 , 2)  ( a 4 , 1)  ( d , 3)            r 6 : ( a 1 , 2) ( a 3 , 2)   ( d ,3)             r 7 : ( a 1 , 2)  ( a 2 , 1) ( a 4 , 1)  ( d , 32)  r 8 : ( a 3 , 2))  ( d , 3)  Usi ng  2 AT  we ca n also  comp u t e out all of th e redu ction s  i n  Table 2:     12 (1) aa  24 (2 ) aa  34 (3 ) aa  12 1 3 4 (4 ) aa aa a  13 (5 ) aa  13 1 4 (6 ) aa a a  3 (7 ) a  34 (8 ) aa  13 1 2 4 (9 ) aa a a a  1 ( 10) a ;   1 234 aa a a    Similarly to ru les ind u ci ng  by method 1  of choo sin g  o p timal com p a t ible cla s ses,  it is no hard to b r ing  out the rule s by method 2 and the out co mes a r e sam e  to  r 1 ',…, r 8 '.      6. Conclusio n   Rou gh set theory a s sum e s that kn owledge  co me s from the ab ility of classif i cation.  Ho wever,  an  explicit hyp o thesi s  in  ro ugh  set is  th at all availab l e obje c ts  ca n be  com p let e ly  descri bed  by  the set of attri butes. In  ord e r to  m ana ge  obje c ts  wh have in com p l e te de scriptio ns  of attribute s so m any  sch o lars h a ve d o ne ex cellent j obs. In  this p aper, th co mpatible  relat i on  and  maximal  co mplete  co mpatible  cla s se s a r e   presented. T he  main  advanta ge of  compat ible   cla ss i s  that it  can m a ke su re that all el e m ents  in t h same  cla s s a r e mu tually compatible  while   tolerant cl ass ca nnot. From the kno w led ge re du ction ba se d on com patibl e  relation, som e   comp act rul e s are min ed.  In the furth e r re sea r che s , we are g o ing to defin e some p r e c ise  measurement s to  weig the reli ability of thos e ru les mi ned f r om in compl e te informatio n   sy st em s.           Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Rule s Minin g  Based o n  Ro ugh Set of Co m patible Rela tion (Weiya n Xu)  6353 Ackn o w l e dg ements   This  wo rk i s   sup porte d by  the Natu ral  Scien c e F o u ndation  of China (No.6 1 1 0011 6),  Natural Sci ence Foun d a tion of Jiang su  Provi n ce of Ch ina (No.BK2011 492 ) a nd  (No.BK20 130 472).       Referen ces   [1 Pa w l a k  Z. R o ug h  se ts.  I n t e rn at ion a l J ourn a l  of  Co mput er  a nd I n f o r m at ion   Scienc es .  19 8 2 ;  11(5):   34 1- 356.   [ 2 ]   Pa w l ak Z ,  Skow r o n A.  Rou g h  set s :  some ext ensi ons,  I n f o rmat i on Sci enc es .  2007;  1 77( 1):  28-40.   [3]  Qian Y H , L i a ng JY,  Pedr ycz W, Dan g   CY. Positiv e   appr o x imati on:  an  acc e ler a tor for  attribut e   reduct i on in ro ugh set  t h e o r y .  Art i f i cial I n t e ll i genc e .  201 0;  174(9- 10):  59 7-618.   [ 4 ]   Yang  XB,   Xi e J,  Song,  XN,  e t  al.  Credi ble r u les i n  inc o mpl e t e  dec isio n s y st em base d  on  descript o rs .   Know led ge-B a sed-Syst e m s .  200 9;  22(1):  8- 17.   [ 5 ]   Xi on g Yus hu.   A Clust e r i n g  A l gorit hm Bas e d on  Ro ug h S e t  an d Gen e t i c Algor it hm.   TEL K OMNIKA   I ndon esi an Jou r nal of  Elect r ic al Eng i ne eri n g .  2013;  1 1 (10):   578 2-57 88.   [ 6 ]   Z hang  Y.  Ro u gh S e t  a nd  D EA of  St rat e g i c Alli anc e St a b le  Dec i sio n -m akin g Mo del.  TEL K OMNIKA   I ndon esi an Jou r nal of  Elect r ic al Eng i ne eri n g .  2013;  1 1 (12):   729 5-73 01.   [7]  Qian YH,  Li a ng JY, P edr ycz W, Dang   CY. An e ffici e n t acce lerator  for attribut reducti on from  in co mp le te  da t a  in  ro ug h  se t fra m e w o r k.  Pat t ern Rec ogn it io n .  2011;  4 4 (8):  165 8-16 70.   [ 8 ]   Xu WH,  L i  Y,  Li ao  XW.  Appro a c hes t o  at t r ib ut e red u ct ions  b a sed  on ro ug set  and m a t r i x   comput at i on  in inc onsist e nt  order ed inf o rmat ion s y st ems.   Know led ge-B a sed Syst e m s.  201 2;  27:  78-9 1 .   [ 9 ]   Lia ng JY,  Wan g  F ,  Dang CY,  Qian YH,  An  ef f i cient  ro ugh  f eat ure sel e ct i on al gor it hm  w i t h  a mult i- gran ulat i on vi e w ,   I n t e rn at ion a l  Journa l of  App r oxi m at e R eas oni ng .  20 12;  5 3 (6):  912- 92 6.   [ 10]   Grz y mal a -Bus se JW.  Dat a   w i t h  missin g  at t r i but e va lues:  g ener aliz at io n o f  indisc erni bil i t y  re lat i o n  a n d   ru le  red u c tion Lect u re N o t e s i n  Co mp ut er Scienc e .  200 4;  3100:  78- 95.   [ 11]   Grz y mal a -Bus se JW,  Wang  AY.  Modif i e d   al gorit hms  LEM1  and  LEM2  f o rule  ind u ct io n f r om dat a   w i t h   missing  at t r ibu t e valu es.  Pro c eed ing  of  t h e  5t h I n t e rn at io nal Works hop  on R o u gh S e t s  and  Sof t   Co mp ut ing  at  t he 3r d J o int   C onf ere n ce  on I n f o rmat io n Sci ences ,  R e se ar ch T r iangl e Pa rk,  NC.  19 97:   69-7 2 .   [12]  Kr y szkie w icz  M. Rules in in complete inf o rmation s y st ems.  I n t e rnat i ona l Journ a of  I n f o rmat i o n   Scienc es .  199 9;  113(3- 4):  27 1-29 2.   [ 13]   St ef ano w s k i  J .  I n compl e t e  i n f o rmat io n t a b l es a nd r o u g h  class i f i cat i o n .  I n t e rnat i o n a l  Jour na l of   Co mp ut at ion a l I n t e lli genc e .  20 01;  17(3):  5 45- 566.   [ 14]   Yao YY.  I n f o rm at ion  gran ul at i on a nd ro ug h a ppro x imat io n.   I n t e rnat i o n a l Jo urna l of  I n t e ll ig ent  Syst e m s 200 1;  16(1):  87 -104.   [ 15]   Xu WH,  Sun  WX,  Z hang  XY,  Z hang WX.  Mult iple  gra nul at ion r oug h  set  appro a ch  t o  ordere d   inf o rmat i on s y s t ems .  I n t e rnat iona l Journ a l of  General Syst e m s.  20 12;  41( 5 ) :  475-50 1.     Evaluation Warning : The document was created with Spire.PDF for Python.