The current availability of efficient algorithms for deci- sion tree induction makes intricate post-processing tech- niques 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 paramet- ric bottom-up algorithm integrating grafting with the standard pruning operator, and analyze its complexity in terms of the number of nodes visited. Immediate in- stances of the parametric algorithm include extensions of error based, reduced error, minimum error, and pes- simistic error pruning. Experimental results show that the computational cost of grafting is paid off by statis- Tically significant smaller trees without accuracy loss.
Subtree Replacement in Decision Tree Simplification
RUGGIERI, SALVATORE
2012-01-01
Abstract
The current availability of efficient algorithms for deci- sion tree induction makes intricate post-processing tech- niques 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 paramet- ric bottom-up algorithm integrating grafting with the standard pruning operator, and analyze its complexity in terms of the number of nodes visited. Immediate in- stances of the parametric algorithm include extensions of error based, reduced error, minimum error, and pes- simistic error pruning. Experimental results show that the computational cost of grafting is paid off by statis- Tically significant smaller trees without accuracy loss.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
