A Hill-Climbing Approach for Optimizing Classification Trees

We consider the problem of minimizing the expected cost of determining the correct value of a binary-valued function when it is costly to inspect the values of its arguments. This type of problem arises in distributed computing, in the design of diagnostic expert systems, in reliability analysis of multi-component systems, and in many other applications. Any feasible solution to the problem can be described by a sequential inspection procedure which is usually represented by a binary classification tree. In this paper, we propose an efficient hill-climbing algorithm to search for the optimal or near-optimal classification trees. Computational results show that the hill-climbing approach was able to find optimal solutions for 95% of the cases tested.