Helde Coelho (Ed.): IBERAMIA'98, LNAI 1484, pp. 326-336, 1998.
 Sp inge -Ve lag Be lin Heidelbe g 1998
Decision Queue Classi ie o Supe ised Lea ning Using
Ro a ed Hype boxes
Jesús Aguila , José Riquelme 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. Uni e sidad de Se illa.
E-mail: {aguila , iquelme, m o o}@lsi.us.es
Keywo ds: da a mining, supe ised lea ning, gene ic algo i hms.
Abs ac . This a icle desc ibes a new sys em o lea ning ules using
o a ed hype boxes as indi iduals o a gene ic algo i hm (GA). Ou
me hod a emp s o ind ou hype boxes a any o ien a ion by
combining de e minis ic hill-climbing wi h GA. S anda d echniques,
such as C4.5, use hype boxes ha a e aligned wi h he coo dina e axes.
The sys em uses he decision queue (DQ) as me hod o ep esen ing he
ule se . I means ha he ob ained ules mus be applied in speci ic o de ,
ha is, an example will be classi y by he i- ule only i i doesn’ sa is y
he condi ion pa o he i-1 p e ious ules. Wi h his policy, he numbe
o ules is less because he ules could be one inside o ano he one. We
ha e es ed ou sys em on eal da a om UCI eposi o y. Mo eo e , we
ha e designed some wo-dimensional a i icial da abases o show
g aphically he expe imen s. The esul s a e summa ized in he las
sec ion.
1 In oduc ion
Supe ised lea ning (SL) is used when he da a samples ha e known ou comes ha
he use wan s o p edic . This ype o lea ning is he mo e common o m because
da a a e usually collec ed wi h some ou come in mind. Human p oblem sol ing is
no mally an exe cise in s udying inpu condi ions o p edic a esul based upon
p e ious expe ience wi h simila si ua ions. SL algo i hms end o emula e ha so o
human beha io .
Decision ees (DT) a e a pa icula ly use ul ool in he con ex o machine lea ning
Decision Queue Classi ie o Supe ised Lea ning Using Ro a ed Hype boxes 327
echniques because hey pe o m classi ica ion by a sequence o simple, easy- o-
unde s and es s whose seman ics is in ui i ely clea o domain expe s. Some
echniques, like C4.5, 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 ies he aining examples [9]. This
class o DTs 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. O he s echniques build oblique decision
ees (ODT), as OC1[7], 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 axes.
A his poin , we mus emembe ha , in a domain wi h N aining examples, each
desc ibed using a k eal- alued a ibu es, he e a e a mos 2kN
k




dis inc k-
dimensional oblique spli s; howe e , o axis-pa allel spli s, he e a e only
N
k×dis inc possibili ies, o ha eason, i could exhaus i ely sea ch he bes spli
a each node.
Anyway, o ind ou he smalles DT (axis-pa allel o oblique) is a NP-ha d p oblem
[2]. 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 [12] in oduced he idea o using hype boxes o clus e o classi y spa ial
da a. Each hype box is iewed as a uzzy clus e , a uzzy se in which all o he
elemen s wi hin he hype box ha e membe ship 1.0 o being in ha se , and elemen s
ou side he hype box can ha e a posi i e membe ship in he se depending on a uzzy
membe ship ule o ha se . Simpson used a de e minis ic p ocedu e o place and
app op ia ely size hype boxes o desc ibe da a. Hype boxes we e c ea ed and sized by
conside ing he da a in an o de ed sequence. A hype box was placed a ound
p elimina y da a. As subsequen da a was added, ei he he p esen hype box was
g own o include he new da a, o a new hype box was added and he p ocess
con inued. This p ocedu e was o limi ed e icacy because i equi ed ial-and-e o
se ing o ope a o pa ame e s and he inal solu ion depended on he o de o
p esen a ion o he da a, e en when he da a possessed only spa ial an no sequen ial
cha ac e is ics. Fogel and Simpson used e olu iona y p og amming o op imize he
posi ion o hype boxes o clus e da a in ligh o a minimum desc ip ion leng h
c i e ion (MDL). Fi s , he expe imen s we e es ic ed o e ol ing hype boxes ha
we e aligned wi h coo dina e axes; and a e wa ds, hey included he capabili y o
o a e he hype boxes. A his poin , i is impo an o no e ha Fogel's me hod y o
sol e he clus e ing p oblem, ha is, unsupe ised lea ning.
Gene ic algo i hms (GA) employ a andomized sea ch me hod o seed a maximally
i hypo hesis [3, 4]. This sea ch is qui e di e en om o he lea ning me hods, like
men ioned abo e. The GA sea ch can mo e much mo e ab up ly, eplacing a pa en
hypo hesis by an o sp ing less likely o all in o he same kind o local minima ha
can happen wi h he o he me hods.
In p e ious wo ks, we p esen ed a sys em o classi y da abases by using hype boxes
(axis-pa allel). This sys em used a GA o sea ch he bes solu ions and p oduced a
hie a chical se o ules. The hie a chy means ha an example will be classi y by he
i- ule i i does no sa is y he condi ions o he i-1 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
328 Jesús Aguila , José Riquelme and Miguel To o
queue, o ha eason we ha e called decision queue (DQ) o he p oduced ule se .
This concep is based on he k-DL, he se o decision lis s wi h conjun i e clauses o
size a mos k a each decision [11]. A decision lis is a lis L o pai s whe e each j is
a e m in n
k
C, each i is a alue in {0,1}, and he las unc ion is he cons an
unc ion ue.
),(),...,,( 11 (1)
A decision lis L de ines a boolean unc ion as ollows: o any assignmen x∈Xn,
L(x) is de ined o be equal o j whe e j is he leas index such ha j(x)=1 (such an
i em always exis s, since he las unc ion is always ue).
DQ is based on DL. Really, DQ is a DL-gene aliza ion because i pe mi s
codi ying unc ions i o con inuous a ibu es and he alues i can belong o any se .
Fu he mo e, DQ does no ha e he las cons an unc ion ue. Howe e , we could
in e p e ha las unc ion as unknown unc ion, ha is, we do no know o which
class he example belongs o. The e o e, i may be ad isable o say "unknown class"
ins ead o aking an e oneous decision.
In he sense men ioned abo e, ou sys em has a measu e, called unknowledge, o
indica e how many es examples ha e no an associa ed class. As he numbe o ules
o he allowed e o a e ( elaxing coe icien ) can be gi en by he domain expe ,
some unnecessa y mis akes could be a oided i he ule se does no assign o he es
example a class. Inc emen ing he elaxing coe icien he unknowledge will be less,
bu he numbe o misclassi ied examples will be highe . The expe , based on
expe imen a ion, mus de e mine such pa ame e .
Fig. 1. Ro a ed e sus axis-pa allel hype boxes.
In his pape , we p opose o hold he p imi i e s uc u e o ou ea ly wo ks [1,10],
bu changing he shapes ha models he sea ch space. Tha is o say, cu en wo k
ex ends hese p e ious e o s by including he capabili y o o a e he hype boxes.
We show in igu e 1 an example, in which o a ed hype boxes can ind ou be e
solu ions han axis-pa allel hype boxes hey do. Decision queue policy is applied in
o de o educe he numbe o ules.
Decision Queue Classi ie o Supe ised Lea ning Using Ro a ed Hype boxes 329
Wi h his DQ-me hod, he e is no p oblem i he egions a e o e lapped. An ex eme
case is p esen ed in he nex igu e.
Fig. 2. Decision queues o o e lapped egions.
In he o he hand, i we use axis-pa allel echniques, he numbe o ules is e y
high. When does i apply one echnique o he o he one? In p inciple, i is no
possible o know i , bu i could be a good solu ion o explo e he sea ch space wi h
axis-pa allel and, inc easingly, o y o o a e he bes solu ions.
Fig. 3. Axis-pa allel solu ion o he igu e 2.
The numbe o ules, in igu e 3, is e y high. The numbe s ep esen s pa s o he
egions ound ou by using o a ed hype boxes, as shows igu e 2.
2 Desc ip ion
2.1 En i onmen
In o de o apply GAs 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 ine an ex e nal unc ion ha assigns
i ness o candida e solu ions. Bo h componen s a e c i ical o he success ul
1
2
34
5
6
1
2
4
5
6
3
330 Jesús Aguila , José Riquelme and Miguel To o
applica ion o he GAs o he p oblem o in e es . In o ma ion o he en i onmen
comes om a da a ile, whe e each example has a class and a numbe o a ibu es.
The GA uses eal codi ica ion; ha is, an indi idual is o med by an n- uple o eal. I
k is he dimension, an indi idual has exac ly 3×k alues: 2×k o he bounda ies
o each dimension; k−1 o he angles o o a ions, in adians, an i-clockwise a ound
he hype box cen e; and 1 o he class. The nex igu e shows a n- uple:
Fig. 4. Rep esen a ion o an indi idual.
whe e li and ui ep esen he lowe and uppe bounds o he indi idual,
espec i ely, o e e y dimension; θi is he o a ion angle; and class. In 2-dimension is
possible o pu an hype box a any o ien a ion by using only one o a ion; in k-
dimension i is necessa y k-1 o a ions.
We conside ha an example belongs o he a ea de e mined o an indi idual i i
sa is ies i s condi ion pa . Thus, le an example be gi en by Pj=(p1, p2, ..., pk, c) hen
i will be in o he de ined egion by he indi idual (o equi alen ly, a ule will be
co e ed by he ule) indh =(l1, u1, l2, u2, ..., lk, uk,
θ
1,
θ
2,...,
θ
k-1, class) i o a ing he
example P=(p1, p2, ... , pk) wi h he angles -
θ
1,-
θ
2,...,-
θ
k-1 wi h ela ion o he cen e o
he hype box de ined by (l1, u1, l2, u2, ... , lk, uk), hen he esul P’ belongs o his
hype box.
Fig. 5. Ro a ion o R he angle θ is equi alen o o a e P he angle -θ a ound he cen e o R.
Fo example, in h ee dimensions he example (p1, p2, p3, c) will be co e ed by he
ule (l1, u1, l2, u2, l3, u3,
θ
1,
θ
2, class) i P’ sa is ies
lpulpulpu
111222333
≤≤∧≤≤∧≤≤''' (2)
whe e P’ is ob ained as ollows:
ll l
12
uu u
12kk
θ
1
θ
θ
2k-1
class
PP’
θ
θ

Decision Queue Classi ie o Supe ised Lea ning Using Ro a ed Hype boxes 331
Le (m1, m2, m3) = ((l1+ u1)/2, (l2+ u2)/2, (l3+ u3)/2) be he cen e o he hype box
de ined by he ule, hen he coo dina es o P’ a e:
3
,
2
,
1
(
100
0
2
cos
2
sen
0
2
sen
2
cos
1
cos
1
sen0
1
sen
1
cos0
001
)
33
,
22
,
11
()
3
',
2
',
1
'( mmmmpmpmpppp +
−
−−−−= 















θθ
θθ
θθ
θθ
(3)
and i will be co ec ly classi y i i s class is equal o c.
2.2 Algo i hm
The algo i hm is a ypical sequen ial co e ing GA [6]. I chooses he bes indi idual
o he e olu iona y p ocess, ans o ming i in o a ule, which is used o elimina e da a
om he aining ile [13]. In his way, he aining ile 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 o
e e y indi idual o he popula ion an example om he aining ile. A e , i is
ob ained an in e al o which he example belongs adding and sub ac ing a andom
quan i y om he alues o he example. Mo eo e , he angles a e andomly
gene a ed be ween ze o and π/2. 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. Fo sol ing i , he sea ch space is
inc eased (ac ually, lowe bound is dec eased 5%, and uppe bound is inc eased 5%).
Fo example in 1-dimension, le a and b be he lowe and uppe bounds o he
a ibu e; hen, he ange o he a ibu e is b-a; now, we andomly choose an example
(x1, class) om he aining ile; las , a possible indi idual o he popula ion could be:
),*,*( 2111 classk angexk angex +− (4)
whe e k1 and k2 a e andom alues belonging o [0,1], and class is he same o ha
o 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 is ob ained om copies o he pa en s,
andomly selec ing i , bu depending on hei i ness alues. 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.
C osso e s a e speci ically designed, choosing a alue among one o he h ee
segmen s o med inside he in e al o he a ibu e by pu ing he wo alues o he
indi idual as c oss poin s. Tha is, o e e y a ibu e, an indi idual has wo alues,
and hen hose alues a e pa i ioning he in e al in h ee segmen s. We selec
andomly a alue inside o a segmen also andomly chooses. The nex igu e shows
he p ocedu e:
332 Jesús Aguila , José Riquelme and Miguel To o
Fig. 6. C osso e ope a o .
One o he h ee ypes o c osso e ope a o could be applied, depending on a
p obabili y. The i s one is mo e conse a i e and second and hi d ones a e mo e
explo a i e. When he c osso e is applied o any angle loca ion, he i s one is
always used.
Mu a ion is applied in wo di e en ways: i he 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 dis ance ac ually is he lowe euclidean
dis ance be ween any wo examples); i he loca ion co esponds o an angle, i is
andomly gene a ed ano he one.
Fu he mo e, i is ad isable o explo e he space wi h he bes indi idual, because
we canno know wha angles a e he bes , and we canno ei he know i an angle is
going o be be e han o he is. In his way, we a e using hill-climbing echnique,
wha could ind ou bes solu ions; despi e o incon eniences said in he in oduc ion.
The me hod consis s o explo ing close o a ed egions wi h he same cen e. The
angles o he explo a ion belongs o he in e al [-π/6,π/6], wi h an inc emen o π/30.
Then, e e y bes ule explo es he sea ch space wi h o he en egions a ound he
same cen e o each a ibu e. Howe e , in o de o each be e i ness alue, he
in e al is also modi ied he same quan i y as mu a ion used.
To imp o e he bes indi idual is a di icul ask. I he i ness alue is be e , hen
he new angle eplaces o he old, and one alue o one a ibu e is modi ied as
men ioned abo e. This me hod allows o a ing an hype box using only one
dimension. To explo e 10 new o ien a ions a he beginning ( he i s gene a ions) can
p oduce he ypical p oblems o he hill-climbing me hods. Fo ha , we ecommend
o use ew explo a ions a he s a and inc ease i owa d he inal. Thus, he las
gene a ions explo e mo e han he i s ones.
We nex show an o e iew o he DQ-Classi ie .
While exis s examples in aining ile
S ep 1. Ini ialize popula ion
S ep 2. Repea num_gene a ions imes
m in m in
(
a
,
b
)
m ax
(
a
,
b
)
max
(1)
(2)
(3)
Decision Queue Classi ie o Supe ised Lea ning Using Ro a ed Hype boxes 333
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 2.6. Imp o e he bes
S ep 3. Pu he bes one in Decision Queue
S ep 4. Elimina e he co e ed ones by he bes one
Fig. 7. O e iew o DQ-Classi ie .
A possible c i e ion o implemen he mu a ion ope a o consis s o dis inguishing
be ween mu a ion o alues and mu a ion o angles, as wo independen ope a o s.
Mu a ion o alues could be a highe p obabili y o applica ion han mu a ion o
angles, and also, o inco po a e o he e alua ion unc ion he dis ance om he
indi idual ( ule) o he close example o he same class. Thus, we can penal y he
o a ed ules wi h w ong angles; ha is, he new indi idual is no going nea o he
close example o he same class.
2.3 Fi ness Func ion
The e olu iona y algo i hm minimizes he i ness unc ion o each indi idual. I is
gi en by
i G(i)*RC<=CE(i) hen CE(i)=0
i
V
T
Gi
CE i
() ()
()
=+
+1
(5)
whe e T is he ca dinali y o he aining ile, V is a new ac o called co e age ( he
ule co e age is he side o a k-dimensional hype cube which olume is equi alen o
he olume o he co e ed k-dimensional egion by he ule); CE(i) is he class e o s,
which a e p oduced when he i example belongs o he egion de ined by he ule, bu
i does no he same class; G(i) is he numbe o goals o he ule; RC is he elaxing
coe icien . E e y ule can quickly expands o inding mo e examples due o V in he
i ness unc ion.
2.4 Relaxing Coe icien
Da abases uses as aining iles ha e no a eas clea ly di e en ia ed, o ha , o
ob ain a ule sys em o ally cohe en in ol es a high numbe o ules. We show in
334 Jesús Aguila , José Riquelme and Miguel To o
p e ious pape [1] a sys em capable o p oducing a ule se exemp om e o a e;
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. When da abases
p esen a dis ibu ion o examples e y ha d o classi y, hen i is ad isable o use a
elaxing coe icien [10]. Many imes, we a e mo e in e es ed in unde s anding he
s uc u e o he da abases han in he e o a e. In his way, i could be be e a sys em
wi h less ca dinali y (despi e some e o s) han oo many ules (wi h 0% o e o a e).
Then, i may be in e es ing o in oduce he elaxing coe icien o unde s anding he
beha io o da abases by dec easing he numbe o ules. RC indica es wha
pe cen age o examples inside o a ule can ha e di e en class o he ule. RC
beha es like he uppe bound o he e o wi h espec o he aining ile, ha is, as an
allowed e o a e.
To deal e icien ly wi h noise and ind 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.
3 Applica ion
3.1 Ex P o eso Da abases
We ha e designed some da abases o a ying complexi y o show g aphically he
expe imen s. These da abases a e shown in he ig. 8. Resul s a e in able 1.
Fig. 8. Ex p o eso da abases named DB1, DB2 and DB3.
3.2 Da abases om UCI Reposi o y
The expe imen s desc ibed in his sec ion a e om UCI Reposi o y [7]. We use i e
c oss alida ion in all ou expe imen s o es ima e classi ica ion accu acy. This c oss
alida ion expe imen consis s o he ollowing s eps: andomly di ide he da a in o