×

zbMATH — the first resource for mathematics

Decision tree design by simulated annealing. (English) Zbl 0784.90104
Summary: In this research the simulated annealing algorithm is applied to design efficient classification and decision trees. Simulated annealing is a random search optimization algorithm. Other researchers have used the algorithm on similar types of combinatorial problems. For simple cost criteria, designs are obtained which match or improve upon those of an information theory greedy algorithm. Optimal solutions for several different cost functions are demonstrated along with cost efficient, robust designs that handle misclassification error.

MSC:
90C90 Applications of mathematical programming
91C99 Social and behavioral sciences: general topics
68T10 Pattern recognition, speech recognition
90C27 Combinatorial optimization
Software:
simannf90
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] E. AARTS and J. KORST, 1989, Simulated Annealing and Boltzmann Machines, John Wiley and Sons. Zbl0674.90059 MR983115 · Zbl 0674.90059
[2] A. J. BAYES, 1973, A dynamic programming algorithm to optimize decision table code, Australian Computer Journal, 5, 77-79.
[3] L. BREIMAN, J. FRIEDMAN, R. OLSHEN and C. STONE, 1984, Classification and Regression Trees, EDMAN, R. OLSH Wadsworth Int. Zbl0541.62042 MR726392 · Zbl 0541.62042
[4] R. S. BUCY and R. S. DIESPOSTI, 1991, Classification Tree Optimization by Simulated Annealing The Aerospace Corp., P.O. Box 92957, Los Angeles,California, USA 90009-2957, ATR No 91 (8073)-l. · Zbl 0784.90104
[5] A. CORANA, M. MARCHESI, C. MARTINI, S. RIDELLA, 1987, Minimizing multimodal functions of continuous variables with the simulated annealing algorithm, ACM Trans, on Mathematical Software, 13, 262-280. Zbl0632.65075 MR918580 · Zbl 0632.65075
[6] G. DEWEY, 1950, Relative Frequency of English Speech Sounds, Harvard University Press.
[7] A. EL GAMAL, L. HEMACHANDRA, I. SHPERLING and V. WEI, 1987, Using simulated annealing to design good codes, IEEE Trans. on Information Theory 33, 116-123.
[8] R. G. GALLAGER, 1968, Information Theory and Reliable Communication, John Wiley and Sons. Zbl0198.52201 · Zbl 0198.52201
[9] M. R. GAREY, 1970, Optimal Binary Decision Trees for Diagnostic Identification Problems, Ph. D. Thesis, Univ. of Wisconsin.
[10] M. R. GAREY and R. L. GRAHAM, 1974, Performance bounds on the splitting algorithm for binary testing, Acta Informatica, 3, 347-355. Zbl0276.68023 · Zbl 0276.68023
[11] C. R. P. HARTMANN, P. K. VARSHNEY, K. G. MEHROTRA and C. L. GERBERICH, 1982, Application of information theory to the construction of efficient decision trees, IEEE Trans, on Information Theory, 28, 565-577. Zbl0483.68064 · Zbl 0483.68064
[12] J. A. HERRERA-BALL, 1988, Theoretical Foundations and Algorithms for the Generation of Optimal Decision Trees, Ph. D. Thesis, Univ. of Tennessee.
[13] S. KIRKPATRICK, C. D. Jr. GELATT and M. P. VECCHI, 1983, Optimization by simulated annealing, Science, 220, 671-680. MR702485 · Zbl 1225.90162
[14] N. METROPOLIS, A. ROSENBLUTH, M. ROSENBLUTH, A. TELLER and E. TELLER, 1953, Equation of state calculation by fast Computing machines, J. of Chem. Physics, 21, 1087-1092.
[15] B. MORET, 1982, Decision trees and diagrams, Computing Surveys 14, 593-623.
[16] O. MURPHY, 1990, A unifying framework for trie design heuristics, Information Processing Letters 34, 243-249. Zbl0696.68035 MR1059987 · Zbl 0696.68035
[17] L. T. REINWALD, R. M. SOLAND, 1966, Conversion of limited entry décision tables to optimal computer programs I : minimum average processing time, J.Ass. Comput. Mach. 13, 339-358. Zbl0173.19505 · Zbl 0173.19505
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.