Greedy algorithm for decision tree construction in context of knowledge discovery problems

Mikhail Ju Moshkov*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

In the paper a greedy algorithm for minimization of decision tree depth is considered and bounds on the algorithm precision are discussed. Under some natural assumptions on the class NP and on the class of considered tables, this algorithm is, apparently, close to best approximate polynomial algorithms for minimization of decision tree depth. Unfortunately, the performance ratio of this algorithm grows almost as natural logarithm on the number of rows in the table. Except usual greedy algorithm we study greedy algorithm with threshold which constructs approximate decision trees. Such approach is fully admissible if we see on decision trees as on a way for knowledge representation. We obtain upper bounds on the depth of decision trees, constructed by this algorithms, which are independent of the number of rows in the table.

Original languageEnglish (US)
Pages (from-to)192-197
Number of pages6
JournalLecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)
Volume3066
StatePublished - 2004
Externally publishedYes

Keywords

  • Approximate decision tree
  • Data table
  • Greedy algorithm
  • Knowledge discovery

ASJC Scopus subject areas

  • Hardware and Architecture
  • Computer Science(all)
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'Greedy algorithm for decision tree construction in context of knowledge discovery problems'. Together they form a unique fingerprint.

Cite this