469
ATTRIBUTE SELECTION FOR CLASSIFICATION
Pa icio Se ende o
Dep. o Elec onics & Compu e Science, U. o Alga e,
Campus Gambelas, Fa o, Po ugal
Miguel To o
Dep. o Languages and In . Sys ems, U. o Se ille,
A . Reina Me cedes s/n, Se ille, Spain
ABSTRACT
The selec ion o a ibu es used o cons uc a classi ica ion model is c ucial in machine lea ning, in pa icula wi h
ins ance simila i y me hods. We p esen a new algo i hm o selec and ank a ibu es based on weighing ea u es
acco ding o hei abili y o help class p edic ion. The algo i hm uses he same s uc u e ha holds aining eco ds o
classi ica ion. A ibu e alues and hei classes a e p ojec ed in o a one-dimensional space, o accoun o a ious
deg ees o he ela ionship be ween hem. Wi h he use deciding on he deg ee o his ela ion, any o se e al po en ial
solu ions can be used as c i e ion o de e mine a ibu e ele ance. This low complexi y algo i hm inc eases classi ica ion
p edic i e accu acy and also helps o educe he ea u e dimension p oblem.
KEYWORDS
Da a Mining, classi ica ion, a ibu e selec ion, ele an a ibu es, exclusi e a ibu es
1. INTRODUCTION
Two well-known p oblems a ise when building classi ie s which use decision ee s uc u es and ins ance-
based me hods. Fi s , he inpu o de o a ibu es de e mines hea ily he p edic ing skills o he algo i hm.
Choosing he w ong o de o a ibu es (o ea u es) could mo e apa in he hype space, alues ha
o he wise would be close . Secondly, some a ibu es con ibu e mo e han o he s in building he p edic ion
hypo hesis [Aha, 1994]; a ibu es conside ed i ele an inc ease he compu a ional cos and can mislead
dis ance me ics calcula ions [Indyk, 2000]. This is pa icula ly ue o nea es neighbou algo i hms, which
ind he class o unknown ins ances using he geome ic concep o p oximi y o simila i y buil a ound he
no ion o dis ance be ween poin s in an n-dimensional space. As he posi ion o any ins ance is de ined by he
alue o i s a ibu es, i hese a e no ele an , hen he basic assump ion is iola ed. Based on hese,
a ibu es a e classi ied as ele an o i ele an , in e ms o hei deg ee o con ibu ion o he classi ica ion
model [Koha i e al., 1997; Lebowi z, 1985]1. Fea u e selec ion is used o his eason, and is de ined as he
p ocess o iden i ying and emo ing as much i ele an and edundan in o ma ion as possible wi h he goal
o imp o ing classi ica ion accu acy. Because we use a ee s uc u e o hold ins ances, ou me hod equi es
i s se ing in he inpu o de , a ibu es wi h la ge disc imina o y powe wi h espec o classes, as done in
some ule induc ion algo i hms [Quinlan, 1986; Co e e al., 1997].
The complexi y o ea u e selec ion algo i hms depends on he numbe and quali y o i s a ibu es.
Sea ching ele an a ibu es canno be exhaus i e in many cases. The dimension o da ase s is exponen ial in
he numbe o a ibu es. Hence, e i ying e e y possible combina ion o a ibu es is, in many cases, ou o
he ques ion [Lesh e al., 1998]. Because o his, we de eloped a low compu a ional algo i hm wi h he
ollowing goals: a) Es ablish a c i e ion o de e mine ele an a ibu es. b) Rank a ibu es a p ep ocessing
ime based on his ele ance and c) Reduce he numbe o a ibu es. The o e all goal is o diminish he
1 These au ho s s ill iden i y edundan a ibu es, a si ua ion which we do no add ess he e.
IADIS In e na ional Con e ence e-Socie y 2003
470
algo i hm's complexi y as well as o inc ease o a leas p ese e i s p edic i e skills. Ou esul s show a
s eady imp o emen o ou classi ica ion algo i hm when o de ed ea u es a e used wi h his simple me hod.
2. DEFINITIONS
2.1 Basic de ini ions
No a ion { ∈ R, c ∈ L|" exp( ) • exp1( )} s and o he se o alues o exp1 when and c ake alues in R
and L, and exp is ue. I exp1( ) = hen he exp ession is educed o { ∈ R |" exp( )}.
Le ’s assume he exis ence o a da a se R composed o a ini e se o N eco ds o ype:
= < 1, 2,.., i,.., n, c >, i ∈ Ti, c ∈ L and i( ) = i . (1)
Each eco d is o med by he Ca esian p oduc o a ini e sequen ial se o a ibu es Ai, belonging o se S
ha ing i alues
∈
Ti. Each eco d is associa ed wi h one o m classes c1, c2,..,cm, belonging o se L. Each
a ibu e’s domain is pa i ioned in o a ini e numbe o use -de ined in e als wi hin domain Ti. These
in e als a e ep esen ed by in ege s wi h alues om 1 o si. We assume he exis ence o unc ion o di(),
which con e s an a ibu e alue in o he co esponding in e al alue:
pi = o di( i), i ä Ti . (2)
Using unc ion o di in (2), e e y a ibu e alue i ∈ Ti is con e ed in o a pa e n elemen wi h alue pi..
E e y pi alue will i in o one o si pa i ions belonging o a ibu e Ai. Toge he , all pi elemen s o m a ec o
called pa e n p con aining n elemen alues. We call P he se o all pa e ns p ob ained om R.
p = <p1, p2,.., pi,.., pn>," p ä P," pi Î (1..si) whe e pi = o di( i( )) . (3)
No ice ha he numbe o pa i ions si is no he same o all a ibu es2.
We de ine unc ions pa ( ) and label( ) such ha :
pa ( ) = p and label( ) = c i = < , c>, = < 1, 2,.., n> . (4)
In e e y pa e n p om (3) we ind n sub-pa e ns qi, which co espond o i s p e ix:
qi = <p1, p2,.., pi >, i =(1..n). So p= <qi, u> whe e u is he su ix po ion. (5)
We de ine unc ion eq(p), which e u ns he numbe o eco ds exhibi ing pa e n p:
eq (p) = # { ∈ R | pa ( ) = p} . (6)
Func ion eq can be equally applied o a sub-pa e n qi:
eq (qi) = # { ∈ R | pa ( ) =<qi,, u>} . (7)
We de ine unc ion eq(), which is applied o he k h in e al om a ibu e Ai, gi ing he o al numbe o
eco ds in k. A a ia ion o his unc ion includes es ic ing he numbe o objec s belonging o class c.
2 This is due o changes in he numbe o pa i ions o selec ed a ibu es as we show la e in sec ion 6.
ATTRIBUTE SELECTION FOR CLASSIFICATION
471
eq(Ai, k) = #{ ä R | o di( i
( )) = k }
eq(Ai, k, c) =#{ ä R | o di( i( )) = k
∧
label( ) = c } (8)
Assuming ha pa i ion g anula i y is such ha allows all pa e ns o ha e a gi en label, we de ine
unc ion labels(p), which e u n he se o labels associa ed wi h he subse o eco ds wi h pa e n p.
labels(p) = { ∈ R, c∈ L | pa ( ) = p
∧
label( ) = c • c } . (9)
The numbe o class labels a ached o a gi en pa e n p is:
nlabels(p) = # labels(p) . (10)
Using he Equa ion in (10) we de ine he s eng h o a pa e n as:
s eng h(p) = # { i∈ (1..n) | nlabels(qi) = 1 } (11)
2.2 O he de ini ions
De ini ion 1. A ibu e Ai is said o be semi-exclusi e o pa i ion k, i unc ion semk() is ue. Func ion
semk() is de ined as:
semk(Ai, k, j) =$ c∈ L • (( eq(Ai, k, c) / eq(Ai, k)) ³ j) (12)
Pa ame e
ϕ
is a use -de ined alue ep esen ing he ac ion o eco ds in in e al k wi h class c. The
special case when
ϕ
= 1, is e e ed o as an exclusi e in e al, meaning ha all Ai alues in his in e al
belongs o he same class. A ibu es exhibi ing his ype o alue a e also desc ibed in he li e a u e as
p ima y [Tu ney, 1996], [Koha i e al., 1997].
De ini ion 2. The deg ee o exclusi eness o a pa e n co esponds o he ac ion o pi elemen s wi hin
pa e n p con o ming o he exclusi e alues p ope y. I is calcula ed wi h he ollowing unc ion:
Semp(p, j) = # {i∈ (1..n) | semk(Ai, pi, j)} / n . (13)
De ini ion 3. The deg ee o ele ance o a ibu e i deno ed wi h
δ
i, is he a io be ween he o al numbe
o eco ds in semi-exclusi e pa i ions and N. La ge alues o d mean a mo e ele an a ibu e.
δ
i = # { ∈ R, k ∈ (1..si) | semk(Ai, k, j
∧
o di( i( )) = k • } / N . (14)
The opposi e ep esen s i ele an a ibu es.
De ini ion 4. The shape o a pa e n is de ined as:
21nn-1
shape(p)=(p-p),..,(p-p)
(15)
And he dis ance be ween wo pa e ns is:
d(p, p’) = åi | pi – pi’| (16)
Using equa ions om De ini ion 4 we can de ine he ollowing:
IADIS In e na ional Con e ence e-Socie y 2003
472
De ini ion 5. The shape simila i y unc ion be ween shapes is de ined as:
1212
s (p,p)=d(shape(p), shape(p))
(17)
In Figu e 1 we show semi-exclusi e in e als and he calcula ion o d o wo a ibu es, A1 and A2. An
as e isk means mo e han one class o a gi en pa i ion; i.e. nlabels (pi) > 1.
si 0 1 2 3 4 5 6 7 8 9 o al
δ
eq
77
32 62 49 79 20 12 23 11 43 408
A1
class * * * * * * * * 4 4 54
54/408=0.132
si 0 1 2 3 4 5 6 7 8 9 o al
δ
A2 eq 227 23 35 17
17 14 12 13 5 45 408 112/408=0.274
class
* 2 * * 4 4 * 4 * 4 112
Figu e 1. A ibu e p ojec ion in one-dimensional space o a ibu es A1 and A2.
3. OVERVIEW OF THE CLASSIFICATION ALGORITHM
We ha e p e iously de eloped a classi ica ion algo i hm o supe ised lea ning based on ins ances and he
nea es neighbou pa adigm in [Se ende o e al., 2001]. Classi ica ion is done ex ac ing wo nea es pa e ns
p+ and p- wi h espec o a que y pa e n px. The ex ac ion o p+ is done i s in a ecu si e way. Any sub-
pa e n
i
q
is o he o m
i
q
=<
1
q
i
−
, k>. S a ing wi h i = 1, assuming an emp y sub-pa e n q0+= <> and
knowing elemen qi-1, he p oblem consis in inding he nex sub-pa e n by calcula ing some alue o k+,
which sa is ies he ollowing p ope y:
" kä K(qi-1) • (|k+ - kx| £ |k – kx|) . (18)
The se K(q)is de ined by:
K(q) = { k | <q, k>Î P} (19)
Hence, k+ is he closes elemen o kx among he elemen s in K(qi-1). I wo alues o k+ e i ies Equa ion
(18), hen we chose he one whe e eq(qi+) is a maximum. The algo i hm sea ches nex o pa e n p-. The
sea ch mechanism is he same as o p+, bu wi h se K(q) using his ime pa e n p+ p e iously calcula ed:
K(q) = {k |<q, k> ä P
∧
((nlabels(<q, k>) > 1)
∨
((labels(<q, k>)
∩
labels(qi+)) =
∅
)} (20)
The new pa e n should ha e i s class dis inc om he p+ class.
A inal s ep consis s in applying unc ion me i () o bo h selec ed pa e ns. The pa e n wi h he la ges
me i (p) is he winne . This unc ion ep esen s an agg ega ion o se e al c i e ia, and is de ined as:
()()
ii
i
me i pwp
α=⋅
∑
(21)
E e y c i e ion in
α
i has weigh wi. These c i e ia
α
i (i = 1..6), numbe ed in no pa icula o de a e:
• The deg ee o exclusi eness o a pa e n, calcula ed as
α
1(p) = semp(p) om (13).
• The s eng h o a pa e n, calcula ed om Equa ion (11). So
α
2(p) = s eng h(p).
ATTRIBUTE SELECTION FOR CLASSIFICATION
473
• The simila i y shape om De ini ion 5 and Equa ion (17) applied o a pa e n agains px o
calcula e he mos simila shape:
α
3(p) = s (px, p).
• A numbe ela ed o he dis ance o px, calcula ed as
α
4(p)= d(px, p) om Equa ion (16).
• The equency o a pa e n, whe e a a la ge equency is a be e op ion, o he condi ions being
equal. Func ion equency is calcula ed as
α
5(p)= eq(p) using unc ion in (6).
• Le be mc he majo i y class, he class wi h he la ges equency hen
α
6(p) equals 1 i label(p)
= mc and 0 o he wise.
Weigh s a e ob ained p ep ocessing he aining da ase . The weigh o each c i e ion co esponds o i s
deg ee o accu acy co ec ly classi ying pa e ns. Each c i e ion is es ed indi idually by se ing all o he
weigh s o ze o. The goal is o op imise T, he deg ee o accu acy o each c i e ion. I is calcula ed as:
T = Nº o eco ds co ec ly classi ied / N; and being he e o e = 1 -T (22)
The applica ion o unc ion me i () a unning ime, allows selec ing he bes pa e n. I s class is assigned
o px. A mo e de ailed explana ion o his p ocess is le o a nex a icle.
In he algo i hm implemen a ion all aining pa e ns a e s o ed in o a ie [F edkin, 1960], including
equencies and class in o ma ion a he sub-pa e n le el. These s uc u es ha e p o en o be e y as on
sea ch p oblems [Be gman, 1994;Me e e al., 1996; Albe e al., 2001], which is one o he main p oblems
in he nea neighbou pa adigm. The la ge s o age equi ed by ies is pa ially sol ed keeping he ile on
disk. Also, se e al known comp ess ools a e a ailable o ies such as Pa icia ees [Gonne e al., 1991],
X- ee [Be ch old e al., 1996] and Bu s ies [Heinz e al., 2002].
4. ATTRIBUTE SELECTION
4.1 De e mining mos ele an a ibu es
In gene al, ou me hod anks a ibu es by hei capaci y o p edic ing classes wi hou aking di ec ly in o
conside a ion o he a ibu es om he o iginal sequence. We pos ula e ha his capaci y inc eases, when an
a ibu e exhibi s a la ge deg ee o ele ance as s a ed in De ini ion 3. Fo ins ance, a ibu e Ai is ele an i
some
α
pe cen age o i s ins ances wi h alue j is associa ed wi h class cl. In his sense, we so en he
Boolean de ini ion ound in [Koha i e al., 1997]. Ou objec i e is o ind he mos disc imina i e a ibu es
om he poin o iew o use ulness o he p edic o , wi h he pu pose o imp o ing i s p edic ion accu acy
[Guyon, 2001]. This heu is ic c i e ion has been used success ully be o e [Liu e al., 2000].
A sub-pa e n q o size i can be a common p e ix o dis inc labels, i.e. when nlabels(qi) > 1, ep esen ing
a eas o la ge en opy wi h espec o classes in he da a hype space, no allowing any conclusion on class
membe ship. In e sely, sub-pa e ns whe e nlabels(qi) = 1, ep esen homogeneous egions, whe e smalle
alues o i (sho e sub-pa e ns) ep esen la ge a eas. I a new ins ance o be classi ied alls in o one o
hese a eas, i s chances o co ec classi ica ion inc ease. Mos o i s neighbou s will sha e he same label. Fo
his eason, we a e in e es ed in looking a he en i e da a space om he iewpoin o a ibu es wi h la ge
numbe o examples whe e classes a e “ isible” di ec ly om hem, hus a oiding endless combina ion o
possibili ies as done in adi ional me hods [Koha i e al., 1997; Mille , 1990; B odley e al., 1995]. We
conside hese a ibu es mo e ele an han o he s. Now, he sho es sub-pa e n con ains only one elemen
q1 = <p1, c>, usually associa ed wi h se e al classes. We wan o ind which a ibu es pe o m be e han
o he s in his si ua ion. To do his, all alues o an a ibu e a e p ojec ed in o a one-dimensional space
p e iously pa i ioned in o equal in e al wid hs. In he ie s uc u e used o implemen a ion his
co esponds o build he ee wi h a single le el. This esembles he 1R classi ica ion sys em [Hol e, 1993]
al hough in his sys em he anking o ea u es is based di ec ly on e o a es. In ou case we a e in e es ed in
he o al numbe o sub-pa e ns q1, ound in semi-exclusi e in e als ( om De ini ion 1), o a gi en a ibu e
Ai and
ϕ
alues. A ibu es showing mo e indi idual pa e ns in hese in e als a e also mo e ele an
(De ini ion 4). Based on his, ele ance can be se as a measu e o a ibu e compa ison as explained nex .

IADIS In e na ional Con e ence e-Socie y 2003
474
4.2 Ranking A ibu es by hei ele ance
Ranking a ibu es is done knowing which a ibu es a e compa a i ely mo e ele an han o he s. To do his
we compu e each a ibu e’s ele ance om (14), and ank hem in dec easing o de acco ding wi h he alue
o d, as he example shown in Fig. 1 o A1 whe e d = 0.132. This anking gi es as esul lis ß, which
ep esen s all a ibu es o de ed by hei deg ee o ele ance:
12inii+1
ß = <, ,..,,...,>, | | || i(1.. n).
δδδδδδ≥∈ (23)
A ibu es whe e di = 0, a e o de ly pushed o he lis ’s end. The lis ep esen s he inpu o de o
a ibu es used by he classi ica ion algo i hm. As shown in Sec ion 5 doing his imp o es he p edic i e
accu acy o he classi ica ion algo i hm.
4.3 Reducing he numbe o a ibu es by hei deg ee o ele ance
Reducing he numbe o i ele an a ibu es d as ically educes he unning ime o a lea ning algo i hm and
yields a mo e gene al concep , easie o unde s and by he domain expe . This educ ion can be achie ed
using he concep o a ibu e exclusi eness as de ined in Sec ion 3. This is done by elimina ing om lis ß in
(23) all a ibu es whe e
δ
is small o ze o. This educ ion, hough, canno be done wi hou a cos . The
ade-o is done a he expense o losing some p edic i e accu acy. Wi h his cons ain in mind, ou goal is o
ind a minimum subse o a ibu es S’ such ha when he classi ica ion algo i hm is applied accep ing some
e o e, we can ob ain a new p edic i e accu acy T´ as S’
⊂
S, ha sa is ies T’ £ T + e . The new se S’
ob ained om lis ß in (24) includes only ele an a ibu es disca ding all o he s. The classi ica ion
algo i hm ebuilds he ee using he new sequence in S’. A unning ime, and using some use -use -de ined
e o o e he exis ing p edic ion alue T om (22), a new T’ alue is ob ained. E o e is a unc ion o cos
and quali y [B odley, 1995]. I Equa ion (24) is sa is ied and (T’ – T) £ e, hen S’ is adop ed as he new se o
a ibu es. O he wise, he h eshold alue o should be educed and lis ß ebuil . As a esul his will
inc ease he numbe o a ibu es in subse S’ and hope ully will also inc ease p edic ion accu acy T’
diminishing he alue o e.
5. RESULTS
We ha e es ed hese echniques on se en da ase s om he UCI eposi o y [Mu phy e al., 1994]. All eco ds
wi h unknown a ibu e alues we e elimina ed. Ten– old c oss alida ion was used. Accu acy esul s we e
a e aged.
Table 1. New A ibu e O de using = 0.75
N. º Reco ds Nº Numbe
A ib. Da ase
T aining
Tes
New A ibu e O de
Numbe ep esen s o iginal o dinal numbe
(Bold ace = a ibu e is ele an )
Rele an
A ibu es
(%)
1 24 Hypo hy oid 1598
1063
18,23,21,1,20,22,7,5,13,24,19,17,16,15,14,
12,11,10,9,8,6,4,3 41.7
2 24 De ma ology 218
140
20,22,27,29,6,12,8,25,33,34,24,15,10,31,26,
30,14,23,7,32,28,21,19,18,17,16,13,11,9,5,4, 3,2,1
57.6
3 33 Adul 28468
15060
3,9,14,2,4,5,7,8,13,6,1,10,11,12 71.4
4 13 Diabe es 462
306
5,6,2,7,4,8,3,1 75.0
5 12 Fo es co e 15120
565892
1,10,5,6,4,12,8,7,9,3,11,2 83.3
6 12 Pendigi s 7494
3498
6,12,3,7,11,4,2,15,5,14,16,8,1,10,9,13 87.5
7 16 Cance –W. 407
273
7,2,1,8,3,9,4,6,5 100.0
The a e age dec ease in e o a e a e o de ing a ibu es o 4.3% in Table 2 is simila o esul s epo ed
o di e en da ase s in a p e ious a icle whe e his echnique was applied [Se ende o e al., 2001]. This
ATTRIBUTE SELECTION FOR CLASSIFICATION
475
con i ms ha he gain in p edic i e accu acy is signi ican and s eady when applied o di e en da a domains.
I also con i ms he need o a ibu e o de ing when ee s uc u es and ins ance-based me hods a e
Table 2. Va ia ion in p edic i e e o a e a e o de ing and educ ion in he numbe o a ibu es
Classi ica ion: P edic i e E o Ra e (%) Va ia ion (%) due o:
Nº
Da ase s O iginal (A)
O de ed (B) Reduced(C) O de
(B-A) Reduc ion
(C-B)
1 Fo es co e 28.2 20.5 23.9 -7.7 +3.4
2 De ma ology 10.2 4.5 6.5 -5.7 +2.0
3 Diabe es 27.8 22.2 22.5 -5.6 +0.3
4 Pendigi s 9.3 5.3 2.0 -4.0 -3.3
5 Cance –W. 5.5 2.2 1.8 -3.3 +0.4
6 Adul 18.9 16.0 10.6 -2.9 -5.4
7 Hypo hy oid 1.6 0.7 1.1 -0.9 -0.4
A e age -4.3
used, as is ou case. Al hough no conclusi e due o expe imen size, a ia ion in e o a es a e a ibu e
educ ion (C-B) seems o be ela ed o he in ensi y o a ibu e “p uning” (Table 1). As expec ed, a la ge
educ ion in he numbe o a ibu es esul s in g ea e e o a es. In 43% o cases educing he numbe o
a ibu es inc eases p edic i e accu acy, meaning ha he anking me hod wo ks well. A ibu es a he lis ’s
end a e indeed i ele an o p edic i e pu poses. Accu acy in he emaining da ase s shows a small loss no
g ea e han 3.3% i compa ed wi h a 56% a e age educ ion on he numbe o a ibu es, and hence, in
p oblem complexi y. In he ace o la ge da ase s wi h high dimensions whe e adi ional ea u e educ ion
me hods ep esen e y high compu a ional cos s, his me hod can be a ai solu ion.
Ou ea u e selec ion me hods in eg a ed in o he classi ica ion algo i hm helps o p oduce compe i i e
esul s as shows i s compa ison wi h Quinlan’s landma k ool C4.5 (also known as See5) in Table 3. In
gene al, ou classi ie shows be e pe o mance han C4.5 o da ase s wi h smalle numbe o classes and
wo se when he opposi e is ue. This is explained by he ac ha in o de o speed up he sea ch p ocess, ou
algo i hm only looks o wo close pa e ns accoun ing o only wo classes.
Table 3. Compa ing classi ica ion accu acy agains he popula C4.5
E o in accu acy (%)
Nº Da ase C4.5 Ou s
1
Adul (Census 94,USA)
14.6 10.6 ± 1.2
2 Fo es co e 29.1 20.5 ± 2.5
3 Cance -W 5.8 2.2 ± 0.2
4 Hypo hy oid 0.7 0.7 ± 0.3
5 De ma ology 3.9 4.5 ± 0.3
6 Pima Indian Diabe es 26.8 22.2 ± 1.4
7 Pendigi s 3.4 2.0 ± 0.5
Sou ce o C4.5 esul s: [Chou e al., 2000; Li e al., 2000; Mu phy e al., 1994; Chawla, e al., 2001].
6. DISCUSSION
In his a icle we p esen a simple and low-cos ea u e selec ion me hod, use ul o algo i hms using decision
ees and ins ance-based me hods in supe ised lea ning. Resul s show on a e age a dec ease o o e 4% in
classi ica ion p edic i e e o when a ibu es a e anked by hei deg ee o ele ance. This esul is consis en
wi h p e ious esul s ob ained on di e en da ase s and o e s a simple solu ion o anking ea u es.
Accu acy inc eases e en u he in 43% o cases a e a ibu e educ ion. This no only con i ms he
co ec ness o his simple me hod o anking a ibu es, bu also he ac ha i wo ks as a good il e
indica ion on he p edic i e skills o a ibu es. In he emaining 57% o cases a loss in p edic ion no g ea e
han 3.3% did ep esen elimina ing an a e age o 56% o a ibu es o all da ase s conside ed. This is e y
impo an o help educing algo i hm complexi y in high dimensional da ase s and he e o e he
comp ehension o he domain expe in da a ela ions.
IADIS In e na ional Con e ence e-Socie y 2003
476
Fu u e wo k includes modi ying sligh ly he algo i hm o ex ac as many pa e ns as classes exis in a
da ase wi h he goal o inc easing p edic i e accu acy in da ase s wi h mo e han wo classes. This should
no signi ican ly inc ease sea ch ime i we conside he excellence o ies wi h espec o sea ch
pe o mance.
REFERENCES
Aha, D. W, Banke , R., 1994. Fea u e Selec ion o Case-Based Classi ica ion o Cloud Types: An Empi ical
Compa ison. In Case-Based Reasoning: Wo kshop, Technical Repo WS-94-01, CA, USA., AAI P ess.
Albe , I. E., e al.,, 2001. Fas Re ie al o Mul i and Hype spec al Images Using Rele ance Feedback. P oceedings o
he In e na ional Geoscience and Remo e Sensing Symposium. Vol. 3, pp. 1149-1151.
Ande sson, A, Nilsson, S., 1994. Fas e Sea ching in T ies and Quad ees – An Analysis o Le el Comp ession.
P oceedings. o he Second Eu opean Symposium on Algo i hms, pp 82-93.
Be ch old, S. e al., 1996. The X- ee: An Index S uc u e o High-Dimensional Da a. P oceedings o he 2
nd
In e na ional Con e ence on Ve y La ge Da abases, Bombay, India, pp. 28- 39.
Be man, A.P., 1994. A New Da a S uc u e Fo Fas App oxima e Ma ching. Technical Repo , 1994-03-02, Dep . o
Compu e Science, Uni e si y o Washing on.
B odley, C. E., 1995. Mul i a ia e Decision T ees. Machine Lea ning, Vol. 19(1), pp. 45-77.
Chawla, N. e al., 2001. C ea ing Ensembles o Classi ie s. P oceedings o he 2001 IEEE In e na ional Con e ence on
Da a Mining, CA, USA, pp. 580-81.
Chou, Y., Shapi o, L. G., 2000. A Hie a chical Mul iple Classi ie Lea ning Algo i hm. P oceedings o he In l.
Con e ence on Pa e n Recogni ion, Vol. 2, pp. 152-155.
Co e , T. Ha , P. 1967. Nea es neighbou pa e n classi ica ion. IEEE T ansac ions on In o ma ion Theo y, Vol. 13:1,
pp 21-27.
Doughe y, J., e al., 1995. Supe ised and Unsupe ised Disc e iza ion o Con inuous Fea u es. P oc. o he 12 h
In e na ional Con e ence on Machine Lea ning, Mo gan Kau man Publishe , San Fco. USA., pp. 94-202.
F edkin, E., T ie Memo y, 1960. Communica ions o he ACM, Vol.3: 9, pp. 490-500.
Gonne , G. H., Baeza-Ya es, R., 1991. Handbook o Algo i hms and Da a S uc u es, Addison-Wesley, UK.
Guyon, I., 2001. In oduc ion o he NIPS 2001, Wo kshop on Va iable and Fea u e Selec ion. BC., Canada.
Heinz, S., Zobel, J., 2002. Williams, H.E., Bu s T ies: A Fas , E icien Da a S uc u e o S ing keys. ACM
T ansac ions on In o ma ion Sys ems, 20(2): pp. 192-223.
Hol e, R.C., 1993. Ve y Simple Classi ica ion Rules Pe o m Well on Mos Commonly Used Da ase s. Machine
Lea ning, 11, pp 63-91.
Indyk, P., 2000. Dimensionali y Reduc ion Techniques o P oximi y P oblems. P oc.11 h.ACM-SIAM Symposium on
Disc e e Algo i hms, pp. 371,378.
Koha i, R, John, G., 1997. W appe s o Fea u e Subse Selec ion. A i icial In elligence Jou nal, Special issue on
ele ance, Vol. 97, Nº 1-2, pp. 273-324.
Lebowi z, M., 1985. Ca ego izing Nume ic In o ma ion o Gene aliza ion. Cogni i e Science, (9) pp. 285-308.
Li, J., Dong, G., Ramamohana ao, K., 2000. Ins ance-Based Classi ica ion by Eme ging Pa e ns. P oc.Fou h Eu opean
Con . On P inciples and P ac ice o Knowledge Disco e y in Da abases, Sp inge -Ve lag, pp. 191-200.
Lesh, N., e al., 1998. Mining Fea u es o Sequence Classi ica ion. MERL, Technical Repo : TR98-22.
Liu, B., e al., 2000. Imp o ing an Associa ion Rule Based Classi ie . 4 h Eu opean Con e ence on P inciples and
P ac ice o Knowledge Disco e y in Da abases, Lyon, Sp inge -Ve lag, pp. 504-509.
Me e , T.H. e al., 1996. Da abase S uc u es, Based on T ies, o Tex Spa ial and Gene al Da a. In . Symposium on
Coope a i e Da abase Sys ems o Ad anced Applica ions, Kyo o, pp. 316:324.
Mille , A.J., 1990. Subse Selec ion in Reg ession. Chapman & Hall, New Yo k, USA.
Mu phy, P.M., Aha, D.W., 1994. UCI Reposi o y o machine lea ning da abases.Uni e si y o Cali o nia, I ing,
Depa men o In o ma ion and Compu e Science. Pa ick M. Mu phy (Reposi o y Lib a ian).
Quinlan, J., 1986. Induc ion o Decision T ees. Machine Lea ning, Vol. 1, pp. 81-106.
Se ende o, P., To o, M., 2001. Supe ised Lea ning Using Ins ance-based Pa e ns. P oceedings o he IX Con e encia de
la Asociación Española pa a la In eligencia A i icial, Spain, Vol. I, pp. 83-92.
Tu ney, P.D. 1996. The managemen o con ex -sensi i e ea u es: A e iew o s a egies. 13 h In e na ional Con e ence
on Machine Lea ning (ICML96),Ba i, I aly, July, pp. 60-66.