To limit the amount of processed data, the sliding window concept is used. There are various windowing models explained in [2], i.e., fixed sliding window, adaptive window, landmark window, and damped window. The number of examples within this window length is chosen for further processing. As the processing of an evolving stream as a whole is a very cumbersome job, many researchers have used the hoeffding bounds for mining data streams. In [3], the authors used the hoeffding bound to generate the decision tree, which is the mathematical tool of the hoeffding theorem [4]. The hoeffding bound ensures, with high probability, that the best splitting attribute chosen from the N examples is similar to the few samples chosen from infinite examples of the data stream. In [5], the authors introduced McDiarmid's inequality [6] to choose the best splitting attribute instead of using the hoeffding bound.

Another research problem in data stream mining is concept drift, i.e., detecting promptly evolving concepts because of the highly dynamic nature of data streams. There are several approaches to handling the concept drift problem in data stream mining like Very Fast Decision Tree (VFDT) [3], Concept-adapting Very Fast Decision Tree (CVFDT) [7], and Efficient-Concept-adapting Very Fast Decision Tree (E-CVFDT) [8]. E-CVFDT will be used in this chapter. VFDT Learner is an incremental learning approach for stationary data distribution. CVFDT is an extension of VFDT that deals with the concept drift problem for high-speed data streams. In the traditional CVFDT method, with the change in concept, a new optional subtree is created and a splitting attribute is chosen on the basis of splitting function. It does not consider the type of concepts arriving at the data stream. The type of concept drift plays an important role in reducing the processing time and cost. Suppose the concept, arriving in a stream, is accidental like noise and disappears very quickly. In CVFDT, as this new concept arrives, a new subtree will be created. As this concept will disappear very quickly, after its disappearance the CVFDT algorithm will rebuild that subtree. Thus this affects the processing time as well as the cost. Gang Liu [8] proposed an improved CVFDT approach for mining data streams, i.e., the E-CVFDT. E-CVFDT considers the three types of concept instances, namely, accidental concept drift, gradual concept drift, and instantaneous concept drift. In accidental concept drift, the new concept will appear for a very short timespan and then the old concept will reappear. Suppose the sequence of the old concept is Seq_A and the sequence of new concept is Seq_b. Then, the accidental concept drift sequence can be represented as S = {A_1, A₂, A₃ … A_n, B₁, B₂, B₃ … B_r, A_P … A_m}. In gradual concept drift, the new concept will evolve with the old concept. This can be shown as S = {A₁, A₂, A₃ … A_n, B₁, B₂, B₃ … B_r, A_P … A_q, B_m … B_s}. In instantaneous concept drift, the new concept will instantly appear and the old concept will disappear. This can be represented as S = {A_1, A₂, A₃ … A_n, B₁, B₂, B₃ … B_M}.

Here, a cached system is also used for storing the new concepts. As the new concepts arrive, the examples are stored in an array and if this concept seems to be useless, then these examples can be dropped. The appropriate sequence of examples is thus selected for the mining purpose. The number of examples is determined by the hoeffding bound. From these examples, the best splitting attribute is chosen and the corresponding decision tree will be created, i.e., incremental learning will be performed. Classification and Regression Tree (CART) decision tree induction is used for mining and classification purposes.

The rest of the chapter is structured as follows: Section 2 discusses the related state of the art. It explains the hoeffding bound CART decision tree induction approach and E-CVFDT algorithm. Section 3 explains the proposed approach, Section 4 shows the experimental results of the proposed work, and lastly Section 5 concludes.

The main task in decision tree induction is to determine the best splitting attribute from the sample of data because it is impossible to get it from the infinite size of the stream. In the literature, there are various approaches that ensure that the best attribute chosen from the sample of data is the same as the best attribute chosen from the whole stream with some high probability.

In this context, P. Domingo and G. Hulten [3] introduced the commonly used algorithm the “hoeffding tree,” which is based on the hoeffding theorem [4].

Theorem 1. If X₁, X₂ … X_n are independent random variables and a_i ≤ X_i ≤ b_i where 1 ≤ i ≤ n, then:

But later on, researchers showed that this theorem violates the split measure function. In [5] Rutkowski et al. proposed McDiarmid's inequality instead of the hoeffding bound. McDiarmid's inequality states that:

then, with the probability , attribute is better split than attribute .

In this chapter, we refer to the dsCART algorithm [18], where the authors proposed a different theorem for making the best split attribute.

Theorem 2. If there are two attributes a^x and a^y, then let ΔG be the difference between the Gini gain function for a^x and a^y, i.e.:

If satisfies for

then is greater than Giniay with probability , i.e., is a better split attribute than .

Theorem 2 allows the authors to design CART for a data stream [18]. In this algorithm, the authors introduced a tie-breaking mechanism that depends on the parameter . It ensures the split of the node after some fixed number of examples even if the best two attributes do not satisfy Eq. (10.9). This mechanism is used to avoid the blocking of splitting the node permanently due to the comparable values of Gini gain for these attributes, i.e., the decision to split the considered node is determined by the conditions:

After satisfaction of the foregoing condition, the node is split on an attribute having maximum gain value among the best two attributes and .

In the dsCART algorithm, the authors do not consider the concept drift issue. Thus we used the E-CVFDT approach [8] to the dsCART algorithm [18] to get much better results.

In E-CVFDT, the examples that will participate in the Gini gain calculation are cached. The caching system is helpful in reducing the cost required for the computation. E-CVFDT considers three types of drifts, i.e., accidental, gradual, and instantaneous concept drifts. In the case of an accidental concept drift where the probabilities appear small, a cache mechanism is used to increase the performance efficiency. This algorithm puts all the examples in an array “discard.” When this array is full, then all the examples are sent back in the process of decision tree creation. In the case of gradual concept drift where the concept drift occurs in an evolving style, regrouping of the evolving data is done into the memory, i.e., the new concept examples are delayed while original concepts are used for the Gini calculation first. This classifies the same concept examples first and avoids the complex distribution of an evolving data stream. To handle the instantaneous concept drift where the new concept arrives instantaneously and the old concept disappears, the traditional CVFDT suits well (Table 10.1).

In E-CART, the sample of an example first checks for the type of concept drift. A similar type of conceptual data is mined first. Thus on the basis of type of concept drift, mining is performed. Three types of concept drift are taken into consideration, i.e., accidental, gradual, and instantaneous concept drifts. A sliding window concept is used. The sample of examples is collected within a window. The size of the window, i.e., the number of examples in a window, is specified by the user. When the sample arrives into the window, three possibilities could occur. If the stream is of accidental concept drift type, then the stream of new concept will be discarded because their occurrence probability was very low and the old concept stream is sent for the Gini calculation. If the stream is of gradual type, then the new concept is cached into another array and used for the Gini calculation after some delay. In case of instantaneous concept drift, the decision tree is built on the basis of the arrived concept.

Thus this algorithm is better than the Gaussian decision tree (GDT) [19], because in the case of GDT, for every new concept, a new decision tree is built, which is useless in case of noise, i.e., accidental concept drift. Thus it computes the stream in an efficient and effective manner.

The E-CART works as follows:

Instead of computing the splitting function for each and every example having a new concept, it checks the type of concept drift occurring in the data stream.

If the stream scenario belongs to an accidental concept drift like noise, then the computation will not be recomputed for this new concept. The decision tree will result on the basis of the old concept.

If the gradual concept drift occurs in the stream, then both the concepts are of importance. In that case, a cache system is used. The new concept is cached into an array and the size of the array is specified by the user. When the size fulfills the user-specified condition, then this new concept is encountered for the calculation of splitting attribute function.

In case of instantaneous concept drift, the algorithm simply builds the decision tree on the basis of a new concept arriving there. It works similar to the GDT data stream mining technique (Table 10.2).

 Let W be the window of examples of different concepts
 Let S(i) be the sample-array of each example
 If |W| > w then
Add each sample S(j) to accept_array
If |W| < w and n(w)<= n∗n_discard then
  Add each sample S(j) to cached_array and used later.
If |W|<w and n(w)>=n∗n_discard then
  Remove this example from the primary processing.
Return accept_array

Let T be a decision tree with single leaf (the root node) X0
Let A0 = A
For each attribute
 For each attribute value λ of class c
  The number of examples are
For each example e in accept_array
 Sort e in leaf
 For each attribute
  For each attribute value λ of class c
   If value ofand class is c then
   Increment
Label the leaf nodewith majority class
If the examples atdoes not belong to same class, then compute the splitting attribute
For each attribute
 For each partition of, i.e. left setand right

  Computeusing

Computeby using theorem 2
 then,
  Makeas an internal node by replacing
  For both the branches left and right of the split
   Add a new leafand letat
   For each valuefor attributeand class = c,
    end=end+1
Return T.

Here, is the number of elements from the c th class of leaf with attribute value λ for attribute . is the Gini gain computed for attribute at leaf L_q.

The data examples generated from the hyperplane generator are similar to the gradual concept drift data stream. By adjusting the data generation rate, the instantaneous concept drift stream is tested, whereas the examples generated from the SEA generator are similar to the instantaneous concept drift.

Computation time for building the decision tree by using the E-CART is calculated for the hyperplane generator and SEA generator and compared with the CVFDT algorithm. It is observed that the computation time for the SEA generator is very similar to the CVFDT approach, whereas in the case of the hyperplane generator, E-CART takes less computation time for building the decision tree classifier than CVFDT.

Table 10.3 represents the time taken by the CVFDT algorithm and the E-CART algorithm for the data examples generated by the SEA generator. The comparison is visualized in Fig. 10.2.

This graph shows that the performance of the E-CART is somewhat similar to the CVFDT approach given by G. Hulten and P. Domingos [7]. As said earlier, in the instantaneous concept drift data stream, the concept drift occurs instantaneously and then the older concept disappears immediately. When the new concept arrives in the stream, decision tree construction starts immediately rather than caching it as is done in the CVFDT approach to decision tree construction to mine the data stream.

Table 10.4 represents the comparison of E-CART and CVFDT approach in terms of performance efficiency on the dataset generated by the hyperplane generator. The computation time decreases with the proposed approach compared to the CVFDT.

The tabulated data shown in Table 10.4 is visualized in Fig. 10.3.

The graph represented in Fig. 10.3 shows that the computation time decreases by using the proposed approach compared to the CVFDT. This happens because the proposed approach E-CART takes the concept drift into consideration. Thus in case of accidental concept drift, it ignores the new concept because the probability of the new concept appearing is very small. Thus rebuilding the decision tree for such a new concept is totally inefficient. Generally, the accidental concept drifts result in case of any noise in the data stream. In case of gradual concept drift, the cached system is used by the proposed approach, which makes it more efficient. This proposed approach results in 93.23% accuracy with the data size of 1,000,000,000 examples as compared to the accuracy of the CART decision tree approach proposed by Rutkowski et al., which is 90%. Accuracy visualization is shown in Fig. 10.4.

This graph shows an accuracy of 93.23%. It shows that the proposed approach for data stream mining is more efficient and better than the previous approaches.