Model Decision Tree: An Accelerated Algorithm of Decision Tree
YIN Ru1, MEN Changqian1, WANG Wenjian2, LIU Shuze3
1.School of Computer and Information Technology, Shanxi University, Taiyuan 030006 2.Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, Shanxi University, Taiyuan 030006 3.Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY 12180
Abstract The decision tree algorithm is constructed in a recursive style. Therefore, the low training efficiency is yielded and the over-classification of decision tree may produce overfitting. An accelerated algorithm called model decision tree(MDT) is proposed in this paper. An incomplete classification decision tree is established via the Gini index on the training dataset firstly. Then a simple model is utilized to classify impure pseudo leaf nodes, which are neither leaf nodes nor in the same class. Consequently, the final MDT is generated. Compared with DT, MDT improves the training efficiency with smaller loss of classification accuracy or even no loss. The experimental results on benchmark datasets show that the proposed MDT is much faster than DT and it has a certain ability to avoid overfitting.
Fund:Supported by National Natural Science Foundation of China(No.61673249), Research Project Supported by Shanxi Scholarship Council of China(No.2016-004), CERNET Innovation Project (No.NGII20170601)
Corresponding Authors:
WANG Wenjian(Corresponding author), Ph.D., professor. Her research interests include machine learning, intelligent computing and image processing.
About author:: YIN Ru, master student.Her research interests include machine learning.MEN Changqian, Ph.D., lecturer. His research interests include support vector machines, machine learning theory and kernel methods.LIU Shuze, undergraduate.
[1] AREL I, ROSE D C, KARNOWSKI T P. Deep Machine Learning-A New Frontier in Artificial Intelligence Research. IEEE Computational Intelligence Magazine, 2010, 5(4): 13-18. [2] SPECHT D F. Probabilistic Neural Networks. Neural Networks, 1990, 3(1): 109-118. [3] VAPNIK V N. Statistical Learning Theory. New York, USA: Wiley, 1998. [4] BAYES T. A Letter from the Late Reverend Mr. Thomas Bayes, F.R.S to John Canton, M.A. and F.R.S. Philosophical Transactions (1683-1775), 1763, 53: 269-271. [5] HINTON G, DENG L, YU D, et al. Deep Neural Networks for Acoustic Modeling in Speech Recognition: The Shared Views of Four Research Groups. IEEE Signal Processing Magazine, 2012, 29(6): 82-97. [6] 毛国军,段立娟,王 实.数据挖掘原理与算法.北京:清华大学出版社, 2005. (MAO G J, DUAN L J, WANG S. Data Mining Principles and Algorithms. Beijing, China: Tsinghua University Press, 2005.) [7] HAN J W, PEI J, KAMBER M. Data Mining: Concepts and Techniques. Amsterdam, The Netherlands: Elsevier, 2011. [8] QUINLAN J R. C4.5: Programs for Machine Learning. Amsterdam, The Netherlands: Elsevier, 2014. [9] MAI Q. A Review of Discriminant Analysis in High Dimensions. Wiley Interdisciplinary Reviews: Computational Statistics, 2013, 5(3): 190-197. [10] HARSITI, MUNANDAR T A, SIGIT H T. Implementation of Fu-zzy-C4.5 Classification as a Decision Support for Students Choice of Major Specialization. International Journal of Engineering Research and Technology, 2013, 2(11): 1577-1581. [11] LEE B K, JEONG E H, LEE S S. Context-Awareness Healthcare for Disease Reasoning Based on Fuzzy Logic. Journal of Electrical Engineering and Technology, 2016, 11(1): 247-256. [12] MEHTA M, AGRAWAL R, RISSANEN J. SLIQ: A Fast Scalable Classifier for Data Mining // Proc of the International Conference on Extending Database Technology. Berlin, Germany: Springer, 1996: 18-32. [13] SHAFER J, AGRAWAL R, MEHTA M. SPRINT: A Scalable Parallel Classifier for Data Mining[C/OL]. [2017-02-25]. http://www.vldb.org/conf/1996/P544.PDF. [14] FRIEDMAN J H, OLSHEN R A, STONE C J, et al. Classification and Regression Trees. Boca Raton, USA: CRC Press, 1984. [15] KASS G V. An Exploratory Technique for Investigating Large Quan-tities of Categorical Data. Applied Statistics, 1980, 29(2): 119-127. [16] ANKERST M, ELSEN C, ESTER M, et al. Visual Classification: An Interactive Approach to Decision Tree Construction // Proc of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 1999: 392-396. [17] DURKIN J,蔡竞峰,蔡自兴.决策树技术及其当前研究方向.控制工程, 2005, 12(1): 15-18, 21. (DURKIN J, CAI J F, CAI Z X. Decision Tree Technique and Its Current Research. Control Engineering of China, 2005, 12(1): 15-18, 21.) [18] YILDIZ C T, ALPAYDIN E. Omnivariate Decision Trees. IEEE Transactions on Neural Networks, 2001, 12(6): 1539-1546. [19] SUN H N, HU X G. Attribute Selection for Decision Tree Learning with Class Constraint. Chemometrics and Intelligent Laboratory Systems, 2017, 163: 16-23. [20] SOK H K, OOI M P L, KUANG Y C. Sparse Alternating Decision Tree. Pattern Recognition Letters, 2015, 60/61: 57-64. [21] SOK H K, OOI M P L, KUANG Y C, et al. Multivariate Alternating Decision Trees. Pattern Recognition, 2016, 50: 195-209. [22] FRIEDMAN J H. Greedy Function Approximation: A Gradient Boosting Machine. The Annals of Statistics, 2001, 29(5): 1189-1232. [23] CHEN T Q, HE T. Xgboost: eXtreme Gradient Boosting[J/OL]. [2018-02-25]. http://ydl.oregonstate.edu/pub/cran/web/packages/xgboost/vignettes/xgboost.pdf. [24] KE G L, MENG Q, FINLEY T, et al. LightGBM: A Highly Efficient Gradient Boosting Decision Tree // GUYON I, LUXBURG U V, BENGIO S, et al., eds. Advances in Neural Information Processing Systems 30. Cambridge, USA: The MIT Press, 2017: 3149-3157. [25] FAN R E, CHANG K W, HSIEH C J, et al. LIBLINEAR: A Library for Large Linear Classification. Journal of Machine Learning Research, 2008, 9: 1871-1874.
2018, Vol. 31 
