I AE I nte rna t io na l J o urna l o f   Art if icia l In t ellig ence   ( I J - AI )   Vo l.   5 ,   No .   2 J u n e   2016 ,   p p .   6 4 ~ 71   I SS N:  2252 - 8938           64       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 J A I   An SV D bas ed  Re a l Coded  G ene tic  Alg o rith m  f o G r a ph   Clustering       P a rt ha j it   Ro y * J . K .   M a nd a l **   D e p a rt m e n o f   Co m p u ter S c ien c e ,   t h e   Un iv e rsity   o f   Bu rd wa n   * *   De p a rt m e n o f   C o m p u ter S c ien c e   &   En g in e e rin g ,   t h e   Un iv e rsity   o f   Ka l y a n i       Art icle  I nfo     AB ST RAC T   A r ticle  his to r y:   R ec eiv ed   Ma r   4 ,   2 0 1 6   R ev i s ed   Ma y   8 ,   2 0 1 6   A cc ep ted   Ma y   2 5 ,   2 0 1 6       T h is  p a p e p ro p o se a   n o v e g ra p h   c lu ste rin g   m o d e b a se d   o n   g e n e ti c   a lg o rit h m   u sin g   a   ra n d o m   p o in t   b ip a rti te  g ra p h .   T h e   m o d e u se ra n d o m   p o i n ts  d istri b u ted   u n if o rm l y   in   th e   d a ta  sp a c e   a n d   th e   m e a s u re m e n o f   d istan c e   f ro m   th e se   p o in ts  t o   th e   tes p o i n ts  h a v e   b e e n   c o n sid e re d   a p ro x im it y .   Ra n d o m   p o i n ts  a n d   t e st  p o i n ts  c re a te  a n   a d jac e n c y   m a t rix .   T o   c re a te  a   si m il a rit y   m a tri x ,   c o rre latio n   c o e f f icie n ts  a re   c o m p u ted   f ro m   th e   g iv e n   b ip a rti te  g ra p h .   T h e   e ig e n v e c to rs  o f   th e   sin g u lar  v a lu e   d e c o m p o siti o n   o f   th e   w e i g h ted   sim il a rit y   m a tri x   a re   c o n sid e re d   a n d   th e   sa m e   a r e   p a ss e d   to   a n   e li ti st  GA   m o d e f o id e n ti fy i n g   th e   c lu ste c e n ters .   T h e   m o d e h a b e e n   tas ted   w it h   th e   sta n d a rd   d a tas e ts  a n d   th e   p e rf o r m a n c e   h a b e e n   c o m p a re d   w it h   e x isti n g   sta n d a rd   a lg o rit h m s.   K ey w o r d :   B ip ar tite G r ap h   C lu s ter   A n a l y s is   C lu s ter   Valid it y   I n d ex   Gen etic  A l g o r ith m   Gr ap h   C l u s ter i n g   Sin g u lar   Valu Dec o m p o s itio n   Co p y rig h ©   2 0 1 6   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 :   P ar th aj it R o y   Dep ar t m en t o f   C o m p u ter   Scie n ce ,     T h Un iv er s i t y   o f   B u r d w a n   I n d ia - 713104     E m ail:  r o y . p ar th aj it@ g m ail. co m       1.   I NT RO D UCT I O N   C lu s ter i n g   is   g r o u p in g   o f   o b j ec ts   th at  h o n o r s   o n l y   t h u n d er ly i n g   p r o x i m it y   a m o n g   t h o b j ec ts .   C lu s ter i n g   is   a n   u n s u p er v is ed   NP - h ar d   g r o u p in g   p r o b le m .   T h er ar e   s ev er al  m eth o d s   o f   clu s ter i n g   av ailab le   in   liter at u r e.   T h p er f o r m a n ce   an al y s is   o f   s ta n d ar d   clu s ter i n g   m o d els h a s   b ee n   p r o p o s ed   b y   Xu   et  al  [ 1 ]   w h er as c lu s ter in g   an d   it s   u n d er l y i n g   alg eb r is   co v er ed   b y   E v er it t   et  al  [ 2 ] .     Gr ap h   is   r ep r esen tatio n   w h i ch   m o d els  t h e   o b j ec ts   an d   t h e ir   r elatio n s h ip .   T h o b j ec ts   ar g e n er all y   r ep r esen ted   as  v er tices  o r   n o d es  o f   t h g r ap h   a n d   t h r elatio n s h ip s   b et w ee n   t w o   o b j ec ts   ar r ep r esen ted   u s in g   ed g es.  Gr ap h   th eo r y   d o es  n o i m p o s a n y   r estrictio n   o n   t h n atu r e   o f   th e   r elatio n s h ip .   An y   r elatio n   t h at  e x i s ts   in   th r ea w o r ld   ca n   b in co r p o r ated   as  r elatio n s h ip .   T h alg eb r aic  s tr u ct u r es  b eh i n d   g r ap h s   ar co v er ed   b y   Go d s il a n d   R o y le  [ 3 ] .     C lu s ter i n g   o n   g r ap h   h as  g ai n ed   en o r m o u s   p o p u lar it y   n o w   d ay s .   I n   ca s o f   g r ap h   clu s ter in g ,   t h d ata  o b j ec ts   ar r ep r esen ted   in   ter m s   o f   v er tice s   an d   t h p r o x i m itie s   ar r ep r esen ted   i n   ter m s   o f   ed g e s .   i.e .   t w o   n o d es  ar i n   p r o x i m it y   i f   th er ex i s ts   an   ed g b et w ee n   th e m .   I n   ca s e   o f   w ei g h ted   g r ap h ,   th e   w ei g h t   m atr ix   i s   also   co n s id er ed   f o r   p r o x i m it y   m ea s u r es.  T h i s   m ea n s ,   t h e x i s ten ce   o f   a n   ed g i s   n o s u f f ici en t,  t h s m aller   t h e   ed g w ei g h t,  th clo s th o b j ec ts   ar e.   On ce   th p r o b lem   h as  b ee n   ca s ted   to   g r ap h   m o d el  b y   r ep r esen ti n g   th d ata  p o in ts   i n to   o b j ec ts   an d   th e   d is ta n ce   b et w ee n   o b j e cts  u s i n g   t h ed g e s ,   t h s ta n d ar d   g r ap h   t h eo r etic   m et h o d s   ar u s ed   f o r   cl u s ter i n g   d ata  p o in ts .   c o n n ec ti v it y   b ased   g r ap h   cl u s ter i n g   h a s   b ee n   p r o p o s ed   b y   Har tu v   an d   S h a m ir   [ 4 ] .   An   w e b   b ased   ap p licatio n   is   m ad b y   He  et  al   [ 5 ] .   A   s u r v e y   o n   g r a p h   b ased   clu s ter in g   is   d o n b y   Sch ae f f er   [ 6 ] .     T h p ap er   u s es  a   b ip ar tite  g r ap h   b ased   d ata  cl u s ter i n g   m e th o d   w h e r e   b ip ar tite  g r ap h   h as   b ee n   cr ea ted   f r o m   t h d ata  p o in t s   b y   tak in g   s o m e x tr r an d o m   p o in ts .   T h p r o x i m it y   o f   th e   s a m p le  p o i n ts   ar e   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - AI     I SS N:  2252 - 8938       A n   S V b a s ed   R ea l Co d e d   Ge n etic  A lg o r ith fo r   Gra p h   C lu s teri n g   ( P a r th a jit R o y )   65   ca lcu lated   b ased   o n   t h eir   s i m i lar it y   to w ar d s   t h b ip ar tite  g r ap h .   A   g o o d   liter atu r is   a v ai lab le  o n   g r ap h   a n d   th b ip ar tit d u to   B o llo b ´ as [ 7 ] .     Sin g u lar   v alu d ec o m p o s itio n ( SVD)   is   f ac to r izatio n   o f   m atr ices  ( n o n ec ess ar il y   s q u ar e )   w h er m atr i x   is   d iv id ed   in to   th r ee   m atr ices  o f   w h ic h   t w o   ar o r th o g o n al  s q u ar m atr ices  a n d   th e   o th er   is   d iag o n al  m atr i x   ca r r ies  th eig e n v al u es .   SVD  is   m ai n l y   u s ed   f o r   d im en s io n alit y   r ed u ctio n .   So m w o r k   o n   S VD  b ased   d i m en s io n al it y   r ed u ctio n   is   d o n b y   P r ab h u ,   an d   An b az h a g an   [ 8 ] .   SVD  b ased   d o cu m e n clu s ter i n g   h as  b ee n   co n s id er ed   b y   Dh illo n   [ 9 ] .   So m ea r lier   w o r k   o n   s i n g u lar   v alu b ased   g r a p h   cl u s ter i n g   is   d o n b y   Dr in ea s   et   al[ 1 0 ] .   Gen etic  A l g o r ith m   i s   a   m o d er n   h e u r is tic  s ea r ch i n g   t o o w h ic h   i s   ap p licab le  w h en   th s ea r c h   s p ac is   h u g an d   t h ex ac s o lu t io n   o f   th p r o b lem   i s   NP - h ar d .     Gen etic  al g o r ith m   o f te n   g e n er ates  p o o o f   p o s s ib le  f ea s ib l s o lu tio n s   ca lled   th ch r o m o s o m es  a n d   allo w s   th e m   to   g e n er ate  o f f s p r in g   s o lu t io n s   b y   m ati n g .   T h o f f s p r in g   o f   g o o d   s o lu tio n s   ar lik el y   to   b b etter .   T h is   ass u m p t io n   i s   t h f u n d a m en tal  o f   g e n etic  al g o r ith m .   T h tar g e t o f   t h g e n etic  al g o r ith m   is   to   o p ti m ize  a n   o b j ec tiv f u n ctio n   to   r ea ch   to   b etter   s o lu tio n .   A   n o v e eliti s G A   m o d el  is   p r o p o s ed   b y   Deb   et  al  [ 1 1 ] .   T h g en et ic  alg o r it h m   b ased   clu s t er in g   tec h n iq u ar d is c u s s ed   b y   Ma u li k   et  al  [ 1 2 ]   b u w o r k   d o es  n o co n s id er   g r ap h   b ased   clu s ter in g r at h e r   it  co n s id er s   f u zz y   clu s ter i n g   o n   i m a g d ata.   So m m o r g en et ic  alg o r it h m   b ased   clu s ter i n g   is   p r o p o s ed   b y   C h [ 1 3 ]   w h er ea s   s o m ap p licatio n   o f   cl u s ter i n g   in   g e n eti alg o r ith m   is   d u e   to   Kala   et  a [ 1 4 ] .   T h is   p ap er   p r o p o s es  s in g u lar   v al u e   d ec o m p o s i tio n   b a s e d   g e n etic   al g o r ith m   m o d el  f o r   clu s ter i n g   b ip ar tite g r ap h .     T h p ap er   is   o r ien ted   as  f o llo w s .   Sectio n   2 .   d is c u s s es  t h n ec ess ar y   m at h e m atics  u s ed   in   th m o d el.   Sectio n   3 .   p r o p o s es  t h m o d el.   T h ex p er i m e n tal   s et u p   h a s   b ee n   co v er ed   i n   s ec ti o n   4 .   w h er ea s   t h e   p er f o r m a n ce   o f   th p r o p o s ed   m o d el  h as  b ee n   tas ted   an d   an al y ze d   i n   s ec tio n   5 . .   C o n c l u s io n s   ar g iv e n   i n   s ec tio n   6 .   an d   th r e f er en ce s   c o m at  t h e n d .       2 .   T H E   M AT H E M AT I CAL  B ACK G RO UND S     Gen etic  al g o r ith m   is   s ea r ch   b ased   o p tim iza tio n   tec h n iq u f o r   NP - h ar d   p r o b lem s .   Gen etic  alg o r ith m   is   i n s p ir ed   b y   t h b io lo g ical  g e n etics  w h er t h ch r o m o s o m o f   th p ar en t s   d ec id es  th n a tu r o f   th eir   o f f s p r i n g .   I is   al s o   b eliev ed   th at  t h g o o d   f ea tu r es  o f   b o th   th p ar en t s   in h er it  to   th e   o f f s p r in g   a n d   th e   o f f s p r in g   m a y   s u p er io r   th an   it s   p ar en ts .   T h ch r o m o s o m c o n s is ts   o f   s e v er al  g e n e s .   E ac h   g en i s   r esp o n s ib le   f o r   s o m p r o p er ty   o f   t h o f f s p r in g .   P r o p er ties   lik h air   co lo r ,   s h ap o f   n o s etc  ar d u to   g e n e.     I n   g e n etic   alg o r it h m ,   t h s a m co n ce p t   h a s   b ee n   in h er it ed .   E v er y   i n d iv id u al  co m p o n en o f   t h e   s o lu tio n   is   e n co d ed   in   g e n an d   ch r o m o s o m is   f o r m ed   f r o m   th g e n s et s .   E ac h   c h r o m o s o m is   ca n d id ate  s o lu tio n   o f   t h g i v en   p r o b lem .   I n   g en et ic  al g o r ith m ,   a   n u m b er   o f   s u c h   s o l u tio n s   ar cr ea ted   as  i n itia p o p u latio n .   T h p o p u latio n   i s   allo w ed   f o r   cr o s s b r ee d in g ,   ca l led   cr o s s o v er .   I n   s u c h   ca s e,   p a ir s   o f   c h r o m o s o m e   ar ch o s e n   f o r   m at in g .   T h r e s u lt   is   t h cr ea tio n   o f   n e w   o f f s p r in g .   T h o f f s p r in g   ar e   th e n   p ass e d   to   a   f i tn e s s   f u n ctio n   f o r   th eir   f it n es s   o r   clo s en e s s   to w ar d s   t h o p ti m al  s o lu tio n .   Fo r   t h is ,   a n   o b j ec tiv f u n ctio n   i s   d eter m in ed   an d   th ch ar ac ter i s tics   o f   t h o f f s p r in g   ar m ea s u r ed .   Usi n g   th r u le  o f   s u r v i v al  o f   th f itte s t,  th e   elitis m   m o d el  o f   t h G A   s e lec ts   b est  n   ch r o m o s o m f r o m   t h cu r r en p o o an d   r est  f r o m   t h o f f s p r i n g .   I n   th is   w a y   th s o lu tio n   s et  ev o l v es.   Du r in g   th i s   ev o l u tio n ,   s o m g en m a y   g et  ch a n g ed   r an d o m l y   to   g en er ate  an   en tire l y   n e w   s o l u tio n .   T h is   is   ca lled   m u tat io n .   A f ter   f i n ite  g en er a tio n s ,   an   ac ce p ted   s o lu tio n   is   e x p ec ted   to   o cc u r   [ 1 6 ] .     Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 2 5 2 - 8938   IJ - AI    Vo l.  5 ,   No .   2 ,     J u n e   2 0 1 6   :   6 4     71   66   T h v alid it y   i n d ex e s   h av e   an   i m p o r ta n r o le  i n   c lu s ter   a n al y s is .   I t   m ea s u r e s   t h q u alit y   o f   th r es u lt s   p r o d u ce d   b y   th cl u s ter i n g   alg o r ith m s .   T h er ar b r o ad ly   tw o   t y p es  o f   v alid it y   i n d ex e s ,   n a m e l y ,   i n ter n al  an d   ex ter n al.   A l m o s all  i n ter n al  cr iter ia  co n s id er s   th w it h in   clu s ter   s ca t ter   an d   b et w ee n   clu s ter   s ep ar atio n   i n   s o m e w a y   o r   o th er .   T h p r ese n p ap er   co n s id er s   o n o f   th e   in ter n a cl u s ter   v alid it y   i n d ex es,  ca lled   B all - Ha ll  in d ex   [ 1 7 ]   as th o b j ec t iv f u n ctio n   f o r   th g en e tic  alg o r it h m .   T h ex ter n al  i n d ex es,  o n   th o th er   h a n d ,   ass u m s o m p r io r   k n o w led g ab o u t t h s a m p le  d is tr ib u tio n   an d   m ea s u r es  th cl u s ter   p r o d u ce d   ac co r d in g l y .   A   g o o d   d is cu s s io n   o n   s u ch   i n d ex e s   is   g i v en   b y   Des g r au p e s   [ 1 8 ]   an d   Sah a   et  al  [ 1 9 ] .       3 .   T H E   P RO P O SE M O DE L                                                     Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - AI     I SS N:  2252 - 8938       A n   S V b a s ed   R ea l Co d e d   Ge n etic  A lg o r ith fo r   Gra p h   C lu s teri n g   ( P a r th a jit R o y )   67           4 .   RE SE AR CH   M E T H O DO L O G Y   T o   test   th p er f o r m a n ce   o f   t h p r o p o s ed   m o d el,   th a n   ex p er i m en tal  s et u p   h as  b ee n   ch o s en .   T h r ee   th i n g s   ar co n s id er ed   f o r   th is   s etu p .   T h ese  ar th p r o b lem   t o   co n s id er ,   th d ataset  co n tain in g   s u c h   p r o b le m s ,   th m ea s u r e m e n t scale s   o n   w h ich   th o u tp u t s   w ill  b m ea s u r ed .     T h er ar m ain l y   t w o   asp ec ts   th at  th cl u s ter i n g   p r o b lem s   ca n   b o b s er v ed .   On is   o n   th b asis   o f   s ep ar ab ilit y   an d   th o th er   is   o n   th b asis   o f   th s h ap o f   th clu s ter s .   T h p r o b lem   o f   s ep ar ab ilit y   m ea n s   w h et h er   th e   cl u s ter s   ar w ell  s ep ar at ed   o r   n o t.  I f   t h cl u s ter s   ar n o w ell  s ep ar ated ,   th p r o b lem   i s   to u ch i n g   p r o b lem .   T h s h ap o f   th cl u s ter s   ar o f   t w o   t y p es.  C o n v e x   s h ap ed   an d   ar b itra r y   s h ap ed .     I n   f i g u r 1 ( a) ,   co n v ex   a n d   w ell  s ep ar ated   s a m p le  h as  b ee n   s h o w n   w h er ea s   in   f i g u r 1 ( b ) ,   a   s a m p l e   is   s h o w n   w h ic h   is   w ell  s ep ar a ted   b u clu s ter   s h ap e s   ar n o n   co n v ex .   I n   f ig u r 1 ( c) ,   th s am p le  is   to u ch i n g   clu s ter s   p r o b lem .   I n   s a m p le  o f   f ig u r 1 ( c) ,   th s a m p le  i s   also   p r o b lem   o f   n o n - co n v e x   cl u s ter s .           Fig u r 1 .   ( a)   T h s a m p le  d atas et  is   a   co m p ac t c o n v e x   s h ap ed   w ell  s ep ar ated   d ataset.   ( b )   T h is   s a m p le  s h o w s   w ell  s ep ar ated   d ataset  b u t th clu s ter   s h ap es a r n o t c o n v e x   ( T h d ataset  h as b ee n   g e n er ate d   b y   tak in g   p ar f r o m   t h Fla m [ 2 0 ]   d ataset) .   ( c)   T h is   d ataset  is   k n o w n   as  Fl a m [ 2 0 ]   d atas et.   T h is   d ataset  es a n   ex a m p le  o f   to u ch i n g   clu s ter s .   T h s h ap i s   also   n o n - co n v e x   f o r   o n cl u s ter .                   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 2 5 2 - 8938   IJ - AI    Vo l.  5 ,   No .   2 ,     J u n e   2 0 1 6   :   6 4     71   68   5 .     RE SU L T S AN D I SCU SS I O NS   T o   test   th p er f o r m a n ce   o f   t h p r o p o s ed   tech n iq u e,   f o u r   s t an d ar d   m o d els  n a m el y ,   k - m e an s   m o d el,   Hier ar ch ical  m o d el  ( Sin g le  L i n k a g e) ,   Hier ar ch ical  m o d el  ( C o m p lete  L in k a g e) ,   Hier ar ch ical  m o d el  ( A v er a g e   L i n k a g e)   h a s   b ee n   co n s id er ed   an d   th p er f o r m a n ce s   ar s h o w n   i n   tab le  1 ,   tab le  2   an d   tab le   3 .       T ab le  1 .   C o m p ar ativ s tu d y   o f   th p r o p o s ed   m o d el  w it h   t h at  o f   o th er   f o u r   s ta n d ar d   m o d els  o n   Seed s   [ 2 2 ]   d ataset.   T h p er f o r m a n ce s   h a v b ee n   m ea s u r ed   o n   f o u r   e x ter n al  v al id it y   i n d ex e s .   Ex t e r n a l   I n d e x   H i e r a r c h i c a l   ( C o mp l e t e   L i n k a g e )   H i e r a r c h i c a l   ( S i n g l e   L i n k a g e )   H i e r a r c h i c a l   ( A v e r a g e   L i n k a g e )   K - M e a n M o d e l   P r o p o se d   M o d e l   C z e k a n o w sk i   D i c e   0 . 7 0 0 3 8 1 8   0 . 4 8 7 9 9 0 7   0 . 8 2 9 1 6 1 2   0 . 8 0 6 7 3 6 5   0 . 7 8 1 7 2 7 3   F o l k s M a l l o w s   0 . 7 0 0 6 8 4 8   0 . 5 5 4 2 9 8   0 . 8 2 9 1 7 7 4   0 . 8 0 6 7 6 2 4   0 . 7 8 1 7 4 9 9   Jac c a r d   0 . 5 3 8 9 1 3 5   0 . 3 2 2 7 4 3 2   0 . 7 0 8 1 7 7 1   0 . 6 7 6 0 7 5 7   0 . 6 4 1 6 6 8 5   K u l c z y n k i   0 . 7 0 0 9 8 8   0 . 6 2 9 6 1 5   0 . 8 2 9 1 9 3 5   0 . 8 0 6 7 8 8 3   0 . 7 8 1 7 7 2 5       Fro m   tab le  1   it   ca n   b s ee n   t h v al u o f   th in d e x es  ar h ig h er   f o r   th p r o p o s ed   m o d el  th an   th e   co m p lete   li n k ag h ier ar ch ical   m o d el.   T h is   i m p lie s   th at  t h p er f o r m a n ce   o f   th p r o p o s ed   m o d el  o n   s ee d s   d ataset  is   b etter   t h an   th e   co m p lete  lin k a g h ier ar ch ical   m o d el  in   all  o f   t h e x ter n al  i n d ex e s .   T h p er f o r m a n ce   o f   t h p r o p o s ed   m o d el  i s   b ette r   o n   s ee d   d ataset   th a n   t h Si n g le  lin k a g Hier ar ch ical  al s o .   T h p er f o r m a n ce   o f   th p r o p o s ed   m o d el  is ,   h o w e v er ,   co m p etitiv o n   s ee d s   d ataset  w it h   th at  o f   av er ag li n k a g Hier ar ch ica l   m o d el   a n d   s ta n d ar d   k - m ea n s   a lg o r ith m .   T h e   th ir d ,   f o u r t h   an d   f if th   co l u m n   o f   tab le  1   s h o w s   th is .       T ab le  2 .   C o m p ar ativ s tu d y   o f   th p r o p o s ed   m o d el  w it h   t h at  o f   o th er   f o u r   s tan d ar d   m o d els  o n   I r is   [ 2 1 ]   d ataset.   T h e   p er f o r m a n ce s   h a v b ee n   m ea s u r ed   o n   f o u r   e x ter n al   v al id it y   i n d ex e s .   Ex t e r n a l   I n d e x   H i e r a r c h i c a l   ( C o mp l e t e   L i n k a g e )   H i e r a r c h i c a l   ( S i n g l e   L i n k a g e )   H i e r a r c h i c a l   ( A v e r a g e   L i n k a g e )   K - M e a n M o d e l   P r o p o se d   M o d e l   C z e k a n o w sk i   D i c e   0 . 7 6 7 1 6 8 8   0 . 7 4 1 4 5 4 3   0 . 8 4 0 4 4 5 3   0 . 8 2 0 6 5 6 5   0 . 9 2 3 4 3 2   F o l k s M a l l o w s   0 . 7 6 8 6 3 7 1   0 . 7 6 3 5 1 7 1   0 . 8 4 0 7 2 8 9   0 . 8 2 0 8 0 8   0 . 9 2 3 4 3 4 2   Jac c a r d   0 . 6 2 2 2 8 2   0 . 5 8 9 1 3 5 8   0 . 7 2 4 8 0 0 0   0 . 6 9 5 8 5 8 8   0 . 8 5 7 7 5 5 4   Jac c a r d   0 . 7 7 0 1 0 8 3   0 . 7 8 6 2 3 6 3   0 . 8 4 1 0 1 2 7   0 . 8 2 0 9 5 9 6   0 . 9 2 3 4 3 6 3       T h p er f o r m an ce   o f   t h p r o p o s ed   m o d el,   o n   ir is   d ataset,   is   b etter   th an   co m p lete  li n k a g h i er ar ch ical  m o d el,   s i n g le   li n k a g h ier ar ch ical  m o d el,   a v er ag li n k ag e   h i er ar ch ical  m o d el  a n d   s ta n d ar d   k - m ea n s   m o d el  i n   all  ex ter n al  v alid it y   in d e x es  c o n s id er ed .   T ab le  2   s h o w s   t h co m p ar ati v s tu d ie s   r esp ec ti v el y .   I i s   clea r   f r o m   th tab le  2 ,   th at  th i n d ex   v al u es  f o r   th p r o p o s ed   m o d el  is   g r ea ter   th an   t h at  o f   all  o t h er   m o d el s .   T h is   m ea n s   th at  th d is tr ib u tio n   p r o d u ce d   b y   th p r o p o s ed   m o d el  is   m o r clo s th ac tu al  d is tr ib u tio n   th a n   th e   d is tr ib u tio n   p r o d u ce d   b y   t h o th er   alg o r it h m s .       T ab le  3 .   C o m p ar ativ s tu d y   o f   th p r o p o s ed   m o d el  w it h   t h at  o f   o th er   f o u r   s tan d ar d   m o d els  o n   Fla m [ 2 0 ]   d ataset.   T h p er f o r m a n ce s   h a v b ee n   m ea s u r ed   o n   f o u r   e x ter n al  v al id it y   i n d ex e s .   Ex t e r n a l   I n d e x   H i e r a r c h i c a l   ( C o mp l e t e   L i n k a g e )   H i e r a r c h i c a l   ( S i n g l e   L i n k a g e )   H i e r a r c h i c a l   ( A v e r a g e   L i n k a g e )   K - M e a n M o d e l   P r o p o se d   M o d e l   C z e k a n o w sk i   D i c e   0 . 6 1 3 5 2 0 3   0 . 6 9 7 6 3 3 9   0 . 7 3 0 6 2 1 6   0 . 7 5 8 1 3 2 5   0 . 8 3 2 0 5 5 5   F o l k s M a l l o w s   0 . 6 2 3 0 3 6 4   0 . 7 3 0 0 2 3 5   0 . 7 3 1 0 7   0 . 7 5 8 6 2 8 9   0 . 8 3 4 2 3 2 8   Jac c a r d   0 . 4 4 2 5 0 2 2   0 . 5 3 5 6 6 6 5   0 . 5 7 5 5 7 4 3   0 . 6 1 0 4 7 7 7   0 . 7 1 2 4 1 0 2   Jac c a r d   0 . 6 3 2 7 0 0 1   0 . 7 6 3 9 1 7   0 . 7 3 1 5 1 8 7   0 . 7 5 9 1 2 5 6   0 . 8 3 6 4 1 5 7       T h p er f o r m a n ce   o f   t h p r o p o s ed   m o d el  o n   Fla m e   [ 2 0 ]   d ataset  i s   al s o   b etter   i n   t h e x ter n al  in d e x es.   T ab le  3   s h o w s   t h is .   T h f la m d ataset  is   a n   ex a m p le  o f   to u ch i n g   cl u s ter   p r o b le m s   a s   well  as  n o n - co n v e x   clu s ter   p r o b le m s .   I n   s u c h   ca s e s   also ,   th al g o r ith m   p r o d u ce s   b etter   r esu lt th a n   t h b en ch m a r k   alg o r ith m s .   T h ac cu r ac y   o f   th p r o p o s ed   m o d el  o n   Seed s   d ataset  h as  b ee n   s h o w n   in   f i g u r 2 ( a) .   T h e   p r ec is io n   is   co m p etiti v w i th   th K - Me an s   m o d el  an d   s lig h tl y   l ess   ac c u r ate  th a n   Hier ar c h ic al  Mo d el( A v er a g e   L i n k a g e) .   B u t   it  i s   m o r ac cu r ate  th a n   C o m p lete   L in k a g a n d   Sin g le  L i n k ag e   Hier ar ch ical   Mo d ela.   T h s a m e   h as b ee n   r e f lecte d   in   ca s o f   F 1   s co r also .   Fig u r 2 ( b )   s h o w s   th i s .   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - AI     I SS N:  2252 - 8938       A n   S V b a s ed   R ea l Co d e d   Ge n etic  A lg o r ith fo r   Gra p h   C lu s teri n g   ( P a r th a jit R o y )   69   T h ac cu r ac y   o f   t h r es u lts   p r o d u ce d   b y   th p r o p o s ed   m o d el  is   m o r ac cu r ate  in   ca s i f   I r is   d ataset.   Fig u r 3 ( a)   an d   f i g u r 3 ( b )   s h o w s   t h at  t h p er f o r m a n ce   o f   th p r o p o s ed   m o d el  is   co n s i d er ab ly   b etter   th a n   o th er   b en ch m ar k   m o d els.   T h p er f o r m a n ce   o f   t h p r o p o s ed   m o d el  is   at  p er   in   ca s o f   p r ec is io n   w it h   K - m ea n s   al g o r ith m   o n   Fla m d ata s et.   T h p r o p o s ed   m o d el  i s   b etter   th a n   o th er   m o d els  in   p r ec is io n   i n d ex .   F ig u r 4 ( a)   s h o w s   t h is .   T h F1   in d e x ,   as   s h o w n   i n   f i g u r e   4 ( b ) ,   is   h i g h est   f o r   th e   p r o p o s ed   m o d el  an d   h e n ce   t h ac cu r ac y   is   al s o   h ig h e s t.             Fig u r e   2 a.   P r ec is io n   o f   th r es u lts   p r o d u ce d   b y   th f i v alg o r it h m s   o n   Seed s   d atas et.   T h p er f o r m an ce   o f   th p r o p o s ed   m o d el  is   s h o w n   i n   d ar k   co lo u r .     Fig u r 2 b .   F1   m ea s u r o f   t h r esu lt s   p r o d u ce d   b y   t h f i v alg o r it h m s   o n   Seed s   d atas et.   T h p er f o r m an ce   o f   th p r o p o s ed   m o d el  is   s h o w n   i n   d ar k   co lo u r .             Fig u r 3 a.   P r ec is io n   o f   th r es u lts   p r o d u ce d   b y   th f i v alg o r it h m s   o n   I r is   d ataset.   T h p er f o r m an ce   o f   th p r o p o s ed   m o d el  is   s h o w n   i n   d ar k   co lo u r .     Fig u r 3 b .   F1   m ea s u r o f   t h r esu lt s   p r o d u ce d   b y   t h f i v alg o r it h m s   o n   I r is   d ataset.   T h p er f o r m an ce   o f   th p r o p o s ed   m o d el  is   s h o w n   i n   d ar k   co lo u r .             Fig u r 4 a.   P r ec is io n   o f   th r es u lts   p r o d u ce d   b y   th f i v alg o r it h m s   o n   Fla m d ata s et.   T h p er f o r m a n ce   o f   th p r o p o s ed   m o d el  is   s h o wn   in   d ar k   co lo u r .     Fig u r 4 b .   F1   m ea s u r o f   t h r esu lt s   p r o d u ce d   b y   t h f i v alg o r it h m s   o n   Fla m d ata s et.   T h p er f o r m a n ce   o f   th p r o p o s ed   m o d el  is   s h o wn   in   d ar k   co lo u r .       Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 2 5 2 - 8938   IJ - AI    Vo l.  5 ,   No .   2 ,     J u n e   2 0 1 6   :   6 4     71   70   6 .     CO NCLU SI O AND  F U T U RE   SCO P E   T h is   p ap er   p r o p o s ed   n o v el  d ata  clu s te r in g   tec h n iq u o n   s in g u lar   m atr i x   o f   b ip ar tite  g r ap h   b ased   o n   g en et ic  al g o r ith m .   T h m o d el  s h o w s   g o o d   p er f o r m a n ce   o n   s tan d ar d   d atasets .   T h m o d el  i s   also   ad v a n tag eo u s   b ec au s t h el itis g en et ic  al g o r ith m   m o d el  b r i g s   th e   r esu lt  o u o f   t h lo ca o p ti m a.   T h o u g h   t h m o d el   s h o w s   g o o d   r esu lt,  th m ai n   attr ib u te   o f   th m o d el  is   t h at  it i s   co m p u tatio n a ll y   d e m a n d in g .   F u r th e r ,   th m o d el  ca n   b e   i m p r o v ed   b y   in co r p o r atin g   m u lti - o b j ec tiv ev o lu tio n ar y   a lg o r ith m s .   Oth er   s o f t - co m p u ti n g   to o ls   m a y   al s o   b u s ed   f o r   f u r t h er   p er f o r m an ce   t u n i n g .       ACK NO WL E D G M E NT   T h au th o r s   ex p r ess   t h d ee p   g r atitu d to   th Dep ar t m e n o f   C o m p u ter   Scien ce ,   t h Un iv er s it y   o f   B u r d w a n ,   W est  B en g al,   I n d ia  an d   Dep ar t m en o f   C o m p u ter   Scie n ce   &   E n g in ee r i n g ,   th Un iv er s it y   o f   Kal y a n i,  W est B en g a l,   I n d ia,   f o r   p r o v id in g   n ec es s ar y   i n f r astr u ctu r a n d   s u p p o r t f o r   th p r es en w o r k .       RE F E R E NC E   [1 ]   X u ,   W u n sc h - II S u rv e y   o f   c lu ste rin g   a lg o rit h m s IEE T ra n sa c ti o n o n   Ne u ra Ne tw o rk 2 0 0 5 16 ( 3 ):   6 4 5 678 .   [2 ]   BS   Ev e rit t,   D   S ta h l,   M   L e e se ,   S   Lan d a u .   C lu ste A n a ly sis,  5 th   e d .   J o h n   W il e y   &   S o n s,  2 0 1 1 .   [3 ]   G o d sil ,   G   Ro y le .   A lg e b ra ic  G ra p h   T h e o ry ,   se r.   G ra d u a te T e x ts  in   M a th e m a ti c s.  S p rin g e r .   2 0 0 1 2 0 7 .   [4 ]   Ha rtu v ,   R   S h a m i r .   A   c lu ste rin g   a lg o rit h m   b a se d   o n   g ra p h   c o n n e c ti v it y .   In f o r m a ti o n   P ro c e ss in g   L e tt e rs,  2 0 0 0 .   [5 ]   X   He ,   CHD   Ho n g y u a n   Zh a ,   HD   S im o n .   W e b   d o c u m e n c lu ste r in g   u sin g   h y p e rli n k   stru c tu re s .   Co m p u tatio n a l   S tatisti c s   a n d   Da ta A n a ly sis 2 0 0 7 41 : 19 45 .   [6 ]   S E   S c h a e f fe r G r a p h   c lu ste rin g .   E lse v ier   Co mp u ter   S c ien c e   Rev iew .   2 0 0 7 ;   1 27 64.   [7 ]   Bo ll o b ´ a s .   M o d e r n   G ra p h   T h e o ry .   S p rin g e r - Ver la g .   2 0 0 5 .   [8 ]   P   P ra b h u ,   A n b a z h a g a n .   I m p ro v in g   th e   p e rf o r m a n c e   o f   k - m e a n c lu ste rin g   f o h ig h   d im e n sio n a d a ta  se t .   In ter n a t io n a J o u rn a o n   Co mp u t e r S c ien c e   a n d   En g i n e e rin g   ( IJ CS E) .   2 0 1 1 3 2 3 1 7 2 3 2 2 .   [9 ]   IS   Dh il l o n .   Co - c l u st e rin g   d o c u me n ts  a n d   wo r d u si n g   b ip a rtit e   s p e c tra g r a p h   p a rtit i o n i n g .   P ro c e e d in g o f   th e   S e v e n th   A CM   S I G K DD   In tern a ti o n a Co n f e re n c e   o n   Kn o w led g e   Disc o v e r y   a n d   Da ta  M in in g .   2 0 0 1 :   2 6 9 2 7 4 [ On li n e ] .   A v a il a b le:  h tt p :/ / d o i. a c m . o rg /1 0 . 1 1 4 5 / 5 0 2 5 1 2 . 5 0 2 5 5 0 .   [1 0 ]   Drin e a s,  A   F riez e ,   R   Ka n n a n ,   S   V e m p a la,  V   V in a y .   Clu ste rin g   la rg e   g ra p h s v ia   th e   sin g u lar v a lu e   d e c o m p o siti o n ,   M a c h .   L e a rn .   2004 ;   56 ( 1 - 3 ):  9 33 .   [ O n li n e ] .   A v a il a b le:  h tt p :/ / d x . d o i . o rg /1 0 . 1 0 2 3 /   B:M A CH.0 0 0 0 0 3 3 1 1 3 . 5 9 0 1 6 . 9 6 .   [1 1 ]   De b ,   A   P ra tap ,   S   Ag a r w a l,   T .   M e y a riv a n .   F a st  a n d   e li ti st  m u lt io b jec t iv e   g e n e ti c   a lg o rit h m Ns g a - ii .   IEE E   T ra n sa c ti o n o n   Evo l u ti o n a ry   Co mp u ta ti o n 2 0 0 2 6 ( 2 ):  1 8 2 1 9 7 .   [1 2 ]   U   M a u li k S   Ba n d y o p a d h y a y .   F u z z y   p a rti ti o n in g   u si n g   a   re a l - c o d e d   v a riab le - len g th   g e n e ti c   a lg o rit h m   f o p ix e c las si f ica ti o n .   IEE E   T ra n sa c ti o n s   o n   Ge o sc ien c e   a n d   Rem o te  S e n si n g 2 0 0 3 41 ( 5 ):   1 0 7 5 1 0 8 1 .   [1 3 ]   Ch e .   A   h y b rid   a lg o rit h m   f o f u z z y   c lu ste rin g .   Eu ro p e a n   J o u r n a l   o In d u stri a E n g in e e rin g .   2 0 1 2 6 50 6 7 .   [1 4 ]   Ka la,  A   S h u k la,  T i w a ri .   Clu ste rin g - b a se d   h ie ra rc h ica g e n e ti c   a lg o rit h m   f o c o m p l e x   f it n e ss   lan d sc a p e s .   In ter n a t io n a J o u rn a o I n telli g e n S y ste ms   T e c h n o l o g ies   a n d   Ap p li c a ti o n s 2 0 1 0 ;   9 :   1 8 5 2 9 5 .   [1 5 ]   G G o lu b CF   v a n   L o a n .   M a tri x   Co m p u tatio n s.   Ba lt im o re Jo h n Ho p k in s Un iv e rsit y   P re ss ,   1 9 9 6 .   [1 6 ]   K   De b ,   M u lt i - Ob jec ti v e   Op ti m iza ti o n   u si n g   Ev o lu ti o n a ry   A l g o rit h m s.  Jo h n   W il e y   P u b li c a ti o n ,   2 0 0 1 .   [1 7 ]   G H   Ba ll DJ   Ha ll .   Iso d a ta:  A   n o v e m e th o d   o f   d a ta  a n a l y sis   a n d   p a tt e rn   c las sif c a ti o n .   M e n l o   P a rk S tan f o rd   Re se a rc h   In stit u te.  (NT IS   No .   A D 6 9 9 6 1 6 ),   1 9 6 5 .   [1 8 ]   De s g ra u p e s .   Clu ste rin g   in d ice s .   Un iv e rsity   P a ris  Ou e st,  L a b   M o d a l‘X ,   T e c h .   Re p . ,   A p ril   2 0 1 3 .   [1 9 ]   S   S a h a ,   S   Ba n d y o p a d h y a y .   P e rf o r m a n c e   e v a lu a ti o n   o f   so m e   s y m m e tr y - b a se d   c lu ste v a li d it y   in d e x e s .   IEE E   T ra n sa c ti o n o n   S y ste ms .   M a n ,   a n d   Cy b e rn e ti c s:  P a rt  C:A p p li c a ti o n s a n d   Re v ie w s .   2 0 0 9 39 ( 4 ):  4 2 0 4 2 5 .   [2 0 ]   L   Fu ,   E   M e d ico .   F lam e ,   a   n o v e f u z z y   c lu ste rin g   m e th o d   f o th e   a n a ly sis  o f   d n a   m icro a rr a y   d a ta .   BM C   b io i n f o rm a ti c s,  2 0 0 7 .   [2 1 ]   RA   F ish e r .   U c m a c h in e   lea rn in g   re p o sito ry .   1 9 3 6 .   [ On l in e ] .   A v a il a b le:  h t tp :/ /arc h iv e . ics . u c i. e d u /m l   [2 2 ]   M   Ch a ry tan o w icz ,   J   Nie w c z a s,  P   Ku lcz y c k i,   P A   Ko wa lsk i,   S   Lu k a sik ,   S   Za k .   Uc m a c h in e   lea r n in g   re p o sit o ry 2 0 1 0 .   [ O n li n e ].   A v a il a b le:  h tt p :/ /arc h iv e . ics . u c i. e d u /m l .                         Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - AI     I SS N:  2252 - 8938       A n   S V b a s ed   R ea l Co d e d   Ge n etic  A lg o r ith fo r   Gra p h   C lu s teri n g   ( P a r th a jit R o y )   71   B I O G RAP H I E S   O F   AUTH O RS         P a rt h a ji Ro y   is  a   M a ste in   C o m p u ter  A p p li c a ti o n f ro m   th e   Un iv e rsit y   o Bu rd w a n   a n d   c u rre n tl y   p u rsu in g   h is  d o c t o ra d e g re e   f ro m   th e   Un iv e rsit y   o f   Ka l y a n i.   He   is   a n   A ss ist a n P r o f e ss o o f   th e   De p a rt m e n o Co m p u ter  S c ien c e ,   th e   Un iv e r s it y   o f   Bu rd wa n .   His  a re a   o in tere st  is  m a in l y   P a tt e rn   Re c o g n it io n ,   Co m p u tati o n a G e o m e tr y   a n d   G ra p h   T h e o ry .   His  c u rre n t   re se a rc h   a re a   is  sp e c tral  g r a p h   th e o ry   b a se d   c lu ste rin g .           J.  K.  M a n d a is  a n   M .   T e c h . (Co m p u ter  S c ien c e ,   Un iv e rsity   o f   Ca lcu tt a ),   P h . D.(E n g g . ,   Ja d a v p u r   Un iv e rsit y in   th e   f ield   o Da ta   Co m p re ss io n   a n d   Err o Co rre c t io n   T e c h n iq u e s,  P ro f e ss o in   Co m p u ter  S c ien c e   a n d   En g in e e rin g ,   Un iv e rsit y   o Ka l y a n i,   In d i a .   L i f e   M e m b e o f   Co m p u ter  S o c iety   o f   In d ia  sin c e   1 9 9 2   a n d   li f e   m e m b e o f   c r y p to lo g y   Re se a rc h   S o c iety   o f   In d ia.  F o rm e r   De a n ,   F a c u lt y   o f   En g in e e rin g ,   Tec h n o l o g y   &   M a n a g e m e n t,   w o rk in g   in   th e   f ield   o f   Ne tw o rk   S e c u rit y ,   S teg a n o g ra p h y ,   Re m o t e   S e n sin g   &   G IS   A p p li c a ti o n ,   I m a g e   P ro c e ss in g   a n d   P a tt e r n   Re c o g n it io n .   2 8   y e a rs  o f   te a c h in g   a n d   re se a rc h   e x p e rien c e s.  El e v e n   S c h o lars   a w a rd e d   P h . D.  o n e   su b m it ted   a n d   8   a re   p u rsu i n g .   T o tal  n u m b e o f   p u b li c a ti o n 3 5 5 .   F u rth e in f o   o n   h is  h o m e p a g e :   h tt p : // jk m a n d a l. c o m             Evaluation Warning : The document was created with Spire.PDF for Python.