First approach toward on-line evolution of association rules with learning classifier systems

ABSTRACT

This paper presents CSar, a Michigan-style Learning Classifier System which has been designed for extracting quantitative association rules from streams of unlabeled examples. The main novelty of CSar with respect to the existing association rule miners isthat it evolves the knowledge on-line and so it is prepared to adapt its knowledge to changes in the variable associations hidden in the stream of unlabeled data quickly and efficiently. Preliminary results provided in this paper show that CSar is able to evolve interesting rules on problems that consist of both categorical and continuous attributes. Moreover, the comparison of CSar with Apriori on a problem that consists only of categorical attributes highlights the competitiveness of CSar with respect to more specific learners that perform enumeration to return all possible association rules. These promising results encourage us for further investigating on CSar.

REFERENCES

• 1: Charu C. Aggarwal, Data Streams: Models and Algorithms (Advances in Database Systems), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 2: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 4: A. Asuncion and D. J. Newman. UCI Machine Learning Repository: {http://www.ics.uci.edu/~mlearn/MLRepository.html}. University of California, 2007.
• 5: Ester Bernadó-Mansilla , Josep M. Garrell-Guiu, Accuracy-based learning classifier systems: models, analysis and applications to classification tasks, Evolutionary Computation, v.11 n.3, p.209-238, Fall 2003 [doi>10.1162/106365603322365289]
• 6: C. H. Cai , A. W. C. Fu , C. H. Cheng , W. W. Kwong, Mining Association Rules with Weighted Items, Proceedings of the 1998 International Symposium on Database Engineering & Applications, p.68, July 08-10, 1998
• 7: Takeshi Fukuda , Yasuhido Morimoto , Shinichi Morishita , Takeshi Tokuyama, Mining optimized association rules for numeric attributes, Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.182-191, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237708]
• 8: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 9: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 10: T. P. Hong, C. S. Kuo., and S. C. Chi. Trade-off between computation time and number of rules for fuzzy mining from quantitative data. International Journal of Uncertainty, Fuzziness, and Knowledge-Based Systems, 9(5):587--604, 2001.
• 11: M. Houtsma and A. Swami. Set-oriented mining of association rules. Technical Report RJ 9567, Almaden Research Center, San Jose, California, October 1993.
• 12: M. Kaya and R. Alhajj. Genetic algorithm based framework for mining fuzzy association rules. Fuzzy Sets and Systems, 152(3):587--601, 2005.
• 13: Brian Lent , Arun N. Swami , Jennifer Widom, Clustering Association Rules, Proceedings of the Thirteenth International Conference on Data Engineering, p.220-231, April 07-11, 1997
• 14: J. Mata , J. L. Alvarez , J. C. Riquelme, An evolutionary algorithm to discover numeric association rules, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain [doi>10.1145/508791.508905]
• 15: R. J. Miller , Y. Yang, Association rules over interval data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.452-461, May 11-15, 1997, Tucson, Arizona, United States
• 16: Marlon Núñez , Raúl Fidalgo , Rafael Morales, Learning in Environments with Unknown Dynamics: Towards more Robust Concept Learners, The Journal of Machine Learning Research, 8, p.2595-2628, 12/1/2007
• 17: A. Orriols-Puig, J. Casillas, and E. Bernadó-Mansilla. Fuzzy-UCS: a michigan-style learning fuzzy-classifier system for supervised learning. IEEE Transactions on Evolutionary Computation, in press.
• 18: A. Salleb-Aouissi, C. Vrain, and C. Nortet. Quantminer: A genetic algorithm for mining quantitative association rules. In M. M. Veloso, editor, Proceedings of the 2007 International Join Conference on Artificial Intelligence, pages 1035--1040, 2007.
• 19: Ashoka Savasere , Edward Omiecinski , Shamkant B. Navathe, An Efficient Algorithm for Mining Association Rules in Large Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.432-444, September 11-15, 1995
• 20: Ramakrishnan Srikant , Rakesh Agrawal, Mining quantitative association rules in large relational tables, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.1-12, June 04-06, 1996, Montreal, Quebec, Canada
• 21: C.-Y. Wang, S.-S. Tseng, T.-P. Hong, and Y.-S. Chu. Online generation of association rules under multidimensional consideration based on negative border. Journal of Information Science and Engineering, 23:233--242, 2007.
• 22: K. Wang, S. H. W. Tay, and B. Liu. Interestingness-based interval merger for numeric association rules. In Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining, KDD, pages 121--128. AAAI Press, 1998.
• 23: Stewart W. Wilson, Classifier fitness based on accuracy, Evolutionary Computation, v.3 n.2, p.149-175, Summer 1995 [doi>10.1162/evco.1995.3.2.149]
• 24: S. W. Wilson. Generalization in the XCS classifier system. In 3rd Annual Conf. on Genetic Programming, pages 665--674. Morgan Kaufmann, 1998.
• 25: Stewart W. Wilson, Get Real! XCS with Continuous-Valued Inputs, Learning Classifier Systems, From Foundations to Applications, p.209-222, January 2000

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

General Terms:
Algorithms

Keywords:
association rules, genetic algorithms, learning classifier systems, unsupervised learning