Abstract
Decision tree is one of the most commonly-used tools in data mining. Most popular induction algorithms construct decision trees in top-down manner. These algorithms generally select splitting feature only with regard to current nodes’ data, while ignoring history information. This kind of approaches need to search whole feature space during splitting each node and will be quite time-consuming in high-dimensional cases. To tackle this problem, we propose an impurity-based heuristic schema (IBH) to utilize history information to accelerate existing top-down induction algorithms. In details, when child node’s impurity is smaller than parent node’s, IBH takes feature performance in parent node as the pseudo upper bound of that in child node, to cut down unpromising computation. The feature selection of IBH biases toward the ones that perform better in parent nodes. Both mathematical analysis and experimental results demonstrate the coherence between IBH and original induction algorithms. Experiments show that IBH can significantly reduce induction time without accuracy degradation in both decision tree and related ensemble methods.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Baker, E., Jain, A.: On feature ordering in practice, some finite sample effects. In: Proceedings of the Third International Joint Conference on Pattern Recognition, pp. 45–49 (1976)
Breiman, L.: Bagging predictors. Mach. Learn. 24(2), 123–140 (1996)
Breiman, L., Friedman, J., Stone, C.J., Olshen, R.A.: Classification and Regression Trees. CRC Press, Boca Raton (1984)
Freund, Y., Schapire, R.E.: A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci. 55(1), 119–139 (1997)
Friedman, J.H.: Greedy function approximation: a gradient boosting machine. Ann. Stat., 1189–1232 (2001)
Gehrke, J., Ramakrishnan, R., Ganti, V.: Rainforest-a framework for fast decision tree construction of large datasets. In: VLDB, vol. 98, pp. 416–427 (1998)
Hyafil, L., Rivest, R.L.: Constructing optimal binary decision trees is np-complete. Inf. Process. Lett. 5(1), 15–17 (1976)
Quinlan, J.R.: Induction of decision trees. Mach. Learn. 1(1), 81–106 (1986)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Liu, J., Liu, Y., Zhong, J., Shen, W. (2016). Faster Decision Tree Induction with Impurity-Based Heuristic Schema. In: Yin, H., et al. Intelligent Data Engineering and Automated Learning – IDEAL 2016. IDEAL 2016. Lecture Notes in Computer Science(), vol 9937. Springer, Cham. https://doi.org/10.1007/978-3-319-46257-8_55
Download citation
DOI: https://doi.org/10.1007/978-3-319-46257-8_55
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-46256-1
Online ISBN: 978-3-319-46257-8
eBook Packages: Computer ScienceComputer Science (R0)