Subtree Replacement in Decision Tree Simplification
By Salvatore Ruggieri. 2012
5 citations recorded by the source corpus.
The current availability of efficient algorithms for decision tree induction makes intricate post-processing techniques worth to be investigated both for efficiency and effectiveness. We study the simplification operator of subtree replacement, also known as grafting, originally implemented in the C4.5 system. We present a parametric bottom-up algorithm integrating grafting with the standard pruning operator, and analyze its complexity in terms of the number of nodes visited. Immediate instances of the parametric algorithm include extensions of error based, reduced error, minimum error, and pessimistic error pruning. Experimental results show that the computational cost of grafting is paid off by statistically significant smaller trees without accuracy loss.
Subfields: Artificial Intelligence, Information Systems
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Salvatore Ruggieri
- Dino Pedreschi
- Riccardo Guidotti
- Fosca Giannotti
- Anna Monreale
- Franco Turini
- Sara Hajian
- Indrė Žliobaitė
In Information Systems
- Salvatore Ruggieri
- Franco Turini
- Riccardo Guidotti
- Fosca Giannotti
- Anna Monreale
- Dino Pedreschi
- Sara Hajian
- Andrea Romei
Citations in the corpus
- A Survey of Methods for Explaining Black Box Models (2018, methodology): “The most well-known simplification method is decision tree pruning, which relies on an error estimation function to compare the errors of the two alternatives: to prune a subtree or not [101].”
- Complete Search for Feature Selection in Decision Trees (2019, background): “Generalization errors are now almost always smaller for all strategies (for Coil2000 the improvement is vast), confirming that tree simplification is an effective strategy (Ruggieri, 2012).”