![\"\"](\"https:\/\/miro.medium.com\/v2\/resize:fit:640\/format:webp\/1*UtNgeZ3E7YLln25VS5mwxg.png)
<\/picture>Tree-based machine learning methods are among the most commonly used supervised learning methods. They are constructed by two entities; branches and nodes. Tree-based ML methods are built by recursively splitting a training sample, using different features from a dataset at each node that splits the data most effectively. The splitting is based on learning simple decision rules inferred from the training data.<\/p>\n
Generally, tree-based ML methods are simple and intuitive; to predict a class label or value, we start from the top of the tree or the root and, using branches, go to the nodes by comparing features on the basis of which will provide the best split.<\/p>\n
Tree-based methods also use the mean for continuous variables or mode for categorical variables when making predictions on training observations in the regions they belong to.<\/p>\n
Since the set of rules used to segment the predictor space can be summarized in a visual representation with branches that show all the possible outcomes, these approaches are commonly referred to as decision tree methods<\/strong>.<\/p>\n The methods are flexible and can be applied to either classification or regression problems. Classification and Regression Trees<\/em> (CART) is a commonly used term by Leo Breiman, referring to the flexibility of the methods in solving both linear and non-linear predictive modeling problems.<\/p>\n Decision trees can be classified based on the type of target or response variable.<\/p>\n The default type of decision trees, used when the response variable is categorical\u2014i.e. predicting whether a team will win or lose a game.<\/p>\n Used when the target variable is continuous or numerical in nature\u2014i.e. predicting house prices based on year of construction, number of rooms, etc.<\/p>\n i) Root node<\/strong> \u2014 this represents the entire population or the sample, which gets divided into two or more homogenous subsets.<\/p>\n ii) Splitting <\/strong>\u2014 subdividing a node into two or more sub-nodes.<\/p>\n iii) Decision node <\/strong>\u2014 this is when a sub-node is divided into further sub-nodes.<\/p>\n iv) Leaf\/Terminal node<\/strong> \u2014 this is the final\/last node that we consider for our model output. It cannot be split further.<\/p>\n v) Pruning \u2014 <\/strong>removing unnecessary sub-nodes of a decision node to combat overfitting.<\/p>\n vi) Branch\/Sub-tree<\/strong> \u2014 the sub-section of the entire tree.<\/p>\n vii) Parent and Child node <\/strong>\u2014 a node that\u2019s subdivided into a sub-node is a parent, while the sub-node is the child node.<\/p>\n The decision of splitting a tree affects its accuracy. Tree-based machine learning models use multiple algorithms to decide where to split a node into two or more sub-nodes. The creation of sub-nodes increases the homogeneity of the resultant sub-nodes. Algorithm selection is based on the type of target variable.<\/p>\n Suppose you\u2019re the basketball coach of a grade school. The inter-school basketball competitions are nearby and you want to do a survey to determine which students play basketball in their leisure time. The sample selected is 40 students. The selection criterion is based on a number of factors such as gender, height, and class.<\/p>\n As a coach, you\u2019d want to select the students based on the most significant input variable among the three variables.<\/p>\n Decision tree algorithms will help the coach identify the right sample of students using the variable, which creates the best homogenous set of student players.<\/p>\n CART is used to train a decision tree. It first splits the training set into two subsets using a single feature k and threshold tk\u2014i.e. height\u2265150cm. The algorithm searches for the pair (k, tk) that produces the purest subsets. The cost function for the classification the algorithm tries to minimize is given by:<\/p>\n The CART algorithm splits the child nodes using the same approach recursively, and once it reaches the max-depth, it stops.<\/p>\n We\u2019ll now have a look at the two commonly-used criteria for measuring the impurity of a node; the Gini index and entropy.<\/p>\n The Gini index states that if we select two items from a population at random, then they must be of the same class and probability if the population is pure. The target variable is normally categorical, such as pass or fail, and it performs only binary splits. The higher the value of the Gini index, the higher the homogeneity. The CART algorithm uses the Gini method to create binary splits.<\/p>\n Referring to the example above, where the basketball coach wants to separate students based on whether they play basketball or not\u2014using the input variables gender, height, and class, we\u2019ll identify which split produces the most homogenous sub-nodes using the Gini index.<\/p>\n Calculating:<\/p>\n Calculating:<\/p>\n Calculating:<\/p>\n It\u2019s evident that the split based on gender has the highest Gini index, hence the split will take place on gender, which will result in the most homogenous sub-nodes.<\/p>\n If we want to calculate the Gini impurity:<\/p>\n 1 \u2014 Gini index<\/p>\n The split on class has the highest Gini impurity and will produce the least homogenous sub-nodes.<\/p>\n In machine learning, entropy is commonly used as an impurity measure. If a sample is completely homogenous, the entropy is zero, and if the sample is equally divided (50%-50%), it has an entropy of one.<\/p>\n Entropy is calculated by the following equation:<\/p>\n P and q are the probability of, say, success and failure in a particular node. Entropy can also be applied to categorical target variables. The lesser the entropy, the better the split.<\/p>\n We\u2019ll now calculate the entropy for all the gender, height, and class nodes in the above example.<\/p>\n It\u2019s evident that the split on gender has the lowest entropy; hence, the most favorable split, which will give homogenous results.<\/p>\n Information gain can be calculated from entropy and is given as:<\/p>\n Information gain = 1 \u2014 entropy<\/strong><\/p>\n Decision trees make very few assumptions about the training data, as opposed to linear models which assume the data is linear.<\/p>\n The tree structure adapts itself to the training data if left unconstrained, resulting in overfitting. Such a model is known as a non-parametric model. The number of parameters in such a model isn\u2019t determined prior to training and the model structure is free to fit closely to the data.<\/p>\n A parametric model, such as a linear model, has a predetermined number of parameters; thus, its degree of freedom is limited. This reduces the risk of overfitting but increases the risk of underfitting. In order to avoid overfitting on the training data, we need to restrict the decision tree\u2019s freedom during training. This is known as regularization.<\/p>\n The regularization of hyperparameters depends on the algorithm used. Decision tree classifier algorithms use hyperparameters that restrict the shape of the decision tree, thus preventing both overfitting and underfitting. They include:<\/p>\n This is the minimum number of samples a node must have before it can be split. It reduces overfitting.<\/p>\n The minimum number of samples a leaf node must have.<\/p>\n The maximum depth of a tree. A higher depth allows the model to learn relations that are very specific to a particular sample.<\/p>\n The maximum number of leaf nodes.<\/p>\n The maximum number of features that are evaluated for splitting at each node.<\/p>\n It\u2019s the same as mini_samples_leaf but expressed as a fraction of the total number of weighted instances.<\/p>\n Increasing the min_* hyperparameters or reducing max_* hyperparameters regularizes the model.<\/p>\n The figure above shows a decision tree trained with the default hyperparameters (no restrictions), and on the right, it\u2019s trained with min_samples_leaf=4. It\u2019s evident that the model on the left is overfitting, while the model on the right generalizes better to unseen data.<\/p>\n How do we implement pruning in decision trees?<\/p>\n A decision tree without constraints such as Standard statistical tests such as the X2 test are used to estimate the probability that the improvement is purely a result of chance (null hypothesis).<\/p>\n If the probability (p-value) is higher than a given threshold (5%), then the node is considered unnecessary, and its children are deleted. Pruning continues until all the unnecessary nodes have been removed.<\/p>\n If we aggregate the predictions of a group of predictors (regressor or classifier), we\u2019ll often get better predictions than with the individual predictor.<\/p>\n A group of predictive models that aim to achieve model accuracy and stability is called an ensemble, and the technique used to achieve accuracy is ensemble learning. An ensemble learning algorithm, such as random forest, is an ensemble method.<\/p>\n We can train a group of decision tree classifiers, each on a different random subset of the training set. To make the final prediction, we obtain the predictions of all the individual trees, then predict the class that gets the most votes.<\/p>\n Such an ensemble of decision trees is called a random forest and is one of the most powerful machines learning algorithms out there for simple classification or regression tasks. It\u2019s able to undertake dimensional reduction methods, treat missing values, outlier values, and perform other exploratory data analysis steps.<\/p>\n Random forest algorithms introduce extra randomness when growing trees\u2014 instead of searching for the very best feature when splitting a node, it searches for the best feature among a random subset of features. This results in a greater tree diversity, yielding an overall better model.<\/p>\n Tree-based algorithms are really important for every data scientist to learn. In this article, we\u2019ve covered a wide range of details about tree-based methods; their features and structure, attribute selection algorithms (entropy, Gini index), and random forests.<\/p>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":" Photo by Jay Mantri on Unsplash Tree-based machine learning methods are among the most commonly used supervised learning methods. They are constructed by two entities; branches and nodes. Tree-based ML methods are built by recursively splitting a training sample, using different features from a dataset at each node that splits the data most effectively. The […]<\/p>\n","protected":false},"author":71,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"customer_name":"","customer_description":"","customer_industry":"","customer_technologies":"","customer_logo":"","footnotes":""},"categories":[6],"tags":[],"coauthors":[169],"class_list":["post-7866","post","type-post","status-publish","format-standard","hentry","category-machine-learning"],"yoast_head":"\nTypes of Decision Trees<\/strong><\/h1>\n
i.<\/strong> Classification Trees<\/strong><\/h2>\n
ii.<\/strong> Regression Trees<\/strong><\/h2>\n
Advantages of Tree-based Machine Learning Methods<\/strong><\/h1>\n
\n
Disadvantages<\/strong> of Tree-based Machine Learning Methods<\/strong><\/h1>\n
\n
Common Terminology<\/strong><\/h1>\n
![\"\"](\"https:\/\/miro.medium.com\/v2\/resize:fit:688\/1*UtNgeZ3E7YLln25VS5mwxg.png\")
<\/figure>Algorithms in Tree-based Machine Learning Models<\/strong><\/h1>\n
![\"\"](\"https:\/\/miro.medium.com\/v2\/resize:fit:700\/1*jIvLFgIrpRbxFOpNitAFqQ.png\")
<\/figure>Classification and Regression Tree (CART) Training Algorithm<\/strong><\/h1>\n
![\"\"](\"https:\/\/miro.medium.com\/v2\/resize:fit:700\/1*ucy_glLBKAHjlrWgqOB_Lg.png\")
<\/figure>i)<\/strong> Gini Index<\/strong><\/h2>\n
Calculating the Gini index<\/strong><\/h2>\n
\n
Split on Gender<\/strong><\/h2>\n
\n
Split on Height<\/strong><\/h2>\n
\n
Split on Class<\/strong><\/h2>\n
\n
\n
ii)<\/strong> Entropy<\/strong><\/h2>\n
![\"\"](\"https:\/\/miro.medium.com\/v2\/resize:fit:351\/1*JA7aAIdMrBjTakoLn9I_sg.png\")
<\/figure>Calculating entropy for a split<\/strong><\/h2>\n
\n
\n
Regularization of Hyperparameters<\/strong><\/h1>\n
i)<\/strong> Min_samples_split<\/strong><\/h2>\n
ii)<\/strong> Min_samples_leaf<\/strong><\/h2>\n
iii)<\/strong> Max_depth<\/strong><\/h2>\n
iv)<\/strong> Max_leaf_nodes<\/strong><\/h2>\n
v)<\/strong> Max_features<\/strong><\/h2>\n
vi)<\/strong> Min_weight_fraction_leaf<\/strong><\/h2>\n
![\"\"](\"https:\/\/miro.medium.com\/v2\/resize:fit:700\/1*x1FhLOgO8NgpVEVoiouGyA.png\")
<\/figure>Pruning in Tree-based Algorithms<\/strong><\/h1>\n
max_depth<\/code> uses a greedy approach and will recursively look for the best split, hence an exponential growth in the nodes. A node whose children are all leaf nodes is considered unnecessary if the purity improvement it provides isn\u2019t statistically significant.<\/p>\nRandom Forest and Ensemble Learning<\/strong><\/h1>\n
Conclusion<\/strong><\/h1>\n