6.1.1 Error Estimation

The evaluation procedure of a learning algorithm determines which examples are used for training the algorithm and which are used for testing the model output by the algorithm.

In traditional batch learning, a first approach is to split the dataset into disjoint training and test sets. If the data is limited, cross-validation is preferable: we create several models and average the results with different random arrangements of training and test data.

In the stream setting, (effectively) unlimited data poses different challenges. Cross-validation typically is computationally too expensive, and not as necessary. On the other hand, creating a picture of accuracy over time is essential. The following main approaches arise:

• Holdout: When data is so abundant that it is possible to have test sets periodically, then we can measure the performance on these holdout sets. There is a training data stream that is used to train the learner continuously, and small test datasets that are used to compute the performance periodically. In MOA, the implementation of this concept requires the user to specify two parameters (say, j and k ): j is the size of the first window (set of instances) for testing purposes, and k is the frequency of testing—that is, test after every k instances (using a test set of size j ).
• Interleaved test-then-train: Each individual example can be used to test the model before it is used for training, and from this, the accuracy can be incrementally updated. The model is thus always being tested on examples it has not seen. In MOA, this scheme is implemented using a landmark window model (data in the stream is considered from the beginning to now).
• Prequential: Like interleaved test-then-train but—in MOA—implements the idea that more recent examples are more important, using a sliding window or a decaying factor. The sizes of the sliding window and the decaying factor are parameters.
• Interleaved chunks: Also like interleaved test-then-train, but with chunks of data in sequence. Chunks of different sizes may need to be considered (this is a parameter in the MOA implementation).

Note that if we set the size of the sliding window to the number of instances in the entire dataset, then the middle two schemes are equivalent.

Holdout evaluation more accurately estimates the accuracy of the classifier on more recent data. However, it requires recent test data that is difficult to obtain for real datasets. There is also the issue of ensuring coverage of important change events: if the holdout is during a less volatile period of change, then it might overestimate classifier performance.

Gama et al. [ 115 ] propose a forgetting mechanism for estimating holdout accuracy using prequential accuracy: a sliding window of size w with the most recent observations, or fading factors that weigh observations using a decay factor α . The fading factor α is used as follows:

with

where n _i is the number of examples used to compute the loss function L _i . We have n _i = 1 since the loss L _i is computed for every single example.

The output of the two mechanisms is very similar, as a window of size w may be approximated by a decay factor α ∼ 1 /w . Figure 6.1 shows a comparison of a holdout evaluation, an interleaved test then train evaluation, and a prequential evaluation using a sliding window of size 1,000. Looking at the plot in figure 6.1 it seems that, at least for this dataset, prequential evaluation using a sliding window is a good approximation of holdout evaluation.

6.1.2 Distributed Evaluation

In a distributed data stream setting, we have classifiers that can be trained at the same time. This provides an opportunity to implement something akin to classic k -fold cross-validation. Several approaches to evaluation in this setting have been proposed to cover combinations of data abundance or scarcity, and numbers of classifiers to be compared [ 40 ]:

• k -fold distributed split-validation: when there is abundance of data and k classifiers. Each time a new instance arrives, it is decided with probability 1 /k whether it will be used for testing. If it is used for testing, it is used by all the classifiers. If not, then it is used for training and assigned to only one classifier. Thus, each classifier sees different instances, and they are tested using the same data.
• 5 x 2 distributed cross-validation: when data is less abundant, and we want to use only, say, ten classifiers. We create five groups of classifier pairs, and for each group, each time a new instance arrives, it is decided with probability 1/2 which of the two classifiers is used to test; the other classifier of the group is used to train. All instances are used to test or to train, and there is no overlap between test instances and train instances.
• k -fold distributed cross-validation: when data is scarce and we have k classifiers. Each time a new instance arrives, it is used for testing in one classifier selected at random, and for training in the others. This evaluation is equivalent to k -fold distributed cross-validation.

6.1.3 Performance Evaluation Measures

In real data streams, the number of instances for each class may be evolving and changing. It may be argued that the prequential accuracy measure is only appropriate when all classes are balanced and have approximately the same number of examples. The Kappa statistic is a more sensitive measure for quantifying the predictive performance of streaming classifiers.

The Kappa statistic κ was introduced by Cohen [ 76 ] and defined as follows:

The quantity p ₀ is the classifier’s prequential accuracy, and p _c is the probability that a chance classifier—one that randomly assigns to each class the same number of examples as the classifier under consideration—makes a correct prediction. If the classifier is always correct, then κ = 1. If its predictions coincide with the correct ones as often as those of a chance classifier, then κ = 0.

The Kappa M statistic κ _m [ 40 ] is a measure that compares against a majority class classifier instead of a chance classifier:

In cases where the distribution of predicted classes is substantially different from the distribution of the actual classes, a majority class classifier can perform better than a given classifier while the classifier has a positive κ statistic.

An alternative to the Kappa statistic is to compute the area under the receiver operating characteristics curve AUC. Brzezinski and Stefanowski present in [ 59 ] an incremental algorithm that uses a sorted tree structure with a sliding window to compute AUC with forgetting. The resulting evaluation measure is called prequential AUC, and is also available in MOA.

Another Kappa measure, the Kappa temporal statistic [ 42 , 262 ], considers the presence of temporal dependencies in data streams. It is defined as

where is the accuracy of the No-change classifier, the classifier that simply echoes the last label received (section 6.2.2), a simple and useful classifier when the same labels appear together in bursts.

Statistic κ _per takes values from 0 to 1. The interpretation is similar to that of κ : if the classifier is perfectly correct, then κ _per = 1. If the classifier is achieving the same accuracy as the No-change classifier, then κ _per = 0. Classifiers that outperform the No-change classifier fall between 0 and 1. Sometimes κ _per < 0, which means that the classifier is performing worse than the No-change baseline.

Using κ _per instead of κ _m , we can detect misleading classifier performance for data that is not IID. For highly imbalanced but independently distributed data, the majority class classifier may beat the No-change classifier. The κ _per and κ _m measures can be seen as orthogonal, since they measure different aspects of the performance.

Other measures that focus on the imbalance among classes are the arithmetic mean and the geometric mean:

where A _i is the testing accuracy on class i and n _c is the number of classes. Note that the geometric accuracy of the majority vote classifier would be 0, as accuracy on the classes other than the majority would be 0. The accuracy of a perfectly correct classifier would be 1. If the accuracies of a classifier are equal for all classes, then both arithmetic and geometric accuracies are equal to the usual accuracy.

Consider the simple confusion matrix shown in table 6.1 . From this table, we see that Class+ is predicted correctly 75 times, and Class− is predicted correctly 10 times. So accuracy p ₀ is 85%. However, a classifier predicting solely by chance—in the given proportions—will predict Class+ and Class− correctly in 68.06% and 3.06% of cases respectively. Hence, it has accuracy p _c = 71.12% and κ = 0.48; the majority class classifier has accuracy p _m = 75% and κ _m = 0.40.

Table 6.1
Simple confusion matrix example.

The accuracy for Class+ is 90.36% and for Class− is 58.82%. The arithmetic mean A is 74.59%, and the geometric mean G is 72.90%. So we see that A ≥ G and that G tends to the lower value.

Imagine that, as shown in table 6.2 , the number of misclassified examples of Class− increases to 57. Then, the accuracy for Class− decreases to 14.92%, κ to 0.05, and κ _m to 0.13. The arithmetic mean A changes to 52.64%, and the geometric mean G to 36.72 %.

Table 6.2
Confusion matrix of table 6.1 , modified.

6.1.4 Statistical Significance

When evaluating classifiers, we should be concerned with the statistical significance of the results. Looking at the performance of only one classifier, it is convenient to give some insights about its statistical significance. We may use confidence intervals of parameter estimates to indicate the reliability of our estimate. To do that, we can use Chernoff’s or Hoeffding’s bounds, which are sharper than Markov’s or Chebyshev’s inequalities, because the measures we are interested in are averages of evaluations on individual items. For reasonably large numbers of points the approximation by a normal is usually applicable; see section 4.2.

When comparing two classifiers, we need to distinguish between random and nonrandom differences in the experimental accuracies. McNemar’s test [ 173 ] is the most popular nonparametric test in the stream mining literature to assess the statistical significance of differences in the performance of two classifiers. This test needs to store and update two variables: the number of instances misclassified by the first classifier and not by the second, a , and the number of instances misclassified by the second classifier and not by the first, b . The McNemar statistic is given as M = | a − b − 1| ² /( a + b ). The test follows the χ ² distribution. At 0.99 confidence it rejects the null hypothesis (the performances are equal) if M > 6.635.

Although the field of ML is several decades old, there is still much debate around the issue of comparing the performance of classifiers and, consequently, measurements of significant performance difference. The latest contribution is by Berrar [ 29 ], who argues that the magnitude of the difference in performance (and reasonable bounds on that difference) should be the focus, not statistical significance. The outcome of this work is a new evaluation tool called confidence curves, curves that show the magnitude difference directly. Issues with null hypothesis significance testing and p -values have also recently led to Bayesian alternatives to the problem being proposed [ 78 ]. Thus, it is not possible at this time to give a definitive answer to the question of performance measurement, as further research in classic and streaming ML is still needed. In particular, a measure for estimating the effect size over time for data streams has yet to be proposed.

6.1.5 A Cost Measure for the Mining Process

The issue of measuring three evaluation dimensions simultaneously has led to another important issue in data stream mining, namely, estimating the combined cost of performing the learning and prediction processes in terms of time and memory. As an example, several rental cost options exist:

• Cost per hour of usage: Amazon Elastic Compute Cloud (Amazon EC2) is a web service that provides resizable computing capacity in the cloud. The cost depends on the time and on the size of the machine rented (for example, small instance with 2 GB of RAM, large with 8 GB or extra large with 16 GB).
• Cost per hour and memory used: GoGrid is a web service similar to Amazon EC2, but it charges by RAM-hours. Every GB of RAM deployed for 1 hour equals by definition 1 RAM-hour.

The use of RAM-Hours as defined above was introduced in [ 37 ] as an evaluation measure of the resources used by streaming algorithms. Although proposed for learning, it can be applied to the other data mining tasks.

6.2.1 Majority Class

The Majority Class algorithm is one of the simplest classifiers: it predicts the class of a new instance to be the most frequent class. It is used mostly as a baseline, but also as a default classifier at the leaves of decision trees. A Majority Class classifier is very easy to compute and maintain, as it only needs to keep an array of counters for each one of the classes.

6.2.2 No-change Classifier

Another simple classifier for data streams is the No-change classifier, which predicts the label for a new instance to be the true label of the previous instance. Like the Majority Class classifier, it does not require the instance features, so it is very easy to implement. In the intrusion detection case where long passages of “no intrusion” are followed with briefer periods of “intrusion,” this classifier makes mistakes only on the boundary cases, adjusting quickly to the consistent pattern of labels.

When a temporal dependence among consecutive labels is suspected, it usually pays to add the label(s) of the previous instance(s) as new attributes. This capability, proposed in [ 42 , 262 ], is available as a generic wrapper T EMPORALLY A UGMENTED C LASSIFIER in MOA.

6.2.3 Naive Bayes

Naive Bayes is a classification algorithm known for its low computational cost and simplicity. As an incremental algorithm, it is well suited for the data stream setting. However, it assumes independence of the attributes, and that might not be the case in many real data streams.

It is based on Bayes’ theorem, which may be stated informally as

that is, it tells how the probability of an event is modified after accounting for evidence. More formally:

where Pr( c ) is the prior, the initial probability of event c , Pr( c | d ) is the posterior, the probability after accounting for d , Pr( d | c ) is the likelihood of event d given that event c occurs, and Pr( d ) is the probability of event d . It is based on the definition of conditional probability, by which Pr( c ∩ d ) = Pr( c )Pr( d | c ) = Pr( d )Pr( c | d ).

The Naive Bayes model is built as follows: Let x ₁ , …, x _k be k discrete attributes, and assume that x _i can take n _i different values. Let C be the class attribute, which can take n _C different values. Upon receiving an unlabeled instance I = ( x ₁ = v ₁ ,… ,x _k = v _k ), the Naive Bayes classifier computes a “probability” of I being in class c as:

The values Pr( x _i = v _j ∧ C = c ) and Pr( C = c ) are estimated from the training data. Thus, the summary of the training data is simply a 3-dimensional table that stores for each triple ( x _i ,v _j ,c ) a count n _i,j,c of training instances with x _i = v _j and class c , together with a 1-dimensional table for the counts of C = c . This algorithm is naturally incremental: upon receiving a new example (or a batch of new examples), simply increment the relevant counts. Predictions can be made at any time from the current counts.

Example 6.1 Suppose we have the following dataset of tweets, and that we want to build a model to predict the polarity of newly arriving tweets.

First, we transform the text associated with each instance to a vector of attributes.

Now, we can build a table with the counts for each class:

Assume we have to classify the following new instance:

First, we convert it to a vector of attributes.

And now we compute the probabilities as follows:

• Pr(+| T 5) = Pr(+) · Pr( glad = 1|+) · Pr( happy = 0|+) · Pr( joyful = 0|+) · Pr( pleasant = 1|+) · Pr( miserable = 1|+) · Pr( sad = 1|+), so

• Pr(−| T 5) = Pr (−) · Pr( glad = 1|−) · Pr( happy = 0|−) · Pr( joyful = 0|−) · Pr( pleasant = 1|−) · Pr( miserable = 1|−) · Pr( sad = 1|−), so

We see that the probabilities are equal to 0 the moment a single term is 0, which is too drastic. A way to avoid this is using the Laplace correction , which is adding, for example, 1 to the numerator and the number of classes to the denominator to allow for unseen instances:

In practice, this is done by initializing the counters to 1. In our example, the table of counts for each class becomes:

And recomputing the probabilities we get:

• Pr(+| T 5) = Pr(+) · Pr( glad = 1|+) · Pr( happy = 0|+) · Pr( joyful = 0|+) · Pr( pleasant = 1|+) · Pr( miserable = 1|+) · Pr( sad = 1|+), so

• Pr(−| T 5) = Pr(−) · Pr( glad = 1|−) · Pr( happy = 0|−) · Pr( joyful = 0|−) · Pr( pleasant = 1|−) · Pr( miserable = 1|−) · Pr( sad = 1|−), so

We see that Pr(−| T 5) > Pr(+| T 5) and the Naive Bayes classifier predicts that the new tweet has negative polarity.

Observe that the two probabilities do not add up to 1 as they should, because we have ignored the term Pr( d ) in Bayes’ theorem. It is normally impossible to assess the probability of a specific data point from a sample. We, can, however normalize by the sum to obtain figures that add up to 1.

6.2.4 Multinomial Naive Bayes

The Multinomial Naive Bayes classifier [ 171 ] is an extension of Naive Bayes for document classification that often yields surprisingly good results. Multinomial Naive Bayes considers a document as a bag of words, so it takes into account the frequency of each word in a document and not just its presence or absence. Since word frequency is usually relevant for text classification, this method is preferred over Naive Bayes for text mining.

Let n _wd be the number of times word w occurs in document d . Then the probability of class c given a test document is calculated as follows:

where Pr( d ) can be thought of as a normalization factor.

But a key difference with Naive Bayes is the interpretation of Pr( w | c ): here it is the ratio between the number of occurrences of w in documents of class c over the total number of words in documents of class c . In other words, it is the probability of observing word w at any position of a document belonging to class c . Observe that, again unlike Naive Bayes, the absence of a word in a document does not make any class more likely than any other, as it translates to a 0 exponent.

Conveniently, n _wd , Pr( w | c ) and Pr( c ) are trivial to estimate on a data streams by keeping the appropriate counters. Laplace correction can be added by initializing all the counts to 1 instead of 0.

Example 6.2 Suppose we want to build a Multinomial Naive Bayes classifier using the tweets in example 6.1. First we compute the number of occurrences of each word in each document. We use Laplace correction, setting each entry to 1 before starting to count occurrences:

And now the probabilities for each class are:

• Pr(+| T 5) =
  Pr(+) · Pr( glad |+) · Pr( pleasant |+) · Pr( miserable |+) · Pr( sad |+),

• Pr(−| T 5) =
  Pr(−) · Pr( glad |−) · Pr( pleasant |−) · Pr( miserable |−) · Pr( sad |−),

In this case, we see that Pr(+| T 5) > Pr(−| T 5) and the Multinomial Naive Bayes classifier predicts that the new tweet has positive polarity, in contrast to regular Naive Bayes, which predicted negative polarity.

6.3.1 Estimating Split Criteria

The measures above need to be estimated from finite samples, but in a way that generalizes to future examples (that is, whether it is made now or in a month, year, or decade hence, it will still be the same decision, assuming stationarity). This calls for concentration inequalities in the spirit of those presented in section 4.2, which bound the probability that an estimate over a finite sample is far off its expectation.

Hoeffding’s inequality has often been used for estimating measures like information gain or the Gini index. Unfortunately, these measures cannot be expressed as a sum of independent random variables, and so Hoeffding’s bound is argued in recent work by Rutkowski et al. [ 218 ] to be the wrong tool.

A generalization of Hoeffding’s inequality called McDiarmid’s inequality can, however, be used for making split decisions using these measures as it works explicitly on functions of the data [ 218 ]. For information gain IG , the following can be shown for any two attributes A and B : if E _S [ IG ( S,A ) − IG ( S,B )] > 𝜖 , then with probability 1 − δ we have IG ( S,A ) − IG ( S,B ) > 0, where , n is the size of S , and n _c is the number of classes. The formulation for the Gini index is simpler: it suffices to have . Similar bounds are given in [ 215 ]. Misclassification error can also be used [ 217 ], eventually giving a bound very similar to Hoeffding’s bound.

Note that our description of work on decision trees for streaming takes a historical perspective. The use of McDiarmid’s bound is cutting-edge for this particular method and represents a relatively new result. Hoeffding trees may, in the future, be proven incorrect in the sense of being based on assumptions that do not hold, however, they are still very effective in practice, and so worthy of study.

6.3.2 The Hoeffding Tree

In the data stream setting, where we cannot store all the data, the main problem of building a decision tree is the need to reuse instances to compute the best splitting attributes. Domingos and Hulten [ 88 ] proposed the Hoeffding Tree, a very fast decision tree algorithm for streaming data, where instead of reusing instances, we wait for new instances to arrive. The most interesting feature of the Hoeffding Tree is that it builds a tree that provably converges to the tree built by a batch learner with sufficiently large data; a more precise statement of this equivalence is provided later in this section.

The pseudocode of the Hoeffding Tree is shown in figure 6.3 . It is based on Hoeffding’s bound, discussed in section 4.2. On the basis of the bound, the proposal in [ 88 ] was to choose, as a confidence interval for the estimation of the entropy at a node, the value

where R is the range of the random variable, δ is the desired probability of the estimate not being within 𝜖 of its expected value, and n is the number of examples collected at the node. In the case of information gain, the entropy is in the range [0,…,log n _c ] for n _c class values. Although the use of Hoeffding’s bound in this context is formally incorrect, as explained before, it is still used in most implementations; the reasonable results it achieves may be due to the fact that it gives, in most cases, an overestimation of the true probability of error.

The Hoeffding Tree algorithm maintains in each node the statistics needed for splitting attributes. For discrete attributes, this is the same information as needed for computing the Naive Bayes predictions: a 3-dimensional table that stores for each triple ( x _i ,v _j ,c ) a count n _i,j,c of training instances with x _i = v _j , together with a 1-dimensional table for the counts of C = c . The memory needed depends on the number of leaves of the tree, not on the length of the data stream.

A theoretically appealing feature of the Hoeffding Tree not shared by other incremental decision tree learners is that it has sound guarantees of performance. It was shown in [ 88 ] that its output is asymptotically nearly identical to that of a nonincremental learner using infinitely many examples, in the following sense.

The intensional disagreement Δ _i between two decision trees DT ₁ and DT ₂ is the probability that the path of an example through DT ₁ will differ from its path through DT ₂ , in length, or in the attributes tested, or in the class prediction at the leaf. The following result is rigorously proved in [ 88 ]: Let HT _δ be the tree produced by the Hoeffding Tree algorithm with parameter δ from an infinite stream of examples, DT be the batch tree built from an infinite batch, and p be the smallest probability of a leaf in DT . Then we have E [Δ _i ( HT _δ ,DT )] ≤ δ/p .

Domingos and Hulten [ 88 ] improved the Hoeffding Tree algorithm to a more practical method called the very fast decision tree (VFDT), with the following characteristics:

• Ties: When two attributes have similar split gain G , the improved method splits if Hoeffding’s bound is lower than a certain threshold parameter τ .

• To speed up the process, instead of computing the best attributes to split every time a new instance arrives, the VFDT computes them every time a number n _min of instances has arrived.
• To reduce the memory used in the mining, the VFDT deactivates the least promising nodes, those with the lowest product p _l × e _l , where
  • p _l is the probability to reach leaf l , and
  • e _l is the error in node l .
• The method can be started from any preexisting decision tree, for example, one built from an available batch of data. Hoeffding trees can grow slowly and performance can be poor initially, so this extension provides an immediate boost to the learning curve.

It is worth noting that there has been very little research on the last point in the VFDT method. Slow initial learning is an issue for these trees, and bootstrapping via an initial decision tree to create a better starting point makes sense.

One way to improve the classification performance of the Hoeffding Tree is to use Naive Bayes learners at the leaves instead of the majority class classifier. Gama and Medas [ 113 ] were the first to use Naive Bayes in Hoeffding Tree leaves, replacing the majority class classifier. However, Holmes et al. [ 135 ] identified situations where the Naive Bayes method outperforms the standard Hoeffding Tree initially but is eventually overtaken. To solve that, they proposed a hybrid adaptive method that generally outperforms the two original prediction methods for both simple and complex concepts: when performing a prediction on a test instance, the leaf will return the Naive Bayes prediction if it has been more accurate overall than the majority class prediction, otherwise it returns the majority class. The only overhead is keeping the two counts for the number of times each classifier has been correct.

6.3.3 CVFDT

Hulten et al. [ 138 ] presented the concept-adapting very fast decision tree (CVFDT) algorithm as an extension of VFDT to deal with concept drift, maintaining a model that is consistent with the instances stored in a sliding window. Unfortunately, such trees do not have theoretical guarantees like Hoeffding trees. Note that, theoretically, Hoeffding trees can to some extent adapt to concept drift, because leaves that would not grow any more under a stationary distribution may start to grow again if evidence gathers that further splitting would improve accuracy. However, this process is too slow in practice.

Figure 6.4 shows a sketch of the code for the CVFDT algorithm; a fuller description is provided in the reference above. It is similar to the code for the Hoeffding Tree but with the changes listed below. Note that here we use the terms “remove” and “forget” which look the same. They are different, however, as forgetting is a complex procedure that removes an instance from the tree. In contrast, adding and removing instances only applies to the sliding window.

• The main method maintains a sliding window with the latest instances, so it has to add, remove, and forget instances.
• The main method calls procedure CVFDTG ROW to process an example, but also method C HECK S PLIT V ALIDITY to check whether the chosen splits are still valid.
• CVFDTG ROW also updates counts of the nodes traversed in the sort.
• C HECK S PLIT V ALIDITY creates an alternate subtree if the attributes chosen to split are now different from the ones that were chosen when the split was done.
• Periodically, the algorithm checks whether the alternate branch is performing better than the original branch tree, and if so it replaces the original branch, and if not, it removes the alternate branch.

6.3.4 VFDTc and UFFT

VFDTc and UFFT are two methods that extend the Hoeffding Tree to handle numeric attributes and concept drift. VFDTc, developed by Gama et al. [ 111 ], does the following:

1. It keeps Naive Bayes learners at the leaves to make predictions.
2. It handles numeric attributes using binary trees, as explained in section 6.4.2.
3. To handle concept drift, it uses the statistical DDM method explained in section 5.3.4.

The ultra fast forest of trees (UFFT), developed by Gama and Medas [ 113 ], generates a forest of binary trees, one for each possible pair of classes. The trees contain a Naive Bayes classifier at each node, like VFDTc. The main difference from VFDTc is in the handling of numeric attributes.

UFFT uses analytical techniques to choose the splitting criteria, and information gain to estimate the merit of each possible splitting test. For multiclass problems, the algorithm builds a binary tree for each possible pair of classes, leading to a forest of trees, that comprises k ( k − 1)/2 classifiers for a k -class problem. The analytical method uses a modified form of quadratic discriminant analysis to include different variances on the two classes.

6.3.5 Hoeffding Adaptive Tree

The Hoeffding Adaptive Tree [ 33 ] is an adaptive extension to the Hoeffding Tree that uses A DWIN as a change detector and error estimator. It has theoretical guarantees of performance and requires no parameters related to change control. In contrast, CVFDT has no theoretical guarantees, and requires several parameters with default values that can be changed by the user, but which are fixed for a given execution. It requires:

1. W : The example window size.
2. T ₀ : Every T ₀ examples, CVFDT traverses the entire decision tree, and checks at each node whether the splitting attribute is still the best. If there is a better splitting attribute, it starts growing an alternate tree rooted at this node, and it splits on the current best attribute according to the statistics at the node.
3. T ₁ : After an alternate tree is created, the following T ₁ examples are used to build the alternate tree.
4. T ₂ : After the arrival of T ₁ examples, the following T ₂ examples are used to test the accuracy of the alternate tree. If the alternate tree is more accurate than the current one, CVFDT replaces it with this alternate tree (we say that the alternate tree is promoted).

The default values are W = 50,000, T ₀ = 10,000, T ₁ = 9,000, and T ₂ = 1,000. We can interpret these figures as the assumptions that often the last 50,000 examples are likely to be relevant, that change is not likely to occur faster than every 10,000 examples, and that 1,000 examples will be sufficient to tell the best among current and candidate trees. These assumptions may or may not be correct for a given data source. Moreover, the stream may change differently at different times, so no single set of values may be best for all the stream.

The main differences of the Hoeffding Adaptive Tree with respect to CVFDT are:

• The alternate trees are created as soon as change is detected, without having to wait for a fixed number of examples to arrive after the change. Furthermore, the more abrupt the change, the faster a new alternate tree will be created.
• The Hoeffding Adaptive Tree replaces an old tree with the alternate tree as soon as there is evidence that it is more accurate, rather than waiting for another fixed number of examples.

These two effects can be summarized by saying that the Hoeffding Adaptive Tree adapts to the scale of time change in the data, rather than relying on the a priori guesses made by the user.

6.4.1 VFML

The very fast machine learning (VFML) package of Hulten and Domingos [ 137 ] contains a method for handling numeric attributes in VFDT and CVFDT. Numeric attribute values are summarized by a set of ordered bins. The range of values covered by each bin is fixed at creation time and does not change as more examples are seen. A hidden parameter serves as a limit on the total number of bins allowed—in the VFML implementation this is hard-coded to allow a maximum of 1,000 bins. Initially, for every new unique numeric value seen, a new bin is created. Once the fixed number of bins have been allocated, each subsequent value in the stream updates the counter of the nearest bin.

Essentially, the algorithm summarizes the numeric distribution with a histogram, made up of a maximum of 1,000 bins. The boundaries of the bins are determined by the first 1,000 unique values seen in the stream, and after that the counts of the static bins are incrementally updated.

There are two potential issues with this approach. Clearly, the method is sensitive to data order. If the first 1,000 examples seen in a stream happen to be skewed to one side of the total range of values, then the final summary cannot accurately represent the full range of values.

The other issue is estimating the optimal number of bins. Too few bins will mean the summary is small but inaccurate, whereas too many bins will increase accuracy at the cost of space. In the experimental comparison the maximum number of bins is varied to test this effect.

6.4.2 Exhaustive Binary Tree

Gama et al. [ 111 ] present this method in their VFDTc system. It aims at achieving perfect accuracy at the expense of storage space. The decisions made are the same that a batch method would make, because essentially it is a batch method—no information is discarded other than the order of values.

It works by incrementally constructing a binary tree as values are observed. The path a value follows down the tree depends on whether it is less than, equal to, or greater than the value at a particular node in the tree. The values are implicitly sorted as the tree is constructed, and the number of nodes at each time is the number of distinct values seen. Space saving occurs if the number of distinct values is small.

On the other hand, the structure saves search time versus storing the values in an array as long as the tree is reasonably balanced. In particular, if values arrive in order, then the tree degenerates to a list and no search time is saved.

6.4.3 Greenwald and Khanna’s Quantile Summaries

The field of database research is also concerned with the problem of summarizing the numeric distribution of a large dataset in a single pass and limited space. The ability to do so can help to optimize queries over massive databases.

Greenwald and Khanna [ 129 ] proposed a quantile summary method with even stronger accuracy guarantees than previous approaches. The method works by maintaining an ordered set of tuples, each of which records a value from the input stream, along with implicit bounds for the range of each value’s true rank. Precisely, a tuple t _i = ( v _i ,g _i ,Δ _i ) consists of three values:

• a value v _i of one of the elements seen so far in the stream,
• a value g _i that equals r _min ( v _i ) − r _min ( v _{i −1} ), where r _min ( v ) is the lower bound of the rank of v among all the values seen so far, and
• a value Δ _i that equals r _max ( v _i ) − r _min ( v _i ), where r _max ( v ) is the upper bound of the rank of v among all the values seen so far.

Note that

The quantile summary is 𝜖 -approximate in the following sense: after seeing N elements of a sequence, any quantile estimate returned will not differ from the exact value by more than 𝜖 N . An operation for compressing the quantile summary is defined that guarantees max( g _i + Δ _i ) ≤ 2 𝜖 N , so that the error of the summary is kept within 2 𝜖 .

The worst-case space requirement is shown to be , with empirical evidence showing it to be even better than this in practice.

6.4.4 Gaussian Approximation

This method, presented in [ 199 ], approximates a numeric distribution in small constant space, using a Gaussian or normal distribution. Such a distribution can be incrementally maintained by storing only three numbers, in a way that is insensitive to data order. A similar method to this one was described by Gama and Medas in their UFFT system [ 113 ].

For each numeric attribute, the method maintains a separate Gaussian distribution per class label. The possible values are reduced to a set of points spread equally across the range, between the minimum and maximum values observed. The number of evaluation points is determined by a parameter, so the search for split points is parametric , even though the underlying Gaussian approximations are not. For each candidate point, the weight of values to either side of the split can be approximated for each class, using their respective Gaussian curves, and the information gain is computed from these weights.

The process is illustrated in figure 6.5 . At the top of the figure are two Gaussian curves, each approximating the distribution of values for a numeric attribute and labeled with a particular class. Each curve can be described using three values: the mean, the variance, and the total weight of examples. For instance, in figure 6.5 , the class shown to the left has a lower mean, higher variance, and higher example weight (larger area under the curve) than the other class. Below the curves, the range of values has been divided into ten split points, labeled A to J. The vertical bar at the bottom displays the relative amount of information gain calculated for each split. The split point that would be chosen as the best is point E, which the evaluation shows has the highest information gain.

A refinement of this method involves also tracking the minimum and maximum values of each class. This requires storing an extra two counts per class, but they are simple and take little time to maintain. When evaluating split points, the method exploits per-class minimum and maximum information to determine when class values lie completely to one side of a split, eliminating the small uncertainty otherwise present in the tails of the Gaussian curves. From the per-class minimum and maximum, the minimum and maximum of the entire range of values can be established, which helps to determine the position of split points to evaluate.

Approximation by a sum of Gaussians will almost certainly not capture the full detail of an intricate numeric distribution, but the approach is efficient in both computation and memory. Whereas the binary tree method uses extreme memory costs to be as accurate as possible, this method employs the opposite approach—using gross approximation to use as little memory as possible. And in fact, the simplified view of numeric distributions is not necessarily harmful to the accuracy of the trees it produces. There will be further opportunities to refine split decisions on a particular attribute by splitting again further down the tree. Also, the approximation by a few simple parameters can be more robust and resistant to noise and outliers than more complicated methods, which concentrate on finer details.

6.7.1 Multi-label Hoeffding Trees

A Multi-label Hoeffding tree was presented in [ 208 ], based on adaptation of the information gain criterion to multi-label problems.

Recall that Hoeffding trees use the information gain criterion to decide the best attribute at each expanding node, and that the information gain of an attribute is the difference between the entropy of the dataset before and after the split. As entropy measures the amount of uncertainty in the dataset, in the case of multi-label examples, we need to add to the entropy the information needed to describe all the classes that an example does not belong to.

Clare and King [ 72 ] showed that this can be accomplished by adding to the regular entropy a term that adds, for each label, a quantity related to the class entropy in the examples having that label. From there, they proposed a multi-label version of C4.5. The Multi-label Hoeffding Tree [ 208 ] uses this strategy to construct a decision tree. A Majority Labelset Classifier (the multi-label version of Majority Class) is used as the default classifier on the leaves of a Multi-label Hoeffding tree. However, any multi-label classifier at the leaves can be used.

6.8.1 Random Strategy

The first (baseline) strategy is naive in the sense that it labels the incoming instances at random instead of actively deciding which label would be most relevant. For every incoming instance the true label is requested with probability B , where B is the budget.

6.8.2 Fixed Uncertainty Strategy

Uncertainty sampling is perhaps the simplest and the most common active learning strategy [ 224 ]. The idea is to label the instances for which the current classifier is the least confident. In an online setting, this corresponds to labeling the instances for which the certainty is below some fixed threshold. A simple way to measure uncertainty is to use the posterior probability estimates, output by a classifier.

6.8.3 Variable Uncertainty Strategy

One of the challenges with the fixed uncertainty strategy in a streaming data setting is how to distribute the labeling effort over time. Using a fixed threshold, after some time a classifier will either exhaust its budget or reach the threshold certainty. In both cases it will stop learning and thus fail to adapt to changes.

Instead of labeling the instances that are less certain than the threshold, we want to label the least certain instances within a time interval. Thus we can introduce a variable threshold, which adjusts itself depending on the incoming data to align with the budget. If a classifier becomes more certain (stable situations), the threshold expands to be able to capture the most uncertain instances. If a change happens and suddenly a lot of labeling requests appear, then the threshold is contracted to query only the most uncertain instances.

It may seem counterintuitive to ask for more labels in quiet periods and fewer labels at change points. But, in fact, this ensures that the algorithm asks for the same fraction of labels in all situations. Since it does not know when or how often changes will be happening, this helps in spending the budget uniformly over time.

The variable uncertainty strategy is described in figure 6.7 . More detail and a comparison with the other strategies can be found in [ 261 ].

6.8.4 Uncertainty Strategy with Randomization

The uncertainty strategy always labels the instances that are closest to the decision boundary of the classifier. In data streams, changes may happen anywhere in the instance space. When concept drift happens in labels, the classifier will not notice it without the true labels. In order to not miss concept drift we should, from time to time, label some instances about which the classifier is very certain. For that purpose, for every instance, the strategy randomizes the labeling threshold by multiplying by a normally distributed random variable that follows N (1 , δ ). This way, it labels the instances that are close to the decision boundary more often, but occasionally also labels some distant instances.

This strategy trades off labeling some very uncertain instances for labeling very certain instances, in order to not miss changes. Thus, in stationary situations this strategy is expected to perform worse than the uncertainty strategy, but in changing situations it is expected to adapt faster.

Table 6.3 summarizes the four strategies with respect to several requirements. The random strategy satisfies all three requirements. Randomized uncertainty satisfies budget and coverage, but it produces biased labeled data. Variable uncertainty satisfies only the budget requirement, and fixed uncertainty satisfies none.

Table 6.3
Summary of budget allocation strategies.