Comparison of greedy algorithms for decision tree construction

Abdulaziz Alkhalid*, Igor Chikalov, Mikhail Moshkov

*Corresponding author for this work

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

7 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationKDIR 2011 - Proceedings of the International Conference on Knowledge Discovery and Information Retrieval
Pages438-443
Number of pages6
StatePublished - 2011
EventInternational Conference on Knowledge Discovery and Information Retrieval, KDIR 2011 - Paris, France
Duration: Oct 26 2011Oct 29 2011

Other

OtherInternational Conference on Knowledge Discovery and Information Retrieval, KDIR 2011
CountryFrance
CityParis
Period10/26/1110/29/11

Keywords

  • Decision trees
  • Dynamic programming
  • Greedy algorithms

ASJC Scopus subject areas

  • Information Systems

Fingerprint Dive into the research topics of 'Comparison of greedy algorithms for decision tree construction'. Together they form a unique fingerprint.

Cite this