Decision Trees: Predicting with Splits

The Anatomy of a Decision Tree

At its core, a decision tree is an intuitive model that makes predictions by asking a series of sequential, yes/no questions about the data. Think of it as a structured game of "20 Questions."

Let's establish the key terminology.

To summarize the key parts:

• Root Node: The top-most node, which represents the entire dataset before any splits are made.
• Decision Nodes (or Internal Nodes): These are the nodes where the data is split based on a question or "condition" about a specific feature.
• Branches: The links connecting the nodes, representing the outcome of a decision (e.g., True or False).
• Leaf Nodes (or Terminal Nodes): The final nodes at the bottom of the tree. They do not split any further and represent the final classification decision for data points that reach them.

Let's look at a fully trained decision tree to see these components in action.

How a Trained Tree Makes Predictions

Once a tree is built, making a prediction for a new data point is straightforward. You start at the root node and answer the question it poses. Based on your answer, you follow the corresponding branch (left for 'True', right for 'False') to the next node. You repeat this process, traversing down the tree until you reach a leaf node. The prediction is simply the class assigned to that leaf.

The prediction at a leaf node is determined by the training data that ended up in that leaf during the model-building process. Typically, the leaf's prediction is the majority class of the samples it contains. If a leaf node contains 8 samples of 'Class A' and 2 of 'Class B', its prediction for any new data point that lands there will be 'Class A'.

The Core Task: Finding the Best Splits

You've seen how a tree makes a prediction, but the crucial question is: how does the algorithm learn which questions to ask and in what order? How does it decide that petal length (cm) <= 2.45 is the best possible first question to ask?

The algorithm builds the tree using a greedy, top-down approach.

• Top-down: It starts at the top (the root) and recursively splits the data.
• Greedy: At each step (each node), it chooses the best possible split at that moment to create the most separation between the classes. It doesn't look ahead to see if a less optimal split now could lead to a better overall tree later.

The "best" split is the one that results in the most purity in the child nodes. A node is "pure" if it contains samples from only one class. The goal of a split is to take an impure parent node (containing a mix of classes) and produce child nodes that are more pure than the parent.

To quantify purity, algorithms use a metric. The two most common are:

1. Gini Impurity
2. Entropy and Information Gain

Scikit-learn's DecisionTreeClassifier uses an optimized version of the CART algorithm, which uses Gini Impurity. We will focus on this metric.

Gini Impurity

Gini Impurity is a measure of how often a randomly chosen element from the set would be incorrectly labeled if it were randomly labeled according to the distribution of labels in the subset.

• A Gini score of 0 represents perfect purity (all elements belong to one class).
• A Gini score of 0.5 represents maximum impurity for a two-class problem (elements are split 50/50 between classes).

The algorithm calculates the Gini Impurity for every possible split on every feature. The split with the lowest weighted Gini Impurity is chosen.

The following video provides an exceptionally clear, step-by-step guide to building a tree from scratch by calculating Gini Impurity.

Let's reinforce this with a static example.

Building the Tree Recursively

The process we just examined for the root node is then applied again and again.

1. Start with the entire dataset at the root node.
2. Find the feature and threshold that produces the best split (lowest Gini Impurity).
3. Split the data into two child nodes based on that condition.
4. For each child node, repeat Step 2 and 3. This node is now treated as a new "parent" to its own children.
5. This process continues until a stopping condition is met. This could be:
   • A node becomes perfectly pure (Gini = 0).
   • The tree reaches a pre-defined maximum depth.
   • A node has fewer samples than a specified minimum.

Let's watch the rest of the StatQuest video to see this recursive process complete our example tree.

By recursively applying this simple, greedy logic, the decision tree algorithm partitions the entire feature space into a set of decision rules that effectively separates the classes in the training data.

Conclusion

In this lesson, you have unpacked the core logic of decision trees. You have moved beyond seeing them as just a diagram and now understand the precise mechanism they use to make predictions.

Key Takeaways:

• Decision trees classify data by routing it through a sequence of if-then-else questions about its features, starting from a root node and ending at a leaf node.
• The prediction at a leaf node is the majority class of the training samples that end up there.
• The tree is built using a greedy, top-down recursive algorithm.
• At each node, the algorithm chooses the feature and split-point that most effectively increases the purity of the resulting child nodes.
• This "best split" is found by minimizing a cost function, most commonly the Gini Impurity.

Preview of the Next Lesson:
With this theoretical foundation firmly in place, you are ready for the practical application. In the next lesson, you will learn how to train and visualize a decision tree classifier using scikit-learn. You will see just how easily this complex logic can be implemented in a few lines of Python code.