Attribute Selection for Classification

469 ATTRIBUTE SELECTION FOR CLASSIFICATION Pa icio Se ende o Dep. o Elec onics & Compu e Science, U. o Alga e, Campus Gambelas, Fa o, Po ugal Miguel To o Dep. o Languages and In . Sys ems, U. o Se ille, A . Reina Me cedes s/n, Se ille, Spain ABSTRACT The selec ion o a ibu es used o cons uc a classi ica ion model is c ucial in machine lea ning, in pa icula wi h ins ance simila i y me hods. We p esen a new algo i hm o selec and ank a ibu es based on weighing ea u es acco ding o hei abili y o help class p edic ion. The algo i hm uses he same s uc u e ha holds aining eco ds o classi ica ion. A ibu e alues and hei classes a e p ojec ed in o a one-dimensional space, o accoun o a ious deg ees o he ela ionship be ween hem. Wi h he use deciding on he deg ee o his ela ion, any o se e al po en ial solu ions can be used as c i e ion o de e mine a ibu e ele ance. This low complexi y algo i hm inc eases classi ica ion p edic i e accu acy and also helps o educe he ea u e dimension p oblem. KEYWORDS Da a Mining, classi ica ion, a ibu e selec ion, ele an a ibu es, exclusi e a ibu es 1. INTRODUCTION Two well-known p oblems a ise when building classi ie s which use decision ee s uc u es and ins ance- based me hods. Fi s , he inpu o de o a ibu es de e mines hea ily he p edic ing skills o he algo i hm. Choosing he w ong o de o a ibu es (o ea u es) could mo e apa in he hype space, alues ha o he wise would be close . Secondly, some a ibu es con ibu e mo e han o he s in building he p edic ion hypo hesis [Aha, 1994]; a ibu es conside ed i ele an inc ease he compu a ional cos and can mislead dis ance me ics calcula ions [Indyk, 2000]. This is pa icula ly ue o nea es neighbou algo i hms, which ind he class o unknown ins ances using he geome ic concep o p oximi y o simila i y buil a ound he no ion o dis ance be ween poin s in an n-dimensional space. As he posi ion o any ins ance is de ined by he alue o i s a ibu es, i hese a e no ele an , hen he basic assump ion is iola ed. Based on hese, a ibu es a e classi ied as ele an o i ele an , in e ms o hei deg ee o con ibu ion o he classi ica ion model [Koha i e al., 1997; Lebowi z, 1985]1. Fea u e selec ion is used o his eason, and is de ined as he p ocess o iden i ying and emo ing as much i ele an and edundan in o ma ion as possible wi h he goal o imp o ing classi ica ion accu acy. Because we use a ee s uc u e o hold ins ances, ou me hod equi es i s se ing in he inpu o de , a ibu es wi h la ge disc imina o y powe wi h espec o classes, as done in some ule induc ion algo i hms [Quinlan, 1986; Co e e al., 1997]. The complexi y o ea u e selec ion algo i hms depends on he numbe and quali y o i s a ibu es. Sea ching ele an a ibu es canno be exhaus i e in many cases. The dimension o da ase s is exponen ial in he numbe o a ibu es. Hence, e i ying e e y possible combina ion o a ibu es is, in many cases, ou o he ques ion [Lesh e al., 1998]. Because o his, we de eloped a low compu a ional algo i hm wi h he ollowing goals: a) Es ablish a c i e ion o de e mine ele an a ibu es. b) Rank a ibu es a p ep ocessing ime based on his ele ance and c) Reduce he numbe o a ibu es. The o e all goal is o diminish he 1 These au ho s s ill iden i y edundan a ibu es, a si ua ion which we do no add ess he e. IADIS In e na ional Con e ence e-Socie y 2003 470 algo i hm's complexi y as well as o inc ease o a leas p ese e i s p edic i e skills. Ou esul s show a s eady imp o emen o ou classi ica ion algo i hm when o de ed ea u es a e used wi h his simple me hod. 2. DEFINITIONS 2.1 Basic de ini ions No a ion { ∈ R, c ∈ L|" exp( ) • exp1( )} s and o he se o alues o exp1 when and c ake alues in R and L, and exp is ue. I exp1( ) = hen he exp ession is educed o { ∈ R |" exp( )}. Le ’s assume he exis ence o a da a se R composed o a ini e se o N eco ds o ype: = < 1, 2,.., i,.., n, c >, i ∈ Ti, c ∈ L and i( ) = i . (1) Each eco d is o med by he Ca esian p oduc o a ini e sequen ial se o a ibu es Ai, belonging o se S ha ing i alues ∈ Ti. Each eco d is associa ed wi h one o m classes c1, c2,..,cm, belonging o se L. Each a ibu e’s domain is pa i ioned in o a ini e numbe o use -de ined in e als wi hin domain Ti. These in e als a e ep esen ed by in ege s wi h alues om 1 o si. We assume he exis ence o unc ion o di(), which con e s an a ibu e alue in o he co esponding in e al alue: pi = o di( i), i ä Ti . (2) Using unc ion o di in (2), e e y a ibu e alue i ∈ Ti is con e ed in o a pa e n elemen wi h alue pi.. E e y pi alue will i in o one o si pa i ions belonging o a ibu e Ai. Toge he , all pi elemen s o m a ec o called pa e n p con aining n elemen alues. We call P he se o all pa e ns p ob ained om R. p = <p1, p2,.., pi,.., pn>," p ä P," pi Î (1..si) whe e pi = o di( i( )) . (3) No ice ha he numbe o pa i ions si is no he same o all a ibu es2. We de ine unc ions pa ( ) and label( ) such ha : pa ( ) = p and label( ) = c i = < , c>, = < 1, 2,.., n> . (4) In e e y pa e n p om (3) we ind n sub-pa e ns qi, which co espond o i s p e ix: qi = <p1, p2,.., pi >, i =(1..n). So p= <qi, u> whe e u is he su ix po ion. (5) We de ine unc ion eq(p), which e u ns he numbe o eco ds exhibi ing pa e n p: eq (p) = # { ∈ R | pa ( ) = p} . (6) Func ion eq can be equally applied o a sub-pa e n qi: eq (qi) = # { ∈ R | pa ( ) =<qi,, u>} . (7) We de ine unc ion eq(), which is applied o he k h in e al om a ibu e Ai, gi ing he o al numbe o eco ds in k. A a ia ion o his unc ion includes es ic ing he numbe o objec s belonging o class c. 2 This is due o changes in he numbe o pa i ions o selec ed a ibu es as we show la e in sec ion 6. ATTRIBUTE SELECTION FOR CLASSIFICATION 471 eq(Ai, k) = #{ ä R | o di( i ( )) = k } eq(Ai, k, c) =#{ ä R | o di( i( )) = k ∧ label( ) = c } (8) Assuming ha pa i ion g anula i y is such ha allows all pa e ns o ha e a gi en label, we de ine unc ion labels(p), which e u n he se o labels associa ed wi h he subse o eco ds wi h pa e n p. labels(p) = { ∈ R, c∈ L | pa ( ) = p ∧ label( ) = c • c } . (9) The numbe o class labels a ached o a gi en pa e n p is: nlabels(p) = # labels(p) . (10) Using he Equa ion in (10) we de ine he s eng h o a pa e n as: s eng h(p) = # { i∈ (1..n) | nlabels(qi) = 1 } (11) 2.2 O he de ini ions De ini ion 1. A ibu e Ai is said o be semi-exclusi e o pa i ion k, i unc ion semk() is ue. Func ion semk() is de ined as: semk(Ai, k, j) =$ c∈ L • (( eq(Ai, k, c) / eq(Ai, k)) ³ j) (12) Pa ame e ϕ is a use -de ined alue ep esen ing he ac ion o eco ds in in e al k wi h class c. The special case when ϕ = 1, is e e ed o as an exclusi e in e al, meaning ha all Ai alues in his in e al belongs o he same class. A ibu es exhibi ing his ype o alue a e also desc ibed in he li e a u e as p ima y [Tu ney, 1996], [Koha i e al., 1997]. De ini ion 2. The deg ee o exclusi eness o a pa e n co esponds o he ac ion o pi elemen s wi hin pa e n p con o ming o he exclusi e alues p ope y. I is calcula ed wi h he ollowing unc ion: Semp(p, j) = # {i∈ (1..n) | semk(Ai, pi, j)} / n . (13) De ini ion 3. The deg ee o ele ance o a ibu e i deno ed wi h δ i, is he a io be ween he o al numbe o eco ds in semi-exclusi e pa i ions and N. La ge alues o d mean a mo e ele an a ibu e. δ i = # { ∈ R, k ∈ (1..si) | semk(Ai, k, j ∧ o di( i( )) = k • } / N . (14) The opposi e ep esen s i ele an a ibu es. De ini ion 4. The shape o a pa e n is de ined as: 21nn-1 shape(p)=(p-p),..,(p-p) (15) And he dis ance be ween wo pa e ns is: d(p, p’) = åi | pi – pi’| (16) Using equa ions om De ini ion 4 we can de ine he ollowing: IADIS In e na ional Con e ence e-Socie y 2003 472 De ini ion 5. The shape simila i y unc ion be ween shapes is de ined as: 1212 s (p,p)=d(shape(p), shape(p)) (17) In Figu e 1 we show semi-exclusi e in e als and he calcula ion o d o wo a ibu es, A1 and A2. An as e isk means mo e han one class o a gi en pa i ion; i.e. nlabels (pi) > 1. si 0 1 2 3 4 5 6 7 8 9 o al δ eq 77 32 62 49 79 20 12 23 11 43 408 A1 class * * * * * * * * 4 4 54 54/408=0.132 si 0 1 2 3 4 5 6 7 8 9 o al δ A2 eq 227 23 35 17 17 14 12 13 5 45 408 112/408=0.274 class * 2 * * 4 4 * 4 * 4 112 Figu e 1. A ibu e p ojec ion in one-dimensional space o a ibu es A1 and A2. 3. OVERVIEW OF THE CLASSIFICATION ALGORITHM We ha e p e iously de eloped a classi ica ion algo i hm o supe ised lea ning based on ins ances and he nea es neighbou pa adigm in [Se ende o e al., 2001]. Classi ica ion is done ex ac ing wo nea es pa e ns p+ and p- wi h espec o a que y pa e n px. The ex ac ion o p+ is done i s in a ecu si e way. Any sub- pa e n i q is o he o m i q =< 1 q i − , k>. S a ing wi h i = 1, assuming an emp y sub-pa e n q0+= <> and knowing elemen qi-1, he p oblem consis in inding he nex sub-pa e n by calcula ing some alue o k+, which sa is ies he ollowing p ope y: " kä K(qi-1) • (|k+ - kx| £ |k – kx|) . (18) The se K(q)is de ined by: K(q) = { k | <q, k>Î P} (19) Hence, k+ is he closes elemen o kx among he elemen s in K(qi-1). I wo alues o k+ e i ies Equa ion (18), hen we chose he one whe e eq(qi+) is a maximum. The algo i hm sea ches nex o pa e n p-. The sea ch mechanism is he same as o p+, bu wi h se K(q) using his ime pa e n p+ p e iously calcula ed: K(q) = {k |<q, k> ä P ∧ ((nlabels(<q, k>) > 1) ∨ ((labels(<q, k>) ∩ labels(qi+)) = ∅ )} (20) The new pa e n should ha e i s class dis inc om he p+ class. A inal s ep consis s in applying unc ion me i () o bo h selec ed pa e ns. The pa e n wi h he la ges me i (p) is he winne . This unc ion ep esen s an agg ega ion o se e al c i e ia, and is de ined as: ()() ii i me i pwp α=⋅ ∑ (21) E e y c i e ion in α i has weigh wi. These c i e ia α i (i = 1..6), numbe ed in no pa icula o de a e: • The deg ee o exclusi eness o a pa e n, calcula ed as α 1(p) = semp(p) om (13). • The s eng h o a pa e n, calcula ed om Equa ion (11). So α 2(p) = s eng h(p). ATTRIBUTE SELECTION FOR CLASSIFICATION 473 • The simila i y shape om De ini ion 5 and Equa ion (17) applied o a pa e n agains px o calcula e he mos simila shape: α 3(p) = s (px, p). • A numbe ela ed o he dis ance o px, calcula ed as α 4(p)= d(px, p) om Equa ion (16). • The equency o a pa e n, whe e a a la ge equency is a be e op ion, o he condi ions being equal. Func ion equency is calcula ed as α 5(p)= eq(p) using unc ion in (6). • Le be mc he majo i y class, he class wi h he la ges equency hen α 6(p) equals 1 i label(p) = mc and 0 o he wise. Weigh s a e ob ained p ep ocessing he aining da ase . The weigh o each c i e ion co esponds o i s deg ee o accu acy co ec ly classi ying pa e ns. Each c i e ion is es ed indi idually by se ing all o he weigh s o ze o. The goal is o op imise T, he deg ee o accu acy o each c i e ion. I is calcula ed as: T = Nº o eco ds co ec ly classi ied / N; and being he e o e = 1 -T (22) The applica ion o unc ion me i () a unning ime, allows selec ing he bes pa e n. I s class is assigned o px. A mo e de ailed explana ion o his p ocess is le o a nex a icle. In he algo i hm implemen a ion all aining pa e ns a e s o ed in o a ie [F edkin, 1960], including equencies and class in o ma ion a he sub-pa e n le el. These s uc u es ha e p o en o be e y as on sea ch p oblems [Be gman, 1994;Me e e al., 1996; Albe e al., 2001], which is one o he main p oblems in he nea neighbou pa adigm. The la ge s o age equi ed by ies is pa ially sol ed keeping he ile on disk. Also, se e al known comp ess ools a e a ailable o ies such as Pa icia ees [Gonne e al., 1991], X- ee [Be ch old e al., 1996] and Bu s ies [Heinz e al., 2002]. 4. ATTRIBUTE SELECTION 4.1 De e mining mos ele an a ibu es In gene al, ou me hod anks a ibu es by hei capaci y o p edic ing classes wi hou aking di ec ly in o conside a ion o he a ibu es om he o iginal sequence. We pos ula e ha his capaci y inc eases, when an a ibu e exhibi s a la ge deg ee o ele ance as s a ed in De ini ion 3. Fo ins ance, a ibu e Ai is ele an i some α pe cen age o i s ins ances wi h alue j is associa ed wi h class cl. In his sense, we so en he Boolean de ini ion ound in [Koha i e al., 1997]. Ou objec i e is o ind he mos disc imina i e a ibu es om he poin o iew o use ulness o he p edic o , wi h he pu pose o imp o ing i s p edic ion accu acy [Guyon, 2001]. This heu is ic c i e ion has been used success ully be o e [Liu e al., 2000]. A sub-pa e n q o size i can be a common p e ix o dis inc labels, i.e. when nlabels(qi) > 1, ep esen ing a eas o la ge en opy wi h espec o classes in he da a hype space, no allowing any conclusion on class membe ship. In e sely, sub-pa e ns whe e nlabels(qi) = 1, ep esen homogeneous egions, whe e smalle alues o i (sho e sub-pa e ns) ep esen la ge a eas. I a new ins ance o be classi ied alls in o one o hese a eas, i s chances o co ec classi ica ion inc ease. Mos o i s neighbou s will sha e he same label. Fo his eason, we a e in e es ed in looking a he en i e da a space om he iewpoin o a ibu es wi h la ge numbe o examples whe e classes a e “ isible” di ec ly om hem, hus a oiding endless combina ion o possibili ies as done in adi ional me hods [Koha i e al., 1997; Mille , 1990; B odley e al., 1995]. We conside hese a ibu es mo e ele an han o he s. Now, he sho es sub-pa e n con ains only one elemen q1 = <p1, c>, usually associa ed wi h se e al classes. We wan o ind which a ibu es pe o m be e han o he s in his si ua ion. To do his, all alues o an a ibu e a e p ojec ed in o a one-dimensional space p e iously pa i ioned in o equal in e al wid hs. In he ie s uc u e used o implemen a ion his co esponds o build he ee wi h a single le el. This esembles he 1R classi ica ion sys em [Hol e, 1993] al hough in his sys em he anking o ea u es is based di ec ly on e o a es. In ou case we a e in e es ed in he o al numbe o sub-pa e ns q1, ound in semi-exclusi e in e als ( om De ini ion 1), o a gi en a ibu e Ai and ϕ alues. A ibu es showing mo e indi idual pa e ns in hese in e als a e also mo e ele an (De ini ion 4). Based on his, ele ance can be se as a measu e o a ibu e compa ison as explained nex . IADIS In e na ional Con e ence e-Socie y 2003 474 4.2 Ranking A ibu es by hei ele ance Ranking a ibu es is done knowing which a ibu es a e compa a i ely mo e ele an han o he s. To do his we compu e each a ibu e’s ele ance om (14), and ank hem in dec easing o de acco ding wi h he alue o d, as he example shown in Fig. 1 o A1 whe e d = 0.132. This anking gi es as esul lis ß, which ep esen s all a ibu es o de ed by hei deg ee o ele ance: 12inii+1 ß = <, ,..,,...,>, | | || i(1.. n). δδδδδδ≥∈ (23) A ibu es whe e di = 0, a e o de ly pushed o he lis ’s end. The lis ep esen s he inpu o de o a ibu es used by he classi ica ion algo i hm. As shown in Sec ion 5 doing his imp o es he p edic i e accu acy o he classi ica ion algo i hm. 4.3 Reducing he numbe o a ibu es by hei deg ee o ele ance Reducing he numbe o i ele an a ibu es d as ically educes he unning ime o a lea ning algo i hm and yields a mo e gene al concep , easie o unde s and by he domain expe . This educ ion can be achie ed using he concep o a ibu e exclusi eness as de ined in Sec ion 3. This is done by elimina ing om lis ß in (23) all a ibu es whe e δ is small o ze o. This educ ion, hough, canno be done wi hou a cos . The ade-o is done a he expense o losing some p edic i e accu acy. Wi h his cons ain in mind, ou goal is o ind a minimum subse o a ibu es S’ such ha when he classi ica ion algo i hm is applied accep ing some e o e, we can ob ain a new p edic i e accu acy T´ as S’ ⊂ S, ha sa is ies T’ £ T + e . The new se S’ ob ained om lis ß in (24) includes only ele an a ibu es disca ding all o he s. The classi ica ion algo i hm ebuilds he ee using he new sequence in S’. A unning ime, and using some use -use -de ined e o o e he exis ing p edic ion alue T om (22), a new T’ alue is ob ained. E o e is a unc ion o cos and quali y [B odley, 1995]. I Equa ion (24) is sa is ied and (T’ – T) £ e, hen S’ is adop ed as he new se o a ibu es. O he wise, he h eshold alue o should be educed and lis ß ebuil . As a esul his will inc ease he numbe o a ibu es in subse S’ and hope ully will also inc ease p edic ion accu acy T’ diminishing he alue o e. 5. RESULTS We ha e es ed hese echniques on se en da ase s om he UCI eposi o y [Mu phy e al., 1994]. All eco ds wi h unknown a ibu e alues we e elimina ed. Ten– old c oss alida ion was used. Accu acy esul s we e a e aged. Table 1. New A ibu e O de using = 0.75 N. º Reco ds Nº Numbe A ib. Da ase T aining Tes New A ibu e O de Numbe ep esen s o iginal o dinal numbe (Bold ace = a ibu e is ele an ) Rele an A ibu es (%) 1 24 Hypo hy oid 1598 1063 18,23,21,1,20,22,7,5,13,24,19,17,16,15,14, 12,11,10,9,8,6,4,3 41.7 2 24 De ma ology 218 140 20,22,27,29,6,12,8,25,33,34,24,15,10,31,26, 30,14,23,7,32,28,21,19,18,17,16,13,11,9,5,4, 3,2,1 57.6 3 33 Adul 28468 15060 3,9,14,2,4,5,7,8,13,6,1,10,11,12 71.4 4 13 Diabe es 462 306 5,6,2,7,4,8,3,1 75.0 5 12 Fo es co e 15120 565892 1,10,5,6,4,12,8,7,9,3,11,2 83.3 6 12 Pendigi s 7494 3498 6,12,3,7,11,4,2,15,5,14,16,8,1,10,9,13 87.5 7 16 Cance –W. 407 273 7,2,1,8,3,9,4,6,5 100.0 The a e age dec ease in e o a e a e o de ing a ibu es o 4.3% in Table 2 is simila o esul s epo ed o di e en da ase s in a p e ious a icle whe e his echnique was applied [Se ende o e al., 2001]. This ATTRIBUTE SELECTION FOR CLASSIFICATION 475 con i ms ha he gain in p edic i e accu acy is signi ican and s eady when applied o di e en da a domains. I also con i ms he need o a ibu e o de ing when ee s uc u es and ins ance-based me hods a e Table 2. Va ia ion in p edic i e e o a e a e o de ing and educ ion in he numbe o a ibu es Classi ica ion: P edic i e E o Ra e (%) Va ia ion (%) due o: Nº Da ase s O iginal (A) O de ed (B) Reduced(C) O de (B-A) Reduc ion (C-B) 1 Fo es co e 28.2 20.5 23.9 -7.7 +3.4 2 De ma ology 10.2 4.5 6.5 -5.7 +2.0 3 Diabe es 27.8 22.2 22.5 -5.6 +0.3 4 Pendigi s 9.3 5.3 2.0 -4.0 -3.3 5 Cance –W. 5.5 2.2 1.8 -3.3 +0.4 6 Adul 18.9 16.0 10.6 -2.9 -5.4 7 Hypo hy oid 1.6 0.7 1.1 -0.9 -0.4 A e age -4.3 used, as is ou case. Al hough no conclusi e due o expe imen size, a ia ion in e o a es a e a ibu e educ ion (C-B) seems o be ela ed o he in ensi y o a ibu e “p uning” (Table 1). As expec ed, a la ge educ ion in he numbe o a ibu es esul s in g ea e e o a es. In 43% o cases educing he numbe o a ibu es inc eases p edic i e accu acy, meaning ha he anking me hod wo ks well. A ibu es a he lis ’s end a e indeed i ele an o p edic i e pu poses. Accu acy in he emaining da ase s shows a small loss no g ea e han 3.3% i compa ed wi h a 56% a e age educ ion on he numbe o a ibu es, and hence, in p oblem complexi y. In he ace o la ge da ase s wi h high dimensions whe e adi ional ea u e educ ion me hods ep esen e y high compu a ional cos s, his me hod can be a ai solu ion. Ou ea u e selec ion me hods in eg a ed in o he classi ica ion algo i hm helps o p oduce compe i i e esul s as shows i s compa ison wi h Quinlan’s landma k ool C4.5 (also known as See5) in Table 3. In gene al, ou classi ie shows be e pe o mance han C4.5 o da ase s wi h smalle numbe o classes and wo se when he opposi e is ue. This is explained by he ac ha in o de o speed up he sea ch p ocess, ou algo i hm only looks o wo close pa e ns accoun ing o only wo classes. Table 3. Compa ing classi ica ion accu acy agains he popula C4.5 E o in accu acy (%) Nº Da ase C4.5 Ou s 1 Adul (Census 94,USA) 14.6 10.6 ± 1.2 2 Fo es co e 29.1 20.5 ± 2.5 3 Cance -W 5.8 2.2 ± 0.2 4 Hypo hy oid 0.7 0.7 ± 0.3 5 De ma ology 3.9 4.5 ± 0.3 6 Pima Indian Diabe es 26.8 22.2 ± 1.4 7 Pendigi s 3.4 2.0 ± 0.5 Sou ce o C4.5 esul s: [Chou e al., 2000; Li e al., 2000; Mu phy e al., 1994; Chawla, e al., 2001]. 6. DISCUSSION In his a icle we p esen a simple and low-cos ea u e selec ion me hod, use ul o algo i hms using decision ees and ins ance-based me hods in supe ised lea ning. Resul s show on a e age a dec ease o o e 4% in classi ica ion p edic i e e o when a ibu es a e anked by hei deg ee o ele ance. This esul is consis en wi h p e ious esul s ob ained on di e en da ase s and o e s a simple solu ion o anking ea u es. Accu acy inc eases e en u he in 43% o cases a e a ibu e educ ion. This no only con i ms he co ec ness o his simple me hod o anking a ibu es, bu also he ac ha i wo ks as a good il e indica ion on he p edic i e skills o a ibu es. In he emaining 57% o cases a loss in p edic ion no g ea e han 3.3% did ep esen elimina ing an a e age o 56% o a ibu es o all da ase s conside ed. This is e y impo an o help educing algo i hm complexi y in high dimensional da ase s and he e o e he comp ehension o he domain expe in da a ela ions. IADIS In e na ional Con e ence e-Socie y 2003 476 Fu u e wo k includes modi ying sligh ly he algo i hm o ex ac as many pa e ns as classes exis in a da ase wi h he goal o inc easing p edic i e accu acy in da ase s wi h mo e han wo classes. This should no signi ican ly inc ease sea ch ime i we conside he excellence o ies wi h espec o sea ch pe o mance. REFERENCES Aha, D. W, Banke , R., 1994. Fea u e Selec ion o Case-Based Classi ica ion o Cloud Types: An Empi ical Compa ison. In Case-Based Reasoning: Wo kshop, Technical Repo WS-94-01, CA, USA., AAI P ess. Albe , I. E., e al.,, 2001. Fas Re ie al o Mul i and Hype spec al Images Using Rele ance Feedback. P oceedings o he In e na ional Geoscience and Remo e Sensing Symposium. Vol. 3, pp. 1149-1151. Ande sson, A, Nilsson, S., 1994. Fas e Sea ching in T ies and Quad ees – An Analysis o Le el Comp ession. P oceedings. o he Second Eu opean Symposium on Algo i hms, pp 82-93. Be ch old, S. e al., 1996. The X- ee: An Index S uc u e o High-Dimensional Da a. P oceedings o he 2 nd In e na ional Con e ence on Ve y La ge Da abases, Bombay, India, pp. 28- 39. Be man, A.P., 1994. A New Da a S uc u e Fo Fas App oxima e Ma ching. Technical Repo , 1994-03-02, Dep . o Compu e Science, Uni e si y o Washing on. B odley, C. E., 1995. Mul i a ia e Decision T ees. Machine Lea ning, Vol. 19(1), pp. 45-77. Chawla, N. e al., 2001. C ea ing Ensembles o Classi ie s. P oceedings o he 2001 IEEE In e na ional Con e ence on Da a Mining, CA, USA, pp. 580-81. Chou, Y., Shapi o, L. G., 2000. A Hie a chical Mul iple Classi ie Lea ning Algo i hm. P oceedings o he In l. Con e ence on Pa e n Recogni ion, Vol. 2, pp. 152-155. Co e , T. Ha , P. 1967. Nea es neighbou pa e n classi ica ion. IEEE T ansac ions on In o ma ion Theo y, Vol. 13:1, pp 21-27. Doughe y, J., e al., 1995. Supe ised and Unsupe ised Disc e iza ion o Con inuous Fea u es. P oc. o he 12 h In e na ional Con e ence on Machine Lea ning, Mo gan Kau man Publishe , San Fco. USA., pp. 94-202. F edkin, E., T ie Memo y, 1960. Communica ions o he ACM, Vol.3: 9, pp. 490-500. Gonne , G. H., Baeza-Ya es, R., 1991. Handbook o Algo i hms and Da a S uc u es, Addison-Wesley, UK. Guyon, I., 2001. In oduc ion o he NIPS 2001, Wo kshop on Va iable and Fea u e Selec ion. BC., Canada. Heinz, S., Zobel, J., 2002. Williams, H.E., Bu s T ies: A Fas , E icien Da a S uc u e o S ing keys. ACM T ansac ions on In o ma ion Sys ems, 20(2): pp. 192-223. Hol e, R.C., 1993. Ve y Simple Classi ica ion Rules Pe o m Well on Mos Commonly Used Da ase s. Machine Lea ning, 11, pp 63-91. Indyk, P., 2000. Dimensionali y Reduc ion Techniques o P oximi y P oblems. P oc.11 h.ACM-SIAM Symposium on Disc e e Algo i hms, pp. 371,378. Koha i, R, John, G., 1997. W appe s o Fea u e Subse Selec ion. A i icial In elligence Jou nal, Special issue on ele ance, Vol. 97, Nº 1-2, pp. 273-324. Lebowi z, M., 1985. Ca ego izing Nume ic In o ma ion o Gene aliza ion. Cogni i e Science, (9) pp. 285-308. Li, J., Dong, G., Ramamohana ao, K., 2000. Ins ance-Based Classi ica ion by Eme ging Pa e ns. P oc.Fou h Eu opean Con . On P inciples and P ac ice o Knowledge Disco e y in Da abases, Sp inge -Ve lag, pp. 191-200. Lesh, N., e al., 1998. Mining Fea u es o Sequence Classi ica ion. MERL, Technical Repo : TR98-22. Liu, B., e al., 2000. Imp o ing an Associa ion Rule Based Classi ie . 4 h Eu opean Con e ence on P inciples and P ac ice o Knowledge Disco e y in Da abases, Lyon, Sp inge -Ve lag, pp. 504-509. Me e , T.H. e al., 1996. Da abase S uc u es, Based on T ies, o Tex Spa ial and Gene al Da a. In . Symposium on Coope a i e Da abase Sys ems o Ad anced Applica ions, Kyo o, pp. 316:324. Mille , A.J., 1990. Subse Selec ion in Reg ession. Chapman & Hall, New Yo k, USA. Mu phy, P.M., Aha, D.W., 1994. UCI Reposi o y o machine lea ning da abases.Uni e si y o Cali o nia, I ing, Depa men o In o ma ion and Compu e Science. Pa ick M. Mu phy (Reposi o y Lib a ian). Quinlan, J., 1986. Induc ion o Decision T ees. Machine Lea ning, Vol. 1, pp. 81-106. Se ende o, P., To o, M., 2001. Supe ised Lea ning Using Ins ance-based Pa e ns. P oceedings o he IX Con e encia de la Asociación Española pa a la In eligencia A i icial, Spain, Vol. I, pp. 83-92. Tu ney, P.D. 1996. The managemen o con ex -sensi i e ea u es: A e iew o s a egies. 13 h In e na ional Con e ence on Machine Lea ning (ICML96),Ba i, I aly, July, pp. 60-66.