Disco e ing Decision Rules
om Nume ical Da a S eams ∗
F ancisco Fe e –T oyano
Dep . o Compu e Science
Uni e si y o Se ille, Spain
[email p o ec ed].es
Jesús S. Aguila –Ruiz
Dep . o Compu e Science
Uni e si y o Se ille, Spain
[email p o ec ed].es
José C. Riquelme
Dep . o Compu e Science
Uni e si y o Se ille, Spain
[email p o ec ed].es
ABSTRACT
This pape p esen s a scalable lea ning algo i hm o classi y nu-
me ical, low dimensionali y, high–ca dinali y, ime–changing da a
s eams. Ou app oach, named SCALLOP, p o ides a se o de-
cision ules on demand which imp o es i s simplici y and help ul-
ness o he use . SCALLOP upda es he knowledge model e e y
ime a new example is ead, adding in e es ing ules and emo -
ing ou –o –da e ules. As he model is dynamic, i main ains he
endency o da a. Expe imen al esul s wi h syn he ic da a s eams
show a good pe o mance wi h espec o unning ime, accu acy
and simplici y o he model.
Keywo ds
Decision ules, scalable algo i hms, da a s eams
1. INTRODUCTION
Medicine, me eo ology, ATM ansac ions, e ail chains, o sci-
en i ic p ojec s a e some examples o di e en ields whe e giga-
by es o nume ical da a s eams a e daily gene a ed and mined un-
de he assump ion ha hey hide aluable in o ma ion. P og ess
in ha dwa e s o age and da a–wa ehouse echnologies allow mod-
e n o ganiza ions o collec as amoun s o da a om p op ie a y
and clien case his o ies. The inhe en nons op da a a ic among
he e ogeneous sou ces gi es ise o noise, missing, and inconsis -
ency on a ibu e alues. In addi ion, when da a dis ibu ion is
no s a iona y (examples a e collec ed o e mon hs), algo i hms
based on da a pa i ioning echniques (ins ance/ ea u e sampling)
a e o e sensi i e o bo h unde i ing and o e i ing. Fu he mo e,
memo y and ime limi a ions compel such sys ems o gi e an ap-
p oxima e answe om ew scans (ideally only one) assu ing ha
bo h esul and pe o mance a e no ad e sely a ec ed by he o de
o he examples. Mining po en ially in ini e da a sequences im-
plies high compu a ional cos and usually esul s in la ge, complex
and incomp ehensible knowledge models, so in e ac i e and use –
con olled sys ems a e becoming inc easingly de eloped mo ing
∗The esea ch has been suppo ed by he Spanish Resea ch Agency
CICYT unde g an TIC2001-1143-C03-02.
Pe mission o make digi al o ha d copies o all o pa o his wo k o
pe sonal o class oom use is g an ed wi hou ee p o ided ha copies a e
no made o dis ibu ed o p o i o comme cial ad an age and ha copies
bea his no ice and he ull ci a ion on he i s page. To copy o he wise, o
epublish, o pos on se e s o o edis ibu e o lis s, equi es p io speci ic
pe mission and/o a ee.
SAC’04, Ma ch 14–17, 2004, Nicosia, Cyp us.
Copy igh 2004 ACM 1-58113-812-1/03/04 ...$5.00.
on he use ’s p io i ies o less accu a e bu mo e comp ehensible
answe s. Fo all hese easons, designing new scaling–up and scal-
able lea ning algo i hms has consolida ed as an impo an challenge
in ecen yea s [11].
This pape in oduces a scalable classi ica ion algo i hm named
SCALLOP (Scalable Classi ica ion ALgo i hm by Lea ning deci-
siOn Pa e ns) ha p o ides a model on demand acco ding o se -
e al use –de ined pa ame e s. In he nex sec ions we desc ibe he
mo i a ionand hebasis o ou app oach, discussingi s majo d aw-
backs. Nex we p esen expe imen al esul s on nume ical da a se s
ha show i s pe o mance mining nume ical, low–dimensionali y,
high–speed da a s eams.
2. MOTIVATION
Many scalable lea ning algo i hms a e based on decision ees,
modelling he whole sea ch space hie a chically as disjoin ed hy-
pe cubes. The highly complex ees gi en by hese sys ems cas
doub s on i s capabili ies as sui able knowledge ep esen a ion due
o he use need o explo e pa hs o se e al dozen o le els o know
in e es ing pa e ns. In addi ion, mining ime–changing da as eams
may in ol e o ebuild an ou –o –da e sub– ee, inc easing he com-
pu a ional cos o a g ea e ex en . Wi hin inc emen al lea ning, a
common app oach o ex ac he concep s o be lea ned consis s in
epea edly applying he lea ne o a sliding window o wexamples.
An impo an issue o hese app oaches is o ind he bes alue o
w ha op imizes he pe o mance as a unc ion o he inpu da a
[13].
Ou p oposal ob ains a educed se o upda ed decision ules so -
ed in a ele ance o de acco ding o he use ’s demand. F om
se e al use –de ined pa ame e s, SCALLOP only models he e-
gions whose cha ac e is ics in e es he use , showing isually he
ob ained ules (see Figu e 1). Con a y o decision– ee–based ap-
p oaches, he whole sea ch space is no modelled. Using a window
o size 1, hose examples loca ed inside he mos in luen ial egions
u n in o hype cubes and ex end i s limi s o he nea es di e en la-
bel egions. This app oach makes he model o be ini ially uns able
since some ules could be w ongly expanded, in e sec ing di e en
labelled egions whose examples ha e no been ead ye . To a ain
he s abiliza ion o he model, SCALLOP associa es g ow h limi s
wi h each ule p e en ing hem o be ex ended. Such g ow h limi s
gi e an excellen way o classi y by o ing wi h a educed se o
ules, di e en ly o decision lis s.
3. THE SCALLOP ALGORITHM
Classi ica ion is gene ally de ined as ollows. An inpu ini e
da a se o aining examples is gi en. E e y aining example is
a pai e= (x,y)whe e xis a ec o o ma ibu e alues (each o
which may be nume ic o symbolic) and yis a class disc e e alue
649
2004 ACM Symposium on Applied Compu ing
750-2500
F- a e
0 5000500 3000
10
3
-4·10
3
V- a e
0 10
4
500
5000
20-35
Age
12 5717 42
yea s
g s/week
g s/week
m c d
c md
d mc
G ow h limi s in F- a e (500,3000)De ini ion limi s in F- a e [750,2500]
Rel.Sup.=
20%
Con .=
98.5%
Label:
HEALTHY
Figu e 1: Example o a ule in SCALLOP: A young pe son will
no be heal hy i he/she ea s less han 500 g s. o ege ables pe
week.
named label. The goal is o ob ain a model y= (x) o classi y o
decide he label o new non–labelled es examples named que ies.
SCALLOP builds a model o med by se e al se s o decision ules,
one se pe label. Hence o h, he nex no a ion is used o desc ibe
ou app oach. Le mbe he numbe o con inuous a ibu es. Le
Y={y1,...,yz}be he se o class labels. Le ei= (xi,yi)be he i h
aining example o be ead, whe e xiis a no malized ec o in Rm
and yiis a disc e e alue in Y.
E e y decision ule in SCALLOP is a se o mclosed in e als
[Ijl,Iju](one pe dimension) named de ini ion limi s which de ine
an hype cube inside he sea ch space. ldeno es lowe bound and u
uppe bound.
DEFINITION 1 (EXAMPLE COVERING). Anexampleisco e ed
by a ule when i belongs o he space gi en by i s de ini ion limi s.
DEFINITION 2 (POSITIVE SUPPORT OF A RULE). Thenumbe
o examples wi h label y co e ed by a ule R wi h label y is said
posi i e suppo o R.
DEFINITION 3 (NEGATIVE SUPPORT OF A RULE). The num-
be o examples wi h label y co e ed by a ule R wi h label y0is he
nega i e suppo o R.
DEFINITION 4 (CONFIDENCE OF A RULE). Le psand ns he
posi i e suppo and he nega i e suppo o a ule R, espec i ely.
The con idence o R is de ined as: C(R) = ps
ps+ns.
In o de o achie e a balanced pe o mance be ween he unning
ime and he classi ica ion accu acy, each ule Rhas associa ed ou
ele an elemen s:
•Cen oid C: ec o in Rmgene a ed as he weigh ed mean
o he ec o s belonging o all he examples co e ed by R.
•Delimi e s D: se o he
β
examples co e ed by R ha a e
a hes o each o he .
β
is an use –de ined pa ame e .
•Ma ke s M: se o
β
ep esen a i e examples co e ed by R.
M,D, and Ca e used o modi y an in alid ule.
•G ow h limi s B: se o mopen in e als (Bjl,Bju), so ha :
Bjl ≤Ijl ≤Iju ≤Bju;∀j∈ {1, . . . , m}
The g ow h limi s play an impo an ole since i we know whe e
e e y ulecan beexpanded o, healgo i hm makes s able he model
as e . Fu he mo e, his in o ma ion is e y help ul o classi y new
que ies because he e is no need o hem o be co e ed.
In addi ion, e e y ule keeps i s posi i e suppo and i s nega i e
suppo , he index o he las co e ed example, a boolean alue ha
indica es i he ule was o med om ano he ule ins ead o an
example, and a se o links o he ules wi h which o e lap. Only
ules associa ed wi h he same label may o e lap.
Mo eo e , he ules a e kep o emo ed acco ding o se e al
use –de ined pa ame e s: he maximum numbe o ules pe label
(
α
), he upda e a e, he minimum posi i e suppo , and he min-
imum con idence.
The algo i hm s a s wi h
α
ules pe label gene a ed om he
i s
α
ead examples o each label. These ules a e no hype cubes
bu poin s. When he e ha e been ead mo e han
α
examples o
a ce ain label yi, h ee di e en si ua ions a e di e en ia ed wi h
e e y new example ei= (xi,yi):
•Posi i e co e ing:xiis co e ed by one o se e al ules asso-
cia ed wi h he same label yi.
•Possible expansion:xiis no co e ed by any ule in he
model bu he e is a leas one ule associa e wi h he same la-
bel ha can be ex ended o co e i wi hou o e lapping wi h
a di e en labelled ule.
•Nega i e co e ing:xiis co e ed by one o se e al ules as-
socia ed wi h a di e en label y06=yi.
Cases 1 and 3 ake u ns o be i s ly checked. I none o hem
come ue, hen he ac ions associa ed wi h he case 2 a e un.
A e each p uning (e e y
γ
ead examples), SCALLOP coun s how
many imes he cases 1 and 3 come ue. Fo he nex
γ
examples
SCALLOP will check i s ly ha case wi h he highes coun ac-
co ding o he p eceding
γ
examples.
In he wo i s cases SCALLOP upda es he delimi e s and he
ma ke s o he in ol ed ules when hey ha e co e ed
β
new ex-
amples (Figu e 2). Le Ebe he se o he
β
la es examples co e ed
by a ule so ha X=D∪M∪E. The i s delimi e selec ed d1 is
he mos dis an poin d1∈X o he cen oid (C) o he ule. The
i s ma ke selec ed m1 is he nea es poin o he middle poin o
d1 and C. The emaining delimi e s a e selec ed om Xacco ding
o he g ea es Euclidean dis ance om he cen oid o new delim-
i e s: he second delimi e d2 is he mos dis an poin o d1 (c0),
he hi d delimi e d3 is he mos dis an poin o he cen oid o
d1 and d2 (c00), he ou h delimi e d4 is he mos dis an poin o
he cen oid o d1, d2 and d3, and so on. The ma ke s a e upda ed
wi h he same c i e ion o m1. The second ma ke m2 is he nea es
poin o he middle poin o d2 and C. The hi d ma ke m3 is he
nea es poin o he middle poin o d3 and C, and so on.
Posi i e co e ing: e e y ule ha co e s xiinc eases i s posi i e
suppo by one uni , upda es he index o he las co e ed example
and mo es i s cen oid. When he i s ule Rp ha co e s he new
example is ound, he o he ules ha may also co e i a e ound
hanks o he links o Rp o hem.
Possible expansion: a ule Rgcan be expanded o seize he poin
xii i ul ills wo condi ions:
•xiis no beyond he g ow h–bounds o Rg, ha is: ∀j∈
{1,...,m}· xij ∈(Bjl,Bju)
•The esul ing ex ended ule does no in e sec wi h any o he
ule associa ed wi h a label di e en om ha o Rg.
Only one ule ou o all he candida e ones is expanded: he one
whose g ow h is he smalles and now co e s xi.
650
I
x
C
x
x
x
x
x
x
x
x
x
x
x
d
1
C
x
x
x
x
x
x
x
x
x
x
m
1
·
II
d
1
(c')
x
x
x
d
2
m
2
x
x
x
x
x
m
1
·
C
III
d
1
x
d
3
x
d
2
m
2
x
x
x
x
m
3
m
1
c''
C
·
IV
d
1
x
d
3
x
d
2
m
2
d
4
m
4
x
x
m
3
m
1
c'''
·
C
V
Figu e 2: Upda ing he delimi e s (di) and he ma ke s (mi) o a ule wi h
β
=4.
DEFINITION 5 (GROWTH OF A RULE). Le R be a ule in Rm.
Le x be a poin in Rm. The g ow h G o he ule R o co e he poin
xiis de ined as:
G(R,xi) =
m
∏
j=1,gj>010
φ
gj−
m
∏
j=1, j>010
φ
j;
gj=uj−lj;uj=max(xij,R.Iju);
lj=min(xij,R.Ijl); j=R.Iju −R.Ijl;
φ
∈N
In o de o measu e only he new egion ha is aken when a
ule Rex ends, he g ow h akes in o accoun only hose dimen-
sions o which he e is expansion. Since SCALLOP no malizes
each a ibu e alue in [0,1] be o e p ocessing an example, he e m
10
φ
is used o a oid ha a ule wi hou expansion in a ce ain di-
mension k(Ikl =Iku) has g ea e g ow h han a ule wi h expansion
in such a dimension and he same in e als in he es o dimen-
sions. Fo example, conside wo ules in R2,Raand Rb, which
can be ex ended o co e a new poin x={0.5,0.5}, so ha : Ra.I=
{[0.1,0.4];[0.5,0.5]}(a segmen ) and Rb.I={[0.1,0.4];[0.6,0.7]}
(a ec angle). Wi hou he e m 10
φ
, i esul s in: G(Ra,x) = 0.4−
0.3; G(Rb,x) = 0.4·0.2−0.3·0.1. Tha is, con a y o expec ed,
Rag ows mo e han Rb. We ha e used
φ
=3 in ou expe imen s.
When a ule Rgex ends, i may o e lap wi h o he ules asso-
cia ed wi h he same label yiso ha SCALLOP upda es he se o
links o each ule in bo h di ec ions.
Nega i e co e ing: when xiis co e ed by a ule associa ed wi h
a di e en label y0, he co e ing ule Rnwi h he nea es cen oid o
xiis ounded as in he i s case. I he new con idence o Rnis s ill
g ea e han o equal o he minimum gi en by he use , hen he
nega i e suppo is inc eased by one uni . I he new con idence is
smalle han he minimum gi en by he use , hen a new ule Rx o
xiis added o he model. In addi ion, Rnis spli in o wo new ules
R0
n ha do no co e xi. Each new ule may be pa ially o o ally
co e ed by a p e ious ule (which mus be linked h ough Rn). I
R0
nis o ally co e ed by o he ule Rc, hen i is no included in he
model. I R0
no e laps wi h Rc, hen bo h ules upda e o each o he
he se o links. Be o e adding hem o he model, he g ow h limi s
o each new ule a e upda ed wi h he g ow h limi s o Rn.
Al hough he new example ximay be co e ed by se e al ules
associa ed wi h a di e en label, only he ule whose cen oid is he
nea es o xiis spli . We ha e decided on his c i e ion unde he
assump ion ha i he example xibelongs o a pa e n, hen nea
examples associa ed wi h he same label yimus be ead sho ly
a e , and w ong ules will be co ec ed. I xiis a noisy example o
belongs o a mino i y pa e n, hen Rxwill be emo ed in he nex
p uning. So e e y ime a noisy example xis ead, di iding only
one ule ins ead o all he ules ha co e xa oids an unnecessa y
compu a ional cos .
3.1 Re ining he model
The se o ules is e ined e e y
γ
new examples.
γ
is an use –
de ined pa ame e . Fi s , an i e a i e p ocedu e is un o join ules
associa ed wi h he same label. When no union is possible he
p ocedu e ends. In e e y i e a ion, he wo nea es ules o each
o he whose union is possible a e analyzed. The wo nea es ules
a e hose whose esul ing olume is he smalles in ela ion o he
olume o he es o he possible unions. The union Ru om wo
ules Raand Rbo he same label is done i wo condi ions a e
ul illed: 1) Rudoes no in e sec wi h any ule associa ed wi h a
di e en label; 2) he esul ing hype cube is loca ed inside he hy-
pe cube ob ained om he g ow h bounds o Raand Rb.
In a second s ep e e y ule has o sa is y wo condi ions o s ay in
he model: 1) mus co e a leas one o he las
δ
ead examples; 2)
he posi i e suppo mus be g ea e han o equal o he minimum
gi en by he use (as pe cen age o he o al numbe o examples
ead a ha ime).
δ
is ano he use pa ame e . I noise is p esen in
da a, hose w ong ules ha s em om noise a e likely o ha e a low
suppo and a a iable upda e a e. I a e his p une he numbe
no ules is s ill g ea e han
α
, hen hey a e so ed by bo h he
posi i e suppo and he index o he las co e ed example, in a
dec easing o de , so ha he las n−
α
ules a e di ec ly emo ed.
The ules ha s ay in he model ese he nega i e suppo .
Be o e emo ing a ule R , some ules associa ed wi h a di e en
label may upda e hei g ow h bounds. I R was ex ended wi h one
o he las
δ
ead examples and was no spli e e , hen SCALLOP
akes i as a alid mino i y ule (no noise). The e o e, he ules
o di e en label ha will emain in he model should no ex end
ac oss he egion gi en by he de ini ion limi s o R (Figu e 4). To
a oid w ong expansions ha may in ol e a spli ing sho ly a e ,
SCALLOP upda es he g ow h bounds o e e y di e en labelled
ule Rs ha o e laps wi h R in all dimensions excep one j, so
ha :
i R .Ijl >Rs.Iju hen Rs.Bju ←min(Rs.Bju,R .Ijl)
i R .Iju <Rs.Ijl hen Rs.Bjl ←max(Rs.Bjl,R .Iju)
3.2 Classi ying new que ies by o ing
I a new que y Qis co e ed by a ule Rq, hen Qis di ec ly
classi ied as he label associa ed wi h Rq. I he e is no ule ha
co e s he new que y, SCALLOP ies o in e which labels a e no
possible o Qand i is classi ied by o ing. Figu e 3 shows his
p ocedu e. I he que y is beyond he g ow h bounds o all he ules
associa ed wi h a ce ain label l, hen lis ejec ed o classi y Q. I
Qis beyond he g ow h bounds o a ule Rywi h label y, hen he
o es agains ya e inc eased by one uni . I a ule R o label can
be ex ended o co e Q(i is inside he g ow h bounds o R and
he esul ing expansion does no in e sec wi h any ule associa ed
wi h a label di e en o y), hen he o es o a e inc eased by one
uni . Thus, he label assigned is ha wi h he highes numbe o
651
Algo i hm 1 classi yTes
Inpu : Q: Vec o in Rm;
Ou pu : label: Disc e e;
begin
i he e is a ule Rq ha co e s Q hen
label ← he label associa ed wi h Rq
else
o all label yk∈Ydo {Y={y1,...,yz}}
alidLabel[k] ← alse
o all ule Rassocia ed wi h he label ykdo
i Qis beyond he g ow h limi s o R hen
o esAgains [k] ← o esAgains [k] + 1
else
i Rcan ex end o co e Q hen
alidLabel[k] ← ue
o esFo [k] ← o esFo [k] + 1
end i
end i
end o
end o
label ←decide( alidLabel, o esFo , o esAgains , ecei ed)
end i
end
Figu e 3: Algo i hm o classi y new es examples.
o es. When wo labels ha e he same numbe o o es, he label
dis ibu ion ( ecei ed) decides which is he class alue o he new
que y.
4. EMPIRICAL EVALUATION
We ha e un all ou expe imen s on an AMD x86/1.4Ghz and
256MbDDR RAMPC unning WindowsXP. SCALLOPha e been
es ed o 15 con inuous a ibu es using a me hod simila o [4].
The concep s o be lea ned a e c ea ed by andomly gene a ion o
decision ees wi h 8 le els (128 concep s o be lea ned). Each lea
is andomly assigned a class label be ween only wo possible al-
ues, 0/1. The ee was g own in each in e nal node wi h a andom
pai (a ibu e, alue) ha is consis en wi h he pa h om he oo
o such a node. Fo e e y example o he aining s eam, he 15
a ibu e alues a e gene a ed wi h a simple uni o m numbe gen-
e a o as a s eam o pseudo– andom numbe s in he eal in e al
[0,1]. The class label associa ed wi h each aining example is hen
assigned acco ding o he a ge ee. As in [4], we ca ied ou all
es s wi hou e e w i ing he aining examples o disk (i.e., gen-
e a ing hem on he ly and passing hem di ec ly o he algo i hm).
We ha e e alua ed h ee aspec s o he pe o mance gi en by
SCALLOP: he p edic ion accu acy, he s abiliza ion speed, and
he unning ime. They ha e been measu ed o di e en sizes o
he aining s eam. We ha e added a class label noise le el o 1%
so ha e e y 100 examples, one o hem was passed wi h a andom
label. Fo each aining se , 10% o examples we e used o es -
ing. We ha e ca ied ou en e alua ions o each aining and en
aining o each size. The alues used o he pa ame e s o he
algo i hm we e:
α
=100,
β
=3,
γ
=104,
δ
=2·104, minimum
con idence 90% and minimum posi i e suppo 0.01%.
Table 1 shows he esul s ob ained wi h espec o he accu acy
and he s abili y gi en by SCALLOP. The las ow shows he es-
ul s o a changing– ee, so ha e e y hund ed housand examples
he a ge ee was eplaced making SCALLOP o ejec he gene -
a ed ules. F om 1 million examples, he ee was s a iona y. The
accu acy becomes s able om one million examples like he num-
Table 1: Pe o mance gi en by SCALLOP lea ning 128 con-
cep s o 15 con inuous dimensions. NE is he numbe o ex-
amples; CA is he classi ica ion accu acy; TC is he pe cen age
o es examples co e ed by he ulese ; AC is he accu acy ob-
ained by di ec co e ing; NR is he inal numbe o ules; NS
is he o al numbe o ules spli du ing he p ocess; and RP is
he numbe o new ules gene a ed be o e
α
examples o each
label a e ead.
NE %CA %TC %AC NR NS RP
5·10466.0±0.70 29.3 28.8 190 780 480
1·10574.0±0.40 45.5 45.4 185 1400 1000
2·10584.0±0.17 64.5 64.4 185 2150 2050
3·10591.5±0.15 73.6 73.5 185 2550 3080
4·10593.0±0.11 81.8 81.7 185 3150 4180
5·10594.0±0.11 84.9 84.9 185 3225 5380
1·10695.3±0.02 90.4 90.4 170 3330 12370
5·10695.8±0.02 90.3 90.3 137 4000 72200
Table 2: Running ime o build he model and classi y 10% es
examples. NE is he numbe o examples; TL is he ime needed
o buil he model (in seconds); TC is he ime o classi y he es
examples (in seconds); and %UE is he pe cen age o examples
ha a e no used o upda e he model.
NE TL TC %UE
5·10465 0.4 42
1·105115 0.6 33
2·105165 1.0 24
3·105210 1.3 18
4·105250 1.6 16
5·105290 1.6 15
1·106340 2.2 6
5·106925 10.8 1
be o co e ed examples. I is impo an he high pe cen age o es
examples co ec ly classi ied wi hou di ec co e o 5·104 es s
(mo e han 37% o co ec ly classi ied) and o 105(abou 30%).
The numbe o spli ules does no inc ease unde a linea end bu
om one million examples ends o be asymp o ic bounded. F om
i e million examples, he numbe o inal ules is e y nea o he
numbe o concep s o be lea ned.
Table 2 shows he esul s ob ained in unning ime (seconds).
Column TL shows ha he unning ime o upda e he model is p o-
po ionally dec easing as he numbe o examples inc eases, so ha
he sys em’s s abili y inc eases as he numbe o examples. Column
UE shows ha he quali y o he ules is inc easingly nea e o he
eal concep s o be ex ac ed. These esul s lead us o hink ha
SCALLOP is a good choice o mine majo pa e ns om con inu-
ous da a s eams.
When he numbe o examples is o e a million, SCALLOP is
able o p ocess abou 5000 examples pe second, wha gi es an
idea o he good pe o mance o ou app oach.
5. RELATED WORK
The e is a huge li e a u e on inc emen al lea ning and ule lea n-
ing [3, 13, 5]. Decision ee based classi ie s o mining e y la ge
da abasesa e Geh kee al.’s BOAT [6] and Ag awale al.’s SPRINT
[12]. BOAT ob ains an app oxima e ee h ough a sample o ixed
size. P e ious app oaches based on subsampling me hods a e also
p oposed byCa le [2]. In con as , SPRINT isa disk–basedlea ne
652
R1-A
R2-A
R3-B
x (j=1)
y (j=2)
z (j=3)
Figu e 4: Upda ing he g ow h bounds o a ule in R3. The
ules R2and R3o e lap in wo dimensions (x,z), whe eas R1
and R3o e lap only in one dimension. R2.B3uis upda ed wi h
R3.I3land R3.B3lis upda ed wi h R2.I3u(=R2.I3l=0), espec -
i ely. R1.Bis no changed.
ha use all he examples and ocus on op imizing sequen ial access
o disk.
Recen wo ks on mining da a s eams has been in oduced by
Domingos e al. in [4] (VFDT) and [9] (CVFDT), building a de-
cision ee using cons an ime and memo y pe example. Thei
app oach is based on Hoe ding bounds [8], which gua an ee ha
he ou pu is asymp o ically nea ly iden ical o ha gi en by a ba ch
con en ionallea ne om enough examples. They alsoapply Hoe -
ding’s inequali ies o build a scaling–up me hod ha is applicable
o any induc ion algo i hm based on disc e e sea ch [10]. The e is
also la ge li e a u e on scaling–up algo i hms [7, 1].
6. CONCLUSIONS
A scalable classi ica ion lea ning algo i hm based on decision
ules and p o o ypes has been in oduced in his pape . P o iding
a model on demand, which imp o es i s simplici y and help ulness
o he use , we ha e de eloped a sys em o mining nume ical,
low–dimensionali y, high–speed, ime–changing da a s eams ha
upda es he model wi h each new example. Wi h a e ining me hod
as pa o he algo i hm, SCALLOP is able o emo e ou –o –da e
ules ha ha e become unin e es ing o he use and w ong ules
caused by noise. This pe iodical p uning does no ad e sely a ec
he compu a ional cos bu a he speeds up i s subsequen upda ing
by helping o make he model mo e s able.
The s ong poin o ou algo i hm is ha he gene a ed ules know
whe e can ex end o, wha p o ides ew ules o classi y new que -
ies wi hou dec easing he accu acy. This app oach is di e en o
decision ee based algo i hms in ha he whole sea ch space is no
modelled and he new que ies a e classi ied by o ing. The pe -
o mance o SCALLOP is excellen , as o p edic ion accu acy as
unning ime.
7. FUTURE WORK
Ou u u e esea ch di ec ions a e o ien ed o d op i ele an di-
mensions, and eco e d oppeda ibu es u ned ele an la e ( he e
is no much li e a u e on ea u e selec ion om da a s eams). We
a e also s udying o deal wi h nominal a ibu es in o de o be able
o compa e SCALLOP wi h ano he classi ica ion algo i hms, as
CVFDT [9] and SPRINT [12].
8. REFERENCES
[1] P.S. B adley, U.M. Fayyad, and C. Reina. Scaling clus e ing
algo i hms o la ge da abase. Knowledge Disco e y and Da a
Mining, pages 9–15, 1998.
[2] J. Ca le . Megainduc ion: machine lea ning on e y la ge
da abases. PhD hesis, Basse Depa men o Compu e
Science, Uni e si y o Sydney, Aus alia, 1991.
[3] W.W. Cohen. Fas e ec i e ule induc ion. In A mand
P iedi is and S ua Russell, edi o s, P oc. o he 12 h
In e na ional Con e ence on Machine Lea ning, pages
115–123, Tahoe Ci y, CA, July 9–12, 1995. Mo gan
Kau mann.
[4] P. Domingos and G. Hul en. Mining high-speed da a s eams.
In P oc. 6 h ACM SIGKDD In e na ional Con . on
Knowledge Disco e y and Da a Mining, pages 71–80,
Bos on, MA, 2000.
[5] V. Gan i, J. Geh ke, and R. Ramak ishnan. DEMON: Mining
and moni o ing e ol ing da a. Knowledge and Da a
Enginee ing, 13(1):50–63, 2001.
[6] J. Geh ke, V. Gan i, R. Ramak ishnan, and W.Y. Loh. BOAT
– op imis ic decision ee cons uc ion. In ACM SIGMOD
Con e ence, pages 169–180, Philadelphia, Pennsyl ania,
1999.
[7] J. Geh ke, R. Ramak ishnan, and V. Gan i. Rain o es – a
amewo k o as decision ee cons uc ion o la ge
da ase s. In P oc. 24 h In . Con . Ve y La ge Da a Bases,
VLDB, pages 416–427 , 1998.
[8] W. Hoe ding. P obabili ies inequali ies o sums o bounded
andom a iables. Jou nal o Ame ican S a is ical
Associa ion, 58:13–30, 1963.
[9] G. Hul en, L. Spence , and P. Domingos. Mining
ime-changing da a s eams. In P oc. 7 h ACM SIGKDD
In e na ional Con . on Knowledge Disco e y and Da a
Mining, pages 97–106, San F ancisco, CA, 2001. ACM
P ess.
[10] G. Hul en, L. Spence , and P. Domingos. Mining complex
models om a bi a ily la ge da abases in cons an ime. In
P oc. 8 h ACM SIGKDD In e na ional Con . on Knowledge
Disco e y and Da a Mining, Edmon on, Albe a, Canada,
2002. ACM P ess.
[11] F. P o os and V. Kollu i. A su ey o me hods o scaling up
induc i e algo i hms. Da a Mining and Knowledge
Disco e y, 3(2):131–169, 1999.
[12] J.C. Sha e , R. Ag awal, and M. Meh a. SPRINT: A scalable
pa allel classi ie o da a mining. In P oc. 22 h In e na ional
Con . Ve y La ge Da abases, VLDB, pages 544–555, 1996.
[13] G. Widme and M. Kuba . Lea ning in he p esence o
concep d i and hidden con ex s. Machine Lea ning,
23(1):69–101, 1996.
653