TY - JOUR
T1 - Application of Information Theory to the Construction of Efficient Decision Trees
AU - Hartmann, Carlos R.P.
AU - Varshney, Pramod K.
AU - Mehrotra, Kishan G.
AU - Gerberich, Carl L.
PY - 1982/7
Y1 - 1982/7
N2 - The problem of conversion of decision tables to decision trees is treated. 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 this heuristic approach, an application of information theoretic concepts to construct efficient decision trees for decision tables which may include “don’t care” entries is made. In contrast to most of the existing heuristic algorithms, this algorithm is systematic and is intuitively appealing from an information theoretic standpoint. The algorithm has low design complexity and yet provides near-optimal decision trees.
AB - The problem of conversion of decision tables to decision trees is treated. 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 this heuristic approach, an application of information theoretic concepts to construct efficient decision trees for decision tables which may include “don’t care” entries is made. In contrast to most of the existing heuristic algorithms, this algorithm is systematic and is intuitively appealing from an information theoretic standpoint. The algorithm has low design complexity and yet provides near-optimal decision trees.
UR - http://www.scopus.com/inward/record.url?scp=0020154199&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0020154199&partnerID=8YFLogxK
U2 - 10.1109/TIT.1982.1056522
DO - 10.1109/TIT.1982.1056522
M3 - Article
AN - SCOPUS:0020154199
SN - 0018-9448
VL - 28
SP - 565
EP - 577
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 4
ER -