Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Greedy Algorithm with Weights for Decision Tree Construction

Wybrane pełne teksty z tego czasopisma
Warianty tytułu
Języki publikacji
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
Opis fizyczny
Bibliogr. 17 poz.
  • Division of Mathematical and Computer Sciences and Engineering, King Abdullah University of Science and Technology, P.O. Box 55455, Jeddah 21534, Saudi Arabia,
  • [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.
Typ dokumentu
Identyfikator YADDA
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.