Comparison of greedy algorithms for α-decision tree construction

Abdulaziz Alkhalid; Igor Chikalov; Mikhail Moshkov

doi:10.1007/978-3-642-24425-4_25

Comparison of greedy algorithms for α-decision tree construction

Abdulaziz Alkhalid, Igor Chikalov, Mikhail Moshkov

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 Scopus citations

Abstract

A comparison among different heuristics that are used by greedy algorithms which constructs approximate decision trees (α-decision trees) is presented. The comparison is conducted using decision tables based on 24 data sets from UCI Machine Learning Repository [2]. Complexity of decision trees is estimated relative to several cost functions: depth, average depth, number of nodes, number of nonterminal nodes, and number of terminal nodes. Costs of trees built by greedy algorithms are compared with minimum costs calculated by an algorithm based on dynamic programming. The results of experiments assign to each cost function a set of potentially good heuristics that minimize it. © 2011 Springer-Verlag.

Original language	English (US)
Title of host publication	Rough Sets and Knowledge Technology
Publisher	Springer Nature
Pages	178-186
Number of pages	9
ISBN (Print)	9783642244247
DOIs	https://doi.org/10.1007/978-3-642-24425-4_25
State	Published - 2011

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-24425-4_25

Cite this

@inproceedings{a35e528139964d9b96795095d8ee8a10,

title = "Comparison of greedy algorithms for α-decision tree construction",

abstract = "A comparison among different heuristics that are used by greedy algorithms which constructs approximate decision trees (α-decision trees) is presented. The comparison is conducted using decision tables based on 24 data sets from UCI Machine Learning Repository [2]. Complexity of decision trees is estimated relative to several cost functions: depth, average depth, number of nodes, number of nonterminal nodes, and number of terminal nodes. Costs of trees built by greedy algorithms are compared with minimum costs calculated by an algorithm based on dynamic programming. The results of experiments assign to each cost function a set of potentially good heuristics that minimize it. {\textcopyright} 2011 Springer-Verlag.",

author = "Abdulaziz Alkhalid and Igor Chikalov and Mikhail Moshkov",

note = "KAUST Repository Item: Exported on 2020-10-01",

year = "2011",

doi = "10.1007/978-3-642-24425-4_25",

language = "English (US)",

isbn = "9783642244247",

pages = "178--186",

booktitle = "Rough Sets and Knowledge Technology",

publisher = "Springer Nature",

}

TY - GEN

T1 - Comparison of greedy algorithms for α-decision tree construction

AU - Alkhalid, Abdulaziz

AU - Chikalov, Igor

AU - Moshkov, Mikhail

N1 - KAUST Repository Item: Exported on 2020-10-01

PY - 2011

Y1 - 2011

N2 - A comparison among different heuristics that are used by greedy algorithms which constructs approximate decision trees (α-decision trees) is presented. The comparison is conducted using decision tables based on 24 data sets from UCI Machine Learning Repository [2]. Complexity of decision trees is estimated relative to several cost functions: depth, average depth, number of nodes, number of nonterminal nodes, and number of terminal nodes. Costs of trees built by greedy algorithms are compared with minimum costs calculated by an algorithm based on dynamic programming. The results of experiments assign to each cost function a set of potentially good heuristics that minimize it. © 2011 Springer-Verlag.

AB - A comparison among different heuristics that are used by greedy algorithms which constructs approximate decision trees (α-decision trees) is presented. The comparison is conducted using decision tables based on 24 data sets from UCI Machine Learning Repository [2]. Complexity of decision trees is estimated relative to several cost functions: depth, average depth, number of nodes, number of nonterminal nodes, and number of terminal nodes. Costs of trees built by greedy algorithms are compared with minimum costs calculated by an algorithm based on dynamic programming. The results of experiments assign to each cost function a set of potentially good heuristics that minimize it. © 2011 Springer-Verlag.

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

UR - http://link.springer.com/10.1007/978-3-642-24425-4_25

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

U2 - 10.1007/978-3-642-24425-4_25

DO - 10.1007/978-3-642-24425-4_25

M3 - Conference contribution

SN - 9783642244247

SP - 178

EP - 186

BT - Rough Sets and Knowledge Technology

PB - Springer Nature

ER -

Comparison of greedy algorithms for α-decision tree construction

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this