Greedy Algorithm with Weights for Decision Tree Construction

• Autorzy: Moshkov M.Ju.
• Języki publikacji: EN

Abstrakty

EN

An approximate algorithm for minimization of weighted depth of decision trees is considered. A bound on accuracy of this algorithm is obtained which is unimprovable in general case. Under some natural assumptions on the class NP, the considered algorithm is close (from the point of view of accuracy) to best polynomial approximate algorithms for minimization of weighted depth of decision trees.

Słowa kluczowe

EN

decision table; decision tree; weight; greedy algorithm

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 104, nr 3
• Strony: 285--292
• Opis fizyczny: Bibliogr. 17 poz.

Twórcy

autor

Moshkov M.Ju.

• Division of Mathematical and Computer Sciences and Engineering, King Abdullah University of Science and Technology, P.O. Box 55455, Jeddah 21534, Saudi Arabia,

Bibliografia

• [1] Ahlswede, R., Wegener, I.: Suchprobleme, B.G. Teubner, Stuttgart, 1979.
• [2] Angluin, D.: Queries and concept learning, Machine Learning, 2(4), 1988, 319-342.
• [3] Ben-Or, M.: Lower bounds for algebraic computation trees, Proc. 15th ACM Annual Symp. on Theory of Comput., 1983.
• [4] Breiman, L., Friedman, J. H., Olshen, R. A., Stone, C. J.: Classification and Regression Trees, Chapman and Hall, New York, 1984.
• [5] Chegis, I. A., Yablonskii, S. V.: Logical methods of electric circuit control, Trudy MIAN SSSR, 51, 1958, 270-360 (in Russian).
• [6] Chvatal, V.: A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3), 1979, 233-235.
• [7] Feige, U.: A threshold of ln n for approximating set cover (Preliminary version), Proc. 28th ACM Annual Symp. on Theory of Comput., 1996.
• [8] Graham, R. L., Knuth, D. E., Patashnik, O.: Concrete Mathematics: A Foundation for Computer Science, 2nd ed., Addison-Wesley, Reading, MA, 1994.
• [9] Hellerstein, L., Pillaipakkamnatt, K., Raghavan, V. V., Wilkins, D.: How many queries are needed to learn? J. ACM, 43(5), 1996, 840-862.
• [10] Moshkov, M. Ju.: Conditional tests, in: Problems of Cybernetics 40 (S. V. Yablonskii, Ed.), Nauka Publishers, Moscow, 1983, 131-170 (in Russian).
• [11] Moshkov, M. Ju.: Classification of infinite information systems depending on complexity of decision trees and decision rule systems, Fundamenta Informaticae, 54(4), 2003, 345-368.
• [12] Moshkov, M. Ju.: Time complexity of decision trees, Transactions on Rough Sets III (J. F. Peters, A. Skowron, Eds.), LNCS 3400, Springer-Verlag, Berlin, 2005, 244-459.
• [13] Pawlak, Z.: Rough Sets - Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Dordrecht, 1991.
• [14] Picard, C. F.: Theorie des Questionnaires, Gauthier-Villars, Paris, 1965.
• [15] Quinlan, J. R.: C4.5: Programs for Machine Learning, Morgan Kaufmann, San Mateo, 1993.
• [16] Slavık, P.: Approximation algorithms for set cover and related problems, Ph.D. Thesis, University of New York at Buffalo, April 1998.
• [17] Yao, A.: Algebraic decision trees and Euler characteristics, Proc. IEEE FOCS, 1992.