Abstract
The technology for building knowledge-based systems by inductive inference from examples has been demonstrated successfully in several practical applications. This paper summarizes an approach to synthesizing decision trees that has been used in a variety of systems, and it describes one such system, ID3, in detail. Results from recent studies show ways in which the methodology can be modified to deal with information that is noisy and/or incomplete. A reported shortcoming of the basic algorithm is discussed and two means of overcoming it are compared. The paper concludes with illustrations of current research directions.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Buchanan, B.G., & Mitchell, T.M. (1978). Model-directed learning of production rules. In D.A.Water-man, F.Hayes-Roth (Eds.), Pattern directed inference systems.Academic Press.
Carbonell, J.G., Michalski, R.S., & Mitchell, T.M. (1983). An overview of machine learning, In R.S. Michalski, J.G. Carbonell and T.M. Mitchell, (Eds.), Machine learning:An artificial intelligence ap-proach.Palo Alto: Tioga Publishing Company.
Catlett, J. (1985). Induction using the shafer representation(Technical report). Basser Department of Computer Science, University of Sydney, Australia.
Dechter, R., & Michie, D. (1985). Structured induction of plans and programs(Technical report). IBM Scientific Center, Los Angeles, CA.
Feigenbaum, E.A., & Simon, H.A. (1963). Performance of a reading task by an elementary perceiving and memorizing program, Behavioral Science, 8.
Feigenbaum, E.A. (1981). Expert systems in the 1980s. In A. Bond (Ed.), State of the art report on machine intelligence.Maidenhead: Pergamon-Infotech.
Garvey, T.D., Lowrance, J.D., & Fischler, M.A. (1981). An inference technique for integrating knowledge from disparate sources. Proceedings of the Seventh International Joint Conference on Arti-ficial Intelligence.Vancouver, B.C., Canada: Morgan Kaufmann.
Hart, A.E. (1985). Experience in the use of an inductive system in knowledge engineering. In M.A. Bramer (Ed.), Research and development in expert systems.Cambridge University Press.
Hogg, R.V., & Craig, A.T. (1970). Introduction to mathematical statistics.London: Collier-Macmillan.
Hunt, E.B. (1962). Concept learning:An information processing problem.New York: Wiley.
Hunt, E.B., Marin, J., & Stone, P.J. (1966). Experiments in induction.New York: Academic Press.
Kononenko, I., Bratko, I., & Roskar, E. (1984). Experiments in automatic learning of medical diagnostic rules(Technical report). Jozef Stefan Institute, Ljubljana, Yugoslavia.
Langley, P., Bradshaw, G.L., & Simon, H.A. (1983). Rediscovering chemistry with the BACON system. In R.S. Michalski, J.G. Carbonell and T.M. Mitchell (Eds.), Machine learning:An artificial intel-ligence approach.Palo Alto: Tioga Publishing Company.
Michalski, R.S (1980). Pattern recognition as rule-guided inductive inference. IEEE Transactions on Pat-tern Analysis and Machine Intelligence 2.
Michalski, R.S., & Stepp, R.E. (1983). Learning from observation:conceptual clustering. In R.S. Michalski, J.G. Carbonell & T.M. Mitchell (Eds.), Machine learning:An artificial intelligence ap-proach.Palo Alto: Tioga Publishing Company.
Michie, D. (1982). Experiments on the mechanisation of game-learning 2-Rule-based learning and the human window. Computer Journal 25.
Michie, D. (1983). Inductive rule generation in the context of the Fifth Generation. Proceedings of the Second International Machine Learning Workshop.University of Illinois at Urbana-Champaign.
Michie, D. (1985). Current developments in Artificial Intelligence and Expert Systems. In International Handbook of Information Technology and Automated Office Systems.Elsevier.
Nilsson, N.J. (1965). Learning machinesNew York: McGraw-Hill.
O’Keefe, R.A. (1983). Concept formation from very large training sets. In Proceedings of the Eighth International Joint Conference on Artificial Intelligence.Karlsruhe, West Germany: Morgan Kaufmann.
Patterson, A., & Niblett, T. (1983). ACLS user manual.Glasgow: Intelligent Terminals Ltd.
Pearl, J. (1978a). Entropy, information and rational decisions (Technical report). Cognitive Systems Laboratory, University of California, Los Angeles.
Pearl, J. (1978b). On the connection between the complexity and credibility of inferred models. Interna-tional Journal of General Systems, 4.
Quinlan, J.R. (1969). A task-independent experience gathering scheme for a problem solver. Proceedings of the First International Joint Conference on Artificial Intelligence.Washington, D.C.: Morgan Kaufmann.
Quinlan, J.R. (1979). Discovering rules by induction from large collections of examples. In D. Michie (Ed.), Expert systems in the micro electronic age.Edinburgh University Press.
Quinlan, J.R. (1982). Semi-autonomous acquisition of pattern-based knowledge. In J.E. Hayes, D. Michie & Y-H. Pao (Eds.), Machine intelligence 10.Chichester: Ellis Horwood.
Quinlan, J.R. (1983a). Learning efficient classification procedures and their application to chess endgames. In R.S. Michalski, J.G. Carbonell & T.M. Mitchell, (Eds.), Machine learning:An artificial intelligence approach.Palo Alto: Tioga Publishing Company.
Quinlan, J.R. (1983b). Learning from noisy data, Proceedings of the Second International Machine Learning Workshop.University of Illinois at Urbana-Champaign.
Quinlan, J.R. (1985a). The effect of noise on concept learning. In R.S. Michalski, J.G.Carbonell & T.M. Mitchell (Eds.), Machine learning.Los Altos: Morgan Kaufmann (in press).
Quinlan, J.R. (1985b). Decision trees and multi-valued attributes. In J.E. Hayes & D. Michie (Eds.), Machine intelligence 11.Oxford University Press (in press).
Sammut, C.A. (1985). Concept development for expert system knowledge bases. Australian Computer Journal 17.
Samuel, A. (1967). Some studies in machine learning using the game of checkers II:Recent progress. IBM J. Research and Development 11.
Shapiro, A. (1983). The role of structured induction in expert systems.Ph. D.Thesis, University of Edinburgh.
Shepherd, B.A. (1983). An appraisal of a decision-tree approach to image classification. Proceedings of the Eighth International Joint Conference on Artificial Intelligence.Karlsruhe, West Germany: Morgan Kaufmann.
Winston, P.H. (1975). Learning structural descriptions from examples. In P.H. Winston (Ed.), The psychology of computer vision.McGraw-Hill.
Rights and permissions
About this article
Cite this article
Quinlan, J. Induction of Decision Trees. Mach Learn 1, 81–106 (1986). https://doi.org/10.1023/A:1022643204877
Issue Date:
DOI: https://doi.org/10.1023/A:1022643204877