Instance and feature weighted k-nearest-neighbors algorithm

Ins ance and Fea u e Weigh ed k-Nea es -Neighbou s Algo i hm Gab iel P a and Llu´ıs A. Belanche Compu e Science Depa men - Uni e si a Poli `ecnica de Ca alunya Omega Building, Jo di Gi ona 1-3, 08034, Ba celona - Spain Abs ac . We p esen a no el me hod ha aims a p o iding a mo e s able selec ion o ea u e subse s when a ia ions in he aining p o- cess occu . This is accomplished by using an ins ance-weigh ing p ocess –assigning diffe en impo ances o ins ances– as a p ep ocessing s ep o a ea u e weigh ing me hod ha is independen o he lea ne , and hen making good use o bo h se s o compu ed weig hs in a s anda d Nea es - Neighbou s classifie . We epo ex ensi e expe imen a ion in well-known benchma king da ase s as well as some challenging mic oa ay gene ex- p ession p oblems. Ou esul s show inc eases in s abili y o mos subse sizes and mos p oblems, wi hou comp omising p edic ion accu acy. 1 In oduc ion The ea u e subse selec ion (FSS) p oblem has been s udied o many yea s by he s a is ical as well as he machine lea ning communi ies. Howe e , he s abili y o he FSS p ocess has been ela i ely neglec ed in he li e a u e un il e y ecen ly –see e.g. [1, 2]. P e ious esea ch aimed a quan i ying s abili y, a he han enhancing i , leading o he de elopmen o s abili y measu es [3]; ew wo ks add ess he explici imp o emen o such s abili y, no ably [2]. In p e ious wo k, we s udied me hods aimed a p o iding a mo e s able se- lec ion o ea u e subse s when a ia ions in he aining p ocess occu [4], in a way ha is independen o he lea ne o he specific FSS algo i hm. We a gue he e ha i is possible ha he classifica ion abili y o diffe en ea u es a ies ac oss he ea u e space: o some subse o he da a we should use a ce ain se o ea u es, while o some o he subse ano he se o ea u es esul s in a be - e classifica ion accu acy; con e sely, he ins ances may con ibu e diffe en ly o he impo ance o ea u es. Ou objec i e is he e o e o os e he s udy o possible syne gies be ween bo h asks o ul ima ely de elop wo kable lea ning algo i hms. In his pape we p esen a me hod ha combines he weigh ing o in- s ances wi h he ea u e weigh ing p ocess in o a mo e effec i e doubly-weigh ed Nea es -Neighbou s classifie . We epo pe o mance in a se ies o expe imen s, using well-known benchma king da ase s and some challenging mic oa ay gene exp ession p oblems. Ou esul s show imp o emen s in FSS s abili y o mos subse sizes and p oblems, wi hou comp omising p edic ion accu acy. 2 P elimina ies Le D={(x1, 1),...,(xN, N)}be a aining da a se o leng h N, each ins ance xn∈Rdwi h i s co esponding class label n.Thema gin o an ins ance wi h 605 ESANN 2016 p oceedings, Eu opean Symposium on A i icial Neu al Ne wo ks, Compu a ional In elligence and Machine Lea ning. B uges (Belgium), 27-29 Ap il 2016, i6doc.com publ., ISBN 978-287587027-8. A ailable om h p://www.i6doc.com/en/. espec o a hypo hesis (a classifica ion ule, in his case) measu es he confidence o he classifie when making i s p edic ion [5]. In pa icula , he hypo hesis ma gin o xis he dis ance be ween he hypo hesis and he closes hypo hesis ha assigns an al e na i e label o x. Fo 1-Nea es -Neighbou s, he hypo hesis ma gin o an ins ance x o a se o da a poin s Dis gi en by [6]: θD(x)=1 2x−m(x)−x−h(x)(1) whe e m(x)andh(x)a e henea hi and nea miss o x: hose ins ances in Dnea es o xwi h he same and wi h a diffe en class label, espec i ely. Relie is a fil e algo i hm ha uses he hypo hesis-ma gin concep in eq. (1) o assess he impo ance o each ea u e in a da ase Das he accumula ed influence ha each ea u e has in compu ing he ma gin o e e y ins ance in D[7]. In pa icula , Relie edF is a de e minis ic ea u e anking algo i hm ha depends on a use -defined pa ame e l. The algo i hm picks one ins ance a a ime and compu es he hypo hesis ma gin o each ea u e independen ly, accumula ing he ea u e-wise dis ances o he lnea es hi s and lnea es misses. Simba is a mo e ecen ea u e weighing algo i hm ha assigns weigh s o ea u es based on hei con ibu ions o he hypo hesis ma gins o he ins ances [5]. Since be e gene aliza ion is expec ed i ins ances ha e la ge ma gins, one should a ou ea u es ha con ibu e mo e o hese ma gins. Ins ances x achie ing highly posi i e θD(x) p esen good modeling beha io (being a om misses and close o hi s), while hose wi h highly nega i e θD(x) become ou lying ones (su ounded by misses and a om hi s). The p esence o absence o hese la e ins ances in a aining sub-sample is he e o e a sou ce o uns abili y. In he Ma gin-based Ins ance Weigh ing (MBIW) me hod, an ins ance x∈ Rdcan be mapped o xacco ding o x j=|xj−m(x)j|−|xj−h(x)j|[8]. The la ge he alue o x j, he mo e ea u e jcon ibu es o he ma gin o ins ance x; husxcap u es he local p ofile o ea u e ele ance. To compu e an o e all ele ance o x, he a e age o e all ma gin ec o s is aken, e y much as Relie does; hen he weigh o an ins ance xis gi en by: ω(x)= 1/dis (x) N i=1 1/dis (x i),whe e dis (x)= 1 N−1 N−1  i=1,x i=xx−x i(2) 3 Combining Ins ance and Fea u e Weigh ing An impo an p oblem wi h he hypo hesis-ma gin concep defined in eq. (1) is he p esence o noise. By his we mean e e y aspec in he da a ha is specific o he pa icula aining sample (i.e., i is no a egula i y o he p oblem). This may affec bo h ins ances (ou lie s), o ea u es ( edundan o i ele an ), and will ce ainly mislead he ma gin calculus o an ins ance. The p oposed me hod ex ends Simba o inco po a e he ins ance weigh s ob ained wi h he MBIW me hod in o he ea u e weigh s, o influence he way Simba beha es. 606 ESANN 2016 p oceedings, Eu opean Symposium on A i icial Neu al Ne wo ks, Compu a ional In elligence and Machine Lea ning. B uges (Belgium), 27-29 Ap il 2016, i6doc.com publ., ISBN 978-287587027-8. A ailable om h p://www.i6doc.com/en/. In his pape , he MBIW me hod is execu ed fi s and he weigh s a e handed o e o Simba. Howe e , ou amewo k is qui e flexible and one could also conside he o he way a ound. We es ed wo diffe en e sions: No mal: unmodified Simba algo i hm (all ins ances d awn andomly) Sample: base ins ance selec ion on he p obabili y dis ibu ion gi en by he lea ned ins ance weigh s O de : so ins ances by dec easing weigh , and base he i e a ion o de di ec ly on he esul ing o de (no andomness) We call he me hods SimbaMBIW:Simba wi h Ma gin Based Ins ance Weigh ing (pseudo-code is shown in Algo i hm 1). No e he use o he weigh ed no m o a ec o zas zw=d  i=1 w2 iz2 i. Using his combined s a egy, ea- u es can be anked acco ding o hei impo ance (using he wweigh s), and a he same ime a ou ing s abili y due o he ωweigh s. Algo i hm 1: SimbaMBIW (D) 1Compu e ins ance weigh s ωusing eq. (2) 2w←(1,1,...,1) ; // Ini ialize ea u e weigh s 3 o n←1 o Ndo 4i s a egy is o de hen 5le xbe he ins ance anked in posi ion nacco ding o ω 6else i s a egy is sample hen 7d aw an ins ance x om D, acco ding o he dis ibu ion ω/ω1 8else 9le xbe he n h ins ance o a andom pe mu a ion o D 10 end 11 calcula e m(x)andh(x) wi h espec o D {x}using ·w 12 o i←1 o ddo 13 Δi←1 2(xi−(m(x))i)2 x−m(x)w−(xi−(h(x))i)2 x−h(x)wwi 14 end 15 w←w+ω(x)Δ 16 end 17 w←w2/ w2 ∞whe e (w2)i:= (wi)2 4 Expe imen al Wo k This sec ion p o ides empi ical e alua ion o he p oposed me hod. We es i o e i y i s eal applicabili y in h ee g oups o p oblems: a selec ion o 15 da ase s om he UCI machine lea ning eposi o y, he fi e p oblems used in he FSS 607 ESANN 2016 p oceedings, Eu opean Symposium on A i icial Neu al Ne wo ks, Compu a ional In elligence and Machine Lea ning. B uges (Belgium), 27-29 Ap il 2016, i6doc.com publ., ISBN 978-287587027-8. A ailable om h p://www.i6doc.com/en/. UCI da ase s p oblem dC N Diabe es 8 2 768 Glass 10 6 214 Hea 13 2 20 Ionosphe e 34 2 351 Landsa 36 6 6,435 LSVT Voice 309 2 126 Mammog am 65 2 86 Musk 168 2 6,598 Pa kinsons 23 2 197 Pop Failu es 18 2 540 Spec F 44 2 267 Sona 60 2 208 Vehicle 18 4 946 Wa e o m 21 3 5,000 Wdbc 10 2 699 Mic oa ay da ase s p oblem dC N B eas cance 24,481 2 97 Colon umou 2,000 2 62 GCM 16,063 14 190 Leukemia 7,129 2 72 Lung cance 12,533 2 181 P os a e cance 12,600 2 136 NIPS Challenge da ase s p oblem dC N A cene 10,000 2 200 Dex e 20,000 2 600 Do o hea 100,000 2 1,150 Gise e 5,000 2 7,000 Madelon 500 2 2,600 Table 1: Da ase desc ip ions: d, C, N a e he numbe o ea u es, classes and ins ances, espec i ely. challenge o ganized du ing he NIPS’2003 con e ence and six widely-used cance mic oa ay da a –Table 1. The s abili y o an algo i hm in selec ing a subse o k ea u es ou o he ini ial ull ea u e size do e a ba ch o M uns can be e alua ed using he Kunche a index (KI), defined as in [1]: KI (E(k)) = 2 M(M−1) M−1  i=1 M  j=i+1 |Si(k)∩Sj(k)|−(k2/d) k−(k2/d) whe e Si(k) is he subse o selec ed ea u es o leng h kin he i- h un, and E={S1,S 2, ..., SM}is he se con aining all he e ie ed ea u e subse s. KI alues a e bounded in [−1,1], wi h 1 co esponding o he maximum s abili y. The expe imen al se up consis s o he wo nes ed c oss- alida ion loops: o e - e y old and epe i ion o he ou e c oss- alida ion loop, wo ea u e-weigh ing p ocesses a e conduc ed wi h he same ins ances: one wi h he o iginal Simba algo i hm and one wi h ou modified e sion aking ins ance weigh s in o ac- coun . The KI is compu ed o e e y subse leng h a e e y pa i ion loop and hen a e aged o e he 10 imes. Once he ea u es ha e been ob ained we es he ob ained ea u e weigh s using a modified k-NN classifie ha accep s bo h ins ance and ea u e weigh s, eco ding p edic ion accu acy on he le ou es pa s. We use hese weigh s o pe o m an inne 5x2- old c oss- alida ion wi h he pu pose o es ima ing he p edic ion e o o each classifie . This e o is hen compu ed o each old o compa e he ea u e se s selec ed by SimbaMBIW. 608 ESANN 2016 p oceedings, Eu opean Symposium on A i icial Neu al Ne wo ks, Compu a ional In elligence and Machine Lea ning. B uges (Belgium), 27-29 Ap il 2016, i6doc.com publ., ISBN 978-287587027-8. A ailable om h p://www.i6doc.com/en/. The modified k-NN classifie –shown in Algo i hm 2– uses he ea u e weigh s o influence he dis ance calcula ion be ween wo ins ances. Ins ead o using a majo i y o ing as he o iginal k-NN does o compu e he label o he es ins ance, i uses he ins ance weigh s o gi e mo e ele an ins ances mo e influence in he o ing –line 9 in he algo i hm. By using an algo i hm ha accep s ea u e weigh s we o e come he need o finding a sui able ea u e se gi en he esul ing weigh s o he p ocess, as we did in ou p e ious pape [4]. I we wan ed o use he adi ional e sion o k-NNa hispoin ,wewould ha e o decide a size s o he selec ed ea u e se , o de he ea u es acco ding o hei weigh s and keep he fi s s, o else use a classifie o pe o m a cos ly sea ch in w appe mode. Algo i hm 2: Ins ance and Fea u e Weigh ed k-Nea es Neighbou s Inpu : T aining se D={x1,...,xN}, cons an k, ins ance weigh s ω, ea u e weigh s w, new ins ance x∗ o be classified Ou pu : Class p edic ion o x∗ 1Ini ialize all ci∈C o 0 ; // Cis he se o class labels 2 o each xn∈Ddo 3dn←xn−x∗w 4end 5So din descending o de 6Dk←nea es kins ances acco ding o d 7 o each xn∈Dkdo 8le kbe he class o xn 9ck←ck+ωn 10 end 11 e u n a g max i ci In Fig. 1 we see he numbe o p oblems (including UCI, NIPS and mic oa - ay) o which he modified e sions o he FSS algo i hm had be e /equal/wo se s abili y esul s, and he numbe o p oblems which he classifica ion e o o he esul ing ea u e se s was be e /equal/wo se. We see ha bo h modifica ions lead o mo e (o equally) s able esul s mos o he ime. In ac , SimbaMIW is only significan ly less s able han s anda d Simba in one single case ( he NIPS Madelon da ase using he ’sample’ e sion). Ve y impo an ly, p edic i e e o s a e simila o hose o mo e uns able e sions. 5 Conclusions The p esen wo k has in oduced SimbaMBIW, a new me hod o imp o ing he s abili y o ea u e subse selec ion algo i hms, which d aws upon p e ious algo i hmic wo k on ea u e weigh ing and hypo hesis ma gins o ins ances. Ou s a egy uses a double se o weigh s, one o he ea u es and ano he one o he 609 ESANN 2016 p oceedings, Eu opean Symposium on A i icial Neu al Ne wo ks, Compu a ional In elligence and Machine Lea ning. B uges (Belgium), 27-29 Ap il 2016, i6doc.com publ., ISBN 978-287587027-8. A ailable om h p://www.i6doc.com/en/. (a) S abili y (b) Classifica ion e o Fig. 1: Numbe o p oblems whe e SimbaMiw was be e /equal/wo se han s anda d Simba ega ding s abili y and classifica ion e o . ins ances. I s sui abili y has been assessed using da a om h ee diffe en en i- onmen s: mic oa ay gene exp ession da a, eal-wo ld and syn he ic da ase s. The p esen wo k offe s a numbe o in e es ing a enues o u he esea ch. We a e in e es ed in quan i ying and imp o ing p edic ion s abili y: he abili y o a classifie in labelling each ins ance cohe en ly (independen ly o i s co ec ness); he e a e also al e na i e ways o combine he weigh s: specifically, he ins ance weigh s can be upda ed a each i e a ion, gi en ha he ea u e weigh s a e e-compu ed, which would lead o a syne ge ic p ocess. Re e ences [1] L I. Kunche a. A s abili y index o ea u e selec ion. In IASTED In e na ional Con e - ence on A i icial In elligence and Applica ions, pp. 390–395, 2007. [2] Y. Saeys, T. Abeel, Y. Pee . Robus ea u e selec ion using ensemble ea u e selec ion echniques. In ECML-PKDD, pages 313–325. Sp inge -Ve lag, 2008. [3] P. Somol, J. No o iˇco ´a. E alua ing s abili y and compa ing ou pu o ea u e selec o s ha op imize ea u e subse ca dinali y. IEEE T ans. on PAMI, 32(11):1921–39, 2010. [4] G. P a , and Ll. Belanche. Imp o ed s abili y o ea u e selec ion by combining ins ance and ea u e weigh ing. In M. B ame and M. Pe idis (eds), Resea ch and De elopmen in In elligen Sys ems XXXI, pp. 35–49. Sp inge , 2014. [5] R.G. Bach ach, A, Na o , N. Tishby. Ma gin based ea u e selec ion - heo y and algo- i hms. In In l. Con . on Machine Lea ning (ICML), pages 43–50, 2004. [6] K. C amme , R.G. Bach ach, A. Na o , N. Tishby. Ma gin Analysis o he LVQ Algo- i hm. In Ad ances in NIPS 2002, pages 462–469, 2002. [7] K. Ki a, L. Rendell. The ea u e selec ion p oblem: T adi ional me hods and a new algo i hm. pp. 129–134, Camb idge, USA, 1992 [8] Y. Han, L. Yu. A Va iance Reduc ion F amewo k o S able Fea u e Selec ion. In ICDM, pp. 206–215, 2010 610 ESANN 2016 p oceedings, Eu opean Symposium on A i icial Neu al Ne wo ks, Compu a ional In elligence and Machine Lea ning. B uges (Belgium), 27-29 Ap il 2016, i6doc.com publ., ISBN 978-287587027-8. A ailable om h p://www.i6doc.com/en/.