Splitting Choice and Computational Complexity Analysis of Decision Trees
Open Access
Abstract
Some theories are explored in this research about decision trees which give theoretical support to the applications based on decision trees. The first is that there are many splitting criteria to choose in the tree growing process. The splitting bias that influences the criterion chosen due to missing values and variables with many possible values has been studied. Results show that the Gini index is superior to entropy information as it has less bias regarding influences. The second is that noise variables with more missing values have a better chance to be chosen while informative variables do not. The third is that when there are many noise variables involved in the tree building process, it influences the corresponding computational complexity. Results show that the computational complexity increase is linear to the number of noise variables. So methods that decompose more information from the original data but increase the variable dimension can also be considered in real applications.Keywords
Funding Information
- Fundamental Research Funds for the Central Universities (2242020R40073, MCCSE2021B02, 2242020R10053, 2242020R40073, MCCSE2021B02, 2242020R10053)
- Guangdong Basic and Applied Basic Research Foundation (2020A1515110129, 2020A1515110129)
- Jiangsu Science Foundation for Youths (BK20200347)
- Nanjing Scientific and Technological Innovation Foundation for Selected Returned Overseas Chinese Scholars (1107010306, 1108000241)
- Jiangsu Foundation for Innovative and Entrepreneurial Doctor (1108000245, 1108000245)
- National Natural Science Foundation of China (62103105, 12171085, 62103105, 12171085)
- Natural Science Foundation of Jiangsu Province (BK20200347, BK20210218)
- Nanjing Scientific and Technological Innovation Foundation for Selected Returned Overseas Chinese Scholars (1107010306, 1108000241)
This publication has 20 references indexed in Scilit:
- Binary PSO with mutation operator for feature selection using decision tree applied to spam detectionKnowledge-Based Systems, 2014
- Classification and regression treesWIREs Data Mining and Knowledge Discovery, 2011
- Unbiased split selection for classification trees based on the Gini IndexComputational Statistics & Data Analysis, 2007
- Unbiased Recursive Partitioning: A Conditional Inference FrameworkJournal of Computational and Graphical Statistics, 2006
- A Lego System for Conditional InferenceThe American Statistician, 2006
- Probabilistic neural networksNeural Networks, 1990
- On the approximate realization of continuous mappings by neural networksNeural Networks, 1989
- Induction of decision treesMachine Learning, 1986
- An Exploratory Technique for Investigating Large Quantities of Categorical DataJournal of the Royal Statistical Society Series C: Applied Statistics, 1980
- Estimation of the probability of an event as a function of several independent variablesBiometrika, 1967