Relationships for Cost and Uncertainty of Decision Trees

Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


This chapter is devoted to the design of new tools for the study of decision trees. These tools are based on dynamic programming approach and need the consideration of subtables of the initial decision table. So this approach is applicable only to relatively small decision tables. The considered tools allow us to compute: 1. Theminimum cost of an approximate decision tree for a given uncertainty value and a cost function. 2. The minimum number of nodes in an exact decision tree whose depth is at most a given value. For the first tool we considered various cost functions such as: depth and average depth of a decision tree and number of nodes (and number of terminal and nonterminal nodes) of a decision tree. The uncertainty of a decision table is equal to the number of unordered pairs of rows with different decisions. The uncertainty of approximate decision tree is equal to the maximum uncertainty of a subtable corresponding to a terminal node of the tree. In addition to the algorithms for such tools we also present experimental results applied to various datasets acquired from UCI ML Repository [4]. © Springer-Verlag Berlin Heidelberg 2013.
Original languageEnglish (US)
Pages (from-to)203-222
Number of pages20
JournalIntelligent Systems Reference Library
StatePublished - 2013

ASJC Scopus subject areas

  • Library and Information Sciences
  • Computer Science(all)
  • Information Systems and Management


Dive into the research topics of 'Relationships for Cost and Uncertainty of Decision Trees'. Together they form a unique fingerprint.

Cite this