
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

An Approximate Algorithm for Decision Tree Design
Satoru OHTA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E75A
No.5
pp.622630 Publication Date: 1992/05/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: PAPER Category: Optimization Techniques Keyword: decision tree, pattern recognition, optimization, approximation algorithm, statistical decision problem, source coding, polynomial time algorithm,
Full Text: PDF>>
Summary:
Efficient probabilistic decision trees are required in various application areas such as character recognition. This paper presents a polynomialtime approximate algorithm for designing a probabilistic decision tree. The obtained tree is nearoptimal 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.

