Understanding Decision Trees for Classification

1. What is a Decision Tree?

At its core, a decision tree is a model that makes predictions by asking a series of simple questions, much like how we make decisions in daily life. Imagine you're deciding whether to approve a small loan. You might ask: "Is the applicant's credit score above 650?" If yes, "Is their annual income above $50,000?" If yes, you might approve the loan. This sequence of questions forms a tree-like structure.

In machine learning, a Decision Tree is a supervised learning model that uses a tree structure to go from observations about an item (represented in the branches) to conclusions about the item's target value (represented in the leaves). For classification tasks, it learns a set of if-then-else rules from the data to predict which category a new data point belongs to.

Let's begin with a short reading that formalizes this definition.

2. The Anatomy of a Decision Tree

To discuss decision trees in an exam, you need to be familiar with their specific components. The structure is quite intuitive and consists of three main parts.

Let's watch a very short video clip that defines these parts, and then we will solidify the definitions with a quick reading.

Now, let's get the formal definitions for these terms.

To summarize these crucial terms:

• Root Node: The single topmost node that represents the entire dataset. It's the starting point of the tree.
• Decision Node (or Internal Node): A node that represents a "test" or a "question" on a specific feature. It splits into two or more branches.
• Branch (or Edge): A link between nodes that represents the outcome of a test (e.g., 'Sunny', 'Overcast', 'Rainy').
• Leaf Node (or Terminal Node): The endpoint of a branch. It represents the final decision or class prediction. A leaf node does not split any further.

3. Making Predictions with a Decision Tree

Once a decision tree is built, using it to classify a new data point is straightforward. You start at the root node, answer the question it poses, and follow the branch corresponding to your answer. You repeat this process until you reach a leaf node. The label of that leaf node is your prediction.

Consider the following dataset and the decision tree that was learned from it.

Let's classify a new day with the following weather conditions: Outlook=Sunny, Humidity=High, Windy=True.

1. Start at the Root Node ("Outlook"). Our value is Sunny, so we follow the leftmost branch.
2. We arrive at a Decision Node ("Windy"). Our value is True, so we follow the right branch.
3. We reach a Leaf Node with the prediction: No.

The model predicts we will not play golf on this day. The path Outlook=Sunny -> Windy=True -> No represents a single classification rule learned from the data.

For a more formal walkthrough of this process, the following reading from a University of Toronto lecture note is helpful.

4. The High-Level Learning Process

Now for the most important part: How does the algorithm build the tree from a dataset? In our last lesson, we defined concept learning as a search. The decision tree learning algorithm is a specific method for conducting this search.

The process is greedy and recursive.

• Greedy: At each step, the algorithm chooses the best possible split to make right now, based on how well it separates the data. It doesn't look ahead to see if this split will lead to a better overall tree in the long run.
• Recursive: The algorithm applies the same splitting logic over and over again to the new subsets of data created by each split, until a stopping condition is met.

The "best" split is the one that does the best job of separating the data into pure groups—that is, groups where most of the data points belong to a single class. This is measured using metrics like Entropy or Gini Impurity, which we will explore in a future lesson. For now, just know the goal is to ask the question that provides the most clarity.

This video gives an excellent conceptual overview of how the algorithm selects the first, best split.

To formalize this for your exam, here is the step-by-step process for building a decision tree:

The stopping criteria are a critical part of the algorithm. The recursion stops and a leaf node is created when one of these conditions is met:

1. All samples in a node belong to the same class. The node is perfectly pure, so no further splits are needed.
2. There are no more features left to split on. Even if the node is impure, we have no more questions to ask.
3. There are no examples left in a node. This can happen if a specific combination of feature values doesn't exist in the training data.
4. A pre-defined limit is reached. For example, a maximum tree depth or a minimum number of samples required to split a node. This is a key technique to prevent a problem called overfitting, which is the topic of our very next lesson.

In cases 2 and 3, where the leaf node is impure, the prediction is typically the majority class of the samples in that node.

Conclusion

In this lesson, we demystified our first major machine learning model. We moved from the abstract theory of Concept Learning to the practical mechanics of a Decision Tree.

Here are the key takeaways for your exam:

• A Decision Tree is a supervised learning model that uses a flowchart-like tree structure to make classifications based on a series of if-then-else rules.
• Its main components are the Root Node (start), Decision Nodes (questions), and Leaf Nodes (predictions).
• To classify a new instance, you traverse the tree from the root to a leaf by answering the questions at each node.
• The learning process is a greedy, recursive algorithm that repeatedly splits the data by selecting the feature that results in the "purest" possible child nodes.
• The algorithm stops when nodes become pure or other predefined stopping conditions are met.

In our next lesson, we will use the decision tree as a case study to explore two of the most fundamental concepts in machine learning: Overfitting and Underfitting. You'll learn what happens when a tree learns the training data too well and how the stopping criteria we just discussed can help prevent it.