I'm a second-year student at the University of Texas at Austin with an interest in engineering, math, and machine learning.
Decision trees are useful tools for classification problems where the features take on a finite category as well. Let’s take a classification system that determines whether an image of a fruit is an orange or not. The system takes in the following features as input: presence of a stem, color, and shape. Each of these features takes in a finite number of possible values (presence of a stem is either yes or no; color is either green or orange; shape is either long or round). A decision tree model may come up with the following decision tree for this classification task:
The topmost node is called the root node whereas the ending box nodes are called decision nodes.
DECISION TREE LEARNING
There are a couple of steps required for the algorithm to learn and construct a good decision tree.
Decide which features should be split on in each node.
- Decision tree learning algorithms split on certain features based on which ones maximize purity (i.e., split the dataset as clearly as possible so one category is on one side and another category is on another side).
Decide when to stop splitting. There are a couple of options here:
Either you can stop splitting when a node is fully (100%) one class/category, or
You can stop splitting when splitting a node further would cause the tree to exceed some maximum depth (i.e., you can set a maximum limit). Limiting the depth of a tree is often helpful to prevent overfitting (the larger the tree, the greater risk there is of it becoming high variance).
You can also stop splitting when improvements in the purity score are below a certain threshold. In other words, splitting another node is not going to improve the performance of the model significantly.
How do you make each of these decisions? You will use something known as the entropy criteria.
entropy and purity
We use a metric called entropy to determine purity. Entropy is a measure of the impurity of a set of data.
p1 is the fraction of the examples that are classified as 1.
Entropy (H) is highest when there is a 50-50 split within the examples and lowest when there is a 100-0 or 0-100 split. As entropy increases, purity decreases.
H(p1) = -p1log2(p1) - p0log2(p0)
where
p0 = 1 - p1
information gain
The decision of which feature to split on is based on which feature reduces entropy (or maximizes purity) the most. The minimization of entropy is known as information gain. When comparing decision trees to select the best one, we take the weighted averages of the entropies of each of the sub-branches of the decision tree. We take a weighted average because the importance of whether the branch is impure or not depends on how many examples are in that branch. By subtracting the weighted average from the entropy had we not split at all (unweighted overall H(p1)), we get the reduction in entropy, otherwise known as information gain.
information gain = H(p1root) - (wleftH(p1left) + wrightH(p1right))
Where p1node/sub-branch is (# of positive examples)/(number of examples in the sub-branch) and wbranch is (# of examples in the sub-branch)/(# of total examples in the data set). H(p1left) and H(p1right) are the entropies at the left and the right branches resulting from the split.
Our goal is to maximize reduction in entropy (in other words, our goal is for entropy to be as close to 0 as possible because if entropy is 0, it means that the split was a clean split that divided the data into two subsets containing data of two different categories (i.e., all of one category in one subset and all of the other category in the other subset). To ensure that our split is as clean as possible, we need to choose the decision tree model that has the least/minimum entropy compared to the other possible decision tree structures we have. Thus, we will choose that model that has the most information gain (most reduction in entropy)).
Determining when to stop splitting
Information gain can also be a useful metric for determining when to stop. If the entropy is not reducing significantly with each split added into the decision tree model, it is probably wise to stop splitting further and leave the decision tree as is–it is not going to get significantly better with the addition of another decision node.
decision tree learning
So how does a decision tree learn?
Starts with all examples at the root node of the tree or subtree
Calculates information gain for all possible features to split on and picks the one with the highest information gain
Splits dataset of the tree/subtree according to the selected feature and creates left and right branches
This is very much a recursive process that repeats for each subtree until the stopping point (the node is fully composed of one singular class or we have reached a very small information gain or we have reached a maximum depth for the tree).
multicategorical features and one-hot encoding
So far, we’ve assumed that the features can only take on one of two categories. What if our features could be one of many categories? How would we construct our decision tree?
It turns out that by deconstructing the multi-categorical features, we can turn them back into binary classification features. Let’s say you add another category to one of your features, color, from the previous orange example. Before, we only had two categories–orange and green. However, to accommodate for varieties of oranges such as blood oranges, you decide to add another possible value for this feature–red. Thus, the feature color can now take on one of three different categories: orange, red, and green. To turn this feature binary again, you can deconstruct the different categories into their own features. Thus, instead of having an overarching “color” feature, we now have three features entailing the following: (1) is the object orange in color? (2) is the object red in color? (3) is the object green in color? Each of these features is binary because it can have one of only two answers: yes or no. Thus, by deconstructing this multicategorical feature of color, we are back to a problem similar to what we have solved before. This kind of deconstruction is called a one-hot encoding since only one of the “color features” will be 1 (hot) at a time. In summary, in the case that we have a multicategorical feature that can take on k values, we create k new binary features that are 0 or 1 valued. Note that this technique can also be used on regular classification (using logistic regression).
But what about features that are not categorical and take in a numerical input?
decision trees and continuous-valued features
If you have a feature with continuous values, there is an extra step that you must take. First, you have set a threshold for the continuous values (i.e., anything greater than or equal to the threshold will be considered positive/value of 1, and anything less than the threshold will be considered the negative case/value of 0). In other words, we have to convert this continuous feature into a binary feature by setting a threshold/boundary. What value you set the threshold to be matters a lot and can ultimately influence the information gain. Thus, you first have to try different values for the threshold to determine the optimal value, then proceed as usual (determine which feature to split on based on the highest information gain). The values you try can be the n-1 midpoints between the n examples as possible splits, and find the split that gives the highest information gain. Thus, the extra step was essentially “prepping” this feature to be a binary feature in a way that maximizes information gain. Once this feature is “ready”, we can treat it as any other binary feature and proceed as usual.
What about multiclass classification with decision trees? Is this possible?
multiclass classification trees
While it may not be the best solution, you can indeed use decision trees for multiclass classification. Just as we have converted multiclass problems into binary problems above, we can do the same here. As we know, each node of the tree represents a question with a binary answer (unless it's a leaf node, which yields the output class). The tree then splits the observations according to the answer to the question asked in the decision node. If you want the model to be able to output multiple different classes, the second-to-last layer can differentiate between multiple classes. You will then end up with multiple leaf nodes, each of them outputting a different class (there will be repeats as well for examples that traverse the tree differently but should be put in the same category at the end of the day).
regression trees
So far, we’ve only talked about decision trees for classification tasks. What about when we want to be able to predict a number?
The output will be an average of the examples that are in the same final subtree.
The feature to split on is determined by which feature yields the least variance (how widely a set of numbers varies) rather than the least entropy.
