Application of Information Theory to the Construction of Efficient Decision Trees

Carlos R.P. Hartmann, Syracuse University
Varshney
Kishan Mehrotra, Syracuse University, Department of Electrical Engineering and Computer Science
Carl L. Gerberich, Syracuse University

SU-CIS-81-03

Description/Abstract

This paper treats the problem of conversion of decision tables to decision trees. In most cases, the construction of optimal decision trees is an NP-complete problem and, therefore, a heuristic approach to this problem is necessary. In our heuristic approach, we apply information theoretic concepts to construct efficient decision trees for decision tables which may include “don’t-care” entries. In contrast to most of the existing heuristic algorithms, our algorithm is systematic and has a sound theoretical justification. The algorithm has low design complexity and yet provides us with near-optimal decision trees.