Rule induction as a method for constructing classifiers is particularly attractive in data mining applications, where the comprehensibility of the generated models is very important. Most existing techniques were designed for small data sets and thus are not practical for direct use on very large data sets because of their computational inefficiency. Scaling up rule induction methods to handle such data sets is a formidable challenge. This article presents a new algorithm for rule induction that can efficiently extract accurate and comprehensible models from large and noisy data sets. This algorithm has been tested on several complex data sets, and the results prove that it scales up well and is an extremely effective learner.
FayyadU. M.Piatetsky-ShapiroG.SmythP.From data mining to knowledge discovery: An overview. In Advances in knowledge discovery and data mining (Eds FayyadU. M.Piatetsky-ShapiroG.SmythP.UthurusamyR.), AAAI Press, Menlo Park, CA.
2.
BrahaD.Data mining for design and manufacturing: Methods and applications, 2001 (Kluwer Academic Publishers, Boston).
3.
MonostoriL.AI and machine learning techniques for managing complexity, changes and uncertainties in manufacturing. Proceedings of the 15th Triennial World Congress, Barcelona, Spain, 2002, pp. 119–130.
4.
PhamD. T.AfifyA. A.Machine-learning techniques and their applications in manufacturing. Proc. IMechE. Part B: J. Engineering Manufacture, 2005, 219(B5), 395–412.
5.
AptéC.WeissS.Data mining with decision trees and decision rules. Future Gener. Comp. Sys., 1997, 13, 197–210.
6.
PhamD. T.AfifyA. A.Machine learning: Techniques and trends. Proceedings of the 9th International Workshop on Systems, signals and image processing (IWSSIP — 02), 2002, pp. 12–36 (World Scientific, Manchester, Town Hall, UK).
7.
FayyadU. M.HausslerD.StolorzP.KDD for science data analysis: Issues and examples. Proceedings of the 2nd International Conference on Data mining and knowledge discovery, 1996, pp. 50–56 (AAAI Press, Menlo Park, CA).
8.
FayyadU. M.Piatetsky-ShapiroG.SmythP.Knowledge discovery and data mining: Towards a unifying framework. Proceedings of the 2nd International Conference on Data mining and knowledge discovery, 1996, pp. 82–88 (AAAI Press, Menlo Park, CA).
9.
MitchellT. M.Machine learning and data mining. Commun. ACM, 1999, 42 (11), 31–36.
10.
ProvostF.KolluriV.A survey of methods for scaling up inductive algorithms. Data Min. Knowl. Disc., 1999, 2, 1–42.
11.
KlasgenW.ŻytkowJ. M.Handbook of data mining and knowledge discovery, 2002 (Oxford University Press, New York).
BlockeelH.SebagM.Scalability and efficiency in multi-relational data mining. ACM SIGKDD Explor. Newslett., 2003, 5 (1), 17–30.
14.
MehtaM.AgrawalR.RissanenJ.SLIQ: A fast scalable classifier for data mining. Proceedings of the 5th International Conference on Extending database technology, 1996, pp. 18–32 (Avignon, France).
15.
ShaferJ.AgrawalR.MehtaM.SPRINT: A scalable parallel classifier for data mining. Proceedings of the 22nd International Conference on Very large data bases (VLDB), 1996, pp. 544–555 (Mumbai (Bombay), India).
16.
RastogiR.ShimK.PUBLIC: A decision tree classifier that integrates building and pruning. Proceedings of the 24th International Conference on Very large data bases (VLDB), 1998, pp. 404–415 (New York, USA).
CendrowskaJ.PRISM: An algorithm for inducing modular rules. Int. J. Man Mach. Stud., 1987, 27, 349–370.
20.
QuinlanJ. R.Learning efficient classification procedures and their application to chess endgames. In Machine learning: An artificial intelligence approach (Eds MichalskiR. S.CarbonellJ. G.MitchellT. M.) 1983, vol. 1, pp. 463–482 (Tioga Publishing Co., Palo Alto, CA).
21.
MichalskiR. S.On the quasi-minimal solution of the general covering problem. Proceedings of the 5th International Symposium on Information processing (FCIP 69), 1969, A3 (Switching Circuits), pp. 125–128 (Bled, Yugoslavia).
22.
MichalskiR. S.LarsonJ. B.Incremental generation of VL1 hypotheses: The underlying methodology and the descriptions of program AQ11. ISG 83–5, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois, 1983.
23.
MichalskiR. S.MozeticI.HongJ.LavracN.The multi-purpose incremental learning system AQ15 and its testing application to three medical domains. American association of artificial intelligence, 1986, pp. 1041–1045 (Morgan Kaufmann, Los Altos, CA).
24.
MichalskiR. S.KaufmanK. A.The AQ19 system for machine learning and pattern discovery: A general description and user guide, Reports of the machine learning and inference laboratory MLI 01–2, George Mason University, Fairfax, VA, USA, 2001.
25.
CervoneG.PanaitL. A.MichalskiR. S.The development of the AQ20 learning system and initial experiments. Proceedings of the 10th International Symposium on Intelligent information systems, Zakopane, Poland, 2001.
ClarkP.BoswellR.Rule induction with CN2: Some recent improvements. Proceedings of the 5th European Conference on Artificial intelligence, Porto, Portugal, 1991, 151–163.
PhamD. T.DimovS. S.An algorithm for incremental inductive learning. Proc. Instn Mech. Engrs. Part B: J. Engineering Manufacture, 1997, 211, 239–249.
33.
PhamD. T.BigotS.DimovS. S.RULES-5: A rule induction algorithm for problems involving continuous attributes. Proc. Instn Mech. Engrs. Part C: J. Mechanical Engineering Science, 2003, 217, 1273–1286.
34.
PhamD. T.AfifyA. A.RULES-6: A simple rule induction algorithm for handling large data sets. Submitted to Proc. IMechE. Part C: J. Mechanical Engineering Science, 2005, 219(C10), 1119–1137.
35.
DomingosP.A unified approach to concept learning. PhD Thesis, University of California, Irvine, 1997.
36.
WeissG. M.HirshA.A quantitative study of small disjuncts. Proceedings of the 17th National Conference on Artificial intelligence, Austin, Texas, 2000, 665–670.
37.
AfifyA. A.Design and analysis of scalable rule induction systems. PhD Thesis, University of Wales Cardiff, School of Engineering, Systems Engineering Division, Cardiff, UK, 2004.
38.
FayyadU. M.IraniK. B.Multi-interval discretization of continuous-valued attributes for classification. Proceedings of the 13th International Joint Conference on Artificial intelligence, Chambery, France, 1993, 1022–1027.
39.
MitchellT. M.The need for biases in learning generalizations, Technical report CBM-TR-117, Rutgers University, 1980.
40.
WebbG.Systematic search for categorical attribute-value data-driven machine learning. In AI'94-Proceedings of the 6th Australian Joint Conference on Artificial intelligence (Eds RowlesC.LiuH.FooN.), 1993, pp. 342–347 (World Scientific, Melbourne).
41.
QuinlanJ. R.Cameron-JonesR. M.Over-searching and layered search in empirical learning. Proceedings of the 14th International Joint Conference on Artificial intelligence, Montreal, Quebec, Canada, 1995, 1019–1024.
WeissS.IndurkhyaN.Reduced complexity rule induction. Proceedings of the 12th International Joint Conference on Artificial intelligence, Sydney, Australia, Morgan Kaufmann, 1991.
44.
CohenW. W.Fast effective rule induction. Proceedings of the 12th International Conference on Machine learning, Tahoe City, CA, 1995, 115–123.
45.
FarnkranzJ.WidmerG.Incremental reduced error pruning. Proceedings of the 11th International Conference on Artificial intelligence, Amsterdam, The Netherlands, 1994, 453–457.
MichalskiR. S.KaufmanK. A.A measure of description quality for data mining and its implementation in the AQ18 learning system. Proceedings of the International ICSC Congress on Computational intelligence methods and applications, Rochester, NY, USA, 1999, 369–375.
50.
SchafferC.Overfitting avoidance as bias. Mach. Learn., 1993, 10, 153–178.
51.
FarnkranzJ.Pruning algorithms for rule learning. Mach. Learn., 1996, 27, 139–171.
52.
FrankE.Pruning decision trees and lists. PhD Thesis, Department of Computer Science, University of Waikato, Hamilton, New Zealand, 2000.
53.
PhamD. T.AfifyA. A.A new MDL-based pruning technique for rule induction algorithms. Technical report, Manufacturing Engineering Centre, Cardiff University, 2004.
MitchellT. M.Machine learning, 1997 (McGraw Hill, New York).
56.
BlakeC. L.MerzC. J.UCI Repository of Machine Learning Databases. University of California, Department of Information and Computer Science, Irvine, CA, 1998, available from http://www.ics.uci.edu/εmlearn/MLRepository.html.
EfronB.TibshiraniR.An introduction to the bootstrap, 1993 (Chapman & Hall, USA).
59.
SegalR. B.Machine learning as massive search. PhD Thesis, Department of Computer Science and Engineering, University of Washington, 1997.
60.
AronisJ.ProvostF.Increasing the efficiency of data mining algorithms with breadth-first marker propagation. Proceedings of the 3rd International Conference on Knowledge discovery and data mining, Newport Beach, CA, USA, 1997.
61.
GraefeG.FayyadU.ChaudhuriS.On the efficient gathering of sufficient statistics for classification of large SQL databases. Proceedings of the 4th International Conference on Knowledge discovery and data mining, 1998 (AAAI Press, New York, NY).
