Greedy algorithm with weights for decision tree construction

Mikhail Moshkov

doi:10.3233/FI-2010-350

Greedy algorithm with weights for decision tree construction

Mikhail Moshkov

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

An approximate algorithm for minimization of weighted depth of decision trees is considered. A bound on accuracy of this algorithm is obtained which is unimprovable in general case. Under some natural assumptions on the class NP, the considered algorithm is close (from the point of view of accuracy) to best polynomial approximate algorithms for minimization of weighted depth of decision trees.

Original language	English (US)
Pages (from-to)	285-292
Number of pages	8
Journal	Fundamenta Informaticae
Volume	104
Issue number	3
DOIs	https://doi.org/10.3233/FI-2010-350
State	Published - Dec 1 2010

ASJC Scopus subject areas

Computational Theory and Mathematics
Algebra and Number Theory
Theoretical Computer Science
Information Systems

Access to Document

10.3233/FI-2010-350

Cite this

@article{aa5eac689587482c907b9c83ff7dd34a,

title = "Greedy algorithm with weights for decision tree construction",

abstract = "An approximate algorithm for minimization of weighted depth of decision trees is considered. A bound on accuracy of this algorithm is obtained which is unimprovable in general case. Under some natural assumptions on the class NP, the considered algorithm is close (from the point of view of accuracy) to best polynomial approximate algorithms for minimization of weighted depth of decision trees.",

author = "Mikhail Moshkov",

note = "KAUST Repository Item: Exported on 2020-10-01 Acknowledgements: This work was partially supported by the KAUST-Stanford AEA program. The author is greatly indebted to the anonymous reviewer for helpful comments and suggestions.",

year = "2010",

month = dec,

day = "1",

doi = "10.3233/FI-2010-350",

language = "English (US)",

volume = "104",

pages = "285--292",

journal = "Fundamenta Informaticae",

issn = "0169-2968",

publisher = "IOS Press",

number = "3",

}

TY - JOUR

T1 - Greedy algorithm with weights for decision tree construction

AU - Moshkov, Mikhail

N1 - KAUST Repository Item: Exported on 2020-10-01 Acknowledgements: This work was partially supported by the KAUST-Stanford AEA program. The author is greatly indebted to the anonymous reviewer for helpful comments and suggestions.

PY - 2010/12/1

Y1 - 2010/12/1

N2 - An approximate algorithm for minimization of weighted depth of decision trees is considered. A bound on accuracy of this algorithm is obtained which is unimprovable in general case. Under some natural assumptions on the class NP, the considered algorithm is close (from the point of view of accuracy) to best polynomial approximate algorithms for minimization of weighted depth of decision trees.

AB - An approximate algorithm for minimization of weighted depth of decision trees is considered. A bound on accuracy of this algorithm is obtained which is unimprovable in general case. Under some natural assumptions on the class NP, the considered algorithm is close (from the point of view of accuracy) to best polynomial approximate algorithms for minimization of weighted depth of decision trees.

UR - http://hdl.handle.net/10754/561592

UR - https://www.medra.org/servlet/aliasResolver?alias=iospress&doi=10.3233/FI-2010-350

UR - http://www.scopus.com/inward/record.url?scp=78650649463&partnerID=8YFLogxK

U2 - 10.3233/FI-2010-350

DO - 10.3233/FI-2010-350

M3 - Article

SN - 0169-2968

VL - 104

SP - 285

EP - 292

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

IS - 3

ER -

Greedy algorithm with weights for decision tree construction

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this