A Hill-Climbing Approach to Construct Near-Optimal Decision Trees
Abstract
We consider the problem of identifying the state of an $n$ component coherent system, where each component can be working or failed. It is costly to determine the states of the components. The goal is to find a decision tree which specifies the order of the components to be tested with minimum expected cost. The problem is known to be NP-hard. We present an extremely promising heuristic method for creating effective decision trees, and computational results show that the method obtains optimal solutions for $95 %$ of the cases tested.
Cite
Text
Sun et al. "A Hill-Climbing Approach to Construct Near-Optimal Decision Trees." Pre-proceedings of the Fifth International Workshop on Artificial Intelligence and Statistics, 1995.Markdown
[Sun et al. "A Hill-Climbing Approach to Construct Near-Optimal Decision Trees." Pre-proceedings of the Fifth International Workshop on Artificial Intelligence and Statistics, 1995.](https://mlanthology.org/aistats/1995/sun1995aistats-hillclimbing/)BibTeX
@inproceedings{sun1995aistats-hillclimbing,
title = {{A Hill-Climbing Approach to Construct Near-Optimal Decision Trees}},
author = {Sun, Xiaorong and Chiu, Steve Y. and Cox, Louis Anthony},
booktitle = {Pre-proceedings of the Fifth International Workshop on Artificial Intelligence and Statistics},
year = {1995},
pages = {513-519},
volume = {R0},
url = {https://mlanthology.org/aistats/1995/sun1995aistats-hillclimbing/}
}