Sage Journals: Discover world-class research

Abstract

Many real-world situations constantly generate concept-drifting data streams at high speed. These situations demand adaptive algorithms able to learn online in accordance with the most recent target function (concept). This paper presents Online Adaptive Classifier Ensemble, a new ensemble algorithm able to learn from concept-drifting data streams. The proposed algorithm uses a change detection mechanism in each base classifier in order to handle possible changes in the underlying target function. Each base classifier in the ensemble can alternate between three different stages during the learning process: stable, warning and drift. In a stable stage, the underlying target function is supposed to remain constant, and the corresponding base classifier is updated with each incoming training instance. In a warning stage, a possible change in the target function can be starting to occur, and an alternative base classifier is created and trained together with the other base classifiers. The alternative classifier is added to the ensemble if the drift stage is reached. The new algorithm is compared with various state-of-the-art ensemble algorithms for online learning. Empirical studies show that this proposal is an effective alternative for learning from non-stationary data streams.

Keywords

Classifier ensemble concept drift data stream massive data online learning

Get full access to this article

View all access options for this article.

References

Baena-Garcia

Campo-Avila

J.D.

Fidalgo

Bifet

Gavalda

, and Morales-Bueno

, Early drift detection method. 2006.

Bifet

Frank

Holmes

and Pfahringer

, Accurate Ensembles for Data Streams: Combining Restricted Hoeffding Trees using Stacking, In ACML, 2010, pp. 225–240.

Bifet

and Gavalda

, Learning from time-changing data with adaptive windowing, In SIAM International Conference on Data Mining, 2007.

Bifet

Holmes

Kirkby

and Pfahringer

, Moa: Massive online analysis, The Journal of Machine Learning Research 11 (2010), 1601–1604.

Bifet

Holmes

and Pfahringer

, Leveraging bagging for evolving data streams, In Machine learning and knowledge discovery in databases, 2010, pp. 135–150. Springer.

Bifet

Holmes

Pfahringer

Kirkby

and Gavalda

, New ensemble methods for evolving data streams, In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, 2009, pp. 139–148, ACM.

Breiman

, Bagging predictors, Machine Learning 24(2) (1996), 123–140.

Brzezinski

and Stefanowski

, Reacting to Different Types of Concept Drift: The Accuracy Updated Ensemble Algorithm, IEEE Transactions on Neural Networks and Learning Systems 25(1) (Jan. 2014), 81–94.

Cestnik

, Estimating probabilities: a crucial task in machine learning, In ECAI, volume 90, 1990, pp. 147–149.

10.

Clark

and Niblett

, The CN2 induction algorithm, Machine Learning 3(4) (1989), 261–283.

11.

Deckert

, Batch weighted ensemble for mining data streams with concept drift, In Foundations of Intelligent Systems, 2011, pp. 290–299. Springer.

12.

Del Campo Ávila

, Nuevos enfoques en aprendizaje incremental, 2007.

13.

Domingos

and Pazzani

, On the optimality of the simple Bayesian classifier under zero-one loss, Machine Learning 29(2–3) (1997), 103–130.

14.

Ferrer Troyano

F.J.

Aguilar-Ruiz

J.S.

and Santos

J.C.R.

, Incremental Rule Learning and Border Examples Selection from Numerical Data Streams, J. UCS 11(8) (2005), 1426–1439.

15.

Freund

and Schapire

R.E.

, A Short Introduction to Boosting, In In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, 1999, pp. 1401–1406. Morgan Kaufmann,

16.

Frias-Blanco

Campo-Avila

J.D.

Ramos-Jimenez

Morales-Bueno

Ortiz-Diaz

and Caballero-Mota

, Online and Non-Parametric Drift Detection Methods Based on Hoeffding Bounds, IEEE Transactions on Knowledge and Data Engineering 27(3) (Mar. 2015), 810–823.

17.

Frías-Blanco

del Campo-Ávila

Ramos-Jiménez

Carvalho

A.C.

Ortiz-Díaz

and Morales-Bueno

, Online adaptive decision trees based on concentration inequalities, Knowledge-Based Systems 104 (2016), 179–194.

18.

Frías Blanco

del Campo Ávila

Ramos Jiménez

Morales Bueno

Ortiz Díaz

and Caballero Mota

, Aprendiendo con detección de cambio online, Computación y Sistemas 18(1) (2014), 169–183.

19.

Frías-Blanco

Verdecia-Cabrera

Ortiz-Díaz

and Carvalho

, Fast adaptive stacking of ensembles, In Proceedings of the 31st Annual ACM Symposium on Applied Computing, 2016, pp. 929–934, ACM.

20.

Gama

and Kosina

, Tracking recurring concepts with meta-learners, In Progress in Artificial Intelligence, 2009, pp. 423–434. Springer.,

21.

Gama

Medas

Castillo

and Rodrigues

, Learning with drift detection, In Advances in artificial intelligence, 2004, pp. 286–295. Springer.

22.

Gama

and Rodrigues

, Learning from Data Streams: Processing Techniques in Sensor Networks, Springer-Verlag, 1 edition, 2007.

23.

Gama

Rodrigues

P.P.

and Sebasti ao

, Evaluating algorithms that learn from data streams, In Proceedings of the 2009 ACM symposium on Applied Computing, 2009, pp. 1496–1500, ACM.

24.

Gama

Sebasti ao

and Rodrigues

, On evaluating stream learning algorithms, Machine Learning 90(3) (2013), 317–346.

25.

Gama

Zliobaite

Bifet

Pechenizkiy

and Bouchachia

, A Survey on Concept Drift Adaptation, ACM Comput. Surv. 46(4) (Mar. 2014), 44:1–44:37.

26.

Harries

Nsw-csetr

and Wales

N.S.

, SPLICE-2 Comparative Evaluation: Electricity Pricing, Technical report, 1999.

27.

Hulten

Spencer

and Domingos

, Mining time-changing data streams, In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, 2001, pp. 97–106, ACM.

28.

Kolter

J.Z.

and Maloof

M.A.

, Dynamic weighted majority: An ensemble method for drifting concepts, The Journal of Machine Learning Research 8 (2007), 2755–2790.

29.

Kuncheva

L.I.

, Combining pattern classifiers: methods and algorithms, John Wiley & Sons, 2004.

30.

Lam

and Suen

, Application of majority voting to pattern recognition: an analysis of its behavior and performance, IEEE Transactions on Systems, Man, and Cybernetics – Part A: Systems and Humans 27(5) (1997), 553–568.

31.

Langley

Iba

and Thompson

, An analysis of Bayesian classifiers, In Aaai, volume 90, 1992, pp. 223–228.

32.

Minku

L.L.

White

A.P.

and Yao

, The impact of diversity on online ensemble learning in the presence of concept drift, Knowledge and Data Engineering, IEEE Transactions on 22(5) (2010), 730–742.

33.

Minku

L.L.

and Yao

, DDD: A new ensemble approach for dealing with concept drift, Knowledge and Data Engineering, IEEE Transactions on 24(4) (2012), 619–633.

34.

Montgomery

D.C.

, Introduction to statistical quality control, John Wiley & Sons, 2007.

35.

Ortiz Diaz

del Campo-Avila

Ramos-Jimenez

Frias Blanco

Caballero Mota

, A. Mustelier Hechavarria and R. Morales-Bueno, Fast Adapting Ensemble: A New Algorithm for Mining Data Streams with Concept Drift, The Scientific World Journal, 2014.

36.

Oza

N.C.

and Russell

, Online Bagging and Boosting, in: Jaakkola

and Richardson

, editors, Eighth International Workshop on Artificial Intelligence and Statistics, pp. 105–112, Key West, Florida. USA, (Jan. 2001). Morgan Kaufmann.

37.

Pazzani

M.J.

, Searching for dependencies in Bayesian classifiers, In Learning from Data, 1996, pp. 239–248. Springer.

38.

Ross

G.J.

Adams

N.M.

Tasoulis

D.K.

and Hand

D.J.

, Exponentially weighted moving average charts for detecting concept drift, Pattern Recognition Letters 33(2) (2012), 191–198.

39.

Stanley

K.O.

, Learning concept drift with a committee of decision trees, Informe tecnico: UT-AI-TR-03-302, Department of Computer Sciences, University of Texas at Austin, USA, 2003.

40.

Street

W.N.

and Kim

, A Streaming Ensemble Algorithm (SEA) for Large-scale Classification, In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’01, 2001, pp. 377–382, New York, NY, USA, ACM.

41.

Wang

Fan

P.S.

and Han

, Mining concept-drifting data streams using ensemble classifiers, In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, 2003, pp. 226–235, ACM.

42.

Widmer

and Kubat

, Learning in the presence of concept drift and hidden contexts, Machine Learning 23(1) (1996), 69–101.

43.

Yue

Guojun

and Chunnian

, Mining concept drifts from data streams based on multi-classifiers, In Advanced Information Networking and Applications Workshops, 2007, AINAW’07. 21st International Conference on, volume 2, 2007, pp. 257–263. IEEE.

44.

Zliobaite

, Learning under concept drift: an overview, Technical report, Overview, Technical report, Vilnius University, 2009 techniques, related areas, applications Subjects: Artificial Intelligence, 2009.