Supervised Learning Using Instance-based Patterns

See discussions, s a s, and au ho p o iles o his publica ion a : h ps://www. esea chga e.ne /publica ion/228937485 Supe ised Ins ance-based Lea ning Using Pa e ns in a T ie like S uc u e A icle CITATION 1 READS 283 2 au ho s: Some o he au ho s o his publica ion a e also wo king on hese ela ed p ojec s: GEOZOCO View p ojec Fai ness View p ojec Pa icio Se ende o Uni e sidade do Alga e 4 PUBLICATIONS18 CITATIONS SEE PROFILE Miguel To o Uni e sidad de Se illa 210 PUBLICATIONS1,642 CITATIONS SEE PROFILE All con en ollowing his page was uploaded by Miguel To o on 29 May 2014. The use has eques ed enhancemen o he downloaded ile. Supe ised Lea ning Using Ins ance-based Pa e ns Pa icio Se ende o1, Miguel To o2 [email p o ec ed], [email p o ec ed] 1Facul y o Sciences and Technology, U. o Alga e, Fa o, Po ugal 2Dep . o Languages and In o ma ion Sys ems, U. o Se ille, Se ille, Spain Abs ac : This pape in oduces a new classi ica ion algo i hm o he ins ance-based lea ning ype. T aining eco ds a e con e ed in o pa e ns associa ed wi h a known class label, and s o ed pe manen ly in o a ie1-like ee s uc u e along wi h o he help ul in o ma ion. Classi ying new eco ds is done selec ing om he ie wo bes pa e ns as solu ions hypo heses. Bes pa e n selec ion is done using s anda d dis ance me ics, a s eng h unc ion and an exclusi e alues concep . Classi ica ion es s done on se e al da a iles ha e shown e y accu a e esul s. Keywo ds: supe ised lea ning, ins ance-based, pa e n s eng h, exclusi e alues, ie. 1 In oduc ion Supe ised lea ning echniques, known also as classi ica ion, belong o he a eas o Ma- chine Lea ning and Knowledge Da a Disco e y. In gene al, hei goal is o build up al- go i hms able o p edic class labels in da a iles o whole da abases. T aining eco ds o known class labels a e used in he c ea ion o he algo i hm. La e , hese a e used o p edic unknown classes p e iously unseen eco ds. A ple ho a o me hods and ools exis s o his pu pose. Among hem: classi ica ion ee induc ion [23], [16], Bayesian classi ica ion me hods [5], [9], neu al ne wo ks [26], gene ic algo i hms [13], [17], and o he s2. Mo i a ion o his wo k is a ound he ollowing opics: a) To ea da a in such a way as o make hem independen om a ibu e ypes. 1 P onounced “ y”, aken om he middle pa o wo d “ e ie e” [12] 2 See also a compa ison o Da a Mining Tools in [10]. Pa icio Se ende o, Miguel To o CAEPIA 2001 b) Ha e no one gene al hypo hesis model bu many hypo heses unc ions o eco ds o be classi ied. c) To use da a s uc u es ha so en somehow p oblems o a ibu e selec- ion and h eshold alue ypical o bina y decision ees. [32]. 2 P oblem De ini ion Le us conside he closed uni e se o med by a da a ile R composed o a ini e se o m eco ds . R = { 1, 2,.., m } (1) We conside se R as o med by a aining subse RT and a es subse RX, such ha R = RT ∪ RX. The i s one will be used o lea n da a pa e ns and o help de eloping he classi ica ion algo i hm. RX is used o es ing and algo i hm e i ica ion. In a gi en e- co d , we ind a ini e sequen ial se o a ibu es S. S = {A1, A2, Ai… An }, a nonemp y se . (2) E e y a ibu e Ai ∈ S can ake i alues belonging o a se Ti, whe e Ti is he domain alue. E e y eco d can be associa ed wi h class labels l1, l2, e c. belonging o a se L.3 L = {l1, l2, lk} (3) Each eco d is o med by he Ca esian p oduc o a ibu e alues A|V and a label l, such ha : = { 1, 2, ..., n, l } i ∈ Ti, l ∈ L. (4) F om hese de ini ions, we can de ine he ollowing basic unc ions: ali( ) = i, he alue associa ed o a ibu e i om eco d label( ) = l, he label associa e wi h eco d . (5) 3 Pa e n De ini ion Da a a ibu es can ha e di e en da a ypes: quali a i e o non-nume ical (symbolic, linguis ic); quan i a i e o nume ical (con inuous, disc e e). We would like o ea hem equally, in o de o c ea e pa e ns whe e all a ibu e alues a e ep esen ed by in ege s. Fo non-nume ical o ca ego ical da a, we do an a bi a y enume a ion, i no al eady o de ed by he domain expe . In addi ion, we apply disc e iza ion o all con inuous- alued eco d’s a ibu es. Disc e iza ion is he p ocess o ans o ming he domain o a con inuous a ibu e o ea u e in o a ini e numbe o in e als. Fo all Ai, use -de ined in e als wi h lowe and uppe alue-limi s a e es ablished in Ti. Thus, o each a ibu e Ai co esponds a pa i ion o he domain Ti. In e als a e ep esen ed by in ege s wi h 3 In his a icle we use indis inc i ely he wo ds class label, class o jus label. Supe ised Lea ning Using Ins ance-based Pa e ns CAEPIA 2001 alues om 1 o si. Thus, we con e e e y a ibu e Ai in o a pa e n alue. Func ion o d() does his con e sion: pi = o di ( i), i∈ Ti, pi ∈ 1,.. si . (6) This unc ion e u ns pi, an in ege alue ep esen ing one in e al alue o a ibu e Ai. We can de ine a pa e n p as he sequence o med by n alues. p = <p1, p2,.., pi,..,pn> pi = {1..si} (7) To each eco d = < 1, 2,..,, n, l> co esponds a pa e n ob ained by applying unc- ion o di(). Hence, o e e y eco d we ob ain he co esponding pa e n p associa ed wi h a gi en label as ollows: pa ( ) = p = < p1, p2,..,pn> = 〈o d1( 1), o d2( 2),..,o dn( n)〉 (8) Fo e e y pa e n p we can de ine n sub-pa e ns qi, which a e he p e ix po ion o a pa e n. qi = <p1, p2,.., pi >, qi subsequence o p, i = {1..i}. (9) Func ion eq(p) e u ns he numbe o eco ds in RT wi h pa e n p. eq(p) = { ∈ RT pa ( ) = p } (10) In addi ion om abo e we can de ine λi = eq(qi), he equency o sub-pa e ns qi. (11) Labels a e a ached o pa e ns. Func ion labels(p) e u ns he se o labels associa e o he subse o eco ds wi h pa e n p. labels(p) = { l ∈ L  ∃ ∈ RT • label( ) = l ∧ pa ( ) = p } (12) F om his, we de ine unc ion nlabels(p) =  labels(p) , nlabels(p) = {1..L } We can ex end his concep o sub-pa e ns. Hence, (nlq)i = nlabels(qi) (12a) In any da ase RT we ind ha gene ally unc ion nlabels (pn) = 1, meaning ha a gi en ull pa e n p ∈ RT is associa ed wi h one label, making da a consis en . As o sub-pa e ns, we o en ind ha nlqi > 1, meaning ha mo e han one label sha es he same qi. This is he o e lapped a ea o pa e ns. In gene al his is he case o ini ial al- ues o i; As he alue o i app oaches n, ac o nlqi end o be associa ed wi h one label and nlabels (p) = 1. F om an in ui i ely iewpoin each pa e n p ep esen a hype cube in a space o n dimensions. Func ion eq (p) measu es he numbe o eco ds om RT in ha hype cube. Func ion labels (p) ep esen s he se o labels p esen in ha hype cube. Pa icio Se ende o, Miguel To o CAEPIA 2001 4 O he De ini ions 4.1 Dis ance Be ween Pa e ns Se e al supe ised lea ning me hods use a me ic dis ance o compa e a ibu e alues. [7]. We calcula e he minimum dis ance be ween wo pa e ns applying he minimum squa e me hod: 1 2' 1 /)||()',(λ i n iippppd −= ∑ = (13) The o e all equency o pa e n p ep esen ed by λ1, is used o add weigh o he measu e o dis ance. 4.2 The s eng h o a Pa e n We di e en ia e be ween s ong and weak pa e ns acco ding o he numbe o single class labels associa ed o each one o i s n sub-pa e ns. I (nlq) i = 1, sub-pa e n qi is s ong. The con a y means a weak sub-pa e n. We de ine unc ion s ongp(p) as a measu e o pa e n s eng h as ollows: s ongp(p) = {i : 1..n. nlabels(qi) = 1 } | (14) Func ion s ongp() a ies om 0 o n and ep esen s he o al numbe o sub-pa e ns qi o p associa ed wi h jus one label. When s ongp (p) = n, he pa e n s eng h is maximum. I (nlabels (qi) > 1 hen (nlq) i = 0, a weak sub-pa e n. An impo an p op- e y o sub-pa e ns is ha once he i h sub-pa e n becomes associa ed wi h one label, hen all subsequen pi+1, pi+2, pi+n sub-pa e ns also ela e o he same label. When i = n, class o e lapping should disappea ; we expec ha he label a ached o he n h elemen is he label a ached o pa e n p as a whole. This is ou basic assump ion: no wo iden i- cal ull pa e ns a e ela ed o di e en classes. I such case exis s p obably due o noise da a, we conside he pa e n as comple ely weak. We could no make any p edic- ion abou i s label. This same c i e ion has been used be o e. See [11] and [31]. 4.3 Exclusi e Values We de ine exclusi e alues as he unique maximum and minimum in e al alues shown by a gi en pi ∈ p always associa ed wi h he same label in RT. F om he poin o iew o a label, his ep esen s i s associa ion wi h a gi en pi and some alue k o all pa e ns p in RT. This can be ep esen ed wi h he ollowing unc ions: s (i, k) = { ∈ RT | pa ( ) = <p1,..,pi,..,pn> and pi = k } ; sl(i, k) = label((s (i, k)) and unc ion Supe ised Lea ning Using Ins ance-based Pa e ns CAEPIA 2001 nsl(i,k) = sl(i,k) (15) Then, we de ine exclusi e alues as: α = ex(p) = Ni : 1..n (nsl(i, pi) = 1)) (16) The numbe o pi alues in pa e n p ha appea always ela ed o a gi en class. 4.4 The Majo i y Class T aining se RT includes one o mo e subse s o eco ds associa ed wi h he same class l; ha is: RT = Rl1 ∪ Rl2 ∪ Rli ∪ Rlj whe e Rlj is he se o eco ds wi h label lj. We de ine majo i y class as he class wi h maximum numbe o eco ds in RT, calcula ed as ol- lows: lmaj(RT) = max(R11,Rl2,..,Rlj ) (17) In popula ions wi h say, wo classes l1 and l2, whe e class l1 is s ongly p edominan , we will p edic l2, only when s ong e idence is ound ha his is he case [14]. 5 Algo i hm The algo i hm is execu ed in wo phases. The i s co esponds o a p e-p ocessing. I is he lea ning phase. I consis s in eading sequen ially all eco ds in RT and applying o each one o hem he unc ion in (7) con e ing hem in o p pa e ns and s o ing hem in o a ie s uc u e. In his p ocess he label indica o and a equency λi o each sub- pa e n qi, a e s o ed as well. Hence, o e e y pa e n in RT, he s uc u e holds: p = <(q1, nlq1, λ1), (q2, nlq2, λ2),..,(qn, nlqn, λn)> (18) We de ine P as he se o pa e ns in RT wi h eq () > ze o. This is o say, all exis - ing pa e ns in RT. Each one o hem is associa ed wi h a known class l. P = {p  eq (p) > 0 } (19) The second phase is he ac ual classi ica ion p ocess. This is he p edic i e phase. A new es ile RX is ead in sequen ially; o each eco d in RX, he algo i hm pe o ms he con e sion px = pa ( ) gene a ing he a ge pa e n px o unknown class label. Fo each pxi alue in px, he algo i hm looks in he s o ed pa e n s uc u e o he closes pi alues using i s dis ance me ic ob aining pa e n p+. This is he closes exis ing pa e n in RT wi h espec o px. We epea his ope a ion in a sligh ly di e en way o ob ain a “second” bes pa e n p-. These wo pa e ns ep esen ou solu ion hypo heses. One o hem will be chosen o p edic he class o he unseen pa e n px. Pa e ns p+ and p- can be de ined as ollows: Fo any sub-pa e n qi, we de ine he se o k in ege s nex (qi). An in ege k is in nex (qi) i <qi, k> i is a sub-pa e n o P. Gi en px, hen p+ and p- a e de ined ecu si ely: Le q+i, q-i, and qxi, be sub-pa e ns o p+, p- and px espec i ely. Fu he , le be Pa icio Se ende o, Miguel To o CAEPIA 2001 q+i +1 = <q+i, k+>, q-i +1= <q-i, k-> and qxi +1 = <qx i, kx>. Thus, k+ is he closes in ege in nex (q+i) o kx and k- is he closes in ege in nex (q-i,) o kx. Pa e n p+ is he closes o px in RT and is calcula ed i s . I wo iden ical pa e ns ex- is in RT and RX, hen px = p+, and labels(px) = labels(p+.) Pa e n p- is sea ched nex . The selec ed pa e n mus be di e en om p+, bu as close as possible o px. I a k- alue di e en om k+ is no a ailable o add in nex sub-pa e n <q-i, k->, exis ing alue k+ is used ins ead. When his is achie ed, q-i becomes dis inc om q+i,. Subsequen p-i+1 alues a e calcula ed as p+ was. Unseen px ins ances a e p edic ed based on he closes dis ance om p+ and p- (13), plus h ee o he pa ame e s. The i s is he s eng h o a pa e n. F om s eng h unc ion in (14), we de ine he ollowing wo unc ions: s + = s ongp(p+) and s - = s ongp(p-) (20) We conside a pa e n s ong, i he a ea we e i belongs is clea ly mo e disjunc i e han o he s, wi h espec o a gi en class. Secondly, he algo i hm sees whe he pa e ns p+ and p- show he p esence o exclu- si e alues. Applying he exclusi e unc ion ex() om (16) we can ob ain pa ame e s α+ and α- as ollows: α+ = ex(p+) and α- = ex(p-) (21) Fac o α ep esen s a deg ee o con idence in he disjunc i e quali y o a pa e n's se o a ibu e alues. I s alue inc eases om ze o by one as mo e pi alues p esen ha ea u e. The algo i hm will a o he pa e n showing a la ge ex (p) alue. I a e applying hese c i e ia he algo i hm s ill canno p edic a label o px, hen unc ion lmaj() is used. p + p - p x Region o he hype space ℜn no co e ed by se P Exclusi e alue Figu e 1. A new pa e n px om RX. Pa e ns p+ and p- a e ob ained om RT. Pa e n px is close o p+ in he hype space. I shows an exclusi e alue co esponding o he same class as p+. 6 Resul s We ha e pe o med expe imen s wi h ou algo i hm ha we call T ie-Class on se e al da ase s, and compa ed wi h published esul s in he li e a u e. Da ase s used o es ing Supe ised Lea ning Using Ins ance-based Pa e ns CAEPIA 2001 comes om public domain in he web, mainly om he UCI[19]. Reco ds wi h un- known a ibu e alues we e emo ed o con e ed o i s mean alue. Using a andom unc ion each ime on he comple e ile, he s anda d en- old c oss alida ion p ocedu e has been done o all esul s. Accu acy alues a e calcula ed o he es ile. We ha e used a ound 60% o eco ds o he aining ile RT; he emaining 40% o es ile RX. Resul s ob ained wi h o he ools we e aken om se e al sou ces, namely [22], [20], [21], [24], [25] and [3]. Table I. Table I. S a log Hea disease ile. _____________________________________________ Me hod Accu acy % Re e ence _____________________________________________ T ie-CLASS 96.2 Ou s Naï e Bayes 83.6 WEKA, RA K* 76.7 WEKA, RA IB1 74.0 WEKA, RA 1R 71.4 WEKA, RA T2 68.1 WEKA, RA MLP+BP 65.6 ToolDiag, RA FOIL 64.0 WEKA, RA RBF 60.0 ToolDiag, RA Induc H 58.5 WEKA, RA Table II. Pima Indian Diabe es ile. ____________________________________________________________ Me hod Accu acy % Re e ence ____________________________________________________________ T ie_CLASS 89.5 Ou s LogDisc 77.7 S a log Incne 77.6 N.jankowski DIPOL92 77.6 S a log Linea Disc . Analysis 77.2 -77.5 S a log, S e & Dobnika SMART 76.8 S a log GTO DT(5xCV) 76.8 Benne and Blue ASI 76.6 S e & Dobnika kNN, k=22, Manha an 75.5 Ka ol G udzinski OC1(10 5- old CV) 73.4 -75.4 Mu hy e al. C4.5 73.0 S a log . Table III. Hea disease, Cle eland ile. ___________________________________________________________________ Me hod Accu acy % Re e ence ___________________________________________________________________ T ie_CLASS 98.2 Ou s Pa icio Se ende o, Miguel To o CAEPIA 2001 Incne 90.0 N. Jankowski 28-NN,s and Euclidean, 7 ea u es 85.1± WD/KG LDA 84.5 S e & Dobnika Fishe disc iminan analysis 84.2 S e & Dobnika 16-NN, s and, Euclidean 84.0±0.6 NCU 25-NN, s and, Euclidean 83.6 ±0.5 NCU FSM, 82.4-84% on es only 84.0 R. Adamczak Naï e Bayes 82.5-83.4 Ra al, S e , Dobnika C4.5(5xCV) 77.8 Benne and Blue Table IV. Annealing ile. (S e ling & Bun ine). A ibu e in e als used: wid h= 20, s eng h = 700, len = 50 and hick = 50. __________________________________________________ Me hod Accu acy % Re e ence ________________________________________________ T ie-CLASS 98.6 Ou s LB 96.4 Bing Liu CBA 96.4 Bing Liu RIPPER 95.4 Bing Liu C4.5 (AdaBoos Ensemble) 95.1 Quinlan [24] Table V. Sa elli e image ile (STATLOG e sion) We used only ou a ibu es as sugges ed: 17, 18,19 and 20. ________________________________________________ Me hod Accu acy % Time ________________________________________________ T ie_CLASS 91.1 8 k-NN 90.6 944 LVQ 89.5 44 Dipol92 88.9 111 Radial 87.9 74 Alloc80 86.8 28757 IndCa 86.2 9 CART 86.2 14 MLP+BP 86.1 53 Bayesian T ee 85.3 10 C4.5 85.0 1 New ID 85.0 53