Simulated annealing in the construction of near-optimal decision trees

The application of simulated annealing to the optimization of decision trees is investigated. An efficient perturbation procedure is described and used as the basis of the Simulated Annealing Classifier System or SACS algorithm. We show that the algorithm is asymptotically convergent for any choice of global cost function. The algorithm is then illustrated, using the Minimum Description Length Principle as cost function, by applying it to several problems involving both noisy and noise-free data.