More Web Proxy on the site http://driver.im/

article

Very fast decision rules for classification in data streams

Authors:

João GamaAuthors Info & Claims

Data Mining and Knowledge Discovery, Volume 29, Issue 1

Pages 168 - 202

https://doi.org/10.1007/s10618-013-0340-z

Published: 01 January 2015 Publication History

Abstract

Data stream mining is the process of extracting knowledge structures from continuous, rapid data records. Many decision tasks can be formulated as stream mining problems and therefore many new algorithms for data streams are being proposed. Decision rules are one of the most interpretable and flexible models for predictive data mining. Nevertheless, few algorithms have been proposed in the literature to learn rule models for time-changing and high-speed flows of data. In this paper we present the very fast decision rules ( VFDR ) algorithm and discuss interesting extensions to the base version. All the proposed versions are one-pass and any-time algorithms. They work on-line and learn ordered or unordered rule sets. Algorithms designed to work with data streams should be able to detect changes and quickly adapt the decision model. In order to manage these situations we also present the adaptive extension ( AVFDR ) to detect changes in the process generating data and adapt the decision model. Detecting local drifts takes advantage of the modularity of the rule sets. In AVFDR , each individual rule monitors the evolution of performance metrics to detect concept drift. AVFDR prunes rules whenever a drift is signaled. This explicit change detection mechanism provides useful information about the dynamics of the process generating data, faster adaptation to changes and generates more compact rule sets. The experimental evaluation demonstrates that algorithms achieve competitive results in comparison to alternative methods and the adaptive methods are able to learn fast and compact rule sets from evolving streams.

References

[1]

Baena-Garcia M, Campo-Avila J, Fidalgo R, Bifet A, Gavalda R, Morales-Bueno R (2006) Early drift detection method. In: Fourth international workshop on knowledge discovery from data streams. ECMLPKDD, Berlin, pp 77-86.

[2]

Berthold MR, Cebron N, Dill F, Gabriel TR, Kötter T, Meinl T, Ohl P, Thiel K, Wiswedel B (2009) KNIME: the konstanz information miner: version 2.0 and beyond. SIGKDD Explor Newsl 11:26-31.

Digital Library

[3]

Bifet A, Gavalda R (2009) Adaptive learning from evolving data streams. In: Advances in intelligent data analysis VIII. Lecture notes in computer science, vol 5772. Springer, Berlin/Heidelberg, pp 249-260.

[4]

Bifet A, Holmes G, Kirkby R, Pfahringer B (2010) MOA: massive online analysis. J Mach Learn Res (JMLR) 11:1601-1604.

Digital Library

[5]

Bifet A, Holmes G, Pfahringer B, Kirkby R, Gavaldà R (2009) New ensemble methods for evolving data streams. In Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining, KDD '09. ACM Press, New York, pp 139-148.

[6]

Breiman L, Friedman J, Stone CJ, Olshen RA (1984) Classification and regression trees, 1st edn. Chapman and Hall/CRC, Boca Raton.

[7]

Clark P, Boswell R (1991) Rule induction with CN2: some recent improvements. In: Proceedings of the European working session on machine learning, EWSL '91. Springer, London, pp 151-163.

[8]

Clark P, Niblett T (1989) The CN2 induction algorithm. Mach Learn 3:261-283.

[9]

Cohen W (1995) Fast effective rule induction. In: Proceedings of the 12th international conference on machine learning, ICML'95. Morgan Kaufmann, San Francisco, pp 115-123.

[10]

Data Expo (2009) ASA sections on statistical computing statistical graphics. http://stat-computing.org/dataexpo/2009/. Accessed 1 Feb 2013.

[11]

Data Mining Group (2011) Predictive model markup language (pmml 4.1). http://www.dmg.org/v4-0-1/RuleSet.html. Accessed 1 Feb 2013.

[12]

Dem¿ar J (2006) Statistical comparisons of classifiers over multiple data sets. J Mach Learn Res 7:1-30.

Digital Library

[13]

Domingos P (1996) Unifying instance-based and rule-based induction. Mach Learn 24:141-168.

Digital Library

[14]

Domingos P, Hulten G (2000) Mining high-speed data streams. In: Proceedings of the sixth ACM SIGKDD international conference on knowledge discovery and data mining, KDD '00. ACM Press, New York, pp 71-80.

Digital Library

[15]

Ferrer F, Aguilar J, Riquelme J (2005) Incremental rule learning and border examples selection from numerical data streams. J Univ Comput Sci 11(8):1426-1439.

[16]

Frank A, Asuncion A (2010) UCI machine learning repository. University of California, Irvine.

[17]

Frank E, Witten IH (1998) Generating accurate rule sets without global optimization. In: Proceedings of the 15th international conference on machine learning, ICML'98. Morgan Kaufmann, San Mateo, pp 144-151.

[18]

Friedman M (1937) The use of ranks to avoid the assumption of normality implicit in the analysis of variance. J Am Stat Assoc 32(200):675-701.

[19]

Friedman M (1940) A comparison of alternative tests of significance for the problem of m rankings. Ann Math Stat 11(1):86-92.

[20]

Fürnkranz J (2001) Round robin rule learning. In: Proceedings of the 18th international conference on machine learning, ICML'01. Morgan Kaufmann, San Mateo, pp 146-153.

[21]

Fürnkranz J, Gamberger D, Lavrac N (2012) Foundations of rule learning. Springer, New York.

[22]

Gama J (2010) Knowledge discovery from data streams. Chapman and Hall/CRC, Baco Raton.

[23]

Gama J, Kosina P (2011) Learning decision rules from data streams. In: Proceedings of the 22nd international joint conference on artificial intelligence. AAAI, Menlo Park, pp 1255-1260.

[24]

Gama J, Rocha R, Medas P (2003) Accurate decision trees for mining high-speed data streams. In: Proceedings of the 9th ACM SIGKDD international conference on knowledge discovery and data mining, KDD'03. ACM Press, New York, pp 523-528.

[25]

Gama J, Medas P, Castillo G, Rodrigues P (2004) Learning with drift detection. In: SBIA Brazilian symposium on artificial intelligence, LNCS 3171. Springer, Heidelberg, pp 286-295.

[26]

Gama J, Fernandes R, Rocha R (2006) Decision trees for mining data streams. Intell Data Anal 10:23-45.

Digital Library

[27]

Gama J, Sebastiao R, Rodrigues PP (2009) Issues in evaluation of stream learning algorithms. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining, KDD '09. ACM Press, New York, pp 329-338.

[28]

Grant E, Leavenworth R (1996) Statistical quality control. McGraw-Hill, New York.

[29]

Harries M (1999) Splice-2 comparative evaluation: electricity pricing. Technical report, The University of New South Wales, Sydney.

[30]

Hinkley D (1970) Inference about the change point from cumulative sum-tests. Biometrika 58:509-523.

[31]

Hulten G, Spencer L, Domingos P (2001) Mining time-changing data streams. In: Proceedings of the 7th ACM SIGKDD international conference on knowledge discovery and data mining. ACM Press, New York, pp 97-106.

[32]

Katakis I, Tsoumakas G, Banos E, Bassiliades N, Vlahavas I (2009) An adaptive personalized news dissemination system. J Intell Inf Syst 32:191-212.

Digital Library

[33]

Klinkenberg R (2004) Learning drifting concepts: example selection vs. example weighting. Intell Data Anal 8(3):281-300.

[34]

Kolter JZ, Maloof MA (2003) Dynamic weighted majority: a new ensemble method for tracking concept drift. In: Proceedings of the 3th international IEEE conference on data mining. IEEE Computer Society, New York, pp 123-130.

[35]

Kosina P, Gama J (2012a) Handling time changing data with adaptive very fast decision rules. In: Proceedings of the 2012 European conference on machine learning and knowledge discovery in databases, ECML PKDD'12, vol I. Springer, Berlin, Heidelberg, pp 827-842.

[36]

Kosina P, Gama J (2012b) Very fast decision rules for multi-class problems. In: Proceedings of the 2012 ACM symposium on applied computing. ACM Press, New York, pp 795-800.

[37]

Lindgren T, Boström H (2004) Resolving rule conflicts with double induction. Intell Data Anal 8(5):457-468.

Digital Library

[38]

Maloof M, Michalski R (2004) Incremental learning with partial instance memory. Artif Intell 154:95-126.

Digital Library

[39]

Moro S, Laureano R, Cortez P (2011) Using data mining for bank direct marketing: an application of the crisp-dm methodology. In: Proceedings of the European simulation and modelling conference, ESM'2011. EUROSIS, Guimaraes, pp 117-121.

[40]

Nemenyi P (1963) Distribution-free multiple comparisons. PhD thesis, Princeton University.

[41]

Oza NC, Russell S (2001) Online bagging and boosting. In: Artificial intelligence and statistics 2001. Morgan Kaufmann, San Mateo, pp 105-112.

[42]

Quinlan JR (1991) Determinate literals in inductive logic programming. In: Proceedings of the 12th international joint conference on artificial intelligence, IJCAI'91, vol 2. Morgan Kaufmann Publishers Inc, San Francisco, pp 746-750.

[43]

Quinlan JR (1993) C4.5: programs for machine learning. Morgan Kaufmann Publishers, San Mateo.

[44]

Rivest R (1987) Learning decision lists. Mach Learn 2:229-246.

[45]

Schlimmer JC, Granger RH (1986) Incremental learning from noisy data. Mach Learn 1:317-354.

[46]

Shaker A, Hüllermeier E (2012) IBLStreams: a system for instance-based classification and regression on data streams. Evol Syst 3:235-249.

[47]

Street WN, Kim Y (2001) A streaming ensemble algorithm SEA for large-scale classification. In: Proceedings of the 7th ACM SIGKDD international conference on knowledge discovery and data mining, KDD '01. ACM Press, New York, pp 377-382.

[48]

Wang H, Fan W, Yu PS, Han J (2003) Mining concept-drifting data streams using ensemble classifiers. In: Proceedings of the 9th ACM SIGKDD international conference on knowledge discovery and data mining, KDD '03. ACM Press, New York, pp 226-235.

[49]

Weiss SM, Indurkhya N (1998) Predictive data mining: a practical guide. Morgan Kaufmann Publishers, San Francisco.

[50]

Widmer G, Kubat M (1996) Learning in the presence of concept drift and hidden contexts. Mach Learn 23:69-101.

Cited By

Yin JTang MCao JWang HYou MLin Y(2022)Vulnerability exploitation time prediction: an integrated framework for dynamic imbalanced learningWorld Wide Web10.1007/s11280-021-00909-z25:1(401-423)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s11280-021-00909-z
Huynh VBeck FFürnkranz J(2022)Incremental Update of Locally Optimal Classification RulesDiscovery Science10.1007/978-3-031-18840-4_8(104-113)Online publication date: 10-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-18840-4_8
Li PWu MHe JHu X(2021)Recurring Drift Detection and Model Selection-Based Ensemble Classification for Data Streams with Unlabeled DataNew Generation Computing10.1007/s00354-021-00126-239:2(341-376)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s00354-021-00126-2
Show More Cited By

Very fast decision rules for classification in data streams
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Supervised learning

Recommendations

Adaptive Model Rules From High-Speed Data Streams

Decision rules are one of the most expressive and interpretable models for machine learning. In this article, we present Adaptive Model Rules (AMRules), the first stream rule learning algorithm for regression problems. In AMRules, the antecedent of a ...
Random rules from data streams
SAC '13: Proceedings of the 28th Annual ACM Symposium on Applied Computing

Existing works suggest that random inputs and random features produce good results in classification. In this paper we study the problem of generating random rule sets from data streams. One of the most interpretable and flexible models for data stream ...
Adaptive model rules from data streams
ECMLPKDD'13: Proceedings of the 2013th European Conference on Machine Learning and Knowledge Discovery in Databases - Volume Part I

Decision rules are one of the most expressive languages for machine learning. In this paper we present Adaptive Model Rules (AMRules), the first streaming rule learning algorithm for regression problems. In AMRules the antecedent of a rule is a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Data Mining and Knowledge Discovery

Data Mining and Knowledge Discovery Volume 29, Issue 1

January 2015

297 pages

ISSN:1384-5810

Issue’s Table of Contents

Copyright © Copyright © 2015 The Author(s).

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 January 2015

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yin JTang MCao JWang HYou MLin Y(2022)Vulnerability exploitation time prediction: an integrated framework for dynamic imbalanced learningWorld Wide Web10.1007/s11280-021-00909-z25:1(401-423)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s11280-021-00909-z
Huynh VBeck FFürnkranz J(2022)Incremental Update of Locally Optimal Classification RulesDiscovery Science10.1007/978-3-031-18840-4_8(104-113)Online publication date: 10-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-18840-4_8
Li PWu MHe JHu X(2021)Recurring Drift Detection and Model Selection-Based Ensemble Classification for Data Streams with Unlabeled DataNew Generation Computing10.1007/s00354-021-00126-239:2(341-376)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s00354-021-00126-2
Gomes HRead JBifet ABarddal JGama J(2019)Machine learning for streaming dataACM SIGKDD Explorations Newsletter10.1145/3373464.337347021:2(6-22)Online publication date: 26-Nov-2019
https://dl.acm.org/doi/10.1145/3373464.3373470
Cano AKrawczyk B(2018)Learning Classification Rules with Differential Evolution for High-Speed Data Stream Mining on GPU s2018 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2018.8477961(1-8)Online publication date: 8-Jul-2018
https://dl.acm.org/doi/10.1109/CEC.2018.8477961
Le TStahl FGaber MGomes JFatta G(2017)On expressiveness and uncertainty awareness in rule-based classification for data streamsNeurocomputing10.1016/j.neucom.2017.05.081265:C(127-141)Online publication date: 22-Nov-2017
https://dl.acm.org/doi/10.1016/j.neucom.2017.05.081
Brzezinski DStefanowski J(2017)Prequential AUCKnowledge and Information Systems10.1007/s10115-017-1022-852:2(531-562)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s10115-017-1022-8
Lindgren TZhang DLiu X(2016)Indexing rules in rule sets for fast classificationProceedings of the International Conference on Artificial Intelligence and Robotics and the International Conference on Automation, Control and Robotics Engineering10.1145/2952744.2952750(1-6)Online publication date: 13-Jul-2016
https://dl.acm.org/doi/10.1145/2952744.2952750
Miguel Ángel AJoão Bártolo GErnestina M(2016)Predicting recurring concepts on data-streams by means of a meta-model and a fuzzy similarity functionExpert Systems with Applications: An International Journal10.1016/j.eswa.2015.10.02246:C(87-105)Online publication date: 15-Mar-2016
https://dl.acm.org/doi/10.1016/j.eswa.2015.10.022

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents