Discovering decision rules from numerical data streams

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