Minimizing Size of Decision Trees for Multi-label Decision Tables
Mohammad Azad, Mikhail Moshkov
DOI: http://dx.doi.org/10.15439/2014F256
Citation: Proceedings of the 2014 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 2, pages 67–74 (2014)
Abstract. We used decision tree as a model to discover the knowledge from multi-label decision tables where each row has a set of decisions attached to it and our goal is to find out one arbitrary decision from the set of decisions attached to a row. The size of the decision tree can be small as well as very large. We study here different greedy algorithms as well as dynamic programming algorithms to minimize the size of the decision trees. Some of the considered algorithms are good enough for the minimization of number of nodes (at most 18.92\% difference), number of nonterminal nodes (at most 20.76\% difference), and number of terminal nodes (at most 18.71\% difference) relative to the optimal result obtained by dynamic programming algorithm.