Back

A streaming ensemble algorithm (SEA) for large-scale classification

W. StreetYongSeog Kim

article2001KDD1,355 citations

Proposes a fast, constant-memory streaming ensemble algorithm that processes continuous data chunks and uses a targeted replacement heuristic to match batch classifier accuracy while rapidly adapting to concept drift.

Listen

Modern organizations collect massive volumes of data at rates reaching millions of records per day, creating significant challenges for traditional machine learning methods. Standard classification algorithms require reading all data into memory at once and struggle when business conditions or customer behaviors change over time—a phenomenon known as concept drift. Existing ensemble methods, such as bagging and boosting, enhance predictive accuracy but rely on repeated data resampling, making them impractical for large-scale and streaming data environments.

The article demonstrates and evaluates the Streaming Ensemble Algorithm, a scalable framework designed to classify continuous data streams. The primary objective is to show that combining multiple decision trees trained sequentially on small, fixed chunks of data can achieve predictive accuracy comparable to a single model trained on all data, while operating with constant memory, a single data pass, and rapid adaptability to shifting concepts.

To assess the framework, the authors conducted empirical experiments across three real-world datasets spanning demographic census records (over 44,000 cases), cancer survival outcomes (over 37,000 cases), and web browsing clickstreams (over 32,000 cases). They also tested an artificial dataset containing 60,000 records structured with four distinct concept blocks and intentional classification noise. The algorithm processed data in batches of 500 or 1,000 instances, maintaining a fixed pool of 25 unpruned decision trees and replacing underperforming members based on how well they classified points where the broader ensemble was nearly undecided.

The findings confirm that the streaming ensemble achieves classification accuracy comparable to single decision trees trained on full datasets, typically performing between single pruned and unpruned models. On datasets reflecting abrupt concept drift, the ensemble adapted and recovered original accuracy levels rapidly by replacing obsolete trees, whereas single trees recovered very slowly. Maintaining roughly 20 to 25 classifiers proved optimal for generalization, and the heuristic replacement strategy consistently improved model quality after filling the initial pool (improving accuracy in up to 90% of evaluation runs). Additionally, the algorithm's observed error on incoming batches provided a reliable, real-time estimate of overall testing performance.

These results show that organizations can deploy predictive modeling on continuous data streams without expensive high-memory hardware or disruptive retraining cycles. By bounding memory usage and processing records sequentially, the method lowers infrastructure costs, mitigates the risk of decision lag in volatile environments, and supports any-time learning where reliable predictions are accessible even if processing halts early.

Organizations handling high-velocity data streams should consider implementing this fixed-size ensemble architecture for real-time decisioning systems. Key trade-offs must be evaluated: smaller batch sizes (such as 500 instances) offer faster adaptation to changing trends but may increase sensitivity to noise, whereas larger batches offer stability. Future developmental work should explore algorithm parallelization and enhanced diversity mechanisms, such as integrating heterogeneous model types or maintaining slightly larger candidate pools to optimize ensemble selection.

Confidence in the core findings is strong for binary classification problems involving moderate data chunk sizes. However, stakeholders should exercise caution in environments characterized by extreme data noise or when deploying very small batch sizes (100 to 200 instances), where individual classifier quality degrades. Further validation remains necessary for multi-class targets and distributed computing architectures.

Management Sciences DepartmentUniversity of Iowaboostingconcept driftsensemble classifiersstreaming ensemble algorithmlarge-scale classificationconcept drift
Street et al (2001).pdf
  • Paper: Mining concept-drifting data streams using ensemble classifiers, Haixun Wang et al. (2003). Directly builds on chunk-based streaming ensembles by introducing accuracy-based dynamic weighting of ensemble members on concept-drifting streams.
  • Paper: Learning with Drift Detection, João Gama et al. (2004). Develops explicit statistical drift-detection mechanisms to trigger retraining, providing a complementary approach to SEA's heuristic replacement strategy.
  • Paper: Learning from Time-Changing Data with Adaptive Windowing, Albert Bifet et al. (2007). Introduces automated adaptive windowing (ADWIN) to dynamically scale historical windows for learning under concept drift without fixed chunk sizes.
  • Paper: MOA: Massive Online Analysis, A. Bifet et al. (2010). Presents the Massive Online Analysis (MOA) stream-mining benchmark framework, which standardizes the evaluation of streaming ensemble algorithms like SEA.
  • Paper: Learning under Concept Drift: A Review, Jie Lu et al. (2019). Surveys the taxonomy of concept drift detection and adaptation techniques, placing chunk-based ensemble architectures into modern context.
Cover for A streaming ensemble algorithm (SEA) for large-scale classification

Abstract

Ensemble methods have recently garnered a great deal of attention in the machine learning community. Techniques such as Boosting and Bagging have proven to be highly effective but require repeated resampling of the training data, making them inappropriate in a data mining context. The methods presented in this paper take advantage of plentiful data, building separate classifiers on sequential chunks of training points. These classifiers are combined into a fixed-size ensemble using a heuristic replacement strategy. The result is a fast algorithm for large-scale or streaming data that classifies as well as a single decision tree built on all the data, requires approximately constant memory, and adjusts quickly to concept drift.

Topics

boostingconcept driftsensemble classifiersstreaming dataensemble algorithmsbase learnerssupport vector machine

Keywords

streaming ensemble algorithmlarge-scale classificationconcept driftensemble methodsdecision treesclassification noiseensemble constructionfeature selection

Table of Contents

  • 1. INTRODUCTION
  • 2. METHODS
  • 3. EXPERIMENTAL RESULTS
  • 3.1 Accuracy
  • 3.2 Concept drift
  • 4. DISCUSSION AND CONCLUSIONS
  • Acknowledgements
  • 5. REFERENCES

Knowls

  1. Knowl 1 — Streaming Ensemble Algorithm for Large-Scale Data

    algorithm

    The Streaming Ensemble Algorithm (SEA) processes sequential, chunked data streams under constant memory and single-pass constraints. The algorithm maintains an ensemble EE containing at most KK base classifiers (specifically, unpruned decision trees such as C4.5). For each incoming block of dd data points, the existing ensemble and a newly trained candidate classifier are evaluated on the new block, and a heuristic quality metric determines whether the new classifier replaces an existing member in EE.

    Input: Data stream SS, chunk size dd, maximum ensemble size KK (default K=25K = 25)
    Output: Ensemble of classifiers EE
    E←∅E \leftarrow \emptyset
    Cprev←nullC_{\text{prev}} \leftarrow \text{null}
    while data points are available from SS do
        Read dd data points from SS to form chunk DD
        Train base classifier CcurrC_{\text{curr}} on DD
        if Cprev≠nullC_{\text{prev}} \neq \text{null} then
            Evaluate CprevC_{\text{prev}} on DD to compute Quality(Cprev)\text{Quality}(C_{\text{prev}})
            Evaluate each ensemble member Ej∈EE_j \in E on DD to compute Quality(Ej)\text{Quality}(E_j)
            if ∣E∣<K|E| < K then
                E←E∪{Cprev}E \leftarrow E \cup \{C_{\text{prev}}\}
            else
                Find Emin⁡=arg⁡min⁡Ej∈EQuality(Ej)E_{\min} = \arg\min_{E_j \in E} \text{Quality}(E_j)
                if Quality(Cprev)>Quality(Emin⁡)\text{Quality}(C_{\text{prev}}) > \text{Quality}(E_{\min}) then
                    E←(E∖{Emin⁡})∪{Cprev}E \leftarrow (E \setminus \{E_{\min}\}) \cup \{C_{\text{prev}}\}
                end if
            end if
        end if
        Cprev←CcurrC_{\text{prev}} \leftarrow C_{\text{curr}}
    end while
    return EE

    Predictions on novel instances are made by majority voting over all active classifiers in EE, with ties broken uniformly at random. Memory usage is strictly bounded by the storage of KK base classifiers plus a single batch buffer of size dd.

  2. Knowl 2 — Margin-Based Quality Metric for Streaming Ensemble Replacement

    model/method

    To decide whether a newly induced classifier TT should replace an existing ensemble member in ensemble EE, classifiers are evaluated on an unseen batch of data points DD. Rather than relying purely on classification accuracy, the scoring mechanism favors classifiers that correctly predict instances where the current ensemble prediction is close or uncertain, avoiding over-emphasis on noisy outliers.

    For a given instance x∈Dx \in D, let:

    • P1∈[0,1]P_1 \in [0, 1] be the fraction of ensemble votes received by the most-voted class,
    • P2∈[0,1]P_2 \in [0, 1] be the fraction of votes received by the second-most-voted class,
    • Pc∈[0,1]P_c \in [0, 1] be the fraction of ensemble votes received by the true class cc, and
    • PT∈[0,1]P_T \in [0, 1] be the fraction of ensemble votes received by the class predicted by candidate classifier TT.

    The quality adjustment ΔQ(T,x)\Delta Q(T, x) for instance xx is computed as follows:

    ΔQ(T,x)={+(1−∣P1−P2∣)if both E and T classify x correctly,+(1−∣P1−Pc∣)if T is correct but E is incorrect,−(1−∣Pc−PT∣)if T classifies x incorrectly.\Delta Q(T, x) = \begin{cases} +(1 - |P_1 - P_2|) & \text{if both } E \text{ and } T \text{ classify } x \text{ correctly}, \\ +(1 - |P_1 - P_c|) & \text{if } T \text{ is correct but } E \text{ is incorrect}, \\ -(1 - |P_c - P_T|) & \text{if } T \text{ classifies } x \text{ incorrectly}. \end{cases}

    The total quality score is accumulated over all x∈Dx \in D:

    Quality(T)=∑x∈DΔQ(T,x)\text{Quality}(T) = \sum_{x \in D} \Delta Q(T, x)

    This same metric is simultaneously computed for each existing ensemble classifier Ej∈EE_j \in E over the same chunk DD. If the ensemble is full and Quality(T)>min⁡Ej∈EQuality(Ej)\text{Quality}(T) > \min_{E_j \in E} \text{Quality}(E_j), the candidate TT replaces the lowest-scoring ensemble member.

  3. Knowl 3 — Empirical Design Guidelines for Streaming Decision Tree Ensembles

    model/method

    Systematic empirical evaluations of streaming ensemble parameters establish several core architectural principles for chunk-based ensemble classification:

    1. Ensemble Size: Generalization performance increases with ensemble size up to approximately 20 to 25 component classifiers, after which performance plateaus.
    2. Decision Tree Pruning: Using unpruned decision trees as base classifiers yields superior ensemble accuracy compared to pruned trees, despite individual unpruned trees having lower standalone accuracy. Overtraining individual base trees generates the diversity necessary for effective committee voting.
    3. Aggregation Schemes: Simple unweighted majority voting performs as well as or better than confidence-weighted voting, accuracy-weighted voting, or gated voting (where auxiliary meta-classifiers predict whether an individual classifier will be correct on a given instance).
    4. Chunk Size Sensitivity: Base models trained on moderate chunk sizes (d=500d = 500 or d=1000d = 1000 points) substantially outperform models trained on smaller chunks (d=100d = 100 or d=200d = 200 points), demonstrating that individual base classifiers must achieve sufficient capacity to overfit their local data subsets.

  4. Knowl 4 — Synthetic Concept Drift Dataset Specification and Class Distributions

    data/table

    A standard synthetic benchmark for evaluating classification algorithms under abrupt concept drift consists of 60,000 data points generated in a three-dimensional feature space [0,10]3[0, 10]^3. Features f1,f2∈[0,10]f_1, f_2 \in [0, 10] are informative, while f3∈[0,10]f_3 \in [0, 10] is irrelevant noise. The stream is divided into four sequential blocks of 15,000 points each, where the true concept is defined by the linear boundary f1+f2≤θf_1 + f_2 \le \theta. The threshold θ\theta abruptly shifts between blocks:

    • Block 1: θ=8\theta = 8
    • Block 2: θ=9\theta = 9
    • Block 3: θ=7\theta = 7
    • Block 4: θ=9.5\theta = 9.5

    Each block contains 10% randomly injected class noise. For each block, 12,500 instances form the training stream (50,000 total) and 2,500 instances are reserved for evaluation (10,000 total).

    Training Set Test Set
    Block Class 1 % Class 2 % Class 1 % Class 2 %
    Block 1 (θ=8\theta=8) 3,602 28.8 8,898 71.2 761 30.4 1,739 69.6
    Block 2 (θ=9\theta=9) 4,473 35.8 8,027 64.2 891 35.6 1,609 64.4
    Block 3 (θ=7\theta=7) 2,758 22.1 9,742 77.9 553 22.1 1,947 77.9
    Block 4 (θ=9.5\theta=9.5) 4,995 40.0 7,505 60.0 1,031 41.2 1,469 58.8
    Total 15,828 31.7 34,172 68.3 3,236 32.4 6,764 67.6

    This benchmark tests an algorithm's ability to recover from sudden shifts in class balance and decision boundary orientation.

  5. Knowl 5 — Adaptation Dynamics and Online Error Tracking Under Concept Drift

    empirical result

    When evaluated on the 4-block synthetic concept drift benchmark with abrupt threshold shifts θ∈{8,9,7,9.5}\theta \in \{8, 9, 7, 9.5\}:

    1. Recovery Speed: Following an abrupt shift in the underlying concept, both single decision trees and SEA experience an immediate surge in error rate. However, SEA replaces outdated base classifiers with new ones trained on the current distribution, returning to baseline error rates (approximately 10% error, matching the injected noise floor) within a few subsequent blocks. In contrast, a cumulative single decision tree trained on all historical data recovers much more slowly or fails to recover.
    2. Chunk Size Trade-off: Ensembles using d=500d = 500 instances per tree adapt to new concepts faster than ensembles with d=1000d = 1000 instances per tree, illustrating a trade-off between concept agility and individual model stability.
    3. Online Generalization Tracking: The pre-update error measured on the incoming chunk DD prior to updating the ensemble ("train error") closely tracks the true generalization error measured on dedicated stationary test sets. This provides an accurate online estimate of generalization error without requiring separate labeled validation streams.

  6. Knowl 6 — Classification Accuracy and Replacement Effectiveness on Stationary Datasets

    empirical result

    On large stationary real-world classification benchmarks (Adult Census with 44,848 instances and 14 features; SEER Breast Cancer survival with 37,715 instances; Anonymous Web Browsing with 32,710 instances and 296 features), the Streaming Ensemble Algorithm demonstrates:

    1. Competitive Generalization: SEA achieves classification accuracy comparable to single decision trees trained on the entire cumulative dataset in batch mode. The ensemble's error rate typically lies between that of a single unpruned tree and a single pruned tree, and on the SEER dataset slightly outperforms the single pruned tree.
    2. Noise Susceptibility: On the Adult dataset (known for classification noise), the single pruned tree significantly outperformed full ensembles (alpha=0.05\\alpha = 0.05) on 27% of evaluation intervals for d=1000d = 1000 and on 83% for d=500d = 500, indicating that the margin-based replacement heuristic retains some sensitivity to label noise.
    3. Replacement Success Rate: After filling the initial 25-tree ensemble, the replacement strategy successfully improved ensemble accuracy on subsequent data chunks in 90% of test intervals on Adult, 84% on SEER, and 58% on Anonymous Web Browsing.

Coverage note — All primary contributions—including the streaming ensemble framework, margin-based replacement heuristic, design parameter analyses, synthetic concept drift benchmark, and empirical evaluations across stationary and drifting data—are covered. General background on prior ensemble methods (e.g., standard Bagging/Boosting) and prospective future work on parallelization and evolutionary search were omitted.

References

  1. 1.E. Bauer and R. Kohavi. An empirical comparison of voting classification algorithms: Bagging, boosting, and variants. Machine Learning, 36:105-142, July-August 1999.
  2. 2.C. L. Blake and C. J. Merz. UCI repository of machine learning databases [http://www.ics.uci.edu/~mlearn/MLRepository.html], 1998. University of California, Irvine, Department of Information and Computer Sciences.
  3. 3.J. Breese, D. Heckerman, and C. Kadie. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, Madison, WI, July 1998.
  4. 4.L. Breiman. Bagging predictors. Machine Learning, 24(2):123-140, 1996.
  5. 5.L. Breiman. Arcing classifiers. Annals of Statistics, 26(3):801-849, 1998.
  6. 6.C. L. Carter, C. Allen, and D. E. Henson. Relation of tumor size, lymph node status, and survival in 24,740 breast cancer cases. Cancer, 63:181-187, 1989.
  7. 7.P. K. Chan and S. J. Stolfo. On the accuracy of meta-learning for scalable data mining. Journal of Intelligent Information Systems, 8:5-28, 1997.
  8. 8.P. Domingos and G. Hulten. Mining high-speed data streams. In Proceedings of the Sixth International Conference on Knowledge Discovery and Data Mining, pages 71-80. ACM Press, 2000.
  9. 9.U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, editors. Advances in Knowledge Discovery and Data Mining. AAAI Press / The MIT Press, 1996.
  10. 10.Y. Freund and R. Schapire. Experiments with a new boosting algorithm. In Proceedings of the Thirteenth International Conference on Machine Learning, pages 148-156, 1996.
  11. 11.G. Fung and O. L. Mangasarian. Data selection for support vector machine classifiers. In Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 64-70. ACM Press, 2000.
  12. 12.J. Gehrke, V. Ganti, R. Ramakrishnana, and W.-Y. Loh. BOAT - Optimistic decision tree construction. In Proceedings of the 1999 SIGMOD Conference, Philadelphia, PA, 1999.
  13. 13.L. O. Hall, K. W. Bowyer, W. P. Kegelmeyer, T. E. Moore, and C. Chao. Distributed learning on very large data sets. In Workshop on Distributed and Parallel Knowledge Discovery (KDD-00), pages 79-84, Aug 2000.
  14. 14.R. A. Jacobs. Methods for combining experts' probability assessments. Neural Computation, 7:867-888, 1995.
  15. 15.R. Kohavi. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, pages 202-207, 1996.
  16. 16.O. L. Mangasarian and D. R. Musicant. Massive support vector regression. Machine Learning, to appear.
  17. 17.D. Opitz. Feature selection for ensembles. In Proceedings of the Sixteenth National Conference on Artificial Intelligence (AAAI), pages 379-384, 1999.
  18. 18.D. Opitz and R. Maclin. Popular ensemble methods: An empirical study. Journal of Artificial Intelligence Research, 11:169-198, 1999.
  19. 19.J. R. Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, San Mateo, CA, 1993.
  20. 20.R. Schapire. The strength of weak learnability. Machine Learning, 5(2):197-227, 1990.
  21. 21.P. Sollich and A. Krogh. Learning with ensembles: How overfitting can be useful. In D. S. Touretzky, M. C. Mozer, and M. E. Hasselmo, editors, Advances in Neural Information Processing Systems, volume 8. MIT Press, 1996.
  22. 22.G. Widmer and M. Kubat. Learning in the presence of concept drift and hidden contexts. Machine Learning, 23:69-101, 1996.

Citation

MLA
Street, W. N., and Y. Kim. “A Streaming Ensemble Algorithm (SEA) for Large-scale Classification”. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2001, pp. 377–82, https://doi.org/10.1145/502512.502568.
APA
Street, W. N., & Kim, Y. (2001). A streaming ensemble algorithm (SEA) for large-scale classification. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 377–382. https://doi.org/10.1145/502512.502568
Chicago
Street, W. N., and Y. Kim. 2001. “A Streaming Ensemble Algorithm (SEA) for Large-scale Classification”. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 377–82. https://doi.org/10.1145/502512.502568.
Harvard
Street, W.N. and Kim, Y. (2001) “A streaming ensemble algorithm (SEA) for large-scale classification”, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp. 377–382. Available at: https://doi.org/10.1145/502512.502568.
Vancouver
1. Street WN, Kim Y (2001) A streaming ensemble algorithm (SEA) for large-scale classification. In: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 377–382

BibTeX

@inproceedings{Street_2001, series={KDD01}, title={A streaming ensemble algorithm (SEA) for large-scale classification}, url={http://dx.doi.org/10.1145/502512.502568}, DOI={10.1145/502512.502568}, booktitle={Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining}, publisher={ACM}, author={Street, W. Nick and Kim, YongSeog}, year={2001}, month=Aug, pages={377–382}, collection={KDD01} }
Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF