Bounds on Average Weighted Depth of Decision Trees

Article type: Research Article

Authors: Moshkov, Mikhail | Chikalov, Igor

Affiliations: Research Institute for Applied Mathematics and Cybernetics of Nizhni Novgorod State University, 10, Uljanova St., Nizhni Novgorod, 603005, Russia. [email protected] | Faculty of Calculating Mathematics and Cybernetics of Nizhni Novgorod State University 23, Gagarina Av., Nizhni Novgorod, 603600, Russia

Abstract: Upper and lower bounds on minimal average weighted depth and minimal average depth of decision trees over arbitrary information systems are considered. In proofs methods of test theory and rough set theory are used.

Keywords: Information system, decision tree, average weighted depth

DOI: 10.3233/FI-1997-31204

Journal: Fundamenta Informaticae, vol. 31, no. 2, pp. 145-156, 1997