Overfitting the training data is a major problem in machine learning, particularly when noise is present. Overfitting increases learning time and reduces both the accuracy and the comprehensibility of the generated rules, making learning from large data sets more difficult. Pruning is a technique widely used for addressing such problems and consequently forms an essential component of practical learning algorithms. An important class of pruning techniques is that based on the minimum description length (MDL) principle. This paper presents three new techniques using the MDL principle for pruning rule sets. An important advantage of these techniques is that all of the training data can be used for both inducing and evaluating rule sets. The performance of the techniques are evaluated using three criteria: classification accuracy, rule set complexity, and execution time. This shows that the new techniques, when incorporated into a rule induction algorithm, are more efficient and lead to accurate rule sets that are significantly smaller in size compared with the case before pruning.
CohenW. W.Fast effective rule induction. In Proceedings of the 12th International Conference on Machine learning, Tahoe City, CA, 1995, pp. 115–123 (Morgan Kaufmann, San Fransisco, CA).
2.
FarnkranzJ.Pruning algorithms for rule learning. Mach. Learn., 1996, 27, 139–171.
3.
PhamD. T.AfifyA. A.SRI: A scalable rule induction algorithm. Proc. Instn Mech. Engrs. Part C: J. Mechanical Engineering Science, 2006, 220(C4), 537–552.
BrunkC. A.PazzaniM. J.An investigation of noise-tolerant relational concept learning algorithms. In Proceedings of the 8th International Workshop on Machine learning, Evanston, Illinois, 1991, 389–393.
13.
CohenW. W.Efficient pruning methods for separate-and-conquer rule learning systems. In Proceedings of the 13th International Conference on Artificial intelligence, Chambery, France, 1993, 988–994 (Morgan Kaufmann, San Fransisco, CA).
14.
FrankE.WittenI. H.Reduced-error pruning with significant tests. Working paper, Department of Computer Science, University of Waikato, Hamilton, New Zealand, 1999.
15.
ElomaaT.KaariainenM.An analysis of reduced error pruning. J. Artif. Int. Res., 2001, 15, 163–187.
16.
FarnkranzJ.WidmerG.Incremental reduced error pruning. In Proceedings of the 11th International Conference on Machine learning, New Brunswick, NJ, 1994, pp. 70–77 (Morgan Kaufmann, San Fransisco, CA).
17.
FarnkranzJ.Top-down pruning in relational learning. In Proceedings of the 11th European Conference on Artificial intelligence, Amsterdam, The Netherlands, 1994, 453–457.
18.
RissanenJ.Stochastic complexity and modelling. Ann. Stat., 1986, 14 (3), 1080–1100.
19.
BarronA.RissanenJ.YuB.The minimum description length principle in coding and modelling. IEEE Trans. Inform. Theory, 1998, 44 (6), 2743–2760.
20.
GrunwaldP.Model selection based on minimum description length. J. Math. Psychol., 2000, 44, 133–170.
21.
TirriH.MDL and classification in machine learning. In Proceedings of the Neural Information Processing Systems Workshop on Minimum description length (NIPS-2001), Whistler, British Columbia, Canada, 2001, (MIT Press, Menlo Park, CA).
22.
GeorgeffM. P.WallaceC. S.A general selection criterion for inductive inference. In Proceedings of the 6th European Conference on Artificial intelligence (ECAI-84), Pisa, Italy, 1984, 473–482.
23.
QuinlanJ. R.RivestR. L.Inferring decision trees using minimum description length principle. Inform. Comp., 1989, 80, 227–248.
24.
QuinlanJ. R.C4.5: Programs for machine learning, 1993 (Morgan Kaufmann, San Mateo, CA).
25.
QuinlanJ. R.The minimum description length principle and categorical theories. In Proceedings of the 11th International Conference on Machine learning, New Brunswick, NJ, 1994, 233–241 (Morgan Kaufmann, San Fransisco, CA).
26.
QuinlanJ. R.MDL and categorical theories (continued). In Proceedings of the 12th International Conference on Machine learning, Lake Tahoe City, CA, 1995, 464–470 (Morgan Kaufmann, San Fransisco, CA).
27.
MehtaM.RissanenJ.AgrawalR.MDL-based decision tree pruning. In Proceedings of the 1st International Conference on Knowledge discovery in databases and data mining (KDD-95), Montreal, Canada, 1995, 216–221 (AAAI Press, Menlo Park, CA).
28.
PfahringerB.Practical uses of the minimum description length principle in inductive learning. PhD Thesis, Institut Für Med. Kybernetik u. AI, Techniscen Universitat Wien, 1995.
29.
PfahringerB.Compression-based pruning of decision lists. In Proceedings of the 9th European Conference on Machine learning, Prague, Czech Republic, 1997, 199–212 (Springer-Verlag, Berlin).
30.
Robnik-ŠikonjaM.KononenkoI.Pruning regression trees with MDLP. In Proceedings of the 13th European Conference on Artificial intelligence (ECAI-98), Brighton, UK, 1998, 455–459 (John Wiley and Sons, Chichester).
31.
PhamD. T.AfifyA. A.A new MDL-based pruning technique for rule induction algorithms. Technical report, Manufacturing Engineering Centre, Cardiff University, 2004.
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.
