Decision Queue Classifier for Supervised Learning Using Rotated Hyperboxes

Helde Coelho (Ed.): IBERAMIA'98, LNAI 1484, pp. 326-336, 1998.  Sp inge -Ve lag Be lin Heidelbe g 1998 Decision Queue Classi ie o Supe ised Lea ning Using Ro a ed Hype boxes Jesús Aguila , José Riquelme and Miguel To o Depa amen o de Lenguajes y Sis emas In o má icos. Facul ad de In o má ica y Es adís ica. Uni e sidad de Se illa. E-mail: {aguila , iquelme, m o o}@lsi.us.es Keywo ds: da a mining, supe ised lea ning, gene ic algo i hms. Abs ac . This a icle desc ibes a new sys em o lea ning ules using o a ed hype boxes as indi iduals o a gene ic algo i hm (GA). Ou me hod a emp s o ind ou hype boxes a any o ien a ion by combining de e minis ic hill-climbing wi h GA. S anda d echniques, such as C4.5, use hype boxes ha a e aligned wi h he coo dina e axes. The sys em uses he decision queue (DQ) as me hod o ep esen ing he ule se . I means ha he ob ained ules mus be applied in speci ic o de , ha is, an example will be classi y by he i- ule only i i doesn’ sa is y he condi ion pa o he i-1 p e ious ules. Wi h his policy, he numbe o ules is less because he ules could be one inside o ano he one. We ha e es ed ou sys em on eal da a om UCI eposi o y. Mo eo e , we ha e designed some wo-dimensional a i icial da abases o show g aphically he expe imen s. The esul s a e summa ized in he las sec ion. 1 In oduc ion Supe ised lea ning (SL) is used when he da a samples ha e known ou comes ha he use wan s o p edic . This ype o lea ning is he mo e common o m because da a a e usually collec ed wi h some ou come in mind. Human p oblem sol ing is no mally an exe cise in s udying inpu condi ions o p edic a esul based upon p e ious expe ience wi h simila si ua ions. SL algo i hms end o emula e ha so o human beha io . Decision ees (DT) a e a pa icula ly use ul ool in he con ex o machine lea ning Decision Queue Classi ie o Supe ised Lea ning Using Ro a ed Hype boxes 327 echniques because hey pe o m classi ica ion by a sequence o simple, easy- o- unde s and es s whose seman ics is in ui i ely clea o domain expe s. Some echniques, like C4.5, cons uc decision ees selec ing he bes a ibu e by using a s a is ical es o de e mine how well i alone classi ies he aining examples [9]. This class o DTs may be called axis-pa allel, because he es s a each node a e equi alen o axis-pa allel hype planes in he space. O he s echniques build oblique decision ees (ODT), as OC1[7], ha es s a linea combina ion o he in e nal a ibu es a each node, o ha , hese es s a e equi alen o hype planes a an oblique o ien a ion o he axes. A his poin , we mus emembe ha , in a domain wi h N aining examples, each desc ibed using a k eal- alued a ibu es, he e a e a mos 2kN k     dis inc k- dimensional oblique spli s; howe e , o axis-pa allel spli s, he e a e only N k×dis inc possibili ies, o ha eason, i could exhaus i ely sea ch he bes spli a each node. Anyway, o ind ou he smalles DT (axis-pa allel o oblique) is a NP-ha d p oblem [2]. Bo h me hods use hill-climbing, ha is, he algo i hm ne e back acks; he e o e, i could be con e ging o locally op imal solu ions ha a e no globally op imal. Simpson [12] in oduced he idea o using hype boxes o clus e o classi y spa ial da a. Each hype box is iewed as a uzzy clus e , a uzzy se in which all o he elemen s wi hin he hype box ha e membe ship 1.0 o being in ha se , and elemen s ou side he hype box can ha e a posi i e membe ship in he se depending on a uzzy membe ship ule o ha se . Simpson used a de e minis ic p ocedu e o place and app op ia ely size hype boxes o desc ibe da a. Hype boxes we e c ea ed and sized by conside ing he da a in an o de ed sequence. A hype box was placed a ound p elimina y da a. As subsequen da a was added, ei he he p esen hype box was g own o include he new da a, o a new hype box was added and he p ocess con inued. This p ocedu e was o limi ed e icacy because i equi ed ial-and-e o se ing o ope a o pa ame e s and he inal solu ion depended on he o de o p esen a ion o he da a, e en when he da a possessed only spa ial an no sequen ial cha ac e is ics. Fogel and Simpson used e olu iona y p og amming o op imize he posi ion o hype boxes o clus e da a in ligh o a minimum desc ip ion leng h c i e ion (MDL). Fi s , he expe imen s we e es ic ed o e ol ing hype boxes ha we e aligned wi h coo dina e axes; and a e wa ds, hey included he capabili y o o a e he hype boxes. A his poin , i is impo an o no e ha Fogel's me hod y o sol e he clus e ing p oblem, ha is, unsupe ised lea ning. Gene ic algo i hms (GA) employ a andomized sea ch me hod o seed a maximally i hypo hesis [3, 4]. This sea ch is qui e di e en om o he lea ning me hods, like men ioned abo e. The GA sea ch can mo e much mo e ab up ly, eplacing a pa en hypo hesis by an o sp ing less likely o all in o he same kind o local minima ha can happen wi h he o he me hods. In p e ious wo ks, we p esen ed a sys em o classi y da abases by using hype boxes (axis-pa allel). This sys em used a GA o sea ch he bes solu ions and p oduced a hie a chical se o ules. The hie a chy means ha an example will be classi y by he i- ule i i does no sa is y he condi ions o he i-1 p eceden ules. The ules a e sequen ially ob ained un il he space is o ally co e ed. The beha io is simila o a 328 Jesús Aguila , José Riquelme and Miguel To o queue, o ha eason we ha e called decision queue (DQ) o he p oduced ule se . This concep is based on he k-DL, he se o decision lis s wi h conjun i e clauses o size a mos k a each decision [11]. A decision lis is a lis L o pai s whe e each j is a e m in n k C, each i is a alue in {0,1}, and he las unc ion is he cons an unc ion ue. ),(),...,,( 11 (1) A decision lis L de ines a boolean unc ion as ollows: o any assignmen x∈Xn, L(x) is de ined o be equal o j whe e j is he leas index such ha j(x)=1 (such an i em always exis s, since he las unc ion is always ue). DQ is based on DL. Really, DQ is a DL-gene aliza ion because i pe mi s codi ying unc ions i o con inuous a ibu es and he alues i can belong o any se . Fu he mo e, DQ does no ha e he las cons an unc ion ue. Howe e , we could in e p e ha las unc ion as unknown unc ion, ha is, we do no know o which class he example belongs o. The e o e, i may be ad isable o say "unknown class" ins ead o aking an e oneous decision. In he sense men ioned abo e, ou sys em has a measu e, called unknowledge, o indica e how many es examples ha e no an associa ed class. As he numbe o ules o he allowed e o a e ( elaxing coe icien ) can be gi en by he domain expe , some unnecessa y mis akes could be a oided i he ule se does no assign o he es example a class. Inc emen ing he elaxing coe icien he unknowledge will be less, bu he numbe o misclassi ied examples will be highe . The expe , based on expe imen a ion, mus de e mine such pa ame e . Fig. 1. Ro a ed e sus axis-pa allel hype boxes. In his pape , we p opose o hold he p imi i e s uc u e o ou ea ly wo ks [1,10], bu changing he shapes ha models he sea ch space. Tha is o say, cu en wo k ex ends hese p e ious e o s by including he capabili y o o a e he hype boxes. We show in igu e 1 an example, in which o a ed hype boxes can ind ou be e solu ions han axis-pa allel hype boxes hey do. Decision queue policy is applied in o de o educe he numbe o ules. Decision Queue Classi ie o Supe ised Lea ning Using Ro a ed Hype boxes 329 Wi h his DQ-me hod, he e is no p oblem i he egions a e o e lapped. An ex eme case is p esen ed in he nex igu e. Fig. 2. Decision queues o o e lapped egions. In he o he hand, i we use axis-pa allel echniques, he numbe o ules is e y high. When does i apply one echnique o he o he one? In p inciple, i is no possible o know i , bu i could be a good solu ion o explo e he sea ch space wi h axis-pa allel and, inc easingly, o y o o a e he bes solu ions. Fig. 3. Axis-pa allel solu ion o he igu e 2. The numbe o ules, in igu e 3, is e y high. The numbe s ep esen s pa s o he egions ound ou by using o a ed hype boxes, as shows igu e 2. 2 Desc ip ion 2.1 En i onmen In o de o apply GAs o a lea ning p oblem, we need o selec an in e nal ep esen a ion o he space o be sea ched and de ine an ex e nal unc ion ha assigns i ness o candida e solu ions. Bo h componen s a e c i ical o he success ul 1 2 34 5 6 1 2 4 5 6 3 330 Jesús Aguila , José Riquelme and Miguel To o applica ion o he GAs o he p oblem o in e es . In o ma ion o he en i onmen comes om a da a ile, whe e each example has a class and a numbe o a ibu es. The GA uses eal codi ica ion; ha is, an indi idual is o med by an n- uple o eal. I k is he dimension, an indi idual has exac ly 3×k alues: 2×k o he bounda ies o each dimension; k−1 o he angles o o a ions, in adians, an i-clockwise a ound he hype box cen e; and 1 o he class. The nex igu e shows a n- uple: Fig. 4. Rep esen a ion o an indi idual. whe e li and ui ep esen he lowe and uppe bounds o he indi idual, espec i ely, o e e y dimension; θi is he o a ion angle; and class. In 2-dimension is possible o pu an hype box a any o ien a ion by using only one o a ion; in k- dimension i is necessa y k-1 o a ions. We conside ha an example belongs o he a ea de e mined o an indi idual i i sa is ies i s condi ion pa . Thus, le an example be gi en by Pj=(p1, p2, ..., pk, c) hen i will be in o he de ined egion by he indi idual (o equi alen ly, a ule will be co e ed by he ule) indh =(l1, u1, l2, u2, ..., lk, uk, θ 1, θ 2,..., θ k-1, class) i o a ing he example P=(p1, p2, ... , pk) wi h he angles - θ 1,- θ 2,...,- θ k-1 wi h ela ion o he cen e o he hype box de ined by (l1, u1, l2, u2, ... , lk, uk), hen he esul P’ belongs o his hype box. Fig. 5. Ro a ion o R he angle θ is equi alen o o a e P he angle -θ a ound he cen e o R. Fo example, in h ee dimensions he example (p1, p2, p3, c) will be co e ed by he ule (l1, u1, l2, u2, l3, u3, θ 1, θ 2, class) i P’ sa is ies lpulpulpu 111222333 ≤≤∧≤≤∧≤≤''' (2) whe e P’ is ob ained as ollows: ll l 12 uu u 12kk θ 1 θ θ 2k-1 class PP’ θ θ Decision Queue Classi ie o Supe ised Lea ning Using Ro a ed Hype boxes 331 Le (m1, m2, m3) = ((l1+ u1)/2, (l2+ u2)/2, (l3+ u3)/2) be he cen e o he hype box de ined by he ule, hen he coo dina es o P’ a e: 3 , 2 , 1 ( 100 0 2 cos 2 sen 0 2 sen 2 cos 1 cos 1 sen0 1 sen 1 cos0 001 ) 33 , 22 , 11 () 3 ', 2 ', 1 '( mmmmpmpmpppp + − −−−−=                 θθ θθ θθ θθ (3) and i will be co ec ly classi y i i s class is equal o c. 2.2 Algo i hm The algo i hm is a ypical sequen ial co e ing GA [6]. I chooses he bes indi idual o he e olu iona y p ocess, ans o ming i in o a ule, which is used o elimina e da a om he aining ile [13]. In his way, he aining ile is educed o he ollowing i e a ion. A e mina ion c i e ion could be eached when mo e examples o co e do no exis . The me hod o gene a ing he ini ial popula ion consis s o andomly selec ing o e e y indi idual o he popula ion an example om he aining ile. A e , i is ob ained an in e al o which he example belongs adding and sub ac ing a andom quan i y om he alues o he example. Mo eo e , he angles a e andomly gene a ed be ween ze o and π/2. Some imes, he examples e y nea o he bounda ies a e ha d o co e du ing he e olu iona y p ocess. Fo sol ing i , he sea ch space is inc eased (ac ually, lowe bound is dec eased 5%, and uppe bound is inc eased 5%). Fo example in 1-dimension, le a and b be he lowe and uppe bounds o he a ibu e; hen, he ange o he a ibu e is b-a; now, we andomly choose an example (x1, class) om he aining ile; las , a possible indi idual o he popula ion could be: ),*,*( 2111 classk angexk angex +− (4) whe e k1 and k2 a e andom alues belonging o [0,1], and class is he same o ha o he example. The e olu ion module includes eli ism: he bes indi idual o e e y gene a ion is eplica ed o he nex one. A se o child en is ob ained om copies o he pa en s, andomly selec ing i , bu depending on hei i ness alues. The emainde is o med h ough c osso e s. A e wa ds, mu a ion is applied depending on a p obabili y. C osso e s a e speci ically designed, choosing a alue among one o he h ee segmen s o med inside he in e al o he a ibu e by pu ing he wo alues o he indi idual as c oss poin s. Tha is, o e e y a ibu e, an indi idual has wo alues, and hen hose alues a e pa i ioning he in e al in h ee segmen s. We selec andomly a alue inside o a segmen also andomly chooses. The nex igu e shows he p ocedu e: 332 Jesús Aguila , José Riquelme and Miguel To o Fig. 6. C osso e ope a o . One o he h ee ypes o c osso e ope a o could be applied, depending on a p obabili y. The i s one is mo e conse a i e and second and hi d ones a e mo e explo a i e. When he c osso e is applied o any angle loca ion, he i s one is always used. Mu a ion is applied in wo di e en ways: i he loca ion co esponds o a alue o he in e al, hen a quan i y is sub ac ed o added, depending on whe he i is he lowe o he uppe bound, espec i ely ( he dis ance ac ually is he lowe euclidean dis ance be ween any wo examples); i he loca ion co esponds o an angle, i is andomly gene a ed ano he one. Fu he mo e, i is ad isable o explo e he space wi h he bes indi idual, because we canno know wha angles a e he bes , and we canno ei he know i an angle is going o be be e han o he is. In his way, we a e using hill-climbing echnique, wha could ind ou bes solu ions; despi e o incon eniences said in he in oduc ion. The me hod consis s o explo ing close o a ed egions wi h he same cen e. The angles o he explo a ion belongs o he in e al [-π/6,π/6], wi h an inc emen o π/30. Then, e e y bes ule explo es he sea ch space wi h o he en egions a ound he same cen e o each a ibu e. Howe e , in o de o each be e i ness alue, he in e al is also modi ied he same quan i y as mu a ion used. To imp o e he bes indi idual is a di icul ask. I he i ness alue is be e , hen he new angle eplaces o he old, and one alue o one a ibu e is modi ied as men ioned abo e. This me hod allows o a ing an hype box using only one dimension. To explo e 10 new o ien a ions a he beginning ( he i s gene a ions) can p oduce he ypical p oblems o he hill-climbing me hods. Fo ha , we ecommend o use ew explo a ions a he s a and inc ease i owa d he inal. Thus, he las gene a ions explo e mo e han he i s ones. We nex show an o e iew o he DQ-Classi ie . While exis s examples in aining ile S ep 1. Ini ialize popula ion S ep 2. Repea num_gene a ions imes m in m in ( a , b ) m ax ( a , b ) max (1) (2) (3) Decision Queue Classi ie o Supe ised Lea ning Using Ro a ed Hype boxes 333 S ep 2.1. E alua ion S ep 2.2. Selec he bes S ep 2.3. Replica ion S ep 2.4. C osso e and Mu a ion S ep 2.6. Imp o e he bes S ep 3. Pu he bes one in Decision Queue S ep 4. Elimina e he co e ed ones by he bes one Fig. 7. O e iew o DQ-Classi ie . A possible c i e ion o implemen he mu a ion ope a o consis s o dis inguishing be ween mu a ion o alues and mu a ion o angles, as wo independen ope a o s. Mu a ion o alues could be a highe p obabili y o applica ion han mu a ion o angles, and also, o inco po a e o he e alua ion unc ion he dis ance om he indi idual ( ule) o he close example o he same class. Thus, we can penal y he o a ed ules wi h w ong angles; ha is, he new indi idual is no going nea o he close example o he same class. 2.3 Fi ness Func ion The e olu iona y algo i hm minimizes he i ness unc ion o each indi idual. I is gi en by i G(i)*RC<=CE(i) hen CE(i)=0 i V T Gi CE i () () () =+ +1 (5) whe e T is he ca dinali y o he aining ile, V is a new ac o called co e age ( he ule co e age is he side o a k-dimensional hype cube which olume is equi alen o he olume o he co e ed k-dimensional egion by he ule); CE(i) is he class e o s, which a e p oduced when he i example belongs o he egion de ined by he ule, bu i does no he same class; G(i) is he numbe o goals o he ule; RC is he elaxing coe icien . E e y ule can quickly expands o inding mo e examples due o V in he i ness unc ion. 2.4 Relaxing Coe icien Da abases uses as aining iles ha e no a eas clea ly di e en ia ed, o ha , o ob ain a ule sys em o ally cohe en in ol es a high numbe o ules. We show in 334 Jesús Aguila , José Riquelme and Miguel To o p e ious pape [1] a sys em capable o p oducing a ule se exemp om e o a e; howe e some imes, i is in e es ing o educe he numbe o ules o ha ing a ule se which may be used like a comp ehensible linguis ic model. When da abases p esen a dis ibu ion o examples e y ha d o classi y, hen i is ad isable o use a elaxing coe icien [10]. Many imes, we a e mo e in e es ed in unde s anding he s uc u e o he da abases han in he e o a e. In his way, i could be be e a sys em wi h less ca dinali y (despi e some e o s) han oo many ules (wi h 0% o e o a e). Then, i may be in e es ing o in oduce he elaxing coe icien o unde s anding he beha io o da abases by dec easing he numbe o ules. RC indica es wha pe cen age o examples inside o a ule can ha e di e en class o he ule. RC beha es like he uppe bound o he e o wi h espec o he aining ile, ha is, as an allowed e o a e. To deal e icien ly wi h noise and ind a good alue o RC, he expe should ha e an es ima e o he noise pe cen age in i s da a. 3 Applica ion 3.1 Ex P o eso Da abases We ha e designed some da abases o a ying complexi y o show g aphically he expe imen s. These da abases a e shown in he ig. 8. Resul s a e in able 1. Fig. 8. Ex p o eso da abases named DB1, DB2 and DB3. 3.2 Da abases om UCI Reposi o y The expe imen s desc ibed in his sec ion a e om UCI Reposi o y [7]. We use i e c oss alida ion in all ou expe imen s o es ima e classi ica ion accu acy. This c oss alida ion expe imen consis s o he ollowing s eps: andomly di ide he da a in o