Approximate algorithm for minimization of decision tree depth

Mikhail J. Moshkov*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

7 Scopus citations

Abstract

In the paper a greedy algorithm for minimization of decision tree depth is described and bounds on the algorithm precision are considered. This algorithm is adapted for application to data tables with both discrete and continuous variables, which can have missing values. To this end we transform given data table into a decision table. Under some natural assumption on the class NP the considered algorithm is close to unimprovable approximate polynomial algorithms for minimization of decision tree depth.

Original languageEnglish (US)
Title of host publicationRough Sets, Fuzzy Sets, Data Mining and Granular Computing - 9th International Conference, RSFDGrC 2003, Proceedings
EditorsGuoyin Wang, Qing Liu, Yiyu Yao, Andrzej Skowron
PublisherSpringer Verlag
Pages611-614
Number of pages4
ISBN (Print)3540140409, 9783540140405
DOIs
StatePublished - Jan 1 2003
Event9th International Conference on Rough Sets, Fuzzy Sets, Data Mining and Granular Computing, RSFDGrC 2003 - Chongqing, China
Duration: May 26 2003May 29 2003

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2639
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other9th International Conference on Rough Sets, Fuzzy Sets, Data Mining and Granular Computing, RSFDGrC 2003
CountryChina
CityChongqing
Period05/26/0305/29/03

Keywords

  • Data table
  • Decision table
  • Decision tree
  • Depth

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Approximate algorithm for minimization of decision tree depth'. Together they form a unique fingerprint.

Cite this