An Approximate Algorithm for Decision Tree Design

Satoru OHTA

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E75-A    No.5    pp.622-630
Publication Date: 1992/05/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Optimization Techniques
decision tree,  pattern recognition,  optimization,  approximation algorithm,  statistical decision problem,  source coding,  polynomial time algorithm,  

Full Text: PDF>>
Buy this Article

Efficient probabilistic decision trees are required in various application areas such as character recognition. This paper presents a polynomial-time approximate algorithm for designing a probabilistic decision tree. The obtained tree is near-optimal for the cost, defined as the weighted sum of the expected test execution time and expected loss. The algorithm is advantageous over other reported heuristics from the viewpoint that the goodness of the solution is theoretically guaranteed. That is, the relative deviation of the obtained tree cost from the exact optimum is not more than a positive constant ε, which can be set arbitrarily small. When the given loss function is Hamming metric, the time efficiency is further improved by using the information theoretical lower bound on the tree cost. The time efficiency of the algorithm and the accuracy of the solutions were evaluated through computational experiments. The results show that the computing time increases very slowly with an increase in problem size and the relative error of the obtained solution is much less than the upper bound ε for most problems.