Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Thuật toán Gia tăng để Sinh cây Quyết định
Tóm tắt
Bài báo này trình bày một thuật toán gia tăng để suy diễn các cây quyết định tương đương với các cây được hình thành bởi thuật toán ID3 không gia tăng của Quinlan, khi có cùng các trường hợp đào tạo. Thuật toán mới, được gọi là ID5R, cho phép áp dụng quy trình suy diễn ID3 cho các nhiệm vụ học mà trong đó các trường hợp đào tạo được trình bày theo thứ tự. Mặc dù các thuật toán xây dựng cây cơ bản chỉ khác nhau ở cách thức mà cây quyết định được xây dựng, các thí nghiệm cho thấy rằng việc đào tạo gia tăng cho phép lựa chọn các trường hợp đào tạo một cách cẩn thận hơn, điều này có thể dẫn đến các cây quyết định nhỏ hơn. Thuật toán ID3 và các biến thể của nó được so sánh về độ phức tạp lý thuyết và hành vi thực nghiệm.
Từ khóa
#Cây quyết định #thuật toán ID3 #thuật toán ID5R #học máy #đào tạo gia tăngTài liệu tham khảo
Barto, A. G. (1985). Learning by statistical cooperation of self-interested neuron-like computing elements. Human Neurobiology, 4, 229–256.
Breiman, L., Friedman, J. H., Olshen, R. A., and Stone, C. J. (1984). Classification and regression trees. Belmont, CA: Wadsworth International Group.
Buchanan, B. G., and Mitchell, T. M. (1978). Model-directed learning of production rules. In D. A. Waterman and F. Hayes-Roth (Eds.), Pattern-directed inference systems. New York: Academic Press.
Cockett, J. R. B. (1987). Discrete decision theory: Manipulations. Theoretical Computer Science, 54, 215–236.
Fisher, D. H. (1987). Knowledge acquisition via incremental conceptual clustering. Machine Learning, 2, 139–172.
Gallant, S. I. (1988). Connectionist expert systems. Communications of the ACM, 31, 152–169.
Lewis, P. M. (1962). The characteristic selection problem in recognition systems. IRE Transactions on Information Theory, IT-8, 171–178.
Michalski, R. S., and Chilausky, R. L. (1980). Learning by being told and learning from examples: An experimental comparison of the two methods of knowledge acquisition in the context of developing an expert system for soybean disease diagnosis. Policy Analysis and Information Systems, 4, 125–160.
Michalski, R. S. (1983). A theory and methodology of inductive learning. In R. S. Michalski, J. G. Carbonell, and T. M. Mitchell (Eds.), Machine learning: An artificial intelligence approach. San Mateo, CA: Morgan Kaufmann.
Mitchell, T. M. (1978). Version spaces: An approach to concept learning. Doctoral dissertation, Department of Electrical Engineering, Stanford University, Palo Alto, CA.
Moret, B. M. E. (1982). Decision trees and diagrams. Computing Surveys, 14, 593–623.
Quinlan, J. R. (1983). Learning efficient classification procedures and their application to chess end games. In R. S. Michalski, J. G. Carbonell, and T. M. Mitchell (Eds.), Machine learning: An artificial intelligence approach. San Mateo, CA: Morgan Kaufmann.
Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1, 81–106.
Quinlan, J. R. (1988). An empirical comparison of genetic and decision-tree classifiers. Proceedings of the Fifth International Conference on Machine Learning (pp. 135–141). Ann Arbor, MI: Morgan Kaufmann.
Schlimmer, J. C., and Fisher, D. (1986). A case study of incremental concept induction. Proceedings of the Fifth National Conference on Artificial Intelligence (pp. 496–501). Philadelphia, PA: Morgan Kaufmann.
Schlimmer, J. C., and Granger, R. H., Jr. (1986). Incremental learning from noisy data. Machine Learning, 1, 317–354.
Shannon, C. E. (1948). A mathematical theory of communication. Bell System Technical Journal, 27, 379–423.
Utgoff, P. E. (1988). ID5: An incremental ID3. Proceedings of the Fifth International Conference on Machine Learning (pp. 107–120). Ann Arbor, MI: Morgan Kaufmann.
Utgoff, P. E. (1989). Improved training via incremental learning. Proceedings of the Sixth International Workshop on Machine Learning. Ithaca, NY: Morgan Kaufmann.
Vere, S. A. (1980). Multilevel counterfactuals for generalizations of relational concepts and productions. Artificial Intelligence, 14, 138–164.
Watanabe, S. (1985). Pattern recognition: Human and mechanical. New York: Wiley and Sons.
Wilson, S. W. (1987). Classifier systems and the animal problem. Machine Learning, 2, 199–228.
