Decision trees

By Alin Dobra. Encyclopedia of Database Systems, 2018

1,384 citations recorded by the source corpus.

Linear regressors from X = R to Y = R have a limited expressive power, because they fit K affine functions to the training set. Functions that are more complex than that are approximated poorly. Similarly, K-class linear classifiers partition the data space X into K convex regions. If the true decision regions are not convex, performance suffers. This limited expressive power has also a silver lining: The number m of parameters of linear predictors is relatively small, m = K(d + 1), so that a linear predictor requires fewer training samples to train, relative to a more expressive predictor, in order to achieve a certain value for the training risk: Linear predictors have low sample complexity. As a result, they generalize better than more expressive ones. When we studied linear classifiers, we also saw the advantages of score-based classifiers: The K scores output by a K-class logistic-regression classifier can be interpreted as a probability distribution of the predicted label ŷ = h(x) given the input x, and this distribution can be used to compute some measure of the confidence of the answer. Decision trees combine the advantages of a score-based predictor (for both classifiers and regressors!) with the expressiveness deriving from a very flexible partition of X. Specifically, they recursively split X with hyperplanes, and they assign a single value (real number or label, depending on whether the problem is one of regression or classification) to each subset of the partition. This recursive splitting leads to effectively arbitrary expressiveness, as long as the partition is fine enough. Since the splitting is recursive, the resulting partition of the data space X can be represented by a strictly binary tree. As will be seen in more detail below, the root of the tree represents all of X, and contains the parameters of the hyper-plane used for the first split. The two children of the root represent the two half-spaces that that hyper-plane divides X into. Each of the two children in turn contains an additional hyper-plane that splits the child’s half-space, and the structure continues recursively. The tree can then be used for prediction: Given a data point x, check which side of the root partition it belongs to, and send it to the corresponding child. This check is repeated at every internal tree node encountered in this way, until a leaf is reached. The leaf corresponds to a (possibly small) convex region of X, and a single value is associated to that region. That value is the prediction y = h(x) returned by the tree. We will see in the next section how the hyper-planes are constructed, and how the prediction value at each leaf is computed. Staying at a high level for now, decision trees determine each of the hyper-planes greedily, by choosing the hyper-plane (out of a set of choices that is typically restricted, as we will see) that

Subfields: Information Systems

View Paper: https://www.semanticscholar.org/paper/e591ff5872ccd3bc28e91afb0329c2754772b63e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Systems

Citations in the corpus

The coefficient of determination R-squared is more informative than SMAPE, MAE, MAPE, MSE and RMSE in regression analysis evaluation (2021, positive): “…two of us authors used in a previous analysis ( Chicco & Jurman, 2021 ): Linear Regression ( Montgomery, Peck & Vining, 2021 ), Decision Trees ( Rokach & Maimon, 2005 ), and Random Forests ( Breiman, 2001 ), all implemented and executed in the R programming language ( Ihaka & Gentleman, 1996 ).”
Machine learning for molecular and materials science (2018, neutral): “Decision trees 27 are flowchart-like diagrams used to determine a course of action or outcomes.”
Machine learning in human movement biomechanics: Best practices, common pitfalls, and new opportunities (2018, neutral): “…(Kamruzzaman and Begg, 2006), determining cerebral palsy severity using motion capture data (Rozumalski and Schwartz, 2009; Sagawa et al., 2013; Trost et al., 2016; Zwick et al., 2004), characterizing movement patterns in post-stroke patients to inform targeted therapy (Huang and Patton, 2016;…”
Predicting ligand-dependent tumors from multi-dimensional signaling features (2017, background): “4b).(47,48) The second feature set did not contain the receptor expression explicitly but only signaling features derived from the computational model based on the receptor expression and the ligand stimulation (Fig.”
Causal analysis with Chain Event Graphs (2010, methodology): “In this our method is similar to that used in the construction of decision trees in decision analysis [29].”
Estimation of crop angle of inclination for lodged wheat using multi-sensor SAR data (2020, methodology): “SVR is a non-parametric machine-learning tool that relies on kernel functions which project the input data into a new (higher dimensional) hyperspace where complex non-linear trends can be represented in a simple manner (Brereton and Lloyd, 2010; Williams, 2011).”
Decision Tree Analysis on J48 Algorithm for Data Mining (2013, background): “• It can handle a variety of input data: Nominal, Numeric and Textual • Able to process erroneous datasets or missing values • High performance with small number of efforts •This can be implemented data mining packages over a variety of platforms [10].”
Protein Networks as Logic Functions in Development and Cancer (2011, background): “In general, however, decision trees can be readily applied to continuous gene activity values and multi-class scenarios [34].”
A Review on Machine Learning for EEG Signal Processing in Bioengineering (2020, background): “Once the data reaches the leaf, it can be classiﬁed under the class associated with that particular leaf [64].”