Incremental rule-based learners for handling concept drift: an overview

• Autorzy: Deckert M
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

data mining; decision rules; rule-based classifiers; incremental learning; online learning; data streams; concept drift; non-stationary environment; overview

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2013
• Tom: Vol. 38, No. 1
• Strony: 35--65
• Opis fizyczny: Bibliogr. 47 poz., fig.

Twórcy

autor

Deckert M

• Institute of Computing Science, Poznań University of Technology, 60-965 Poznań, Poland

Bibliografia

• [1] An A., Learning Classification Rules from Data, Computers and Mathematics with Applications, vol. 45, p. 737-748, 2003.
• [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.
• [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.
• [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.
• [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.
• [6] Cendrowska J., PRISM An Algorithm for Inducing Modular Rules, International Journal Man-Machine Studies, vol. 27, p. 349-370, 1987.
• [7] Cestnik B., Estimating Probabilities: A Crucial Task in Machine Learning, Proceedings ECAO 1990, Stockholm, Sweden, 1990.
• [8] Clark P, Boswell R., Rule Induction with CN2: some recent improvement, Proceedings of 5th European Working Session on Learning, ESWL 1991, Porto, Portugal, p. 151-163, 1991.
• [9] Clark P., Niblett T., The CN2 Induction Algorithm, Machine Learning, vol. 3, p. 261-283, 1989.
• [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.
• [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.
• [12] Domingos P., Hulten G., Mining High-Speed Data Streams, Proceedings of the KDD 2000, ACM Press, p. 71-80, 2000.
• [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.
• [14] Ferrer-Troyano F.J., Aguilar-Ruiz J.A., Riquelme J.C., Data Streams Classification by Incremental Rule Learning with Parametrized Generalization, Proceedings of ACM Symposium on Applied Computing 2006, SAC 2006, p. 657-661, ACM, 2006.
• [15] Fürnkranz J., Separate-and-Conquer Rule Learning, Artificial Intelligence Review, vol. 13, p.3-54, 1999.
• [16] Fürnkranz J., Gamberger D., Lavrač N., Foundations of Rule Learning, Cognitive Technologies, 2012.
• [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.
• [18] Gama J., Knowledge Discovery from Data Streams, Chapman and Hall/CRC 2010.
• [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.
• [20] Giraud-Carrier C., A Note on the Utility of Incremental Learning, AI Communications, vol. 13, p. 215-223, 2000.
• [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.
• [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.
• [23] Grzymala-Busse J.W., Selected Algorithms of Machine Learning from Examples, Fundamenta Informaticae, vol. 18, p. 193-207, 1993.
• [24] Grzymala-Busse J.W., Managing Uncertainty in Machine Learning from Examples. Proceedings of 3rd International Symposium in Intelligent Systems, p. 70-84, 1994.
• [25] Hulten G., Spencer L., Domingos P., Mining Time-changing Data Streams, Proceedings of the KDD 2001, ACM Press, p. 97-106, 2001.
• [26] Kosina P., Gama J., Very Fast Decision Rules for Multi-class Problems, Proceedings of the 2012 ACM Symposium on Applied Computing, New York, USA, p. 795-800, 2012.
• [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.
• [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.
• [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.
• [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.
• [31] Maloof M., Michalski R., Selecting Examples for Partial Memory Learning, Machine Learning, vol. 41, p. 27-52, Kluwer Academic Publishers, 2000.
• [32] Maloof M., Michalski R., Incremental Learning with Partial Instance Memory, Artificial Intelligence, vol. 154, p. 95-126, Elsevier, 2003.
• [33] Maloof M., Incremental Rule Learning with Partial Instance Memory for Changing Concepts, Proceedings of the International Joint Conference on Neural Networks 2003, IJCNN-03, vol. 4, p. 2764-2769, IEEE Press, 2003.
• [34] Michalski R.S., A Theory and Methodology of Inductive Learning, Machine Learning: An Artificial Intelligence Approach, p. 83-134, 1983.
• [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.
• [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.
• [37] Schlimmer J., Granger R., Incremental Learning from Noisy Data, Machine Learning, vol. 1(3), p. 317-357, 1986.
• [38] Shannon C.E., A Mathematical Theory of Communication, Bell System Technical Journal, vol. 27(3), p. 379-423, 1948.
• [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.
• [40] Stefanowski J., Algorytmy Indukcji Regu l Decyzyjnych w Odkrywaniu Wiedzy [in Polish], Habilitation thesis, Rozprawy series, vol. 361, Poznań University of Technology, 2001.
• [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.
• [42] Tsymbal A., The Problem of Concept Drift: Definitions and RelatedWork, Technical Report, Department of Computer Science, Trinity College Dublin, Ireland, 2004.
• [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.
• [44] Widmer G., Kubat M., Learning in the Presence of Concept Drift and Hidden Contexts, Machine Learning, vol. 23, p. 69-101, 1996.
• [45] Zliobaite I., Learning Under Concept Drift: An Overview, Technical Report, Faculty of Mathematics and Informatics, Vilnius University, Vilnius, Lithuania, 2009.
• [46] Zliobaite I., Bakker J., Pechenizkiy M., OMFP: An Approach for Online Mass Flow Prediction in CFB Boilers, Discovery Science, p. 272-286, 2009.
• [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.