## Abstract

In the paper a greedy algorithm for minimization of decision tree depth is considered and bounds on the algorithm precision are discussed. Under some natural assumptions on the class NP and on the class of considered tables, this algorithm is, apparently, close to best approximate polynomial algorithms for minimization of decision tree depth. Unfortunately, the performance ratio of this algorithm grows almost as natural logarithm on the number of rows in the table. Except usual greedy algorithm we study greedy algorithm with threshold which constructs approximate decision trees. Such approach is fully admissible if we see on decision trees as on a way for knowledge representation. We obtain upper bounds on the depth of decision trees, constructed by this algorithms, which are independent of the number of rows in the table.

Original language | English (US) |
---|---|

Pages (from-to) | 192-197 |

Number of pages | 6 |

Journal | Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science) |

Volume | 3066 |

DOIs | |

State | Published - 2004 |

Externally published | Yes |

Event | 4th International Conference, RSCTC 2004 - Uppsala, Sweden Duration: Jun 1 2004 → Jun 5 2004 |

## Keywords

- Approximate decision tree
- Data table
- Greedy algorithm
- Knowledge discovery

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science