COMPARISON OF GREEDY ALGORITHMS FOR DECISION TREE CONSTRUCTION

Abdulaziz Alkhalid, Igor Chikalov, Mikhail Moshkov

2011

Abstract

The paper compares different heuristics that are used by greedy algorithms for constructing of decision trees. Exact learning problem with all discrete attributes is considered that assumes absence of contradictions in the decision table. Reference decision tables are based on 24 data sets from UCI Machine Learning Repository (Frank and Asuncion, 2010). Complexity of decision trees is estimated relative to several cost functions: depth, average depth, and number of nodes. Costs of trees built by greedy algorithms are compared with exact minimums calculated by an algorithm based on dynamic programming. The results associate to each cost function a set of potentially good heuristics that minimize it.

Paper Citation

in Harvard Style

Alkhalid A., Chikalov I. and Moshkov M. (2011). COMPARISON OF GREEDY ALGORITHMS FOR DECISION TREE CONSTRUCTION . In Proceedings of the International Conference on Knowledge Discovery and Information Retrieval - Volume 1: KDIR, (IC3K 2011) ISBN 978-989-8425-79-9, pages 430-435. DOI: 10.5220/0003654904380443

in Bibtex Style

@conference{kdir11,
author={Abdulaziz Alkhalid and Igor Chikalov and Mikhail Moshkov},
title={COMPARISON OF GREEDY ALGORITHMS FOR DECISION TREE CONSTRUCTION},
booktitle={Proceedings of the International Conference on Knowledge Discovery and Information Retrieval - Volume 1: KDIR, (IC3K 2011)},
year={2011},
pages={430-435},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003654904380443},
isbn={978-989-8425-79-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Knowledge Discovery and Information Retrieval - Volume 1: KDIR, (IC3K 2011)
TI - COMPARISON OF GREEDY ALGORITHMS FOR DECISION TREE CONSTRUCTION
SN - 978-989-8425-79-9
AU - Alkhalid A.
AU - Chikalov I.
AU - Moshkov M.
PY - 2011
SP - 430
EP - 435
DO - 10.5220/0003654904380443