A Hill-Climbing Approach to Construct Near-Optimal Decision Trees

Xiaorong Sun, Steve Y. Chiu, Louis Anthony Cox Jr
Pre-proceedings of the Fifth International Workshop on Artificial Intelligence and Statistics, PMLR R0:513-519, 1995.

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 this Paper

BibTeX
@InProceedings{pmlr-vR0-sun95a, title = {A Hill-Climbing Approach to Construct Near-Optimal Decision Trees}, author = {Sun, Xiaorong and Chiu, Steve Y. and Cox, Jr, Louis Anthony}, booktitle = {Pre-proceedings of the Fifth International Workshop on Artificial Intelligence and Statistics}, pages = {513--519}, year = {1995}, editor = {Fisher, Doug and Lenz, Hans-Joachim}, volume = {R0}, series = {Proceedings of Machine Learning Research}, month = {04--07 Jan}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/r0/sun95a/sun95a.pdf}, url = {https://proceedings.mlr.press/r0/sun95a.html}, 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.}, note = {Reissued by PMLR on 01 May 2022.} }
Endnote
%0 Conference Paper %T A Hill-Climbing Approach to Construct Near-Optimal Decision Trees %A Xiaorong Sun %A Steve Y. Chiu %A Louis Anthony Cox, Jr %B Pre-proceedings of the Fifth International Workshop on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 1995 %E Doug Fisher %E Hans-Joachim Lenz %F pmlr-vR0-sun95a %I PMLR %P 513--519 %U https://proceedings.mlr.press/r0/sun95a.html %V R0 %X 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. %Z Reissued by PMLR on 01 May 2022.
APA
Sun, X., Chiu, S.Y. & Cox, Jr, L.A.. (1995). A Hill-Climbing Approach to Construct Near-Optimal Decision Trees. Pre-proceedings of the Fifth International Workshop on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research R0:513-519 Available from https://proceedings.mlr.press/r0/sun95a.html. Reissued by PMLR on 01 May 2022.

Related Material