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/.