Mining Low Dimensionality Data Streams of Continuous Attributes

Mining Low Dimensionality Data Streams of Continuous Attributes Francisco J. Ferrer-Troyano, Jes´us S. Aguilar-Ruiz, and Jos´e C. Riquelme Department of Computer Science, University of Seville Avenida Reina Mercedes s/n, 41012 Seville, Spain {ferrer, aguilar, riquelme}@lsi.us.es Abstract. This paper presents an incremental and scalable learning algorithm in order to mine numeric, low dimensionality, high–cardinality, time–changing data streams. Within the Supervised Learning field, our approach, named SCALLOP, provides a set of decision rules whose size is very near to the number of concepts to be extracted. Experimental results with synthetic databases of different complexity degrees show a good performance from streams of data received at a rapid rate, whose label distribution may not be stationary in time. Keywords: Classification, decision rules, incremental learning, scalable learning algorithms, data streams. 1 Introduction In recent years, designing scaling–up and scalable algorithms has consolidated as an important challenge within data mining research community. Memory and time limitations compel make such system to give an approximate answer from few scans (ideally only one) assuring that both result and performance are not adversely affected by the order of the examples. In addition, when the distribution is not stationary (records are collected over months), algorithms based on data partitioning techniques (instance/feature sampling) are oversensitive to both underfitting and overfitting. Many scalable learning algorithms are based on decision trees, modelling the whole search space hierarchically as disjointed hypercubes. The large and complex trees given by these systems cast doubts on its capabilities as suitable knowledge representation due to the user need to explore paths of several dozen of levels to know interesting patterns. In addition, mining time–changing data streams may involve to check an out–of–date sub– tree, increasing the computational cost. A common approach in these systems consists in repeatedly applying the learner to a sliding window of wexamples. The main goal in these systems is then to find the value for wthat optimizes the performance as a function of the input data. So interactive and user–controlled data mining systems are becoming increasingly developed. Such approaches trade accuracy for simplicity providing more meaningful and understandable models. This paper introduces a scalable classification algorithm named SCALLOP (SCALabLe classification algorithm tO learning Patterns) that provides a model Fernando Moura Pires, Salvador Abreu (Eds.): EPIA 2003, LNAI 2902, pp. 264–278, 2003. c Springer-Verlag Berlin Heidelberg 2003 Mining Low Dimensionality Data Streams of Continuous Attributes 265 on demand from several user–defined parameters. Using a window of size 1, our approach obtains hypercubic decision rules sorted in a relevance order according to the regions whose characteristics interest the user. In the next sections we describe our approach and discuss its major drawbacks. Next we present experimental results on synthetic data of different degrees of complexity which show its usefulness and effectiveness to mine numerical, low–dimensionality, high–speed, time–changing data steams. 2 Related Work There has been many recent works on mining very large databases and data streams. Domingos and Hulten introduce VFDT [7] and CVFDT [14] which build a decision tree using constant time and memory per example. Their approach is based on Hoeffding bounds, which guarantee that the output is asymptotically nearly identical to that given by a batch conventional learner from enough examples. They also apply Hoeffding’s inequalities to build a scaling–up method that is applicable to any induction algorithm based on discrete search [15]. Decision tree based classifiers are also Gehrke et al.’s BOAT [10] and Agrawal et al.’s SPRINT [20]. BOAT obtains an approximate tree through a subsample of fixed size. Previous approaches based on subsampling methods are also proposed by Catlett [4]. In contrast, SPRINT [20] is disk–based learner that use all the examples and focus on optimizing sequential access to disk. Garofalakis et al. [17,9] propose several algorithms for building decision trees under size and accuracy constraints in order to give an meaningful model for the user. Dobra and Gehrke’s SECRET [6] is a regression tree based algorithm providing a more easy to interpret output than that given by decision trees. SECRET uses EM clustering algorithm for Gaussian mixtures to generate leaves as linear transformation from found close clusters. There is also large literature on scaling–up algorithms [19,11,3], model maintenance [8,16,5,2], and scalable clustering algorithms [18,12,13,21]. 3 The SCALLOP Algorithm Classification is generally defined as follows. An input finite data set of training examples is given. Every training example is a pair e=(x, y) where xis a vector of mattribute values (each of which may be numeric or symbolic) and yis a class discrete value named label. The goal is to obtain a model y=f(x)to classify or decide the label for new non–labelled test examples named queries. Henceforth, the next notation is used to describe our approach. Let mbe the number of continuous attributes. Let Y={y1,...,y z}be the set of class labels. Let ei=(xi,y i)betheith training example to be read, where xiis a normalized vector in Rmand yiis a discrete value in Y. SCALLOP builds a model formed by zsets of decision rules, one set per label. 266 F.J. Ferrer-Troyano, J.S. Aguilar-Ruiz, and J.C. Riquelme In order to achieve a balanced performance between the running time and the classification accuracy, each rule Ris a data structure that comprises twelve elements: –Definition limits I: set of mclosed intervals [Ijl,I ju], one per numerical attribute (j∈{1,...,m}). ldenotes lower bound and uupper bound. –Centroid C: vector in Rmgenerated as weighted mean from the examples covered by R. –Central vector N: vector of the nearest example to Cfrom all those examples covered by R. –Delimiters D: set of the most distant βvector to each other from all examples covered by R.βis an user–defined parameter. –Markers M: set of the nearest βexamples to Nthat have been covered by R.M,D, and Care used to modify a wrong rule. –Overlapping rules O: set of links that reference others rules with which R shares a sub–region belonging to the region defined by I. Only rules belonging to the same set can make non-empty intersections among themselves. –Growth limits B: set of mopen intervals (Bjl,B ju) (one per numerical attribute) so that: Bjl <I jl ≤Iju <B ju;∀j∈[1,m]. These limits play an important role since by knowing where a rule can extend to, the algorithm makes stable the model faster. Furthermore, this information is very helpful to classify new queries with few rules by voting. –sis the support or number of examples covered by Rwhich are associated with the same label. –dis the number of different labelled examples covered by R. The maximum value of dis computed as a function of sand the user parameter γ, so that: s−d s≥γ. –fis a boolean value that indicates if Rwas split ever. –ris the index of the last example covered by R. –uis a boolean value that indicates if Rwas extended with some of the last δread records. δis an user parameter. In addition, the search space is modelled according to five user–defined parameters: the maximum number of rules per label α, the minimum support λ, the minimum confidence γ, the minimum update frequency µ, and the pruning frequency δ. Every δread examples, if the number of rules for a label is greater than αthen SCALLOP attempts to simplify the model by joining similar rules and by removing uninteresting rules: those ones with a support smaller than λ per cent of the number of read examples and those ones that were not updated with the latest µread examples. The algorithm starts with αrules per label generated from the first αread examples of each label. These rules are not hypercubes but points. We name these rules point–rules. When there have been read more than αexamples for a certain label yi, three situations are differentiated with every new example ei=(xi,y i): –Correct covering:xiis covered by one or several rules associated with the same label yi. Mining Low Dimensionality Data Streams of Continuous Attributes 267 Fig. 1. Three cases are differentiated by updating the model with a new example. The label distribution is stored for using it in the classification phase, if necessary. –Possible expansion:xiis not covered by any rule in the model but there is at least one rule associate with the same label that can be extended to cover it without overlapping with a different labelled rule. –Possible split:xiis covered by one or several rules associated with a different label y=yi. Cases 1 and 3 take turns to be firstly checked. If none of them come true, then the actions associated with the case 2 are run. After each pruning (every δread examples), SCALLOP counts how many times the cases 1 and 3 come true. For the next δexamples SCALLOP will check firstly that case with the highest count according to the preceding δread examples. Correct covering: every rule that covers xiincreases its positive support by one unit, updates the index of the last covered example and moves its centroid (procedure checkCover in Figure 1). When the first rule Rcthat covers the new example is found, the other rules that may also cover it are found thanks to the links of Rcto them (Rc.O). All the rules that also cover xiare updated with the same three operations. One rule out of Rcand those linked by Rc.O, the rule Rnwhose centroid Rn.C is the nearest to xi, may be updated with respect to Rn.M and Rn.N. If xiis nearer to Rn.C than Rn.N, then xireplaces Rn.N, and Rn.N is checkedtobeinRn.M. If the size of Rn.M is smaller than β, then xi(or the 268 F.J. Ferrer-Troyano, J.S. Aguilar-Ruiz, and J.C. Riquelme previous Rn.N if the replacement was done) is directly added to Rn.M.Ifthe size of Rn.M is equal to βbut xiis nearer to Rn.N than the marker zmost distant from Rn.N, then zis replaced by xi. Possible expansion. When no rule covers xi, SCALLOP looks for rules Re associated with the same label yiwhich can extend to cover xi. A rule Recan be expanded to seize the point xiif fulfills two conditions: 1. xiis not beyond the growth–bounds Re.B, that is: ∀j∈{[1,...,m}· xij ∈(Re.Bjl,R e.Bju) 2. The resulting extended rule does not intersect with any rule associated with a label different to yi. Only one rule, out of all the candidate rules that can extend to cover the new example, is able to grow: that one whose growth or volume increase is the smallest when covering xi(see Figure 2). Definition 1 (Growth of a rule) Let Rbe a rule in Rm.Letxbe a point in Rm. It is defined the growth Gof the rule Rin order to cover the point xias: G(R, xi)= m  j=1,g j>0 10φgj− m  j=1,r j>0 10φrj; gj=uj−lj;uj= max(xij,R.I ju); lj= min(xij ,R.I jl); rj=R.Iju −R.Ijl;φ∈N In order to measure only the new region that is taken when a rule Rextends to cover a new example xi, the growth takes into account only those dimensions for which there is an expansion. Since SCALLOP normalizes each attribute value in [0,1] before processing an example, the term 10φis used to avoid that a rule Rawithout expansion in a certain dimension k(Ra.Ikl =Ra.Iku) has greater growth than a rule Rbthat has expansion in such a dimension and the same intervals in the rest of dimensions (Ra.Ij=Rb.Ij;∀j=k). Consider two rules in R2,Raand Rb, which can be extended to cover a new point x={0.5,0.5}, so that: Ra.I ={[0.1,0.4]; [0.5,0.5]} (a segment) and Rb.I ={[0.1,0.4]; [0.6,0.7]}(a surface). Without the term 10φ, it results in: G(Ra,x)=0.4−0.3; G(Rb,x)=0.4·0.2−0.3·0.1. That is, contrary to expected, Ragrows more than Rb. We have used φ= 3 in our experiments. A rule can extend to cover a point if it does not overlap with any rule associated with a different label. If this rule Reis found, it is updated with six operations: –Re.r ←i –Re.u ←true –Re.s ←Re.s +1 –Re.Ijb ←Min(Re.Ijb,x ij); Mining Low Dimensionality Data Streams of Continuous Attributes 269 B R1 AR3 - A B d 11 d 12 R2 - A X A ; ; ;;; ; B R1 AR3 - A B d 11 d 12 R2 - A X A a new example B R1 AR3 - A B d 11 R2 - A d 12 A I II III Fig. 2. Case Possible expansion. (1) A new A–example xis not covered by any rule. (2) The rules R1 and R2 do not intersect with any rule associated with a different label when are extended to cover x. (3) Because of the R2’s growth is greater than R1’s, this latter rule extends to cover x. The set R1.D is updated with x, and the rules R1 and R3 are linked each other through R1.O and R3.O, respectively. –Re.Iju ←Max(Re.Ijb,x ij); –Re.Cj←Re.Cj·Re.s+xij Re.s+1 ;∀j∈{1,...,m} When a rule Reis extended, it may overlap with other rules associated with the same label, so that SCALLOP updates the set of links in both directions. In addition, its set of delimiters Re.D ={de1,...,d en}may be updated. If the number of delimiters at the current time (n) is smaller than β, then xiis added to Re.D. When nis equal to β, a delimiter dek may be replaced by xi. Let dek be the nearest delimiter to xi. Let deq be the nearest delimiter to dek.Ifthe Euclidean distance between xiand deq is greater than the Euclidean distance between dek and deq, then dek is replaced by xi(see Figure 2). In a first prototype of SCALLOP the rule selected to cover a new example xiwas that one with the nearest centroid to xi. With this approach we searched for a smaller number of rules by attempting to obtain regions greater than the regions covered by the current rules. But this approach was not a good choice when noise is present in data. Clean streams are unlikely since the nonstop traffic of high dimensionality and high cardinality in the attribute values gives rise to noise, missing, and inconsistencies frequently. With the growth introduced, the model will have a greater number of rules, and these rules will have smaller volume. Nevertheless, by generating more reduced hypercubes, the likelihood that noisy examples are located inside will be smaller than by trying to generalize rules as large as possible. To compact scarcely crowded and dispersed rules, the procedure refineModel is called every δread examples. This means an extra computational cost only at the beginning of the process, as when the model reaches stability, such a refining is almost unnecessary. 270 F.J. Ferrer-Troyano, J.S. Aguilar-Ruiz, and J.C. Riquelme Fig. 3. A rule Ris split when its confidence is smaller than γ. In this case, several derived rules based on R.N,R.D, and R.M are generated. Possible split: when xiis covered by a rule generated for a different label y, the covering rule Rwith the nearest centroid to xiis founded as in the first case. If the new confidence of R((R.s −R.d −1)/R.s) is still greater than or equal to the minimum γgiven by the user, then the number of enemies (R.d) covered by Ris increased by one unit. If the new confidence is smaller than γ, then a new point–rule Rpfor xi is added to the model. Next the support of Rresolves two new subcases. If R.s is smaller than λ% examples received, then Ris directly removed. On the contrary, if R.s is greater than or equal to λ% examples read, then Ris replaced by several derived rules that are built using an iterative procedure from R.N, R.D, and R.M (procedure splitRule in Figure 3): 1. R.N, the delimiters of R.D, and the markers of R.M are sorted in a list LS by the Euclidean distance to xiin a decreasing order. Let sd and sm be the size of R.D and R.M, respectively. 2. A new point–rule R is created for the first element in LS, the most distant vector to xiwith respect to the vectors of LS. Then R.f is initialized as true and such a generating vector is removed from LS. While it is possible, SCALLOP attempts to extend R with the first vector in the list. R can be extended when the resulting region does not cover xi.IfR is extended, the first element in LS is removed again. If the vector that creates or extends R is a delimiter, then R.s is initialized to or increased by one unit. If such Mining Low Dimensionality Data Streams of Continuous Attributes 271 R1 A B B R3 - A R4 A c 1 R1 A B B R3 - A R4 A c 1 A R''2 R1 A B B R2 - A R3 A c 1 R5 N 2 d 22 m 22 C 2 R2-A d 21 m 21 X B A R''3 v'' 1 R''1-A m 22 d 21 m 21 B A R4-A N 4 d 41 d 42 I II III Fig. 4. Case Possible split. (1) A new B–example xis covered by two rules (R1 and R2) associated with the label A. (2) The rule whose centroid is the nearest to such an example (R2) results in three new reduced rules (R”1,R”2, and R”3) that are generated according to R2.N,R2.D and R2.M. (3) R”1 overlaps with a previous rule so that both rules updates their set of links. Moreover, R”2 is removed since is totally covered by R1. Because of R2 was never split, R”1 R”3 update their growth bounds by x.R1 is not changed. a vector is R.N or belongs to R.M, then R.s is initialized to or increased by (R.s −sd)/(sm + 1). 3. When R can not be extended, R.B is updated with R.B (see Figure 6). If R.f is true, then R.B may be updated with xi: when R covers exactly m−1 attribute values of xi, then the value not covered means either an upper growth bound or a lower growth bound (procedure updateGrowthBounds in Figure 5). Finally, R is added to the list reducedRules.IfLS is not empty, the procedure repeats the loop (2) again. A new rule R generated by the procedure splitRule might be partially or totally covered by a previous rule Rc=R, which must is linked through R.O. If a rule R is totally cover by Rc, then R is not included in the model (rule R”2 in Figure 4–II). Moreover, Rcis not updated by R because the examples covered by Rand located inside R they updated Rc.r,Rc.C, and Rc.s when they were read (case Correct covering). If R is partially covered by Rc(rule R”1 in Figure 4–II, R4 in Figure 4– III), then both rules update to each other the sets of links R.O and Rc.O, respectively. If a new rule R is disjointed with all the rules associated with its same label (rule R”3 in Figure 4–II, R5 in Figure 4–III), then is directly added to the model. Although the new example ximay be covered by several rules associated with a different label (rules R1 and R2 in Figure 4), only the rule whose centroid is the nearest to xiis split. We have decided on this criterion under the assumption that if the example xibelongs to a pattern, then near examples associated with the same label yimust be read shortly later, and wrong rules will be corrected. 272 F.J. Ferrer-Troyano, J.S. Aguilar-Ruiz, and J.C. Riquelme Fig. 5. Updating the growth bounds of the rule R2 based on the growth bounds of the split rule R1 and the attribute values of the example xthat split R1. Every time a noisy example xis read, dividing only one rule instead of all the rules that cover xavoids an unnecessary computational cost. In addition, the subsequent updating of the model is hardly harmed as the number of new rules scarcely increases (only the rules from a split that have enough support are included in the model). If xiis noisy or belongs to a minority pattern, then Rp will be removed in the next pruning. Furthermore, the number of overfitting– errors in the final classification phase will be smaller since the probability of covering a new query will be higher. Owing to data streams present a high sensitivity to noise, to make sure a rule is wrong before splitting involves a decisive issue to quickly attain the stability of the model. With a similar criterion, only the nearest rule that covers a new example xicould be updated instead of all the rules for the same label. Nevertheless we have decided on the second option because the centroid associated to each rule will tend to the centroid of an equal solid hypercube with the same spatial location and with uniform mass density. It may benefit the splitting of a rule and the computation of its delimiters and markers, in that it will tend to be more accurate. In addition, the computational cost is not adversely affected. When no rule associated with the label yican cover xi, a new point–rule is generated provided the number of rules associated with yiis smaller than α(basic case). This happens when every expansion causes a non–empty intersection among rules associated with different labels.