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.
Hartmann, Carlos R.P.; Varshney, Pramod; Mehrotra, Kishan; and Gerberich, Carl L., "APPLICATION OF INFORMATION THEORY TO THE CONSTRUCTION OF EFFICIENT DECISION TREES" (1981). Electrical Engineering and Computer Science - Technical Reports. 3.