I nte rna t io na l J o urna l o f   E lect rica l a nd   Co m p ute E ng in ee ring   ( I J E CE )   Vo l.  7 ,   No .   3 ,   J u n 2 0 1 7 ,   p p .   1 3 8 5 ~ 1 3 9 7   I SS N:  2 0 8 8 - 8 7 0 8 ,   DOI : 1 0 . 1 1 5 9 1 /i j ec e. v 7 i3 . p p 1 3 8 5 - 1397        1 3 8 5         J o ur na l ho m ep a g e h ttp : //ia e s jo u r n a l.c o m/o n lin e/in d ex . p h p /I JE C E   Appro x i m a tion   M ea sures  f o r   Co n ditiona l F unc tion a l   Dependen cies Usi ng  St rippe d Con d ition a l P a rti tions     Anh Duy   T ra n 1 ,   So m j it   Arc h - int 2 ,   Ng a m n ij   Arc h - int 3   1, 2, De p a rtm e n o f   Co m p u ter S c ien c e ,   F a c u lt y   o f   S c ien c e ,   Kh o n   Ka e n   Un iv e rsity       Art icle  I nfo     AB ST RAC T     A r ticle  his to r y:   R ec eiv ed   A p 1 1 ,   2 0 1 7   R ev i s ed   M a y   5 ,   2 0 1 7   A cc ep ted   M a y   2 4 ,   2 0 1 7         Co n d it io n a f u n c ti o n a d e p e n d e n c ies   (CF Ds h a v e   b e e n   u se d   to   i m p ro v e   th e   q u a li ty   o f   d a ta,  in c lu d in g   d e tec ti n g   a n d   re p a iri n g   d a ta  i n c o n siste n c ies .   A p p ro x ima ti o n   m e a su re s   h a v e   si g n if ica n i m p o rtan c e   f o d a ta  d e p e n d e n c ies   in   d a ta  m in in g .   T o   a d a p to   e x c e p ti o n in   re a d a ta,  th e   m e a su re a re   u se d   to   re lax   th e   strictn e ss   o f   CF Ds   fo m o re   g e n e ra li z e d   d e p e n d e n c ies ,   c a ll e d   a p p ro x im a te  c o n d it io n a f u n c ti o n a d e p e n d e n c ies   (A CF Ds ).   T h is  p a p e a n a ly z e th e   w e a k n e ss e o f   d e p e n d e n c y   d e g re e ,   c o n f id e n c e   a n d   c o n v ictio n   m e a su re f o g e n e ra CF Ds   ( c o n sta n a n d   v a riab le CF Ds ).   A   n e w   m e a su re   f o g e n e ra CF Ds   b a se d   o n   in c o m p lete   k n o w led g e   g ra n u larit y   is  p ro p o se d   to   m e a su re   th e   a p p ro x im a ti o n   o f   th e se   d e p e n d e n c ies   a w e ll   a th e   d istri b u ti o n   o f   d a ta  tu p les   i n to   th e   c o n d it io n a l   e q u iv a len c e   c las se s.  F in a ll y ,   th e   e ffe c ti v e n e ss   o f   strip p e d   c o n d it i o n a p a rti ti o n a n d   th is  n e w   m e a su re   a re   e v a lu a ted   o n   sy n th e ti c   a n d   re a d a ta  se ts.   T h e se   re su lt a re   i m p o rtan to   th e   stu d y   o f   th e o r y   o f   a p p ro x im a ti o n   d e p e n d e n c ies   a n d   im p ro v e m e n o d isc o v e r y   a lg o rit h m s o f   CF Ds   a n d   A CF Ds .   K ey w o r d :   Ap p r o x im ate co n d itio n al  f u n cti o n al  d ep en d en cies   Me asu r es   Strip p ed   c o n d itio n al  p ar titio n s   I n co m p lete  k n o wled g e   g r an u lar it y   C o p y rig h ©   2 0 1 7   In stit u te o A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e .   Al rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   An h   Du y   T r an ,     Dep ar t m en t o f   C o m p u ter   Scie n ce ,   Facu l t y   o f   Scie n ce ,     Kh o n   Kae n   U n iv er s it y ,       1 2 3   Mo o   1 6   Mittap ap   R o ad . ,   Nai - M u a n g ,   M u an g   Di s tr ict,   Kh o n   Kae n   4 0 0 0 2 , T h ailan d   E m ail:  d u y a n h 2 0 8 @ g m ail. co m         1.   I NT RO D UCT I O N     Hig h   d ata  q u alit y   h as   v er y   i m p o r tan t   r o le  f o r   m a n y   o r g an izatio n s   i n   m a k i n g   co r r ec d ec is io n s .   Ho w e v er ,   in   r ea l - w o r ld   ap p licatio n s ,   th d ata  o f te n   co n tain s   in co n s i s te n cies ,   in ac c u r ac ies  an d   er r o r s   b ec au s o f   in te g r atio n   o f   d ata  f r o m   v a r io u s   s o u r ce s .   A   r ec e n r ep o r s h o w ed   th at  b ill io n s   o f   d o llar s   in   lo s s e s   an n u all y   f o r   US  b u s i n es s   i s   d u e   to   p o o r   d ata  q u alit y   [1 ] A lt h o u g h   f u n ctio n al  d ep en d en c ies  ( F Ds)  ar s i g n i f ican t   co n s tr ain ts   an d   k n o w led g i n   r elatio n al  d atab ase  d esig n   a n d   d ata  m i n i n g   [2 - 6 ] ,   th e y   ar n o r o b u s t   en o u g h   to   ad d r ess   d ata  q u alit y   p r o b le m .   T h er ef o r e,   CF D s   h a v b ee n   ex ten d ed   f r o m   FD s   to   s o lv e   t h is   p r o b lem   [7 - 8] FDs   o n l y   h o ld   o n   s et  o f   tu p l es  s ati s f y i n g   t h co n d itio n s   c h ar ac ter ized   b y   C FD s .   Fo r   ex a m p le,   let  cu s t   b a   r elatio n   s p ec if y i n g   cu s to m er s   w it h   t h attr ib u te s C C   ( co u n t r y   co d e) ,   Z I P   ( zip   co d e) ,   S T R   ( s tr ee t) ,   A C   ( ar ea   co d e) ,   C T   ( city )   a s   i n tr o d u ce d   in   [7 ][ 9 ] .   L et's  co n s id er   t w o   C FD s 1   =   ( [ C C ,   ZIP ]     S TR,   ( 4 4 ,   -   ||   - ))   a n d   2   =   ( [ C C ,   A C ]     C T,   ( 0 1 ,   212   ||   N YC ) ) .    C FD  1   o n l y   h o ld s   o n   th r elatio n   cu s w h en   th cu s to m er 's  co u n tr y   co d is   4 4 .   C FD  2   s h o w s   t h at  if   al cu s to m er s   i n   th US  ( C C =0 1 )   h av a n   ar ea   co d o f   2 1 2 ,   th en   th eir   cit y   m u s t   b NY C .   T h ese  co n s tr ain t s   ca n n o t   b d is co v e r ed   f r o m   t h d atab ases   u s i n g   t h co n ce p t o f   FD.   T h e   m ai n   ap p lica tio n   o f   C FD s   is   d ata  clea n i n g   [ 7 ][ 10 ][ 11 ]   in   w h ic h   C F d is co v er y   is   an   i m p o r tan t   s tag e.   T h m ea s u r es  h a v b ee n   u s ed   to   d is co v er   th in ter est in g   r u les ,   r ed u ce   s ea r ch   s p ac e   an d   r elax   s tr ictn e s s   of   C FDs   w it h   e x ce p tio n s   i n   d a ta  [ 9 ][ 12 - 13 ] C h ian g   et   al  [ 1 2 ]   in tr o d u ce d   t h v ar io u s   m ea s u r es to   ev al u ate   th e   d ata  q u alit y   r u le s ,   in cl u d in g   S u p p o r t,  2 - T est,  C o n f id en ce ,   I n ter est  an d   C o n v ict i o n .   B ased   o n   th s u b s u m ed   class es   in   t h p ar titi o n s ,   th e s m ea s u r es   ca p tu r e d   in ter esti n g   C FDs   s u c h   th at   th er e   e x i s t h co n d itio n al   Evaluation Warning : The document was created with Spire.PDF for Python.
                    I SS N :   2 0 8 8 - 8708     I J E C E   Vo l.  7 ,   No .   3 ,   J u n 2 0 1 7   : 1 3 8 5     1 3 9 7   1386   attr ib u tes   o n   th le f h a n d   s id e   ( L HS)   o f   th ese  C FDs .   T h n o n - s u b s u m ed   clas s es  ar u s e d   to   f o r m alize   th e   ap p r o x im a te  co n s ta n C FD s   f o r   id en tify i n g   d ir t y   d ata  v alu e s .   T h er ef o r e,   it   s ee m s   d if f ic u lt   to   ap p r o x im ate  t h e   g en er al  C FD s   b ased   o n   th ese  m ea s u r es.     T h in ter esti n g   r u les   in   t h d i s co v er y   p r o b lem   o f   co n s ta n t   C FD s   [ 1 4 ]   w er e   also   e v al u ate d   b ased   o n   th 2 - Te s t .     Mo r eo v er   th c o n v ictio n   is   a n   e f f ec t iv m ea s u r f o r   ass o ciatio n   r u les  b ec au s it  tac k le s   th e   w ea k n ess e s   o f   t h co n f id en c an d   in ter est  m ea s u r es  [ 1 5 ] .   A s   s h o w n   in   [ 1 2 ] ,   th co n v ictio n   i s   th b es m ea s u r f o r   p r o v id in g   th i n t er esti n g   C FD s   an d   id e n ti f y in g   t h d ir t y   d ata  v al u es.  T h er e f o r e,   th co n v ict io n   m ea s u r w i ll b s elec ted   f o r   a n al y s i s   in   t h is   s t u d y .   R ec en t l y ,   Nak a y a m et  a [ 1 3 p r esen ted   t h f o r m aliza tio n   o f   A C FDs   w it h   t h co n f id en c m ea s u r e   b ased   o n   th m a x i m u m   n u m b er   o f   tu p les  in   r elatio n   s at is f y in g   t h co n d it io n al  d ep en d en c y .   T h is   m ea s u r is   ex ten d ed   f r o m   t h er r o r   m ea s u r g 3 [ 1 6 ] ,   w h ic h   h a s   b ee n   u s ed   w id el y   i n   th s t u d y ,   d is co v er y   a n d   ap p licatio n   o f   ap p r o x i m ate  f u n ctio n al  d ep en d en cie s   ( AFDs )   a n d   co m p a r ab le  d ep en d en cies  ( C Ds)  [ 17 - 2 1 ] .   Nak a y a m et   al  f o c u s ed   o n   e x te n d in g   t h r ee   d is co v er y   al g o r ith m s   f o r   A C FD s   ( ap p r o x C F DM in er ,   a p p r o x C T A NE   an d   ap p r o x Fas tC FD)   f r o m   C FD d i s co v er y   al g o r ith m s   [9 ].   Un f o r tu n atel y   t h e f f ec tiv e n es s   o f   s tr ip p ed   co n d itio n al  p ar titi o n s   an d   e v alu a tio n   o f   t h is   m e asu r f o r   AC FD s   w er n o t   co n s id er ed .   T h er ef o r w in tr o d u ce   th co n d itio n al  i n d is ce r n ib ilit y   r elatio n ,   co n d itio n a l   eq u iv ale n ce   c lass ,   co n d itio n a p ar titi o n s tr ip p ed   co n d itio n al  p ar titi o n   a n d   d ep en d en c y   d eg r ee     a s   a n   ex ten s io n   f r o m   t h co n ce p ts   o f   P a w la k   r o u g h   s et   [ 2 2 - 23 ]   to   co n f r o n t   t h is   p r o b le m .   R o u g h   s et  t h eo r y   i s   an   ef f ec tiv e   ap p r o ac h   f o r   a n al y z in g   u n ce r tai n   a n d   i n co m p lete   d ata  in   m a n y   ar ea s   o f   d ata  m i n in g ,   k n o w led g e   d is co v er y   an d   attr ib u te  r ed u c t io n   [ 2 2 - 28 ] .   I n   ad d itio n ,   in f o r m atio n   ( k n o w led g e)   g r a n u lar it y   ca n   b u s ed   to   m ea s u r u n ce r tai n t y   o f   in f o r m atio n   [ 29 - 33 ] .     T h is   s tu d y   al s o   in f er s   th at  t h e   m ea s u r e m e n o f   A C FDs   allo w s   u s   to   k n o w   th e   d is tr ib u tio n   d eg r ee   o f   o b j ec ts   in   th co n d it io n al  eq u iv a len ce   cla s s es.  Fo r   ex a m p le ,   w ca n   r ep r esen h o w   m u ch   d eg r ee   p atien t s   co r r esp o n d in g   to   an y   s y m p to m   ar d is tr ib u ted   in to   d is ea s g r o u p s .   Ho w ev er   t h ab o v m ea s u r e s   ca n n o t   ex p r ess   t h is   d is tr ib u t io n .   W th er ef o r i n tr o d u ce   t h i n co m p lete   k n o w led g g r an u la r it y   o f   co n d itio n al   p ar titi o n   in d u ce d   b y   ite m s et s   b ased   o n     th k n o w led g g r an u lar i t y   o f   t h p ar t itio n   [ 3 3 ]   to   p r o p o s n ew   m ea s u r th at   n o o n l y   m ea s u r e s   th ap p r o x i m atio n   d eg r ee   o f   d ep en d en cies  C FDs ,   b u al s o   th d is tr ib u tio n   o f   d ata  tu p les  in to   th co n d it io n a eq u iv ale n ce   class e s .   T h is   m e asu r ca n   g iv u s   m o r g e n e r al  v ie w   o f   A C FDs   w it h   e x p ec tat io n   f o r   ex te n d in g   A C FDs   to   o t h er   ap p licatio n   d o m ai n s   s u c h   as  cla s s i f icatio n   an d   s o cio lo g ica l   in v e s ti g atio n .   Fi n all y   th co m p u tat io n s   o f   m ea s u r es  u s i n g   t h s tr ip p ed   co n d itio n al   p ar titi o n s   allo w   th e   d is co v er y   ti m o f   C FD s   an d   AC FD s   to   b i m p r o v ed   ef f ec t iv el y .   Fro m   th i s   p r o m is i n g   an al y s is ,   th p ap er   f o cu s es   o n   s o lv in g   t h f o llo w i n g   is s u e s :     C o m p u tin g   t h m ea s u r es  b a s ed   o n   t h co n d itio n al  p ar titi o n s   a n d   s tr ip p ed   co n d itio n al   p ar titi o n s .     E v alu a tin g   t h ef f ec ti v en e s s   o f   th s tr ip p ed   co n d itio n al  p ar titi o n   f o r   d is co v er y   al g o r ith m   o f   AC FD s   ( ap p r o x C T A NE )   b ased   o n   th co n f id en ce   m ea s u r e.     E v alu a tin g   t h li m itatio n s   o f   th m ea s u r es   f o r   A C FDs ,   i n clu d i n g   th d ep en d e n c y   d eg r ee ,   co n f id e n ce   an d   co n v ictio n.     P r o p o s in g   n e w   m ea s u r e   f o r   C FD s   an d   ev al u ati n g   th u tili t y   o f   t h is   m ea s u r e .   T h r est  o f   th p ap er   is   o r g an ized   as  f o llo w s Sectio n   2   p r esen ts   p r i m ar y   co n ce p t s   o f   p ar titi o n ,   d ep en d en c y   d eg r ee   a n d   co n d itio n al  f u n ctio n al  d ep en d en ci es.  I n   s ec tio n   3 ,   w co m p u te   th m ea s u r es  an d   p r o p o s n e w   m ea s u r f o r   C FDs   b ased   o n   co n d itio n al  p ar titi o n   an d   s tr ip p ed   co n d itio n al  p ar titi o n   as  w el as   an al y ze   a m o n g   th e   m ea s u r e s .   Sectio n   4   i n tr o d u ce s   th d i s co v er y   p r o b le m   o f   AC F Ds  a n d   p r o d u ct  o f   t w o   s tr ip p ed   co n d itio n al  p ar titi o n s .   T h ev alu a tio n   o f   m ea s u r es   an d   d is co v er y   o f   AC FD s   ar co n d u ce d   o n   th e   s y n t h etic  an d   r ea l d ata  s ets i n   Sectio n   5 .   Sectio n   6   co n cl u d es   th p ap er .     2.   P RE L I M I NARIE S     I n   th i s   s ec tio n ,   w i n tr o d u ce   s o m co n ce p ts   o f   r elati o n al  d atab ase,   in d is ce r n ib ili t y   r elat io n ,   p ar titi o n s ,   d ep en d en c y   d e g r ee   an d   co n d itio n al  f u n ctio n al  d ep en d en cie s   [7 - 9 ] [ 2 2 - 23 ] [ 34 ] .   L et  r ( R )   b r elatio n   o n   s et   o f   attr ib u tes  R   {A 1 ,   A 2 ,   . . . ,   A m } ,   w h er d o m( A k )   i s   d o m ain   o f   A   R.   T h en   an   i n d is ce r n ib ilit y   r elatio n   I X   is   d ef i n ed   b y   ]} [ ] [ , | ) , {( 2 k j k i k j i X A t A t X A r t t I   T h r elatio n   I X   p a r titi o n s   th s et  o f   tu p les  r   i n to   eq u iv a le n ce   class es.  Fo r   t i     r ,   an   eq u i v al en ce   clas s   ) ( i X t I   o f   t i   o n   s et  o f   attr ib u tes  X   is   d ef in ed   by     ]} [ ] [ , | { ) ( k j k i k j i X A t A t X A r t t I   Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I SS N:  2 0 8 8 - 8708       A p p r o xima tio n   Mea s u r es fo r   C o n d itio n a l F u n ctio n a l D e p en d en cies U s in g   S tr ip p ed   . . . .   ( A n h   Du Tr a n )   1387   T h en   s et  o f   eq u i v alen ce   c lass es  } | ) ( { r t t I I i i X X   is   ca lled   p ar titi o n   o f   r   o n   X T h e   p ar titi o n X I is   f i n er   t h an   Y I if   an d   o n l y   i f   f o r   an y   eq u iv ale n ce   cla s s   w X I ,   th er e x is t s   t h eq u iv a len ce   clas s   q   in   Y I   s u c h   th at   w   q .   T o   r ed u ce   co m p u tat io n al  t i m e   w it h   t h p ar titi o n s ,   H u h tala  et   al [ 1 7 ]   h av e   p r o p o s ed   th s tr ip p ed   p ar titi o n   o f   X I ,   d en o ted   X I ˆ as f o llo w s       } 1 | | | { ˆ w I w I X X     s et   o f   tu p les   O      r   ca n   b ap p r o x i m ated   w it h   r esp ec t o     R   b y   d e f in in g   th e   lo wer   ) ( * O X   ap p r o x im a tio n ,   w h er e } ) ( | { ) ( * O t I r t O X i X i .   T h en   f o r   t w o   s et s   o f   attr ib u tes  X   a n d   Y ) ( ) , ( * O X r Y X P OS Y I O is   p o s itiv r eg io n   o f   d ep en d e n c y     Y   T h co ef f icie n | | ) , ( ) , ( r r Y X P O S r Y X d ef in e s   d ep en d en c y   d e g r ee   o f     Y .   I f , 1 ) , ( r Y X   th en   X Y   is   a   f u n ctio n a l d ep en d en c y .   Fu n ctio n al  Dep e n d en cies  ( F Ds)  ex p r ess   th r elatio n s h ip   b et w ee n   t w o   s ets  o f   attr ib u tes  o n   t h e   r elatio n   r ( R ) .   I n   m o r g en er ali ze d   f o r m ,   C FD s   s p ec if y   t h co n s tr ain ts   b et w ee n   t w o   s e ts   o f   attr ib u tes  f ix ed   b y   p ar ticu lar   v alu e s .   A   C o n d itio n al  Fu n ctio n al  Dep en d en c y   ( C FD)   ,   d en o ted   ( X     Y,  t p )   [9 ] ,   is   Fu n ctio n al   Dep en d en c y   w it h   r esp ec t   to   p atter n   t u p le  t p    s u c h   t h at  f o r   ea ch     A k     X Y ,     t p [A k ]   =   a     o r     t p [A k ]     =   - ,   w h er e   th co n s ta n     d o m( A k )   a n d   v alu o f   u n n a m ed   v ar iab le  -   d r a w n   f r o m     d o m( A k ) .   A   t u p le  t i   m atc h es  t h e   p atter n   tu p le  t p   o n   th s et  o f   attr ib u tes  X ,   d en o ted   t i [ X ]       t p [ X ]   if   an d   o n ly   i f     f o r   ea ch   A k     X ,   ( t i [A k ]   =   t p [A k ]   )   or    (t i [A k ]   =   ' a ',   t p [A k ]   =     ' - ') ,   a     d o m( A k )   .   W w r ite   t i [ X ] <<  t p [ X ]   if   t i [X       t p [ X ]   b u   t p [ X ]     t i [ X ] .   T h C FD    =   ( X     Y,   t p )   h o l d s   o n   r   ( o r   r   s ati s f ies  ,   d en o t ed   | r )   if ,   f o r   an y   t i ,   t j     r   s u ch   t h at   t i [ X ]   =   t j [ X ]     ≤    t p [ X ] ,   th en   t i [ Y ]   =    t j [ Y ]       t p [ Y ] .   As  m en tio n ed   i n   [9 ][ 12 ]   w e   ca n   d is co v er   th e   C F Ds  o f   f o r m     ( X     A k ,   t p ),   w h er e   th s i n g l e   attr ib u te  A k   is   i n   R   a n d   n o t i n   X .     L et      ( X     A k , t p )   b C FD a n d   X       .   A cc o r d in g   t o   [9 ] X c     is   s et  o f   attr ib u tes  s u c h   th at  t p [X c ]   is   co n s tan p atter n   t u p le.   T h r e m ain in g   attr ib u te s   X v   X   -   X c   is   co r r esp o n d in g   to   v ar iab le  p atter n   t u p le  s u ch   th at  t p [X v ]   ( - ,   . . . ,   - ).   T h er ef o r e,   th C FD    ca n   b ex p r es s ed   b y   t h f o r m     ( [ X c , X v   A k , t p ).       3.   AP P RO XIM AT E   M E ASUR E S F O CF Ds   I n   th is   s ec t io n ,   w p r esen th e   co n d itio n al  p ar titi o n ,   s tr ip p ed   co n d itio n al  p ar titi o n an d   a p p r o x im a te   m ea s u r es  f o r   d ep en d en cies.   W f ir s t c o n s id er   s o m e   m ea s u r es   f o r   C FDs .   Def ini t io n   3 . 1 .   [9 ][ 12 ] [ 3 5 L et  r ( R )   b r ela tio n ,   t h s u p p o r o f   C FD    ( X     A k ,   t p )   o n   r ,   d en o ted   s u p ( ,   r ) ,   is   d ef i n ed   b y       | | | | ) , s u p ( r r r p t   ( 1 )     w h er | | | | ] [ k p p XA t t r r is   t h n u m b er   t u p les i n   r   m a tch i n g   t p   o n   s et  o f   attr ib u t es  XA k .   Fro m   th co n v ict io n   m ea s u r in   [ 1 2 ] ,   Def in itio n   3 . 2   d ef in es t h is   m ea s u r f o r   g e n er al  C FDs .   Def ini t io n 3 . 2 .    L et  r ( R )   b r elatio n ,   th co n v ic tio n   m ea s u r o f   C FD    = ( X     A k , t p )   o n   r ,   d en o ted   C o n v( ,   r ) ,   is   d ef i n ed   b y       ])) [ , ( ]), [ , (( ])) [ , ( ( ])). [ , (( ) , ( k p k p k p k p A t A X t X P A t A P X t X P r C o n v     w h er p r o b ab ilit y   P ( X , t p [ X ] )   i s   eq u al  to   s u p ( X ,   t p [ X ] )   an d   if   ( X ,   t p [ X ] )   an d   (A k ,   t p [A k ])   ar e   in d ep en d en t,  t h en   C o n v( ,   r)   is   eq u a l to   1 .   Def ini t io 3 . 3 .   [ 1 3 L et  r ( R )   b r elatio n ,   t h co n f id en ce   o f   C FD    ( X     A k ,   t p )   o n   r ,   d en o ted   co n f ( ,   r ) ,   is   d e f i n ed   b y       | | )} , ( | ' , ' || ' m a x { | ) , ( r t A X r r r r r c o n f p k   (2 )   Evaluation Warning : The document was created with Spire.PDF for Python.
                    I SS N :   2 0 8 8 - 8708     I J E C E   Vo l.  7 ,   No .   3 ,   J u n 2 0 1 7   : 1 3 8 5     1 3 9 7   1388   P ar titi o n s   o f   ite m s e ts   ar e   i n tr o d u ce d   in   [9 ]   to   c h ec k   co r r ec tn es s   o f   C FD s   i n   th e   d is co v er y   p r o b le m L et  r ( R )   b r elat io n   o n   R   an d   ( Z,  t p [ Z ] )   b an   ite m s et,   w h er     R .   T h er ex is t s   co n d itio n al  in d is ce r n ib ilit y   r elat io n   ]) [ , ( Z t Z p I o r ,   d ef i n ed   b y       ]} [ ] [ ] [ | ) , {( 2 ]) [ , ( Z t Z t Z t r t t I p j i j i Z t Z p     A   co n d itio n al  eq u i v ale n ce   class   o f   t i   w it h   r esp ec to   item s et  ( Z,  t p [ Z ] ) ,   d en o ted   ), ( ]) [ , ( i Z t Z t I p   is   d ef in ed   b y   ]} [ ] [ ] [ | { ) ( ]) [ , ( Z t Z t Z t r t t I p j i j i Z t Z p . T h er ef o r e   th er ex is t s   co n d itio n al  p ar titi o n   o f   r   w it h   r esp ec t to   ( Z,  t p [ Z ] ) ,   d ef in ed   b y       } 0 | ) ( | , | ) ( { ]) [ , ( ]) [ , ( ]) [ , ( i Z t Z i i Z t Z Z t Z t I r t t I I p p p   (3 )     T ab le  1 A   d ata  tab le     A1   A2   A3   t 1   0   1   0   t 2   0   1   0   t 3   1   2   0   t 4   1   2   0   t 5   0   1   0   t 6   0   2   1   t 7   1   2   2   t 8   1   3   2   t 9   1   3   2   t 10   2   1   3   t 11   2   2   1   W h av e   th a t   ) ( ]) [ , ( i Z t Z r t t I p i ,   w h er e   ) ( ]) [ , ( i Z t Z t I p ≠  ,   is   n o al w a y s   eq u al  to   r .   T h er ef o r th e   co n d itio n al  p ar titi o n   ]) [ , ( Z t Z p I is   s e m i - p ar titi o n .   Fo r   ex a m p le,   let  r ( R )   b r elatio n   as T ab le  1 .   T h en   } { }, { }, , { }, , , { }, { }, , , { 11 10 9 8 7 4 3 6 5 2 1 , ( ) , , 2 1 t t t t t t t t t t t I A A ;   } { }, , , { }, { 11 7 4 3 6 , ( ) 2 , , 2 1 t t t t t I A A   r t t t t t w A A I w } , , , , { 11 7 6 4 3 ) 2 , , 2 , 1 (   Def ini t io n 3 . 4 .   L et     r   b a   s et  o f   t u p les   an d   let   ( Z,  t p [ Z ] )   b an   ite m s et   s u c h   t h at     R,   th e   lo w er   ) ( ]) [ , ( * O Z t Z p ap p r o x im a tio n   o f   O    i s   d ef i n e d   b y       } ) ( | { ) ( ]) [ , ( ]) [ , ( ]) [ , ( * O t I and I r t O Z t Z i Z t Z Z t Z i p p p   (4 )   Def ini t io 3 . 5 .   L et    r ( R )   b r elatio n ,   th d ep en d en c y   d eg r ee   o f   C FD      ( X     A k ,   t p )   o n   r d en o ted   ( ,   r ) ,   is   d ef i n ed   by       | | | ) , ( | | | 1 ) , ( ] [ ] [ r r P O S r r X t X t p p   (5 )   w h er e:    ) ( ]) [ , ( ) , ( * ]) ] [ ] [ , ( q X t X r P OS p I q X t k A p t k A p   an d   w r X p t X p I w X t ]) [ , ( ] [   P ro po s it io 3 . 1 .   L et  r ( R )   b r elatio n ,   th s u p p o r t o f   C FD    = ( X     A k , t p )   o n   r   is   co m p u ted   by       | | | | | | | | ) , s u p ( ]) [ , ( r w r r r k XA p t k XA p I w t   ( 6)   P r o o f.   w h a v | | | | ] [ k p p XA t t r r | | ]) [ , ( w k XA p t k XA I w P r o p o s itio n   3 . 1   th er e f o r ca n   b e   in f er r e d   f r o m   De f i n itio n   3 . 1      P ro po s it io n   3 . 2 .    L et  r ( R )   b e   r elatio n ,   t h co n v ictio n   m e asu r o f   C FD    ( X     A k ,   t p )   o n   r   is   Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I SS N:  2 0 8 8 - 8708       A p p r o xima tio n   Mea s u r es fo r   C o n d itio n a l F u n ctio n a l D e p en d en cies U s in g   S tr ip p ed   . . . .   ( A n h   Du Tr a n )   1389   co m p u ted   by       | | | | |) | | . ( | | | . | | 1 ) , ( ] [ ] [ ] [ ] [ k p p k p p XA t X t A t X t r r r r r r r C o n v   ( 7 )     w h er Z =X   ,   Z =A k,   o r   Z =X A k   ,     w r Z p t Z p I w Z t ]) [ , ( ] [ an d   if   ( X ,   t p [ X ] )   an d   (A k ,   t p [A k ])   ar in d ep en d en t,  th e n   C o n v( ,   r)   is   eq u a l to   1 .   P r o o f .   W h av e ])) [ , ( ( k p k A t A P =1 - | | | | 1 ])) [ , s u p ( ( ] [ r r A t A k p A t k p k     an d     ])) [ , ( ]), [ , (( k p k p A t A X t X P = ])) [ , s u p ( ( X t X p   -   |) | | . ( | | | 1 ])) [ , s u p ( ( ] [ ] [ k p p XA t X t k p k r r r XA t XA   T h er ef o r Pro p o s itio n   3 . 2   ca n   b e   p r o v en   f r o m   De f in i tio n   3 . 2 .      P ro po s it io n 3 . 3 .   L et  r ( R )   b r elatio n   an d     = ( X     A k , t p ) .   T h en   th m ea s u r C o n f   is   co m p u ted   b y       | | } , | | m a x { | | | 1 ) , ( ]) [ , ( ]) [ , ( ] [ r w q I q q r r C o n f X p t X k p k p I w XA t XA X t   ( 8 )     w h er e         o t h e r w i s e r O X if I w w w r c X t X I w X t c p c X p t X p | | | | | | | | | ]) [ , ( ] [ ]) [ , (   ( 9 )   P r o o f.   Fro m   E q u atio n   2 ,   w o b tain   | | | | } | , | | m a x { | ) , ( ] [ ] [ r r r s r s s r C o n f X t X t p p           | | } | , | | m a x { | | | 1 ] [ ] [ r s r s s r X t X t p p     On   t h o th er   h an d i n   a   s i m ilar   w a y   to   th co m p u tat io n   o f   g 3   i n   [ 1 7 ] w h a v e   } | , | | m a x {| ] [ s r s s X t p ]) [ , ( } , | | m a x {| ]) [ , ( X p t X k p k I w XA t XA w q I q q .   P r o p o s itio n   3 . 3   is   th er ef o r   p r o v en .       E x a m p le  3 . 1 .   L et ' s   co m p u te  t h m ea s u r e s   S u p ,   C o n f,  an d   C onv   f o r   th   d ep en d en cies  1   an d   2   f r o m   T ab le  1 :   1   = ( A 1     A 2 ,   0   ||   1 )   2   = ( A 1     A 2 -   ||  - )   T h r o u g h   1   2   an d   T ab le  1 ,   w ca n   in f er   th co n d itio n al  p ar titi o n s   as  f o llo w s :   } , , , { 6 5 2 1 ) 0 , ( 1 t t t t I A   } , { }, , , , , { }, , , , { 11 10 9 8 7 4 3 6 5 2 1 ) , ( 1 t t t t t t t t t t t I A   } , , , { 10 5 2 1 ) 1 , ( 2 t t t t I A   } , { }, , , , , { }, , , , { 9 8 11 7 6 4 3 10 5 2 1 ) , ( 2 t t t t t t t t t t t I A   } , , { 5 2 1 ) 1 , 0 , ( 2 , 1 t t t I A A   } { }, { }, , { }, , , { }, { }, , , { 11 10 9 8 7 4 3 6 5 2 1 ) , , ( 2 , 1 t t t t t t t t t t t I A A   Fro m   th e s co n d itio n al  p ar titi o n s   an d   E q u atio n s   5 - 8 ,   w h a v e:     11 / 3 ) , ( 1 r Sup   11 / 11 ) , ( 2 r Sup   11 / 7 11 0 4 1 ) , ( 1 r   0 11 0 11 1 ) , ( 2 r   11 / 10 11 3 4 1 ) , ( 1 r C o n f   11 / 7 11 ) 1 3 3 ( 11 1 ) , ( 2 r c o n f   11 / 28 3 4 ) 4 11 .( 4 . 11 1 ) , ( 1 r C o n v   1 ) , ( 2 r C o n v   Evaluation Warning : The document was created with Spire.PDF for Python.
                    I SS N :   2 0 8 8 - 8708     I J E C E   Vo l.  7 ,   No .   3 ,   J u n 2 0 1 7   : 1 3 8 5     1 3 9 7   1390   B ec au s e 1 )) , (( )). , (( )) , , (( 2 1 2 1 A P A P A A P w i n f er   th a ) , ( 1 A   an d   ) , ( 2 A   ar in d ep en d en t.   T he r ef o r e 1 ) , ( 2 r C o n v .       T h f o llo w in g   p r o p o s itio n   ex p r ess es   an   i n ter esti n g   r el atio n s h ip   b et w ee n   t h co n f i d en ce   an d   d ep en d en c y   d eg r ee .   P ro po s it io n 3 . 4 L et   r ( R )   b r elatio n   an d     = ( X     A k , t p ) .   T h en   | | } , | | m a x { | ) , ( ) , ( ]) [ , ( ]) [ , ( r w q I q q r r C o n f X p t X k p k I w XA t XA     P r o o f.     Fro m   ( 8 ) ,   w o b tain   t h f o llo w in g   co n n ec tio n   | | } , | m a x { | | | 1 ) , ( ]) [ , ( ]) [ , ( ] [ r w q I q q r r C o n f X p t X k p k p I w XA t XA X t   | | | ) ( ]) [ , ( | | | 1 * ] [ ]) [ , ( r q X t X r p I q X t k A p t k A p   | | } , | m a x { | ) , ( ]) [ , ( ]) [ , ( r w q I q q r X p t X k p k I w XA t XA        W n ex p r esen an   e x a m p le  to   an al y ze   th r ee   m ea s u r es,  in clu d in g   d ep en d en c y   d e g r ee ,   co n f id e n ce   an d   co n v ict io n   f o r   g en er al  C F Ds.   E x a m p le   3. 2 .   L et ' s   co m p u te  t h m ea s u r e s   f o r   th f o llo w in g   d ep en d en cies f r o m   T ab le  1   1   = ( A 1     A 2 ,   0   ||   1 )   2   = ( A 1     A 2 -   ||  - )   3   = ( A 1 A 2     A 3 - , 2   ||   - )   4   = ( A 1     A 3 ,   1   ||   - )   5   = ( A 1 A 2     A 3 - , -   ||   0 )   6   = ( A 2 A 3     A 1 ,   2 , -   ||  - )   Fro m   E q u atio n s   5 7   an d   8 ,   w e   h av e   ( 1 ,   r)   =   7 /1 1   ( 2 ,   r)   =   0   ( 3 ,   r)   =   8 /1 1     C o n f ( 1 ,   r )   = 1 0 /1 1   C o n f ( 2 ,   r )   = 7 /1 1   C o n f ( 3 ,   r )   = 1 0 /1 1   C o n v ( 1 ,   r )   = 2 8 /1 1   C o n v ( 2 ,   r )   = 1   C o n v ( 3 ,   r )   = 1       ( 4 ,   r)   =   6 /1 1   ( 5 ,   r)   =   3 /1 1   ( 6 ,   r)   =   9 /1 1   C o n f ( 4 ,   r )   = 9 /1 1   C o n f ( 5 ,   r )   = 5 /1 1   C o n f ( 6 ,   r )   = 1 0 /1 1   C o n v ( 4 ,   r )   = 1   C o n v ( 5 ,   r )   = 1   C o n v ( 6 ,   r )   = 1             Re m a r k   3 . 1 .   Fro m   E x a mp l 3 . 2 ,   let' s   ev a lu ate  t h m ea s u r es  b ased   o n   th eo r y   an al y s is :   1.   T h m ea s u r C o n v   ca n n o t d ef i n h o w   m u c h   d ep en d en c y   ( o r   v io latio n )   is   t h er i n     = ( [ X c , X v   A k , t p )   w it h   th f o llo w i n g   C FD   f o r m s :     t p [A k ]   = ‘ - ,   X 2     t p [A k ]   = ‘ - ,   X c     ≠  , X v     ≠  and  6     t p [A k ]   = ‘ - ,   X 4     t p [A k ]     - ,   X 5   T o   u n r av el  th is ,   b ec au s ( X ,   t p [ X ] )   an d   (A k ,   t p [A k ])   ar in d ep en d en i n   t h ese  f o r m s ,   w in f er   th a t     th eir   C o n v   m ea s u r es  ar e   al w a y s   eq u al  to   1   ev en   w h en   a n y   v alu e s   in   d ata  t u p les  ar e   ch an g ed .   W ca n   s ee   t h is   li m ita tio n   i n   2,   3,   4,   5 ,   an d   6 .   2.     Dep en d en c y   d eg r ee     i s   to o   s t r ict  f o r   m ea s u r in g   t h ap p r o x im atio n   o f   C F Ds.   I n d ee d ,   w it h   d ep en d en c y   f r o m   E x a m p le  3 . 2 ,   w o b s er v th at  j u s f o u r   t u p les  v io lati n g   m ak e   d ep en d en c y   d eg r ee   o f   2   to   b 0 .   3.   As  s h o w n   i n   E x a m p le  3. 2   f o r   d ep en d en cies  f r o m   to   6 ,   th m ea s u r C o n f   ca n   o v er co m th e   d r a w b ac k s   o f     a n d   C o n v   f o r   g en er al  C FD s .   H o w ev er ,   t h e y   ca n n o m ea s u r t h d is tr ib u tio n   o f   d ata   tu p es i n   th co n d it io n al  eq u i v a len ce   clas s es.   I n d ee d ,   if   v alu e s   i n   t u p es  t 3   a n d   t 9   co r r esp o n d in g   to   attr ib u tes  A 3   a n d   A 2   ar ch a n g ed   f r o m   0   to   1   an d   3   to   5 ,   th en   C o n f   ( ev en     a n d   C o n v )   o f   an d   n ev er   c h an g e.   T h er ef o r e,   w p r o p o s th f o ll o w i n g   le m m an d   d ef in i tio n s   f o r   n e w   m ea s u r e.     Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I SS N:  2 0 8 8 - 8708       A p p r o xima tio n   Mea s u r es fo r   C o n d itio n a l F u n ctio n a l D e p en d en cies U s in g   S tr ip p ed   . . . .   ( A n h   Du Tr a n )   1391   Fro m   t h k n o w led g g r a n u l ar it y   o f   p ar titi o n   [ 3 3 ] ,   w in tr o d u ce   t h i n co m p let e   k n o w led g e   g r an u lar it y   o f   co n d itio n al  p ar titi o n   in d u ce d   b y   ite m s et   ( Z,  t p [ Z ] ) .   Def ini t io 3 . 6 .   L et  } ..., , { 1 ]) [ , ( l Z t Z w w I p   b co n d itio n al  p ar titi o n   w it h   t h in co m p lete   p r o b a b ilit y   d is tr ib u tio n   ) ( ..., ), ( 1 ]) [ , ( l I w P w P P Z p t Z   o n   th s et  o f   t u p es  r | | / | | ) ( r w w P i i   an d   1 ) ( ]) [ , ( Z p t Z i I w i w P .   T h en   in co m p lete  k n o w led g g r an u lar it y   o f   ]) [ , ( Z t Z p I is   d ef in ed   b y       l i i i l i i i Z t Z r w w w P w I IE p 1 1 ]) [ , ( | | | | | | ) ( | | ) (   ( 1 0 )   L e mm a   3 . 1 .    L et  r ( R )   b r elatio n     ( X     A k ,   t p )   h o ld s   o n   r   i f   a n d   o n l y   i f   ) ( ) ( ]) [ , ( ]) [ , ( k p k p XA t XA X t X I IE I IE   P r o o f.   W d em o n s tr ate   th at   ) ( ) ( ]) [ , ( ]) [ , ( k p k p XA t XA X t X I IE I IE   if   an d   o n l y   if   t h er is   th e   s a m e   d is tr ib u tio n   o f   t h tu p les  r   i n to   class es  ]) [ , ( X t X p I w   an d   ]) [ , ( k p k XA t XA I q   r esp ec tiv el y ,   i . e ,   f o r   an y ]) [ , ( X t X p I w ,   th er ex is t s   ]) [ , ( k p k XA t XA I q   s u c h   th at  q w ,   i.e ,     h o ld s   o n   r .     L e m m 3 . 1   is   th er ef o r e   p r o v en .         Fro m   L e m m 3 . 1 ,   d is tr ib u tio n   er r o r   d eg r ee   o f     ca n   b ex p r ess ed   b y       ) ( ) ( ) ( ) , ( ]) [ , ( ]) [ , ( ]) [ , ( X t X XA t XA X t X E p k p k p I IE I IE I IE r   ( 1 1 )   T h en   w h av n e w   m ea s u r f o r   C FD a s   f o llo w s   Def ini t io 3 . 7 L et   r ( R )   b a   r elatio n   a n d     =   ( X     A k ,   t p ) .   n e w   m ea s u r e,   ca lled   d is tr ib u tio n   d ep en d en c y   d eg r ee ,   is   d ef in ed   b y :   o t h e r w i s e I if I IE I IE r r X t X X t X XA t XA E D p p k p k 0 0 | | ) ( ) ( ) , ( 1 ) , ( ]) [ , ( ]) [ , ( ]) [ , (   ( 1 2 )   E x a m p le  3 . 3 .   Fro m   E x a m p le  3 . 2 ,   w h a v D ( 2 ,   r)   =   5 /9   an d   D ( 4 ,   r )   1 3 /2 5 .   I f   w c h an g d ata   v alu e s   as i n   R e m ar k   3 . 1   ( 3 . ) ,   t h en   D ( 2 ,   r )   = 2 3 /4 5   an d   D ( 4 ,   r )     = 1 1 /2 5 .   W s ee   th at  th b ig g er   m ea s u r D th b ig g er   d ep en d en c y   p r o b a b ilit y   o f   I f   D ( ,   r )   1 ,   th en     b ec o m e s   C FD.  T h er ef o r D   ca n   b u s ed   to   m ea s u r t h ap p r o x i m a tio n   o f   AC FD s .   Mo r eo v er ,   D   ca n   m ea s u r t h d is tr ib u tio n   d eg r ee   o f   d ata  tu p les  b ased   o n   th co n d itio n al  d ep en d en c i es   as  i n d ica ted   i n   f o llo w in g   e x a m p le.   T ab le  2 .   A   d ata  tab le  o f   p atien ts     N a me   S y mp t o m   D i se a se   t 1   N 1   1   1   t 2   N 2   1   2   t 3   N 3   1   3   t 4   N 4   2   2   t 5   N 5   2   2   t 6   N 6   2   2   t 7   N 7   1   4   t 8   N 8   1   5   t 9   N 9   3   1   t 10   N 10   2   3   t 11   N 11   2   4   t 12   N 12   3   1   t 13   N 13   3   1   t 14   N 14   2   1   t 15   N 15   3   1       Evaluation Warning : The document was created with Spire.PDF for Python.
                    I SS N :   2 0 8 8 - 8708     I J E C E   Vo l.  7 ,   No .   3 ,   J u n 2 0 1 7   : 1 3 8 5     1 3 9 7   1392   E x a m p le  3 . 4 L et    r ( R )   b r elatio n     as T ab le  2   W ith   11  ( S ymp to   Dis ea s e, 1   ||   - ) ,   12  =   ( S ymp to   Dis ea s e,   2   ||   - ) ,   an d   13  =    ( S y mp to   Dis ea s e,   3   ||   - )   in   T ab le  2 ,   w e   h av D ( 11 ,   r )   1 /5 ,   D ( 12 ,   r )   1 /3 ,   an d   D ( 13 ,   r ) =1 .   If  v alu e s   i n   t u p es  t 10   an d   t 11   co r r esp o n d in g   to   Dis ea s attr ib u te   ar ch a n g ed   f r o m   3   to   1   an d   4   to   2 ,   th en   D ( 12 ,   r )   = 5 /9 .   W o b s er v th at  th n ea r er   t h m ea s u r D ( 1i ,   r )   is   to   1 ,   th b ig g er   th ce n tr alize d   d is tr ib u tio n   o f     th p atien t s   i n   i r 1 in to   o n o r   m o r e   d is ea s e s   is .   W n o w   p r o p o s th co m p u ta tio n   f o r   m ea s u r es  b ased   o n   th s tr ip p ed   c o n d itio n al  p ar titi o n   to   r ed u ce   th co m p u tatio n al  t i m i n   d is c o v er in g   A C FDs .     Def ini t io 3 . 8 L et  r ( R )   b r elatio n   an d   le ( Z,  t p [ Z ] )   b an   ite m s et  s u c h   t h at      R .   A   s tr ip p ed   co n d itio n al  p ar titi o n   of   ]) [ , ( Z t Z p I   ,   d en o ted   ]) [ , ( ˆ Z t Z p I   is   d ef in ed   b y       } 1 | | | { ˆ ]) [ , ( ]) [ , ( w I w I Z t Z Z t Z p p   ( 1 3 )   B ased   o n   th s tr ip p ed   co n d itio n al  p ar titi o n ,   f o r   an y   ite m s et   ( Z,  t p [ Z ] ) ,   w h er     an d       R ,   if   1 | | ] [ Z t p r ,   th en   w h av t h f o llo w in g   d ef i n itio n s ,   p r o p o s itio n s ,   an d   le m m as.   Def ini t io 3 . 9 L et  r ( R )   b r elatio n .   T h en ,   th s u p p o r o f     is   co m p u ted   ac co r d in g   E q u atio n   1 w h er | | p t r is   d ef i n ed   b y       o t h e r w i s e r O Z if XA Z I w w r r c k Z t Z XA t t c p c k p p | | , ˆ | | | | | | | ]) [ , ( ] [   ( 1 4 )   P ro po s it io 3 . 5 T h in co m p l ete  k n o w led g g r a n u lar it y   o f   ]) [ , ( Z t Z p I is   d ef i n ed   b y       | | ) 1 | (| | | | | 1 ) ( ]) [ , ( ˆ ] [ ]) [ , ( Z p t Z p p I w Z t Z t Z r w w r I IE   ( 1 5 )   P r o o f.   Fro m   E q u atio n   3   an d   1 3 ,   w i n f er   th a ]) [ , ( ˆ ] [ | | | | Z p t Z p I w Z t w r is   th e   n u m b er   o f   s in g l e   co n d itio n al  eq u i v ale n ce   clas s e s   r e m o v ed   f r o m   th co n d i t io n a l p ar titi o n ]) [ , ( Z t Z p I .   Hen ce ,       | | ) 1 | (| | | | | | | | | | | ] [ ˆ ˆ ] [ 2 ˆ 2 ]) [ , ( ]) [ , ( ]) [ , ( ]) [ , ( Z t I w I w Z t I w I w p Z p t Z Z p t Z p Z p t Z Z p t Z r w w w r w w ( 1 6 )   P r o p o s itio n   3 . 5   is   th er ef o r e   p r o v en .      No w   t h r o u g h   t h s tr ip p ed   co n d itio n al  p ar titi o n s ,   th n e w   m ea s u r D   ca n   b co m p u ted   u s in g   E q u atio n s   1 2 ,   1 4 ,   an d   15.     T h co m p u ta tio n   o f   C o n f    is   b ased   o n   P r o p o s itio n   3 . 6   as f o llo w s   P ro po s it io 3 . 6 .   L et     r ( R )   b e   r elatio n   a n d     ( X     A k ,   t p )   w h er     R ,     A k     R .   T h en ,   th e   co n f id e n ce   m ea s u r C o n f   o f     is   d ef in ed   b y   o t h e r w i s e r r r A t if r w f r Conf k p p X p t X XA t X t k p I w | | | | | | 1 ' ' ] [ | | ) ( 1 ) , ( ] [ ] [ ˆ ]) [ , (   ( 1 7 )   w h er e   o t h e r w i s e w w q t h a t s u c h I q e x i s t s t h e r e if I q q w w f k p k k p k XA t XA XA t XA 1 | | ˆ } ˆ | | m a x { | | | ) ( ]) [ , ( ]) [ , (   Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I SS N:  2 0 8 8 - 8708       A p p r o xima tio n   Mea s u r es fo r   C o n d itio n a l F u n ctio n a l D e p en d en cies U s in g   S tr ip p ed   . . . .   ( A n h   Du Tr a n )   1393   | | ] [ X t p r an d   | | ] [ k p XA t r   ar co m p u ted   b ased   o n   E q u atio n   1 4.   P r o o f.   I f   t p [A k ]   - ,   th en   f o r   an y   eq u iv ale n ce   cla s s   ]) [ , ( X t X p I w ,   th er ex is t   th eq u iv a len ce   class es   ]) [ , ( k p k XA t XA I q   s u c h   t h at  q w k XA p t k XA I q ]) [ , ( On   th e   o th er   h an d ,   f o r   an y ]) [ , ( X t X p I w ,   if   ca r d in alit y   o f   w   is   eq u al  to   1   an d   t i     w   t h e n   t i   al w a y s   s atis f ie s     ( X     A k ,   t p ) .   He n ce ,   f o r   an y ]) [ , ( ˆ X t X p I w ,   if   th er ex i s ts   ]) [ , ( ˆ k p k XA t XA I q   s u ch   t h at      w ,   th en   t h n u m b er   o f   t u p le s   in   w   v io lati n g   C FD    is } , ˆ | | m a x {| | | ) ( ]) [ , ( w q I q q w w f k p k XA t XA .   Oth er w is e,   q   w a s   r e m o v ed   f r o m   t h co n d itio n al   p ar titi o n ]) [ , ( k p k XA t XA I .   T h u s ,   f( w ) = | w |   -   1 .   If   t p [A k ]     - ,   th en   f o r   an y   ]) [ , ( X t X p I w ,   if   th er ex i s ts   ]) [ , ( k p k XA t XA I q   s u ch   t h at      w ,   th e n   q   is   u n iq u e.   Hen ce ,       | | | | | | 1 | | | | | | 1 ) , ( ] [ ] [ ]) [ , ( ]) [ , ( r r r r q w r C o n f k p p X p t X k XA p t k XA XA t X t I w I q   P r o p o s itio n   3 . 6   is   th er ef o r e   p r o v en .          4.   T H E   DI SCO V E RY  P RO B L E M   O F   ACF Ds   L et  S u p Th r   b s u p p o r t th r esh o ld ,   C FD    ( X     A k , t p )   i s   f r eq u e n t i f   s u p ( , r )   SupT hr     [9 ]   As in tr o d u ce d   in   [ 1 3 ] ,   w ith   c o n f id e n ce   th r es h o ld   C o n fTh r ,   th AC FD     ( X     A k , t p )   h o ld s   o n   th e   r elatio n   r   ( o r   ap p r o x i m atel y   s atis f ie s   ,   d e n o ted   r   |= Conf  )   if   a n d   o n l y   i f   C o n f( ,   r )      C o n fTh r .   T h en     ( X     A k ,   t p )   is   m i n i m al  if   1 )   , X A k 2 )   f o r   an y   p r o p er   s u b s et  , X Y , ( | k C o n f A Y r ]), [ || ] [ k p p A t Y t an d   3 )   f o r   an y   p atter n   t u p le p s w h er p p s t  ) || ] [ , ( | X s A X r p k C o n f .   P ro ble m   1 .   L et  r ( R )   b r elatio n .   T h d is co v er y   p r o b lem   o f   A C FDs   is   to   d is co v er   th f r e q u en an d   m i n i m al  A C FDs   o n   r .   T h r ig h t   -   h a n d   -   s id ( R H S )   ca n d id ate  s et   o f   ( X ,   s p ) ,   d en o te d   C + ( X   , s p ) ,   is   u s ed   to   ch ec k   m i n i m alit y   o f   d ep en d en cie s   a n d   p r u n t h s ea r ch   s p ac o f     d is co v er y   alg o r ith m s   o f   C FDs   an d   A C FDs   ( C T A NE   a n d   ap p o x C T A N E )   b ased   o n   attr ib u te - s et/p atter n   lattice   T o   d is co v er   th f r eq u en an d   m i n i m al  AC FD s   o n   r ,   t h al g o r ith m   ap p o x C T A NE   [ 1 3 ]   s tar ts   f r o m   a   s et   L 1 = { ( A k , -   | A k     R   { ( A k , a s u p ( A k , a   S u p T h r ,   A k     R ,   a     dom ( A k )   }   an d   g e n er ates  L 2   f r o m   L 1 ,   L 3   f r o m   L 2 ,   …in   w h ich ,         is   th s et  o f   ite m s ets  ( X , s p )   s u c h   th at  th ca r d in alit y   o f   is   eq u al  to     .   Fo r   ea ch   ite m s et  ( X , s p     th e   R HS  ca n d id ate  s et  C + ( X   , s p )   is   co m p u ted   b y   in ter s ec tio n   o f   R HS   ca n d id ate  s e ts   C + (X \ A k   ,s p [X \ A k ] )   f o r   an y   A k X .   T h en   t h d ep en d en c y     ( X \ A k     A k ,   s p [X \ A k ] | |s p [A k ])   is   m i n i m al  if   an d   o n l y   if   ( A k ,   s p [ A k ])    C + ( X   , s p ) .   Fro m   th a t,  to   m in th f r e q u en a n d   m i n i m a AC FD s   o n   r ,   ap p o x C T A N E   ch ec k s   t h d ep en d en c ies    ( X \ A k     A k ,   s p [X \ A k ] ||   s p [A k ])   s u c h   t h at  ( A k s p [A k ]   C + ( X   , s p ) ,   ( X ,   s p         an d   A k     X L e t   u p     b a n y   tu p le  p atter n   s u c h   t h at  u p [ A k ]   s p [A k ]   o r     -    ,   an d   u p [ X \ A k   s p [ X \ A k ]   .   I f   C o n f( ,   r )     C o n fTh r ,   th e n   o u tp u t   ,   a n d   r e m o v ( A k , )   f r o m   C + ( X ,   u p f o r   ev er y   ( X ,   u p         w h er e   ’  d en o tes     a ll   v alu e s   f o r   A k ,   in clu d i n g   t h v ar iab le   .     I f   C o n f( ,   r ) =0 ,   th en   re m o v e   ( A p )   f ro m   C + ( X   , u p )   f o e v e r y   A p   ∈  R \ X a n d   ( X ,   u p       .   Nex t,  th alg o r ith m   r e m o v e s   ite m s ets  ( X   , s p )   f r o m          s u ch   th at  C + ( X   , s p )   is   e m p t y .   T h i s   p r o ce s s   is   p er f o r m ed   f o r   th n ex lev e ls                       , …  u n til t h er ex i s t s   q   s u c h   t h at         is   e q u al  to   e m p ty .   R ea d er s   ca n   r ef er   C + ( , s p )   an d   th e   alg o r ith m s   C T A NE   a n d   ap p o x C T A NE   in   t h p ap er s   [ 9 ] [ 1 3 ].   No w ,   let  r ( R )   b r elatio n   an d   let  ( X ,   t p )   a n d   ( Y,  s p )   b t w o   ite m s ets  s u c h   th a 0 | | p t r an d 0 | | p s r T h en ,   th ite m s et  ( Z,  u p i s   g e n er ated   f r o m   ( X ,   t p )   a n d   ( Y,  s p )   s u c h   th at   Z =  X Y   an d     0 | | ) , ( ] [ ] [ 0 | | ]) [ , ( Y X if s t Y X s Y X t and Y X if Y X Y s t s t u p p p p p p p p p   A cc o r d in g   to   th p r o d u ct   o f   t w o   p ar titi o n s   i n   [ 9 ]   an d   [ 1 7 ] ,   th f o llo w i n g   le m m as  h o ld   b ase d   o n   th e   co n d itio n al  p ar titi o n s   an d   s tr ip p ed   co n d itio n al  p ar titi o n s .   L e mm a   4 . 1 .   T h co n d itio n al  p ar titi o n   ) , ( p u Z I is   co m p u ted   b y   ) , ( ) , ( ) , ( . p p p s Y t X u Z I I I     Evaluation Warning : The document was created with Spire.PDF for Python.
                    I SS N :   2 0 8 8 - 8708     I J E C E   Vo l.  7 ,   No .   3 ,   J u n 2 0 1 7   : 1 3 8 5     1 3 9 7   1394   w h er e   } 0 | | , , | { . ) , ( ) , ( ) , ( ) , ( q w I q I w q w I I p p p p s Y t X s Y t X   L e mm a   4 . 2 .   A s s u m th at  1 | | p t r 1 | | p s r an d   1 | | p u r T h en   th s tr ip p ed   co n d itio n al  p ar titi o n   ) , ( ˆ p u Z I is   co m p u ted   b y   ) , ( ) , ( ) , ( ˆ . ˆ ˆ p p p s Y t X u Z I I I   w h er e   } 1 | | , ˆ , ˆ | { ˆ . ˆ ) , ( ) , ( ) , ( ) , ( q w I q I w q w I I p p p p s Y t X s Y t X   L e m m a s   4 . 1   an d   4 . 2   ar u s e d   to   co m p u te  t h p r o d u cts  o f   t w o   co n d itio n al   p ar tit i o n s   a n d   s tr i p p ed   co n d itio n al  p ar titi o n s   f o r   th it e m s et s   in   t h le v els  L 2 ,   L 3 , … o f   th attr ib u te - s et/p atter n   la tti ce .   T h r esu lts   i n   Sec tio n   3   an d   4   allo w   u s   e f f ec tiv e l y   i m p r o v th co m p u tatio n   ti m f o r   t h C FD  a n d   AC FD   d is co v er y   al g o r it h m s .   T h ese  r es u lt s   ar al s o   u s e d   to   ev al u ate   th e   li m itat io n s   o f   t h m ea s u r es   ( d ep en d en c y   d eg r ee ,   co n v icti o n   an d   co n f id en ce i n   g e n er a C FD s   an d   t h u tili t y   o f   t h e   p r o p o s ed   m ea s u r e   ( D ).     5.   RE SU L T S AN D I SCU SS I O N   T h is   s ec tio n   e v al u ates  t h e f f ec tiv e n e s s   o f   t h s tr ip p ed   co n d itio n al  p ar titi o n   f o r   t h e   d is co v er y   alg o r ith m   o f   AC FD s   b ased   o n   th co n f id en ce   m ea s u r an d   t h u ti lit y   o f   n e w   m ea s u r ( D ).   B ased   o n   th alg o r ith m   ap p o x C T A NE   [ 1 3 ] ,   th alg o r ith m s   t h a d is co v er   AC FD s   u s i n g   t h e   co n d itio n al  p ar titi o n s   ( C P s )   an d   s tr ip p ed   co n d itio n al  p ar titi o n s   ( S CP s )   ar ca lled   C P - ap p o x C T ANE   an d   SC P - ap p o x C T A NE ,   r esp ec tiv el y .     CP - ap p o x C T A NE   al g o r ith m   m i n es  t h AC FD s   th r o u g h   t h p r o d u ct  o f   C P s     ( L e m m 4. 1 )   an d   th e   co m p u tatio n s   o f   t h s u p p o r an d   co n f id en ce   o f     u s i n g   C P s   ( Def i n it i o n   3 . 1   an d   P r o p o s itio n   3 . 3 ) .   W h ile  th d is co v er y   o f   SC P - ap p o x C T ANE    is     b ased   o n   t h e   p r o d u ct  o f   S C P s   ( L e m m 4 . 2 )   an d   t h e   co m p u tat io n s   o f   t h e   s u p p o r t a n d   co n f id e n ce   o f     u s in g   S C P s   ( Def i n it i o n   3 . 1 ,   Def in it i o n   3 . 9   an d   P r o p o s itio n   3 . 6 ).     T ab le  3 .   A   d escr ip tio n   o f   d ata  s ets     D a t a se t   #   o f   a t t r i b u t es   #   o f   t u p l e s   1   S y n t h e t i c   d a t a se t s   6 - 12   5 0 0 0 0 0   2   B l o o d   T r a n sf u s i o n   5   7 4 8   3   N u r se r y   9   1 2 9 6 0   4   C h e ss   7   2 8 0 5 6   5   C a r   Ev a l u a t i o n   7   1 7 2 8     W ith   th s y n t h etic  a n d   r ea d ata  s ets ,   as  s h o w n   i n   T ab le  3 ,   t h ex p er i m en t s   ar co n d u ce d   u n d er   t h e   CP - ap p o x C T A NE   a n d   SC P - ap p o x C T A NE   alg o r it h m s .   T h ese  al g o r ith m s   ar i m p le m en ted   in   R   o n   a   co m p u ter   w it h   3 . 5   GHz   I n tel  C o r i7   p r o ce s s o r   an d   8 GB   m e m o r y .   T h s y n t h etic  d ata s ets   s et s   a r g e n er ated   r an d o m l y   b y   v a r y in g   th e   n u m b er   o f   d is ti n ct   v al u es   o f   attr ib u tes   ( N DV ) ,   t h n u m b e r   o f   t u p les   ( |r| ) ,   t h n u m b er   o f   a ttrib u te s   ( a r ity ) ,   a n d   t h s u p p o r th r es h o ld   ( S u p Th r ) .   N o te  th at  attr ib u tes  p er   d ata  s et  h av th s a m N D V.   T o   ev alu ate  t h e   e f f ec tiv e n e s s   o f   s tr ip p ed   co n d itio n al   p ar titi o n s   f o r   d is co v er y   al g o r it h m s ,   t h e   ex p er i m e n ts   ar c ar r ied   o u t a s   f o llo w s :   o   W f ix   C o n fTh r |r| a r ity   a n d   S u p Th r   eq u al  to   0 . 8 ,   5 0 0 0 0 0 ,   6 ,   an d   1 0 0   r esp ec tiv el y .   N DV   is   v ar ied   f r o m   1 0 0   to   5 0 0 .   o   Fix i n g   C o n fTh r N V D ,   a r ity   a n d   S u p Th r     eq u al  to   0 . 8 ,   1 0 0 ,   6   an d   0 . 0 0 1     r esp ec tiv el y ,   w v ar y   |r|   f r o m   1 0 0 k   to   5 0 0 k .   o   W ith   S u p Th r   =   0 . 0 0 5 ,   C o n fTh r   =   0 . 8   an d   N DV   =   2 0 ,   a r ity   is   v ar ied   f r o m   6   to   1 2 .   o   W ith   |r|   =   5 0 0 k ,   a r ity   6 ,   N DV   =   1 0 0 ,   w v ar y   S u p Th r   f r o m   0 . 0 0 1   to   0 . 1 .   As  s h o w n   i n   Fi g u r e s   1   an d   2 SC P - ap p o x C T A NE   o u tp er f o r m s   C P - ap p o x C T A NE   w it h   in cr ea s i n g   th n u m b er   o f   d i s ti n ct  v al u es,  ar it y   as  w ell  a s   th n u m b er   o f   tu p les a n d   d ec r ea s in g   t h s u p p o r t th r esh o ld s .     Si m i lar l y ,   w ca n   ap p l y   L e m m 4 . 2   an d   L e m m 3 . 1   ( th in co m p lete  k n o w l ed g g r a n u lar it y   o f   S C P s   f o r   C FD  )   an d   P r o p o s itio n   3 . 5   to     r e d u ce   th d is co v er y   ti m o f   C FD s   f o r   C T A NE   al g o r it h m   i n   t h p ap er   [ 9 ] .   Evaluation Warning : The document was created with Spire.PDF for Python.