TRABAJO FIN DE MÁSTER
Ap endizaje Supe isado median e
Random Fo es s
P esen ed by:
Ma ía C is ina Mole o del Río
Supe iso s:
DR. RAFAEL BLANQUERO BRAVO
DR. EMILIO CARRIZOSA PRIEGO
FACULTAD DE MATEMÁTICAS
Depa amen o de Es adís ica e In es igación Ope a i a
Se illa, Junio 2017
Con en s
Resumen 5
In oduc ion 7
1 Supe ised Classi ica ion 9
1.1 Sco ing unc ions............................ 9
1.2 Valida ion echniques and pe o mance c i e ia . . . . . . . . . . . . 10
1.3 Supe ised eg ession . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Classi ica ion ees 15
2.1 Ge ing amilia wi h classi ica ion ees . . . . . . . . . . . . . . . . 16
2.2 Topology and ype o spli ing . . . . . . . . . . . . . . . . . . . . . 18
2.3 Spli ingc i e ia............................. 19
2.3.1 Impu i y unc ions . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.1.1 Classi ica ion e o a e . . . . . . . . . . . . . . . 22
2.3.1.2 Giniindex...................... 22
2.3.1.3 C oss-en opy . . . . . . . . . . . . . . . . . . . . 22
2.3.2 Gain a io............................ 23
2.4 S oppingc i e ia............................. 24
2.5 Labeling e minal nodes . . . . . . . . . . . . . . . . . . . . . . . . 25
2.6 Classi ica ion ee s ep by s ep . . . . . . . . . . . . . . . . . . . . . 26
2.7 T eeP uning .............................. 31
2.8 Reg ession ees............................. 32
3 Ensembling ees: Random Fo es s 33
3.1 Random o es s. In luences and de ini ion. . . . . . . . . . . . . . . . 33
3.1.1 Backg ound........................... 33
3.1.2 De ini ion............................ 34
3.1.2.1 Pa ame e s uning . . . . . . . . . . . . . . . . . . 35
3.2 P ope ies o Random Fo es s . . . . . . . . . . . . . . . . . . . . . . 37
3.2.1 Va iable impo ance . . . . . . . . . . . . . . . . . . . . . . 37
3.2.1.1 Mean Dec ease Accu acy . . . . . . . . . . . . . . 37
3
4 Con en s
3.2.1.2 Mean Dec ease Impu i y . . . . . . . . . . . . . . 39
3.2.2 P oximi y measu e . . . . . . . . . . . . . . . . . . . . . . . 40
3.2.2.1 Da a isualiza ion . . . . . . . . . . . . . . . . . . 41
3.2.2.2 Ou lie s de ec ion . . . . . . . . . . . . . . . . . . 42
3.2.2.3 Missing alues impu a ion . . . . . . . . . . . . . . 42
3.2.2.4 P o o ypes sea ch . . . . . . . . . . . . . . . . . . 43
3.3 Reg ession Random Fo es s . . . . . . . . . . . . . . . . . . . . . . . 44
4 Random Fo es s in R 45
4.1 Random Fo es s and p ope ies . . . . . . . . . . . . . . . . . . . . . 46
4.2 Fea u e Selec ion based on Random Fo es s . . . . . . . . . . . . . . 52
Bibliog aphy 60
Resumen
Muchos p oblemas de la ida eal pueden modela se como p oblemas de clasi icación,
ales como la de ección emp ana de en e medades o la concesión de c édi o a un
cie o indi iduo. La Clasi icación Supe isada [9] se enca ga de es e ipo de p oble-
mas: ap ende de una mues a con el obje i o inal de in e i obse aciones u u as.
Hoy en día, exis e una amplia gama de écnicas de Clasi icación Supe isada. En es e
abajo nos cen amos en los bosques alea o ios (Random Fo es s, [4]).
El Random Fo es s es una écnica de clasi icación que consis e en cons ui una
colección de á boles de decisión indi iduales [8] sob e los cuales se aplica alea o iedad
de cie a mane a. Es conocido que es a écnica p opo ciona un buen endimien o, in-
cluso cuando a a con p oblemas de g an escala como los que se ienen en la ac u-
alidad. Sin emba go, exis e una pequeña b echa en e la eo ía elacionada con es a
écnica y la expe iencia empí ica de la misma. El Random Fo es s ambién es ú il en
o os campos del Ap endizaje Au omá ico: da medidas de impo ancia de las a iables,
que pod ían u iliza se en la Selección de A ibu os, y una ma iz de p oximidades en-
e las obse aciones, lo que pe mi e al analis a de ec a alo es a ípicos, eemplaza
alo es pe didos, busca p o o ipos y ob ene una isualización comp ensible de los
da os. Es as úl imas p opiedades hacen que el Random Fo es s sea una écnica aún
más a ac i a.
En es e abajo se hace, en p ime luga , una b e e desc ipción de la Clasi icación
Supe isada, incluyendo las p incipales écnicas de alidación y los c i e ios de endimien o
más ele an es. En segundo luga , se explica en de alle la cons ucción de un á -
bol de clasi icación. Seguidamen e, se p esen a el Random Fo es s y se e isan las
p opiedades p incipales del mismo. Po úl imo, se mues an esul ados expe imen ales
en R.
5

In oduc ion
Many p oblems in he eal li e can be modelled as classi ica ion p oblems: he ea ly
de ec ion o diseases o he g an ing o c edi o a ce ain indi idual, among o he s.
Supe ised Classi ica ion [9] handles his issue by lea ning om a sample in o de
o in e o hcoming obse a ions. Nowadays, he e exis a wide ange o Supe ised
Classi ica ion echniques. Along his wo k, we will ocus on Random Fo es s classi i-
ca ion me hod [4].
Random o es s is a collec ion o indi idual decision ees [8] on which andom-
ness is applied somehow. This classi ica ion echnique is well-known o p o iding
g ea pe o mance, e en wi h la ge-scale p oblems. Ne e heless, he e is a li le gap
be ween heo y and empi ical expe ience in his scheme. Random Fo es s a e also use-
ul o o he ields in Machine Lea ning: hey gi e measu es o a iables impo ance,
which could be used in Fea u e Selec ion, and p oximi ies be ween obse a ions, which
allows he analys o de ec ou lie s, eplace missing alues, sea ch p o o ypes and ob-
ain a comp ehensi e isualiza ion o he da a. These la e p ope ies make Random
Fo es s e en mo e a ac i e.
This wo k is o ganised as ollows. Chap e 1 in oduces o he Supe ised Clas-
si ica ion, including he mos ele an alida ion echniques and pe o mace c i e ia.
Nex , in Chap e 2, he cons uc ion o a classi ica ion decision ee is add essed in
de ail. Then, Chap e 3 is en e ely de o ed o Random Fo es s. The main p ope ies
o Random Fo es s a e e iewed. Las , in Chap e 4, compu a ional expe ience wi h
Random Fo es s is epo ed. The code in Rso wa e is also displayed.
7
Chap e 1
Supe ised Classi ica ion
Supe ised Lea ning is one o he mos ele an asks in Machine Lea ning and Da a
Mining. The gene al idea in Supe ised Lea ning is o in e a unc ion which is known
only o some examples, wi h he inal goal o mapping new o hcoming examples.
Depending on he ange o he in e ed unc ion, one can dis inguish be ween Supe -
ised Classi ica ion and Supe ised Reg ession. Along his ex we will mainly ocus
on Supe ised Classi ica ion and b ie ly su ey he eg ession case.
The aim o Supe ised Classi ica ion is o seek p ocedu es o classi ying objec s
in a se Ωin o a ini e se Co nominal alues o classes. Each objec uin Ωhas
associa ed a pai (xu, yu), whe e xu, he p edic o ec o , akes alues on a se X,
usually assumed o be a subse o Rp, and yu∈Cis he class membe ship o he objec .
Hence o ce, each componen o he p edic o ec o and ywill be named p edic o and
esponse a iables, espec i ely.
The whole in o ma ion abou all he objec s in Ωis no a ailable as a ule. Ins ead,
we assume we a e gi en a sample Dn={(x1, y1),...,(xn, yn)}o independen an-
dom a iables dis ibu ed as he independen p o o ype pai (X, C). The goal is o use
he da a se Dn o cons uc a classi ie , i.e., an es ima e mn:X−→ Co he unc ion
m(x), which gi es o each x he class minimizing he misclassi ica ion cos .
1.1 Sco ing unc ions
Ac ually, classi ie s a e based on sco ing unc ions c:X→Rbuil o each class
c∈C. These unc ions a e in cha ge o anking a o hcoming objec : hey indica e,
in a ce ain sense, he likelihood ha an objec ep esen ed by xbelongs o each class.
In his way, he classi ie will be gi en by he unc ion
mn(x)∈a g max
c∈C c(x)∀x∈X. (1.1)
These sco ing unc ions ha e a pa icula p ope y: i e e y cis eplaced by c+h
o a common h, he same classi ie mnis ob ained. This p ope y is in e es ing in
9
16 2.1. Ge ing amilia wi h classi ica ion ees
ee-based decision making a he same le el as o he powe ul echniques.
In he emainde o his chap e , he goal is o p o ide an unde s andable desc ip-
ion o he cons uc ion o a classi ica ion ee, wi h main ocus on he CART model.
Finally, we will sligh ly mo e on o eg ession ees.
2.1 Ge ing amilia wi h classi ica ion ees
P io o o mally ackling he cons uc ion o a classi ica ion ee, some gene al no ions
will be p o ided o eade s. The main elemen s o a ee a e p esen ed oo. Figu e
2.1 depic s an example o a diag am ee o a hypo he ical wo-class classi ica ion
p oblem, C={Posi i e,Nega i e}.
Figu e 2.1: A diag am ee.
As i can be seen in Figu e 2.1, a classi ica ion ee is a classi ie ha in ol es
he pa i ioning o Ω, ca ied ou by consecu i e and descendan di isions o disjoin
subse s o Ω. Fo ins ance, 21 and 22 a e disjoin and add up he o al p e ious subse ,
13 = 21 22.
Subse s a e known as nodes. The oo node is he one ha appea s he highes ,
ep esen ing Ωi sel . Non-spli subse s, indica ed by ec angula boxes, a e called

Chap e 2. Classi ica ion ees 17
e minal nodes and hey o m a pa i ion o Ω,
Ω = 11 31 32 33 21 22.
The es o nodes a e non- e minal nodes.
A class label o Cis assigned o each e minal node in such a way ha he e may be
mo e han one e minal node wi h he same class label. The way o do his assignmen
is ye o be de ined.
Besides nodes, b anches a e ano he elemen o a ee. They indica e he di e en
decision op ions ha can be aken in each spli . Spli s a e due o condi ions on he
a iables in x= (x1, . . . , xp). Fo example, Spli 2 in o 21 and 22 could be o he
o m 21 ={x∈ 13 :x2+x4≤3}
22 ={x∈ 13 :x2+x4>3}(2.1)
o Spli 3 in o 31, 32 and 33:
31 ={x∈ 12 :x5=Blue}
32 ={x∈ 12 :x5=Pink}
33 ={x∈ 12 :x5=G ey}.
In o de o p edic he class o a gi en objec making use o he classi ica ion ee in
he Figu e 2.1, he p ocedu e is o s a by he i s spli and ake he b anch con aining
he condi ion sa is ied by he objec . In his way, he objec ge s o ano he node om
wi h he same p ocedu e is o be done and epea ed un il a e minal node is eached.
The p edic ed class o he objec will be gi en by he class label a ached o ha e -
minal node.
Acco ding o his b ie in oduc ion o classi ica ion ees, i ollows ha he g ow h
o a ee depends on ou basic ing edien s:
•Topology o he ee and ype o spli ings. Fi s o all, he opology o he ee
is o be chosen, ha is, he numbe o b anches allowed in spli s. In mos cases,
ees a e assumed o be bina y. The kind o condi ions on spli ing ha e o be
decided oo.
•Spli ing c i e ion. A each non- e minal node, no any spli wo ks. I is neces-
sa y o de ine a spli ing c i e ion om which he selec ed spli makes p edic ion
accu acy imp o es among he es .
•S opping c i e ion. Deciding when o con inue spli ing o decla e a node e -
minal is ano he ask ha should be aken in o accoun .
•Classes assignmen . Finally, once he e minal nodes ha e been loca ed, he las
s ep is o assign a class label o each one o hese nodes.
The essence o he p oblem is, he e o e, how o add ess hese issues o ob ain an
accu a e classi ie . This will be discussed in he nex sec ions.
18 2.2. Topology and ype o spli ing
2.2 Topology and ype o spli ing
The opology o shape o a decision ee comp ises, as ad anced be o e, he de e mi-
na ion o how many di e en b anches o op ions he e a e when a spli is ca ied ou
o c ea e new nodes. The e exis bina y spli ing and mul i-spli ing.
Le us add ess sepa a ely he cases in ag eemen wi h he ype o a iable unde
conside a ion. Recall ha wo king wi h bo h, ca ego ical and con inuous a iables, is
easible in his amewo k. Le us s a wi h ca ego ical a iables.
Suppose we depa om a node . Le xm,1≤m≤p, be a ca ego ical a iable,
aking alues, say, in {b1, . . . , bQ}. Fo bina y spli ing, wo al e na i es a e equen ly
conside ed. Fo i= 1, . . . , Q he i s al e na i e is o conside only as possible spli s
he ollowing subse s:
L={u∈ :xu
m=bi}
R={u∈ :xu
m6=bi},
deno ing Land R he le and igh new subse s. Qpossible spli s a e done in his
way. The second al e na i e is o conside e e y possible subse o {b1, . . . , bQ}, ha
is,
L={u∈ :xu
m∈S}
R={u∈ :xu
m6∈ S},
whe e S anges o e all subse s o {b1, . . . , bQ}. In his case, since Land Rgene a e
he same subse s wi h Land R e e sed, 2Q−1−1spli s a e necessa y.
Fo mul i-spli ing, a new b anch pe each i,1≤i≤Q, is c ea ed, subdi iding he
cu en node in o
i={u∈ :xu
m=bi}.(2.2)
Le xm,1≤m≤p, be con inuous now, so we ha e om Dnn eal alues o
xm. Assuming ha hese alues a e in o de om lowes o highes , a mos n−1
di e en di isions can be done o bina y spli ing a mos , by sepa a ing he l i s
objec s, al eady o de ed up o xm, and he emaining n−l, wi h l= 1, . . . , n −1, i.e.:
L={u∈ :xu
m≤cl}
R={u∈ :xu
m> cl}(2.3)
whe e he cu poin clis he hal way be ween consecu i e da a alues o xm. Howe e ,
no e e y di isions mus be conside ed; hose spli s in which he e is no a change o
class a e domina ed by he o he s. Anyway, he bigge is n, he bigge is he numbe
o po en ial cu o s o be aken in o conside a ion, which is ime-consuming. In o de
o educe he compu a ional bu den, con inuous a iables can be disc e ized in a p e-
ious s ep. Mul i-spli ing in con inuous a iables is no o in e es because i has been
p o ed ha he e is no any ad an age in p edic ion accu acy o e bina y spli ing, [27].
Chap e 2. Classi ica ion ees 19
The p ocess explained abo e is ac ually applied o uni a ia e spli s, ha is, spli s
de ined by one single p edic o a iable. Ne e heless, his conside a ion can be ex-
ended o mul i a ia e spli s, spli s in which se e al p edic o a iables ake pa , see
(2.1). This ex ension seems o be plausible in e ms o accu acy. Linea spli s a e
he mos popula mul i a ia e spli s. Aside om heu is ic algo i hms, hey can be pe -
o med by using Linea Disc iminan Analisis o he linea SVM, o name a couple o
hem.
The simples opology o a decision ee is when ea ing wi h uni a ia e spli s and
bina y spli ings. This me hod is known as ecu si e bina y spli ing.
2.3 Spli ing c i e ia
The p oblem o building an op imal bina y ee is NP-comple e. Due o he complexi y
o his elemen a y ee, all ees a e cons uc ed by a g eedy p ocedu e: a each non-
e minal node, all possible spli s a e gene a ed and he bes o hem a he cu en
s ep, acco ding o a spli ing c i e ion, is selec ed. Howe e , his elec ion could no
be op imal o u u e s eps. In his sec ion, he spli ing c i e ion pa excellence is
desc ibed.
Assuming ha he se So possible spli s is al eady compu ed o a pa icula
non- e minal node, he issue is o decide which o hem is he bes op ion in o de o
imp o e he classi ie accu acy.
Fi s o all, some de ini ions and no a ions a e needed. Remind he gene al ame-
wo k: we a e gi ing a sample Dn={(x1, y1),...,(xn, yn)}wi h xi∈Xand
yi∈C={C1, . . . , Ck},1≤i≤n. Deno e nj he numbe o obse a ions in Dn
ha belong o he same class Cj, o 1≤j≤k. P io class p obabili ies πjcan be
hen es ima ed om he sample as ollows
πj=nj
n.
Gi en a node , le nj( )be he numbe o obse a ions in ha belong o he same
class Cj,1≤j≤k, and n( ) he o al numbe s o obse a ions ha ha e allen in o
node ; he p opo ion o examples belonging o Cj ixed an a bi a y node is gi en
by
πj( ) = nj( )
n( ).(2.4)
Then, an es ima ion o he p obabili y ha an example eaches he node and belongs
o class jcan be deduced:
P(Cj, ) = πjπj( ).
On ano he hand, he ma ginal p obabili y ha an obse a ion eaches he node is
20 2.3. Spli ing c i e ia
gi en by
P( ) =
k
X
j=1
P(Cj, ).
The p obabili y ha an obse a ion belongs o class jgi en ha i alls in o node is
de ined by
P(Cj| ) = P(Cj, )
P( ).
When πja e es ima ed using (2.4), one has
P(Cj| ) = nj( )
n( ),
so hese p obabili ies a e he ela i e p opo ions o class jin node .
The abo e de ini ions will help us o unde s and he spli ing c i e ia. The way pa
excellence o selec he bes spli , acco ding o he ypes in oduced in Sec ion 2.2,
is o choose he spli ha bes sepa a e he objec s in he aining sample up o hei
classes, ha is, ha p oduces he maximum educ ion in he di e si y o impu i y o
objec s associa ed o esul an nodes. To be e see his idea, imagine a ou -classes
bina y ee. The p opo ions o he classes in he ini ial node a e equal, i.e., P(j| 0=
Ω) = 1/4∀j= 1,...,4. A good spli ing c i e ion would be o ake he spli ha
leads o wo new descendan nodes in which he e a e only he hal o he classes, as
shown in Figu e 2.2. A quan i a i e measu e o he e ec i eness o a spli in his sense
Figu e 2.2: Fi s spli o a ou -classes bina y ee. The equencies o classes ha all
in o each node appea nex .
is ob ained by he concep o impu i y.
Chap e 2. Classi ica ion ees 21
De ini ion 2.3.1 (Impu i y unc ion).Le Φ : P−→ Rwhe e
P=((p1, . . . , pm) :
m
X
j=1
pj= 1, pj≥0, j = 1, . . . , m).
Φis an impu i y unc ion i i e i ies
(1) Φ eaches i s unique maximum a he poin (1
m,..., 1
m).
(2) Φachie es i s minima exclusi ely a he poin s (1,0,...,0),(0,1,0,...,0),. . . ,
(0,...,0,1).
(3) Φis a symme ic unc ion o p1, . . . , pm, i.e., i he e is a pe mu a ion o he
a iables pj,Φwill emain cons an .
De ini ion 2.3.2 (Impu i y measu e).Le Φbe an impu i y unc ion. An impu i y mea-
su e i( )o any node is de ined as
i( ) = Φ (P(C1| ), . . . , P(Ck| )) ,
whe e P(Cj| )is he es ima ed p obabili y o class jwi hin node .
In his way, he impu i y measu e will achie e i s maximum when e e y classes in
node a e in he same p opo ion, and i s minimum when he e is only one class in
node .
Since he undamen al idea is o p oduce pu e nodes, he selec ion o he spli o a
pa en node will be done in e ms o a new concep : he in o ma ion gain, which mea-
su es somehow he pu i y gained when a node is spli in o descendan nodes acco ding
o a ype o spli ing. In wha ollows, his concep is o mally de ined.
De ini ion 2.3.3 (In o ma ion gain).Le s∈Sbe a possible spli , le be he numbe
o b anches conside ed in he g ow h o he ee and le ibe an impu i y unc ion. The
in o ma ion gain o s ela i e o node is de ined as he a e age educ ion o impu i y
ob ained by spli ing he obse a ions wi hin node up o s
G( , s) = i( )−
X
j=1
qji( j),(2.5)
whe e jis each descendan node o igina ed in he spli ing and qj he p opo ion o
obse a ions (wi hin node ) ha become elemen s om new node j.
By i ue o he abo e de ini ion, he selec ed spli o e he cu en se o nodes Ωc
will be he one ha maximizes he co esponding in o ma ion gain:
G( ∗, s∗) = max
∈Ωc,s∈S{G( , s)}.(2.6)

22 2.3. Spli ing c i e ia
I is no ha d o see om (2.5) ha maximizing he in o ma ion gain when he e is one
single node is equi alen o minimizing he e m ha is subs ac ed in he o mula,
i.e., minimizing he weigh ed a e age impu i y o he possible new descendan nodes
o .
The e o e, once an impu i y unc ion is chosen, he selec ion c i e ion is pe ec ly
de ined.
2.3.1 Impu i y unc ions
Common impu i y unc ions a e in oduced now, ha is, unc ions ha p esen he
desi able p ope ies lis ed in De ini ion 2.3.1. They a e: he classi ica ion e o a e o
misclassi ica ion a e, he Gini index and he c oss-en opy.
2.3.1.1 Classi ica ion e o a e
Gi en he ec o (p1, . . . , pm)∈P, he classi ica ion e o a e (CER) is de ined as
Φ(p1, . . . , pm) = 1 −max
1≤j≤m{pj}.
In he ield o decision ees, he elemen s pja e assumed o be P(Cj| )acco ding o
De ini ion 2.3.2, hus, CER would be he ac ion o obse a ions in node ha do no
belong o he mos common class. I seems ha CER has he de iciency o no being
sensi i e enough o he o e all ee-g owing p ocedu e. Fo u he de ails, he eade
is e e ed o [8]. The ollowing impu i y unc ions a e p e e able ins ead.
2.3.1.2 Gini index
Gi en he ec o (p1, . . . , pm)∈P, he Gini index is de ined as
Φ(p1, . . . , pm) =
m
X
j=1
pj(1 −pj)=1−
m
X
j=1
p2
j.
When pj=P(Cj| ), he Gini index measu es he o al a iance ac oss all he kclasses.
By he way his index is de ined, i akes smalle alues i e e y pjin node is close
o ze o o one. In his sense, node impu i y is pe ec ly measu ed: a small alue will
indica e ha he node is domina ed by a single class.
2.3.1.3 C oss-en opy
Gi en he ec o (p1, . . . , pm)∈P, he c oss-en opy is de ined as
Φ(p1, . . . , pm) = −
m
X
j=1
pjlog2(pj)
Chap e 2. Classi ica ion ees 23
Figu e 2.3: Impu i y unc ions o wo classes.
wi h he ag eemen 0 log20=0. The nega i e sign is due o he p0
js: in his ield, hey
ep esen p obabili ies and i ollows ha log pj<0when 0≤pj≤1.
The in e p e a ion wi h pj=P(Cj| )is qui e simila o he Gini index: i a node
is pu e, he c oss-en opy will ake a small alue. In ac , he Gini index and he c oss-
en opy a e usually alike nume ically.
Ac ually, he concep o en opy was i s in oduced in In o ma ion Theo y. In his
way, i can be seen as he minimum numbe o in o ma ion bi s needed o encode he
classi ica ion o any objec in a pa icula node. Fo ins ance, Φ (1,0,...,0) = 0 since
he gi en objec belongs o C1undoub edly, wi h no need o any message o any bi
o ansmi i s in o ma ion.
In Figu e 2.3, hese h ee impu i y unc ions a e shown o a wo-class p oblem.
2.3.2 Gain a io
In he case o non-bina y ees, he in o ma ion gain is a measu e ha gi es ad an age
o hose a iables ha ha e a lo o ca ego ies when deciding he spli ing. To deal
wi h his p oblem, al e na i e measu es o he selec ion o he spli ing a iable ha e
been p oposed. One o hem is he gain a io, which penalizes a iables wi h many
ca ego ies by means o he in o ma ion alue.
24 2.4. S opping c i e ia
De ini ion 2.3.4 (In o ma ion alue).Le Abe a a iable wi h possible ca ego ies.
Le mj( )be he numbe o examples o ca ego y j ha all in o node . Then, he
in o ma ion alue I (A, )o Ain o is de ined as
IV (A, ) = −
X
j=1
mj( )
n( )log mj( )
n( ).(2.7)
The in o ma ion gain is no hing mo e han he c oss-en opy de ined abo e bu ,
ins ead o conside ing he ou pu s o he classi ica ion, he ca ego ies o a iable Aa e
now ad essed. F om he in o ma ion gain, he gain a e is de ined.
De ini ion 2.3.5 (Gain a e).Le be a node and Aa pa icula a iable. The gain
a e o Ain node is:
GR (A, ) = G(A, )
IV (A, )(2.8)
whe e Gand IV e e o he in o ma ion gain and a iable, espec i ely.
The gain a e p esen s an issue: i s denomina o can be nea ze o i mj( )and
n( )a e close o each o he o some ca ego y. A heu is ic ule can be adop ed: i s ,
he in o ma ion gain is compu ed o each a iable candida e o he spli ing and hen,
making use o he same selec ion ule based on he gain a e (2.6), he spli ing is
chosen. The only di e ence is ha only hose a iables whose gain is abo e a e age
will be conside ed.
2.4 S opping c i e ia
In he p e ious sec ion, he me hodology o e alua ing he quali y o a pa icula spli
has been analyzed. The ollowing s ep is o decide when o decla e a node e minal.
The p ocess o g owing a ee could con inue un il e e y node con ains one single
obse a ion. In his way, he e will be one e minal node pe obse a ion in he gi en
sample, so each one will be labelled wi h he class o i s co esponding obse a ion.
This p oposal can p esen se ious de iciencies in p ac ice, ending up in he g ea p ob-
lem o Machine Lea ning: he o e i ing. The o e i ing is he e ec o ge ing any
lea ning algo i hm ha has lea ned oo much om he aining sample and is no able
o gene alize and p edic new examples, see Figu e 2.4. Se e al c i e ia ha help o
a oid o e i ing a e usually aken.
A i s c i e ion is no o spli a node i he maximum in o ma ion gain ha one
would ob ain by making he spli is lowe han some p e-se h eshold β:
max
s∈SG(s, )≤β.
Al hough his ule seems o be qui e easonable, i may no p o ide sa is ac o y ou -
comes: i βis oo small, he esul ing ee may be oo complex and o e i he aining
Chap e 2. Classi ica ion ees 25
Figu e 2.4: O e i ing.
da a; i βinc eases, i akes chances o s opping spli ing nodes wi h low maximum
in o ma ion gain, bu whose descendan nodes would do su e spli s wi h a high max-
imum in o ma ion gain.
Ano he ule ha is also used is he one based on s opping he subdi ision o a node
i i does no p esen a minimum numbe o aining examples. 1, 5 o 10 a e ypical
alues.
Finally, a c i e ion based on s a is ic es s exis s and i is due o [25]. The idea is o
con inue spli ing un il he class dis ibu ion o he a ailable obse a ions is indepen-
den o he a iables in he p edic o ec o . Fo ca ego ical a iables, one can use he
χ2 es ; o con inuous ones, he F−S uden es .
Ac ually, an al e na i e o hese ules is done in p ac ice. Ins ead o s opping he
g ow h o he ee, a e y la ge ee is buil and p ope ly p uned la e so ha he
b anches ha explain wo se a e elimina ed. This p ocess o p uning a ee is de el-
oped in Sec ion 2.7.
2.5 Labeling e minal nodes
Once e minal nodes a e decla ed by means o a s opping c i e ion, he class labels
assignmen is s ill le . Recall om Sec ion 2.1 ha he se o e minal nodes Tinduces
a pa i ion o Ω. Le ∈Tbe a e minal node. The assignmen ule is
A:T→C
7→ a g max
Cj
nj( ),(2.9)
32 2.8. Reg ession ees
whe e Φusually deno es he ac ion o cases in he aining sample ha a e misclassi-
ied, bu any impu i y unc ion can be used. R(T)is called he esubs i u ion e o o
T. So, gi en a eal numbe α, he o al cos Rα(T)o ee T is de ined as
Rα(T) = R(T) + α|T|.(2.10)
The pa ame e αis he penal y imposed o e he complexi y (size) o he ee; while
small alues o αwill o igina e ees wi h a huge numbe o e minal nodes, big alues
o αwill o igina e ees wi h ew e minal nodes. The basic idea gi en in [8] is o
selec a sub ee T(α), wi h he same oo node ha Tmax, ha minimizes (2.10).
2.8 Reg ession ees
Fo eg ession ees, he cons uc ion is qui e simila . In ac , Sec ions 2.2 and 2.4 can
be applied o he eg ession case wi hou change. Rega ding spli ing c i e ia, he spli
is selec ed by minimizing he Residual Sum o Squa es (RSS). The esidual o each
obse a ion is compu ed as he di e ence o i s alue in he esponse a iable and he
mean alue o all obse a ions in he same node. By las , as expec ed, he p edic ion
o alue associa ed o each e minal node is usually he mean o he esponse a iable
in e e y aining objec ha has allen in o he same e minal node.

Chap e 3
Ensembling ees: Random Fo es s
Random o es s (RFs) a e a s a e o he a p edic ion me hod. RFs a e known o
usually p o iding g ea p edic ions and being lexible enough o deal wi h la ge-scale
p oblems, e en in se ings whe e he numbe o a iables is much la ge han he num-
be o obse a ions. Despi e being widely used, RFs’ pe o mance is no suppo ed by
many heo e ical esul s. The e is, he e o e, a li le gap be ween heo y and empi ical
expe ience in his scheme. E en so, along his chap e , he mos celeb a ed heo e ical
esul s o RFs will be ske ched ou .
A andom o es is a collec ion o indi idual decision ees, e iewed in Chap e
2, each o which is cons uc ed by applying andomness wice: i s , a aining sample
is selec ed andomly o each ee and, secondly, andomness is injec ed somehow in
he spli selec ion p ocess. The e m andom o es is a ibu ed o B eiman, who i s
in oduced i in [4].
RFs inhe i he p ope ies om decision ees, which we e named in he in oduc-
ion o Chap e 2: hey gi e measu es o a iables impo ance and p oximi ies be ween
obse a ions, mainly. The ex ension o hese p ope ies o RFs usually makes he con-
clusions mo e eliable since a collec ion o di e en p edic o s a e now aken in o
accoun . In addi ion o o he s, hese p ope ies a e ully discussed a e wa ds.
3.1 Random o es s. In luences and de ini ion.
3.1.1 Backg ound
Fi s o all, he oad o RFs is in oduced o he eade in his i s sec ion.
Decision ees, discussed in Chap e 2, a e known o su e om high a iance.
This means ha i wo decision ees a e g own o e wo disjoin subsamples om he
aining da a, hey may lead o qui e di e en esul s. A gene al p ocedu e o educing
a iance o any lea ning me hod is bagging [3], which has al eady been p esen ed in
Chap e 1. The idea o bagging gi en in Chap e 1 was o gi e a echnique o handling
33
34 3.1. Random o es s. In luences and de ini ion.
small da ase s. In his con ex , using bagged ees is based on he s a is ical esul
ou lined in No e 3.1.1.
No e 3.1.1. Gi en Bindependen obse a ions, each wi h a iance σ2, he a iance o
he mean o hese obse a ions is educed o σ2/B.
So, conside ing a collec ion o decision ees is ansla ed in o a educ ion o a i-
ance, which di ec ly leads o an inc ease o p edic ion accu acy. The andom subspace
me hod was also p oposed o cons uc ing decision o es s [21]. This me hod aims
o educe co ela ion be ween ees by andomizing he p edic o a iables o use in
each indi idual ee. The nex s op o RFs is andom spli selec ion [16], which uses
bagging wi h he only di e ence ha a each node, among he kbes po en ial spli s,
he inal spli is chosen in a andom way. B eiman emphasizes ha he key pape , he
one ha was eally decisi e o de elop andom o es s, was [1], in which a andom
selec ion o ea u es a each spli is done o a pa icula p oblem. And his is how he
Random Fo es s g ew up [4].
3.1.2 De ini ion
Random o es s sha e common cha ac e is ics wi h bagging: Bdecision ees a e
g own o e Bboo s apped aining samples and he p edic ion is he class wi h ma-
jo i y o e oo; bu , a each ime a spli is conside ed, a andom sample o mp edic o
a iables is chosen andomly among he pini ial p edic o a iables. Remembe om
Chap e 1 ha he obse a ions no appea ing in he boo s ap sample a e called OOB
obse a ions. A i s sigh , his andomiza ion o bagged ees seems no o make sense
bu i helps o “deco ela e” ees. In o de o unde s and how i deco ela es ees we
will use he explana ion gi en in [24], which is qui e simple. Conside a da ase ha
con ains a e y s ong p edic o a iable oge he wi h o he mode a ely s ong p edic-
o a iables. Then, al hough he numbe o decision ees is la ge, mos o hem will
loca e he s ong p edic o a iable in he op spli . In consequence, e e y decision ee
will look qui e simila o each o he , and p edic ions in all he ees will be highly co -
ela ed. This ac would imply ha he educ ion in a iance will no be as impo an
as expec ed.
De ini ion 3.1.1 (Random o es s’ p edic ion).Le {mn(X, θb)}1≤b≤Bbe a amily o
Bindi idual decision ees, buil as in Algo i hm 2. Gi en an unlabeled obse a ion
x, i s p edic ed class using RFs is
mn(x, θ1, . . . , θB) = a g max
Cj
B
X
b=1
I{mn(x,θb)=Cj},
whe e I(·)is he indica o unc ion.
Chap e 3. Ensembling ees: Random Fo es s 35
Algo i hm 2: RF’s cons uc ion.
Inpu : inpu s in Algo i hm 1, he numbe o ees Band he numbe o
p edic o a iables o selec andomly a each spli p.
o b∈ {1, . . . , B}do
Gene a e a boo s ap sample o Dn,Dn(θb).
S o e he OOB obse a ions in Dn(θb).
Cons uc an indi idual decision ee acco ding o Algo i hm 1 o e Dn(θb).
Compu e he boo s ap e o o he ee, i.e.,
eboo (b) = P(x,y)∈Dn(θb)I{mn(x;θb)6=y}
|Dn(θb)|.
end
Ob ain he boo s ap e o by a e aging o e all he ees, i.e.,
eboo =1
B
B
X
b=1
eboo (b).
Ou pu : The collec ion o indi idual decision ees o RFs,
{mn(X, θb)}1≤b≤B, and he boo s ap e o , eboo .
3.1.2.1 Pa ame e s uning
Resea ch in pa ame e s uning is sca ce in RFs. A icle [15] handles hese issues.
The i s pa ame e is he size o he o es , ha is, he numbe Bo indi idual
decision ees o be g own. B eiman [4] in oduces an in e es ing esul o B: RFs do
no o e i as la ge Bis, bu yield a limi ing alue o he gene aliza ion e o . Theo em
3.1.1 picks up his esul . Two p e ious de ini ions a e needed.
De ini ion 3.1.2 (Ma gin unc ion).Le {mn(X, θb)}1≤b≤Bbe a amily o Bindi idual
decision ees. The ma gin unc ion mg(·)is de ined as
mg(X, Y ) = 1
B
B
X
b=1
I{mn(X,θb)=Y}!−max
j6=Y 1
B
B
X
b=1
I{mn(X,θb)6=j}!
whe e I(·)is he indica o unc ion.
Acco ding o De ini ion 3.1.2, he ma gin unc ion measu es how much (in e-
quency) objec s co ec ly classi ied exceed objec s misclassi ied in any o he class.
Thus, he la ge his ma gin unc ion is, he mo e con idence in he p edic ion.
36 3.1. Random o es s. In luences and de ini ion.
De ini ion 3.1.3 (Gene aliza ion e o ).The gene aliza ion e o o a andom o es is
de ined as he p obabili y ha he ma gin unc ion is nega i e, i.e.:
PE∗=P(X,Y )[mg(X, Y )<0] .
Theo em 3.1.1. The gene aliza ion e o PE∗con e ges almos su ely o
P(X,Y )Pθ(mn(X, θ) = Y)−max
j6=Y(mn(X, θ) = j)<0.
The p oo o Theo em 3.1.1 ollows di ec ly om he S ong Law o La ge Num-
be s and i can be ound in [4]. Ac ually, his esul can be ex ended o any ensemble o
classi ie s. One consequence o Theo em 3.1.1 is ha one does no equi e o compu e
a e y la ge numbe o decision ees, since, om a alue B∗on, he p edic i e powe
o he model will s ay he same. In his con ex , La inne el al. p opose in [28] an ap-
p oach o de e mining a p io i he numbe Bin o de o ob ain an accu acy simila o
he one ob ained wi h a la ge B. This app oach is based on a non-pa ame ic es , he
McNema es [29]. Gi en wo andom o es s RFmand RFno size mand n, espec-
i ely, he McNema es compa es he numbe o examples misclassi ied by RFmbu
no by RFn(labeled Mmn) and he numbe o examples misclassi ied by RFnbu no
by RFm(labeled Mnm), i.e., in o mally, he es is
H0:The e is no di e ence be ween RF0
nand RF0
mp edic ions.
The e a e h ee possible answe s when compu ing he McNema es : o ejec H0wi h
Mmn > Mnm, in his case he conclusion is ha combining ndecision ees yields
a signi ican imp o emen in pe o mance han combining mdecision ees, and he
p ocedu e should ca y on wi h a Bla ge han m; o ejec H0wi h Mnm > Mmn,
he e he p ocedu e mus s op and use B=m; o no o ha e signi ican e idence o
ejec ing H0, which means ha he e is no signi ican di e ence be ween g owing n
o mdecicion ees, so he inal decision mus be o cons uc he minimum classi ie s
as possible: B=m. Expe imen al esul s in [28] show ha Bcan be limi ed signi -
ican ly. Ne e heless, au ho s in gene al, included [15], belie e ha he pa ame e B
is i ele an and op no o une i , as long as hey ake i la ge enough o ge ing he
s abili y (B eiman [6] p oposes B= 1000 o B= 5000) bu o compu a ions o be
comple ed wi hin a easonable ime.
The second pa ame e is m, he numbe o p edic o a iables aking pa in each
spli . B eiman in [5] ound m=d√pe o be a good choice since he ob ained gene ally
nea op imum esul s. His ad ice is o g ow h ee andom o es s wi h m=d√pe,
m= 2d√peand m=1
2d√pe, espec i ely, and obse e he one ha pe o ms he bes
and mo e a ound ha alue. B eiman also poin s ou ha a highe mwo ks be e
when noise p edic o a iables a e p esen . In [15], hey conclude, again, ha uning
his pa ame e is no an in e es ing ask.
Chap e 3. Ensembling ees: Random Fo es s 37
Aside om choosing Band m, he elemen s o each ee ha e o be decided, ha
is, he opology o he ees, he ypes o spli ing, he spli ing c i e ion, he s opping
c i e ion and i hey a e p uned ees o no . So a , he p oposed RFs’ a e collec ions o
unp uned ees. The elemen s named a e he ones ha di e en ia e be ween ees. Fo
ins ance, B eiman’s o iginal o es uses CARTs: unp uned ees wi h uni a ia e spli s,
bina y spli ing, he in o ma ion gain as a spli ing c i e ion and he nodesize c i e ion.
In he Rpackage andomFo es ,1is se as a de aul alue o nodesize, and 5
o eg ession. These alues a e epo ed o be a good choice in [15].
3.2 P ope ies o Random Fo es s
Du ing he cons uc ion o he indi idual ees he OOB obse a ions can be used o
measu e he pe o mance o he o es wi hou eque ing an independen alida ion se
(as we could app ecia e in Algo i hm 2), as well as ob aining some in o ma ion abou
he da a. Also, he ou pu o he indi idual ees gi e us some in e es ing in o ma ion.
He ea e , he main p ope ies o RFs a e being e iewed.
3.2.1 Va iable impo ance
RFs p o ide a iable impo ance measu es, making hem e y in e es ing since a hi-
e a chy o he p edic o a iables can be ob ained om he model, ha is, i can be
measu ed how ela ed each p edic o a iable is o he esponse a iable. Mo eo e ,
hese measu es help wi h ano he appealing ask in Machine Lea ning: Fea u e Selec-
ion. Fea u e Selec ion is he p ocess o disca ding i ele an o edundan p edic o
a iables, wi hou losing powe in p edic ion. In his way, he obus ness o he classi-
ie may be imp o ed and compu ing ime will be educed.
Two embedded me hods o measu ing a iable impo ance a e desc ibed: he
Mean Dec ease Accu acy (MDA, [4]) and he Mean Dec ease Impu i y (MDI, [5]).
They a e called embedded because hey a e speci ic o RFs and a e compu ed du ing
he aining p ocess.
No e 3.2.1. B eiman [5] p oposed o g ow mo e han he usual numbe o ees i one
sea ches o some auxilia y in o ma ion like a iable impo ance measu es o p oximi-
ies (which will be seen la e ), o make hese measu es s able. In [15], B eiman’s hesis
is suppo ed expe imen ally: as Bg ows, he a iable impo ance measu es s a o
be s able.
3.2.1.1 Mean Dec ease Accu acy
The Mean Dec ease Accu acy (MDA, [4]), also known as he pe mu a ion impo ance
measu e, is one o he mos common a iable impo ance measu es. MDA is based
on he ollowing p inciple: i a a iable is no in luen ial in he model, ea anging he

38 3.2. P ope ies o Random Fo es s
alues i akes should no deg ade p edic ion accu acy. I he p edic o a iable b ings
no hing bu andom noise, he p edic ion accu acy will like no o be a ec ed a e
he pe mu a ion. OOB obse a ions will be he main cha ac e s in MDA. E e y ime
an indi idual ee is g own o e a boo s ap sample, accu acy in OOB obse a ions is
going o be compu ed. Also, accu acy in OOB obse a ions a e pe mu ing he alues
o some a iable will be compu ed. The MDA o ha a iable is ob ained by a e aging
o e all ees he di e ences o bo h accu acies. See Algo i hm 3.
Algo i hm 3: Compu ing MDA.
Inpu : inpu s in Algo i hm 2.
o b∈ {1, . . . , B}do
Gene a e a boo s ap sample o Dn,Dn(θb).
S o e he OOB obse a ions in Dn(θb).
Cons uc an indi idual decision ee acco ding o Algo i hm 2 o e Dn(θb).
Compu e he numbe o co ec ly classi ied samples in Dn(θb),i.e.,
Accb=X
(x,y)∈Dn(θb)
I{mn(x;θb)=y}.
o j∈ {1, . . . , p}do
Pe mu e andomly he alues ha p edic o a iable j akes on he se
Dn(θb), yielding a sample Dn(θb)j.
Compu e he numbe o co ec ly classi ied samples in Dn(θb)j,i.e.,
Accjb =X
(x,y)∈Dn(θb)j
I{mn(x;θb)=y}.
Compu e di jb =Accb−Accjb.
end
end
o j∈ {1, . . . , p}do
MDA(X(j)) = 1
B
B
X
b=1
di jb.
end
Ou pu : Mean Dec ease Accu acy (MDA) o each p edic o a iable.
The e o e, he la ge he MDA, he be e he associa ed p edic o a iable.
No e 3.2.2. I pe mu a ions a e done o e OOB obse a ions in he same class, a
measu e o a iable impo ance o e each class is ob ained.
Chap e 3. Ensembling ees: Random Fo es s 39
3.2.1.2 Mean Dec ease Impu i y
Ano he way o anking p edic o a iables is Mean Dec ease Impu i y (MDI, [5]).
Recall ha he spli ing c i e ion used o g owing a decision ee, ex ensi ely ex-
plained in Sec ion 2.3, was o selec among e e y non- e minal node ha spli ha
maximizes he in o ma ion gain. This means ha i a a iable appea s in a gi en node
is because, among he o he mp eselec ed a iables, i is he one ha bes sepa a es
be ween classes. As a esul , he MDI is based on ha idea: gi en a p edic o a iable
Xj, i s co esponging MDI is ob ained by a e aging o e all he ees in he o es he
dec ease o impu i y (o , equi alen ly, in o ma ion gain in ou language) co esponding
o spli s along ha a iable, which is weigh ed wi h he ac ion o examples alling
in ha node. As we can see, he e he OOB obse a ions do no ake pa , only he
boo s apped aining samples a e used. See Algo i hm 4.
When he impu i y unc ion is he Gini index, his measu e is commonly called
Gini impo ance.
Algo i hm 4: Compu ing MDI.
Inpu : inpu s in Algo i hm 2.
o b∈ {1, . . . , B}do
Gene a e a boo s ap sample o Dn,Dn(θb).
Cons uc an indi idual decision ee acco ding o Algo i hm 2 o e Dn(θb).
Ini ialize WIG as he null ec o o dimension p.
o j∈ {1, . . . , p}do
o ∈ {1, . . . , numbe .o .non. e minal.nodes}do
i jpa i ions node hen
WIG(Xj) = WIG(Xj) + N
NIG( , s)
end
end
end
end
o j∈ {1, . . . , p}do
MDI(Xj) = 1
B
B
X
b=1
WIG(Xj).
end
Ou pu : Mean Dec ease Impu i y (MDI) o each p edic o a iable.
No e 3.2.3. The impo ance o a p edic o a iable is usually gi en by i s ela i e
in luence, which is simply he ac ion o i s impo ance measu e o e he sum o he
40 3.2. P ope ies o Random Fo es s
impo ance measu es o all a iables:
RIM(Xj) = IM(Xj)
Pp
i=1 IM(Xi),
whe e RIM is he abb e ia ion o Rela i e Impo ance Measu e, IM is he Impo -
ance Measu e ha can be any o MDA and MDI and Xj e e s o he j- h p edic o
a iable.
3.2.2 P oximi y measu e
A p oximi y measu e quan i ies he simila i y o dissimila i y o pai s o objec s. RFs
gi e a no el and embedded way o ob ain a simila i y measu e be ween objec s.
The s anda d p oximi y measu e was p oposed by B eiman [5] and is compu ed as
ollows. Le iand jbe wo objec s, he simila i y measu e be ween bo h, δij, is he
p opo ion o ees ha he RF places bo h in he same e minal node. S a ing wi h
δij = 0, objec iand objec ja e applied down each ee and, each ime hey end up
in he same e minal node, δij is inc eased by one. Finally, his measu e is no malized
by he numbe o ees B. Usually, his p oximi y measu e is calcula ed while he
cons uc ion o RF aking use o he OOB obse a ions. Now, i is no no malized by
Bbu by he numbe o ees whe e each pai o OOB obse a ions concu .
P oximi ies a e ep esen ed by an objec -by-objec ma ix, ∆=(δij), which is
symme ic. E e y δij akes alues on he closed in e al [0,1].δij nea o one means
ha objec s iand ja e alike; so, he main diagonal only con ains ones since any objec
is i ially simila (equal) o i sel . As consequence, he close δij is o ze o, he mo e
dissimila objec s iand ja e.
Recall ha B eiman in [4] and au ho s in [15] ind i necessa y o ake a la ge
numbe o ees o ge s able es ima es o da a p oximi y. In [18], a new p oximi y
measu e when ew ees a e g own is p oposed:
δij =1
BX
b∈B
1
ew·gijb ,
whe e gijb is he numbe o b anches be ween he wo e minal nodes whe e iand j
ha e allen in ee b, and wis an a bi a y pa ame e ha con ols he in luence o he
dis ance be ween bo h e minal nodes. To know how gwo ks, go o Figu e 2.1 and
check ha g 11, 21,1= 3. In his way, gi en a ee b, i iand jend up in he same
e minal node, gi,j,b = 0 and δij will be inc eased by one as in he o iginal p oximi y
measu e.
In addi ion o gi e a di e en p oximi y measu e using RFs, in [18] an app oach
o assessing he quali y o da a p oximi y ma ices is p oposed: o use hem as ke nel
ma ices in a Suppo Vec o Machine (SVM) classi ie . The bes da a p oximi y ma ix
will be he one ha gi es he highes classi ica ion accu acy. Bo h p oximi y measu es,
Chap e 3. Ensembling ees: Random Fo es s 41
he s anda d and he new ones, a e compa ed he eby. An SVM based on he adial
basis unc ion ke nel is also used. Expe imen al esul s ac oss ou da a se s show
ha he p oposed measu e imp o es he da a p oximi y es ima e, especially when RFs
a e made o a small numbe o ees. Fu he mo e, an SVM exploi ing he sugges ed
p oximi y ma ix ke nel has been able o ou pe o m an SVM based on he s anda d
adial basis unc ion ke nel in many cases.
A da a p oximi y ma ix is an impo an in o ma ion sou ce om which RFs can
ake sides o many ele an asks in da a mining: da a isualiza ion ia scaling, ou lie
de ec ion, missing alues impu a ion and p o o ypes sea ch; some o hem speci ic o
RFs’ simila i ies and o he s, mo e gene al. A e iew o how he p oximi y ma ix
ob ained wi h RF can be applied o hese ields is done nex , [7].
3.2.2.1 Da a isualiza ion
Da a isualiza ion includes e e y echnique ha helps o unco e hidden pa e ns in
da a by means o pic u es. In o de o p o ide a isual ep esen a ion o he pa e n
o p oximi ies, RF’s simila i y measu e in ou case, he classical app oach used o
his is Mul iDimensional Scaling (MDS, [13]). MDS is simila o P incipal Compo-
nen Analysis (PCA) wi h he main di e ence ha PCA uses as inpu he co ela ion
ma ix and MDS, any p oximi y ma ix (dissimila i y ma ices, gene ally). The RF’s
dissimila i y ma ix is de ined as ¯
∆ = (¯
δij), whe e
¯
δij =p1−δij.
Wi hou going in o much de ail, he main idea o he MDS is, gi en ¯
∆, o cons uc
n ec o s, 1, . . . , n∈Rm, as many as obse a ions in he sample, such ha k i−
jk ≃ ¯
δij ∀i, j = 1, . . . , n, whe e k·kis an a bi a y no m. When his no m is he
Euclidean one, he MDS is known as he Classical MDS (CMDS). In o he wo ds, i
we a e dealing wi h CMDS, o ins ance, he me hod e u ns a se o poin s in a low
dimensional Euclidean space such ha he Euclidean dis ances be ween he poin s a e
p ese ed.
The mnew coo dena es a e o de ed in he sense ha o i<j, he i- h coo dena e
explains mo e abou he p oximi y o da a han he j- h coo dena e, ∀i, j = 1, . . . , m.
Fo his eason, he i s wo coo dina es o all new poin s 1, . . . , na e usually p o-
jec ed down in o he wo dimensional plane and i poin s o di e en classes a e also
colou ed di e en ly, an o e iew o how sepa a ed he classes a e can be obse ed. In
his way, his pic u e would allow analys s o decide i he model explains he esponse
a iable p ope ly o , by con as , he in o ma ion ob ained is con using. The way o in-
e p e ing his g aph is: he close he dis ance be ween poin s, he close he simila i y
be ween hei co esponding objec s.
In Chap e 2 o [13], a p ac ical algo i hm o he CMDS and i s heo e ical de el-
opmen can be ound.
48 4.1. Random Fo es s and p ope ies
## Sepal.Leng h 8.916362 10.098419 12.051028
## Sepal.Wid h 6.624870 1.037431 8.454989
## Pe al.Leng h 30.762171 46.828426 39.621372
## Pe al.Wid h 32.085780 46.794090 44.675201
## MeanDec easeAccu acy MeanDec easeGini
## Sepal.Leng h 15.506218 9.976061
## Sepal.Wid h 8.264094 2.454234
## Pe al.Leng h 46.363973 42.803821
## Pe al.Wid h 47.402607 44.058583
The p e ious able shows he measu es o impo ance o each a iable. Le us see i
g aphically.
a ImpPlo (i is. )
Sepal.Wid h
Sepal.Leng h
Pe al.Leng h
Pe al.Wid h
10 20 30 40
MeanDec easeAccu acy
Sepal.Wid h
Sepal.Leng h
Pe al.Leng h
Pe al.Wid h
0 10 20 30 40
MeanDec easeGini
i is.
Bo h measu es o a iable impo ance e iewed a e ep esen ed in he pic u e abo e:
on he le side, he MDA; on he igh side, he MDI using he Gini index as he
impu i y unc ion. On his occasion, he e is no disc epancy be ween bo h measu es
since hey poin ou ha he p edic o a iables Pe al.Wid h and Pe al.Leng h a e he
mos impo an .
Nex , ollowing he same o de han in Sec ion 3.2, le us ob ain he s anda d p ox-
imi y ma ix. Again, he same o es is buil , now adding p oximi y = TRUE.
se .seed(1349187)
i is. = andomFo es (Species∼., da a=i is, n ee=1000,
m y=2,p oximi y=TRUE)
A ma ix o dimension 150 by 150 is ob ained. Le us see, o example, he measu e
o p oximi y o he i s i e obse a ions, which co espond o lowe s o he species
Se osa.

Chap e 4. Random Fo es s in R 49
i is. $p oximi y[1:5,1:5]
## 12345
## 1 1.0000000 0.9683544 0.9931973 0.9930070 1.0000000
## 2 0.9683544 1.0000000 0.9877301 0.9790210 0.9791667
## 3 0.9931973 0.9877301 1.0000000 1.0000000 0.9925373
## 4 0.9930070 0.9790210 1.0000000 1.0000000 0.9913043
## 5 1.0000000 0.9791667 0.9925373 0.9913043 1.0000000
I is obse ed ha he i s i e cases a e closely ela ed. Also, emembe ha hey a e
pa o he species ha ou model classi ies bes .
F om now on, we exploi he abili y o he p oximi y ma ix.
Da a isualiza ion
MDSplo (i is. ,i is$Species,pch=19,cex=1.1,
pale e=c(3,5,6),main="Mul idimensional Scaling")
legend(-0.55,0.44,col=c(3,5,6),pch=19,
legend=le els(i is$Species),cex=1.1)
−0.6 −0.4 −0.2 0.0 0.2
−0.4 −0.2 0.0 0.2 0.4
Mul idimensional Scaling
Dim 1
Dim 2
se osa
e sicolo
i ginica
This g aph shows ha he Se osa species is clea ly dis inguished om he o he wo
species, as he con usion ma ix ad anced.
50 4.1. Random Fo es s and p ope ies
Ou lie s de ec ion
ou _measu e = ou lie (i is. )
plo (ou _measu e, ype="h",col=c("g een"," ed","blue"),
[as.nume ic(i is$Species)])
0 50 100 150
0 50 100 200 300
Index
ou _measu e
The species Se osa does no p esen huge le els o ou lyingness, compa ed o species
Ve sicolo and he Vi ginica, being he la e he one wi h mo e ou lie s.
Missing alues impu a ion
I is da abase does no p esen missing alues; howe e , we will do an expe i-
men in o de o see how good he impu a ion me hod p o ided by andom o es s
is when eplacing missing alues. Suppose we do no know he alues o he a iable
Sepal.Leng h o lowe s 1(Se osa), 51 (Ve sicolo ) and 101 (Vi ginica). The algo i hm
o impu a ion o los alues will be applied and, la e , he di e ence be ween he p e-
dic ed and he eal alues o he p edic o a iable Sepal.Leng h o he h ee lowe s
is going o be compu ed.
i is.na = i is
i is.na[1,"Sepal.Leng h"]=NA
i is.na[51,"Sepal.Leng h"]=NA
i is.na[101,"Sepal.Leng h"]=NA
se .seed(1349187)
i is.impu ed = Impu e(Species∼., i is.na)
Chap e 4. Random Fo es s in R 51
(di 1 = i is.impu ed[1,"Sepal.Leng h"]
-i is[1,"Sepal.Leng h"])
## [1] -0.1046023
(di 51 = i is.impu ed[51,"Sepal.Leng h"]
-i is[51,"Sepal.Leng h"])
## [1] -1.125318
(di 101 = i is.impu ed[101,"Sepal.Leng h"]
-i is[101,"Sepal.Leng h"])
## [1] 0.4308188
Excep o he lowe 51, he me hod has a p ope pe o mance.
P o o ypes sea ch
Las , a ep esen a i e ins ance o each species is being compu ed.
x = i is[,names(i is)!="Species"]
label =i is$Species
(i is.p o =classCen e (x,label,i is. $p oximi y))
## Sepal.Leng h Sepal.Wid h Pe al.Leng h
## se osa 5.0 3.4 1.5
## e sicolo 5.8 2.8 4.3
## i ginica 6.5 3.0 5.6
## Pe al.Wid h
## 0.20
## 1.30
## 2.05
Fo e e y species, he p e ious able shows he medioid, i.e., he ins ance ha bes
ep esen s i s class. We will ep esen he p o o ypes oge he wi h he obse a ions
o e he p edic o a iables ela ed o he pe als.
52 4.2. Fea u e Selec ion based on Random Fo es s
1 2 3 4 5 6 7
0.5 1.0 1.5 2.0 2.5
Obse a ions and p o o ypes
Pe al.Leng h
Pe al.Wid h
se osa
e sicolo
i ginica
4.2 Fea u e Selec ion based on Random Fo es s
RFs p o ide wo measu es o a iable impo ance: he MDA and he MDI, p e iously
e iewed in Subsec ion 3.2.1. In his sec ion, he pu pose is o use hese measu es
as Fea u e Selec ion echniques and in es iga e hei pe o mance. Gi en a da a se ,
he idea is o ain di e en classi ie s wi h di e en echniques o Fea u e Selec ion
in he cu en li e a u e (including hose o RFs’ a iable impo ance measu es) and
check which echnique pe o ms bes in e ms o he accu acy o e a es se , o ally
independen om he aining se . The echnique ha gi es he highes accu acy o e
he whole se o classi ie s will be conside ed as he bes . Remembe om Chap e 1
ha he accu acy is de ined as he p opo ion o obse a ions co ec ly classi ied by a
gi en classi ie .
The package andomFo es will be used o compu ing MDA and MDI. The
o he echniques will be aken om he package FSelec o , which con ains some
unc ions o selec ing a ibu es om a gi en da ase . Among hem, he unc ions
c s,chi.squa ed,oneR, elie and consis ency a e used. While he echniques c s and
consis ency gi e a subse o p edic o a iables o conside , he echniques chi.squa ed,
oneR and elie pe o m simila o MDA and MDI: hei ou coming is a anking o he
p edic o a iables, so he size o he subse o p edic o a iables is o be chosen. In
his s udy, a ound he 25% o he whole se o p edic o a iables is aken.
The classi ie s o be used in his s udy a e: Nai e Bayes (NB), Radial Basis Func-
ion (RBF) SVM and o cou se Random Fo es s (RF).
Chap e 4. Random Fo es s in R 53
An ou line o he expe imen can be seen in Algo i hm 7.
Algo i hm 7: Compa ison o Fea u e Selec ion echniques.
Gi en a da a se :
S ep 1. Spli he sample in o a aining sample (70%) and a es sample (30%).
S ep 2. Ob ain he subse o p edic o a iables conside ed o e e y Fea u e
Selec ion echnique using he aining sample.
S ep 3.
• T ain he di e en classi ie s making hei co esponding pa ame e s uning o
e e y subse o p edic o a iables ob ained in S ep 2. The aining sample is
used.
• Measu e he pe o mance (accu acy) o e he es sample o e e y pai Fea u e
Selec ion echnique - Classi ie .
S ep 4. Ge conclusions.
Th ee di e en da a se s a e used o his ask: B eas Cance Wisconsin, Iono-
sphe e and Spam da a se s:
• B eas Cance Wisconsin, which consis s o a sample o size 569 on which 30
con inuous ea u es a e compu ed om a digi ized image o a ine needle aspi a e
(FNA) o a b eas mass. They desc ibe cha ac e is ics o he cell nuclei p esen in
he image. Mo eo e , he e is a a iable ha iden i ies e e y obse a ion, which
is ou o he s udy, and he esponse a iable malignan ha akes he alue 1i
he cell is malignan and 0, o he wise.
• Ionosphe e, which comp ises 351 obse a ions (elec ons in he ionosphe e) on
which 35 a iables we e measu ed. The i s 34 a iables a e p edic o and con-
inuous, excep wo o hem ha ha e been emo ed om he s udy; he las one
is he esponse a iable and akes good i e u ns a e hose showing e idence o
some ype o s uc u e in he ionosphe e and bad, i e u ns a e hose ha do no ;
hei signals pass h ough he ionosphe e.
• Spam, which con ains a sample o 4601 e-mails spam and non-spam so he e-
sponse a iable akes one o hese alues. In addi ion o his class label he e a e
57 p edic o a iables indica ing he equency o ce ain wo ds and cha ac e s
in he e-mail.
The code used in R o he Spam da ase will be displayed nex . Fo B eas Cance
Wisconsin and Ionosphe e da a se s, he p ocedu e is he same.
Fi s , he da a se Spam is loaded om he lib a y ke nlab. Du ing he expe imen ,
when dealing wi h andomness, seeds a e going o be se in o de o make he esul s
ep oducible a any code line.

54 4.2. Fea u e Selec ion based on Random Fo es s
lib a y(ke nlab)
da a(spam)
S ep 1
se .seed(123)
n <- n ow(spam)
ainindex <- sample(1:n, size = loo (0.7*n))
spam. ain <- spam[ ainindex,]
spam. es <- spam[- ainindex,]
S ep 2
A he same ime each subse o p edic o a iables is ob ained o a gi en Fea u e
Selec ion echnique, he aining and he es samples o ha es ic ed se o p edic o
a iables a e going o be s o ed.
MDA and MDI
The way o ob aining bo h a iable impo ance measu es p o ided by RF is based
on B eiman’s ad ice: Bis aken la ge enough in o de o ge s able measu es, B=
5000, and mis uned be ween m1=d√pe,m2=1
2d√peand m3= 2d√pe. The
chosen alue o mwill be he one ha gi e he low e o a e in he OOB obse a ions.
Fo he MDI, he Gini index is aken as he impu i y unc ion.
lib a y( andomFo es )
p <- ncol(spam)-1
m1 <- ound(sq (p))
m2 <- 0.5*m1
m3 <- 2*m1
se .seed(123)
RFm1 <- andomFo es ( ype∼., da a=spam. ain, n ee=5000,
m y=m1)
p in (RFm1)
##
## Call:
## andomFo es ( o mula = ype ~ ., da a = spam. ain,
## n ee = 5000, m y = m1)
## Type o andom o es : classi ica ion
Chap e 4. Random Fo es s in R 55
## Numbe o ees: 5000
## No. o a iables ied a each spli : 8
##
## OOB es ima e o e o a e: 4.63%
## Con usion ma ix:
## nonspam spam class.e o
## nonspam 1897 60 0.03065917
## spam 89 1174 0.07046714
se .seed(123)
RFm2 <- andomFo es ( ype∼., da a=spam. ain, n ee=5000,
m y=m2)
p in (RFm2)
##
## Call:
## andomFo es ( o mula = ype ~ ., da a = spam. ain,
## n ee = 5000, m y = m2)
## Type o andom o es : classi ica ion
## Numbe o ees: 5000
## No. o a iables ied a each spli : 4
##
## OOB es ima e o e o a e: 5%
## Con usion ma ix:
## nonspam spam class.e o
## nonspam 1899 58 0.02963720
## spam 103 1160 0.08155186
se .seed(123)
RFm3 <- andomFo es ( ype∼., da a=spam. ain, n ee=5000,
m y=m3)
p in (RFm3)
##
## Call:
## andomFo es ( o mula = ype ~ ., da a = spam. ain,
## n ee = 5000, m y = m3)
## Type o andom o es : classi ica ion
## Numbe o ees: 5000
## No. o a iables ied a each spli : 16
##
## OOB es ima e o e o a e: 4.88%
56 4.2. Fea u e Selec ion based on Random Fo es s
## Con usion ma ix:
## nonspam spam class.e o
## nonspam 1892 65 0.03321410
## spam 92 1171 0.07284244
Acco ding o he esul s, m=m1:
se .seed(123)
RF <- andomFo es ( ype∼., da a=spam. ain, n ee=5000,
m y=m1, impo ance=TRUE)
names <- colnames(spam)
size <- ceiling(0.25*p)
subse MDA <- names[o de (RF$impo ance[,"MeanDec easeAccu acy"],
dec easing = TRUE)][1:size]
ainMDA <- spam. ain[,c(subse MDA," ype")]
es MDA <- spam. es [,c(subse MDA," ype")]
subse MDGini <- names[o de (RF$impo ance[,"MeanDec easeGini"],
dec easing = TRUE)][1:size]
ainMDGini <- spam. ain[,c(subse MDGini," ype")]
es MDGini <- spam. es [,c(subse MDGini," ype")]
Now, om FSelec o package.
lib a y(FSelec o )
lib a y(RWeka)
CFS
subse CFS <- c s( ype∼., spam. ain)
ainCFS <- spam. ain[,c(subse CFS," ype")]
es CFS <- spam. es [,c(subse CFS," ype")]
chi.squa ed
weigh sChi <- chi.squa ed( ype∼.,spam. ain)
subse Chi <- cu o .k(weigh sChi, size)
ainChi <- spam. ain[,c(subse Chi," ype")]
es Chi <- spam. es [,c(subse Chi," ype")]
oneR
Chap e 4. Random Fo es s in R 57
weigh sOneR <- oneR( ype∼.,spam. ain)
subse OneR <- cu o .k(weigh sOneR,size)
ainoneR <- spam. ain[,c(subse oneR," ype")]
es oneR <- spam. es [,c(subse oneR," ype")]
elie
weigh sRelie <- elie ( ype ., spam. ain, neighbou s.coun
= 5,sample.size = 20)
subse Relie <- cu o .k(weigh sRelie , size)
ain elie <- spam. ain[,c(subse elie ," ype")]
es elie <- spam. es [,c(subse elie ," ype")]
Consis ency
subse Consis ency <- consis ency( ype∼., spam. ain)
ainConsis ency <- spam. ain[,c(subse Consis ency," ype")]
es Consis ency <- spam. es [,c(subse Consis ency," ype")]
S ep 3 In his s ep e e y classi ie has o be ained wi h he aining sample o
each Fea u e Selec ion echnique and, hen, be e alua ed o e hei co esponding es
sample. He e, he pai s NB-MDA, RBF SVM-MDA and RF-MDA a e displayed.
None heless, all he pai s ha e been compu ed and a e shown in Table 4.1.
NB
NB does no equi e any uning p ocedu e, which speeds up he expe imen .
lib a y(e1071)
NBMDA <- nai eBayes( ype∼.,da a = ainMDA)
p edi es NBMDA <- p edic (NBMDA, es MDA[,-ncol( ainMDA)])
con u es NBMDA <- able( es MDA[,ncol( ainMDA)],
p edi es NBMDA)
(NBMDAaccu acy <- 100*(con u es NBMDA[1,1]+
con u es NBMDA[2,2])/sum(con u es NBMDA))
## [1] 82.26
RBF SVM
The RBF SVM has wo pa ame e s o une. The same pa ame e s g id has been
made o all cases and he pai o pa ame e s ha gi e he bes pe o mance is chosen.