IJCSS, Vol.1, No.1, 2000 73
DISCOVERING HIERARCHICAL DECISION RULES WITH
EVOLUTIVE ALGORITHMS IN SUPERVISED LEARNING
José C. Riquelme, Jesús S. Aguila and Miguel To o
Depa amen o de Lenguajes y Sis emas In o má icos.
Facul ad de In o má ica y Es adís ica.
A enida Reina Me cedes s/n
41012 Se illa
Spain
e-mail: iquel[email p o ec ed]s, aguila @lsi.us.es, miguel. o [email protected]
Accep ed in he Þnal o m: 15 No embe , 2000
Abs ac .This pape desc ibes a new app oach, HIDER (HIe a chical DEcision Rules), o lea ning
ules in con inuous and disc e e domains based on e olu i e algo i hms. The algo i hm p oduces a
hie a chical se o ules, ha is, he ules mus be applied in a speciÞc o de . Wi h his policy, he
numbe o ules may be educed because he ules could be one inside o ano he . The e olu i e
algo i hm uses bo h eal and bina y codiÞca ion o he indi iduals o he popula ion and in oduces
se e al new gene ic ope a o s. In addi ion, his pape discusses he capabili y o lea ning sys ems
based on an e olu i e algo i hm o educe bo h he numbe o ules and he numbe o a ibu es
in ol ed in he ule se . We ha e es ed ou sys em on eal da a om he UCI eposi o y. The esul s
o a 10- old c oss alida ion a e compa ed o C4.5’s and hey show an impo an imp o emen .
Keywo ds: E olu i e Algo i hms, Supe ised lea ning, Decision Lis s.
1In oduc ion
Supe ised lea ning is used when he use knows he ou comes o he da a samples and wan s o
p edic he ou come o a new unseen ins ance. An algo i hm ca ies ou he p edic ion (classiÞca ion)
and i can p oduce knowledge by using a sui able da a s uc u e. Some echniques, like nea es
neighbou sea ching o neu al ne wo ks, can classi y an ins ance, bu canno ob ain he knowledge
om he in o ma ion s o ed in he da abase. This so o lea ning is called “lazy lea ning” because
he algo i hm does no gene a e a model o knowledge o he da abase. Howe e , o he echniques
p oduce se s o ules wi h a speciÞc s uc u e: decision ees, decision lis s, o simply, se o ules. In
gene al, when a ule-based amewo k is used o exp ess he acqui ed knowledge, his is o en called
decision ules. Such ules can subsequen ly be used bo h o in e p ope ies o he co esponding
ca ego ies and o classi y o he , p e iously unseen, examples om he o iginal space.
The algo i hm is an once o p oduce he se o ules ha classi y many new ins ances. O he
echniques as nea es neighbou classiÞe s need one execu ion e e y ime we wan o p edic he class o
an unseen new example. The e o e, he diffe ence be ween he echniques ha can p oduce knowledge
and hose ha canno is e y impo an om he poin o iew o he numbe o execu ions.
Supe ised lea ning algo i hms end o emula e he human beha iou , since om inpu condi ions
y o p edic he ac ion o be aken, based upon expe ience wi h simila si ua ions. Such expe ience
74 IJCSS, Vol.1, No.1, 2000
is collec ed in a da abase and knowledge is in e ed by means o heu is ics o algo i hms.
Decision ees a e a pa icula ly use ul ool in he con ex o supe ised lea ning because hey
pe o m classiÞca ion by a sequence o es s whose seman ics is in ui i ely clea and easy o unde s and.
Some echniques, like C4.5 [1], cons uc decision ees selec ing he bes a ibu e by using a s a is ical
es o de e mine how well i alone classiÞes he aining examples. This so o decision ees may be
called axis-pa allel, because he es s a each node a e equi alen o axis-pa allel hype planes in he
space. On he con a y, o he echniques build oblique decision ees, as OC1[2], ha es s a linea
combina ion o he in e nal a ibu es a each node, o ha , hese es s a e equi alen o hype planes
a an oblique o ien a ion o he coo dina e axes. To Þnd ou he smalles decision ee (axis-pa allel
o oblique) is a NP-ha d p oblem [3]. Bo h me hods use hill-climbing, ha is, he algo i hm ne e
back acks; he e o e, i could be con e ging o locally op imal solu ions ha a e no globally op imal.
Simpson [4] in oduced he idea o using hype ec angles o clus e o classi y spa ial da a. Each
hype ec angle is iewed as a uzzy clus e , a uzzy se in which all o he elemen s wi hin he hype ec -
angle ha e membe ship 1, and examples ou side he hype ec angle can ha e a posi i e membe ship in
he se depending on a uzzy membe ship unc ion. Simpson used a de e minis ic p ocedu e o place
and app op ia ely size hype ec angles o desc ibe da a.
Gene ic Algo i hms (GA) a e a amily o compu a ional models inspi ed by e olu ion. These
algo i hms employ a andomized sea ch me hod o Þnd solu ions o a pa icula p oblem [5]. This
sea ch is qui e diffe en om he o he lea ning me hods men ioned abo e. A GA is any popula ion-
based model ha uses selec ion and ecombina ion ope a o s o gene a e new sample examples in a
sea ch space [6]. The GA sea ch can mo e much mo e ab up ly, eplacing a pa en indi idual wi h an
offsp ing less likely o all in o he same kind o local minima ha can happen wi h he o he me hods.
GAs ha e been used in a wide a ie y o op imiza ion asks [7, 8] including nume ical op imiza ion
and combina o ial op imiza ion p oblems, al hough he ange o p oblems o which GAs ha e been
applied is qui e b oad. The main asks in applying GAs o any p oblem a e selec ing an app op ia e
ep esen a ion (coding) and an adequa e e alua ion unc ion (Þ ness).
In classical GAs he membe s o he popula ion ( ypically main aining a cons an -sized) a e ep-
esen ed as Þxed-leng h s ings o bina y digi s. The leng h o he s ings and he popula ion size
Pa e comple ely dependen on he p oblem. The popula ion simula es he na u e beha io since
he ela i ely “good” solu ions p oduce offsp ing, which eplace he ela i ely “wo se” ones, e aining
many o he ea u es o hei pa en s. The es ima e o he quali y o a solu ion is based on a Þ ness
unc ion, which de e mines how good an indi idual is wi hin he popula ion in each gene a ion.
New indi iduals (offsp ing) o he nex gene a ion a e o med by using (no mally) wo gene ic
ope a o s: c osso e and mu a ion. C osso e combines he ea u es o wo indi iduals o c ea e
se e al (commonly wo) indi iduals. Mu a ion ope a es by andomly changing se e al componen s o
a selec ed indi idual.
The aim o ou esea ch was o ob ain a se o ules o classi y a da abase in he con ex o
supe ised lea ning. In p e ious wo ks, we p esen ed a sys em o classi y da abases using bina y coding
[9]; a e wa ds, we adop ed eal codiÞca ion o handle efficien ly con inuous domains and axis-pa allel
ep esen a ions. (In addi ion, we explo ed o he ep esen a ions such as o a ed hype ec angles and
hype ellipses). Then, new gene ic ope a o s we e in oduced o eal codiÞca ion. This me hod is
concep ually nea e o e olu iona y algo i hms (EA) han GA. This new sys em used an EA o sea ch
he bes solu ions and p oduced a hie a chical se o ules. The hie a chy ollows ha an example will
be classiÞed by he i h- ule i i does no ma ch he condi ions o he (i−1) h p eceden ules. The
ules a e sequen ially ob ained un il he space is o ally co e ed.The beha io is simila o a decision
lis [10]. A decision lis DL is a lis o pai s ( 1,
1),...,( ,
)whe e each jis a e m in Cn
k,each i
is a alue in {0,1},and helas unc ion is he cons an unc ion ue.(Cn
kdeno es he se o all
e ms (conjunc ions) o size a mos k wi h li e als d awn om Ln={x1, x1,...,x
n, xn}, he e o e,
|Cn
k|=
k
X
i=0 Ã2n
i!(1)
IJCSS, Vol.1, No.1, 2000 75
I condi ions Then class
Else I condi ions Then class
Else I condi ions Then class
............................................
Else "unknown class"
Figu e 1: Hie a chical se o ules.
A decision lis DL deÞnes a boolean unc ion as ollows: o any assignmen x∈Xn,DL(x)is deÞned
o be equal o jwhe e jis he leas index such ha j(x)=1(such an i em always exis s, since he
las unc ion is always ue).
I is e y impo an o no e ha decision ules a e no he same hing as decision lis s. The concep
o decision ules is mo e gene al han decision lis s, because a decision lis is a linea ly o de ed se o
decision ules [10].
We ex end he concep o decision lis o con inuous domains. Decision lis s wo k well wi h objec s
ha a e desc ibed as concep s, so i can ep esen boolean a ibu es (posi i es o nega i es examples).
Howe e , when we wan o lea n ules in he con ex o con inuous a ibu es, we need o ex end he
concep o decision lis in wo ways: Þ s , o adap ing he boolean unc ions o in e al unc ions; and
second, o ep esen ing classes ins ead o ue and alse alues (posi i es and nega i es examples).
We le Cdeno e he se o classes (labels) o a da abase. Fo each con inuous ( eal) a ibu e aiwe
ob ain he bounda y alues, called liand ui(lowe and uppe bounda ies, espec i ely) which deÞne
he space Ri( ange o he a ibu e i). Le Hibe an in e al [l, u]whe e l<uand l, u ∈Ri, o he
a ibu e i.Then,anex ended decision lis EDL is a lis o pai s
( 1,
1),...,( ,
)(2)
whe e each iis a unc ion in H1×H2×···Hm, iis a alue in Cand mis henumbe o a ibu es.
Ou EDL does no ha e he las cons an unc ion ue as DL has. Howe e , we could in e p e
he las unc ion as an unknown unc ion, ha is, we do no know which class he example belongs
o. The e o e, i may be ad isable o say “unknown class” ins ead o making an e oneous decision.
The s uc u e o he se o ules will be as shown in Þgu e 1.
Decision lis policy is applied in o de o educe he numbe o ules. Fo an a iÞcial wo-
dimensional da abase, Þgu e 2 shows he classiÞca ion ha C4.5 gi es. Ne e heless, as illus a ed in
Þgu e 3, ules inside o ano he one could imp o e he quali y o he ule se .
A
B
B
A
B
A
A
A
A
A A
A
A
B
B B
A
Figu e 2: C4.5
The mos e iden ea u e, g aphically obse ed in Þgu e 3, is he educ ion o he numbe o ules
because o he ules o e lapping.
As men ioned in [11] one o he p ima y mo i a ions o using eal-coded EAs is he p ecision
o ep esen a ibu es alues and ano he is he abili y o exploi he g adualness o unc ions o
76 IJCSS, Vol.1, No.1, 2000
A
B
B
A
B
Figu e 3: HIDER
con inuous a ibu es. We implemen ed ou Þ s e sions wi h bina y-coded GAs, bu we could p o e
ha eal-coded EAs a e mo e efficien ( ime and quali y o esul s). In addi ion, HIDER educes he
numbe o a ibu es in ol ed in a ule, making i s comp ehension by humans easie .
2 P inciples
Be o e an EA can be un, a sui able coding o he p oblem mus be de ised. We also equi e a Þ ness
unc ion, which assigns a Þgu e o me i o each coded solu ion. Du ing he un, pa en s a e selec ed
o ep oduc ion, and ecombined o gene a e offsp ing. These aspec s a e desc ibed below.
2.1 Coding
In o de o apply EAs o a lea ning p oblem, we need o selec an in e nal ep esen a ion o he
space o be sea ched and deÞne an ex e nal unc ion ha assigns Þ ness o candida e solu ions. Bo h
componen s a e c i ical o he success ul applica ion o he EAs o he p oblem o in e es .
In o ma ion o he en i onmen comes om a da a Þle, whe e each example has a class and a
numbe o a ibu es. We ha e o codi y ha in o ma ion o deÞne he sea ch space, which no mally
will be dimensionally g ea e . Each a ibu e will be o med by se e al componen s in he sea ch
space, depending on he speciÞc ep esen a ion.
To Þnd ou an app op ia e coding o he p oblem is e y difficul , bu i is almos impossible o ge
he pe ec one. The e exis wo basic p inciples o choosing he coding: he p inciple o meaning ul
building blocks and he p inciple o minimal alphabe s [5].
In Þ s app oaches, we s udied se e al GA-based classiÞe [12, 13] wi h bina y coding. These a e
gene ally used as concep lea ne s, which coding assigns a bi o each alue o he a ibu e, i.e., e e y
a ibu e is symbolic (GABIL and GIL a e wo e y known sys ems). Fo example, an a ibu e wi h
h ee possible alues would be ep esen ed by h ee bi s. A alue o one in a bi indica es ha he
alue o he a ibu e is p esen . Se e al bi s could be ac i e. This coding is app op ia e o symbolic
domains. Howe e , i is e y difficul o use in con inuous domains, because he numbe o possible
alues o an a ibu e is inÞni y.
The leng h o an indi idual is de e mined by he sum o he numbe o alues o each a ibu e.
Using bina y encoding in con inuous domains equi es ans o ma ions om bina y o eal o e e y
a ibu e. To apply he e alua ion unc ion is necessa y o con e he bina y o eal encoding. This
p ocess inc eases he compu a ion ime by a ac o o m(numbe o a ibu es).
Mo eo e , when we con e bina y o eal, we a e loosing p ecision. Fo ha eason, we ha e o
Þnd he exac numbe o bi s o elimina e he diffe ence be ween any wo alues o an a ibu e. This
ensu es ha a mu a ion o he leas signiÞcan bi o an a ibu e will no include o exclude mo e
han one example om he aining se in a single s ep. Le liand uibe he lowe and uppe bounds o
IJCSS, Vol.1, No.1, 2000 77
an a ibu e. Le mibe he leas absolu e diffe ence o any wo alues o he a ibu e i.Theallowed
e o o his a ibu e mus be less han mi. Then, he leng h o an a ibu e would be as ollows:
Li=»log2µ1+ui−li
e o i¶¼ (3)
Howe e , in his pape , o elimina e he p oblem we use he eal codiÞca ion. Thisimplies o
edeÞne he gene ic ope a o s o i as we see below.
The ep esen a ion o con inuous and disc e e a ibu es is bes explained by e e ing o Þgu e
4, whe e liand uia e alues ep esen ing an in e al o he con inuous a ibu e; bia e bina y alues
indica ing ha he alue o he disc e e a ibu e is ac i e o no . A las alue (omi ed) is o he
class.
con inuous disc e e
a ibu e
b 1 b
2 b k
...
Bina y
alues
l
i u i a ibu e
Real
alues
Figu e 4: Con inuous (le ) and disc e e ( igh ) a ibu es.
The numbe o classes de e mines he se o alues o which an example belongs, i.e., i he e a e
Þ e classes, he alue o a class will belong o he se {0,1,2,3,4}. E e y ule will be ob ained om
his ep esen a ion, bu when li=min(ai)o ui=max(ai) he ulewillno ha edeÞned ha alue
in he in e al. Fo example, in he Þ s case he ule would be [−, ]( he le alue o he in e al is
equal o he minimum alue o he ange o he a ibu e) and in he second one [ ,−]( he igh alue
o he in e al is equal o he maximum alue o he ange o he a ibu e). I bo h alues a e equal
o he bounda ies hen he ule appea s [−,−] o ha a ibu e, which means ha i is no ele an .
Unde hese assump ions, some con inuous a ibu es may no appea in he ule se . In addi ion,
when e e y disc e e alue is ac i e, ha a ibu e does no appea in he ule.
2.2 Algo i hm
The algo i hm is a ypical sequen ial co e ing GA [14]. I chooses he bes indi idual o he e olu ion-
a y p ocess, ans o ming he indi idual in o a ule, which is used o elimina e da a om he aining
Þle [15]. In his way, he aining Þle is educed o he ollowing i e a ion. A e mina ion c i e ion
could be eached when mo e examples o co e do no exis . The me hod o gene a ing he ini ial
popula ion consis s o andomly selec ing an example om he aining Þle o e e y indi idual o he
popula ion. Then, an in e al o which he example belongs is ob ained by adding and sub ac ing a
andom quan i y om he alues o he example.
Some imes, he examples e y nea o he bounda ies a e ha d o co e du ing he e olu iona y
p ocess. To esol e his p oblem, he sea ch space is inc eased (ac ually, he lowe bound is dec eased
by 5%, and he uppe bound is inc eased by 5%). Fo example in one dimension, le aand bbe he
lowe and uppe bounds o he a ibu e; hen, he ange o he a ibu e is b−a; nex , we andomly
choose an example (x1,class) om he aining Þle; o las , a possible indi idual o he popula ion
could hus be (x1− ange ×k1,x
1+ ange ×k2,class)whe e k1and k2a e andom alues belonging
o [0, ange
N](Nis he size o he aining da a, and class is he same o ha o he example). Fo
disc e e a ibu es, his is no a p oblem because he indi idual has he same ac i e alues as he
example. The e olu ion module includes eli ism: he bes indi idual o e e y gene a ion is eplica ed
o he nex one. A se o child en (50%) is ob ained om copies o andomly selec ed pa en s, gene a ed
by hei Þ ness alues and using he oule e wheel selec ion. These indi iduals could be mu a ed la e
(only he indi idual om he eli e will no be mu a ed). The emainde is o med h ough c osso e s.
A e wa ds, mu a ion is applied depending on a p obabili y.
An o e iew o he EA-based classiÞe isshownin heÞgu e 5.

78 IJCSS, Vol.1, No.1, 2000
While exis s examples in aining ile
S ep 1. Ini ialize popula ion
S ep 2. Repea num gene a ions imes
S ep 2.1. E alua ion
S ep 2.2. Selec he bes
S ep 2.3. Replica ion
S ep 2.4. C osso e and Mu a ion
S ep 3. Pu he bes one in Decision Lis
S ep 4. Elimina e examples co e ed by bes
Figu e 5: Pseudocode.
W igh ’s linea c osso e ope a o [16] c ea es h ee offsp ing: ea ing wo pa en s as wo poin s
p1and p2, one child is he midpoin o bo h, and he o he wo lie on a line de e mined by 3
2p1−1
2p2
and −1
2p1+3
2p2. Radcliffe’s ßa c osso e [17]chooses alues o anoffsp ing by uni o mly picking
alues be ween (inclusi ely) he wo pa en s alues. Eshelman and Schaffe use a c osso e ope a o
ha is a gene aliza ion o Radcliffe’s which is called blend c osso e (BLX-α). I uni o mly picks
alues ha lie be ween wo poin s ha con ain he wo pa en s, bu may ex end equally on ei he
side de e mined by a use speciÞed EA-pa ame e α.Fo example,BLX-0.1picks alues om poin s
ha lie on an in e al ha ex ends 0.1Ion ei he side o he in e al I be ween he pa en s. Logically,
BLX-0.0is he Radcliffe’s ßa c osso e .
Ou c osso e ope a o is like Radcliffes’s mos o he ime, and some imes he alue is pe u bed
o app oxima e i o he bounda y. Le [l1,u
1]and [l2,u
2]be he in e als o wo pa en s o he
same a ibu e. In he Þgu e 6 he pa en s a e in he Þ s wo segmen s. F om hese pa en s we can
gene a e ou possible child en selec ing alues as ollows: le [l, u]be he in e al we wan o ob ain
a e applying he c osso e o wo pa en s and le Land Ube he bounda ies o he a ibu e being
ea ed. We ha e ou possibili ies ( he pe cen ages o applica ion a e o he igh ):
l∈[l1,l
2]u∈[u1,u
2] 85%
l∈[L, min(l1,l
2)] u∈[max(u1,u
2),U]5%
l∈[l1,l
2]u∈[max(u1,u
2),U]5%
l∈[L, min(l1,l
2)] u∈[u1,u
2]5%
1
1 u
1
1
2 u
2
(1)
(2)
Figu e 6: Axis-Pa allel c osso e ope a o .
Mu a ion is applied in wo diffe en ways: i he andomly chosen loca ion co esponds o a alue
o he in e al, hen a quan i y is sub ac ed o added, depending on whe he i is he lowe o he
uppe bound, espec i ely ( he quan i y ac ually is he lowe Euclidean dis ance be ween any wo
examples); i he loca ion co esponds o he class, a new alue is andomly gene a ed.
When he a ibu e is disc e e, he c osso e ope a o is like uni o m c osso e [18] and mu a ion
is applied wi h low p obabili y. We in oduce a speciÞc mu a ion ope a o o gene alize he a ibu e
IJCSS, Vol.1, No.1, 2000 79
when almos all alues a e 1. In his case, he a ibu e does no appea in he ule. Fo example in
Þgu e 10, he a ibu e sex is no in he ule R1.
2.3 Relaxing coefficien
Da abasesusedas ainingÞles do no ha e clea ly diffe en ia ed a eas. The e o e, o ob ain a ule
sys em o ally cohe en (wi hou e o om he aining Þle) in ol es a high numbe o ules. We
showed in p e ious pape s [19] a sys em capable o p oducing a ule se exemp om e o ; howe e
some imes, i is in e es ing o educe he numbe o ules o ha ing a ule se which may be used
like a comp ehensible linguis ic model. In his way, i could be be e o ha e a sys em wi h ewe
ules, despi e some e o s, han oo many ules and no e o s. When da abases p esen a dis ibu ion
o examples e y ha d o classi y, i may be in e es ing o in oduce he elaxing coefficien (RC) o
unde s anding he beha io o da abases by dec easing he numbe o ules [20]. RC indica es wha
pe cen age o examples inside o a ule can ha e a diffe en class han wha he ule has. RC beha es
like he uppe bound o he e o wi h espec o he aining Þle, ha is, as an allowed e o a e.
To deal efficien ly wi h noise and Þnd a good alue o RC, he expe should ha e an es ima e o he
noise pe cen age in i s da a. Fo example, i da abase X p oduces oo many ules when RC is 0, we
could se RC o 5 o dec ease he numbe o ules and, possibly, he e o a e migh be he same as
be o e.
2.4 Fi ness unc ion
The Þ ness unc ion mus be able o disc imina e be ween co ec and inco ec classiÞca ion o exam-
ples. Finding an app op ia e unc ion is no a i ial ask, due o he noisy na u e o mos da abases.
The e olu iona y algo i hm minimizes he Þ ness unc ion o each indi idual. I is gi en by
(i)=2(N−CE(i)) + G(i)+Co e age(i)
whe e he ule co e age is he alue o he side o a k-dimensional hype cube which olume is equi alen
o he olume o he k-dimensional egion co e ed by he ule; CE(i)is he class e o , which a e
p oduced when he example ibelongs o he egion deÞned by he ule, bu does no ha e he same
class; G(i)is he numbe o goals o he ule. E e y ule can be quickly expanded o Þnding mo e
examples due o he ule co e age in he Þ ness unc ion. The eason why (i)is no N−CE(i)+
G(i)+Co e age(i)is as ollows: o example, when CE(i)=7and G(i)=9we will ha e he same
Þ ness alue as when CE(i)=15and G(i)=17( he diffe ence is 2; assuming he same co e age o
bo h). The e o e, we decided o penal y he second case (9
7is g ea e han 17
15 ).
3 Applica ion
The expe imen s desc ibed in his sec ion a e om he UCI eposi o y [21]. To measu e he pe o -
mance o he me hod, a 10- old c oss alida ion was ealized wi h each da ase . I is e y impo an
o no e ha e e y execu ion has been ca ied ou wi h a popula ion size o as li le as 100 indi iduals
and 300 gene a ions o he EA. These a e e y low numbe s conside ing he numbe he examples
and he dimensionali y o some da abases. HIDER needed abou 8hou s o comple e he 10- old c oss
alida ion o he 18 da abases on a Pen ium 400Mhz wi h 64Mb o RAM. Howe e , C4.5 only needed
abou 8minu es on he same machine. C4.5 is an ex emely obus algo i hm ha pe o ms well on
many domains. I is e y difficul o consis en ly ou pe o m C4.5 on a a ie y o da ase s. Thus,
imp o ing C4.5 should yield an in e es ing lea ning algo i hm.
The esul s o hese ials appea in ables 1, 2 and 3. Table 1 gi es a 10- old c oss alida ion o
he e o a es o he C4.5 and HIDER algo i hms on he selec ed domains.
Table 2 compa es he numbe o ules gene a ed by he wo app oaches. F om he poin o iew o
he comp ehension o he knowledge inside he da abase, HIDER is much be e han C4.5 since he
numbe o ules is e y much lowe .
80 IJCSS, Vol.1, No.1, 2000
Table 1: Compa ing e o a es.
Da abase C4.5R8 HIDER
Bupa 34.73 35.71
B eas Cance 6.28 4.29
Cle eland 26.77 20.49
Ge man 32.1 29.1
Glass 32.73 29.41
Hea 21.83 22.32
Hepa i is 21.42 19.41
Ho se Colic 19.0 17.64
I is 4.67 3.33
Lenses 29.99 25.0
Mush oom 0.01 0.76
Pima 32.06 25.9
Sona 30.31 43.07
Tic-Tac-Toe 14.2 3.85
Vehicle 30.6 30.6
Vo e 6.19 6.42
Wine 6.71 3.95
Zoo 7.0 8.0
A e age 19.81 18.29
The se o ules gene a ed o he Wine da abase is p esen ed in Þgu es 7 and 8. The exac same
olds we e used o bo h algo i hms so ha he en esul ing pe o mance numbe s o HIDER and
C4.5 a e pai waise compa able. HIDER p oduced an e o a e o 0%, howe e , ha o C4.5 was
22.2%.
c12<=2.15:
| c4 <= 17.5 : 2 (6.0)
| c4 > 17.5 : 3 (45.0/2.0)
c12 > 2.15 :
| c13 <= 725 : 2 (54.0/1.0)
| c13 > 725 :
| |c10 <= 3.4 : 2 (4.0)
| | c10 > 3.4 : 1 (51.0)
Figu e 7: Decision T ee gene a ed by C4.5 o Wine da abase.
Table 3 shows a measu e o imp o emen (²) o he e o a e (Þ s column: (²e )) and he numbe
o ules (second column: (²n )). To calcula e hose coefficien (²e and ²n , espec i ely) he e o a e
(numbe o ules) o C4.5 has been di ided by he e o a e (numbe o ules) o HIDER. The las
ow con ains he a e age o e e y column. On a e age, HIDER ound solu ions ha had less han hal
o he ules ou pu by C4.5. Su p isingly, C4.5 gene a ed a numbe o ules Þ e imes g ea e han
HIDER o one hi d o he da abases.
Figu es 9 and 10 illus a e an example a li le mo e complex (Hepa i is da abase), which shows
ha when he numbe o ules is la ge, he numbe o a ibu es in ol ed in he ule se is also educed.
Thus, in he example, C4.5 uses 63 condi ions and HIDER uses 30 condi ions.
Mo o e , he e o a e was 31.2% o C4.5, in con as wi h 12.5% o HIDER (using he same
old).
IJCSS, Vol.1, No.1, 2000 81
Table 2: Compa ing numbe o ules.
Da abase C4.5R8 HIDER
Bupa 28.6 11.3
B eas Cance 21.9 2.6
Cle eland 35.2 7.9
Ge man 181.5 13.3
Glass 29.0 19.0
Hea 29.2 9.2
Hepa i is 13.8 4.5
Ho se Colic 39.3 6.0
I is 5.5 4.8
Lenses 4.1 6.5
Mush oom 15.5 3.1
Pima 93.6 16.6
Sona 16.8 2.8
Tic-Tac-Toe 93.9 11.9
Vehicle 102.3 36.2
Vo e 14.7 4.0
Wine 5.4 3.3
Zoo 9.9 7.2
A e age 41.12 9.46
IF R1: c7 [1.08,-] and
c10 [3.82,-] and
c13 [741.80,-] : 1(51|0)
ELSE IF R2: c7 [1.14,-] and
c11 [0.68,-] and
c12 [1.61,-] : 2(64|1)
ELSE IF R3: c4 [11.57,-] : 3(43|0) ELSE unknown
Figu e 8: Hie a chical Decision Lis gene a ed by HIDER o Wine da abase.
4 Conclusions
A supe ised lea ning ool o classi y da abases is p esen ed in his pape . I p oduces a hie a chical
se o decision ules whe e he condi ions o each ule indica e i an example belongs o a egion. The
numbe o ules is educed wi h ega d o o he sys ems, like C4.5, and imp o es he ßexibili y o
cons uc a classiÞe a ying he elaxing coefficien . We also ha e explo ed se e al ypes o c osso e
and mu a ion ope a o s. Finally, eal-coded gene ic algo i hms a e mo e efficien Þnding ule se s han
bina y-coded ones on supe ised lea ning wi h con inuous domains. The ables show how effec i e
HIDER is, pa icula ly, wi h espec o he numbe o ules. The e o a e p o ided by C4.5 is
abou 20% g ea e . Likewise, he numbe o ules p o ided by C4.5 is abou a ac o o ou g ea e
han HIDER p oduces. In addi ion, he numbe o a ibu es in ol es in he ule se is educed oo.
The e o e, HIDER would be conside ed an app oach o g ea quali y.
Acknowledgemen s
The esea ch was suppo ed by he Spanish esea ch agency CICYT unde g an TIC99-0351.