Multi-pruning and restricted multi-pruning of decision trees

Fawaz Alsolami*, Mohammad Azad, Igor Chikalov, Mikhail Moshkov

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

1 Scopus citations


In this chapter, we consider two questions related to decision trees: (i) how to construct decision trees with reasonable number of nodes and reasonable number of misclassifications when they are used for knowledge representation, and (ii) how to improve the prediction accuracy of decision trees when they are used as classifiers. We created so-called multi-pruning approach based on dynamic programming algorithms for bi-criteria optimization of CART-like decision trees relative to the number of nodes and the number of misclassifications. This approach allows us to construct the set of all Pareto optimal points and to derive, for each such point, decision trees with parameters corresponding to that point. Experiments with decision tables from the UCI ML Repository show that, very often, we can find a suitable Pareto optimal point and derive a decision tree with small number of nodes at the expense of small increment in the number of misclassifications. Multi-pruning approach includes a procedure which constructs decision trees that, as classifiers, often outperform decision trees constructed by CART. We considered a modification of multi-pruning approach (restricted multi-pruning) that requires less memory and time but usually keeps the quality of constructed trees as classifiers or as a way for knowledge representation. Based on the uncertainty measure abs which is applicable both to decision tables with single- and many-valued decisions, we extended the considered approaches to the case of decision tables with many-valued decisions.

Original languageEnglish (US)
Title of host publicationIntelligent Systems Reference Library
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages22
StatePublished - 2020

Publication series

NameIntelligent Systems Reference Library
ISSN (Print)1868-4394
ISSN (Electronic)1868-4408

ASJC Scopus subject areas

  • General Computer Science
  • Information Systems and Management
  • Library and Information Sciences


Dive into the research topics of 'Multi-pruning and restricted multi-pruning of decision trees'. Together they form a unique fingerprint.

Cite this