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 language | English (US) |
---|---|
Title of host publication | KDIR 2011 - Proceedings of the International Conference on Knowledge Discovery and Information Retrieval |
Pages | 438-443 |
Number of pages | 6 |
State | Published - 2011 |
Event | International Conference on Knowledge Discovery and Information Retrieval, KDIR 2011 - Paris, France Duration: Oct 26 2011 → Oct 29 2011 |
Other
Other | International Conference on Knowledge Discovery and Information Retrieval, KDIR 2011 |
---|---|
Country | France |
City | Paris |
Period | 10/26/11 → 10/29/11 |
Keywords
- Decision trees
- Dynamic programming
- Greedy algorithms
ASJC Scopus subject areas
- Information Systems