Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 2

Proceedings of the 2014 Federated Conference on Computer Science and Information Systems

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)

Full text

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.