SOME BOUNDS ON MINIMAL DECISION TREE DEPTH

Article type: Research Article

Authors: Moshkov, Mikhail

Affiliations: Research Institute for Applied Mathematics and Cybernetics of the Nizhni Novgorod State University, 10, Uljanova St., Nizhni Novgorod, 603005, Russia

Note: [] Most part of this work was done when the author visited the Institute of Mathematics at Warsaw University. Also it was supported by Russian Foundation for Fundamental Research (grant # 93-01-00488). The travel to RSKD'93 was supported by International Science Foundation (grant # 0701).

Abstract: We investigate decision trees for decision tables. We present upper and lower bounds on the minimal decision tree depth. Some bounds are expressed by parameters of decision rule systems constructed for decision tables.

Keywords: decision table, decision rule, decision tree, depth, bounds

DOI: 10.3233/FI-1996-272307

Journal: Fundamenta Informaticae, vol. 27, no. 2-3, pp. 197-203, 1996