ACM Home Page
Please provide us with feedback. Feedback
Digital Library logoTake a look at the new version of this page: [ beta version ]. Tell us what you think.
Induction of Decision Trees
Source Machine Learning archive
Volume 1 ,  Issue 1  () table of contents
Pages: 81 - 106  
Year of Publication: 1986
ISSN:0885-6125
Author
Publisher
Kluwer Academic Publishers  Hingham, MA, USA
Bibliometrics
Downloads (6 Weeks): n/a,   Downloads (12 Months): n/a,   Citation Count: 898
Additional Information:

abstract   references   cited by   index terms   collaborative colleagues  

Tools and Actions: Review this Article  
DOI Bookmark: 10.1023/A:1022643204877

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.


REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

 
1
Buchanan, B. G ., & Mitchell, T. M. (1978). Model-directed learning of production rules. In D. A. Waterman, F. Hayes-Roth (Eds.), Pattern directed inference systems. Academic Press.
 
2
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 approach . Palo Alto: Tioga Publishing Company.
 
3
Catlett, J. (1985). Induction using the shafer representation (Technical report). Basser Department of Computer Science, University of Sydney, Australia.
 
4
Dechter, R., & Michie, D. (1985). Structured induction of plans and programs (Technical report). IBM Scientific Center, Los Angeles, CA.
 
5
Feigenbaum, E. A., & Simon, H. A. (1963). Performance of a reading task by an elementary perceiving and memorizing program, Behavioral Science, 8.
 
6
Feigenbaum, E. A. (1981). Expert systems in the 1980s. In A. Bond (Ed.), State of the art report on machine intelligence. Maidenhead: Pergamon-Infotech.
 
7
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 Artificial Intelligence. Vancouver, B. C., Canada: Morgan Kaufmann.
 
8
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.
 
9
Hogg, R. V., & Craig, A. T. (1970). Introduction to mathematical statistics. London: Collier-Macmillan.
 
10
Hunt, E. B. (1962). Concept learning: An information processing problem. New York: Wiley.
 
11
Hunt, E. B., Marin, J., & Stone, P. J. (1966). Experiments in induction. New York: Academic Press.
 
12
Kononenko, I., Bratko, I., & Roskar, E. (1984). Experiments in automatic learning of medical diagnostic rules (Technical report). Jozef Stefan Institute, Ljubljana, Yugoslavia.
 
13
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 intelligence approach. Palo Alto: Tioga Publishing Company.
 
14
Michalski, R. S (1980). Pattern recognition as rule-guided inductive inference. IEEE Transactions on Pattern Analysis and Machine Intelligence 2.
 
15
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 approach . Palo Alto: Tioga Publishing Company.
 
16
Michie, D. (1982). Experiments on the mechanisation of game-learning 2 - Rule-based learning and the human window. Computer Journal 25.
 
17
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.
 
18
Michie, D. (1985). Current developments in Artificial Intelligence and Expert Systems. In International Handbook of Information Technology and Automated Office Systems. Elsevier.
 
19
Nilsson, N. J. (1965). Learning machines, New York: McGraw-Hill.
 
20
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.
 
21
Patterson, A., & Niblett, T. (1983). ACLS user manual. Glasgow: Intelligent Terminals Ltd.
 
22
Pearl, J. (1978a). Entropy, information and rational decisions (Technical report). Cognitive Systems Laboratory, University of California, Los Angeles.
 
23
Pearl, J. (1978b). On the connection between the complexity and credibility of inferred models. International Journal of General Systems, 4.
 
24
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.
 
25
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.
 
26
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.
 
27
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.
 
28
Quinlan, J. R. (1983b). Learning from noisy data, Proceedings of the Second International Machine Learning Workshop. University of Illinois at Urbana-Champaign.
 
29
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).
 
30
 
31
Sammut, C. A. (1985). Concept development for expert system knowledge bases. Australian Computer Journal 17.
 
32
Samuel, A. (1967). Some studies in machine learning using the game of checkers II: Recent progress. IBM J. Research and Development 11.
 
33
Shapiro, A. (1983). The role of structured induction in expert systems. Ph.D. Thesis, University of Edinburgh.
 
34
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.
 
35
Winston, P. H. (1975). Learning structural descriptions from examples. In P. H. Winston (Ed.), The psychology of computer vision. McGraw-Hill.

CITED BY  898