Nothing Special   »   [go: up one dir, main page]

skip to main content
article
Open access

The Activity of a Variable and Its Relation to Decision Trees

Published: 01 October 1980 Publication History

Abstract

The construction of sequential testing procedures from functions of discrete arguments is a common problem in switching theory, software engineering, pattern recognition, and management. The concept of the activity of an argument is introduced, and a theorem is proved which relates it to the expected testing cost of the most general type of decision trees. This result is then extended to trees constructed from relations on finite sets and to decision procedures with cycles. These results are used, in turn, as the basis for a fast heuristic selection rule for constructing testing procedures. Finally, some bounds on the performance of the selection rule are developed.

References

[1]
AKERS, S.B. Binary decision diagrams. IEEE Trans. Comput. C-27, 6 (June 1978), 509-516.
[2]
BOZOYAN, SH.YE. Certain properties of Boolean differentials and the activities of the arguments of Boolean functions and questions of construction of reliable schemes that have unreliable elements. Eng. Cybern. 13, 5 (Sept. 1975), 108-120.
[3]
BREITBART, Y., AND REITER, A. Algorithms for fast evaluation of Boolean expressions. Acta Inf. 4 (1975), 107-116.
[4]
BREITBART, Y., AND RE~TER, A. A branch-and-bound algorithm to obtain an optimal evaluation tree for monotonic Boolean functions. Acta Inf. 4 (1975), 311-319.
[5]
CERNY, E., MANGE, D., AND SANCUEZ, E. Synthesis of minimal binary decision trees. IEEE Trans. Comput. C-28, 7 (July 1979), 472--482.
[6]
GANAPATHY, S., AND RAJAMARAN, V. Information theory applied to the conversion of decision tables to computer programs. Commun. ACM 16, 9 (Sept. 1973), 532-539.
[7]
GAREY, M.R. Optimal identification procedures. SIAM J. Appl. Math. 23, 2 (1972), 173-186.
[8]
HYAFIL, L., AND RIVEST, R.L. Constructing optimal binary decision trees is NP-complete. Inf. Proc. Letters 5, 1 (1976-1977), 15-17.
[9]
LEE, C.R. Representation of switching circuits by binary decision programs. Bell Syst. Tech. J. 38 (July 1959), 945-999.
[10]
MARTELLI, A., AND MONTANARI, U. Optimizing decision trees through heuristically guided search. Commun. ACM 21, 12 (Dec. 1978), 1025-1039.
[11]
METZNER, J.R., AND BARNES, B.M. Decision Table Languages and Systems. Academic Press, New York, 1977.
[12]
PAYNE, H.J., AND MEISEL, W.S. An algorithm for constructing optimal binary decision trees. IEEE Trans. Comput. C-26, 9 (Sept. 1977), 905-916.
[13]
PICARD, C.F. Graphes et Questionnaires, Volume 2: Questionnaires. Gauthier-Villars, Paris, 1972.
[14]
POLLACK, S.L. Conversion of limited-entry decision tables to computer programs. Commun. ACM 8, 11 (Nov. 1965), 677-682.
[15]
REINWALD, L.T., AND SOLAND, R.M. Conversion of limited-entry decision tables to computer programs I: Minimum average processing time. J. ACM 13, 3 (July 1966), 339-358.
[16]
ROUNDS, E.M. A combined non-parametric approach to feature selection and binary tree design. Proc. Conf. on Pattern Recognition and Image Processing, Chicago, Ill., 1979, pp. 38-43.
[17]
SHWAYDER, K. Extending the information theory approach to converting limited-entry decision tables to computer programs. Commun. ACM 17, 9 (Sept. 1974), 532-537.
[18]
WINDER, R.O. Chow parameters in threshold logic. J. ACM 18, 2 (April 1971), 265-289.
[19]
YAsuI, T. Some aspects of decision table conversion techniques. SIGPLAN Notices 6, 9 (Sept. 1971), 104-111.
[20]
You, K.C., AND FU, K.S. An approach to the design of a linear binary tree classifier. Proc. Symp. on Machine Processing of Remotely Sensed Data, Lafayette, Ind., 1976, pp. 3A1-3A10.

Cited By

View all
  • (2018)Different Kinds of Decision TreesExtensions of Dynamic Programming for Combinatorial Optimization and Data Mining10.1007/978-3-319-91839-6_4(35-48)Online publication date: 23-May-2018
  • (2014)Total Path Length and Number of Terminal Nodes for Decision TreesProcedia Computer Science10.1016/j.procs.2014.08.13235(514-521)Online publication date: 2014
  • (2013)Optimization and analysis of decision trees and rules: dynamic programming approachInternational Journal of General Systems10.1080/03081079.2013.79890242:6(614-634)Online publication date: Aug-2013
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems
ACM Transactions on Programming Languages and Systems  Volume 2, Issue 4
Oct. 1980
131 pages
ISSN:0164-0925
EISSN:1558-4593
DOI:10.1145/357114
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1980
Published in TOPLAS Volume 2, Issue 4

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)43
  • Downloads (Last 6 weeks)5
Reflects downloads up to 18 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2018)Different Kinds of Decision TreesExtensions of Dynamic Programming for Combinatorial Optimization and Data Mining10.1007/978-3-319-91839-6_4(35-48)Online publication date: 23-May-2018
  • (2014)Total Path Length and Number of Terminal Nodes for Decision TreesProcedia Computer Science10.1016/j.procs.2014.08.13235(514-521)Online publication date: 2014
  • (2013)Optimization and analysis of decision trees and rules: dynamic programming approachInternational Journal of General Systems10.1080/03081079.2013.79890242:6(614-634)Online publication date: Aug-2013
  • (2013)Comparison of Greedy Algorithms for Decision Tree OptimizationRough Sets and Intelligent Systems - Professor Zdzisław Pawlak in Memoriam10.1007/978-3-642-30341-8_3(21-40)Online publication date: 2013
  • (2013)Relationships Among Various Parameters for Decision Tree OptimizationInnovations in Intelligent Machines-410.1007/978-3-319-01866-9_13(393-410)Online publication date: 15-Nov-2013
  • (2011)Constructing an optimal decision tree for FAST corner point detectionProceedings of the 6th international conference on Rough sets and knowledge technology10.5555/2050461.2050492(187-194)Online publication date: 9-Oct-2011
  • (2011)Comparison of greedy algorithms for α-decision tree constructionProceedings of the 6th international conference on Rough sets and knowledge technology10.5555/2050461.2050491(178-186)Online publication date: 9-Oct-2011
  • (2011)Constructing an Optimal Decision Tree for FAST Corner Point DetectionRough Sets and Knowledge Technology10.1007/978-3-642-24425-4_26(187-194)Online publication date: 2011
  • (2011)Comparison of Greedy Algorithms for α-Decision Tree ConstructionRough Sets and Knowledge Technology10.1007/978-3-642-24425-4_25(178-186)Online publication date: 2011
  • (2009)Stochastic Decision TheoryProbability in the Engineering and Informational Sciences10.1017/S02699648000009663:01(13)Online publication date: 27-Jul-2009
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Full Access

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media