For Full-Text 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.
Optimal Decision Tree Design Based on Information Theoretical Cost Bound
Satoru OHTA Fumio KANAYA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1991/09/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Issue on Information Theory and Its Applications)
Full Text: PDF>>
Decision tree design is an important issue because decision trees have many applications in, for example, fault diagnosis and character recognition. This paper describes an algorithm designing a probabilistic decision tree, in which a test applied to a state produces different outcomes with non-zero probability. The algorithm strictly minimizes the tree cost, which is defined as the weighted sum of expected loss and expected test execution time. The lower bound of the cost is utillized to remove the excessive computing time needed to search for the exact optimum. This lower bound is derived from information theory and is transformed to an easily computable representation by introducing a network model. The result of a computational experiment confirms the time efficiency of the proposed method.