CaltechAUTHORS
  A Caltech Library Service

Decision tree design from a communication theory standpoint

Goodman, Rodney M. and Smyth, Padhraic (1988) Decision tree design from a communication theory standpoint. IEEE Transactions on Information Theory, 34 (5). pp. 979-994. ISSN 0018-9448. http://resolver.caltech.edu/CaltechAUTHORS:20190314-130609598

[img] PDF - Published Version
See Usage Policy.

1377Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20190314-130609598

Abstract

A communication theory approach to decision tree design based on a top-town mutual information algorithm is presented. It is shown that this algorithm is equivalent to a form of Shannon-Fano prefix coding, and several fundamental bounds relating decision-tree parameters are derived. The bounds are used in conjunction with a rate-distortion interpretation of tree design to explain several phenomena previously observed in practical decision-tree design. A termination rule for the algorithm called the delta-entropy rule is proposed that improves its robustness in the presence of noise. Simulation results are presented, showing that the tree classifiers derived by the algorithm compare favourably to the single nearest neighbour classifier.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/18.21221DOIArticle
Additional Information:© 1988 IEEE. Manuscript received March 23, 1987; revised January 27, 1988. This work was supported in part by Pacific Bell. This paper was presented in part at the 1986 IEEE International Symposium on Information Theory, Ann Arbor, MI, October 1986.
Funders:
Funding AgencyGrant Number
Pacific BellUNSPECIFIED
Record Number:CaltechAUTHORS:20190314-130609598
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20190314-130609598
Official Citation:R. M. Goodman and P. Smyth, "Decision tree design from a communication theory standpoint," in IEEE Transactions on Information Theory, vol. 34, no. 5, pp. 979-994, Sept. 1988. doi: 10.1109/18.21221
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:93822
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:14 Mar 2019 21:14
Last Modified:14 Mar 2019 21:14

Repository Staff Only: item control page