Incremental Rule-Based Learners for Handling Concept Drift: An Overview

Deckert, Magdalena

doi:10.2478/v10209-011-0020-y

Abstract

Learning from non-stationary environments is a very popular research topic. There already exist algorithms that deal with the concept drift problem. Among them there are online or incremental learners, which process data instance by instance. Their knowledge representation can take different forms such as decision rules, which have not received enough attention in learning with concept drift. This paper reviews incremental rule-based learners designed for changing environments. It describes four of the proposed algorithms: FLORA, AQ11-PM+WAH, FACIL and VFDR. Those four solutions can be compared on several criteria, like: type of processed data, adjustment to changes, type of the maintained memory, knowledge representation, and others.

References

[1] An A., Learning Classification Rules from Data, Computers and Mathematics with Applications, vol. 45, p. 737-748, 2003.10.1016/S0898-1221(03)00034-8
Search in Google Scholar
[2] Baena-Garcia M., Del Campo-Avila J., Fidalgo R., Bifet A., Early Drift Detection Method, Proceedings of the 4th ECML PKDD International Workshop on Knowledge Discovery from Data Streams, p. 77-86, Berlin, Germany, 2006.
Search in Google Scholar
[3] Bakker J., Pechenizkiy M., Food Wholesales Prediction: What is Your Baseline?, Proceedings of the 18th Symposium on Methodologies for Intelligent Systems, ISMIS 2009, Prague, Czech Republic, LNCS, vol. 5722, p. 493-502, 2009.
Search in Google Scholar
[4] Bifet A., Holmes G., Pfahringer B., Kranen P., Kremer H., Jansen T., Seidl T.: MOA: Massive Online Analysis a Framework for Stream Classification and Clustering, Workshop on Applications of Pattern Analysis, HaCDAIS, 2010.
Search in Google Scholar
[5] Błaszczyński J., Stefanowski J., Zaja̧c M., Ensembles of Abstaining Classifiers Based on Rule Sets, Proceedings of the 18th International Symposium on Methodologies for Intelligent Systems, ISMIS 2009, Prague, Czech Republic, LNCS, vol. 5722, p. 382-391, 2009.
Search in Google Scholar
[6] Cendrowska J., PRISM An Algorithm for Inducing Modular Rules, International Journal Man-Machine Studies, vol. 27, p. 349-370, 1987.10.1016/S0020-7373(87)80003-2
Search in Google Scholar
[7] Cestnik B., Estimating Probabilities: A Crucial Task in Machine Learning, Pro- ceedings ECAO 1990, Stockholm, Sweden, 1990.
Search in Google Scholar
[8] Clark P, Boswell R., Rule Induction with CN2: some recent improvement, Pro- ceedings of 5th European Working Session on Learning, ESWL 1991, Porto, Portugal, p. 151-163, 1991.10.1007/BFb0017011
Search in Google Scholar
[9] Clark P., Niblett T., The CN2 Induction Algorithm, Machine Learning, vol. 3, p. 261-283, 1989.10.1007/BF00116835
Search in Google Scholar
[10] Deckert M., Batch Weighted Ensemble for Mining Data Streams with Concept Drift, Proceedings of the 19th International Symposium on Methodologies for Intelligent Systems, ISMIS 2011, Warsaw, Poland, LNCS, vol. 6804, p. 290-299, 2011.
Search in Google Scholar
[11] Deckert M., Stefanowski J., Comparing Block Ensembles for Data Streams with Concept Drift, Proc. of Workshop Mining Complex and Stream Data, ADBIS 2012, Poznań, Poland, AISC, vol. 185, p. 69-78, 2012.10.1007/978-3-642-32518-2_7
Search in Google Scholar
[12] Domingos P., Hulten G., Mining High-Speed Data Streams, Proceedings of the KDD 2000, ACM Press, p. 71-80, 2000.10.1145/347090.347107
Search in Google Scholar
[13] Ferrer-Troyano F.J., Aguilar-Ruiz J.A., Riquelme J.C., Incremental Rule Learning and Border Examples Selection from Numerical Data Streams, Journal of Universal Computer Science, vol. 11(8), p. 1426-1439, 2005.
Search in Google Scholar
[14] Ferrer-Troyano F.J., Aguilar-Ruiz J.A., Riquelme J.C., Data Streams Classification by Incremental Rule Learning with Parametrized Generalization, Proceed- ings of ACM Symposium on Applied Computing 2006, SAC 2006, p. 657-661, ACM, 2006.10.1145/1141277.1141428
Search in Google Scholar
[15] Fürnkranz J., Separate-and-Conquer Rule Learning, Artificial Intelligence Re- view, vol. 13, p.3-54, 1999.10.1023/A:1006524209794
Search in Google Scholar
[16] Fürnkranz J., Gamberger D., Lavrač N., Foundations of Rule Learning, Cognitive Technologies, 2012.10.1007/978-3-540-75197-7
Search in Google Scholar
[17] Gama J., Medas P., Castillo G., Rodrigues P., Learning with Drift Detection, Proceedings of Brazilian Symposium on Artificial Intelligence, SBIA 2004, LNAI, vol. 3171, p. 286-295, Springer-Verlag, 2004.
Search in Google Scholar
[18] Gama J., Knowledge Discovery from Data Streams, Chapman and Hall/CRC 2010.10.1201/EBK1439826119
Search in Google Scholar
[19] Gama J., Kosina P., earning Decision Rules from Data Streams, Proceedings of 22th International Joint Conference on Artificial Intelligence, IJCAI 11, vol. 2, p. 1255-1260, AAAI Press, 2011.
Search in Google Scholar
[20] Giraud-Carrier C., A Note on the Utility of Incremental Learning, AI Commu- nications, vol. 13, p. 215-223, 2000.
Search in Google Scholar
[21] Greco S., S lowiński R., Stefanowski J., Żurawski M., Incremental versus Nonincremental Rule Induction for Multicriteria Classification, Transactions on Rough Sets II, LNCS, vol. 3135, p. 33-53, 2004.
Search in Google Scholar
[22] Grzymala-Busse J.W., LERS - A System for Learning from Examples Based on Rough Sets, Intelligent Decision Support. Handbook of Applications and Advances of the Rough Sets Theory, p. 3-18, 1992.10.1007/978-94-015-7975-9_1
Search in Google Scholar
[23] Grzymala-Busse J.W., Selected Algorithms of Machine Learning from Examples, Fundamenta Informaticae, vol. 18, p. 193-207, 1993.10.3233/FI-1993-182-408
Search in Google Scholar
[24] Grzymala-Busse J.W., Managing Uncertainty in Machine Learning from Examples. Proceedings of 3rd International Symposium in Intelligent Systems, p. 70-84, 1994.
Search in Google Scholar
[25] Hulten G., Spencer L., Domingos P., Mining Time-changing Data Streams, Pro- ceedings of the KDD 2001, ACM Press, p. 97-106, 2001.10.1145/502512.502529
Search in Google Scholar
[26] Kosina P., Gama J., Very Fast Decision Rules for Multi-class Problems, Proceed- ings of the 2012 ACM Symposium on Applied Computing, New York, USA, p. 795-800, 2012.10.1145/2245276.2245431
Search in Google Scholar
[27] Kosina P., Gama J., Handling Time Changing Data with Adaptive Very Fast Decision Rules, Proceedings of the 2012 European conference on Machine Learn- ing and Knowledge Discovery in Databases, ECML/PKDD 2012, Bristol, United Kingdom, vol. 1, p. 827-842, 2012.10.1007/978-3-642-33460-3_58
Search in Google Scholar
[28] Kuncheva L. I., Classifier Ensembles for Changing Environments, Proceedings of 5th International Workshop on Multiple Classifier Systems, MCS 04, LNCS, vol. 3077, p. 1-15, Springer-Verlag, 2004.
Search in Google Scholar
[29] Kuncheva L. I., Classifier Ensembles for Detecting Concept Change in Streaming Data: Overview and Perspectives, Proceedings 2nd Workshop SUEMA 2008, ECAI 2008, p. 5-10, Patras, Greece, 2008.
Search in Google Scholar
[30] Maison R., Zakrzewicz M., Content-based Load Shedding in Multimedia Data Stream Management System, Foundations of Computing and Decision Sciences, vol. 37(2), p. 79-95, 2012.10.2478/v10209-011-0007-8
Search in Google Scholar
[31] Maloof M., Michalski R., Selecting Examples for Partial Memory Learning, Ma- chine Learning, vol. 41, p. 27-52, Kluwer Academic Publishers, 2000.10.1023/A:1007661119649
Search in Google Scholar
[32] Maloof M., Michalski R., Incremental Learning with Partial Instance Memory, Artificial Intelligence, vol. 154, p. 95-126, Elsevier, 2003.10.1016/j.artint.2003.04.001
Search in Google Scholar
[33] Maloof M., Incremental Rule Learning with Partial Instance Memory for Changing Concepts, Proceedings of the International Joint Conference on Neural Net- works 2003, IJCNN-03, vol. 4, p. 2764-2769, IEEE Press, 2003.
Search in Google Scholar
[34] Michalski R.S., A Theory and Methodology of Inductive Learning, Machine Learning: An Artificial Intelligence Approach, p. 83-134, 1983. 10.1016/B978-0-08-051054-5.50008-X
Search in Google Scholar
[35] Michalski R.S., Mozetic I., Hong J., Lavrac N., The AQ15 Inductive Learning System: An Overview and Experiments, Report 1260, Department of Computer Science, University of Illinois, 1986.
Search in Google Scholar
[36] Nishida K., Yamauchi K., Omori T., ACE: Adaptive Classifiers-Ensemble System for Concept-Drifting Environments, Multiple Classifier Systems, LNCS, vol. 3541, p. 176-185, 2005.
Search in Google Scholar
[37] Schlimmer J., Granger R., Incremental Learning from Noisy Data, Machine Learning, vol. 1(3), p. 317-357, 1986.10.1007/BF00116895
Search in Google Scholar
[38] Shannon C.E., A Mathematical Theory of Communication, Bell System Technical Journal, vol. 27(3), p. 379-423, 1948.10.1002/j.1538-7305.1948.tb01338.x
Search in Google Scholar
[39] Stefanowski J., The Rough Set Based Rule Induction Technique for Classification Problems. Proceedings of the 6th European Conference on Intelligent Techniques and Soft Computing, EUFIT-98, p. 109-113, 1998.
Search in Google Scholar
[40] Stefanowski J., Algorytmy Indukcji Regu l Decyzyjnych w Odkrywaniu Wiedzy [in Polish], Habilitation thesis, Rozprawy series, vol. 361, Poznań University of Technology, 2001.
Search in Google Scholar
[41] Sulzmann J.N., Fürnkranz J., A Study of Probability Estimation Techniques for Rule Learning, From Local Patterns to Global Models. Proceedings of the ECML/PKDD 2009 Workshop, p. 123-138, 2009.
Search in Google Scholar
[42] Tsymbal A., The Problem of Concept Drift: Definitions and RelatedWork, Technical Report, Department of Computer Science, Trinity College Dublin, Ireland, 2004.
Search in Google Scholar
[43] Wang H., Fan W., Yu P.S. and Han J., Mining Concept-drifting Data Streams Using Ensemble Classifiers, Proceedings ACM SIGKDD, p. 226-235, 2003.10.1145/956750.956778
Search in Google Scholar
[44] Widmer G., Kubat M., Learning in the Presence of Concept Drift and Hidden Contexts, Machine Learning, vol. 23, p. 69-101, 1996.10.1007/BF00116900
Search in Google Scholar
[45] Zliobaite I., Learning Under Concept Drift: An Overview, Technical Report, Faculty of Mathematics and Informatics, Vilnius University, Vilnius, Lithuania, 2009.
Search in Google Scholar
[46] Zliobaite I., Bakker J., Pechenizkiy M., OMFP: An Approach for Online Mass Flow Prediction in CFB Boilers, Discovery Science, p. 272-286, 2009.10.1007/978-3-642-04747-3_22
Search in Google Scholar
[47] Zliobaite I., Bakker J., Pechenizkiy M., Towards Context Aware Food Sales Prediction. In Proceedings of the 3nd International Workshop on Domain Driven Data Mining (DDDM'09), IEEE International Conference on Data Mining ICDM'09, Miami, Florida, USA, p. 94-99, 2009. 10.1109/ICDMW.2009.60
Search in Google Scholar

Incremental Rule-Based Learners for Handling Concept Drift: An Overview

Abstract

Paradigm

My account