The AQ Methods for Concept Drift

Marcus A. Maloof

Since the mid-1990's, we have developed, implemented, and evaluated a number of learning methods that cope with concept drift. Drift occurs when the target concept that a learner must acquire changes over time. It is present in applications involving user preferences (e.g., calendar scheduling) and adversaries (e.g., spam detection). We based early efforts on Michalski's AQ algorithm, and our more recent work has investigated ensemble methods. We have also implemented several methods that other researchers have proposed. In this chapter, we survey results that we have obtained since the mid-1990's using the Stagger concepts and learning methods for concept drift. We examine our methods based on the AQ algorithm, our ensemble methods, and the methods of other researchers. Dynamic weighted majority with an incremental algorithm for producing decision trees as the base learner achieved the best overall performance on this problem with an area under the performance curve after the first drift point of .882. Systems based on the AQ11 algorithm, which incrementally induces rules, performed comparably, achieving areas of .875. Indeed, an AQ11 system with partial instance memory and Widmer and Kubat's window adjustment heuristic achieved the best performance with an overall area under the performance curve, with an area of .898.

Paper available from Springer.

  author = "Maloof, M. A.",
  title = "The {AQ} methods for concept drift",
  booktitle = "Advances in Machine Learning {I}: Dedicated to the Memory
    of {Professor Ryszard S. Michalski}",
  editor = "Koronacki, J. and Ras, Z. W. and Wirzchon, S. T. and Kacprzyk, J.",
  year = 2010,
  pages = "23--48",
  series = "Studies in Computational Intelligence", 
  volume = 262,
  address = "Berlin-Heidelburg",
  publisher = "Springer",
  annote = {