Bounds on Average Time Complexity of Decision Trees

Igor Chikalov

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

In this chapter, bounds on the average depth and the average weighted depth of decision trees are considered. Similar problems are studied in search theory [1], coding theory [77], design and analysis of algorithms (e.g., sorting) [38]. For any diagnostic problem, the minimum average depth of decision tree is bounded from below by the entropy of probability distribution (with a multiplier 1/log2 k for a problem over a k-valued information system). Among diagnostic problems, the problems with a complete set of attributes have the lowest minimum average depth of decision trees (e.g, the problem of building optimal prefix code [1] and a blood test study in assumption that exactly one patient is ill [23]). For such problems, the minimum average depth of decision tree exceeds the lower bound by at most one. The minimum average depth reaches the maximum on the problems in which each attribute is "indispensable" [44] (e.g., a diagnostic problem with n attributes and kn pairwise different rows in the decision table and the problem of implementing the modulo 2 summation function). These problems have the minimum average depth of decision tree equal to the number of attributes in the problem description. © Springer-Verlag Berlin Heidelberg 2011.
Original languageEnglish (US)
Pages (from-to)15-39
Number of pages25
JournalAverage Time Complexity of Decision Trees
Volume21
DOIs
StatePublished - 2011

ASJC Scopus subject areas

  • Library and Information Sciences
  • General Computer Science
  • Information Systems and Management

Fingerprint

Dive into the research topics of 'Bounds on Average Time Complexity of Decision Trees'. Together they form a unique fingerprint.

Cite this