Decision trees are widely used models for classification and regression tasks.
Imagine you want to distinguish between the following four animals: bears, hawks, penguins, and dolphins. Your goal is to get to the right answer by asking as few questions as possible. You might start off by asking whether the animal has feathers, a question that narrows down your possible animals to just two. If the answer is “yes” you can ask another question that could help you distinguish between hawks and penguins.
Building decision trees
Learning a decision tree means learning the sequence of if/else questions that gets us to the true answer most quickly. In the machine learning setting, these questions are called tests (not to be confused with the test set, which is the data we use to test to see how generalizable our model is).
To build a tree, the algorithm searches over all possible tests and finds the one that is most informative about the target variable. Splitting the dataset vertically at x[1]=0.0596 yields the most information; it best separates the points in class 1 from the points in class 2. The top node, also called the root, represents the whole dataset, consisting of 75 points belonging to class 0 and 75 points belonging to class 1. The split is done by testing whether x[1] <= 0.0596 is indicated by a black line. If the test is true, a point is assigned to the left node, which contains 2 points belonging to class 0 and 32 points belonging to class 1. Otherwise, the point is assigned to the right node, which contains 48 points belonging to class 0 and 18 points belonging to class 1. These two nodes correspond to the top and bottom regions. Even though the first split did a good job of separating the two classes, the bottom region still contains points belonging to class 0, and the top region still contains points belonging to class 1. We can build a more accurate model by repeating the process of looking for the best test in both regions.
For continuous features, the decisions are comparisons with a threshold value:
Then each node (subset) is recursively partitioned with a new decision:
The process stops when we have only “pure” leaves in the tree, i.e. one of the counts is zero:
This recursive process yields a binary tree of decisions, with each node containing a test. Alternatively, you can think of each test as splitting the part of the data that is currently being considered along one axis. This yields a view of the algorithm as building a hierarchical partition. As each test concerns only a single feature, the regions in the resulting partition always have axis-parallel boundaries. The recursive partitioning of the data is repeated until each region in the partition (each leaf in the decision tree) only contains a single target value (a single class or a single regression value). A leaf of the tree that contains data points that all share the same target value is called pure.
A prediction on a new data point is made by checking which region of the partition of the feature space the point lies in, and then predicting the majority target (or the single target in the case of pure leaves) in that region. The region can be found by traversing the tree from the root and going left or right, depending on whether the test is fulfilled or not. It is also possible to use trees for regression tasks, using exactly the same technique. To make a prediction, we traverse the tree based on the tests in each node and find the leaf the new data point falls into. The output for this data point is the mean target of the training points in this leaf.
Entropy
To define most information, or best separation rigorously, we need the concept of entropy
We define the entropy of a set with two classes:
The total number of points is N.
There are m points of class 0 and n points of class 1.
We have m + n = N.
p = m/N and q = n/N. We have p + q = 1 (normalization).
E = -p·log2p -q·log2q
In practice, either entropy or a related measure, the Gini impurity are used. Scikit-learn’s DecisionTreeClassifier supports both:
we can claculate entropy in python as the following:
Controlling the complexity of decision trees
Typically, building a tree as described here and continuing until all leaves are pure leads to models that are very complex and highly overfit to the training data. The presence of pure leaves means that a tree is 100% accurate on the training set; each data point in the training set is in a leaf that has the correct majority class.
There are two common strategies to prevent overfitting: stopping the creation of the tree early (also called pre-pruning) or building the tree but then removing or collapsing nodes that contain little information (also called post-pruning or just pruning). Possible criteria for pre-pruning include limiting the maximum depth of the tree, limiting the maximum number of leaves, or requiring a minimum number of points in a node to keep splitting it.
Decision trees in scikit-learn are implemented in the DecisionTreeRegressor and DecisionTreeClassifier classes. scikit-learn only implements pre-pruning, not post-pruning.
Let’s explore how to model breast cancer data using decision trees:
Import Libraries
Load data
Splitting dataset into train and test
Build the decision tree model clf1
Accuracy score
As expected, the accuracy on the training set is 100% — because the leaves are pure, the tree was grown deep enough that it could perfectly memorize all the labels on the training data. The test set accuracy is slightly worse than for the linear models we looked at previously, which had around 95% accuracy. If we don’t restrict the depth of a decision tree, the tree can become arbitrarily deep and complex. Unpruned trees are therefore prone to overfitting and not generalizing well to new data. Now let’s apply pre-pruning to the tree, which will stop developing the tree before we perfectly fit the training data. One option is to stop building the tree after a certain depth has been reached. Here we set max_depth=4, meaning only four consecutive questions can be asked. Limiting the depth of the tree decreases overfitting. This leads to a lower accuracy on the training set, but an improvement on the test set:
Model optimization by building decision tree clf2 (max_depth=4)
Accuracy
Limiting the depth of the tree decreases overfitting. As a result, we have lower accuracy on the training set, but an improvement on the test set. Great!
Analyzing decision trees
We can visualize the tree using the export_graphviz function from the tree module. This writes a file in the .dot file format, which is a text file format for storing graphs. We set an option to color the nodes to reflect the majority class in each node and pass the class and features names so the tree can be properly labeled:
Feature importance
Instead of looking at the whole tree, which can be taxing, there are some useful properties that we can derive to summarize the workings of the tree. The most commonly used summary is feature importance, which rates how important each feature is for the decision a tree makes. It is a number between 0 and 1 for each feature, where 0 means “not used at all” and 1 means “perfectly predicts the target.” The feature importances always sum to 1:
We can visualize the feature importances in a way that is similar to the way we visualize the coefficients in the linear model.
Here we see that the feature used in the top split (“worst radius”) is by far the most important feature.
Conclusion
Parameters that control model complexity in decision trees are the pre-pruning parameters that stop the building of the tree before it is developed. Usually, picking one of the pre-pruning strategies — setting either max_depth, max_leaf_nodes, or min_samples_leaf, is sufficient to prevent overfitting.
Decision trees have two advantages over many of the algorithms we’ve discussed so far: the resulting model can easily be visualized and understood by nonexperts (at least for smaller trees), and the algorithms are completely invariant to scaling of the data. As each feature is processed separately, and the possible splits of the data don’t depend on scaling, no preprocessing like normalization or standardization of features is needed for decision tree algorithms. In particular, decision trees work well when you have features that are on completely different scales, or a mix of binary and continuous features.
The main downside of decision trees is that even with the use of pre-pruning, they tend to overfit and provide poor generalization performance. Therefore, in most applications, the ensemble methods are usually used in place of a single decision tree.
